基于KD树的KNN算法优化
一、介绍
KD树是一颗二叉树，是对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构
KNN最简单的实现是线性扫描，每个测试样本都要与所有训练样本计算距离。当数据量很大时，计算非常耗时，为了提高搜索效率，使用树形结构存储训练集来减少计算距离的次数。通过选择不同维度对空间划分，以选择训练实例在选定维度上的中位数为划分点。
最简单的KD树也就是常见的二叉排序树，此时的K=1，划分维度也只有一个。
以 [5, 7]，[3, 8]，[6, 3]，[8, 5]，[15, 6]，[10, 4]，[12, 13]，[9, 10]，[11, 14] 为例，一颗二维KD树如下图所示：
首先，将所有的样本排序，关键字为第0个维度，取中位数作为根节点
其次，将剩下的两个部分，依次作为根节点的左右子树
最后，左右子树的建立就和重新建立一颗树一样，由递归调用完成
那么KD树是如何提高搜索效率?
其实道理就和二叉排序树相同，例如我们在二叉排序树上找一个小于根节点的数，只需要在左子树里面搜索即可。KD树通过不同维度的划分来在每一个维度上构建了类似的二叉排序树，通过判断来排除右子树是否还需要遍历。
但是这时候有人会有疑问，某个节点只是在某一维度上有序，但是我们需要衡量的是节点到测试样本点的距离，如果在这一维度上我们舍弃了某个点，但由于在其他维度上离样本点很接近导致这个点也有可能是距离比较小的点。其实这里KD树会在遍历的时候不断记录和更新K个最近点（这里的K是KNN中的K并非KD Tree中的K），如果当前遍历的节点在当前维度上离测试样本点的距离小于K个最近点中最远的那个点到测试样本点的距离，那么我们会考虑右子树上可能有更近的点，但是如果在当前维度上离测试样本点的距离大于K个最近点中最远的那个点到测试样本点的距离，那说明右子树中不可能有更近的点，此时就可以舍弃右子树的点。
二、KD Tree的创建
1. 节点数据结构
2. 树的创建
