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

近似最近邻 (ANN) 是一种算法，可在数据集中找到一个非常接近给定查询点的数据点，但不一定是绝对最近的数据点。NN 算法会穷举搜索所有数据，以找到最理想的匹配项；而 ANN 算法则会接受足够接近的匹配项。

这可能听起来是个更不尽如人意的解决方案，但它实际上却是实现快速相似度搜索的关键所在。ANN 会使用智能捷径和数据结构来高效地在搜索空间中进行查找。因此，它无需耗费大量时间和资源，就能以更少的努力识别出足够接近且在大多数实际场景中有用的数据点。

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

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

这些算法基于度量空间这一数学概念：数据点位于度量空间中，而数据点之间的距离可以被定义。这些距离必须遵循特定规则（非负性、同一性、对称性、三角不等式），并可通过欧氏距离或余弦相似度等常见函数进行计算。

为了更好地理解这一点，可以想象您正在度假，并在寻找自己租下的别墅。您不必逐一检查每栋建筑（高维问题），而是可以使用地图，将问题简化为二维问题（低维问题）。（这是一个有意简化的示例。降维并不是 ANN 算法用来提升效率的唯一方法。）

ANN 算法还会利用一种称为索引的巧妙数据结构来提升效率。通过将数据预处理到这些索引中，ANN 可以更快地遍历搜索空间。您可以把这些索引想象成路标，帮助您在地图上确定位置，从而更快地抵达度假别墅。

在快速发展的数据科学领域，效率至关重要。虽然找到真正的最近邻（精确最近邻搜索）很有价值，但正如我们前面所说，这通常需要付出计算成本。这正是 ANN 搜索的优势所在：它提供了一种极具吸引力的折中方案，即以极快的速度获得较高但并非绝对的准确性。

但您究竟应该在什么时候放弃其他搜索方法而选择 ANN 呢？

精确最近邻搜索可能速度较慢，但当您优先考虑准确性或使用小型数据集时，它仍是最佳选择。k-近邻 (kNN) 介于 NN 和 ANN 之间，可在保持高准确性的同时提供更快的结果。但 k 值并不容易确定，而且 kNN 在处理高维数据时也会面临挑战。

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

• 大型数据集：在处理数百万甚至数十亿个数据点时，精确最近邻搜索的穷举特性会导致速度变慢。而 ANN 擅长在庞大的数据空间中导航，并能快速提供结果。

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

• 实时应用：需要即时获得结果？推荐系统、欺诈检测和异常检测都依赖实时见解。ANN 的速度使其成为这些场景的理想选择。

• 可接受的近似结果：如果您的应用可以容忍结果存在轻微误差，那么 ANN 的速度优势就会变得非常有价值。例如，在图像搜索中，找到视觉上相似的图像，而不是绝对最接近的那张，可能就已经足够。

向量搜索处理编码为密集向量的数据，捕获复杂的关系和嵌入的含义。这使其成为了搜索图像、文本和用户偏好等内容的理想方案，而传统的基于关键字的搜索往往力不从心。但是维数灾难对其同样适用。因为随着用于表征这些向量的维度数量不断增加，传统的搜索方法会难以应付，进而导致查询速度大幅减慢且效率低下。

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

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

虽然 ANN 的概念在搜索中具有显著的速度优势，但这个术语实际上涵盖了一整套多样化的算法工具。这些算法各有优势和取舍。理解这些细微差别，对于根据您的具体数据和搜索需求选择合适的工具至关重要。

KD 树以层级式树形结构组织数据点，并基于特定维度划分空间。这有助于在低维空间以及基于欧氏距离的查询中实现快速高效的搜索。

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

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

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

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

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

• 数据集大小与维度：对于大型高维数据，可以考虑使用局部敏感哈希；对于较小且维度较低的数据，可以考虑使用 KD 树。

• 所需准确度级别：如果绝对精确度至关重要，线性扫描可能是最佳选择；否则，可以考虑使用 LSH 或 Annoy，在速度和准确性之间取得良好平衡。

• 计算资源：Annoy 具备灵活性，但在选择其中的算法之前，需要考虑内存和处理能力限制。

请记住，没有一种解决方案可以适用于所有场景。您可以尝试不同的 ANN 算法，并评估它们在您具体数据上的表现，从而找到最适合您向量搜索需求的方案。除了这些选项之外，ANN 算法领域也在不断演进，因此也值得持续关注行业动态，以免错过可能提升搜索效果的新技术。

庞大而复杂的数据世界需要高效的工具来探索。ANN 正是这样一种“秘密武器”，它能将相似性搜索的体验从“好用”提升到“卓越”。它具备速度快、可扩展性强的优点，但代价是在准确性上会有轻微的权衡。相关研究仍在持续推进，几乎每周每周都有新进展，这让 ANN 领域始终保持着动态发展。例如，量子计算和机器学习的进步可能会催生出更快、更高效的新型 ANN 算法。

我们已经探讨了不同的 ANN 算法，每种算法都有其独特的优势与局限。但归根结底，最佳选择取决于您的具体需求。请综合考虑数据规模、维度、准确性要求以及资源等因素。通过不断的试验与探索，选择合适的算法，才能充分释放 ANN 的价值。从图像搜索到欺诈检测，这些算法都扮演着重要角色，能快速揭示隐藏的关联，并驱动数据驱动型洞察。

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

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

1. 开始免费试用，了解 Elastic 如何助力您的业务。

2. 查看我们的解决方案 了解 Elasticsearch Platform 的运作方式，以及我们的解决方案如何满足您的需求。

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

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