Annoy 1个优秀的”邻近搜索”解决方案

Annoy是由 spotify 开源的一个Python第三方模块,它能用于搜索空间中给定查询点的近邻点。

此外,众所周知,Python由于GIL的存在,它的多线程最多只能用上一个CPU核的性能。如果你想要做性能优化,就必须用上多进程。

但是多进程存在一个问题,就是所有进程的变量都是独立的,B进程访问不到A进程的变量,因此Annoy为了解决这个问题,增加了一个静态索引保存功能,你可以在A进程中保存Annoy变量,在B进程中通过文件的形式访问这个变量。

1.准备

开始之前,你要确保Python和pip已经成功安装在电脑上,如果没有,请访问这篇文章:超详细Python安装指南 进行安装。

(可选1) 如果你用Python的目的是数据分析,可以直接安装Anaconda:Python数据分析与挖掘好帮手—Anaconda,它内置了Python和pip.

(可选2) 此外,推荐大家用VSCode编辑器来编写小型Python项目:Python 编程的最好搭档—VSCode 详细指南

Windows环境下打开Cmd(开始—运行—CMD),苹果系统环境下请打开Terminal(command+空格输入Terminal),输入命令安装依赖:

pip install annoy

2.基本使用

Annoy使用起来非常简单,学习成本极低。比如我们随意生成1000个0,1之间的高斯分布点,将其加入到Annoy的索引,并保存为文件:

# 公众号:Python 实用宝典
from annoy import AnnoyIndex
import random

f = 40
t = AnnoyIndex(f, 'angular')  # 用于存储f维度向量
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

t.build(10) # 10 棵树,查询时,树越多,精度越高。
t.save('test.ann')

这样,我们就完成了索引的创建及落地。Annoy 支持4种距离计算方式:

"angular""euclidean""manhattan""hamming",或"dot",即余弦距离、欧几里得距离、曼哈顿距离、汉明距离及点乘距离。

接下来我们可以新建一个进程访问这个索引:

from annoy import AnnoyIndex

f = 40
u = AnnoyIndex(f, 'angular')
u.load('test.ann') 
print(u.get_nns_by_item(1, 5))
# [1, 607, 672, 780, 625]

其中,u.get_nns_by_item(i, n, search_k=-1, include_distances=False)返回第 i 个item的n个最近邻的item。在查询期间,它将检索多达search_k(默认n_trees * n)个点。如果设置include_distancesTrue,它将返回一个包含两个列表的元组:第二个列表中包含所有对应的距离。

3.算法原理

构建索引:在数据集中随机选择两个点,用它们的中垂线来切分整个数据集。再随机从两个平面中各选出一个顶点,再用中垂线进行切分,于是两个平面变成了四个平面。以此类推形成一颗二叉树。当我们设定树的数量时,这个数量指的就是这样随机生成的二叉树的数量。所以每颗二叉树都是随机切分的。

查询方法
1. 将每一颗树的根节点插入优先队列;
2. 搜索优先队列中的每一颗二叉树,每一颗二叉树都可以得到最多 Top K 的候选集;
3. 删除重复的候选集;
4. 计算候选集与查询点的相似度或者距离;
5. 返回 Top K 的集合。

4.附录

下面是Annoy的所有函数方法:

  • AnnoyIndex(f, metric) 返回可读写的新索引,用于存储f维度向量。metric 可以是 "angular""euclidean""manhattan""hamming",或"dot"
  • a.add_item(i, v)用于给索引添加向量v,i 是指第 i 个向量。
  • a.build(n_trees)用于构建 n_trees 的森林。查询时,树越多,精度越高。在调用build后,无法再添加任何向量。
  • a.save(fn, prefault=False)将索引保存到磁盘。保存后,不能再添加任何向量。
  • a.load(fn, prefault=False)从磁盘加载索引。如果prefault设置为True,它将把整个文件预读到内存中。默认值为False。
  • a.unload() 释放索引。
  • a.get_nns_by_item(i, n, search_k=-1, include_distances=False)返回第 i 个item的 n 个最近邻的item。
  • a.get_nns_by_vector(v, n, search_k=-1, include_distances=False)与上面的相同,但按向量v查询。
  • a.get_item_vector(i)返回第i个向量。
  • a.get_distance(i, j)返回向量i和向量j之间的距离。
  • a.get_n_items() 返回索引中的向量数。
  • a.get_n_trees() 返回索引中的树的数量。
  • a.on_disk_build(fn) 用以在指定文件而不是RAM中建立索引(在添加向量之前执行,在建立之后无需保存)。

我们的文章到此就结束啦,如果你喜欢今天的 Python 教程,请持续关注Python实用宝典。

有任何问题,可以在公众号后台回复:加群,回答相应验证信息,进入互助群询问。

原创不易,希望你能在下面点个赞和在看支持我继续创作,谢谢!

给作者打赏,选择打赏金额
¥1¥5¥10¥20¥50¥100¥200 自定义

​Python实用宝典 ( pythondict.com )
不只是一个宝典
欢迎关注公众号:Python实用宝典

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注