关于kd树的构建搜索有关问题
李航博士的《统计学习方法》毋庸置疑是机器学习的经典入门书籍之一，本文是针对其中KNN算法中的KD树进行略微细致的论述。由于鄙人学识尚浅（是真的很浅），所以如果有误，希望大家指正。
关于KNN近邻算法请参考《统计学习方法》中的叙述，这里不再重复凑字数叙述了。
KD树的构建亦可以参考《统计学习方法》中的叙述，需要注意的是目前KD树在构建时，特征选取不再是《统计学习方法》中的轮着来，而是选取方差最大的特征。这里举出一个我认为比较好的例子。树与其映射到坐标系后的结果如下图所示。
观察叶子节点的位置，叶子节点都是分布在其父节点所在“墙壁的”两边，所以KDD可以理解为“分房子”，所有的非叶子节点都是卡在“墙壁”之中，作为“墙壁的分界点”。所有叶子节点都在分好了的房子之中呆着。这里我们再描述KD树的搜索方式，我认为《统计学习方法》中的KD树最近邻搜索方式有点晦涩难懂，或许是我太蠢了吧。。。
KD树最近邻搜索方式：
输入：已构造完毕的KD树，目标点X；
输出：目标点X的最近邻。
中间变量：需要一个T变量表示当前与目标点X最近的节点
一、根据目标点X的坐标，从根节点开始按照每个节点的切分规则向下搜索，直到节点为叶子节点，则停止搜索。（其实这一部分有一个问题，就是如果想要搜索的叶子节点不存在 怎么办的问题，我目前看到的算法是，如果当前搜索节点只有一个叶子节点，则无视切分规则直接落在该叶子节点上。此部分我们后面再讨论）
二、到达了叶子节点，计算目标点X到该叶子节点的距离，如果此时T变量为空，或者目标点到该叶子节点的距离小于目标点X到T节点的距离，则T替换为当前叶子节点，并且标记此 叶子节点，表示已计算过。
三、如果当前节点不是已被标记过的根节点，则执行1，否则输出T，算法结束
1、向上搜索节点，如果当前节点是已被标记节点，则再次执行1，否则，执行A再执行B
A、计算目标点X与当前节点的距离，如果目标点到该节点的距离小于目标点X到T节点的距离，则T替换为当前叶子节点，并且标记此叶子节点，表示已计算过
B、计算X到当前节点切分线的距离是否大于等于X到T节点的距离（实际上就是以X为圆心以X到T节点的距离为半径画一个超球体，查看这个超球体是否与分开这个节点的墙 壁相交，相交则表示墙壁的另一边可能有和X节点更近点，否则就没有。），如果大于等于，则另一边不会有更近的点，执行（三），如果小于，则表示另一边可能有更近的点，则到另一边去找，即将另一边作为一颗新的树从（一）开始执行。
（未完待续。。。）