Faiss

1.Faiss是什么

  Faiss是Facebook Ai Research开发的一款稠密向量检索工具。引用Faiss Wiki上面的一段简介

Faiss is a library for efficient similarity search and clustering of dense vectors.
It contains algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM.
It also contains supporting code for evaluation and parameter tuning.
Faiss is written in C++ with complete wrappers for Python (versions 2 and 3).
Some of the most useful algorithms are implemented on the GPU.
It is developed by Facebook AI Research.

上面的简介包含了如下信息：

1. Faiss是针对稠密向量进行相似性搜索和聚类的一个高效类库。
2. 它包含可搜索任意大小的向量集的算法，这些向量集的大小甚至都不适合RAM。
3. 它还包含用于评估和参数调整的支持代码。
4. Faiss用C ++编写，并且有python2与python3的封装代码。
5. 一些最有用的算法在GPU上有实现。
6. Faiss是由Facebook AI Research开发的。

简单来说，Faiss的工作，就是把我们自己的候选向量集封装成一个index数据库，它可以加速我们检索相似向量TopK的过程，其中有些索引还支持GPU构建，可谓是强上加强。

2.Faiss的使用简介

整体来说，Faiss的使用方式可以分为三个步骤：

1. 构建训练数据以矩阵的形式表示，比如现在经常使用的embedding，embedding出来的向量就是矩阵的一行。
2. 为数据集选择合适的index，index是整个faiss的核心部分，将第一步得到的训练数据add到index当中。
3. search，或者说query，搜索到最终结果。

3.Faiss的原理与核心算法

  Faiss的主要功能是对向量进行相似搜索。具体就是给定一个向量，在所有已知的向量库中找出与其相似度最高的一些向量，本质是一个KNN(K近邻)问题，比如google的以图找图功能。 Faiss中最重要的是索引Index。 Faiss 创建索引对向量预处理，提高查询效率 。Faiss中的稠密向量各种索引都是基于 Index 实现的，主要的索引方法包括： IndexFlatL2、IndexFlatIP、IndexHNSWFlat、IndexIVFFlat、IndexLSH、IndexScalarQuantizer、IndexPQ、IndexIVFScalarQuantizer、IndexIVFPQ、IndexIVFPQR等 。

3.1 IndexFlatL2

   这种索引的方式是计算L2距离，为一种暴力的(brute-force))精确搜索的方式，计算方式自然就是计算各向量的欧式距离(L2距离)。

import numpy as np
import faiss                   # make faiss available# 准备数据
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.
"""
训练集 xb：[100000,64]  查询数据集 xq：[10000,64]
"""
# 1.创建索引
index = faiss.IndexFlatL2(d)   # build the index
print(index.is_trained)        # 表示索引是否需要训练的布尔值
# True
#2.添加训练集 add方法一般添加训练时的样本；
index.add(xb)                  # add vectors to the index
print(index.ntotal)            # 索引中向量的数量。
# 100000# 3.寻找相似相似向量
k = 4                          # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
# D：numpy array对象，表示与相似向量的距离(distance)，维度
# I：numpy array对象，表示相似用户的ID
print(I)
"""
[[  0 393 363  78][  1 555 277 364][  2 304 101  13][  3 173  18 182][  4 288 370 531]]
"""
print(D)
"""
[[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 ]]
"""D, I = index.search(xq, k)     # actual search
print(I[:5])                   # neighbors of the 5 first queries
print(I[-5:])                  # neighbors of the 5 last queries
"""
[[ 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]]
"""

• 方式：全量搜索
• 流程：
  • 创建索引
  • 添加训练集 (add方法)
  • 寻找相似向量
• 存在问题：速度太慢

3.2 IndexIVFFlat

• 介绍：IndexIVFFlat 是一种 加速索引方法，其所用的方法为倒排法；
• 方式：
• 先聚类再搜索，可以加快检索速度，先将xb中的数据进行聚类（聚类的数目是超参）
  • nlist: 聚类的数目；
  • nprobe: 在多少个聚类中进行搜索，默认为1, nprobe越大，结果越精确，但是速度越慢
• 流程：
  • 使用K-means建立聚类中心；
  • 然后通过查询最近的聚类中心；
  • 最后比较聚类中的所有向量得到相似的向量

  IndexIVFFlat 在搜索的时候，引入了nlist(cell的数量)与nprob(执行搜索的cell树)参数。通过调整这些参数可以在速度与精度之间平衡。

import numpy as np
import faiss# 准备数据
d = 64  # 向量维度
nb = 100000  # 向量集大小
nq = 10000  # 查询次数
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.# 1.定义索引 和 聚类簇数
#  #聚类中心的个数
nlist = 100
# k：查找最相似的k个向量
k = 4
# 注：创建IndexIVFFlat时需要指定一个其他的索引作为量化器(quantizer)来计算距离或相似度。
quantizer = faiss.IndexFlatL2(d)  # the other index
# faiss.METRIC_L2: faiss定义了两种衡量相似度的方法(metrics)，分别为faiss.METRIC_L2、faiss.METRIC_INNER_PRODUCT。一个是欧式距离，一个是向量内积index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
# here we specify METRIC_L2, by default it performs inner-product search# 2.添加训练集
assert not index.is_trained
index.train(xb)
assert index.is_trained
index.add(xb)  # 添加索引可能会有一点慢# 3.寻找相似向量
D, I = index.search(xq, k)  # 搜索
print(I[-5:])  # 最初五次查询的结果
# index.nprobe：查找聚类中心的个数，默认为1个。
index.nprobe = 10  
D, I = index.search(xq, k)
print(I[-5:])  # 最后五次查询的结果
"""
[[ 9900  9309  9810 10048][11055 10895 10812 11321][11353 10164  9787 10719][10571 10664 10632 10203][ 9628  9554  9582 10304]]
[[ 9900 10500  9309  9831][11055 10895 10812 11321][11353 11103 10164  9787][10571 10664 10632  9638][ 9628  9554 10036  9582]]
"""

由上面的实验结果可以看出，结果并不是完全一致的，增大nprobe可以得到与brute-force更为接近的结果，nprobe就是速度与精度的调节器。

3.3 IndexIVFPQ

• 动机：索引 IndexFlatL2 和 IndexIVFFlat 都会全量存储所有的向量在内存中，如果数据量是海量级别的时候，怎么办呢？
• 介绍：IndexIVFPQ 基于Product Quantizer(乘积量化)的压缩算法编码向量大小到指定的字节数的索引算法，存储的向量时压缩过的，查询的距离也是近似的。关于乘积量化的算法可自行搜索。
• 方式：基于乘积量化（product quantizers）对存储向量进行压缩，节省存储空间
  • m：乘积量化中，将原来的向量维度平均分成多少份，d必须为m的整数倍
  • bits: 每个子向量用多少个bits表示

import numpy as np
import faiss
d = 64  # 向量维度
nb = 100000  # 向量集大小
nq = 10000  # 查询次数
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.# 1.定义索引 和 聚类簇数
nlist = 100
m = 8
k = 4
quantizer = faiss.IndexFlatL2(d)  # 内部的索引方式依然不变
# 之前我们定义的维度为d = 64，向量的数据类型为float32。这里压缩成了8个字节。所以压缩比率为 (64*32/8) / 8 = 32
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)# 2.添加训练集
index.train(xb)
index.add(xb)# 3.寻找相似向量
D, I = index.search(xb[:5], k)  # 测试
print(I)
print(D)
index.nprobe = 10  # 与以前的方法相比
D, I = index.search(xq, k)  # 检索
print(I[-5:])
"""
[[   0   78  424  608][   1  555 1063 1150][   2  179  304  134][   3  773  265  527][   4  288  270  531]]
[[1.5790609 6.278362  6.401214  6.538094 ][1.2966543 5.7154517 5.837444  6.361595 ][1.7337201 6.209969  6.2725325 6.318082 ][1.8157879 6.5942464 6.732297  6.857512 ][1.6160889 5.9198503 6.308422  6.363411 ]]
[[10437  8746 10500  9432][10240 11373 10913 10494][11291 10719 10424 10847][10122 10005 11578 10125][ 9229  9878 10304 10249]]
"""

IndexIVFPQ 能正确找到距离最小的向量(他本身)，但是距离不为0，这是因为向量数据存储时候有压缩，会损失一部分精度。

4.Faiss实现向量NN

  Embedding的近邻搜索是当前图推荐系统非常重要的一种召回方式，通过item2vec、矩阵分解、双塔DNN等方式都能够产出训练好的user embedding、item embedding，对于embedding的使用非常的灵活：

• 输入user embedding，近邻搜索item embedding，可以给user推荐感兴趣的items
• 输入user embedding，近邻搜搜user embedding，可以给user推荐感兴趣的user
• 输入item embedding，近邻搜索item embedding，可以给item推荐相关的items

一旦user embedding、item embedding数据量达到一定的程度，对他们的近邻搜索将会变得非常慢，如果离线阶段提前搜索好在高速缓存比如redis存储好结果当然没问题，但是这种方式很不实时，如果能在线阶段上线几十毫秒的搜索当然效果最好。

Faiss的使用基本流程：

1. 读取训练好的Embedding数据
2. 构建faiss索引，将待搜索的Embedding添加进去
3. 取得目标Embedding，实现搜索得到ID列表
4. 根据ID获取电影标题，返回结果

1.准备数据

import pandas as pd
import numpy as np
df = pd.read_csv("./datas/movielens_sparkals_item_embedding.csv")
df.head()

# 构建ids
ids = df["id"].values.astype(np.int64)
print(type(ids), ids.shape) # (numpy.ndarray, (3706,))
print(ids.dtype) # dtype('int64')
ids_size = ids.shape[0]
print(ids_size) #3706# 构建datas
import json
import numpy as npdatas = []
for x in df["features"]:datas.append(json.loads(x))
datas = np.array(datas).astype(np.float32)
print(datas.dtype) # dtype('float32')
print(datas.shape) #(3706, 10)
print(datas[0])
"""
array([ 0.2586649 , 0.35605943, 0.15589039, -0.7067125 , -0.07414215,-0.62500805, -0.0573845 , 0.4533663 , 0.26074877, -0.60799956],dtype=float32)
"""
# 维度
dimension = datas.shape[1]
print(dimension) # 10

2.建立索引

import faiss
index = faiss.IndexFlatL2(dimension)
index2 = faiss.IndexIDMap(index)
print(ids.dtype) # dtype('int64')
index2.add_with_ids(datas, ids)
print(index.ntotal) #3706

3.搜索近邻ID列表

df_user = pd.read_csv("./datas/movielens_sparkals_user_embedding.csv")
df_user.head() # id features

user_embedding = np.array(json.loads(df_user[df_user["id"] == 10]["features"].iloc[0]))
user_embedding = np.expand_dims(user_embedding, axis=0).astype(np.float32)
print(user_embedding)
"""
array([[ 0.59742886, 0.17486966, 0.04345559, -1.3193961 , 0.5313592 ,-0.6052168 , -0.19088413, 1.5307966 , 0.09310367, -2.7573566 ]],dtype=float32)
"""
print(user_embedding.shape)#(1, 10)
print(user_embedding.dtype) #dtype('float32')
topk = 30
D, I = index.search(user_embedding, topk) # actual search
print(I.shape) #(1, 30)
print(I)
"""
array([[3380, 2900, 1953, 121, 3285, 999, 617, 747, 2351, 601, 2347,42, 2383, 538, 1774, 980, 2165, 3049, 2664, 367, 3289, 2866,2452, 547, 1072, 2055, 3660, 3343, 3390, 3590]])
"""

4. 根据电影ID取出电影信息

target_ids = pd.Series(I[0], name="MovieID")
print(target_ids.head())
"""
0 3380
1 2900
2 1953
3 121
4 3285
Name: MovieID, dtype: int64
"""
df_movie = pd.read_csv("./datas/ml-1m/movies.dat",sep="::", header=None, engine="python",names = "MovieID::Title::Genres".split("::"))
print(df_movie.head())

df_result = pd.merge(target_ids, df_movie)
df_result.head()

5.总结

• Faiss的工作，就是把我们自己的候选向量集封装成一个index数据库，它可以加速我们检索相似向量TopK的过程，其中有些索引还支持GPU构建，可谓是强上加强。
• Faiss的使用流程：构建索引，训练数据，寻找相似搜索
• Faiss中最重要的是索引Index。 Faiss 创建索引对向量预处理，提高查询效率 。

本文仅仅作为个人学习记录，不作为商业用途，谢谢理解。

参考：https://www.jb51.net/article/192362.htm