最近邻的快速计算是机器学习中一个活跃的研究领域。最简单的近邻搜索的实现涉及数据集中所有成对点之间距离的暴力计算： 对于 D维度中的N个样本来说, 这个方法的复杂度是 O。 对于小数据样本，高效的暴力近邻搜索是非常有竞争力的。 然而，随着样本数N的增长，暴力方法很快变得不切实际了。
KD树
为了解决效率低下的暴力计算方法，已经发明了大量的基于树的数据结构。总的来说， 这些结构试图通过有效地编码样本的 aggregate distance (聚合距离) 信息来减少所需的距离计算量。 基本思想是，若A点距离B点非常远，B点距离C点非常近， 可知点与C点很遥远，不需要明确计算它们的距离。 通过这样的方式，近邻搜索的计算成本可以降低为O或更低。 这是对于暴力搜索在大样本数N中表现的显著改善。
利用这种聚合信息的早期方法是 KD tree 数据结构（* K-dimensional tree* 的简写）, 它将二维 Quad-trees 和三维 Oct-trees推广到任意数量的维度. KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算D-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为O。 虽然 KD 树的方法对于低维度 (D\u0026lt;20) 近邻搜索非常快, 当D增长到很大时, 效率变低: 这就是所谓的 “维度灾难” 的一种体现。
ball树
为了解决 KD 树在高维上效率低下的问题, ball 树 数据结构就被研发出来了. 其中 KD 树沿卡迪尔轴（即坐标轴）分割数据, ball 树在沿着一系列的 hyper-spheres 来分割数据. 通过这种方法构建的树要比 KD 树消耗更多的时间, 但是这种数据结构对于高结构化的数据是非常有效的, 即使在高维度上也是一样.
ball 树将数据递归地划分为由质心 C和半径r定义的节点,使得节点中的每个点位于由r和C
定义的 hyper-sphere 内. 通过使用 triangle inequality（三角不等式） 减少近邻搜索的候选点数:|x+y|\u0026lt;=|x|+|y|通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构。
最近邻算法的选择
对于给定数据集的最优算法是一个复杂的选择, 并且取决于多个因素:
样本数量 N(i.e. n_samples) 和维度(例如. n_features).Brute force 查询时间以 O增长Ball tree 查询时间大约以 O增长KD tree 的查询时间 D的变化是很难精确描述的.对于较小的D(小于20) 的成本大约是O, 并且 KD 树更加有效.对于较大的D成本的增加接近O, 由于树结构引起的开销会导致查询效率比暴力还要低.对于小数据集 (N小于30),log(N)相当于N, 暴力算法比基于树的算法更加有效.KDTree 和 BallTree 通过提供一个 leaf size 参数来解决这个问题:这控制了查询切换到暴力计算样本数量. 使得两种算法的效率都能接近于对较小的N的暴力计算的效率.
数据结构: 数据的 intrinsic dimensionality (本征维数) 和/或数据的 sparsity (稀疏度). 本征维数是指数据所在的流形的维数d\u0026lt;=D, 在参数空间可以是线性或非线性的. 稀疏度指的是数据填充参数空间的程度(这与“稀疏”矩阵中使用的概念不同, 数据矩阵可能没有零项, 但是从这个意义上来讲,它的 structure 仍然是 “稀疏” 的)。Brute force (暴力查询)时间不受数据结构的影响。Ball tree 和 KD tree 的数据结构对查询时间影响很大. 一般地, 小维度的 sparser (稀疏) 数据会使查询更快. 因为 KD 树的内部表现形式是与参数轴对齐的, 对于任意的结构化数据它通常不会表现的像 ball tree 那样好.在机器学习中往往使用的数据集是非常结构化的, 而且非常适合基于树结构的查询。
query point（查询点）所需的近邻数k。Brute force 查询时间几乎不受k值的影响.Ball tree 和 KD tree 的查询时间会随着k的增加而变慢. 这是由于两个影响: 首先, k的值越大在参数空间中搜索的部分就越大. 其次, 使用k\u0026gt;1进行树的遍历时, 需要对内部结果进行排序.当k相比N变大时, 在基于树的查询中修剪树枝的能力是减弱的. 在这种情况下, 暴力查询会更加有效.
query points（查询点）数. ball tree 和 KD Tree 都需要一个构建阶段. 在许多查询中分摊时，这种结构的成本可以忽略不计。 如果只执行少量的查询, 可是构建成本却占总成本的很大一部分. 如果仅需查询很少的点, 暴力方法会比基于树的方法更好.
■网友
正好我也在了解KNN这部分，只谈怎么构造KD树和ball 树;KD树是对依次对K维坐标轴，以中值切分构造的树,每一个节点是一个超矩形，在维数小于20时效率最高--可以参看《统计学习方法》第二章和scikit-learn中的介绍；ball tree 是为了克服KD树高维失效而发明的，其构造过程是以质心C和半径r分割样本空间，每一个节点是一个超球体。
■网友
球树的中文资料比较少，我只简单说下球树搜索最近邻的过程。
KD树在搜索路径优化时使用的是两点之间的距离来判断，而球树使用的是两边之和与第三边大小来判断，即
。
以下图为例搜索点
的半径为 【kNN里面的两种优化的数据结构：kd-tree和ball-tree，在算法实现原理上有啥区别】
内的最近邻，即满足
：
1. 从根节点
开始从上至下递归遍历每个可能包含最终近邻的子空间
。
2. 如果子空间的半径
与 分页标题#e#
之和小于
中心点
到目标点
的距离，即
，接着在满足这样条件的子空间样本点内递归搜索满足
的点就是我们想要的最近邻点了。换句简单的话来说，对于目标空间
，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索。
3. 由于子超球体
与
被
所截，而对于
与
内的子空间，
又被
所截，所以接下来就会在
内进行线性搜索。诸如
这些距离太远的子空间将被舍去。最后
就是最终得到的最近邻。


参考文献:
Mohamad Dolatshah, Ali Hadian, Behrouz Minaei-Bidgoli, "Ball*-tree: Efficient spatial indexing for constrained nearest-neighbor search in metric spaces", ArXiv e-prints, Nov 2015.

■网友
个人见解，kd-tree基于欧氏距离的特性：
balltree基于更一般的距离特性：
因此：kd-tree只能用于欧氏距离，并且处理高维数据效果不佳。balltree在kd-tree能够处理的数据范围内要慢于kd-tree。
■网友
这一句话两句话可说不清，自己去看吧k-d tree算法【机器学习】K-means聚类算法初探
■网友
看看这篇文章吧 作为补充 k-d tree算法原理及实现 - 磊磊落落的博客

来源：(未知)

【】网址：/a/2020/0516/gd474951.html

标题：kNN里面的两种优化的数据结构：kd-tree和ball-tree，在算法实现原理上有啥区别