球树是一种二叉树数据结构，用于将多维空间中的数据点划分为嵌套超球面（称为球）的层次结构。树中的每个节点表示一个包含数据点子集的球，根节点包含所有点。该树通过递归地将数据点分成两组来构建，每组由自身的球包围，直到满足停止条件，例如最大叶节点大小或最小球半径。球树主要用于加速最近邻查询、相似性搜索和核密度估计，常见于机器学习应用，如数据增强和聚类。
球树相对于其他空间索引结构（如k-d树）的主要优势在于其在高维空间中的性能。k-d树使用轴对齐的超平面划分空间，随着维度增加，由于维度灾难，其效率会下降，而球树使用适应数据局部分布的度量球进行划分。这一特性使得球树能更有效地剪除搜索空间中的大部分区域，尤其是当数据呈现聚类或低内在维度结构时。因此，球树已被广泛应用于各种科学和工程领域，包括机器人学、天文学和神经网络超参数调优。
结构与构建
球树由一组嵌套的球定义，每个球由中心和半径表示。中心通常选为球内包含点的质心，半径是中心到球内任意点的最大距离。该树使用递归算法构建。在每一步，算法选择一个距当前中心最远的点，然后选择距第一个选定点最远的第二个点。这两个点作为枢轴，根据其余点与每个枢轴的接近程度将其划分为两个簇。对每个结果簇重复此过程，直到叶节点包含少于指定数量的点（通常为一个小常数）。
对于n个点，球树的构建时间为O(n log n)（在低维情况下），但在非常高维的情况下，由于距离计算成本增加，构建时间可能退化。存在多种改进构建的策略，包括使用近似最远点选择和平衡树以确保对数深度。度量的选择也会影响结构；尽管欧几里得距离很常见，但球树可以使用任何满足三角不等式的度量构建，例如曼哈顿距离或闵可夫斯基距离。
最近邻搜索
球树最常见的用途是k最近邻（k-NN）搜索，这是分类和回归任务中的基础操作。搜索算法递归遍历树，维护一个已找到的最佳候选点的优先队列。在每个节点，算法计算查询点到节点球中心的距离。如果该距离减去球的半径大于当前第k近的距离，则可以剪除整个子树，因为该球内的任何点都不可能比当前最佳点更近。这种剪除利用了三角不等式，该不等式保证球内的任何点与查询点至少相隔一定距离。
在实践中，球树可以将k-NN的计算复杂度从每次查询O(n)（朴素扫描）降低到平均约O(log n)（对于低内在维度的数据）。然而，随着维度增长，剪除效率会下降。研究人员提出了变体，例如使用双树算法，其中查询树和数据树同时遍历，以进一步提高高维设置下的性能。这些技术已被集成到人工智能框架中使用的库中，例如scikit-learn和亚马逊网络服务 SageMaker。
应用
球树广泛用于机器学习流水线中。在核密度估计中，球树通过聚合点簇的贡献而非单个点来加速局部密度估计的计算。它们也出现在交叉注意力机制和多头注意力架构中，用于变换器模型，其中高效检索相关键可能有益，尽管传统实现使用密集注意力。
在机器学习之外，球树用于机器人学中的路径规划和碰撞检测、计算机图形学中的光线追踪，以及地理信息系统中的空间查询。例如，Waymo和其他自动驾驶系统使用球树索引传感器数据，以快速检索地图特征的最近邻。在天文学中，球树通过快速邻近查询帮助编目恒星。它们的多功能性源于底层度量的简单性和精确查询结果的保证，这与基于哈希的近似方法不同。
与其他结构的比较
球树常与k-d树、R树和局部敏感哈希（LSH）进行比较。k-d树通过轴对齐分割进行划分，在低维（通常小于20）下高效，但在更高维中会因过度回溯而受影响。球树不需要轴对齐分割，能适应数据的形状。R树主要用于数据库中的边界矩形，对任意度量的灵活性较低。LSH提供近似结果，在极高维下更快，但不保证精确最近邻。球树提供了中间选择：精确查询且高维性能优于k-d树，但在非常高维下仍超过线性搜索。
局限性与扩展
球树的一个关键局限性是维度灾难：随着维度数量增长，球体积与周围空间的比例变得极小，使剪除失效。在这种情况下，近似方法如LSH更受青睐。此外，球树是静态结构；插入或删除点需要重建树，除非使用平衡变体，否则不适合动态数据集。
扩展包括k-d树球混合结构，它在较高层级使用球分割，在较低层级使用轴对齐分割，以及覆盖树，它在某些数据假设下保证接近对数的查询时间。研究继续关注自适应度量和学习索引，其中深度学习模型预测分割边界，尽管这些方法仍属小众。
另见
- k-d树
- 最近邻搜索
- 度量树
- 降维