kd树方法

$kd$树是一种对$k$维空间中的实例点进行存储以便对其进行快速检索的树形结构。它是二叉树，表示对$k$维空间的一个划分（partition）。构造$kd$树相当于不断地用垂直于坐标轴的超平面将$k$维空间划分，构成一列的$k$维超矩形区域。$kd$树的每个节点对应于一个$k$维超矩形区域。

pic source: http://homes.sice.indiana.edu/yye/lab/teaching/spring2014-C343/moretrees.php

1. 构造平衡$kd$树算法

输入：$k$维空间数据集$T=\{x^{(1)},x^{(2)},...,x^{(m)}\}$，其中$x^{(i)}=(x_1, x_2, ..., x_k)^T$，$i=1,2,...,m$

输出：kd树

1）开始：构造根节点，根节点对应于包含$T$的$k$维空间的超矩形区域。

选择$x_1$为坐标轴，以$T$中所有实例的$x_1$坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x_1$垂直的超平面实现。

由根节点生成深度为1的左右子树：左子树对应于坐标$x_1$的值小于切分点的子区域，右子树对应于坐标$x_1$的值大于切分点的子区域。

将落在切分超平面上的实例点保存在根节点。

2）重复：对于深度为$l$的节点，选择$x_j$为切分的坐标轴，$j=l\pmod k+1$，举例来讲就是第一次切分选择坐标$x_1$，第二次选择坐标$x_2$，第三次选择坐标$x_3$，当$k$维后，返回到$x_1$继续作为切分坐标。切分由通过切分点并与轴$x_j$垂直的超平面实现。

对于左右子树，以$x_j$坐标的中位数为切分点，并保存为子树的根节点，然后同样分成两个子树。

3）直到两个子区域没有实例存在时停止，从而形成$kd$树的区域划分。

2. kd树的最近邻搜索

输入：已经构造好的$kd$树；目标点$x$

输出：$x$的最近邻

1）首先在$kd$树中找出包含目标点$x$的叶节点。方法是从根节点出发，递归地向下访问$kd$树，若目标点$x$当前维的坐标小于切分点的坐标，则往左子树查找，否则往右子树查找，一直到叶节点为止。

2）以此叶节点为“当前最邻近点”

3）递归往上回退，在每个节点上进行如下操作

• 如果该节点的实例比当前保存的最近点的距离更近，则以该节点为“当前最邻近点”
• 检查另一边子树有没有更近的点，如果有则从该节点往下找
• 即检查当前节点的超平面是否跟以目标节点$x$为圆心，目标节点$x$与“当前最邻近点”的距离为半径构成的圆体相交。
• 如果相交，可能在超平面的另外一侧有节点离目标节点更近，因此移动到超平面的另外一侧的递归执行搜索
• 如果不相交，则向上回退

4）当回退到根节点时（根节点已经完成了步骤3 的操作），搜索结束，最后的“当前最近点”即为$x$的最邻近点。

如果实例点是随机分布的，则$kd$树搜索的平均计算复杂度是$O(logN)$。$kd$树更适用于训练实例数远大于空间维数的情况，如果训练实例数接近空间维数，则效率退化为线性扫描。

3. 例子

示例1：

pic source: http://blog.csdn.net/baimafujinji/article/details/52928203

示例2：

维基百科上的一个动画例子（https://en.wikipedia.org/wiki/K-d_tree）

By User A1 at English Wikipedia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=16242339