二、 kd树

发布于 2023-07-17 23:38:26 字数 8926 浏览 0 评论 0 收藏 0

实现 $ MathJax-Element-157 $ 近邻法时，主要考虑的问题是：如何对训练数据进行快速 $ MathJax-Element-157 $ 近邻搜索。
最简单的实现方法：线性扫描。此时要计算输入样本与每个训练样本的距离。
当训练集很大时，计算非常耗时。解决办法是：使用 $ MathJax-Element-154 $ 树来提高 $ MathJax-Element-157 $ 近邻搜索的效率。
$ MathJax-Element-154 $ 树是一种对 $ MathJax-Element-157 $ 维空间中的样本点进行存储以便对其进行快速检索的树型数据结构。
它是二叉树，表示对 $ MathJax-Element-157 $ 维空间的一个划分。
构造 $ MathJax-Element-154 $ 树的过程相当于不断的用垂直于坐标轴的超平面将 $ MathJax-Element-157 $ 维空间切分的过程。
$ MathJax-Element-154 $ 树的每个结点对应于一个 $ MathJax-Element-157 $ 维超矩形区域。

2.1 kd树构建算法

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

2.2 kd 树搜索算法

$ MathJax-Element-154 $ 树最近邻搜索算法（ $ MathJax-Element-157 $ 近邻搜索以此类推）：
- 输入：
  - 已构造的 $ MathJax-Element-154 $ 树
  - 测试点 $ MathJax-Element-150 $
- 输出： $ MathJax-Element-150 $ 的最近邻测试点
- 步骤：
  - 初始化：当前最近点为 $ MathJax-Element-341 $ ，当前最近距离为 $ MathJax-Element-370 $ 。
  - 在 $ MathJax-Element-154 $ 树中找到包含测试点 $ MathJax-Element-150 $ 的叶结点：从根结点出发，递归向下访问 $ MathJax-Element-154 $ 树（即：执行二叉搜索）：
    - 若测试点 $ MathJax-Element-150 $ 当前维度的坐标小于切分点的坐标，则查找当前结点的左子结点。
    - 若测试点 $ MathJax-Element-150 $ 当前维度的坐标大于切分点的坐标，则查找当前结点的右子结点。
    在访问过程中记录下访问的各结点的顺序，存放在先进后出队列 Queue 中，以便于后面的回退。
  - 循环，结束条件为Queue 为空。循环步骤为：
    - 从Queue 中弹出一个结点，设该结点为 $ MathJax-Element-331 $ 。计算 $ MathJax-Element-150 $ 到 $ MathJax-Element-331 $ 的距离，假设为 $ MathJax-Element-376 $ 。
      若 $ MathJax-Element-403 $ ，则更新最近点与最近距离：
      $ \text{distance}_{nst}=\text{distance}_q,\quad \mathbf{\vec x}_{nst}= \mathbf{\vec x}_q $
    - 如果 $ MathJax-Element-331 $ 为中间节点：考察以 $ MathJax-Element-150 $ 为球心、以 $ MathJax-Element-364 $ 为半径的超球体是否与 $ MathJax-Element-331 $ 所在的超平面相交。
      如果相交：
      - 若Queue 中已经访问过了 $ MathJax-Element-331 $ 的左子树，则继续二叉搜索 $ MathJax-Element-331 $ 的右子树。
      - 若Queue 中已经访问过了 $ MathJax-Element-331 $ 的右子树，则继续二叉搜索 $ MathJax-Element-331 $ 的左子树。
      二叉搜索的过程中，仍然在Queue 中记录搜索的各结点。
  - 循环结束时， $ MathJax-Element-337 $ 就是 $ MathJax-Element-150 $ 的最近邻点。
$ MathJax-Element-154 $ 树搜索的平均计算复杂度为 $ MathJax-Element-152 $ ， $ MathJax-Element-156 $ 为训练集大小。
$ MathJax-Element-154 $ 树适合 $ MathJax-Element-155 $ 的情形，当 $ MathJax-Element-156 $ 与维度 $ MathJax-Element-157 $ 接近时效率会迅速下降。
通常最近邻搜索只需要检测几个叶结点即可：
但是如果样本点的分布比较糟糕时，需要几乎遍历所有的结点：

2.3 示例

假设有 6 个二维数据点： $ MathJax-Element-203 $ 。
构建kd 树的过程：
- 首先从 x 轴开始划分，根据x 轴的取值2,5,9,4,8,7 得到中位数为 7 ，因此切分线为： $ MathJax-Element-207 $ 。
  可以根据x 轴和y 轴上数据的方差，选择方差最大的那个轴作为第一轮划分轴。
- 左子空间（记做 $ MathJax-Element-211 $ ）包含点 (2,3),(5,4),(4,7)，切分轴轮转，从y 轴开始划分，切分线为： $ MathJax-Element-214 $ 。
- 右子空间（记做 $ MathJax-Element-216 $ ）包含点 (9,6),(8,1)，切分轴轮转，从y 轴开始划分，切分线为： $ MathJax-Element-220 $ 。
- $ MathJax-Element-211 $ 的左子空间（记做 $ MathJax-Element-222 $ ）包含点(2,3)，切分轴轮转，从x 轴开始划分，切分线为： $ MathJax-Element-234 $ 。
  其左子空间记做 $ MathJax-Element-258 $ ，右子空间记做 $ MathJax-Element-261 $ 。由于 $ MathJax-Element-264 $ 都不包含任何点，因此对它们不再继续拆分。
- $ MathJax-Element-211 $ 的右子空间（记做 $ MathJax-Element-226 $ ）包含点(4,7)，切分轴轮转，从x 轴开始划分，切分线为： $ MathJax-Element-256 $ 。
  其左子空间记做 $ MathJax-Element-280 $ ，右子空间记做 $ MathJax-Element-303 $ 。由于 $ MathJax-Element-300 $ 都不包含任何点，因此对它们不再继续拆分。
- $ MathJax-Element-216 $ 的左子空间（记做 $ MathJax-Element-230 $ ）包含点(8,1)，切分轴轮转，从x 轴开始划分，切分线为： $ MathJax-Element-267 $ 。
  其左子空间记做 $ MathJax-Element-307 $ ，右子空间记做 $ MathJax-Element-312 $ 。由于 $ MathJax-Element-317 $ 都不包含任何点，因此对它们不再继续拆分。
- $ MathJax-Element-216 $ 的右子空间（记做 $ MathJax-Element-233 $ ）不包含任何点，停止继续拆分。
最终得到样本空间拆分图如下：
样本空间结构图如下：
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 。