标签：KNN 分割第一 KD Tree 所示维度数据节点

0 前言

本文主要讲解KNN算法中用于快速检索最近元素的KD树的构建及查找原理。
为了达到最佳阅读效果，请读者按照本文顺序阅读，文章使用了大量图片帮助读者理解。

1 背景

1.1 为什么要使用KD-Tree?

k近邻法(KNN)最简单的实现方法是线性扫描。这时要计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。
为了提高k近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。

1.2 KD-Tree效率如何？

如果实例点是随机分布的，kd树搜索的平均计算复杂度是(logN)，这里N是训练实例数。
kd树更适用于训练实例数远大于空间维数时的k近邻搜索。
当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。

2 构建原理

2.1 算法简介

上图(图2-1)取自李航统计学习方法，请读者耐心读完。

2.2 后文表述方式

例如我们有一组空间坐标点：{ (x1,y1,z1) , (x2,y2,z2) , (x3,y3,z3) , ... ,(xn,yn,zn) }。

其中x1称作第一个数据的第一维度，y1称为第一个数据的第二维度，z1称为第一个数据的第三维度。
x3称作第三个数据的第一维度，y3称为第三个数据的第二维度，z3称为第三个数据的第三维度。

2.3 构建原理详细阐述

2.3.1 数据集

给定一个二维空间数据集：

根据数据集T，有超矩形区域如下图(图2-2)所示。

2.3.2 分割超区域

构造KD树是根据所有样本的某一维度取中位数进行分割构造。

首先将所有数据按照第一维度(红色数字)从小到大排序，排序后的结果如下所示。

选取中位数的规则是取较大的数值，在上述数据序列中，第一维度(红色数字)的中位数是5和7，故选取较大的数值7，即坐标(7,2)。
由于是按照第一维度取中位数，故以"第一维度=7"将超空间分割成左右两个子区间，分割后如下图(图2-3)所示。
接着对图2-3中右侧二叉树的左右子树分割，对于L1的左子树，第一维度<=7的数据有(2,3)(4,7)(5,4)，将该序列按照第二维度从小到大排序，并取第二维度的中位数4，由于是按照第二维度进行排序，故以"第二维度=4"将超空间分割成上下两个子区间，注意并不是分割整个超空间，而是分割属于该子树的空间(第一维度<=7条件下的子空间)。分割结果如下图(图2-4)所示。
构造L1的右子树，此时有数据(8,1)(9,6)，按照第二维度从小到大排序，取第二维度的中位数6，由于是按照第二维度进行排序，故以"第二维度=6"将超空间分割成上下两个子区间，分割结果如下图(图2-5)所示。
由于本文所给数据集只有两个维度，所以只能以第一维度分割和第二维度分割，当数据集有多个维度时，可以按照第一维度、第二维度、...、第N维度分割。若数据集有三个维度，则绘制出来的分割图应该是三维立体分割，例如下图(2-6)所示。

若在T时刻是按照第N个维度进行区间分割，则下一时刻应该重新以第一维度分割，例如1、2、3、... 、N、1、2、3、...一直循环，直到不可再分。
构造L2的左子树，此时还剩下的数据集只有(2,3)，将(2,3)按照第一维度从小到大排序，取其第一维度的中位数2，以"第一维度=2"将超空间分割成左右两个子区间。分割结果如下图(图2-7)所示。

此时L4的左右子树均没有数据，所以停止构造该节点的子树，而是去构建其他节点的子树。
构造L2的右子树，此时只有一个数据(4,7)，按照第一维度从小到大排序，取其第一维度的中位数4，以"第一维度=4"将超空间分割成左右两个子区间。分割结果如下图(图2-8)所示。

此时L5的左右子树均没有数据，所以停止构造该节点的子树，而是去构建其他节点的子树。
构造L3的左子树，此时只有一个数据(8,1)，按照第一维度从小到大排序，取其第一维度的中位数8，以"第一维度=8"将超空间分割成左右两个子区间。分割结果如下图(图2-9)所示。

此时L6的左右子树均没有数据，所以停止构造该节点的子树，又因为所有的数据均构造完，所以构造终止，其中L4、L5、L6称为叶子节点。

3 KD树的最近邻查找

3.1 算法

上图来源于李航统计学习方法。

3.2 递归向下

根据上文笔者构建了所给数据集的二叉树，如下图(3-1)所示。

假设有点(2,4.5)，基于上图的二叉树构建该点。

step-1，图3-2:

首先对比第一维度，目标点(2,4.5)的第一维度为2<=7，所以应该往L1节点的左子树方向移动。
step-2，图3-3:

再对比第二维度，目标点(2,4.5)的第二维度为4.5>4，所以应该往L2节点的右子树方向移动。
step-3，图3-4:

再对比第一维度，目标点(2,4.5)的第一维度为2<=4，所以应该往L5节点的左子树方向移动。
step-4，图3-5:

又因为L5为叶子结点，所以结束递归操作，此时点(2,4.5)属于线段L5所切分后的左子区域，如上图红色区域所示。

3.3 搜索最近邻

根据上文所给的数据集，笔者构建了超维度分割区域如下图(3-6)所示，假设有目标点(2,4.5)，在图3-6中以点G(粉色)标注。
找到该目标节点的父节点。结果如下图(3-7)所示。

点(2,4.5)在节点L5的左子树上，故点(2,4.5)的父节点是L5。目标节点信息在图3-7中以粉色标注，父节点信息在图3-7中以绿色标注。
绘制临近距离。现设直线L5上的数据点D为最邻近点，以点G为圆心，点D与点G之间的距离为半径画圆，真正的最邻近点一定在该圆上或圆内(来自李航统计学习方法)。如下图(3-8)所示。
回朔。返回到节点L5的父节点L2，节点L2上的点B到圆心的距离小于圆的半径(|BG|<|BD|)，故更新最近邻节点，以点B到点G的距离为新的圆半径，结果如下图(图3-9)所示。
检索子树。又因为直线L2与圆相交(圆心G到直线L2的距离小于圆的半径|BG|)，则需要搜索L2的另一个子树L4极其子树(可能没有)，当检索到直线L4时，发现点A到圆心G的距离更小，故更新新的圆半径，新的圆半径为|AG|。 由于L2的父节点L1所代表的直线并未与圆相交，故L1及其右子树不需要遍历，最终结果如下图(图3-10)所示。

遍历完节点L4后发现节点L4并没有子节点，所有的可遍历节点均已遍历，此时遍历终止，点A就是点G的最邻近点。