KD_Tree

前言

KNN算法中，计算某点的K个近邻，然后根据K个近邻中最多label数量作为该点的label。如果采用minkowski计算点之间的相似度，采用暴力搜索的方式计算K个近邻，那么时间复杂度是O(n^2)，如果数据集较大，数据维度较高，那么这种计算方式的时间消耗巨大。一种加快搜索过程的方式是KD_tree。

简介

首先考虑一下数据是一维的情况，该问题也就是我们常说的在数组中查找某个数是否存在。解决该问题，如果数组是无序的，那只能遍历一次数组；如果数组是有序的，那么通过折半查找的方式，时间复杂度可以降低为O(logn)。这是折半的方式可以理解为二叉搜索树。如果数据上升到K维度，那么这种树应该怎么建立呢？

kdtree是一棵二叉树，将k维空间划分为小空间块的方法。每个内部节点根据一个维度的属性划分空间，划分界面是一个超平面，超平面正交于划分属性的坐标轴，将空间分为两部分，一部分是左子树空间，另一侧是右子树空间。

操作

建树

建树的过程就是选择划分属性的过程，如果选择不同的划分属性，那么就会有不同结构的树。想一下一维属性的点构成的二叉树，如果该树是不平衡的，那么在树中搜索的效率就会下降，最差降到O(N)。所以在建立KDTree的时候应该考虑平衡问题。（但是，平衡树并不能保证使得所有的情景下都是搜索最优的）建树过程递归过程如下：

• 计算样本集D（该子树需要划分的样本，递归过程中，该样本集不断减小）中方差最大的特征作为划分属性
• 使用堆排序或者归并排序的方式找到该样本集D下，该划分属性的中值（保证树的平衡生长），作为分类点。
• 样本集D中所有样本，划分属性小于划分点属性值的归为左子树，否则归为右子树
• 在左右子树递归调用上述过程，直到没有划分属性。