k近邻算法的实现：kd树

    k近邻算法最简单的实现方法是线性扫描。但当训练集很大时，搜索效率低，为了提高效率，可构建kd树。

一、构建kd树

    以中位数作为切分点得到的kd树时平衡树。kd树本身是一个二叉树，对特征空间进行划分。

    算法：输入：数据集T

                输出：kd树

            1.构造根节点，选择第一个特征为坐标轴，然后只考虑第一个特征，对所有实例的第一个特征的值进行排序，找出中位数，并由此作为切分点，将数据集划分为两大部分。（将落在切分超平面的点即中位数对应点放在结点上）。

            2.重复：依次对各个坐标轴进行切分，再从第一个坐标轴循环切分。

            3.结束：直至两个子区域没有实例存在时停止。

            二维的切分可以如下图：

                    

二、搜索kd树

    构建好kd树看起来是个冗余的过程，但是构建完成之后，对特例点进行找寻邻近点时就会大大提高效率。类似于linux命令的locate和find命令。

    利用kd树进行最近邻搜索：

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

            输出：x的最近邻

            步骤：1.在kd树中找出包含目标点x的叶节点。

                        2.以此叶结点作为当前最近点。

                        3.递归向上回退，对每个结点进行操作：

                            如果该结点保存的实例点比当前最近点距离近，更新最近点为此结点。

                            检查该子节点的父节点的另一子节点对应区域是否有更近点。如果有，更新。

                            接着，递归向上进行搜索。

                        4.当回退到根结点时，搜索结束。

kd树搜索的平均计算复杂度时O(logN)。

kd树更适用于训练示例数远大于空间维数时的k近邻搜索。