【机器学习】k-近邻算法（k-nearest neighbor, k-NN）

前言

k$k$近邻学习是一种常用的监督学习方法。

k$k$近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。

k$k$近邻法的工作机制很简单：给定测试样本，基于某种距离度量（关于距离度量可以点击此处）找出训练集中与其最靠近的k$k$个训练样本，然后基于这k$k$个“邻居”的信息来进行预测。

分类时，对新的实例，根据其k$k$个最邻近的训练实例的类别（通过距离度量求得），通过多数表决等方式进行预测，也即“投票法”（选择着k$k$个样本中出现次数最多的类别标记作为预测结果）。因此，k$k$近邻法不具有显示的学习过程，事实上，它是“懒惰学习”的著名代表。

k$k$近邻法实际上利用训练数据集对特征空间进行划分，并作为其分类的“模型”；k$k$值的选择、距离度量及分类决策规则是k$k$近邻法的三个基本要素。

k$k$近邻算法

输入：训练数据集T={(x1,y1),(x2,y2),...,(xN,yN)}$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中，xi∈X=Rn$x_i\in \mathcal{X}=R^n$为实例的特征向量，yi∈Y={c1,c2,...,cK}$y_i\in \mathcal{Y}=\{c_1,c_2,...,c_K\}$为实例的类别，i=1,2,...,N$i=1,2,...,N$；实例特征向量x$x$；

输出：实例x$x$所属的类的y$y$。

（1）根据给定的距离度量，在训练数据集T$T$中找出与x$x$最邻近的k$k$个点，涵盖这k$k$个点的x$x$的领域记作Nk(x)$N_k(x)$;
（2）在Nk(x)$N_k(x)$中根据分类决策规则（如多数表决）决定x$x$的类别y$y$：

其中，I$I$ 为指示函数，即当 yi=cj$y_i=c_j$ 时 I$I$ 为1，否则为0
k邻近法的特殊情况是k=1$k=1$的情形，称为最近邻算法；对于输入的实例点（特征向量x$x$），最近邻法将训练数据集中与x$x$最邻近的点的类作为x$x$的类。

k$k$近邻模型

k$k$近邻法中，当训练集、距离度量、k$k$值以及分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上诉要素将特征空间划分为一些子空间，确定子空间里的每个点的属性的类。

下面我们来看看k$k$近邻分类器的一个示意图。

图中可以看出，当k=3$k=3$时，根据多数表决规则，则分类结果为红点；当k=5$k=5$时，则分类结果为绿色。显然，k$k$是一个重要的参数，当k$k$的取不同值时，分类结果会有显著不同。另一方面，如采用不同的距离度量方式，则找出的“近邻”也可能会有显著差别，从而导致不同的分类结果。

注：对于距离度量、k$k$值选择以及分类决策规则，下篇博客中更新。
参考文献 ：李航《统计学习分析》、图灵书籍《机器学习实战》