什么是KD树

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

构建KD树

输入：K维空间数据集，样本数为N。$x_i = (x_i^{(1)},x_i^{(2)},x_i^{(3)}….x_i^{(k)})^T$
输出：KD树
(1)开始：构造根节点，根节点包含了K维空间的超矩形区域。
选择$x^{(1)}$作为第一个切分的维度，找到$x^{(1)}$坐标的中位数为切分点，将数据集一分为二，大于$x_i^{(1)}$的中位数在右，小于在左。切分由通过切分点并与坐标轴$x^{(1)}$垂直的超平面实现。
将落在切分超平面的实例点保存在根节点。
(2)重复切分操作，再将$x^{(2)}$作为切分的维度，并在之前已经一分为二的左边和右边分别找到$x^{(2)}$维度的中位数，接着分别切分到左右两边。
(3)一直重复切分操作,对深度为j的节点,选择$x^{(l)}$为切分的坐标轴，l=j(mod)k +1,以该结点的区域中所有实例的$x^{(l)}$坐标的中位数为切分点，将该结点对应的超平面矩形区域切分为两个子区域。将落在切分超平面的实例点保存在根节点。
(4)直到两个子区域没有实例存在时停止。从而形成kd数的区域划分。

搜索kd树（最近邻）

下面介绍如何利用kd树进行最近邻搜索。利用kd树可以省去大部分数据点的搜索，从而减少搜索的计算量。
输入：（1）已经构造好的kd树（2）目标点x（想找到距离x最近的点）
输出： x的最近邻
（1）在kd树种找出包含目标点x的叶节点：从根节点出发，递归的向下访问kd树。若目标点x当前维（用哪个维度分的就用哪个维度）的坐标小于切分点的坐标，则移动到左子节点，否则移动到右子节点。直到找到子节点为叶节点为止。
（2）以次叶节点为‘当前最近点’
（3）递归（刚才一路下来的那些点都要进行接来下来的操作）地向上回退，在每个结点都进行以下操作：
a:如果该结点保存的实例点比当前最近点的距离（用选定的公式计算比如欧氏距离）目标点更近，则以该实例点为‘当前最近点’。
b:检查目前结点的另一子结点对应的区域是否以目标点为球心、以目标点与‘当前最近点’间的距离为半径的超球体相交。
若相交：可能在另一个子结点对应的区域内存在距离目标点更近的点，移动到另一个子结点，接着递归的向下搜索
如果不想交：向上回退。
（4）当退回到根节点时，搜索结束。最后的‘当前最近点’即为x的最近邻点。

kd数搜索的评论计算复杂度是O(logN),N是训练实例数.kd树更适用于训练实例数远大于空间维数时的k近邻搜索。

搜索kd树*（K近邻）

输入：给定一个已经构建好的kd树，需要寻找的点P，需要寻找几个近邻K。
输出：L列表，L列表里有K个空位，每个空位装的是近邻点。

（1）根据切分的维度对比同维度下P的坐标值向下搜索。（也就是说，如果树的节点是照 $x_r=a$ 进行切分，并且 p 的 r 坐标小于 a，则向左枝进行搜索；反之则走右枝）。
（2）当到达叶子结点时，将其标记为访问过。如果L列表中不足k个点，则将当前结点的坐标加入到L列表。如果L列表不为空并且当前结点与P的距离小于L中所存放结点的最大距离，则用当前结点替换掉L中离P最远的结点。
（3）如果当前的结点不是整棵树最顶端的结点，执行a操作；反之，输出L列表。
a:向上爬一个结点。如果当前（向上爬过之后的）结点没有被访问过，将其标记为访问过，然后执行b和c操作；如果当前结点被访问过，再次执行a.
b:如果此时L列表中不足k个点，则将结点加入到L；如果L中已经满k个点，并且当前结点与P的距离小于 L列表中最远的距离的点，则用结点替换掉L中距离P最远的点。
c:计算p和当前结点切分线的距离（作垂线）。如果该距离大于等于L列表中距离最远的点并且L列表中已经有k个点，则在当前结点的另外一边（没访问过的那边）不会有更近的点，接着执行（3）；如果该距离小于L列表中距离最远的点或者L列表中不足k个点，则切分线另一边可能有更近的点，因此在当前结点的另外一边可能有更近的点，因此在当前结点的另外一边从（1）开始重新执行。

大概过成就是这样，下面有一个链接，链接里有距离寻找K近邻的例子。
搜索kd数k近邻搜索样例