kNN 相似性搜索简介及其使用倒排表索引的加速。

维亚切斯拉夫-叶菲莫夫

9 分钟阅读

4 月 28 日

相似性搜索是一个给定查询的问题，其目标是在所有数据库文档中找到与之最相似的文档。

导言

在数据科学中，相似性搜索经常出现在 NLP 领域、搜索引擎或推荐系统中，在这些领域中，需要为查询检索最相关的文档或项目。通常，文档或项目以文本或图像的形式表示。然而，机器学习算法无法直接处理原始文本或图像，这就是为什么文档和条目通常要经过预处理并存储为数字向量的原因。

有时，一个向量的每个分量都可以存储一个语义。在这种情况下，这些表征也被称为嵌入。这种嵌入可能有数百个维度，其数量可达数百万！由于数量如此庞大，任何信息检索系统都必须能够快速检测出相关文档。

在机器学习中，向量也被称为对象或点。

索引

为了提高搜索性能，我们在数据集嵌入的基础上建立了一种特殊的数据结构。这种数据结构被称为索引。在这一领域已经开展了大量研究，并发展出了多种类型的索引。在选择一种索引用于某项任务之前，有必要了解它在引擎盖下是如何运行的，因为每种索引都有不同的用途和优缺点。

本文将介绍最简单的方法--kNN。在 kNN 的基础上，我们将转而使用倒排文件--一种用于更可扩展搜索的索引，可将搜索过程加快数倍。

kNN

kNN 是最简单、最幼稚的相似性搜索算法。考虑一个数据向量集和一个新的查询向量 Q，我们希望找到与 Q 最相似的前 k 个数据向量集向量。事实上，有几种相似度度量方法可以做到这一点。下图展示了其中一些。

相似度指标

训练

kNN 是机器学习中少数几种不需要训练阶段的算法之一。选择一个合适的度量后，我们就可以直接进行预测。

推理

对于一个新对象，算法会穷举计算它与所有其他对象的距离。然后，它会找出距离最小的 k 个对象，并将它们作为响应返回。

kNN 工作流程

显然，通过检查与所有数据集向量的距离，kNN 可以保证得到 100% 的准确结果。然而，这种蛮力方法在时间性能方面非常低效。如果一个数据集由 m 维的 n 个向量组成，那么对于 n 个向量中的每一个向量，都需要 O(m) 个时间来计算查询 Q 与之的距离，从而导致总时间复杂度为 O(mn)。稍后我们将看到，还有更高效的方法。

此外，原始向量没有压缩机制。想象一下，一个数据集有数十亿个对象。在 RAM 中存储所有这些对象可能是不可能的！

kNN 性能。100% 的准确率和无训练阶段会导致推理过程中的穷举搜索和向量的无内存压缩。注：此类图表显示的是不同算法的相对比较。根据具体情况和所选的超参数，性能可能会有所不同。

应用

kNN 的应用范围有限，只能用于以下情况之一：

数据集大小或嵌入维度相对较小。这确保了算法的快速运行。要求算法的准确率必须达到 100%。就准确率而言，没有其他近邻算法能胜过 kNN。

根据一个人的指纹对其进行检测就是一个要求 100%准确的例子。如果某人犯了罪并留下了指纹，就必须只检索到正确的结果。否则，如果系统不是 100% 可靠，那么另一个人就可能被认定有罪，这是一个非常关键的错误。

基本上，有两种主要方法可以改进 kNN（我们将在后面讨论）：

缩小搜索范围。降低向量的维度。

使用这两种方法中的一种时，我们不会再进行穷举搜索。这种算法被称为近似近邻算法（ANN），因为它们不能保证结果百分之百准确。

倒排索引

"倒排索引（也称为张贴列表、张贴文件或倒排文件）是一种数据库索引，存储从内容（如单词或数字）到其在表格、文档或文档集中的位置的映射"--维基百科

执行查询时，会计算查询的哈希函数，并从哈希表中提取映射值。每个映射值都包含一组潜在候选值，然后根据条件对这些候选值进行全面检查，以确定它们是否是查询的最近邻域。这样，所有数据库向量的搜索范围都会缩小。

倒排索引工作流

根据哈希函数的计算方法，该索引有不同的实现方式。我们要研究的实现方式是使用 Voronoi 图（或 Dirichlet 细分图）。

训练

该算法的原理是创建几个不相交的区域，每个数据集点都属于这些区域。每个区域都有自己的中心点，该中心点指向该区域的中心。

有时，Voronoi 区域也被称为单元或分区。

沃罗诺图示例。白点是各分区的中心点，其中包含一组候选者。

沃罗诺伊图的主要特性是，从一个中心点到其区域内任何一点的距离都小于从该点到另一个中心点的距离。

推理

当给定一个新对象时，会计算该对象到所有 Voronoi 分区中心点的距离。然后选择距离最小的中心点，并将该分区中包含的向量作为候选向量。

通过给定的查询，我们搜索最近的中心点（位于绿色区域内）

最终，通过计算与候选者的距离，并选择最接近的 k 个候选者，返回最终答案。

查找所选区域内的最近邻居

正如你所看到的，这种方法比前一种方法要快得多，因为我们不需要查看所有数据集向量。

边缘问题

在提高搜索速度的同时，倒排索引也有一个缺点：它不能保证找到的对象总是最近的。

在下图中，我们可以看到这样一种情况：实际最近的邻居位于红色区域，但我们只从绿色区域选择候选者。这种情况被称为边缘问题。

边缘问题

这种情况通常发生在查询对象位于另一个区域的边界附近时。为了减少这种情况下的错误数量，我们可以扩大搜索范围，根据离对象最近的前 m 个中心点，选择几个区域来搜索候选对象。

在多个区域内搜索最近邻域（m = 3）

探索的区域越多，结果就越精确，计算所需的时间也就越长。

应用

尽管存在边缘问题，但倒排索引在实践中显示出了不错的效果。如果我们想用精度上的些许下降来换取速度上的数倍增长，那么使用它就再合适不过了。

其中一个用例是基于内容的推荐系统。想象一下，它根据用户过去观看过的其他电影向其推荐一部电影。数据库中有一百万部电影可供选择。

通过使用 kNN，系统确实能为用户选择最相关的电影并进行推荐。但是，执行查询所需的时间非常长。我们假设，在文件索引倒置的情况下，系统会推荐第 5 部最相关的电影，这可能是现实生活中的情况。搜索时间比 kNN 快 20 倍。

从用户体验来看，很难区分这两个推荐结果的质量：最相关结果的第 1 位和第 5 位都是从无数可能的电影中推荐出来的好结果。用户可能会对其中任何一个推荐结果都感到满意。从时间角度来看，倒排索引显然是赢家。因此，在这种情况下，最好使用后一种方法。

反转文件索引性能。在这里，我们略微降低了精确度，以提高推理速度。

Faiss 实现

Faiss(Facebook 人工智能搜索相似性）是一个用 C++ 编写的 Python 库，用于优化相似性搜索。该库提供不同类型的索引，这些索引是用于高效存储数据和执行查询的数据结构。

根据 文档中的信息我们将了解如何创建索引和参数化索引。

kNN

采用 kNN 方法的索引在 Faiss 中被称为平面索引，因为它们不压缩任何信息。它们是唯一能保证搜索结果正确的索引。实际上，Faiss 中存在两种平面索引：

IndexFlatL2.相似度以欧氏距离计算。IndexFlatIP.相似度以内积的形式计算。

这两种索引的构造函数都只需要一个参数 d：数据维度。这些索引没有任何可调整参数。

Faiss 实现 IndexFlatL2 和 IndexFlatIP

存储一个向量的一个分量需要 4 个字节。因此，要存储维数为 d 的单个矢量，需要 4 * d 字节。

倒排文件索引

对于描述的倒排文件，Faiss 实现了 IndexIVFFlat 类。与 kNN 的情况一样，"Flat "一词表示不对原始向量进行解压缩，而是完全存储。

要创建这个索引，我们首先需要传递一个量化器，这个对象将决定数据库向量的存储和比较方式。

IndexIVFFlat 有两个重要参数：

nlist：定义训练时要创建的区域（沃罗诺伊单元）数量。nprobe：决定搜索候选对象时需要多少个区域。更改 nprobe 参数无需重新训练。

Faiss 实施 IndexIVFFlat

与之前的情况一样，我们需要 4 * d 字节来存储一个向量。但现在我们还需要存储向量所属数据集的 Voronoi 区域信息。在 Faiss 实现中，每个向量需要 8 个字节。因此，存储单个向量所需的内存为

结论

我们已经了解了相似性搜索的两种基本算法。实际上，kNN 几乎不应该用于机器学习应用，因为除了特定情况外，它的可扩展性很差。另一方面，倒排索引文件为加速搜索提供了良好的启发式算法，其质量可以通过调整超参数来提高。我们还可以从不同角度提高搜索性能。在本文系列的下一部分，我们将介绍其中一种用于压缩数据集向量的方法。