k近邻法 kd树 平衡kd树

k近邻法

k近邻法的思想：

k近邻法是一种基本分类与回归方法。输入为实例的特征向量，输出为实例的类别（可取多类）。具体过程是：给定一个已经分好类的数据集，对于新的实例，加入此数据集，以离这个点最近（距离度量）的k个点（k值选取）的类别进行多数表决（分类策略）去决定这个新的实例的类别。

k近邻法三要素：

k值的选择：

k小，用于训练的点少，只有新实例点旁边的点起作用（表决），近似误差小，估计误差大；k大，用于训练的点的数量多，模型较简单，近似误差大，估计误差小。

距离的度量：

特征空间中两个实例之间的距离是两个实例之间相似程度的度量。距离的度量方式有L1距离(曼哈顿距离)L2距离（欧式距离）,更一般的Lp距离或明氏距离。

分类的策略：

多数表决。等价于经验风险最小化。

kd树

kd树是什么：

k近邻法需要判断实例点之间的距离，大规模数据时，不停的计算距离显然是一件十分耗时的事情。为了减少计算的次数以提高效率，考虑用特殊的结构去存储训练数据，这里用kd树来存储。kd树首先是一种二叉树。因为数据可以是高维的，所以对应的kd树的每个节点都是一个k维数值点的二叉树。这也是与以前学的二叉树的一个不同。kd树主要应用在高维数据索引上，做空间划分和近邻搜索。以上是kd树的作用，明白了它是用来划分高维空间、存储高维数据的之后，接下来要知道kd树如何构造，怎么就划分了高维空间了，以及怎么样搜索就减少了计算的次数了。

kd树的构造

一维数据构造的二叉树及其查找过程：

比如这是一个班里语文的成绩，现在想找出来成绩在区间[40,80]之间的，很好找，设此集合为S1。

但如果还要求数学成绩在区间[80,90]里，我们就需要同样的方法，在数学成绩二叉树里找出这个集合S2，然后S1∩S2。

那初中九门课呢，如果对每门课都要求了区间，就要求九个集合在求交集嘛？有点麻烦的。所以考虑把每个学生的这九门课成绩放在一起组成一个九维的数据，用这个九维的数据去构造一个二叉树，也就是kd树了，再搜索数据就可以直接从这个树里找。

一步步来，往上先升一维。对于二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)，如何构造kd树呢

首先要选择从哪个维度进行切分。一般选择在哪个维度上坐标值的方差大就选哪个维度（方差大说明分的散，从这个维度切分的比较均匀）。这是二维的数据，我不知道书上算了没反正直接选了第一维切分，但我算了下方差确实第一维大。这个只是顺序问题，肯定不是说选了第一维就不在第二维切分了，只是先在第一维切，然后第二维，然后第一维，循环，直到子区域没有实例点了就停止。这也是kd树的一般构造过程的一步，循环依序取数据点的各维度来作为切分维度，取数据点在该维度的中值作为切分超平面，将中值左侧的数据点挂在其左子树，将中值右侧的数据点挂在其右子树。递归处理其子树，直至所有数据点挂载完毕。

然后构造根节点，根节点是对应于k维空间中包含所有实例点的超矩形区域（这个反正都是固定的）。然后选择第一维坐标的中位数作为切分点，对这个超矩形区域进行第一次切分。中位点怎么选呢，有两种：第一种，算法开始前，对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。
第二种，从原始数据点中随机选择固定数目的点，然后对其进行排序，每次从这些样本点中取中值，来作为分割超平面。该方式在实践中被证明可以取得很好性能及很好的平衡性。这里就选第一种。

以上点集合在第一维从小到大排序为(2,3)，(4,7)，(5,4)，(7,2)，(8,1)，(9,6)；其中值为(7,2)。（注：2,4,5,7,8,9在数学中的中值为(5 + 7)/2=6，但因该算法的中值需在点集合之内，所以本文中值计算用的是len(points)//2=3, points[3]=(7,2)）所以（7，2）这个点就是你构造出来的kd树的根节点了。第一维小于7的挂在左边：（2，3）（4，7）（5，4）；大于7的挂在右边：（8，1）（9，6）。然后左右两边都要对第二维进行切分了，左边三组按第二维排序选出中位数为4，右边选中位数为6，各自切分：

再往下都是叶子节点了，就结束了。

kd平衡树

像上面那个步骤选取中位数为切分点、循环依次按维度切分，构造出来的就是平衡kd树。一个平衡的kd树，其所有叶子节点到根节点的距离近似相等。但一个平衡的k-d tree对最近邻搜索、空间搜索等应用场景并非是最优的。