K近邻算法 简介
这一部分就不赘述了，挺基本的。
为啥需要KD-Tree
KD-Tree是存储训练数据的一种结构，因为K近邻算法
没有显示的学习过程，所以每次对目标点进行分类的时候，都需要借助已知的训练数据。而类似感知机这种具有显示的学习过程的算法，会根据训练数据，得出一个模型sign(<w,x>+B)，后续预测直接用训练好的模型进行预测就行了。因为这个特性，所以如果不采取特殊的数据结构对数据进行存储，那么每一次
分类目标点的时候，都要遍历所有的训练数据，时间不可控。对此，KD-Tree就出来了，其实KD-Tree听名字就是一棵树，可以参考二分查找的过程。
什么是KD-Tree
这里先给出一颗KD-Tree的例子，后续再对KD-tree的Construction与Searching进行论述。
每一个节点对应着一个划分(就是一个大饼被刀切了)，如图所示，根节点(30,40)对应了整个输入空间（整个饼），根节点将整个输入控件分为了两类，分别是x<30, x>30，由其两个分支表示。（解释为啥是x，这与选择的特征有关，看图根节点左边是选的x，所以对比x）。这样不断往下划分，最终得到了整个输入空间的划分（左边），对应的数据结构如右边所示。闲话：其实通过上面描述应该就知道KD-Tree存储的什么东西了，它将数据的信息（具体特征的数值大小）表示在了结构上。其与排序二叉树十分类似嘛。
KD-Tree’s Construction
- 数据描述：(5,25) (10, 12) (30, 40) (35, 45) (50, 30) (70, 70)，输入空间为
整个二维平面。即每个样本点，有两个特征，我们假定为(x, y)。我们先展示整个构造过程，再解释构造细节。
随机选择一点(30, 40)，作为
根节点，x<30的(5,25) (10, 12)位于根节点左子树上。大于的就位于右子树。在左子树中，随机选择一点作为
左子树的根节点，这里选择了(5, 25)。然后y<25的位于其左子树，y>25的位于右子树这样不断迭代，最终形成了树的模样。
根据构造出来的树画图：根据
判别条件画垂直的线。如根节点，根据x来判别的，那么就在这一点上，垂直与x轴，将其代表的划分(根节点是整个输入空间嘛)，一分为二。
由上可知，整个过程中存在着3个问题尚未解决：我们在划分时应该选取哪个维度？划分时我们应该选择哪一个值来划分？什么时候停止划分？
应该选择哪一个维度？
一般是交叉维度来进行选择，如有n个维度，那么依次选择(1, 2, 3…n, 1, 2…n…)这样子。上述例子中就是交叉选择(x,y,x,y…)来进行的
维度确定了我们应该选择哪一个点当作划分点？
这个其实理论上来说当然是选择搜索路径最短的那个点，但是这好像不是很容易达到。《统计学习方法》中采用的方法是
采用中位数当作划分点，这样可以保证整个树是平衡的。如上述第一步骤中，x的中位数是(30, 40) (以左边为基准的话)。那么根节点就是(30, 40)。我们什么时候停止划分?
这是我们自己设定阈值，我们知道，每一个点对应一个划分区域，那么我们可设定
threshold = 10，表示如果这个划分区域中，1
2if num(point_In_Split) < threshold
End Spliting.
KD-Tree’s Searching
这个我懒得描述了，看李航老师《统计学习方法》上就有。需要更正的一点是（我觉得其算法3.3漏了一个判别步骤），算法3.3
的(1)中，强调的是“直到子节点为叶节点为止”，但是有可能搜索结束后发现结束的那个节点并不是叶节点，如(50,30)，那么就要在(50, 30)下添加一个空节点，然后以该空节点作为"包含目标点x的叶节点"。