更新于 2026年8月10日

KD 树#

术语解释#

KD 树（K-Dimensional Tree）是一种用于组织 $k$ 维空间中样本点的基于特征维度划分的数据结构。 KD 树在本质上等同于二叉搜索树，区别在于其每个节点存储的是一个 $k$ 维的样本点，而非单一数值。

二叉搜索树示意图

KD 树在构造过程中，每一层节点会循环地选择 $k$ 个维度中的一个进行比较，同时为了保证树的平衡，通常选择当前子树中该维度取值的中位数作为切分点。

KD 树示例图

通过这种交替选择特征维度进行划分的方式，KD 树将整个特征空间分割成多个子空间（矩形区域），每个节点对应空间中的一个划分面。

KD 树特征空间划分图

解决搜索效率瓶颈：K 近邻（KNN）等算法的核心在于如何快速找到距离目标样本最近的点。如果采用暴力遍历（Brute-force）的方法计算所有样本点的距离，当数据量达到一定规模时，计算开销巨大，效率极低。
优化组织结构：为了避免无效的距离计算，需要一种高效的索引结构来组织高维空间数据，从而实现快速地找到当前样本点周围最近的 $K$ 个点。

优点：
- 大幅提升检索速度：KD 树通过搜索策略排除掉不可能存在更优解的子树，避免了全量遍历，极大地提高了最近邻和 $K$ 近邻搜索的效率。
- 应用广泛：除了 KNN 算法外，它也常被用于加速基于密度的聚类算法（如 DBSCAN）中核心样本的搜索过程。相关内容可以参见「11.10 基于密度的聚类算法：DBSCAN 原理与应用」。
- 结构稳健：通过取中位数构建的 KD 树是一棵平衡树，能够保证搜索时的时间复杂度在平均情况下达到 $O(\log n)$ 级别。
缺点：
- 计算复杂度随规模增长：虽然比暴力搜索快，但在大规模或特定算法（如 DBSCAN）中，KD 树搜索的 $O(n \log n)$ 复杂度相较于某些线性迭代算法（如 Kmeans 的 $O(\text{num\_iter})$）仍然显得较慢。
- 受特征维度限制：KD 树在低维空间表现优异，但随着特征维度 $k$ 的增加，其搜索性能会逐渐退化，甚至在极高维情况下效率可能接近遍历搜索（即维度灾难的影响）。
- 实现逻辑复杂：相比于直接计算距离，KD 树的构建与递归搜索逻辑（如回溯判断、子空间排除）实现起来更为繁琐，且在训练数据频繁变动时维护成本较高。