最近邻搜索

最邻近搜索(Nearest Neighbor Search, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点q ∈ M,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离或曼哈顿距离决定。

来源:维基百科
简介

最邻近搜索是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点qM,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离曼哈顿距离决定。

最邻近搜索问题在很多领域中都有应用,包括:模式识别,特别是光学字符识别; 统计分类,参见KNN(k-nearest neighbor algorithm); 计算机视觉;数据库,如基于内容的图像检索; 编码理论,见最大似然编码 ; 数据压缩,见MPEG-2标准; 向导系统; 网络营销; DNA测序; 拼写检查,建议正确拼写; 剽窃侦查; 相似比分算法,用来推断运动员的职业表现。

最邻近搜索问题有若干种解决方案的优劣决定于他们求解的时间复杂度和用来查找的数据结构的空间复杂度。一种通常的说法表述为“维数灾难”(curse of dimensionality),指对于在大维数的欧几里得空间里用最邻近搜索的话,无法找到多项式的算法和多对数的查找时间。

方法1:精确检索

1.线性查找(暴力计算brute)

最简单的近邻搜索涉及数据集中所有成对点之间距离的暴力计算:对于D维度中的N个样本来说,这个方法的复杂度是

对于小数据样本,高效的暴力近邻搜索是非常有竞争力的。然而,随着样本数N的增长,暴力方法很快变得不行了.

2.空间分割

七十年代分支限界branch and bound)方法被应用于这个问题。对欧几里得空间来说,这个方法被称为空间索引或者空间访问方法。目前已发展出好几种分支限界方法。恐怕最简单的当属K-D树,它将查找空间不断将父节点包含的区域分为相邻的两部分,每部分包含原来区域中的一半点。求解时,从根节点开始在每个分叉点上对目标点进行计算,直到叶节点。对于给定的维度,查找时间复杂度为O(log N)。另外R-tree也能用来解决动态环境下的最邻近搜索;并且R* tree数据结构能高效插入和删除节点。R-tree不仅支持Euclidean距离,也支持其他距离的计算方式。

对于一般的度量空间中分支限界方法被称为度量树metric trees,特别的例子有VP树Bk树

K-D树

为了解决效率低下的暴力计算方法,已经发明了大量的基于树的数据结构。总的来说,这些结构试图通过有效地编码样本的aggregate distance (聚合距离)信息来减少所需的距离计算量。基本思想是,若A点距离B点非常远,B点距离C点非常近,可知A点与C点很遥远,不需要明确计算它们的距离。 通过这样的方式,近邻搜索的计算成本可以降低为O(Dlog(N))或更低。 这是对于暴力搜索在大样本数N中表现的显著改善。

利用这种聚合信息的早期方法是KD tree 数据结构(* K-dimensional tree* 的简写), 它将二维 Quad-trees 和三维 *Oct-trees推广到任意数量的维度. KD树是一个二叉树结构,它沿着数据轴递归地划分参数空间,将其划分为嵌入数据点的嵌套的各向异性区域。KD树的构造非常快:因为只能沿数据轴执行分区,无需计算D-dimensional距离。一旦构建完成,查询点的最近邻距离计算复杂度仅为O(log(N))。虽然KD树的方法对于低维度(D<20)近邻搜索非常快,当D增长到很大时,效率变低:这就是所谓的“维度灾难”的一种体现。

Ball树

为了解决 KD 树在高维上效率低下的问题, 开发了 ball 数据结构. 其中 KD 树沿笛卡尔轴分割数据, ball 树在沿着一系列的 hyper-spheres 来分割数据. 通过这种方法构建的树要比 KD 树消耗更多的时间, 但是这种数据结构对于高结构化的数据是非常有效的, 即使在高纬度上也是一样.

ball树将数据递归地划分为由质心C和半径r定义的节点,使得节点中的每个点位于由r和C定义的hyper-sphere内.通过使用triangle inequality(三角不等式) 减少近邻搜索的候选点数:

通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它可以在高维度上执行 KD-tree, 尽管实际的性能高度依赖于训练数据的结构.

[描述来源:apache,URL:http://sklearn.apachecn.org/cn/0.19.0/modules/neighbors.html#id10]

方法2:近似法

近似法主要时根据概率找到近似最近的点,如果距离计算方法选择合理,那么近似法几乎能找差距不大的近似点。

1. LSH

LSH(Locality sensitive hashing)其核心思想是:在高维空间相邻的数据经过哈希函数的映射投影转化到低维空间后,他们落入同一个吊桶的概率很大而不相邻的数据映射到同一个吊桶的概率则很小。在检索时将欧式空间的距离计算转化到汉明(Hamming)空间,并将全局检索转化为对映射到同一个吊桶中的数据进行检索,从而提高了检索速度。

2.具有小内部维数的空间最邻近搜索

覆盖树(cover-tree)有一个基于点集倍常量的理论界限。这个查找时间的界限是O(C12 log n),其中c是点集的膨胀常数

3.矢量量化方法

在高纬度空间,树的索引时没有多大用的,因为持续增长的节点太多。为了提高搜索效率,特征向量的一个压缩版本存储在RAM中用于预滤器在首次运行数据集。在第二阶段,确定最后邻近点,它们是通过计算的未压缩的数据从磁盘的距离来获得。[9]

4.基于压缩/聚类的搜索

VA-file方法是基于压缩搜索的一个特例,其中每个特征都是被统一并且独立地压缩。多维空间的最优压缩技术也叫Vector Quantization (VQ),其是通过聚类实现。对数据库进行聚类,并对最“可靠”集群进行检索。在VA-File巨额收益,基于树的索引和顺序扫描观察。还要注意集群和激光冲徊化之间的相似之处。

5.在小的图中进行贪婪搜索

对于NNS一个可能的方法是,对于当前所有点构建一个G(V,E)图 , 距离就是边的权重,通过启发式的搜索获取最临近的点。这种方法也应用于很多场景中,如VoroNet system for the plane, RayNet system 等。

[描述来源:Wikipedia,URL:https://en.wikipedia.org/wiki/Nearest_neighbor_search#cite_note-msw2014-14]

发展历史

最邻近搜索问题早先都是用基本的线性来解决该问题,但是因为“维数灾难”问题,导致计算消耗太大。最邻近搜索问题再次兴起于20世纪70年代。

方法一:基于空间分割的方法

第一种是使用分类树来进行空间分割,例如Freidman(1977)等人提出的KD-Tree ,Bayer and McCreight ( 1972) 提出的B-trees ,Guttman(1984)等人提出的Ball-tree。但是依旧存在运行速度低下的情况,如KD-树在高纬度时,效率就不尽人人意。因此,Arya et al. 等人提出了KD-树的演变算法,称为“error bound” 错误约束approximate search,也就是错误约束的近似临近搜索算法。另一种近似最近邻的方法是通过限制在搜索过程中花费的时间进行搜索搜索,也成为“时间约束”近似搜索,Beis在1997年提出了这个方法。在实践中,人们给出了近似准则,结果比错误约束的近似搜索结果更好。之后,2008年,Silpa-Anan提出随机KD树,也就是多个随机k-d树算法,可以理解成加速近似的近邻搜索。在Muja的2009论文中,作者对多种方法进行了广泛的比较,发现多个随机树是匹配高维数据的最有效方法之一。基于非轴对称分区的k-d树的演化提出了PCA树,RP-tree,和三倍的投影树 。但是并没有发现这些的算法比随机KD-tree空间分解更有效率。

另一类是使用各种聚类算法来分割空间,而不是使用k-d树。例子包括等级的k-means树,GNAT,the anchors hierarchy ,vptree,the cover tree 和spill-tree。Nist和Stewenius提出了词汇树。通过访问分层的k-means的单个叶子来搜索树。在各种实验中,在某些数据下,基于聚类的分割可以达到最好的结果,但是其他的获得最好结果的方法是随机KD树。

Jegou等提出了product quantization approach ,它将空间分解为低纬度的子空间并且展示通过压缩编码作为量化指标展示数据集的点。Babenko和Lempitsky提出了反向多指标,用product quantization替代了反向索引中的标准量子化,获得了搜索空间的更密集细分空间。这两种方法在大数据集中搜索都非常效率,以后可以结合考虑FLANN。

方法二:基于哈希法的最近邻技术

最著名的基于哈希的最近邻技术就是1998年,Indyk and Motwani提出本地敏感哈希( locality sensitive hashingLSH),它使用大量的哈希函数,这些哈希表中元素之间越相似,它们越可能在一起。LSH的变体如multi-probe LSH通过减少哈希表的数量来改善存储成本;LSH Forest更适合于无需手动调整参数的数据。

散列方法的性能很大程度上取决于他们所使用的hashing函数的质量,一个大的研究机构已经针对提高哈希方法通过不同哈希函数方法,如:参数敏感的哈希,光谱hashing等,进行了实验。不同的LSH算法在搜索质量上得到了很多提高。许多项目表明,LSH算法通常比使用空间划分结构算法,如随机k-d树和优先搜索k-means树更加优秀。

方法三:基于图论的最近技术

最近的方法是建立一个图结构来解决最近邻问题。点是顶点,将每个点与其他点相连,边的权重为两点之间的距离。各种各样的启发式策略来找出他们最近的邻居。2002年,T. B. Sebastian 作者选择了一些分离的点,在图中称为“种子”,并从这些种子开始图的探索找出最佳邻居。类似地,2011年,K. Hajebi, 作者首先探索了k-NN图算法,但使用爬山算法的搜索策略,并且随机选择起始点。但是k-NN图结构非常昂贵,所以王等人,通过构建近似最近邻图来缓解构造图的花费。

NNS问题的衍生:

随着NNS问题的不断深入,NNS也衍生出了很多其他问题,最著名的有: k-nearest neighbor searchε-approximate nearest neighbor search.

  1. K-nearest neighbor:KNN查找最邻近的K个点。这种方法常被用在预测分析中,用某点的一些临近点来对它估计和分类。
  2. Approximate nearest neighbor:在一些应用中指需要有个对最邻近的猜测。这种情况下,我们可以用一个不保证能每次都返回绝对正确的最近点的算法,用来提高运算速度或节约存储空间。常常这样的算法大都能找到正确的最近点,但这大大取决于采用点集的分布。采用近似查找的算法包括Best Bin First和Balanced Box-Decomposition Tree。ε近似最邻近查找是目前流行的打破维数灾难的工具。
  3. Nearest neighbor distance ratio:最邻近距离比不直接用目标点和邻近点的距离作为阈值,而是将与到前一个邻近点的距离相关的比值来作为阈值。这被用在基于内容的图像检索中,通过基于本地特征的相似性的“例子查找”来得到图像。更广泛的用途是在一些匹配问题中。
  4. Fixed-radius near neighbors:固定半径近邻就是想根据一个给定的固定距离到一个指定点找出所有欧几里得空间近似点。该数据结构中,距离是固定的,不过是查询点是任意的。
  5. All nearest neighbors:有时,我们需要找到在整个点集中距离所有点都最近的那个点。把最邻近搜索在所有点上运行一次自然能解决问题,但改进的策略能避免点集中距离信息的冗余,从而更高效地查找。比如:当我们算出了X到Y的距离,我们也同时得到了Y到X的距离,于是结果就能被以后的一次求解直接利用。

主要事件

年份事件相关论文
1972Bayer R提出B-tree数据结构Bayer, R. (1972). Symmetric binary B-trees: Data structure and maintenance algorithms. Acta informatica, 1(4), 290-306.
1977Friedman提出KD-tree结构Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977). An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), 3(3), 209-226.
1997Arya基于KD树提出错误约束KD树解决近似临近问题Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998). An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6), 891-923.
1997Beis基于KD树提出时间约束KD树解决近似临近问题Beis, J. S., & Lowe, D. G. (1997, June). Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on (pp. 1000-1006). IEEE.
2006Andoni等人提出基于哈希的算法来解决近似临近问题Andoni, A., & Indyk, P. (2006, October). Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on (pp. 459-468). IEEE.
2008Silpa-Anan提出随机KD树Silpa-Anan, C., & Hartley, R. (2008, June). Optimised KD-trees for fast image descriptor matching. In Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on (pp. 1-8). IEEE.
2009Muja对多种近似临近算法进行比较Muja, M., & Lowe, D. G. (2009). Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP (1), 2(331-340), 2.
2011Jegou, H提出Product quantization来解决临近问题Jegou, H., Douze, M., & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1), 117-128.
2012Wang等人构建近似最近邻图来优化KNN图的花费Wang, J., Wang, J., Zeng, G., Tu, Z., Gan, R., & Li, S. (2012, June). Scalable k-nn graph construction for visual descriptors. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on (pp. 1106-1113). IEEE.

发展分析

瓶颈

  1. 对高阶原始数据的处理。
  2. 基于图论的最近邻技术只适用于小数据范围。
  3. 在很多情况下,高内存和长的运算时间是NNS搜索算法的软肋。

未来发展方向

NNS的解决方法大大提高的运行速度。与此同时,以后的数据基本都是大数据量且高维度的,另外哈希散列方法基于二进制编码的近似最近邻查找虽然大大提高了检索效率,但其检索的准确度始终不高,因此以乘积量化为代表的矢量量化方法可能将是一个可行的办法。除此之外,还可以和FLANN算法进行结合考虑,来优化算法。

Contributor: Ruiying Cai

相关人物
简介
相关人物