内容 隐藏
1.准备
2.基本使用
3.算法原理
4.附录

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_distances为True，它将返回一个包含两个列表的元组：第二个列表中包含所有对应的距离。

3.算法原理

annoy

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

查询方法：
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实用宝典。

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

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

我要打赏

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

Pandas 性能优化
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。