KD树(k维树的简称)是一种用于组织多维坐标空间中各点的数据结构。它使用垂直于坐标轴的超平面递归划分空间,将分割面两侧的点放入不同子树。这种组织方式使搜索能够排除不可能包含相关结果的区域。KD树广泛应用于计算几何、机器学习和计算机图形学,尤其适用于低维空间中的范围搜索和最近邻查询。
结构与空间划分
KD树是一种二叉树。每个内部节点都指定一个分割坐标和一个分割值。对于点 ,在坐标 上以值 进行分割时,可按照如下规则将点分开:
对应的几何边界是超平面 。连续分割将空间划分为与坐标轴对齐的区域。在二维空间中,这些区域是矩形,也可能是无界的;在三维空间中,它们是长方体区域。
两种常见的表示方式是:
- **节点存点树:**每个节点存储一个点,以及划分其余点所需的信息。
- **桶式叶节点树:**内部节点存储分割信息,叶节点则存储一小组点。
在经典构建方法中,分割坐标按各维度循环选取。二维树交替使用水平坐标和垂直坐标。其他构建方法会选择坐标值跨度最大的维度,或采用旨在改善划分区域形状的规则。
尽管名为KD树,它并不是每个节点都有 个子节点的树:通常每个节点至多有两个子节点。字母 表示维数。它推广了二叉搜索树的部分思想,但不同层可以比较不同的坐标,因此并不对所有点施加单一的全局顺序。
构建
一种常见的静态构建方法采用分治法:
- 选择分割坐标。
- 找到中位点或坐标中位数。
- 将点划分为两个大小近似相等的子集。
- 递归构建每棵子树。
- 当子集足够小、可以作为叶节点时停止。
采用适当的同值处理规则时,中位数分割可以生成高度为 的树,其中 是点的数量。坐标值相等的情况需要谨慎处理:如果将所有等于分割值的点都分到同一侧,即使采用基于中位数的构建方法,也可能无法保持平衡。
对于固定维数,如果在每一层使用线性时间的中位数选择算法,构建时间为 。如果在每次递归调用中都从头对各子集排序,则可得到一种直接的 构建方法。预先排序并维护各坐标上的次序也能支持高效构建,但需要额外的维护工作。
平衡的树不一定在几何上也高效。中位数分割能够平衡点的数量,但当数据分布不均匀时,可能产生狭长区域。基于中点的规则和滑动中点规则则更注重空间划分,有时会为此牺牲点数上的平衡。
二维示例
考虑以下点:
一种构建方式是先在第一坐标的中位数附近进行分割,再在得到的每个子集中按第二坐标分割。更深的层次则重新使用第一坐标。
对于 附近的查询,搜索最初会向第一坐标较大、第二坐标较小的点所在区域下降。找到一个邻近候选点后,就可能无需逐一检查远处区域中的点,便可将这些区域排除。
搜索操作
精确查找
为了定位某个特定点,搜索会根据分割规则比较该点的坐标,并沿相应的子节点向下查找。在路由规则明确无歧义的平衡树中,这需要访问 个节点。
对于重复点和分割坐标值相等的情况,构建与查找时必须遵循相同的约定。使用浮点坐标时,还需要区分坐标精确相等与由应用定义的邻近关系。
正交范围搜索
正交范围查询返回与坐标轴对齐的盒状区域内的点:
对于每棵子树,其空间区域可分为以下几种情况:
- **与查询区域不相交:**跳过该子树。
- **完全包含在查询区域内:**直接返回其中的点,无需进一步进行几何筛选。
- **部分重叠:**检查该节点,或递归访问其子节点。
对于按坐标循环分割的标准平衡KD树,当维数固定且 ,并对边界退化情况进行适当处理时,经典的结果报告复杂度上界为:
其中 是返回的点数。这一保证适用于上述构建方式和查询模型,并不是所有称为KD树的结构都普遍满足的上界。
最近邻搜索
最近邻查询旨在寻找与查询点 距离最小的已存储点。对于欧氏距离,
精确搜索通常先访问包含查询点的子区域对应的子节点,找到一个初始候选点,再检查其他子树是否可能包含更好的候选点。
如果当前最优距离为 ,则查询点到分割平面的距离可以作为另一侧子树中各点距离的一个简单下界。若该下界大于 ,便可跳过这棵子树。更紧的判定方法是使用查询点到该子树包围盒的最小距离。
对于盒状区域 ,定义:
查询点到该盒状区域的欧氏距离平方为:
由于盒内任意点到查询点的距离都不小于这个值,因此可以利用该下界安全地剪枝。这是分支定界法的一个实例:当某个区域内可能得到的最优结果也无法改进当前答案时,就将其排除。如果必须返回所有距离相同的最近点,则需要相应处理剪枝边界上的等号情况。
搜索多个最近邻时,通常使用一个容量受限的优先队列维护候选点。找到足够多的候选点后,保留的候选点中距离最远者决定当前的剪枝距离。半径查询使用相同的距离界,找出指定距离内的所有点。
近似搜索
近似查询通过放宽结果要求来减少工作量。有些方法保证返回的最近邻距离 满足:
其中 是真实的最近邻距离,。另一些方法则限制检查的叶节点或节点数量,提供经验上的速度与准确度权衡,而不作上述保证。
近似规则是搜索算法的一部分,并不是树本身自动具备的性质。
复杂度与性能
KD树的性能取决于维数、数据分布、分割策略、查询类型和叶节点大小。
| 操作或性质 | 典型上界或适用条件 |
|---|---|
| 平衡树高度 | |
| 使用高效中位数选择的静态构建 | 固定维数时为 |
| 树的存储空间 | 固定维数时为 |
| 平衡树中的精确查找 | 访问 个节点 |
| 精确最近邻搜索 | 在低维空间中通常较高效;最坏情况下需检查 个点 |
| 正交范围结果报告 | 在经典假设下为 |
这些上界区分了树遍历与坐标运算。当维数可变时,存储点需要 个坐标,而一次距离计算通常需要 的时间。在每个节点存储完整的包围盒,也会引入与维数有关的存储和计算开销。
平衡树并不保证最近邻搜索具有对数时间复杂度。一次查询可能无法通过距离界排除许多区域,从而迫使搜索大量回溯。因此,即使维数固定,精确最近邻搜索在最坏情况下也可能接近完整扫描。
桶式叶节点可以减少递归遍历的开销,并允许对小型点数组进行连续扫描。其实际效率受CPU 缓存行为和向量化距离计算的影响。较小的叶节点有利于更精细的剪枝;较大的叶节点则可减少树导航的开销。
更新
插入操作按照分割规则向下查找,直到到达合适的位置。在简单的不平衡实现中,不利的插入顺序可能产生高度为 的树。
删除比普通二叉搜索树中的删除更复杂,因为替代点必须保持依赖坐标的分区约束。实现时可以针对特定坐标寻找替代点、将点标记为已删除,或重建受影响的子树。
普通搜索树的旋转通常不能直接用作平衡手段,因为旋转可能破坏空间分区。因此,KD树天然适合静态或以静态为主的数据集。动态实现往往依赖定期重建、缓冲更新或专门的平衡方法。
应用
当需要反复执行空间查询、足以抵偿构建索引的成本时,KD树便具有实用价值。
局限与替代结构
高维问题
KD树会受到维数灾难的影响。随着维数增加,包围区域排除点的能力往往减弱,一次搜索可能需要访问树的大部分区域。并不存在一个普遍适用的维数阈值,超过后KD树就一定失效:性能还取决于内在维数、数据规模、数据分布和所需准确度。
当剪枝效果较弱时,直接扫描可能比树遍历更快,尤其是在距离计算能够高效向量化的情况下。高维嵌入向量检索经常使用其他近似最近邻索引。
坐标依赖性与距离函数
轴对齐划分依赖于坐标系。旋转数据集不会改变任意两点之间的欧氏距离,却可能显著改变KD树的性能。同样,除非对度量作出相应调整,否则特征缩放既会改变分区的几何形状,也会改变距离的含义。
KD树尤其适合欧氏距离、曼哈顿距离及其他闵可夫斯基距离等基于坐标的距离。对于更一般的相似性度量,需要有效的区域距离下界才能保证剪枝正确。
相关结构
球树将点组织到以球而非轴对齐盒为边界的区域中。R树使用包围矩形组织对象,广泛用于具有空间范围的对象,而不只是单个点。
四叉树和八叉树通常将二维或三维空间细分为固定数量的子区域。KD树则采用二分方式,并可根据数据调整分割位置。这些替代结构没有哪一种在所有情况下都更优;其有效性取决于被索引的对象和查询负载。
历史
乔恩·路易斯·本特利于1975年提出多维二叉搜索树,作为一种用于关联搜索的结构。KD树后来成为基础性的空间搜索结构,后续研究进一步发展了最近邻搜索方法、其他分割规则、桶式表示和近似查询技术。
如今,这一术语涵盖一系列相关实现,而不是某种固定的布局或构建算法。因此,讨论性能时,需要明确表示方式、分割策略、距离度量,以及查询是精确查询还是近似查询。