K-近邻算法详解-2（kd树）

1.什么是kd树
kd树是一种空间划分树，将整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关的搜索操作，主要用于多维空间关键位置的搜索。
kd树表示对k维空间的一个划分（partition），构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

2.kd树的构建
下面举一个简单的实例来解释kd树怎么构建。
假设有6个数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内，为了能有效找到最近邻，kd树采用分而治之的方法，将整个空间划分为几个小部分。

具体步骤如下所示：
1.确定6个点在x，y维度上的数据方差分别为多少，选择方法大的作为划分轴，上述数据中，x轴方法最大，选择x轴

2.根据x轴上的数据将数据依次排序，选择数据的中位数，上述数据的中位数为7，则分割超平面以（7,2）点通过，即x=7

3.确定左子空间和右子空间，x<=7的部分为左子空间，包含3个节点，分别为{（2,3），（5,4），（4,7）}，另一部分为右子空间，包含2个节点，分别为{（9,6），（8,1）}。

kd树是一个递归过程，对左子空间和右子空间重复上述操作，得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步划分，直至空间中只包含一个数据。

得到的kd树图如下所示：

下面为kd树的算法步骤：

3.搜索kd树
在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行’回溯’操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（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为半径画圆，如下图所示。发现该圆并不和超平面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。以（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。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图右所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。

参考：https://blog.****.net/qll125596718/article/details/8426458
https://blog.****.net/u010002184/article/details/86654411