球状树

在计算机科学中，球状树、球状树或公制树是一种空间划分数据结构，用于组织多维空间中的点。球状树的名字来自于它将数据点分割成一个被称为球的相交超球的嵌套。由此产生的数据结构的特点使其对一些应用非常有用，最明显的是近邻搜索。

球树是一棵二进制树，其中每个节点都定义了一个D维的超球，或称球，包含了要搜索的点的一个子集。树的每个内部节点将数据点划分为两个不相干的集合，这些集合与不同的球相关联。虽然球本身可能相交，但每个点根据其与球中心的距离被分配到分区中的一个或另一个球。树上的每个叶子节点都定义了一个球，并列举了该球内的所有数据点。树上的每个节点都定义了包含其子树上所有数据点的最小的球。这就产生了一个有用的属性：对于球外的一个给定的测试点t，到树中的球B中的任何点的距离都大于或等于t到球表面的距离。从形式上看。{displaystyleD{B}(t)}是指从任何一个点出发的最小可能距离。是球B中任何一点到某个点t的最小可能距离。球型树与M型树有关，但只支持二元分割，而在M型树中，每一级的分割是{displaystyle2m}，从而导致更浅的树结构。折叠，从而导致一个较浅的树结构，因此需要较少的距离计算，这通常会产生更快的查询。此外，M-树可以更好地存储在磁盘上，它是以页为单位组织的。M-树还保持了从父节点开始的距离的预计算，以加快查询速度。Vantage-point树也是类似的，但它们二进制分成一个球，和剩余的数据，而不是使用两个球。

有许多球树的构建算法可用。这种算法的目标是产生一棵树，在平均情况下有效地支持所需类型的查询（如最近邻居）。一个理想的树的具体标准将取决于被回答的问题的类型和基础数据的分布。然而，一个普遍适用的高效树的衡量标准是使其内部节点的总体积最小。考虑到现实世界数据集的不同分布，这是一项艰巨的任务，但是有几个启发式方法可以在实践中很好地划分数据。一般来说，在构建树的成本和这个指标所实现的效率之间存在着权衡。本节简要介绍了这些算法中最简单的算法。StephenOmohundro对五种算法做了更深入的讨论。

最简单的这种程序被称为k-d构建算法，通过与构建k-d树的过程进行类比。这是一种离线算法，也就是说，这种算法可以一次性对整个数据集进行操作。通过递归地将数据点分割成两组，自上而下地构建树。分割是沿着点的分布最广的单一维度选择的，这些集合按该维度上所有点的中位值划分。

为每个内部节点寻找分割点需要在该节点所包含的样本数量上花费线性时间，从而产生了一个时间复杂度为{displaystyleO(n,log,n)}，其中n是数据数量。其中，n是数据点的数量。伪码函数construct_balltree的输入是：D，一个数据点数组。D，一个数据点的数组。输出。B，构造球树的根。如果仍有一个单点，则创建一个包含D中单点的叶子B，然后返回B，否则让c为xxx扩散的维度，让p为考虑c而选择的中心点，让L、R为沿c维度位于中位数左右的点集，创建有两个子节点的B：B.pivot:=pB.child1:=construct_balltree(L),B.child2:=construct_balltree(R),让B.radius为与p之间的xxx距离，返回Bendif结束函数

球树的一个重要应用是加速近邻搜索查询，其目的是找到树中按某种距离指标（如欧氏距离）最接近给定测试点的k个点。一个简单的搜索算法，有时被称为KNS1，利用了以下的距离属性