5.knn - 二、 kd树 - 《AI算法工程师手册》

二、 kd树

二、 kd树

实现近邻法时，主要考虑的问题是：如何对训练数据进行快速近邻搜索。
最简单的实现方法：线性扫描。此时要计算输入样本与每个训练样本的距离。

当训练集很大时，计算非常耗时。解决办法是：使用树来提高近邻搜索的效率。
树是一种对维空间中的样本点进行存储以便对其进行快速检索的树型数据结构。

它是二叉树，表示对维空间的一个划分。
构造树的过程相当于不断的用垂直于坐标轴的超平面将维空间切分的过程。

树的每个结点对应于一个维超矩形区域。

2.1 kd树构建算法

平衡树构建算法：
- 输入：维空间样本集
- 输出：树
- 算法步骤：
  - 构造根结点。根结点对应于包含的维超矩形。
    
    选择为轴，以中所有样本的坐标的中位数为切分点，将根结点的超矩形切分为两个子区域，切分产生深度为 1 的左、右子结点。切分超平面为：。
    - 左子结点对应于坐标的子区域。
    - 右子结点对应于坐标的子区域。
    - 落在切分超平面上的点( ) 保存在根结点。
  - 对深度为的结点，选择为切分的坐标轴继续切分，。本次切分之后，树的深度为。
    
    这里取模而不是，因为树的深度可以超过维度。此时切分轴又重复回到，轮转坐标轴进行切分。
  - 直到所有结点的两个子域中没有样本存在时，切分停止。此时形成树的区域划分。

2.2 kd 树搜索算法

树最近邻搜索算法（近邻搜索以此类推）：
- 输入：
  - 已构造的树
  - 测试点
- 输出：的最近邻测试点
- 步骤：
  - 初始化：当前最近点为，当前最近距离为。
  - 在树中找到包含测试点的叶结点：从根结点出发，递归向下访问树（即：执行二叉搜索）：
    - 若测试点当前维度的坐标小于切分点的坐标，则查找当前结点的左子结点。
    - 若测试点当前维度的坐标大于切分点的坐标，则查找当前结点的右子结点。
    在访问过程中记录下访问的各结点的顺序，存放在先进后出队列 Queue 中，以便于后面的回退。
  - 循环，结束条件为Queue 为空。循环步骤为：
    - 从Queue 中弹出一个结点，设该结点为。计算到的距离，假设为。
      
      若，则更新最近点与最近距离：
    - 如果为中间节点：考察以为球心、以为半径的超球体是否与所在的超平面相交。
      
      如果相交：
      - 若Queue 中已经访问过了的左子树，则继续二叉搜索的右子树。
      - 若Queue 中已经访问过了的右子树，则继续二叉搜索的左子树。
      二叉搜索的过程中，仍然在Queue 中记录搜索的各结点。
  - 循环结束时，就是的最近邻点。
树搜索的平均计算复杂度为，为训练集大小。

树适合的情形，当与维度接近时效率会迅速下降。
通常最近邻搜索只需要检测几个叶结点即可：

但是如果样本点的分布比较糟糕时，需要几乎遍历所有的结点：

2.3 示例

假设有 6 个二维数据点：。

构建kd 树的过程：
- 首先从 x 轴开始划分，根据x 轴的取值2,5,9,4,8,7 得到中位数为 7 ，因此切分线为：。
  
  可以根据x 轴和y 轴上数据的方差，选择方差最大的那个轴作为第一轮划分轴。
- 左子空间（记做）包含点 (2,3),(5,4),(4,7)，切分轴轮转，从y 轴开始划分，切分线为：。
- 右子空间（记做）包含点 (9,6),(8,1)，切分轴轮转，从y 轴开始划分，切分线为：。
- 的左子空间（记做）包含点(2,3)，切分轴轮转，从x 轴开始划分，切分线为：。
  
  其左子空间记做，右子空间记做。由于都不包含任何点，因此对它们不再继续拆分。
- 的右子空间（记做）包含点(4,7)，切分轴轮转，从x 轴开始划分，切分线为：。
  
  其左子空间记做，右子空间记做。由于都不包含任何点，因此对它们不再继续拆分。
- 的左子空间（记做）包含点(8,1)，切分轴轮转，从x 轴开始划分，切分线为：。
  
  其左子空间记做，右子空间记做。由于都不包含任何点，因此对它们不再继续拆分。
- 的右子空间（记做）不包含任何点，停止继续拆分。
最终得到样本空间拆分图如下：

样本空间结构图如下：

kd 树如下。
- kd 树以树的形式，根据样本空间的拆分，重新组织了数据集的样本点。每个结点都存放着位于划分平面上数据点。
- 由于样本空间结构图 中的叶区域不包含任何数据点，因此叶区域不会被划分。因此kd 树的高度要比样本空间结构图 的高度少一层。
- 从kd 树中可以清晰的看到坐标轮转拆分。
假设需要查询的点是P=(2.1,3.1) 。
- 首先从kd 树进行二叉查找，最终找到叶子节点(2,3)，查找路径为：Queue=<(7,2),(5,4),(2,3)> 。
- Queue 弹出结点(2,3)：P 到 (2,3)的距离为0.1414 ，该距离作为当前最近距离，(2,3) 作为候选最近邻点。
- Queue 弹出结点(5,4)：P 到 (5,4)的距离为3.03 。候选最近邻点仍然为(2,3)，当前最近距离仍然为0.1414 。
  
  因为结点(5,4)为中间结点，考察以P 为圆心，以0.1414 为半径的圆是否与y=4 相交。结果不相交，因此不用搜索(5,4) 的另一半子树。
- Queue 弹出结点(7,2)：P 到 (7,2)的距离为5.02 。候选最近邻点仍然为(2,3)，当前最近距离仍然为0.1414 。
  
  因为结点(7,2)为中间结点，考察以P 为圆心，以0.1414 为半径的圆是否与x=7 相交。结果不相交，因此不用搜索(7,2)的另一半子树。
- 现在Queue 为空，迭代结束。因此最近邻点为(2,3) ，最近距离为0.1414 。
假设需要查询的点是P=(2,4.5) 。
- 首先从kd 树进行二叉查找，最终找到叶子节点(4,7)，查找路径为：Queue=<(7,2),(5,4),(4,7)> 。
- Queue 弹出结点 (4,7) ：P 到 (4,7) 的距离为3.202 ，该距离作为当前最近距离， (4,7) 作为候选最近邻点。
- Queue 弹出结点 (5,4) ：P 到 (5,4) 的距离为3.041 ，该距离作为当前最近距离， (5,4) 作为候选最近邻点。
  
  因为(5,4) 为中间结点，考察以P 为圆心，以3.041 为半径的圆是否与y=4 相交。
  
  结果相交，因此二叉搜索(5,4) 的另一半子树，得到新的查找路径为：Queue=<(7,2),(2,3)> 。
  
  二叉查找时，理论上P 应该位于结点(5,4) 的右子树。但是这里强制进入(5,4) 的左子树，人为打破二叉查找规则。接下来继续维持二叉查找规则。
- Queue 弹出结点 (2,3) ：P 到 (2,3) 的距离为1.5 ，该距离作为当前最近距离， (2,3) 作为候选最近邻点。
- Queue 弹出结点(7,2)：P 到 (7,2)的距离为5.59 。候选最近邻点仍然为(2,3)，当前最近距离仍然为1.5 。
  
  因为结点(7,2)为中间结点，考察以P 为圆心，以1.5 为半径的圆是否与x=7 相交。结果不相交，因此不用搜索(7,2)的另一半子树。
- 现在Queue 为空，迭代结束。因此最近邻点为(2,3) ，最近距离为1.5 。