机器学习算法：k近邻（kNN）算法
k近邻算法（k-nearest neighbor, kNN）是一种基本分类方法。k近邻算法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。分类时，对于新的实例（如下图的绿色方框），根据其k个最近的训练实例的类别，通过多数表决等方式进行预测。具体分类过程如下图所示。
从上图可以看出，kNN不具有显式的学习过程，实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。距离度量、k值选择及分类决策规则是k近邻法的3个基本要素。
1、距离度量
特征空间中两个实例点的距离是两个实例点相似程度的反映。k近邻模型的特征空间一般是n维实数向量空间
。可以使用的距离度量可定义为：
，其中
当
时，称为欧氏距离（Euclidean distance）；
当
时，称为曼哈顿距离（Manhattan distance）；
当
为无穷大时，它是各个坐标距离的最大值。
2、k值的选择
k值的选择会对k近邻算法的结果产生重大影响。例如：
当
时，新实例（如上图中绿色方框）判定为蓝色三角形类；当
时，新实例判定为红色圆圈类。
k值越小就意味着整体模型变得复杂，容易发生过拟合。
k值越大就意味着整体模型变得简单，预测容易发生错误。
在应用中，k值一般取一个较小的数值，通常采用交叉验证法来选取最优的k值。如下图所示，当增大k时，一般错误率会先降低，因为有周围更多的样本可以借鉴了，分类效果会变好。当k增大到一定程度使，分类模型变得越来越简单，错误率会更高。
3、分类决策规则
k近邻算法中的分类决策规则往往是多数表决，即由k个邻近的训练实例中的多数类决定新实例的类别。多数表决规则等价于经验风险最小化。
4、优缺点分析
优点：1）简单易用，相比其他算法，KNN算法简洁明了；2）模型训练时间快；3）预测效果好；4）对异常值不敏感。
缺点：1）需存储所有训练数据，对内存要求较高；2）预测阶段可能很慢；3）对不相关的功能和数据规模敏感。
5、算法实现
实现k近邻算法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。这点在特征空间的维数大及训练数据容量大时尤其必要。
k近邻算法最简单的实现方法是线性扫描（linear scan）。这时要计算新实例与每个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。
为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。具体方法很多，kd树方法是其中一种。
首先，对所有训练数据构造kd树。即是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。
其次，利用kd树进行k近邻搜索。利用kd树可以省去大部分数据点的搜索，从而减少搜索的计算量。
6、sklearn库中kNN实践
1）kNN函数介绍
首先，介绍sklearn库中kNN算法的一些参数：
def KNeighborsClassifier(n_neighbors =5, weights='uniform', algorithm ='', leaf_size ='30', p =2, metric ='minkowski', metric_params = None, n_jobs = None )
其中，
n_neighbors：这个值就是指 kNN 中的 k
weights：最普遍的 KNN 算法无论距离如何，权重都一样，但有时候我们想搞点特殊化，比如距离更近的点让它更加重要。这时候就需要 weight 这个参数了，这个参数有三个可选参数的值，决定了如何分配权重。参数选项如下：
• 'uniform'：不管远近权重都一样，就是最普通的 KNN 算法的形式。
• 'distance'：权重和距离成反比，距离预测目标越近具有越高的权重。
• 自定义函数：自定义一个函数，根据输入的坐标值返回对应的权重，达到自定义权重的目的。
algorithm：在 sklearn 中，要构建 KNN 模型有三种构建方式。一是暴力法，就是直接计算距离存储比较的那种放松。二是kd 树构建 KNN 模型。三是使用球树构建。其中暴力法适合数据较小的方式，否则效率会比较低。如果数据量比较大一般会选择用 KD 树构建 KNN 模型，而当 KD 树也比较慢的时候，则可以试试球树来构建 KNN。参数选项如下：
• 'brute' ：蛮力实现
• 'kd_tree'：KD 树实现 KNN
• 'ball_tree'：球树实现 KNN
• 'auto'： 默认参数，自动选择合适的方法构建模型
不过当数据较小或比较稀疏时，无论选择哪个最后都会使用 'brute'
leaf_size：如果是选择蛮力实现，那么这个值是可以忽略的，当使用KD树或球树，它就是是停止建子树的叶子节点数量的阈值。默认30，但如果数据量增多这个参数需要增大，否则速度过慢不说，还容易过拟合。
p：和metric结合使用的，当metric参数是"minkowski"的时候，p=1为曼哈顿距离， p=2为欧式距离。默认为p=2。
metric：指定距离度量方法，一般都是使用欧式距离。
• 'euclidean' ：欧式距离
• 'manhattan'：曼哈顿距离
• 'chebyshev'：切比雪夫距离
• 'minkowski'： 闵可夫斯基距离，默认参数
n_jobs：指定多少个CPU进行运算，默认是-1，也就是全部都算。
2）代码实例
以sklearn官方给出的例子，给出代码实例如下：
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as pltfrom sklearn.neighbors
import KNeighborsClassifier
#读取鸢尾花数据集
iris = load_iris()
x = iris.data
y = iris.target
k_range = range(1, 31)
k_error = []
#循环，取k=1到k=31，查看误差效果
for k in k_range:
knn = KNeighborsClassifier(n_neighbors=k)
#cv参数决定数据集划分比例，这里是按照5:1划分训练集和测试集
scores = cross_val_score(knn, x, y, cv=6, scoring='accuracy')
k_error.append(1 - scores.mean())
#画图，x轴为k值，y值为误差值
plt.plot(k_range, k_error)
plt.xlabel('Value of K for KNN')
plt.ylabel('Error')
plt.show()