一、kd-tree和ball-tree在算法实现原理上的区别

KD树是对依次对K维坐标轴，以中值切分构造的树,每一个节点是一个超矩形，在维数小于20时效率较高；ball tree 是为了克服KD树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每一个节点是一个超球体。

kd 树是一个二叉树，每一个内部的节点都代表了一个超矩形空间，并且它的子树包含在这个超矩形空间内部的所有样本点。

但是 kd 树对于一些样本分布情况而言效率并不高，比如当大量样本落在一个超矩形的角落的情况，此时使用球树的效率会更高。

球树的结构与 kd 树类似，同样是一个二叉树，根节点选择方式如下：

找到一个中心点，使所有样本点到这个中心点的距离最短。

对于每一个节点的子节点的选择，方式如下：

让我们举一个具体的例子：

对以下样本点构建球树：[1,2], [5,3], [7,9], [1,6], [9,2], [8,4], [4,4], [5,7]

首先建立根节点，找到包含所有样本点的超球体，记录球心位置，作为根节点（超球体可以是最小外接超球体，也可以不是，只需要将符合要求的样本点包含进去即可，当然越小的超球体，在搜索过程中效率越高，最小外接超球体的拟合存在很多方法，可以拉到最后查看本文最后一章，现在假设已经找到最小外接超球体）

找到所有点中距离最远的两个点，并判断其他样本点与这两个点的距离，距离哪个点最近，则将该样本点划分到该点所在的圆内，并得到包含所有相同类别的点的圆的圆心坐标和半径，生成两个子节点。

何时停止空间分割呢，可以设定一个阈值 r，当子节点中包含的样本点数量 <= r 时，即可停止对这个子节点的分割。如果 r=4，此时我们的球树已经构建完毕。

当 r=3，或 r=2，我们还需要对两个子节点做同样的空间分割操作：

球树的每个节点中，需要包含的信息如下：

延伸阅读：

二、随机增量法

对于一个已经将 i-1 个点包含在内的最小外接圆来说，我们增加一个点 i，如何找到所有点的最小外接圆呢？过程如下：

以上就是关于kd-tree和ball-tree在算法实现原理上的区别的内容希望对大家有帮助。

上一篇

脚本语言和c语言，c++，java有啥区别?

下一篇

数据仓库与大数据有什么区别?