K近邻 | K-Nearest Neighbors

type

Post

status

Published

summary

K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

slug

knn

date

May 11, 2020

1、KNN算法核心思想

K近邻算法 (k-nearest neighbors,KNN) ，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

K 近邻法既可以做分类，也可以做回归；KNN做分类预测时，一般是选择多数表决法，即训练集里与预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。而KNN做回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。这也就是我们的目的，来了一个新的数据点，我要得到它的类别是什么？

使用K近邻算法来进行分类：

如果K=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。

如果K=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

2、KNN算法三要素

KNN 算法我们主要要考虑三个重要的要素，他们分别是 k 值的选取，距离度量的方式和分类决策规则。对于分类决策规则，一般都是使用前面提到的多数表决法。所以我们重点是关注与 k 值的选择和距离的度量方式。

K值的选取

对于 k 值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的 k 值。

选择较小的 k 值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K 值的减小就意味着整体模型变得复杂，容易发生过拟合；

选择较大的 k 值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且 K 值的增大就意味着整体的模型变得简单。

一个极端是 k 等于样本数 m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

距离的度量方式

详见：距离公式

3、KNN的实现方式

蛮力实现

既然我们要找到 k 个最近的邻居来做预测，那么我们只需要计算预测样本和所有训练集中的样本的距离，然后计算出最小的 k 个距离即可，接着多数表决，很容易做出预测。这个方法的确简单直接，在样本量少，样本特征少的时候有效。但是在实际运用中很多时候用不上，为什么呢？因为我们经常碰到样本的特征数有上千以上，样本量有几十万以上，如果我们这要去预测少量的测试集样本，算法的时间效率很成问题。因此，这个方法我们一般称之为蛮力实现。比较适合于少量样本的简单模型的时候用。

KD 树实现原理

KD 树算法没有一开始就尝试对测试样本分类，而是先对训练集建模，建立的模型就是 KD 树，建好了模型再对测试集做预测。所谓的 KD 树就是 K 个特征维度的树，注意这里的 K 和 KNN 中的 K 的意思不同。KNN 中的 K 代表最近的 K 个样本，KD 树中的 K 代表样本特征的维数。为了防止混淆，后面我们称特征维数为 n。

KD 树算法包括三步，第一步是建树，第二部是搜索最近邻，最后一步是预测。

KD 树的建立

我们首先来看建树的方法。KD 树建树采用的是从 m 个样本的 n 维特征中，分别计算 n 个特征的取值的方差，用方差最大的第 k 维特征来作为根节点。对于这个特征，我们选择特征的取值的中位数对应的样本作为划分点，对于所有第 k 维特征的取值小于的样本，我们划入左子树，对于第 k 维特征的取值大于等于的样本，我们划入右子树，对于左子树和右子树，我们采用和刚才同样的办法来找方差最大的特征来做更节点，递归的生成 KD 树。

比如我们有二维样本 6 个，{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，构建 kd 树的具体步骤为：

1）找到划分的特征。6 个数据点在 x，y 维度上的数据方差分别为 6.97，5.37，所以在 x 轴上方差更大，用第 1 维特征建树。

2）确定划分点（7,2）。根据 x 维上的值将数据排序，6 个数据的中值 (所谓中值，即中间大小的值) 有两个，分别为5和7（中位元素尽管是左和右都可以，但是在构建kd树时应该得保证遵从统一规则：也就是全选左或者全选右。不然在搜索的时候会在产生相等情况的时候不知应当在左还是右进行递归。），这里选择（7,2）。这样，该节点的分割超平面就是通过（7,2）并垂直于：划分点维度的直线 x=7；

3）确定左子空间和右子空间。分割超平面 x=7 将整个空间分为两部分：x<=7 的部分为左子空间，包含 3 个节点 ={(2,3),(5,4),(4,7)}；另一部分为右子空间，包含 2 个节点 ={(9,6)，(8,1)}。

4）用同样的办法划分左子树的节点 {(2,3),(5,4),(4,7)} 和右子树的节点{(9,6)，(8,1)}。最终得到 KD 树。

最后得到的 KD 树如下：

KD 树搜索最近邻

KD树搜索最近邻的步骤如下：

在kd树中找出包含目标点的叶结点；

计算目标点与搜索路径上个点的距离，得到“当前最近点”（当前最近点一般是搜索路径上的最后一个叶节点，不过也有例外，详见例①）；

返回到当前叶结点的父节点，判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点；

具体判断方法是以目标点为圆心，以“当前最近点”的距离为半径做圆，看圆是否与父节点的另外一半子空间相交，如果相交就到这个子节点寻找是否有更加近的近邻, 有的话就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。

当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。

从上面的描述可以看出，KD 树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。

这里举两个例子帮助理解：

①对点 (2.1,3.1) 找最近邻的过程

二叉树搜索：先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<(7,2)，(5,4)，(2,3)>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，

回溯查找：在得到（2,3）为查询点的最近点之后，回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如下图所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中(图中灰色区域)去搜索；

最后，再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。

②对点 (2,4.5) 找最近邻的过程

先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由 y = 4 为分割超平面的，由于查找点为 y 值为 4.5，因此进入右子空间查找到（4,7），形成搜索路径 <(7,2)，(5,4)，(4,7)>，但（4,7）与目标查找点的距离为 3.202，而（5,4）与查找点之间的距离为 3.041，所以（5,4）为查询点的最近点；以（2，4.5）为圆心，以 3.041 为半径作圆，如下图所示。可见该圆和 y = 4 超平面交割，所以需要进入（5,4）左子空间进行查找，也就是将（2,3）节点加入搜索路径中得 <(7,2)，(2,3)>；于是接着搜索至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为 1.5；回溯查找至（5,4），直到最后回溯到根结点（7,2）的时候，以（2,4.5）为圆心 1.5 为半径作圆，并不和 x = 7 分割超平面交割，如下图所示。至此，搜索路径回溯完，返回最近邻点（2,3），最近距离 1.5。

KD 树预测

有了 KD 树搜索最近邻的办法，KD 树的预测就很简单了，在 KD 树搜索最近邻的基础上，我们选择到了第一个最近邻样本，就把它置为已选。在第二轮中，我们忽略置为已选的样本，重新选择最近邻，这样跑 k 次，就得到了目标的 K 个最近邻，然后根据多数表决法，如果是 KNN 分类，预测为 K 个最近邻里面有最多类别数的类别。如果是 KNN 回归，用 K 个最近邻样本输出的平均值作为回归预测值。