1.K-近邻算法简介

1.1 什么是K-近邻算法

简单理解就是根据你的“邻居”推断你的类别

因此我们给出更准确的定义：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

两个样本的距离又称欧氏距离，通过如下的公式计算：
$$d=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$
举个简单的例子：

其中9号电影不知道类别，如何去预测？我们可以利用K近邻算法的思想：
分别计算每个电影和被预测电影的距离，然后求解：

1.2 KNN算法流程总结

1）计算已知类别数据集中的点与当前点之间的距离

2）按距离递增次序排序

3）选取与当前点距离最小的k个点

4）统计前k个点所在的类别出现的频率

5）返回前k个点出现频率最高的类别作为当前点的预测分类

2.K近邻算法api初步使用

2.1 机器学习的流程

1. 获取数据集
2. 数据基本处理
3. 特征工程
4. 机器学习
5. 模型评估

2.2 引入Scikit-learn

2.2.1 安装

Scikit-learn工具介绍：一款Python语言的机器学习工具，包括许多知名的机器学习算法的实现，文档完善，容易上手，丰富的API

pip3 install scikit-learn

2.2.2 K-近邻算法API

参数介绍：

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5)
n_neighbors：int,可选（默认= 5），k_neighbors查询默认使用的邻居数

导入模块：

from sklearn.neighbors import KNeighborsClassifier
# 构造数据集
x = [[0], [1], [2], [3]]
y = [0, 0, 1, 1]

# 实例化API
estimator = KNeighborsClassifier(n_neighbors=1)
# 使用fit方法进行训练
estimator.fit(x, y)
# 预测
estimator.predict([[1]])

3.距离度量

既然KNN算法是基于距离实现，哪有哪些常见的距离度量呢

3.1 欧式距离(Euclidean Distance)

二维平面上点$a(x_1,y_1)$与$b(x_2,y_2)$的欧氏距离：
$$d_{12}=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$$
三维平面上点$a(x_1,y_1,z_1)$与$b(x_2,y_2,z_2)$的欧氏距离：
$$d_{12}=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}$$
以此类推：n维平面上点$a(x_{11},x_{12},...,x_{1n})$与$b(x_{21},x_{22},...,x_{2n})$的欧氏距离：
$$d_{12}=\sqrt{\sum _{k=1}^n(x_{1k}-x_{2k}{)}^2}$$

3.2 曼哈顿距离(Manhattan Distance)

曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。

二维平面上点$a(x_1,y_1)$与$b(x_2,y_2)$的曼哈顿距离：
$$d_{12}=|x_1-x_2|+|y_1-y_2|$$
同理：n维平面上点$a(x_{11},x_{12},...,x_{1n})$与$b(x_{21},x_{22},...,x_{2n})$的曼哈顿距离：
$$d_{12}=\sum _{k=1}^n|x_{1k}-x_{2k}|$$

3.3 切比雪夫距离 (Chebyshev Distance)

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

二维平面上点$a(x_1,y_1)$与$b(x_2,y_2)$的切比雪夫距离：
$$d_{12}=max(|x_1-x_2|,|y_1-y_2|)$$
同理：n维平面上点$a(x_{11},x_{12},...,x_{1n})$与$b(x_{21},x_{22},...,x_{2n})$的切比雪夫距离：
$$d_{12}=max(|x_{1k}-x_{2k}|)$$

3.4 闵可夫斯基距离(Minkowski Distance)

闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述
两个n维变量$a(x_{11},x_{12},\dots ,x_{1n})$与$b(x_{21},x_{22},\dots ,x_{2n})$间的闵可夫斯基距离定义为：
$$d_{12}=\sqrt[p]{\sum _{k=1}^n|x_{1k}-x_{2k}{|}^p}$$
其中p是一个变参数：

• 当p=1时，就是曼哈顿距离；

• 当p=2时，就是欧氏距离；

• 当p→$\infty$时，就是切比雪夫距离。

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

4.K值的选择

1. 选择较小的K值，就相当于用较小的领域中的训练实例进行预测，

• “学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，
• 换句话说，K值的减小就意味着整体模型变得复杂，越容易受到异常点的影响，从而容易发生过拟合。

2. 选择较大的K值，就相当于用较大领域中的训练实例进行预测，

• 其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误。
• 且K值的增大就意味着整体的模型变得简单，越容易受到样本均衡的问题，从而容易发生欠拟合。

3. K=N（N为训练样本个数），则完全不足取，

• 因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。

5.kd树

5.1 为什么需要kd树

实现k近邻算法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。

这在特征空间的维数大及训练数据容量大时尤其必要。

k近邻法最简单的实现是线性扫描（穷举搜索），即要计算输入实例与每一个训练实例的距离。计算并存储好以后，再查找K近邻。当训练集很大时，计算非常耗时。

为了提高kNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减小计算距离的次数。

5.2 什么是kd树

根据KNN每次需要预测一个点时，我们都需要计算训练数据集里每个点到这个点的距离，然后选出距离最近的k个点进行投票。当数据集很大时，这个计算成本非常高，针对N个样本，D个特征的数据集，其算法复杂度为$O(D{N}^2)$。

kd树：为了避免每次都重新计算一遍距离，算法会把距离信息保存在一棵树里，这样在计算之前从树里查询距离信息，尽量避免重新计算。其基本原理是，如果A和B距离很远，B和C距离很近，那么A和C的距离也很远。有了这个信息，就可以在合适的时候跳过距离远的点。

这样优化后的算法复杂度可降低到$O(Dlog(N))$

5.3 kd树原理

黄色的点作为根节点，上面的点归左子树，下面的点归右子树，接下来再不断地划分，分割的那条线叫做分割超平面（splitting hyperplane），在一维中是一个点，二维中是线，三维的是面。

黄色节点就是Root节点，下一层是红色，再下一层是绿色，再下一层是蓝色。

5.4 kd树案例

如果说原理比较抽象，那么直接上案例就很好理解

给定一个二维空间数据集：T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}，构造一个平衡kd树。

1. 树的建立：根据方差划分数据，选取方差大的为划分轴，因为方差大，则数据离散，则可以生成更均匀的子节点，避免冗余划分
   第一维度：x = [ 2 , 4 , 5 , 7 , 8 , 9]（已排序）方差：5.81
   第二维度：y = [ 1 , 2 , 3 , 4 , 6 , 8]（已排序）方差：5.6667
   选取x为轴，kd树的构造与二叉排序树相似，由于x中位数为6，因此这里选择7作为中位数，第一层选取x轴划分，第二层需选取y轴划分，即对于左子树 [ (2,3)，(5,4)，(4,7) ] ，4为3与7的中位数，则选取(5,4)作为二层根节点，右子树中 [ (8,1)，(9,6) ] 类似，第三层再根据x轴划分，以此类推。
   
2. 最近领域的搜索：
   
   样本集{(2,3),(5,4), (9,6), (4,7), (8,1), (7,2)}

查找点 (2.1,3.1)：

根据二叉排序树查找法，进入第一层搜索，比较第一维度x，其中2.1小于7，入栈(7,2)，并向左子树搜索；进入第二层搜索，比较第二维度y，其中3.1小于4，入栈(5,4)，并向左子树搜索；进入第三层搜索，比较第一维度x，其中2.1大于2，入栈(2,3)，并向右子树搜索；叶节点搜索完毕，此时栈中有<(7,2)，(5,4)，(2,3)>，名其为search_path。

• 从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141；
• 然后回溯至(5,4)，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆，并不和超平面y=4相交，如上图，所以不必跳到结点(5,4)的右子空间去搜索，因为右子空间中不可能有更近样本点了。
• 于是再回溯至(7,2)，同理，以(2.1,3.1)为圆心，以dist=0.141为半径画一个圆并不和超平面x=7相交，所以也不用跳到结点(7,2)的右子空间去搜索。
• 至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2.1,3.1)的最近邻点，最近距离为0.141。

查找点(2,4.5)

同理构造search_path为<(7,2),(5,4), (4,7)>

• 从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202；
• 然后回溯至(5,4)，以(2,4.5)为圆心，以dist=3.202为半径画一个圆与超平面y=4相交，所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中，现在search_path中的结点为<(7,2),(2, 3)>；另外，(5,4)与(2,4.5)的距离为3.04 < dist = 3.202，所以将(5,4)赋给nearest，并且dist=3.04。
• 回溯至(2,3)，(2,3)是叶子节点，直接平判断(2,3)是否离(2,4.5)更近，计算得到距离为1.5，所以nearest更新为(2,3)，dist更新为(1.5)
• 回溯至(7,2)，同理，以(2,4.5)为圆心，以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。
• 至此，search_path为空，结束整个搜索，返回nearest(2,3)作为(2,4.5)的最近邻点，最近距离为1.5。
  
  

6.特征工程-特征预处理

6.1 为什么需要特征预处理

特征的单位或者大小相差较大，或者某特征的方差相比其他的特征要大出几个数量级，容易影响（支配）目标结果，使得一些算法无法学习到其它的特征。

6.2 预处理方法——归一化

1. 定义：通过对原始数据进行变换把数据映射到(默认为[0,1])之间
2. 公式：
   $$\begin{array}{rl}{x}^{\prime }& =\frac{x-\min }{\max -\min }\\ x^{\prime \prime }& =x^{\prime }\cdot (mx-mi)+mi\end{array}$$
   
3. API:

sklearn.preprocessing.MinMaxScaler (feature_range=(0,1)… )
  MinMaxScalar.fit_transform(X)
  X:numpy array格式的数据[n_samples,n_features]
返回值：转换后的形状相同的array

4. 归一化特点：最大值与最小值非常容易受异常点影响，所以这种方法鲁棒性较差，只适合传统精确小数据场景。

6.3 预处理方法——标准化

1. 定义：通过对原始数据进行变换把数据变换到均值为0,标准差为1范围内
2. 公式：
   $$x^{\prime }=\frac{x-mean}{\sigma }$$

• 对于归一化来说：如果出现异常点，影响了最大值和最小值，那么结果显然会发生改变
• 对于标准化来说：如果出现异常点，由于具有一定数据量，少量的异常点对于平均值的影响并不大，从而方差改变较小。
  

3. API:

sklearn.preprocessing.StandardScaler( )
处理之后每列来说所有数据都聚集在均值0附近标准差差为1
  StandardScaler.fit_transform(X)
  X:numpy array格式的数据[n_samples,n_features]
返回值：转换后的形状相同的array

4. 标准化特点：在已有样本足够多的情况下比较稳定，异常值影响小，适合现代嘈杂大数据场景。

7.交叉验证，网格搜索

7.1 什么是交叉验证(cross validation)

交叉验证：将拿到的训练数据，分为训练和验证集。以下图为例：将数据分成4份，其中一份作为验证集。然后经过4次(组)的测试，每次都更换不同的验证集。即得到4组模型的结果，取平均值作为最终结果。又称4折交叉验证。

7.1.1 分析

我们之前知道数据分为训练集和测试集，但是为了让从训练得到模型结果更加准确。做以下处理

• 训练集：训练集+验证集
• 测试集：测试集

7.1.2 为什么需要交叉验证

交叉验证目的：为了让被评估的模型更加可信（注：交叉验证只能提升模型可信度，不能提升模型准确度）

7.2 什么是网格搜索(Grid Search)

通常情况下，有很多参数是需要手动指定的（如k-近邻算法中的K值），这种叫超参数。但是手动过程繁杂，所以需要对模型预设几种超参数组合。每组超参数都采用交叉验证来进行评估。最后选出最优参数组合建立模型。

sklearn.model_selection.GridSearchCV(estimator, param_grid=None,cv=None)
对估计器的指定参数值进行详尽搜索
  estimator：估计器对象
  param_grid：估计器参数(dict){“n_neighbors”:[1,3,5]}
  cv：指定几折交叉验证
  fit：输入训练数据
  score：准确率
结果分析：
  bestscore__:在交叉验证中验证的最好结果
  bestestimator：最好的参数模型
  cvresults:每次交叉验证后的验证集准确率结果和训练集准确率结果

7.3 网格搜索示例

实现一个鸢尾花种类预测

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

# 1、获取数据集
iris = load_iris()
# 2、数据基本处理 -- 划分数据集
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=22)
# 3、特征工程：标准化
# 实例化一个转换器类
transfer = StandardScaler()
# 调用fit_transform
x_train = transfer.fit_transform(x_train)
x_test = transfer.transform(x_test)
# 4、KNN预估器流程
#  4.1 实例化预估器类
estimator = KNeighborsClassifier()

# 4.2 模型选择与调优——网格搜索和交叉验证
# 准备要调的超参数
param_dict = {"n_neighbors": [1, 3, 5]}
estimator = GridSearchCV(estimator, param_grid=param_dict, cv=3)
# 4.3 fit数据进行训练
estimator.fit(x_train, y_train)
# 5、评估模型效果
# 方法a：比对预测结果和真实值
y_predict = estimator.predict(x_test)
print("比对预测结果和真实值：\n", y_predict == y_test)
# 方法b：直接计算准确率
score = estimator.score(x_test, y_test)
print("直接计算准确率：\n", score)

# 进行评估查看最终选择的结果和交叉验证的结果
print("在交叉验证中验证的最好结果：\n", estimator.best_score_)
print("最好的参数模型：\n", estimator.best_estimator_)
print("每次交叉验证后的准确率结果：\n", estimator.cv_results_)

最终结果：

比对预测结果和真实值：
 [ True  True  True  True  True  True  True False  True  True  True  True
  True  True  True  True  True  True False  True  True  True  True  True
  True  True  True  True  True  True  True  True  True  True  True  True
  True  True]
直接计算准确率：
 0.947368421053
在交叉验证中验证的最好结果：
 0.973214285714
最好的参数模型：
 KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=1, n_neighbors=5, p=2,
           weights='uniform')
每次交叉验证后的准确率结果：
 {'mean_fit_time': array([ 0.00114751,  0.00027037,  0.00024462]), 'std_fit_time': array([  1.13901511e-03,   1.25300249e-05,   1.11011951e-05]), 'mean_score_time': array([ 0.00085751,  0.00048693,  0.00045625]), 'std_score_time': array([  3.52785082e-04,   2.87650037e-05,   5.29673344e-06]), 'param_n_neighbors': masked_array(data = [1 3 5],
             mask = [False False False],
       fill_value = ?)
, 'params': [{'n_neighbors': 1}, {'n_neighbors': 3}, {'n_neighbors': 5}], 'split0_test_score': array([ 0.97368421,  0.97368421,  0.97368421]), 'split1_test_score': array([ 0.97297297,  0.97297297,  0.97297297]), 'split2_test_score': array([ 0.94594595,  0.89189189,  0.97297297]), 'mean_test_score': array([ 0.96428571,  0.94642857,  0.97321429]), 'std_test_score': array([ 0.01288472,  0.03830641,  0.00033675]), 'rank_test_score': array([2, 3, 1], dtype=int32), 'split0_train_score': array([ 1.        ,  0.95945946,  0.97297297]), 'split1_train_score': array([ 1.        ,  0.96      ,  0.97333333]), 'split2_train_score': array([ 1.  ,  0.96,  0.96]), 'mean_train_score': array([ 1.        ,  0.95981982,  0.96876877]), 'std_train_score': array([ 0.        ,  0.00025481,  0.0062022 ])}

8.KNN算法总结

1. 优点：

• 简单有效
• 重新训练的代价低
• 适合类域交叉样本**：KNN方法主要靠周围有限的邻近的样本**,而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
• 适合大样本自动分类：该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

2. 缺点：

• 惰性学习：KNN算法是懒散学习方法（lazy learning,基本上不学习），一些积极学习的算法要快很多
• 类别评分不是规格化：不像一些通过概率评分的分类
• 输出可解释性不强：例如决策树的输出可解释性就较强
• 对不均衡的样本不擅长：当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
• 计算量较大：目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。