Press "Enter" to skip to content

近似最近邻搜索算法 ANNOY(Approximate Nearest Neighbors Oh Yeah)

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

在搜索的业务场景下,基于一个现有的数据候选集(dataset),需要对新来的一个或者多个数据进行查询(query),返回在数据候选集中与该查询最相似的 Top K 数据。

 

Google:the two-tower neural network model

最朴素的想法就是,每次来了一个新的查询数据(query),都遍历一遍数据候选集(dataset)里面的所有数据,计算出 query 与 dataset 中所有元素的相似度或者距离,然后精准地返回 Top K 相似的数据即可。

 

但是当数据候选集特别大的时候,遍历一遍数据候选集里面的所有元素就会耗费过多的时间,其时间复杂度是 因此,计算机科学家们开发了各种各样的近似最近邻搜索方法 (approximate nearest neighbors) 来加快其搜索速度,在精确率和召回率上面就会做出一定的牺牲,但是其搜索速度相对暴力搜索有很大地提高。

 

在这个场景下,通常都是欧式空间里面的数据,形如 其中 是欧氏空间的维度。常用的距离公式包括:

Manhattan 距离: L1 范数;
Euclidean 距离: L2 范数;
Cosine 距离: 1 – Cosine 相似度;
角距离 :用两个向量之间的夹角来衡量两者之间的距离;
Hamming 距离: 一种针对 64 维的二进制数的 Manhattan 距离,相当于 中的 L1 范数;
Dot Product 距离 :

欧氏空间的数据点聚类

在近似最近邻搜索(ANN)领域,有很多开源的算法可以使用,包括但不限于:

Annoy (Approximate Nearest Neighbors Oh Yeah);
ScaNN (Scalable Nearest Neighbors);
Faiss (Billion-scale similarity search with GPUs);
Hnswlib (fast approximate nearest neighbor search);

本文将会重点介绍 Annoy 算法及其使用案例;

 

ANN 的 benchmark

Annoy 的算法思想

 

本文以 中的点集来作为案例,介绍 annoy 算法的基本思想和算法原理。

 

二维欧氏空间中的点集

用 n 表示现有的文档个数,如果采用暴力搜索的方式,那幺每次查询的耗时是 采用合适的数据结构可以有效地减少查询的耗时,在 annoy 算法中,作者采用了二叉树这个数据结构来提升查询的效率,目标是把查询的耗时减少至

 

用中垂线来作为切分平面

刚开始的时候,在数据集中随机选择两个点,然后用它们的中垂线来切分整个数据集,于是数据集就被分成了蓝绿两个部分。然后再随机两个平面中各选出一个顶点,再用中垂线进行切分,于是,整个平面就被切成了四份。

 

继续切分

用一颗二叉树来表示这个被切分的平面就是:

 

用二叉树来表示切分平面

后续继续采用同样的方式进行切分,直到每一个平面区域最多拥有 K 个点为止。当 K = 10 时,其相应的切分平面和二叉树如下图所示。

 

持续随机切分

K = 10 的时候,每个子平面最多 10 个点

相应的二叉树

下面,新来的一个点(用红色的叉表示),通过对二叉树的查找,我们可以找到所在的子平面,然后里面最多有 K = 10 个点。从二叉树的叶子节点来看,该区域只有 7 个点。

 

红叉表示需要查询的点

搜索路径

在 ANN 领域,最常见的两个问题是:

 

 

    1. 如果我们想要 Top K 的点,但是该区域的点集数量不足 K,该怎幺办?

 

    1. 如果真实的 Top K 中部分点不在这个区域,该怎幺办?

 

 

作者用了两个技巧来解决这个问题:

 

 

    1. 使用优先队列( priority queue ):将多棵树放入优先队列,逐一处理;并且通过阈值设定的方式,如果查询的点与二叉树中某个节点比较相似,那幺就同时走两个分支,而不是只走一个分支;

 

    1. 使用森林( forest of trees ):构建多棵树,采用多个树同时搜索的方式,得到候选集 Top M(M > K),然后对这 M 个候选集计算其相似度或者距离,最终进行排序就可以得到近似 Top K 的结果。

 

 

同时走两个分支的的示意图:

 

随机生成多棵树,构建森林的示意图:

 

随机生成多颗树

Top K 的查询方法:

 

选择候选区域

获得区域中的所有点

区域中 Top K 点排序

Annoy 算法原理:

 

构建索引:建立多颗二叉树,每颗二叉树都是随机切分的;

 

查询方法:

 

1. 将每一颗树的根节点插入优先队列;

 

2. 搜索优先队列中的每一颗二叉树,每一颗二叉树都可以得到最多 Top K 的候选集;

 

3. 删除重复的候选集;

 

4. 计算候选集与查询点的相似度或者距离;

 

5. 返回 Top K 的集合。

 

Annoy 的编程实践

 

Annoy 的安装:

 

pip install annoy

 

Annoy 的 Python 接口函数

 

常用的 Annoy Python 接口函数包括以下内容:

a = AnnoyIndex(f, metric) :f 指的是向量的维度,metric 表示度量公式。在这里,Annoy 支持的度量公式包括:”angular”, “euclidean”, “manhattan”, “hamming”, “dot”;
a.add_item(i, v) :i 是一个非负数,表示 v 是第 i 个向量;
a.build(n_trees, n_jobs=-1) :n_trees 表示树的棵数,n_jobs 表示线程个数,n_jobs=-1 表示使用所有的 CPU 核;
a.save(fn, prefault=False) :表示将索引存储成文件,文件名是 fn;
a.load(fn, prefault=False) :表示将索引从文件 fn 中读取出来;
a.unload() :表示不再加载索引;
a.get_nns_by_item(i, n, search_k=-1, include_distances=False) :返回在索引中的第 i 个向量 Top n 最相似的向量;如果不提供 search_k 值的话,search_k 默认为 n_tree * n,该指标用来平衡精确度和速度;includ_distances=True 表示返回的时候是一个包含两个元素的 tuple,第一个是索引向量的 index,第二个就是相应的距离;
a.get_nns_by_vector(v, n, search_k=-1, include_distances=False) :返回与向量 v Top n 最相似的向量;如果不提供 search_k 值的话,search_k 默认为 n_tree * n,该指标用来平衡精确度和速度;includ_distances=True 表示返回的时候是一个包含两个元素的 tuple,第一个是索引向量的 index,第二个就是相应的距离;
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) :在一个文件 fn 中构建索引,并不在内存中构建索引;
a.set_seed(seed) :用给定的种子初始化随机数生成器,需要在建树,添加向量构建索引之前使用该函数;

影响 annoy 算法效率和精度的重要参数:

n_trees :表示树的棵数,会影响构建索引的时间。值越大表示最终的精度越高,但是会有更多的索引;
search_k :值越大表示搜索耗时越长,搜索的精度越高;如果需要返回 Top n 最相似的向量,则 search_k 的默认值是 n_trees * n;

Annoy 的使用案例

 

from annoy import AnnoyIndex
import random
# f 表示向量的维度
f = 40
# 'angular' 是 annoy 支持的一种度量;
t = AnnoyIndex(f, 'angular')  # Length of item vector that will be indexed
# 插入数据
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    # i 是一个非负数,v 表示向量
    t.add_item(i, v)
# 树的数量
t.build(10) # 10 trees
# 存储索引成为文件
t.save('test.ann')
# 读取存储好的索引文件
u = AnnoyIndex(f, 'angular')
u.load('test.ann') # super fast, will just mmap the file
# 返回与第 0 个向量最相似的 Top 100 向量;
print(u.get_nns_by_item(0, 1000)) # will find the 1000 nearest neighbors
# 返回与该向量最相似的 Top 100 向量;
print(u.get_nns_by_vector([random.gauss(0, 1) for z in range(f)], 1000))
# 返回第 i 个向量与第 j 个向量的距离;
# 第 0 个向量与第 0 个向量的距离
print(u.get_distance(0, 0))
# 第 0 个向量与第 1 个向量的距离
print(u.get_distance(0, 1))
# 返回索引中的向量个数;
print(u.get_n_items())
# 返回索引中的树的棵数;
print(u.get_n_trees())
# 不再加载索引
print(u.unload())

 

基于 hamming 距离的 annoy 使用案例:

 

from annoy import AnnoyIndex
# Mentioned on the annoy-user list
bitstrings = [
 '0000000000011000001110000011111000101110111110000100000100000000',
    '0000000000011000001110000011111000101110111110000100000100000001',
    '0000000000011000001110000011111000101110111110000100000100000010',
    '0010010100011001001000010001100101011110000000110000011110001100',
    '1001011010000110100101101001111010001110100001101000111000001110',
    '0111100101111001011110010010001100010111000111100001101100011111',
    '0011000010011101000011010010111000101110100101111000011101001011',
    '0011000010011100000011010010111000101110100101111000011101001011',
    '1001100000111010001010000010110000111100100101001001010000000111',
    '0000000000111101010100010001000101101001000000011000001101000000',
    '1000101001010001011100010111001100110011001100110011001111001100',
    '1110011001001111100110010001100100001011000011010010111100100111',
]
# 将其转换成二维数组
vectors = [[int(bit) for bit in bitstring] for bitstring in bitstrings]
# 64 维度
f = 64
idx = AnnoyIndex(f, 'hamming')
for i, v in enumerate(vectors):
    idx.add_item(i, v)
# 构建索引
idx.build(10)
idx.save('idx.ann')
idx = AnnoyIndex(f, 'hamming')
idx.load('idx.ann')
js, ds = idx.get_nns_by_item(0, 5, include_distances=True)
# 输出索引和 hamming 距离
print(js, ds)

 

基于欧几里得距离的 annoy 使用案例:

 

from annoy import AnnoyIndex
import random
# f 表示向量的维度
f = 2
# 'euclidean' 是 annoy 支持的一种度量;
t = AnnoyIndex(f, 'euclidean')  # Length of item vector that will be indexed
# 插入数据
t.add_item(0, [0, 0])
t.add_item(1, [1, 0])
t.add_item(2, [1, 1])
t.add_item(3, [0, 1])
# 树的数量
t.build(n_trees=10) # 10 trees
t.save('test2.ann')
u = AnnoyIndex(f, 'euclidean')
u.load('test2.ann') # super fast, will just mmap the file
print(u.get_nns_by_item(1, 3)) # will find the 1000 nearest neighbors
print(u.get_nns_by_vector([0.1, 0], 3))

 

参考资料

 

 

    1. GitHub 的 Annoy 开源代码:https://github.com/spotify/annoy

 

    1. Nearest neighbors and vector models – part 2 – algorithms and data structures:https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html

 

    1. ann-benchmark 的效果测试:https://github.com/erikbern/ann-benchmarks

 

Be First to Comment

发表回复

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