理解近似最近邻 (ANN) 算法

近似最近邻 (ANN) 算法会从数据集中找到与给定查询点十分接近的数据点，但并非要找到最接近的唯一数据点。NN 算法会搜遍所有数据以找出最完美的匹配项，但 ANN 算法在找到足够接近的匹配项后就会停止。

这可能听起来是个更不尽如人意的解决方案，但它实际上却是实现快速相似性搜索的关键所在。ANN 会使用智能捷径和数据结构来高效地在搜索空间中进行查找。所以，ANN 算法不会占用大量的时间和资源，让您花费少得多的精力，便能找到足够接近且在大部分实际场景中有用的数据点。

从本质上讲，这是一种取舍。如果必须找到最为匹配的唯一数据点，则您可以使用 NN，但需要在时间和性能方面做出牺牲。但是如果您可以容许准确性方面的些许下滑，那 ANN 几乎肯定是更好的解决方案。

ANN 运行过程的第一部分是降维，降维的目标是将高维数据集转换为低维数据集。我们的目的是：不用分析所有数据，从而降低预测模型任务的复杂性，并提高这一模型的效率。

这些算法所依赖的数学概念是度量空间；数据点就位于度量空间中，而且数据点之间的距离是可定义的。这些距离必须遵循特定规则（非负性、同一性、对称性、三角不等性），而且我们会使用诸如欧氏距离或余弦相似性等常见函数来计算距离。

为了更好地理解这一点，您可以想象自己正在度假，此刻正在搜索您租的别墅。您用不着逐一检查每一栋楼（高维度），而是可以使用地图，这样就把问题简化成了二维问题（低维度）。（此处特意给出一个简单的例子。降维并非 ANN 为提高效率而采用的唯一方法。）

ANN 还会使用精巧的数据结构（称为索引）来提高效率。通过将数据预处理为这些索引，ANN 能够在极大程度上提高在搜索空间中查找内容的速度。您不妨把索引想象成道路标牌；借助道路标牌，您可以知道自己在地图上的位置，从而更快地找到度假别墅。

在快速发展的数据科学领域，效率为王。虽然找到真正的最近邻（精准最近邻搜索）有其价值，但正如我们所讲，这通常需要付出计算成本。这就是 ANN 搜索大放异彩的地方，因为此算法能够提供让人信服的折中方案：闪电般的搜索速度，以及高（虽然并非绝对最高）准确性。

但严格来说，您应该在什么时候放弃其他搜索方法而选择 ANN 呢？

精准最近邻可能会很慢，但如果准确性是您的第一要务，或者您的数据集较小，那它可能是最佳方案。k 最近邻 (kNN) 介于 NN 和 ANN 之间，能够在更短时间内给出结果，同时还能保持高准确性。但确定正确的 k 值是个难题，而且 kNN 也难以用来处理高维数据。

ANN 速度快，效率高，再加上能实现高（但并非绝对最高）准确性，这些特点使得它成为很多情况下的理想选择：

• 大数据集：在处理数百万个乃至数十亿个数据点时，精准 NN 的穷尽特性导致其速度十分慢。ANN 在拥有大量数据的环境中进行搜索时表现出色，能够快速给出结果。

• 高维数据：随着维数的增加，精准 NN 的计算量呈爆炸式增长。在处理诸如图像和文本等复杂数据时，ANN 的降维方法能够有效缩小搜索空间并提高效率。

• 实时应用场景：需要立即获得结果？推荐系统、欺诈检测和异常检测均依赖实时洞察。ANN 在速度方面的优势使得它成为这些场景中的理想方案。

• 可接受的近似度：如果您的应用场景能够容许稍微不准确的结果，那 ANN 的速度就是十分宝贵的优势。例如，在搜索图像时，找到视觉上相似的图像可能就足够了，而不用找到绝对最接近的图像。

向量搜索处理的是被编码为密集向量的数据，会采集复杂关系和嵌入的含义。这使得它十分适用于搜索诸如图像、文本和用户喜好等内容，传统的关键字搜索通常在搜索这些内容时效果并不好。但维数灾难在这里也适用。随着代表这些向量的维度数量的增加，传统搜索方法开始难以应对，速度变慢，效率变低。

ANN 解决这个问题的方法是将重点从寻找精准匹配转移到“足够接近的”匹配。这使得快速检索成为可能，同时您的向量搜索可以在大规模数据集中以闪电般的速度找到相似的向量。它还为您提供内置可扩展性，因此您可以根据需要随意扩展数据集而不会牺牲速度。

实时响应，再加上改进后的相关性和效率，通常意味着 ANN 在解锁向量搜索真正的潜力方面，可以发挥关键作用。

虽然 ANN 的概念能够在搜索时提供令人信服的速度优势，但实际上这个术语涵盖了各种算法工具箱。每种工具都有自己的优缺点，在针对具体的数据和搜索需求选择适合的正确工具时，理解这些细微差别至关重要。

KD 树以层级式的树形结构来组织数据，基于特定维度来划分空间。这种方法支持在低维空间和基于欧氏距离的查询中实现快速高效的搜索。

但是，虽然 KD 树在从低维数据中找到最近邻方面表现出色，但这一方法受制于“维数灾难”。 也就是，当维数增加时，点之间的空间会呈爆炸式增长。在这些高维度场景中，KD 树基于单一轴进行分割的策略已经不再有效。使用此方法进行搜索时，由于需要检查大部分数据，所以它失去了效率优势，其速度之慢堪比对所有点进行简单线性扫描时的缓慢程度。

LSH 是一种强大的 ANN 技术，它会将数据点“哈希”到较低维度空间中，而且在转换过程中能巧妙地保留数据点之间的相似关系。这种聚类方法使得数据点更容易被找到，并且使得 LSH 在搜索庞大的高维数据集（如图像或文本）时在速度和可扩展性方面都能拥有出色表现。而且在提供上述优势的同时，它仍然能够以良好的准确性返回“足够接近的”匹配结果。但请记住，LSH 偶尔也可能产生误报（将非相似点识别为相似），其效果可能会根据距离度量和数据类型而有所不同。有多种旨在处理不同指标（例如欧氏距离、杰卡德相似度）的 LSH 族群，这意味着 LSH 仍然具有很多用途。

Annoy（全称为 Approximate Nearest Neighbors Oh Yeah）并非单一的算法，而是一个开源的 C++ 库，会使用其独有算法来构建和查询树，而不会直接实施 LSH 或 KD 树。它设计用于在高维空间中实现能节省内存且快速的搜索体验，这使得它适用于实时查询。本质上讲，它是一个用户友好型界面，能够灵活应对不同数据类型和搜索场景。Annoy 的优势在于可通过一个界面利用多种 ANN 方法，从而让您选择最适合自身需求的方法。虽然它简化了过程，但请记住：要想实现最佳性能，在 Annoy 中选择正确的内部算法至为关键；而且它的有效性仍然取决于其他因素，例如您的数据和准确性要求。

尽管线性扫描通常不会被归类为 ANN 方法，但它仍值得一提，因为这是一种暴力匹配算法，与其他 ANN 算法一样，也能给出相似的结果。它按顺序对每个数据点都完成迭代过程，计算记录之间的距离，并跟踪最佳匹配结果。由于这一算法十分简单，所以它易于实施，且十分适用于小型数据集。这一更基本方法的缺点是：它在处理大型数据集时效率低下，在处理高维数据时速度较慢，并且在实时应用场景中不具有可行性。

在开始选择 ANN 之前，您需要考虑以下几点：

• 数据集的大小和维度：在处理大型的高维数据集时，可以考虑使用局部敏感哈希；而在处理较小的低维数据集时，则可以选择 KD 树。

• 所需的准确性水平：如果绝对精准度十分重要，那么线性扫描可能是最佳方案，否则，可以考虑使用 LSH 或 Annoy 来快速获得较为准确的结果。

• 计算资源：Annoy 十分灵活，但是在 Annoy 中选择算法时，要考虑内存和处理方面的限制。

请谨记，没有放之四海而皆准的解决方案。尝试不同的 ANN 算法并评估其在处理特定数据时的性能，从而找到可满足您向量搜索需求的理想方案。除了这些方案以外，ANN 算法领域也在持续发展，所以您有必要随时了解发展动态，这样才不会错过能改进搜索体验的新技术。

在庞大而复杂的数据领域，我们需要高效的工具来驾驭其复杂性。ANN 就是一大秘诀，能够让您的相似性搜索更上一层楼。它在速度和可扩展性方面都有优势，尽管您需要在准确性方面稍微做出一些牺牲。而且业界仍在持续不断地开展研究，成果会每周发布，所有这些都会为 ANN 领域带来日新月异的发展。例如，量子计算和 Machine Learning 领域的进步可能会带来更快、更高效的新型 ANN 算法。

我们已经探索了不同的 ANN 算法，以及各种算法的独特优势和缺点。但最终，如何做出最佳选择扔取决于您的具体需求。考虑诸如数据量、维度、准确性要求和资源等因素。试验、探索并选择正确的算法，从而最充分利用 ANN。从图像搜索到欺诈检测，这些算法能够为您带来巨大改善，揭示隐藏的联系，并支持您快速获得数据驱动型洞察。

因此，下次您搜索要听的下一首歌、要看的下一部电影，或者要玩的下一款电子游戏时，请记住在幕后提供支持的无名英雄——ANN 算法，正是它连点成线并建立了联系。

当您准备好后，我们可以通过下面四种方法帮助您从业务数据中获取见解：

1. 开始免费试用，并了解 Elastic 可以为贵公司提供什么帮助。

2. 浏览我们的解决方案，了解 Elasticsearch 平台的运作方式，以及我们的解决方案如何满足您的需求。

3. 了解如何在企业中采用生成式 AI。

4. 与您认识且喜欢阅读此类内容的人分享本篇文章。通过电子邮件、LinkedIn、Twitter 或 Facebook 将本篇文章分享给他们。