kd树方法
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$$树更适用于训练实例数远大于空间维数的情况，如果训练实例数接近空间维数，则效率退化为线性扫描。
示例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