KD树

建树过程

1. KD树建树采用的是从m个样本的n维特征中，分别计算n个特征的取值的方差，用方差最大的第k维特征nk来作为根节点。
2. 对于这个特征，我们选择特征nk的取值的中位数nkv对应的样本作为划分点，对于所有第k维特征的取值小于nkv的样本，我们划入左子树，对于第k维特征的取值大于等于nkv的样本，我们划入右子树，
3. 对于左子树和右子树，我们采用和刚才同样的办法来找方差最大的特征来做更节点，递归的生成KD树。

---

http://www.cnblogs.com/pinard/p/6061661.html