k近邻算法的实现：kd树

当特征空间维度大，训练数据容量大时，如何对训练数据进行快速k近邻搜索。

k近邻法最简单的实现方式是线性扫描，这时要计算输入实例与每一个训练实例的距离，当训练集容量大时计算太耗时，这种方法不可行。

为了提高k近邻搜索的效率，可以利用特殊的结构来存储训练数据，以便减少距离的计算次数。kd树就是其中的一种存储结构。

kd树：

kd树定义：kd树是一种对k维空间中的实例进行存储，以便进行快速检索的树形结构。kd树是二叉树，表示对k维空间的一个划分。

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

x(1)选择

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

2重复，对于深度为j的节点，选择x(l)为切分的坐标轴，l=j mod k + 1;以该节点的区域的所有实例的x(l)坐标的中位数作为切分点，将该节点对应的超矩形区域切分为两个子区域。切分由通过切分点，且与坐标轴x(l)垂直的超平面实现。

该节点生成深度为j+1的左右两个子节点，左子节点对应于坐标x(l)小于切分点的子区域，右子节点对应于坐标x(l)大于切分点的子区域。

将落在切分超平面上的点保存在该节点。

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

如何使用kd树进行k近邻搜索。

利用kd树可以省去对大部分数据点的搜索，从而减小搜索的计算量。

包含目标点的叶节点对应包含目标点的最小超矩形区域。以此叶节点的实例点作为当前最近点。

用kd树搜索最近邻点：

输入：构造好的kd树，目标点：x;

输出：x的最近邻点

1在kd树中找出包含目标点x的叶节点，从根节点出发递归的访问kd树。若目标点x当前纬度的坐标小于切分点的坐标，移动到切分点的左节点，否则移动到右节点。直到子节点为叶节点为止。

2以此叶节点为当前最近点。

3递归的向上回退，遇到每个节点进行以下操作：

a如果该节点保存的实例点比当前最近点距离目标点更近，则将当前最近点更新为该实例点。

b当前最近点一定存在于该节点的一个子节点对应的区域。检查该子节点的父节点的另一个子节点对应的区域是否存在离目标点更近的点。具体的 ，检查该子节点对应的区域是否和以目标点为秋心，以目标点与当前最近点距离为超球体相交。

如果不相交，向上回退。

如果相交，可能在另一个子节点对应的区域内存在距离目标点更近的点，最近邻搜索另一个子节点。

4当回退到根节点时，搜索结束，最后当前最近点作为目标点x的最近邻点。

复杂度：如果实例点是随机分布的，那么kd树搜索的复杂度是O(logN),N是训练实例数。

适用于：训练实例数远远大于空间维度数的k近邻搜索。当空间维数接近于训练实例数时，搜索效率下降，接近于线性扫描。