KD Tree是KNN算法中用于计算最近邻的快速简便的构建方式。
当样本量少的时候，用brute直接搜索最近邻的方式是可行的。即计算到所有样本的距离。但当样本量庞大时，直接计算所有样本距离的工作量很大，这种情况使用KD Tree可以节约大量时间成本。
KD Tree构建方式
KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用方差最大的第k维特征nk 作为根节点。对于这个特征，选择取值中的中位数 nkv 作为样本的划分点，对于小于该值的样本划分到左子树，对于大于等于该值的样本划分到右子树，对左右子树采用同样的方式找方差最大的特征作为根节点，递归产生KD Tree。
为什么要选择方差最大的进行划分？
构建树的目的是加快我的搜索过程。
既然我想加快我的搜索过程，要就意味着我最终的数据落在某个叶子节点上。我希望只需搜索整个二叉树的某一些列即可，那么最好的划分方式，就是让我的每个分支上数据的差异性最大化。
那么衡量数据差异性的最基础的数学指标是什么？
是方差。方差越大，意味着数据的离散程度就越大，我将离散程度由大到小的数据一分为二，方差小意味着数据更集中到了一起。
KD Tree
示例 KD_Tree的构建：
现在有一个二维样本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、计算x1和x2每一列对应的方差
a、通过pandas计算出的是样本方差:
/ (n-1)
import numpy as np
import pandas as pd
data = np.array([
[2,3],
[5,4],
[9,6],
[4,7],
[8,1],
[7,2]
])
df = pd.DataFrame(data)
df.var()
0| 6.966667
1| 5.366667
dtype: float64
b、通过numpy计算出的是总体方差:
/ n
import numpy as np
import pandas as pd
data = np.array([
[2,3],
[5,4],
[9,6],
[4,7],
[8,1],
[7,2]
])
print(data)
mean =np.mean(data,axis = 0)
var = np.var(data,axis = 0)
a_var = np.sum(pow(data-mean,2),axis = 0)/6
print(var)
print(a_var)
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
特征空间的划分
第一个树的划分：基于x1进行划分
[2,4,5,7,8,9]的中位数是5和7的平均值6。
虽然严格意义上说中位数是6，但是在计算机中我们人为得定义x1的中位数是7。
即 x1 ≤ 7的数据落在左侧；x1 ＞ 7的数据落在右侧；
左侧：（2,3）（5,4）（4,7） （7,2）
右侧: （9,6）（8,1）
第一次划分生成的区域
第二个树的划分：根据右侧（9,6）（8,1）的x2进行划分
下侧：x2 ≤ 6；上侧x2＞6
第二次划分的区域
第二个树的划分：根据左侧（2,3）（5,4）（4,7） （7,2）的x2进行划分
寻找2、3、4、7的中位数 4 进行划分
第三次划分的区域
....
注意：每次生成的划分都是一个矩形。当叶子节点无法被继续划分的时候，KD树的构建完成，递归结束。
KD Tree查找最近邻
我们生成了KD Tree后，现在就可以去预测测试集里面的样本目标点了。
1、对于一个目标点，先在KD树里找到包含目标点的叶子节点。
2、以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。
3、然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交。
4、如果相交就倒这个子节点寻找着是否有更加近的近邻，有的话就更新最近邻。
5、如果不相交，直接返回父节点中的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束。
6、此时保存的最近邻节点就是最终的最近邻。
如果现在想找(2,4.5)这点的最近邻，该如何操作？
1、画出二叉树：
2、寻找(2,4.5)这点：
一个比较好的理解方式：首先找到第一个最近邻，然后画出一个圆。然后逐渐收缩圆的半径，查看每次缩小后的圆是否能够和矩形相交于一个更小的最近邻点，如果有则更新。直到回到根节点。
网友评论