k近邻（k-nearest neighbor，k-NN）及其实现 - kd树（k-dimensional tree）

布满荆棘的人生 2023-07-07 12:57 68阅读 0赞

> 学习整理，部分描述来源于网络

# 1. 概述 #

## 1.1 定义 ##

> k近邻法（k-nearest neighbor，k-NN）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。

简单来说就是：在样本空间（训练集）中，与待测样本**最相邻**（通过距离度量）的**k个样本**中，**大多数属于**某一个类别，则该待测样本也属于这个类别，并具有这个类别上样本的特性。

从上面的定义中可以提炼出k-NN的三个基本要素：

1.  **“最相邻”-距离度量**： L p L\_p Lp距离 / Minkowski距离；
2.  **“k个样本”-k值的选择**：会决定模型的复杂程度；
3.  **“大多数属于”-分类决策规则**：k-NN中的分类决策规则往往是多数表决规则（majority voting rule）。

## 1.2 示例 ##

引用[百度百科][Link 1]中对k-NN的一个直观的例子来解释。

![在这里插入图片描述][20200223235310499.png_pic_center]

> **右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？**  
> 如果K=3，由于红色三角形所占比例为2/3（实线圈内），绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5（虚线圈内），因此绿色圆被赋予蓝色四方形类。

# 2. k-NN实现：kd树 #

实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索，这点在特征空间的维数大及训练数据容量大时尤为必要。为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。具体方法很多，下面介绍其中的kd树（kd-tree）方法。

## 2.1 构造kd树 ##

有很多种方法可以选择轴垂直分割面（ axis-aligned splitting planes ），所以有很多种创建k-d树的方法。 最典型的方法如下：

*  随着树的深度轮流选择轴当作分割面。（例如：在三维空间中根节点是 x 轴垂直分割面，其子节点皆为 y 轴垂直分割面，其孙节点皆为 z 轴垂直分割面，其曾孙节点则皆为 x 轴垂直分割面，依此类推。）；
 *  在该维度上选择中位数为划分点（pivot）对该数据集合进行划分，得到两个子集合，同时创建一个树节点node，用于存储；
 *  对两个子集合重复前面两个步骤的过程，直至所有子集合都不能再划分为止。

此外，也有一些其它方法用来选择垂直分割面，如：在k维数据集合中选择具有最大方差的维度k等。

> 这个方法产生一个平衡的k-d树。每个叶节点的高度都十分接近。然而，平衡的树不一定对每个应用都是最佳的。

***举个例子：***

> 假设有6个二维空间中的数据点（下图中黑点）： ( 2 , 3 ) , ( 5 , 4 ) , ( 9 , 6 ) , ( 4 , 7 ) , ( 8 , 1 ) , ( 7 , 2 ) \{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)\} (2,3),(5,4),(9,6),(4,7),(8,1),(7,2)。  
> ![在这里插入图片描述][20200225235515260.png_pic_center]
> 
> *图 二维数据kd树空间划分示意图*
> 
> 确定上图中分割线的过程就是构建kd树的过程，具体步骤如下：  
> （1）分别计算x、y方向上数据的方差，得知x方向上的方差最大；  
> （2）根据x轴方向数值 2 , 5 , 9 , 4 , 8 , 7 \{2,5,9,4,8,7\} 2,5,9,4,8,7得中位数为7，所以根节点的data为 ( 7 , 2 ) (7,2) (7,2)，并确定超平面为图中x=7的竖线；  
> （3）通过超平面x=7将原数据集分割为左子空间（ x ≤ 7 的 部 分 x\\leq 7的部分 x≤7的部分）和右子空间（剩余部分）。 （4）递归整个过程可完成kd树的构建。  
> ![在这里插入图片描述][20200226000515938.png_pic_center]
> 
> *图 上述实例生成的kd树*

## 2.2 搜索kd树（最邻近搜索） ##

最邻近搜索用来找出在树中与输入点最接近的点。k-d树最邻近搜索的过程如下：

1.  从根节点开始，递归的往下移。往左还是往右的决定方法与插入元素的方法一样(如果输入点在分区面的左边则进入左子节点，在右边则进入右子节点)。
2.  一旦移动到叶节点，将该节点当作"当前最佳点"。
3.  解开递归，并对每个经过的节点运行下列步骤：
    
    1.  如果当前所在点比当前最佳点更靠近输入点，则将其变为当前最佳点。
    2.  检查另一边子树有没有更近的点，如果有则从该节点往下找。
4.  当根节点搜索完毕后完成最邻近搜索。

***举个例子：***

> 在前面例子中构建的kd树中搜索点 ( 2.1 , 3.1 ) (2.1,3.1) (2.1,3.1)。  
>   
> 为了找到真正的最近邻，还需要进行“回溯”操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图4所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。  
> ![在这里插入图片描述][20200226001458764.png_pic_center]
> 
> *图 查找(2.1,3.1)点的两次回溯判断*
> 
> 再回溯到（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。以（2，4.5）为圆心，以3.041为半径作圆，如图5所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图6所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。

# 4. 代码实现（Python） #

可参考[这里][Link 2]的实现，写得很棒。

## 参考 ##

\[1\] 《统计学习方法》第三章. 李航  
\[2\] [https://baike.baidu.com/item/kd-tree/2302515?fr=aladdin][https_baike.baidu.com_item_kd-tree_2302515_fr_aladdin]  
\[3\] [https://www.jianshu.com/p/29b9dd354793][Link 2]

[Link 1]: https://baike.baidu.com/item/%E9%82%BB%E8%BF%91%E7%AE%97%E6%B3%95/1151153?fromtitle=knn&fromid=3479559&fr=aladdin
[20200223235310499.png_pic_center]: https://img-blog.csdnimg.cn/20200223235310499.png#pic_center
[20200225235515260.png_pic_center]: https://img-blog.csdnimg.cn/20200225235515260.png#pic_center
[20200226000515938.png_pic_center]: https://img-blog.csdnimg.cn/20200226000515938.png#pic_center
[20200226001458764.png_pic_center]: https://img-blog.csdnimg.cn/20200226001458764.png#pic_center
[Link 2]: https://www.jianshu.com/p/29b9dd354793
[https_baike.baidu.com_item_kd-tree_2302515_fr_aladdin]: https://baike.baidu.com/item/kd-tree/2302515?fr=aladdin