Press "Enter" to skip to content

【Python Faiss库】(一)入门

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

文章目录

​​Faiss库​​
​​获取一些数据​​
​​建立索引并向其中添加向量​​
​​搜索​​

Faiss库

 

Faiss是一个用于高效相似性搜索(similarity search)和密集向量聚类的库。它包含的算法可以搜索任意大小的向量集,甚至可以是不适合RAM的向量集。它还包含用于评估和参数调整的支持代码。

 

Faiss是用C++编写的,可以被Python调用。一些最有用的算法是在GPU上实现的。

 

什幺是相似性搜索?

 

给定一组维向量,Faiss将对它构建RAM中的一种数据结构。结构构造完毕后,当给定维的新向量时,它将有效执行操作:

 

其中为欧几里得距离()。

 

对于Faiss,数据结构是一个​​ index​
​​,一个可以用​​add​
​​方法添加向量的的对象。请注意,假设的 ​​​index​
​是固定的。

 

​argmin​
​是对索引的搜索操作。

 

除此之外,Faiss还有以下功能:

不仅可以返回最近的邻居,还可以返回第二、第三、第k个最近的邻居
一次搜索多个向量,而不是一个(批处理)。对于许多索引类型,这比逐个搜索向量要快
以精度换取速度,即实现速度快10倍或占用内存少10倍的方法,代价是有10%概率会给出错误的结果
执行最大内积搜索,而不是最小欧几里德距离搜索。这对其他距离(等)的支持有限。
返回查询点给定半径内的所有元素(范围搜索)
将索引存储在磁盘上,而不是存储在RAM中。

获取一些数据

 

Faiss处理固定​​d​
​​维的向量集合,通常需要10到100秒。这些集合可以存储在矩阵中。我们假设按行存储,即向量数的第个分量存储在矩阵的第行列中。Faiss只使用32位浮点矩阵。

 

我们需要两个矩阵:

 

​xb​
​​表示数据库(​​database​
​​),它包含所有必须索引的向量,我们将在其中搜索。它的尺寸是。

 

​xq​
​​为查询(​​query​
​​) 向量,我们需要找到最近的邻居。它的大小是。如果我们有一个查询向量,​​​nq=1​
​。

 

在下面的例子中,我们将使用在​​d=64​
​维的服从均匀分布的向量。为了差异化,我们在第一维度上添加了小的递增增量,增量取决于向量索引值。

 

import numpy as np
import faiss
d = 64                           # dimension
nb = 100000                      # database size
nq = 10000                       # nb of queries
np.random.seed(1234)             # make reproducible
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.

 

建立索引并向其中添加向量

 

​Faiss​
​​是围绕​​Index​
​​对象构建的。它封装了数据库向量集,并可选地对它们进行预处理,以提高搜索效率。索引有很多种类型,我们将使用最简单的版本,只对它们执行L2距离搜索:​​IndexFlatL2​
​。

 

所有索引(indexes)都需要知道它们所操作的向量的维数,在我们的例子中是​​d​
​​。然后,大多数索引还需要一个训练阶段,以分析向量的分布。对于​​IndexFlatL2​
​,我们可以跳过此操作。

 

建立和训练索引时,可以对索引执行两个操作:​​add​
​​ 和 ​​search​
​。

 

为了向索引中添加元素,我们称之为​​add​
​​ on ​​xb​
​​。我们还可以显示索引的两个状态变量:​​is_trained​
​​(表示是否需要训练的布尔值)和​​ntotal​
​(表示索引向量的数量)。

 

一些索引还可以存储与每个向量对应的整数ID(不是​​IndexFlatL2​
​​)。如果没有提供id,​​add​
​只使用向量序号作为id,即第一个向量得到0,第二个向量得到1,以此类推。

 

index = faiss.IndexFlatL2(d)   # build the index
print(index.is_trained)
index.add(xb)                  # add vectors to the index
print(index.ntotal)

 

输出:

 

True
100000

 

搜索

 

可以对索引执行的基本搜索操作是​​k​
​​近邻搜索,即对于每个查询向量(​​query vector​
​​),在数据库中查找其​​k​
​近邻。

 

该操作的结果可以方便地存储在大小为的整数矩阵中,其中
​I​
​的第i行包含查询向量i的邻居的id,按距离的递增排序。除此矩阵外,搜索操作还返回一个
浮点矩阵
​D​

,其中包含相应的平方距离。

 

为了健全性检查(sanity check),我们可以首先在数据库内搜索它内部的几个向量,以确保其最近的邻居确实是向量本身。

 

k = 4                          # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
print('Size of I:',np.shape(I))
print('Size of D:',np.shape(D))
print(I)
print(D)
D, I = index.search(xq, k)     # actual search
print('Size of I:',np.shape(I))
print('Size of D:',np.shape(D))
print(I[:5])                   # neighbors of the 5 first queries
print(I[-5:])                  # neighbors of the 5 last queries

 

结果:

 

健全性检查的输出应如下所示:

 

Size of I: (5, 4)
Size of D: (5, 4)
[[  0 393 363  78]
 [  1 555 277 364]
 [  2 304 101  13]
 [  3 173  18 182]
 [  4 288 370 531]]
 
[[0.        7.175174  7.2076287 7.251163 ]
 [0.        6.323565  6.684582  6.799944 ]
 [0.        5.7964087 6.3917365 7.2815127]
 [0.        7.277905  7.5279875 7.6628447]
 [0.        6.763804  7.295122  7.368814 ]]

 

即,每个查询的最近邻实际上是向量的索引,对应的距离为0。在一行之内,距离在增加。

 

实际搜索的输出类似于

 

Size of I: (10000, 4)
Size of D: (10000, 4)
# 第一近邻,第2近邻,第3近邻,第4近邻
[[ 381  207  210  477]
 [ 526  911  142   72]
 [ 838  527 1290  425]
 [ 196  184  164  359]
 [ 526  377  120  425]]
 
[[ 9900 10500  9309  9831]
 [11055 10895 10812 11321]
 [11353 11103 10164  9787]
 [10571 10664 10632  9638]
 [ 9628  9554 10036  9582]]

 

由于向向量的第一个分量添加了递增的增量。因此,前几个向量的近邻向量位于数据集的开头,而在10000左右的向量的近邻向量在数据集中的索引也在10000左右。

 

参考:

 

[1]https://faiss.ai/

 

[2] https://github.com/facebookresearch/faiss/wiki/Getting-started

Be First to Comment

发表回复

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