统计学习方法BR-CH3：K近邻法(knn)【存疑】

By arthur503 -- 04 Oct 2013

一、原理

knn方法的原理很好理解，就是根据训练数据集训练出来模型，在对新的实例分类时，根据其周围k个最近邻的训练实例的类别来进行判断即可。

knn方法的优点是简单、直观，是一种基本的分类和回归方法。在李航这本书里面，讨论分类问题，不讨论回归问题。

knn的本质是使用训练数据集中的实例对特种空间进行划分。在特征空间中，对于训练实例点xi，距离该点比其他点更近的所有点组成的区域叫做单元（cell）。特征空间便被训练实例点划分成这样多个单元。

KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。

KNN 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于 KNN 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN 方法较其他方法更为适合。

该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的 K 个邻居中大容量类的样本占多数。

KNN 算法不仅可以用于分类，还可以用于回归。通过找出一个样本的 K 个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

可见，knn算法的分类时间复杂度为O(n)，适用于类域交叉或重叠较多、并且样本容量比较大的类域的自动分类，如果样本不平衡，则那些容量比较小的类域采用这种算法容易产生误分类。

knn原理简单，在实现上的难点在于：如何快速的寻找到新实例周围k个最近邻的训练实例。

二、模型三要素

knn的模型主要有三个要素：k值选择、距离度量和分类决策规则。

k值选择

由于新实例点的分类是由周围k个训练实例点的分类决定的，因此，选择的k值对于分类的误差有很大影响。

这里涉及到的分类误差有两种，分别是近似误差（approximation error）和估计误差（estimation error）。

如果k值较小，只有与输入实例较近的训练实例才会对预测结果起作用，则“学习”的近似误差较小；但是由于预测结果对近邻的实例点非常敏感，若有噪声则会出错，因此估计误差就会增大；反之若k值较大，则估计误差减小，但是近似误差增大。（近似误差判断的是新实例点和训练实例点是否相似，越近表示越相似；估计误差表示新实例点的判断错误可能性大不大，参考的训练实例点越少表示估计误差越大）

总体来说，k值的选择反映了在近似误差和学习误差之间的权衡。k值越小，整体模型会变得复杂，容易发生过拟合；k值越大，模型变得简单，但计算量也增大。特殊情况下，若K=1，则表现为最近邻算法；若k=N，完全无效果，不可取。在实际应用中，一般k值取一个较小的数值，并采用交叉验证法来选取最优的k值。

另外，K近邻算法中也提到了，可以采用对不同距离的邻居采用不同权值的方法来改进knn算法。这样，可以得到更好的近似误差。

2. 距离度量

特征空间中两个点的距离反映了两个点的相似程度。

一般情况下，计算两个点之间的距离采用的是欧氏距离比较多，还可以选择的距离有：L-p距离（即Minkowski距离）等。

L-p距离在p=1时为曼哈顿距离，p=2时为欧式距离，p=∞时为各个坐标距离的最大值。

由于距离的度量方法不一样，因此，由不同的距离度量所确定的最近邻点是不同的！需要在实际情况中，根据需要选择合适的距离度量方法。至于有哪些距离度量方法，我之前就一直想总结一下，详细内容参看另一篇博客：统计学习方法学习笔记-附录：距离度量有几种方法？

另外，在K近邻算法作者中提到：

在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

3. 分类决策规则

由于是根据多个训练实例点来判别新实例点的分类，这种离散情况，一般选择多数表决规则。可以推到，多数表决规则的误分类率最小即是经验风险最小，因此，多数表决规则等价于经验风险最小化。

三、knn的实现

在选定了k值，找到合适的距离度量方法，并决定了分类决策规则之后，knn的模型就建立起来了。根据之前所说，knn在实现上的难点在于：如何快速的寻找到新实例周围k个最近邻的训练实例。这在特征空间的维数大及训练数据容量大的时候尤其必要。

knn的最简单实现方法是线性扫描。但这要计算输入实例与每个训练实例之间的距离，属于很糙很笨的方法，在维数高和训练数据大时很消耗计算资源，不可取。

为了提高k近邻搜索的效率，可以考虑用特殊结构来存储数据，以减少计算距离的次数。具体方法有很多，书上介绍的是kd树的方法。kd树方法包括构造和搜索两部分。

kd树的构造

kd树是二叉树，表示对k维空间的一个划分。构造kd树就是使用递归方法，不断的用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域，使得kd数中的每一个结点都对应一个k维超矩形区域。

构建方法为：

确定split分解域：对k维上的数据都计算方差，选择方差最大的维度进行分割（方差大表示数据分散的比较开，容易有较好的分割效果）； * 在选定的分解维度上，找到需要分解的数据的中位数的数据点作为切分点（中位数可以更好的分割）。通过切分点并与所选维度坐标轴垂直的平面即为切分超平面； * 切分超平面将数据集分为左右两个子空间，分别对左右子空间中的数据点进行上面的步骤，直至所有数据点都被划分（每个小空间只包含一个数据点），构建完成。

在李航的书中，P42页有例题，将二维空间的数据集构建成一个kd二叉树。从网上找来的图片如下：

构造前的特征空间划分（注：此处已包含第一次切割，切分点为(7,2)）：

构造后的特征空间划分：

构造后的kd二叉树：

kd树的搜索

构造kd树的目的在于提高搜索k近邻的次数。由上图可以看出，kd树中，将所有训练实例作为切分点，将特征空间划分为不同的特征空间，是从根节点逐次向下划分的。

因此，我们在搜索的时候，也可以依照如此思路，对新实例点进行逐次寻找，直至找到最底层的叶节点，即是和该节点相近的节点。但是，这个叶结点是否就是最近邻的结点呢？不一定。因为最近邻的结点还有可能存在相邻的空间中。如何判断是否存在相邻的空间中，我们来看一下。

我们继续使用上图（其实是别人画好的图，ORZ），如下：

星号表示要查找的点（2.1,3.1）。通过二叉搜索，我们找到了最近邻的（2,3）节点。如果（2,3）节点不是最近邻的，那么最近邻的节点一定在以查询点为圆心，以查询点和叶节点（此处即（2,3）结点）的距离为半径的圆域内。为了找到真正的近邻，还需沿着搜索路径反向查找进行“回溯”操作。我们计算这两个节点之间的距离，画出该圆如图中所示，发现该圆并不和父节点（5,4）的超平面y=4相交，因此无需进入相邻的子空间（即（5,4）结点的右空间）进行搜索。这样，更不可能与超平面x=7相交，“回溯”完成，结束搜索，返回最近邻结点（2,3）。

对于更复杂的例子，如下图：

查找点（2,4.5）的k近邻。同样进行二叉查找，得到搜索路径：（7,2）、（5,4）、（4,7）。取（4,7）为当前最近邻点，计算与目标点距离为3.202。按照搜索路径回溯到点（5,4），计算与（5,4）的距离为3.041。重新画圆。之后，判断圆点（5,4）的超平面y=4相交，因此需要进入（5,4）的左子空间查找。因此，需要将点（2,3）加入搜索路径，得：（7,2）、（2,3）。计算查找点与（2,3）距离为1.5，所以更新点（2,3）为最近邻点，重新画圆。回溯到节点（7,2），发现并不与节点（7,2）的超平面x=7相交。路径回溯完成，返回最近邻点（2,3）。

在文章k-d tree算法和统计学习笔记（3）——k近邻法与kd树中还给出了C++的伪代码，可供参考。

另外，在k-d tree算法中说到：

当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。研究表明N个节点的K维k-d树搜索过程时间复杂度为：t_worst = O(kN^(1-1/k))

像实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降。

假设数据集的维数为D，一般来说要求数据的规模N满足N » 2^D，才能达到高效的搜索。所以这就引出了一系列对k-d树算法的改进。有待进一步研究学习。

四、思维导图

本章的思维导图如下：

五、【存疑】

最后，放几个存疑的问题，等到之后再来查。

kd树与GEOHash的相似之处？
平衡kd树的搜索效率未必是最高的，那怎么构造效率才会最高？
kd树可以推广到三叉树、n叉树的情况吗？
实现knn代码，解答书中例3.2。

参考资料：

* 《统计学习方法》- 李航