最近邻搜索|Nearest neighbor search

维基百科：https://en.wikipedia.org/wiki/Nearest_neighbor_search
觉得整理的挺好，翻译

最近邻搜索( NNS ) 作为 邻近搜索（proximity search的一种形式，是在给定集合中找到与给定点最接近（或最相似）的点的优化问题（optimization problem）。相似度通常用不相似函数表示：对象越不相似，函数值越大。

形式上，最近邻（NN）搜索问题定义如下：给定空间M中的一组点S和查询点q ∈ M，找到S 中与q的最近点。唐纳德·高德纳( Donald Knuth )在*The Art of Computer Programming* (1973)的第3 篇将其称为邮局问题（post-office problem），指的是为住宅分配最近的邮局的应用程序。这个问题的直接概括是k -NN 搜索，我们需要找到k 个最近点。

最常见的M是一个 度量空间（metric space），相异性表示为距离度量，它是对称的并且满足三角不等式（triangle inequality）。更常见的是，M被视为d维向量空间，其中使用欧几里得距离、曼哈顿距离或其他距离度量来测量相异性。然而，相异函数可以是任意的。一个例子是不对称的Bregman 散度，三角不等式对此不成立。[1]

应用

最近邻搜索问题出现在许多应用领域，包括：

• 模式识别–尤其是光学字符识别
• 统计分类–参见k-最近邻算法
• 计算机视觉
• 计算几何–参见最近的点对问题
• 数据库–例如基于内容的图像检索
• 编码理论–见最大似然解码
• 数据压缩–见MPEG-2标准
• 机器人传感[2]
• 推荐系统–例如协作过滤
• 网络营销–见上下文广告和行为定位
• DNA测序
• 拼写检查–建议正确的拼写
• 抄袭检测
• 预测职业运动员职业道路的相似度得分。
• 聚类分析–将一组观测值分配到子集（称为聚类）中，以便同一聚类中的观测值在某种意义上是相似的，通常基于欧几里得距离
• 化学相似性
• 基于采样的运动规划

方法

已经提出了针对NNS问题的各种解决方案。算法的质量和有用性取决于查询的时间复杂度以及必须维护的任何搜索数据结构的空间复杂度。通常被称为维度灾难（curse of dimensionality）的非正式观察表明，使用多项式预处理和多对数搜索时间在高维欧几里得空间中没有通用的精确解。

精确方法

线性搜索|Linear search

NNS 问题最简单的解决方案是计算从查询点到数据库中每个其他点的距离，保存当前最好的。此算法中，有时被称为天真的方法（暴力算法），具有运行时间的复杂度为$O(dN)$，其中N是S集合的基数（cardinality）和d是M空间的的维数。没有要维护的搜索数据结构，因此线性搜索没有超出数据库存储的空间复杂度。平均而言，朴素搜索在高维空间上的性能优于空间划分方法。[3]

空间划分|Space partitioning

自 1970 年代以来，分支定界方法已应用于该问题。在欧几里得空间的情况下，这种方法包括空间索引（spatial index）或空间访问方法。已经开发了几种空间划分（space-partitioning）方法来解决 NNS 问题。可能最简单的是kd 树，它迭代地将搜索空间平分为两个 区域，其中包含父区域的一半点。通过评估每个拆分处的查询点，通过从根到叶遍历树来执行查询。根据查询中指定的距离，可能还需要评估可能包含命中的相邻分支。对于恒定维度查询时间，平均复杂度为$O(logN)$ [4]在随机分布点的情况下，最坏情况复杂度为$O(k{N}^{(}1-1/k))$ [5] 或者，R-tree数据结构被设计为支持动态最近邻搜索上下文，因为它具有高效的插入和删除算法，例如R*树。[6] R-trees 不仅可以为欧几里德距离生成最近邻，还可以用于其他距离。

在一般度量空间的情况下，分支定界方法称为度量树(metric tree)方法。具体示例包括vp-tree和BK-tree方法。

使用一组取自 3 维空间的点并放入BSP 树中，并给定取自同一空间的查询点，给出了寻找离查询点最近的点云点问题的可能解决方案在下面的算法描述中。

对于树的每个分支，猜测点云中最近的点位于包含查询点的半空间中。情况可能并非如此，但它是一个很好的启发式方法。在递归地解决了猜测半空间问题的所有麻烦之后，现在将这个结果返回的距离与查询点到分区平面的最短距离进行比较。后一个距离是查询点与可能存在于未搜索的半空间中的最近可能点之间的距离。如果这个距离大于前面结果中返回的距离，那么显然不需要搜索另一个半空间。如果有这样的需求，那么就必须费力解决另一半空间的问题，然后将其结果与前一个结果进行比较，然后返回正确的结果。当查询点靠近云时，该算法的性能比线性时间更接近对数时间，因为当查询点与最近的点云点之间的距离接近于零时，该算法只需使用查找查询点作为获取正确结果的关键。然后将其结果与前一个结果进行比较，然后返回正确的结果。当查询点靠近云时，该算法的性能比线性时间更接近对数时间，因为当查询点与最近的点云点之间的距离接近于零时，该算法只需使用查找查询点作为获取正确结果的关键。然后将其结果与前一个结果进行比较，然后返回正确的结果。当查询点靠近云时，该算法的性能比线性时间更接近对数时间，因为当查询点与最近的点云点之间的距离接近于零时，该算法只需使用查找查询点作为获取正确结果的关键。

近似方法|Approximation methods

允许近似最近邻搜索算法返回点，其与查询的距离最多为c乘以从查询到最近点的距离。这种方法的吸引力在于，在许多情况下，近似最近邻几乎与精确邻接一样好。特别是，如果距离测量准确地捕捉到用户的质量，那么距离的微小差异是无关紧要。[7]

邻近邻域图中的贪婪搜索

近似图方法（例如 HNSW [8]）被认为是近似最近邻搜索的当前最新技术。[8] [9] [10]

这些方法基于邻近邻域图中的贪婪遍历 $G(V,E)$，其中每一点$x_i\in S$ 与顶点唯一关联 $v_i\in V$. **在集合S中搜索查询q的最近邻采用在图中搜索顶点的形式$G(V,E)$。

基本算法 - 贪婪搜索 - 工作如下：

搜索从输入点顶点开始$v_i\in V$，通过计算从查询 q到其邻域的每个顶点的距离 $v_j:(v_i,v_j)\in E$ ，然后找到具有最小距离值的顶点。如果查询与选定顶点之间的距离值小于查询与当前元素之间的距离值，则算法移动到选定顶点，它成为新的输入点。该算法在达到局部最小值时停止：一个顶点，其邻域不包含比顶点本身更接近查询的顶点。

邻近邻域图的概念在多篇文章中得到了利用，包括 Arya 和 Mount 的开创性论文，[11]在 VoroNet 系统中用于平面，[12]在 RayNet 系统中用于平面$E^n$ , [13]以及在 Metrized Small World [14] 和 HNSW [8]算法中用于具有距离函数的空间的一般情况。在这些作品之前，Toussaint 发表了一篇开创性的论文，其中他介绍了相对邻域图的概念。[15]

局部敏感散列|Locality sensitive hashing

局部敏感散列（LSH）是一种基于对点进行操作的距离度量将空间中的点分组为“桶”的技术。在所选度量下彼此靠近的点以高概率映射到同一个桶。[16]

在具有小的固定维度的空间中搜索最近邻|Nearest neighbor search in spaces with small intrinsic dimension

该cover tree具有基于数据集上的一个理论界限加倍不变。搜索时间的界限是$O(c^{12}logn)$，其中c 是数据集的扩展常数。

投影径向搜索|Projected radial search

在数据是几何点的密集 3D 地图的特殊情况下，传感技术的投影几何可用于显着简化搜索问题。这种方法要求 3D 数据通过对二维网格的投影进行组织，并假设数据在除对象边界之外的相邻网格单元之间是空间平滑的。这些假设在处理诸如测量、机器人和立体视觉等应用中的 3D 传感器数据时是有效的，但通常不适用于无组织的数据。在实践中，该技术对knn问题的平均搜索时间为$O(1)$ 或$O(K)$- 应用于现实世界立体视觉数据时的最近邻问题。 [2]

矢量近似文件|Vector approximation files

在高维空间中，树索引结构变得无用，因为无论如何都需要检查越来越多的节点。为了加速线性搜索，存储在 RAM 中的特征向量的压缩版本用于在第一次运行中预过滤数据集。在第二阶段使用来自磁盘的未压缩数据来确定最终候选对象以进行距离计算。[17]

基于压缩/聚类的搜索|Compression/clustering based search

VA 文件方法是基于压缩的搜索的一种特殊情况，其中每个特征组件都被均匀且独立地压缩。多维空间中的最佳压缩技术是矢量量化(VQ)，通过聚类实现。对数据库进行聚类，并检索最“有希望”的聚类。已经观察到对 VA-File、基于树的索引和顺序扫描的巨大收益。[18] [19]还要注意聚类和 LSH 之间的相似之处。

变体

NNS 问题有许多变体，其中最著名的两个是*k-*最近邻搜索和ε-近似最近邻搜索。

k-最近邻

k-最近邻搜索识别查询的前k 个最近邻。这种技术通常用于预测分析，以根据其邻居的共识来估计或分类一个点。k最近邻图是其中每个点都连接到它的k 个最近邻的图**。

近似最近邻

在某些应用程序中，检索最近邻居的“正确猜测”可能是可以接受的。在这些情况下，我们可以使用一种算法**，该算法不能保证在每种情况下都返回实际的最近邻居，以换取提高速度或节省内存。通常这种算法会在大多数情况下找到最近的邻居，但这在很大程度上取决于被查询的数据集**。

支持近似最近邻搜索的算法包括局部敏感散列、最佳 bin 优先和基于平衡框分解树的搜索。[20]

最近邻距离比

最近邻距离比率不是将阈值应用于从原始点到挑战者邻居的直接距离，而是根据与前一个邻居的距离的比率来应用阈值。它在CBIR中使用局部特征之间的相似性通过“示例查询”来检索图片。更一般地说，它涉及几个匹配问题。

近邻的固定半径

固定半径近邻是一个问题，即希望在距指定点的给定固定距离内有效地找到欧几里得空间中给定的所有点。假设距离是固定的，但查询点是任意的。

所有最近的邻居

对于某些应用程序（例如熵估计），可能有N 个数据点，并希望知道这N 个点中的每一个的最近邻。当然，这可以通过对每个点运行一次最近邻搜索来实现，但改进的策略将是一种利用这N 个查询之间的信息冗余来产生更有效搜索的算法。举个简单的例子：当找到从点X到点Y的距离时，这也告诉了我们从点Y到点X的距离，因此可以在两个不同的查询中重复使用相同的计算。

给定一个固定维度，一个半定正范数（因此包括每个 L p范数），以及这个空间中的n个点，每个点的最近邻可以在$O(nlogn)$ 时间内找到，并且m 个最近邻每个点都可以在$O(mnlogn)$ 时间内找到。[21] [22]

相关

• 球树
• 最近的点对问题
• 聚类分析
• 基于内容的图像检索
• 维度的诅咒
• 数字信号处理
• 降维
• 近邻的固定半径
• 傅里叶分析
• 基于实例的学习
• *k -*最近邻算法
• 线性最小二乘
• 局部敏感散列
• 最小哈希
• 多维分析
• 最近邻插值
• 邻居加入
• 主成分分析
• 范围搜索
• 相似性学习
• 奇异值分解
• 稀疏分布式内存
• 统计距离
• 时间序列
• Voronoi 图
• 小波

参考文献

1. Cayton, Lawerence (2008). “Fast nearest neighbor retrieval for bregman divergences”. Proceedings of the 25th International Conference on Machine Learning. pp. 112–119. doi:10.1145/1390156.1390171. ISBN 9781605582054. S2CID 12169321.
2. Jump up to:a b Bewley, A.; Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds (PDF). Australian Conference on Robotics and Automation.
3. Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). “A quantitative analysis and performance study for similarity search methods in high dimensional spaces” (PDF). VLDB '98 Proceedings of the 24rd International Conference on Very Large Data Bases. pp. 194–205.
4. Andrew Moore. “An introductory tutorial on KD trees” (PDF). Archived from the original (PDF) on 2016-03-03. Retrieved 2008-10-03.
5. Lee, D. T.; Wong, C. K. (1977). “Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees”. Acta Informatica. 9 (1): 23–29. doi:10.1007/BF00263763. S2CID 36580055.
6. Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). “Nearest neighbor queries”. Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.
7. Andoni, A.; Indyk, P. (2006-10-01). “Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions”. 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06). pp. 459–468. CiteSeerX 10.1.1.142.3471. doi:10.1109/FOCS.2006.49. ISBN 978-0-7695-2720-8.
8. Jump up to:a b c Malkov, Yury; Yashunin, Dmitry (2016). “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs”. arXiv:1603.09320 [cs.DS].
9. “New approximate nearest neighbor benchmarks”.
10. “Approximate Nearest Neighbours for Recommender Systems”.
11. Arya, Sunil; Mount, David (1993). “Approximate Nearest Neighbor Queries in Fixed Dimensions”. Proceedings of the Fourth Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas.: 271–280.
12. Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). “Voro Net: A scalable object network based on Voronoi tessellations” (PDF). 2007 IEEE International Parallel and Distributed Processing Symposium. RR-5833. pp. 23–29. doi:10.1109/IPDPS.2007.370210. ISBN 1-4244-0909-8. S2CID 8844431.
13. Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). Peer to Peer Multidimensional Overlays: Approximating Complex Structures. Principles of Distributed Systems. 4878. pp. 315–328. CiteSeerX 10.1.1.626.2980. doi:10.1007/978-3-540-77096-1_23. ISBN 978-3-540-77095-4.
14. Malkov, Yury; Ponomarenko, Alexander; Krylov, Vladimir; Logvinov, Andrey (2014). “Approximate nearest neighbor algorithm based on navigable small world graphs”. Information Systems. 45: 61–68. doi:10.1016/j.is.2013.10.006.
15. Toussaint, Godfried (1980). “The relative neighbourhood graph of a finite planar set”. Pattern Recognition. 12 (4): 261–268. Bibcode:1980PatRe…12…261T. doi:10.1016/0031-3203(80)90066-7.
16. A. Rajaraman & J. Ullman (2010). “Mining of Massive Datasets, Ch. 3”.
17. Weber, Roger; Blott, Stephen. “An Approximation-Based Data Structure for Similarity Search” (PDF). S2CID 14613657. Archived from the original (PDF) on 2017-03-04.
18. Ramaswamy, Sharadh; Rose, Kenneth (2007). “Adaptive cluster-distance bounding for similarity search in image databases”. ICIP.
19. Ramaswamy, Sharadh; Rose, Kenneth (2010). “Adaptive cluster-distance bounding for high-dimensional indexing”. TKDE.
20. Arya, S.; Mount, D. M.; Netanyahu, N. S.; Silverman, R.; Wu, A. (1998). “An optimal algorithm for approximate nearest neighbor searching” (PDF). Journal of the ACM. 45 (6): 891–923. CiteSeerX 10.1.1.15.3125. doi:10.1145/293347.293348. S2CID 8193729. Archived from the original (PDF) on 2016-03-03. Retrieved 2009-05-29.
21. Clarkson, Kenneth L. (1983), “Fast algorithms for the all nearest neighbors problem”, 24th IEEE Symp. Foundations of Computer Science, (FOCS '83), pp. 226–232, doi:10.1109/SFCS.1983.16, ISBN 978-0-8186-0508-6, S2CID 16665268.
22. Vaidya, P. M. (1989). “An O(n log n) Algorithm for the All-Nearest-Neighbors Problem”. Discrete and Computational Geometry. 4 (1): 101–115. doi:10.1007/BF02187718.