江苏龙网

  1. 首页 > 生活 > >

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

最近邻的快速计算是机器学习中一个活跃的研究领域。最简单的近邻搜索的实现涉及数据集中所有成对点之间距离的暴力计算： 对于 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 那样好.在机器学习中往往使用的数据集是非常结构化的, 而且非常适合基于树结构的查询。


推荐阅读


上一篇：微信以后会不会把虚拟现实AR直接加到扫一扫里面，与扫二维码并存呢这样就不用下载那么多AR的APP了

下一篇：炉石传说中是否存在着一种“好运机制”