如何在Python中使用Spotify的Annoy库进行向量相似度搜索

一个markdown文件里面永远只有一个 ---，前面都是front matter。front matter是文件的元数据，但它跟文件显示和渲染的内容没有关系。 粗体语法请参考此网站 https://sspai.com/post/44617 (opens in a new tab)，https://sspai.com/post/44617 (opens in a new tab)。

import BlogHeader from '../../components/blog-header';

<BlogHeader />

你是否厌倦了在机器学习项目中进行缓慢而低效的最近邻搜索？你是否希望能够加快这一关键步骤，而不会牺牲太多准确性？那么，你的愿望即将实现。欢迎来到近似最近邻搜索之都——Approximate Nearest Neighbor Oh Yeah（Annoy），这是一款Python库正在掀起机器学习界的革命。

在这个全面的指南中，我们将深入研究Annoy，探索它的内部机制、Python实现方式以及为什么它正在迅速成为该领域专业人员的首选。准备好了吗？因为我们将带您踏上一段惊险刺激的快速高效最近邻搜索之旅。

什么是Approximate Nearest Neighbor Oh Yeah（Annoy）？

在我们深入研究细节之前，让我们搞清楚一些定义。**Approximate Nearest Neighbor Oh Yeah（Annoy）**是一种用于更高效地处理最近邻搜索的算法。与执行穷举搜索的传统方法不同，Annoy使用一种巧妙的数据结构——二叉搜索树，对搜索空间进行分区并加快搜索过程。

• 传统方法：速度慢，执行穷举搜索。
• Annoy：使用二叉搜索树进行快速、近似搜索。

Annoy的优势是什么？

您可能会想知道，当有其他算法和库可供最近邻搜索时，为什么应该选择Annoy。以下是一些令人信服的原因:

• 速度：Annoy非常快，得益于其对二叉搜索树的高效利用。
• 内存效率：Annoy使用一个映射到内存的文件，允许多个进程共享相同的数据。
• 灵活性：Annoy支持不同的距离度量，如欧氏距离、曼哈顿距离和角度距离。
• 易于使用：使用其Python库，实现Annoy就像吃个馅饼。

Annoy是如何工作的？

现在我们知道了Annoy是什么，让我们深入了解它的工作原理。在核心层面，Annoy使用一种称为二叉搜索树的数据结构来分区向量空间。这与使用连通图或穷举搜索的传统方法有根本的不同。

核心数据结构：二叉搜索树

在Annoy中，二叉搜索树中的每个节点表示数据集中的一个向量。通过递归地将向量空间分区为两半来构建树。这种分区是使用超平面完成的，超平面与数据集中两个随机选择的向量的距离相等。

• 超平面：用于分区向量空间。
• 随机向量：随机选择的两个向量，用于定义每个超平面。

例如，假设我们有向量(A)和(B)。与(A)和(B)距离相等的超平面会将空间分为两半。距离(A)更近的所有向量将进入左子树，而距离(B)更近的向量将进入右子树。

递归分区：Annoy中的巧妙之处

真正的魔力发生在向量空间的递归分区过程中。树中的每个节点都与将空间分成两个部分的超平面相关联。对于每个子节点，这个过程会重复进行，进一步分区空间，直到每个叶节点包含的元素少于预定义的数量，比如(K)个。

• 叶节点：包含少于(K)个元素。
• (K)：一个用户定义的参数，控制分区的粒度。

通过使用这种树结构，Annoy可以快速确定查询向量属于哪个分区，从而减少需要进行比较的向量数量。这就是Annoy如此快速和高效的原因。

在Annoy中进行索引：逐步指南

在理解了Annoy背后的核心概念之后，现在是时候动手进行一些实际实现了。索引是使用Annoy的首个关键步骤，这是二叉搜索树的魔法发挥作用的地方。

步骤1：安装Annoy库

首先，您需要安装Annoy库。可以使用pip轻松完成此操作：

pip install annoy

步骤2：导入库并初始化索引

安装完成后，导入库并初始化Annoy索引，方法如下：

from annoy import AnnoyIndex
 
# 使用40个维度初始化索引
t = AnnoyIndex(40, 'angular')

• 40：每个向量的维度数。
• 'angular'：所使用的距离度量（可选欧氏距离、曼哈顿距离和角度距离）。

步骤3：向索引中添加项目

现在，将项目（向量）添加到索引中。每个项目由一个整数ID来标识。

# 向索引中添加三个向量
t.add_item(0, [1.0, 2.1, 3.2, ...])
t.add_item(1, [4.5, 5.1, 6.3, ...])
t.add_item(2, [7.2, 8.1, 9.4, ...])

步骤4：构建索引

在添加完所有项目后，构建索引。这是Annoy构建二叉搜索树的地方。

# 使用10棵树构建索引
t.build(10)

• 10：索引中的树的数量。树的数量越多，准确性越高，但查询时间越慢。

步骤5：保存和加载索引

您可以将索引保存到磁盘并在以后进行查询时加载。

# 保存索引
t.save('my_index.ann')
 
# 加载索引
u = AnnoyIndex(40, 'angular')
u.load('my_index.ann')

通过以下步骤，您已成功创建了一个用于快速和高效最近邻查询的Annoy索引。

如何查询最近邻的Annoy？

一旦您构建了索引，查询最近邻就变得非常简单。get_nns_by_item和get_nns_by_vector方法是您用于这个目的的首选函数。

使用get_nns_by_item

这个方法检索给定项在索引中的最近邻。

# 查找离项0最近的5个邻居
print(t.get_nns_by_item(0, 5))

使用get_nns_by_vector

或者，您可以找到与特定向量最接近的邻居。

# 查找离给定向量最近的5个邻居
print(t.get_nns_by_vector([1.0, 2.1, 3.2, ...], 5))

这两种方法都返回一个按照与查询项或向量的距离排序的项ID列表。

3个Python Annpy示例

示例1：基本初始化和构建索引

在这个示例中，我们使用数据集初始化Annoy索引，并使用指定数量的树构建索引。这是大规模最近邻搜索的常见用例。

from annoy import AnnoyIndex
import os
import logging
 
def main(args):
data = Dataset(args.dataset)
f = data.base.shape[1]
t = AnnoyIndex(f)
idxpath = os.path.join(args.exp_dir, 'sift_annoy_ntrees%d.idx' % ntrees)
 
if not os.path.exists(idxpath):
logging.info("正在添加项...")
for i in range(data.nbae):
t.add_item(i, data.base[i])
logging.info("正在构建索引...")
t.build(ntrees)
logging.info("正在保存索引...")
t.save(idxpath)

在这个示例中，我们使用日志记录来跟踪过程。索引保存在磁盘上，以便在将来运行时快速重新加载。

示例2：处理稀疏数据

在这里，我们演示如何使用稀疏数据构建Annoy索引。当您的数据集是高维稀疏数据时，这特别有用。

from annoy import AnnoyIndex
import numpy as np
from scipy.sparse import csr_matrix
import os
 
def test_build_sparse_annoy_index(annoy_index_file):
data = np.random.choice([0, 1], size=(10, 5))
sparse_data = csr_matrix(data)
index = AnnoyIndex(5, metric='angular')
index.load(annoy_index_file)
assert os.path.exists(annoy_index_file)

在这个示例中，我们使用SciPy库中的csr_matrix来创建稀疏数据。然后，我们从文件中加载一个现有的Annoy索引。

示例3：在推荐系统中使用Annoy

在这个示例中，我们将Annoy集成到推荐系统中，以便快速找到相似的项。

import annoy
import logging
 
def fit(self, Ciu, show_progress=True):
super(AnnoyAlternatingLeastSquares, self).fit(Ciu, show_progress)
logging.debug("正在构建Annoy相似项索引")
 
self.similar_items_index = annoy.AnnoyIndex(self.item_factors.shape[1], 'angular')
for i, row in enumerate(self.item_factors):
self.similar_items_index.add_item(i, row)
self.similar_items_index.build(self.n_trees)

在这里，我们扩展了一个名为AnnoyAlternatingLeastSquares的类，并添加了一个方法来构建相似项的Annoy索引。这使得推荐系统能够更快地获取相似的项。

结论：Annoy - 快速和高效最近邻搜索的首选库

总之，Annoy是任何处理大规模高维数据集并且需要快速近似最近邻搜索的不可或缺的工具。它的速度、效率和易用性使其成为各种应用的首选选择，从推荐系统到自然语言处理和图像识别。虽然它可能没有某些其他算法的精确准确性，但其性能通常已经足够满足实际应用的要求。如果您希望在项目中实现最近邻搜索，Annoy绝对值得考虑。

Annoy的主要用途是什么？

Annoy通常用于推荐系统、自然语言处理和图像识别任务。其快速查找近似最近邻的能力使其在这些应用中非常理想。

Annoy如何实现其速度？

Annoy使用一组树，具体而言是随机投影树，将空间划分为较小的区域。这使它能够快速排除不太可能包含最近邻的数据集的大部分数据，从而加快搜索速度。

Annoy适用于所有类型的数据吗？

Annoy特别适用于高维数据。然而，它也可以用于低维数据。关键是选择合适的参数，如树的数量和search_k参数，以优化其在您的特定数据集上的性能。

Annoy与其他最近邻算法相比如何？

Annoy通常比K-D树和Ball树等其他算法更快，占用更少的内存。虽然它是一个近似最近邻算法，但它的准确性对于大多数实际应用来说通常足够好。

我可以在Python以外的语言中使用Annoy吗？

是的，Annoy提供了C++、Java和Lua等其他语言的绑定。这使它具有灵活性，适用于各种类型的项目集成。

优化Annoy的一些高级技术有哪些？

一些高级技术包括使用不同的距离度量、优化树的数量以适应特定的用例，以及对于大型数据集使用内存映射文件。这些技术可以帮助您更好地提升Annoy索引的性能。

想了解最新的LLM新闻吗？查看最新的LLM排行榜！