机器学习算法 01 —— K-近邻算法(数据集划分、归一化、标准化)

文章目录系列文章K-近邻算法1 什么是K-仅邻算法1.1 K-近邻算法(KNN)概念1.2 举例说明K-近邻算法1.3 K-近邻算法流程总结2 K-近邻算法API初步使用2.1 Scikit-learn工具介绍2.2 K-近邻算法API3 距离公式3.1 距离公式基本性质3.2 常见的举例公式欧式距离(Euclidean Distance)曼哈顿距离(Manhattan Distance)切⽐雪夫

来一碗锅巴洋芋

9745人浏览 · 2021-08-11 20:10:58

来一碗锅巴洋芋 · 2021-08-11 20:10:58 发布

系列文章

机器学习算法 01 —— K-近邻算法(数据集划分、归一化、标准化)

机器学习算法 02 —— 线性回归算法(正规方程、梯度下降、模型保存)

机器学习算法 03 —— 逻辑回归算法(精确率和召回率、ROC曲线和AUC指标、过采样和欠采样)

机器学习算法 04 —— 决策树(ID3、C4.5、CART，剪枝，特征提取，回归决策树)

机器学习算法 05 —— 集成学习(Bagging、随机森林、Boosting、AdaBost、GBDT)

机器学习算法 06 —— 聚类算法(k-means、算法优化、特征降维、主成分分析PCA)

机器学习算法 07 —— 朴素贝叶斯算法(拉普拉斯平滑系数、商品评论情感分析案例)

机器学习算法 08 —— 支持向量机SVM算法(核函数、手写数字识别案例)

机器学习算法 09 —— EM算法(马尔科夫算法HMM前置学习，EM用硬币案例进行说明)

机器学习算法 10 —— HMM模型(马尔科夫链、前向后向算法、维特比算法解码、hmmlearn)

K-近邻算法

学习目标：

掌握K-近邻算法实现过程
知道K-近邻算法的距离公式
知道K-近邻算法的超参数K值以及取值问题
知道kd树实现搜索的过程
应⽤KNeighborsClassifier实现分类
知道K-近邻算法的优缺点
知道交叉验证实现过程
知道超参数搜索过程
应⽤GridSearchCV实现算法参数的调优

1 什么是K-近邻算法

用下面这个图来简单说明就是，你所处的位置距离小明最近，那么你就被认为也处于地区A。即根据你最近的“邻居”来推断你所属的类别。

在这里插入图片描述

1.1 K-近邻算法(KNN)概念

K Nearest Neighbor算法⼜叫KNN算法，这个算法是机器学习⾥⾯⼀个⽐较经典的算法，总体来说KNN算法是相对⽐较容易理解的算法。

定义：如果⼀个样本在特征空间中的k个最相似**(即特征空间中最邻近)**的样本中的⼤多数属于某⼀个类别，则该样本也属于这个类别。上面的例子里K取的是1，如果k取3，那么在最近的3个地区中取众数，距离最近的3个邻居是小明、小呆、小绿，而小呆和小绿都是地区B，所以你属于地区B。
距离公式：两个样本的距离可以通过如下公式计算（又叫欧式距离）。关于距离公式会在后面说明。

在这里插入图片描述

1.2 举例说明K-近邻算法

下面通过一个例子来说明：通过K-近邻算法预测一部电影的类型。

现在已知前8部电影的类型，根据它们的各种镜头来判断第9部电影是什么类型。根据图表我们知道，喜剧片搞笑镜头较多，动作片打斗镜头较多，爱情片拥抱镜头较多。

现在对《唐人街探案》的三种镜头和其他电影的三种镜头运用距离公式

假设我们K取5（即最近的5部电影），根据众数，这五部电影中有3部喜剧，1部爱情，所以得出结果《唐人街探案》是喜剧片。

1.3 K-近邻算法流程总结

计算已知类别数据集中的点与当前点之间的距离
按距离递增次序排序
选取与当前点距离最⼩的k个点
统计前k个点所在的类别出现的频率
返回前k个点出现频率最⾼的类别作为当前点的预测分类

2 K-近邻算法API初步使用

2.1 Scikit-learn工具介绍

Science Kit Learn，包含了许多知名机器学习算法的实现，内置了很多数据集，scikit-learn文档比较完善且容易上手，因此对于初学者比较友好。要安装使用scikit-learn，需要先安装numpy、scipy等库，所以推荐直接安装Anaconda，它专门管理Python库，内置了许多科学库，可以参考我另外的博客 Python包/库/环境管理 —— Anaconda、PyCharm导入Anaconda的包。

2.2 K-近邻算法API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)，n_neighbors就是K值，默认是5。

下面简单举例使用，这里推荐用PyCharm，jupyter主要是一些探索性工作，PyCharm更适合一个项目开发。同时，由于只是简单使用，所以机器学习开发流程中的一些布置就省略了。

获取数据集
数据基本处理（该案例中省略）
特征⼯程（该案例中省略）
机器学习
模型评估（该案例中省略）

from sklearn.neighbors import KNeighborsClassifier

# 1. 获取数据集（这里是我们自己构造一个简单的）
x = [[0], [1], [3], [5]] # 特征值
y = [0, 0, 1, 1] # 目标值

# 4. 机器学习
# 4.1 实例化一个估计器
estimator = KNeighborsClassifier(1) # K 取1
# 4.2 模型训练
estimator.fit(x, y) # 简单来说，fit就是求得训练集X的均值，方差，最大值，最小值,这些训练集X固有的属性。

# 数据预测
result = estimator.predict([[6]])
print(result) # 结果 1，因为6距离【5】最近，而【5】的结果是1，所以6归类为1

看到这里，你肯定会有一些疑惑：

距离公式除了欧氏距离外，还有哪些公式可以使用？
K值应该如何选择？
API中的其他参数有什么含义？

这里后面将会一一进行解答。

3 距离公式

3.1 距离公式基本性质

在机器学习过程中，对于函数 dist(., .)，若它是"距离度量" (distance measure)，则需满⾜⼀些基本性质:

⾮负性： dist(X , X ) >= 0 ；
同⼀性：dist(x , x ) = 0。当且仅当 X = X ；
对称性： dist(x , x ) = dist(x , x )；
直递性： dist(x , x ) <= dist(x , x ) + dist(x , x )

直递性常被直接称为“三⻆不等式”。

3.2 常见的距离公式

欧式距离(Euclidean Distance)

欧⽒距离是最容易直观理解的距离度量⽅法，我们⼩学、初中和⾼中接触到的两个点在空间中的距离⼀般都是指欧⽒距离。

# 点A、B、C、D
X=[[1,1],[2,2],[3,3],[4,4]]; 
经计算得: AB距离-1.4142、AC距离-2.8284、AD距离-4.2426、BC距离-1.4142、BD距离-2.8284、CD距离-1.4142

曼哈顿距离(Manhattan Distance)

在曼哈顿街区要从⼀个⼗字路⼝开⻋到另⼀个⼗字路⼝，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。下图中，从A到B的三条线路距离是相同的。

# A、B、C、D
X=[[1,1],[2,2],[3,3],[4,4]]; 
经计算得: AB=2、AC=4、AD=6、BC=2、BD=4、CD=2

切⽐雪夫距离 (Chebyshev Distance)

国际象棋中，国王可以直⾏、横⾏、斜⾏，所以国王⾛⼀步可以移动到相邻8个⽅格中的任意⼀个。国王从格⼦(x1,y1)⾛到格⼦(x2,y2)最少需要多少步？这个距离就叫切⽐雪夫距离。

X=[[1,1],[2,2],[3,3],[4,4]]; 
经计算得: d = 1 2 3 1 2 1

闵可夫斯基距离(Minkowski Distance)

闵⽒距离不是⼀种距离，⽽是⼀组距离的定义，是对多个距离度量公式的概括性的表述。

两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

其中p是⼀个变参数：

当p=1时，就是曼哈顿距离；
当p=2时，就是欧⽒距离；
当p→∞时，就是切⽐雪夫距离。

根据p的不同，闵⽒距离可以表示某⼀类/种的距离。

⼩结：

闵⽒距离，包括曼哈顿距离、欧⽒距离和切⽐雪夫距离，都存在明显的缺点:

例如：⼆维样本(身⾼[单位:cm]，体重[单位: ])，现有三个样本：a(180,50)，b(190,50)，c(180,60)。a与b的闵⽒距离（⽆论是曼哈顿距离、欧⽒距离或切⽐雪夫距离）等于a与c的闵⽒距离。但实际上身⾼的10cm并不能和体重的10kg划等号。

闵⽒距离的缺点：
- 将各个分量的“单位”同等看待了；
- 没有考虑到各个分量的分布（期望，⽅差等）可能是不同的。

3.3 “连续属性”和“离散属性”的距离计算

我们常将属性划分为"连续属性和"离散属性"，前者在定义域上有⽆穷多个可能的取值，后者在定义域上是有限个取值。

若属性值之间存在序关系，则可以将其转化为连续值，例如：身⾼属性“⾼”“中等”“矮”，可转化为{1, 0.5, 0}。
- 闵可夫斯基距离可以⽤于有序属性。
若属性值之间不存在序关系，则通常将其转化为向量的形式，例如：性别属性“男” “⼥”，可转化为{(1,0),(0,1)}。

4 K值的选取

假如我们之前电影类型预测案例中的K值取1或者取6会发生什么问题呢？

K值过小：
- 容易受到异常点的影响
- 例如K=1，最近的是《美人鱼》喜剧片，但如果《美人鱼》在统计时不小心记录为爱情片，那么预测结果也会跟着出错。
K值过大：
- 容易出现样本均衡的问题
- 例如K=6，就会出现3部喜剧片和3部爱情片，此时预测结果无法得知。

K值选择问题，李航博⼠的⼀书「统计学习⽅法」上说：

选择较⼩的K值，就相当于⽤较⼩的领域中的训练实例进⾏预测，
- “学习”近似误差会减⼩，只有与输⼊实例较近或相似的训练实例才会对预测结果起作⽤，与此同时带来的问题是“学习”的估计误差会增⼤。
- 换句话说，K值的减⼩就意味着整体模型变得复杂，容易发⽣过拟合；
选择较⼤的K值，就相当于⽤较⼤领域中的训练实例进⾏预测，
- 其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增⼤。这时候，与输⼊实例较远（不相似的）训练实例也会对预测器作⽤，使预测发⽣错误。
- 且K值的增⼤就意味着整体的模型变得简单。
K=N（N为训练样本个数），则完全不⾜取，因为此时⽆论输⼊实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中⼤量有⽤信息。

概念解释

近似误差：
- 对现有训练集的训练误差，关注训练集，
- 如果近似误差过⼩可能会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较⼤偏差的预测。
- 模型本身不是最接近最佳模型。
估计误差：
- 可以理解为对测试集的测试误差，关注测试集，
- 估计误差⼩说明对未知数据的预测能⼒好，
- 模型本身最接近最佳模型。
过拟合：所建的机器学习模型或者是深度学习模型在训练样本中表现得过于优越，导致在测试数据集中表现不佳。
欠拟合：模型学习的太过粗糙，连训练集中的样本数据特征关系都没有学出来。

5 KD树

问题导入：在实现K-邻近算法时，主要考虑的问题是如何对训练数据快速进行K-邻近搜索（即找出最近的“邻居”），最简单的方法当然是线性扫描，将输入值与每一个训练数据进行距离计算，但这在训练数据量大时会非常耗时。

因此，为了提高KNN搜索效率，使用的是特殊存储结构，以减少计算距离的次数。

5.1 KD树介绍

KNN每次要预测一个点时，都需要计算这个点到训练数据集里每个点的距离，针对N个样本，每个样本有D个特征的数据集，这样的时间复杂度是O(DN²)。

KD树的原理：假如点A和点B距离很远，点B和点C距离很近，那么可以得出点A和点C距离也很远，在计算距离时就可以跳过点C。这样算法复杂度可以降低到O(DNlogN)。

KD树类似于二叉排序树，先对所有点进行大小排序，将中间的点作为根节点（事例里是黄点），将黄点上面的归为左子树，下面的归为右子树，然后再对这两个区域继续划分直到区域里没有点。分割的那条线叫超平面。（在一维里是点，二维里是线，三维里是面）

第一层是黄色根节点，第二层是红色，第三层是绿色，第四层是蓝色。

构造好树后，距离计算就类⽐“⼆分查找”：

给出⼀组数据：[9 1 4 7 2 5 0 3 8]，要查找8。如果挨个查找（线性扫描），那么将会把数据集都遍历⼀遍。⽽如果排⼀下序那数据集就变成了：[0 1 2 3 4 5 6 7 8 9]，按前⼀种⽅式我们进⾏了很多没有必要的查找，现在如果我们以5为分界点，那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。因此，根本就没有必要进⼊第⼀个簇，可以直接进⼊第⼆个簇进⾏查找。

5.2 KD树案例

下面通过一个例子来说明KD树的如何构造的。

树的建立

给定一个二维数据集：T={(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)}，将其构造成一个平衡KD树。其结果如下：

首先将x和y分开成两个维度，然后选择方差更大的那个维度找出中位数

第一维度 x：2、5、9、4、8、7
第二维度 y：3、4、6、7、1、2

由于第一维度 x的方差更大（肉眼观察，x的分散程度更高，方差就更大），所以选x来排序。

排序后	第一维度 x：2、4、5、7、8、9
中位数是5和7的平均值：6

由于中位数是6，接下来选择最接近中位数的点来作为根节点时，这里既可以选(5, 4)又可以选(7, 2)，它们x距离相同。这里选的是(7, 2)。

选择(7,2)，所以树的第一层是(7,2)
此时，根据排序，在7左边的有 2、4、5，在7右边的有8、9。
对应的点是 (2, 3)、(4, 7)、(5, 4)，(8, 1)、(9, 6)

接下来再对剩余的点进行划分，但这次是要根据第二维度y来找中位数。

左边的点的y排序：3、4、7，即点(2, 3)、(5, 4)、(4, 7)，此时中位数是4,所以第二层左子树根节点是(5, 4)

右边的点的y排序：1、6，即点(8, 1)、(9, 6)，此时中位数是5，随便选一个点(9, 6)作为根节点。

所以特征空间划分（图里面的线就是超平面）和KD树就是下面这样的：

6 鸢尾花种类预测案例

6.1 数据集介绍

Iris数据集是常⽤的分类实验数据集，由Fisher, 1936收集整理。Iris也称鸢尾花卉数据集，是⼀类多重变量分析的数据集。关于数据集的具体介绍：

通常一个领域的数据集选择是由该领域的行业专家来判断，不需要机器学习开发者来做。

加载数据集

sklearn.datasets加载数据集，它有两种方式：

sklearn.datasets.load_xx()：获取小规模数据集，sklearn本身就有，无需下载。
- 例如，这次使用的鸢尾花数据集sklearn.datasets.load_iris()
sklearn.datasets.fetch_xx(datahome=None)：获取大规模数据集，需要联网下载，参数datahome是下载到本地的位置，默认是~/scikit_learn_data/
- 例如sklearn.datasets.fetch_20newsgroups(data_home=None,subset=‘train’)，其中subset可取训练集’train’、测试集’test’、全部’all’
load和fetch返回的数据类型都是datasets.base.Bunch(字典格式)
- data：特征数据数组，是⼆维 numpy.ndarray 数组
- target：标签数组，是⼀维 numpy.ndarray 数组
- DESCR：数据描述
- feature_names：特征名,新闻数据，⼿写数字、回归数据集没有
- target_names：标签名

from sklearn.datasets import load_iris 
# 获取鸢尾花数据集 
iris = load_iris() 
print("鸢尾花数据集的返回值：\n", iris) 
# 返回值是⼀个继承⾃字典的Bench 
print("鸢尾花的特征值:\n", iris["data"]) 
print("鸢尾花的⽬标值：\n", iris.target) 
print("鸢尾花特征的名字：\n", iris.feature_names) 
print("鸢尾花⽬标值的名字：\n", iris.target_names) 
print("鸢尾花的描述：\n", iris.DESCR)

数据集可视化

下面通过seaborn来查看鸢尾花的数据分布情况，我另一篇博客有说明seaborn使用：机器学习入门 06 —— Seaborn使用

seaborn.lmplot() 用于绘制回归图，它会在绘制⼆维散点图时，⾃动完成回归拟合。
- sns.lmplot() ⾥的 x, y 分别代表横纵坐标的列名,
- data：数据集,
- hue：表示按照花的类别分类显示,
- fit_reg：是否进⾏线性拟合。

import seaborn as sns
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.datasets import load_iris, fetch_20newsgroups

# 获取数据
iris = load_iris()

# 把数据转换成DataFrame的格式
iris_d = pd.DataFrame(iris['data'], 
                      columns=['Sepal_Length', 'Sepal_Width', 'Petal_Length', 'Petal_Width'])
# 新增一列 种类(目标值target就是种类）
iris_d['Species'] = iris.target

def plot_iris(iris, col1, col2):
    sns.lmplot(x=col1, y=col2, data=iris, hue="Species", fit_reg=False)
    plt.xlabel(col1)
    plt.ylabel(col2)
    plt.title('鸢尾花种类分布图')
    plt.show()

plot_iris(iris_d, 'Petal_Width', 'Sepal_Length')

数据集划分

通常机器学习的数据集会被划分为两个部分：

训练数据：⽤于训练、构建模型
测试数据：在模型检验时使⽤，⽤于评估模型是否有效

划分比例大致分为：

训练集：70%、80%、75%
测试集：30%、20%、25%

sklearn.model_selection.train_test_split(arrays, *options)

参数：
- arrays：数据集，或者传入x特征值、y目标值。（这里由于鸢尾花数据集是自带的，就不需要区分特征值和目标值）
- test_size：测试集的⼤⼩，例如 0.7，那么测试集就占总数据的70%
- random_state：随机数种⼦，不同的种⼦会造成不同的随机采样结果。相同的种⼦返回结果也相同。
返回值：训练集的特征值x_train, 测试集的特征值x_test, 训练集的目标值y_train, 测试集的目标值y_test

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 1、获取鸢尾花数据集
iris = load_iris()
# 对鸢尾花数据集进⾏分割
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)
print("x_train:\n", x_train.shape)
# 随机数种⼦
x_train1, x_test1, y_train1, y_test1 = train_test_split(iris.data, iris.target, random_state=6)
x_train2, x_test2, y_train2, y_test2 = train_test_split(iris.data, iris.target, random_state=6)
print("如果随机数种⼦不⼀致：\n", y_test == y_test1)  # 数组中，有False，也有True，因为可能随机到相同的
print("如果随机数种⼦⼀致：\n", y_test1 == y_test2)  # 全为True

6.2 特征预处理

什么是特征预处理

定义：通过一些转换函数将特征数据转换成更适合算法模型的特征数据的过程（主要是归一化和标准化）。例如下图，将特征1234都转换到一个范围里。（这就是归一化）

为什么要特征预处理

特征的单位或者⼤⼩相差较⼤，或者某特征的⽅差相⽐其他的特征要⼤出⼏个数量级，容易影响（⽀配）⽬标结果，使得⼀些算法⽆法学习到其它的特征。所以，我们需要⽤到⼀些⽅法进⾏⽆量纲化，使不同规格的数据转换到同⼀规格。

归一化

定义：通过对原始数据进行变化，把数据映射到某个区间。（默认是[0, 1]，所以叫归一)

公式如下：

作⽤于每⼀列，max为⼀列的最⼤值，min为⼀列的最⼩值,那么X’’为最终结果，mx，mi分别为指定区间值默认mx为1,mi为0

前面那张图就是归一化，其中每个特征都套用了这个公式。90转换到1，就是 $x'=\frac{90-60}{90-60}$ 、 $x^{''} = x^{'} (1 - 0) + 0 = 1$ 。

代码实现归一化：

先实例化转换器对象MinMaxScaler(feature_range=(0, 1))，再调用转换器的fit_transform(X)方法进行转换。

import pandas as pd
from sklearn.preprocessing import MinMaxScaler

def minmax_demo():
    """
    归一化演示
    :return:None
    """
    data = pd.DataFrame({"特征1": [90, 60, 75],
                         "特征2": [2, 4, 3],
                         "特征3": [10, 15, 13],
                         "特征4": [40, 45, 46]})
    print(data)
    # 1. 实例化一个转换器对象;feature_range指定区间
    transfer = MinMaxScaler(feature_range=(0, 1))
    # 2. 调用转换器的fit_transform，开始转换
    data = transfer.fit_transform(data[["特征1", "特征2", "特征3", "特征4"]])
    print("归一化：\n", data)

minmax_demo()

标准化

如果数据中的异常点比较多，例如特征2中突然有个数据是100，这明显比其他数据大很多，那么归一化时就会对结果产生很大影响。因为归一化会受到最大和最小值影响，因此归一化的鲁棒性（稳定性）比较差，只适合传统精确的小数据场景。

标准化定义：通过对原始数据进⾏变换把数据变换到平均值为0,标准差为1范围内。对于标准化来说，如果出现异常点，由于具有⼀定数据量，少量的异常点对于平均值的影响并不⼤，从⽽⽅差改变较⼩。 更适合现代嘈杂大数据场景，因此常用的是标准化。

公式如下：

作⽤于每⼀列，mean为平均值，σ为标准差

这次我们把上面的特征2里的4改成100。

代码实现标准化：

先实例化转换器对象StandardScaler()，再调用转换器的fit_transform(X)方法进行转换。

import pandas as pd
from sklearn.preprocessing import StandardScaler

def stand_demo():
    """
    标准化演示
    :return:None
    """
    data = pd.DataFrame({"特征1": [90, 60, 75],
                         "特征2": [2, 100, 3],
                         "特征3": [10, 15, 13],
                         "特征4": [40, 45, 46]})
    print(data)
    # 1. 实例化一个转换器对象;
    transfer = StandardScaler()
    # 2. 调用转换器的fit_transform，开始转换
    data = transfer.fit_transform(data[["特征1", "特征2", "特征3", "特征4"]])
    print("标准化：\n", pd.DataFrame(data))
    print("每一列未转化特征值的平均值：", transfer.mean_)
    print("每一列未转化特征的方差：", transfer.var_)

stand_demo()

预处理的API—fit、fit_transform和transform的区别

fit()：该函数是求得训练集X的均值，方差，最大值，最小值等这些训练集X固有的属性。
transform()：在fit的基础上，进行标准化，降维，归一化等操作（看具体用的是哪个工具，StandardScaler就是标准化）
fit_transform()：fit_transform是fit和transform的组合，既包括了训练又包含了转换。
transform()和fit_transform()二者的功能都是对数据进行某种统一处理（比如标准化~N(0,1)，将数据缩放(映射)到某个固定区间，归一化，正则化等）
fit_transform(trainData)对部分数据先拟合fit，找到这部分数据的整体指标，如均值、方差、最大值最小值等等（根据具体转换的目的），然后对trainData进行转换，从而实现数据的标准化、归一化等等。

根据对之前部分trainData进行fit的整体指标，对剩余的数据（testData）使用同样的均值、方差、最大最小值等指标进行转换transform(testData)，从而保证train、test处理方式相同。所以，在预处理阶段一般都是这么用：

from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
sc.fit_tranform(X_train)
sc.tranform(X_test)

必须先用fit_transform(trainData)，之后再transform(testData)
如果直接transform(testData)，程序会报错
如果fit_transfrom(trainData)后，使用fit_transform(testData)而不transform(testData)，虽然也能归一化，但是两个结果不是在同一个“标准”下的，具有明显差异。(一定要避免这种情况)

6.3 流程实现

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm='auto')

n_neighbors：邻居数目，也就是K值
algorithm：指定使用什么算法
- auto：自动选择合适的
- brute：暴力搜索，也就是线性扫描，当训练集很⼤时，计算⾮常耗时。
- kd_tree：构造kd树存储数据以便对其进⾏快速检索的树形数据结构，在维数⼩于20时效率⾼。
- ball_tree：克服kd树⾼维失效⽽发明的，数据集的维度超过20时使用。

下面完整展示对鸢尾花种类预测的流程

# -*- coding = utf-8 -*-
# @Time : 2021/8/5 10:17 上午
# @Author : zcy
# @File : 4.iris_example.py
# @Software : PyCharm

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# K-近邻算法 —— 鸢尾花种类预测
# 实例数量：150（3个种类，0山鸢花、1变色鸢尾、2维吉尼亚鸢尾，每种各50个）
# 属性数量：4（数值型。萼片长度、萼片宽度、花瓣长度、花瓣宽度）

# 1. 获取数据集
iris = load_iris()

# 2. 数据基本处理 - 这里是只是把数据集划分为训练集和测试集
x_train, x_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=10)

# 3. 特征工程 - 特征预处理 标准化
transfer = StandardScaler()
x_train = transfer.fit_transform(x_train)
x_test = transfer.transform(x_test)  # 这里看前面特征预处理部分，有解释

# 4. 机器学习 - KNN
# 4.1 实例化一个估计器
estimator = KNeighborsClassifier(n_neighbors=5)
# 4.2 估计器训练
estimator.fit(x_train, y_train)

# 5. 模型评估
# 5.1 预测值结果输出
y_pre = estimator.predict(x_test)
print("预测值是：\n", y_pre)
print("预测值和真实值的对比：\n", y_pre == y_test)
# 5.2 准确率
score = estimator.score(x_test, y_test)
print("准确率：\n", score)

结果每次运行都是下面这样，因为在划分数据时指定了random_state=10，如果去掉该属性，那么每次结果都随机。

7 K-近邻算法优缺点

优点：

是一种非常典型的分类监督学习算法，可以解决多分类的问题。
适合类域交叉样本，适合大样本的自动分类
整体思想简单
重新训练的代价低
- 不会像其他算法一样需要有模型保存之类的操作，直接训练就完事儿了
精度高、对异常值不敏感、无数据输入假定。

缺点：

效率低，时间复杂度高、空间复杂度高
惰性学习，正是因为没有模型学习，所以效率更低
对不均衡的样本不擅长
- 例如一个班里大部分都是男生，极少数女生，那么预测一个插班生进来，一找邻居发现都是男生，就会预测成男生。
- 改进方法是对K临近点进行加权，也就是距离近的点的权值大，距离远的点权值小。
解释性不强，类别评分不是规格化
- 预测结果只是来自于对于测试数据最近的点的属性，整体上很难解释，也导致了很难进行后续的改进和发展；
- 其他算法的预测可能给出你一个百分比，让你很清晰的知道是什么情况，而KNN是直接给你结果。
计算量较大
- 每个待分类的样本都要计算它到全部点的距离，根据距离排序才能求得K个临近点。
- 改进方法是先对已知样本点进行剪辑，事先去除对分类作用不大的样本

8 模型调优—交叉验证与网格搜索

交叉验证：数据处理中把数据集划分为训练数据和测试数据，而交叉验证则再把训练数据划分为训练集和验证集。如下图，将训练数据分为4分，一份作为验证集，另外三分作为训练集。然后进行N次测试，每次都更换不同的验证集（下图是进行4次验证），最后把所有验证结果取平均值，作为最终结果。这就是N折交叉验证。（下图是4折交叉验证）

注意：交叉验证只是让被评估的模型更加可信，并不能提高最后的准确率。

超参数：在sklearn中需要我们手动指定的参数，例如K-近邻里的K值。

网格搜索：一个模型通常都会有超参数，例如K-近邻的K，我们可能预设不同的K值，然后根据结果确定最好的K值。但这个过程比较麻烦，要反复调用函数，而网格搜索就是预先设置好超参数，每组超参数都采取交叉验证进行评估，最后选出最优参数建立模型。

sklearn.model_selection.GridSearchCV(estimator, param_grid=None,cv=None)

estimator：估计器
param_grid：我们预设的超参数
cv：指定⼏折交叉验证
返回的结果对象特有属性：
- best_score__：在交叉验证中验证的最好结果
- best_estimator__：最好的参数模型
- cv_results_：每次交叉验证后的验证集准确率结果和训练集准确率结果

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# K-近邻算法 —— 鸢尾花种类预测
# 实例数量：150（3个种类，山鸢花、变色鸢尾、维吉尼亚鸢尾，每种各50个）
# 属性数量：4（数值型。萼片长度、萼片宽度、花瓣长度、花瓣宽度）

# 1. 获取数据集
iris = load_iris()

# 2. 数据基本处理 - 这里是只是把数据集划分为训练集和测试集
x_train, x_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=10)

# 3. 特征工程 - 特征预处理 标准化
transfer = StandardScaler()
x_train = transfer.fit_transform(x_train)
x_test = transfer.transform(x_test)  # fit_transform和transform的区别是 前者

# 4. 机器学习 - KNN
# 4.1 实例化一个估计器
estimator = KNeighborsClassifier() # 不指定K值了

# 4.2 模型选择与调优——⽹格搜索和交叉验证
# 准备要调的超参数
param_dict = {"n_neighbors": [1, 3, 5, 7]}  # 预设K为 1、3、5、7，最后会选择一个最好的参数
estimator = GridSearchCV(estimator, param_grid=param_dict, cv=5)  # 4折交叉验证

# 4.3 估计器训练
estimator.fit(x_train, y_train)

# 5. 模型评估
# 5.1 预测值结果输出
y_pre = estimator.predict(x_test)
print("预测值是：\n", y_pre)
print("预测值和真实值的对比：\n", y_pre == y_test)
# 5.2 准确率
score = estimator.score(x_test, y_test)
print("准确率：\n", score)
# 5.3 交叉验证和网格搜索的特有属性
print("在交叉验证中验证的最好结果：\n", estimator.best_score_)
print("最好的参数模型：\n", estimator.best_estimator_)
print("每次交叉验证后的准确率结果：\n", estimator.cv_results_)

9 实战案例：预测FaceBook签到位置

项目数据集来自Kaggle：https://www.kaggle.com/c/facebook-v-predicting-check-ins

为了方便下载，我也上传到CSDN里了（免积分）：https://download.csdn.net/download/qq_39763246/21002651

本次⽐赛的⽬的是预测⼀个⼈将要签到的地⽅。为了本次⽐赛，Facebook创建了⼀个虚拟世界，其中包括10公⾥10 公⾥共100平⽅公⾥的约10*万个地⽅。对于给定的坐标集，您的任务将根据⽤户的位置，准确性和时间戳等预测⽤户下⼀次的签到位置。数据被制作成类似于来⾃移动设备的位置数据。请注意：您只能使⽤提供的数据进⾏预测。

数据集情况：

id：签⼊事件的id 
x y：坐标 
accuracy: 准确度，定位精度 
time: 时间戳 
place_id: 签到的位置，这也是你需要预测的内容

步骤分析：

对于数据做⼀些基本处理
- 1 缩⼩数据集范围 DataFrame.query() ，因为数据量很大，为了节省时间，就减少一些数据。
- 2 选取有⽤的时间特征。特征time是时间戳，不是常见的日期格式，将其转换下。
- 3 将签到位置少于n个的⽤户删除。每一行都是一个用户签到记录，每行的place_id是该用户签到的地区编号，有些地区编号可能只有一两个人，这种地区就可以去除。
分割数据集
标准化处理
k-近邻预测

具体步骤： 
# 1.获取数据集 
# 2.基本数据处理 
# 2.1 缩⼩数据范围 
# 2.2 选择时间特征 
# 2.3 去掉签到较少的地⽅ 
# 2.4 确定特征值和⽬标值 
# 2.5 分割数据集 
# 3.特征⼯程 -- 特征预处理(标准化) 
# 4.机器学习 -- knn+cv 
# 5.模型评估

具体代码如下（建议用jupyter编程，里面每个步骤单独运行查看）：

导包

import pandas as pd
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

获取数据

# 1.获取数据集
facebook = pd.read_csv("FaceBook_train.csv")
facebook.head(3)

数据基本处理

# 2. 数据基本处理

# 2.1 缩小数据范围以减少训练时间（）
facebook_data = facebook.query("x > 2.0 & x < 3.0 & y > 2.0 & y < 3.0")

# 2.2 对time进行转换处理（time是时间戳，将其转为日期格式）
time = pd.to_datetime(facebook_data["time"], unit="s") # 时间戳的单位是秒，所以用unit设置下
time = pd.DatetimeIndex(time)
facebook_data["day"] = time.day # 在源数据里新增day列
facebook_data["week"] = time.week # 在源数据里新增week列
facebook_data["hour"] = time.hour # 在源数据里新增hour列

# 2.3 去除 签到 比较少的地方（place_id是地区编号，每一行签到都会属于一个地区）
place_count = facebook_data.groupby("place_id").count() # 根据地区编号进行分组聚合，统计每个地区有多少签到处
place_count = place_count[place_count["row_id"]>3] #根据统计结果，筛选出签到处大于3的地区

 # place_count此时只包含签到处大于3的地区，但不是一个完整的表，根据place_count的索引（索引就是place_id）来获取完整数据
facebook_data = facebook_data[facebook_data["place_id"].isin(place_count.index)]

# 2.4 确定特征值和目标值
x = facebook_data[["x", "y", "accuracy", "day", "week", "hour"]] # 特征值
y = facebook_data["place_id"] # 目标值

# 2.5 分割数据
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=10)

特征工程

# 3. 特征工程 —— 特征预处理 标准化
# 3.1 实例化一个转换器
transfer = StandardScaler()
# 3.2 开始转换
x_train = transfer.fit_transform(x_train)
x_test = transfer.transform(x_test)

机器学习

# 4. 机器学习 KNN
# 4.1 实例化一个估计器
estimator = KNeighborsClassifier()
# 4.2 交叉验证、网格搜索
param_grid = {"n_neighbors":[3, 5, 7, 9]}
# n_jobs表示用几核CPU来跑这个程序，我的电脑是8核，-1表示整个CPU都来跑，花了12秒。
estimator = GridSearchCV(estimator=estimator, param_grid=param_grid, cv=3, n_jobs=6)
# 4.3 模型训练
estimator.fit(x_train, y_train)

模型评估

# 5. 模型评估
# 5.1 基本评估方式
score = estimator.score(x_test, y_test)
print("预测的准确率：", score)

y_predic = estimator.predict(x_test)
print("预测值为：", y_predic)
print("预测试和真实值的对比：", y_predic == y_test)

# 5.2 交叉验证的评估
print("在交叉验证中的最好结果：", estimator.best_score_)
print("在交叉验证中的最好参数模型：", estimator.best_estimator_)
print("每次交叉验证后的验证集和训练集的准确率结果：", estimator.cv_results_)