1. 介绍
当面试程序员时,面试官经常会问:"如果在数百万个向量中查找与给定的向量最相似的向量,你会如何操作?" 这是一个非常典型的机器学习面试问题。 这里介绍的两个库:faiss和annoy,是这个问题的两个常用解决方案。
2. Faiss
2.1 Faiss介绍
Faiss是Facebook AI Research团队开发的一种高效的相似向量搜索工具。它利用了多个CPU和GPU,并且通常比其他相似向量搜索工具快2-3倍。 Faiss支持各种输入,但是它最适合以术语“large-scale”或“big data”运行的向量数据。
2.2 Faiss使用方式
使用faiss相似度搜索,您需要定义四个输入参数:
- N是向量的数量
- D是向量的维度
- X是形状为(N, D)的向量组
- q是形状为(M, D)的查询向量
这些参数经常与训练集和测试集相关。 数据集的大小可以通过输入N来确定。 每个向量的维数可以通过输入D来确定。 现在我们有X和q. 如下所示,“X”矩阵包含三个向量以及它们的相应向量ID,q是我们的查询向量
import faiss
import numpy as np
d = 64
nb = 5000
nq = 100
np.random.seed(1234)
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.
#建立索引
index = faiss.IndexFlatL2(d)
# 添加矢量到索引中
index.add(xb)
# 搜索
k = 4
D, I = index.search(xb[:5], k) #搜索5个最近的邻居
print(I)
print(D)
输出
array([[ 0, 514, 7, 4],
[ 1, 9, 367, 52],
[ 2, 169, 3, 293],
[ 3, 67, 23, 263],
[ 4, 0, 514, 7]])
array([[0. , 2.853418, 3.020032, 3.065527],
[0. , 2.789154, 2.815496, 3.058163],
[0. , 2.612029, 2.939454, 2.955015],
[0. , 2.461938, 2.787858, 3.002960],
[0. , 2.853418, 3.020032, 3.065527]], dtype=float32)
搜索的返回值“D”和“I”分别包含k个最近邻居的距离和索引。这意味着,如果k = 4,则搜索结果将为每个查询点返回形状为(m,4)的数组
3. Annoy
3.1 Annoy介绍
Annoy是另一个开源库,用于快速相似向量搜索。要使用Annoy搜索和检索系统,您需要先构建一个索引,该索引存储所有向量,并具有关于这些向量的元数据。 这些元数据可以是代表向量的单个字符串,也可以是可对向量进行映射的数字ID。
3.2 Annoy使用方式
以下是使用Annoy搜索模块进行相似向量搜索的步骤示例:
pip install annoy
f = 40
t = AnnoyIndex(f, 'angular')
for i in range(nb):
v = xb[i]
t.add_item(i, v)
t.build(10)
t.save('test.ann')
u = AnnoyIndex(f, 'angular')
u.load('test.ann')
result = []
for i in I:
r = u.get_nns_by_item(i, 4)
result.append(r)
print(result)
我们使用AnnoyIndex类构建了一个索引。 可以通过调用AnnoyIndex类的add_item()方法将标识符和其相应的向量添加到索引中。 为了构建索引,可以调用索引的build()方法,最后,可以通过调用save()方法将索引保存到磁盘。 为了从磁盘加载索引,可以实例化一个新的AnnoyIndex类并调用其load()方法。
在搜索过程中,我们使用“get_nns_by_item”函数检索与提供的向量编号相对应的最邻近邻居。 它返回一个列表,其中包含与每个搜索向量最相似的向量的标识符。
4. 总结
在大规模向量数据的情况下,Faiss和Annoy都是非常有用的工具。 Faiss更适合大规模数据处理,可以利用GPU加速查询并且其查询速度更快。然而,建立并训练一个FAISS模型并不是非常容易,因为很多参数需要调整。Annoy则更加简单易用,建立索引的时间更短,但是它的查询速度较慢。在用户使用它们之前,最好根据自己的需求仔细选择,并使用性能比较测试技术来比较它们的正确性和精度。
此外,随着信息技术日益发展,有许多其他的数据查询方法可以被使用。一些提及的数据查询方法包括:Ball Tree,KD Tree,Locality Sensitive Hashing,Tree-Saving,以及 Metric Tree等