向量数据库-Faiss详解

接下来介绍几种最核心的index类型（算法）的用法及优缺点，当然faiss支持的index类型非常多，但是以下这些index属于faiss最核心的几种基本index，大部分其他index是在这些核心index思想上的扩展、补充和改进，比如在PQ思想基础上的改进有SQ、OPQ、LOPQ，基于LSH的改进有ALSH等等，使用方法和下面介绍的类似。Faiss的工作，就是把我们自己的候选向量集封装成一个i

HAXIMOF

698人浏览 · 2023-12-12 12:37:14

HAXIMOF · 2023-12-12 12:37:14 发布

Aximof| 编辑

科技博文| 分类

介绍

向量数据库Faiss是Facebook AI研究院开发的一种高效的相似性搜索和聚类的库。它能够快速处理大规模数据，并且支持在高维空间中进行相似性搜索。

Faiss的工作，就是把我们自己的候选向量集封装成一个index数据库，它可以加速我们检索相似向量Top K的过程，一些最有用的算法是在 GPU 上实现的。它主要由 Meta 的基础 AI 研究团队 FAIR 开发。

什么是相似性搜索？

给定一组d维度向量x_i，Faiss从中构建RAM中的数据结构。构造结构后，当给定一个新的d维度向量x时，它会有效地执行以下操作：

$\mathrm{argmin}_i || x - x_i ||$

其中 $∣∣.∣∣$ 是欧几里得距离（L2），寻找与x最相似的向量数据；其中计算 argmin 的过程就是在索引中搜索操作。

以下是Faiss能够完成的：

不仅返回最近邻的向量，还返回第二个最近的、第三个、…、第 k 个最近的邻居；
一次搜索多个向量，而不是一个（批处理）。对于许多索引类型，这比一个接一个地搜索向量要快；
用精度换速度。使用速度快10倍或内存少10倍的方法，在10%的情况下给出不精确的结果
执行最大内积搜索，而不是最小欧几里得搜索。对其他距离（L1、Linf 等）有一定的支持。
返回查询点给定半径内的所有元素（范围搜索）
将索引存储在磁盘上，而不是存储在 RAM 中。
索引二进制向量而不是浮点向量
根据向量 ID 上的谓词忽略索引向量的子集。

Faiss 的工作原理

Faiss 是围绕一个索引类型（算法）构建的，该索引类型存储一组向量，并提供一个函数，通过 L2 和/或内积向量比较在其中进行搜索。某些索引类型是简单的基线，例如精确搜索。大多数可用的索引结构(算法)都对应于以下方面的各种权衡:

搜索时间
搜索质量
每个索引向量使用的内存
训练时间
插入时间
需要外部数据进行无监督训练
可选的 GPU 实现方式提供了（截至 2017 年 3 月）的高维向量的最快精确和近似（压缩域）最近邻搜索实现、最快的Lloyd’s k-means和最快的small k-selection算法。

搭建Faiss环境

pip 安装

conda create -n faiss
conda activate faiss

#pip install faiss-cpu
#GPU版本
#pip install faiss-gpu

conda install -c conda-forge faiss-cpu

Faiss的基本使用

Faiss检索相似向量TopK的工程基本都能分为三步：

得到向量库；
用faiss 构建index，并将向量添加到index中；
用faiss index 检索。
打开 jupyter notebook

#在虚拟环境中安装ipykernel
conda install ipykernel

#继续在该环境中安装nb_conda
conda install -c conda-forge nb_conda

#该环境中启动jupyter notebook
jupyter notebook

导入库

import numpy as np
import faiss

随机数据作为我们的向量数据库

d = 128                            # dimension
nb = 10000                         # database size
np.random.seed(1234)             # make reproducible
xb = np.random.random((nb, d)).astype('float32')

需要创建一个索引。索引是Faiss进行高效搜索的关键。在这个例子中，我们选用暴力检索的方法FlatL2，L2代表构建的index采用的相似度度量方法为L2范数，即欧氏距离

index = faiss.IndexFlatL2(d)   # build the index
print(index.is_trained)

将我们的数据添加到索引中

index.add(xb)                  # add vectors to the index
print(index.ntotal)

检索TopK相似query;向量数据库已经准备好了，我们可以进行搜索了。我们生成了5个查询向量，并且我们希望找到每个查询向量的最近的4个向量

nq = 5                          # number of query vectors
 k = 4                           # we want 4 similar vectors
 Xq = np.random.random((nq, d)).astype('float32')
 D, I = index.search(Xq, k)     # sanity check
 print('Xq is:\n',Xq)
 print('result is')
 print(I)
 print(D)

在这个例子中，I是一个数组，它包含了每个查询向量的最近的4个向量的索引。D是一个数组，它包含了这些向量的距离
Faiss的强大之处在于它可以处理任何可以表示为向量的数据，包括图片和文件。

图片搜索

在进行图片搜索时，首先需要将图片转换为向量。这通常通过深度学习模型，如CNN，来实现。这些模型可以将图片的视觉内容编码为一个向量，这个向量可以捕获图片的重要特征。

本例子中，使用预训练的ResNet模型将图片转换为向量：

from torchvision import models, transforms
from PIL import Image

#Load the pretrained model
model = models.resnet50(pretrained=True)
model = model.eval()

#Define the image transformations
transform = transforms.Compose([
     transforms.Resize(256),
     transforms.CenterCrop(224),
     transforms.ToTensor(),
     transforms.Normalize(mean=[0.485, 0.456, 0.406], std=[0.229, 0.224, 0.225]),
 ])
 
#Load the image
image = Image.open('image.jpg')

#Apply the transformations and get the image vector
image = transform(image).unsqueeze(0)
print(image.shape)
image_vector = model(image).detach().numpy()
print(image_vector.shape)

然后，我们可以将这个向量添加到Faiss的索引中，就像我们在前面的例子中做的那样。当我们需要搜索相似的图片时，我们可以将查询图片也转换为向量，然后使用Faiss进行搜索。
可以看到通过模型向量化之后，数据量从3x244x244变小为1000。

文件搜索

对于文件搜索，我们也需要将文件转换为向量。这通常通过自然语言处理模型，如BERT，来实现。这些模型可以将文本内容编码为一个向量，这个向量可以捕获文本的语义信息。

from transformers import BertModel, BertTokenizer

#Load the pretrained model and tokenizer
model = BertModel.from_pretrained('bert-base-uncased')
tokenizer = BertTokenizer.from_pretrained('bert-base-uncased')
 
#Load the text file
with open('file.txt', 'r') as f:
     text = f.read()
     
#Tokenize the text and get the text vector
inputs = tokenizer(text, return_tensors='pt')
outputs = model(**inputs)
text_vector = outputs.last_hidden_state.mean(dim=1).detach().numpy()

Faiss常用index算法

Faiss之所以能加速，是因为它用的检索方式并非精确检索，而是模糊检索。既然是模糊检索，那么必定有所损失，我们用召回率来表示模糊检索相对于精确检索的损失。

在我们实际的工程中，候选向量的数量级、index所占内存的大小、检索所需时间（是离线检索还是在线检索）、index构建时间、检索的召回率等都是我们选择index时常常需要考虑的地方。

首先，我建议关于Faiss的所有索引的构建，都统一使用faiss.index_factory，基本所有的index都支持这种构建索引方法。

构建index方法和传参方法建议修改为：

dim, measure = 64, faiss.METRIC_L2
param = 'Flat'
index = faiss.index_factory(dim, param, measure)

三个参数中，dim为向量维数；
最重要的是param参数，它是传入index的参数，代表需要构建什么类型的索引(搜索算法)；
measure为度量方法，Faiss度量方法支持的主要方法有L2和内积两种。其他的由IndexFlat, IndexHNSW 和 GpuIndexFlat支持。
截至2023年12月,现在现在faiss官方支持的度量方式有（faiss/faiss

/MetricType.h）：

enum MetricType {
    METRIC_INNER_PRODUCT = 0, ///< maximum inner product search（内积）
    METRIC_L2 = 1,            ///< squared L2 search （欧式距离）
    METRIC_L1,                ///< L1 (aka cityblock)（曼哈顿距离）
    METRIC_Linf,              ///< infinity distance （无穷范数）
    METRIC_Lp,                ///< L_p distance, p is given by a faiss::Index
                              /// metric_arg   （p范数）

    /// some additional metrics defined in scipy.spatial.distance
    METRIC_Canberra = 20,   （兰氏距离/堪培拉距离）
    METRIC_BrayCurtis,   （BC相异度）
    METRIC_JensenShannon, （JS散度）
    METRIC_Jaccard, ///< defined as: sum_i(min(a_i, b_i)) / sum_i(max(a_i, b_i))
                    ///< where a_i, b_i > 0   （杰卡德距离）
};

Faiss构建模块:聚类，PCA，量化

Faiss 基于一些基本的算法构建，这些算法具有非常高效的实现：k-means 聚类、PCA、PQ 编码 / 解码。

聚类

Faiss 提供了一个高效的 k-means 实现。对于给定的二维张量中的一组向量进行聚类的方法如下：

ncentroids = 1024 
niter = 20 
verbose = True 
d = x.shape [1] 
kmeans = faiss.Kmeans (d, ncentroids, niter=niter, verbose=verbose) 
kmeans.train (x)

结果中心点存储在.kmeans.centroids 中。

目标函数的值（在 k-means 情况下为总平方误差）随迭代次数的变化存储在变量中，并且更详细的统计信息存储在.kmeans.objkmeans.iteration_stats 中。

要在 GPU 上运行，在 Kmeans 构造函数中添加选项。这将使用机器上所有可用的GPU.gpu=True .

计算 PCA

将 40D 向量降维到 10D。

# random training data 
mt = np.random.rand(1000, 40).astype('float32')
mat = faiss.PCAMatrix (40, 10)
mat.train(mt)
assert mat.is_trained
tr = mat.apply(mt)
# print this to show that the magnitude of tr's columns is decreasing
print (tr ** 2).sum(0)

量化器

量化器对象继承自，该对象提供三种常用方法（参见 impl/Quantizer.h）：Quantizer

训练：在向量矩阵上训练量化器
compute_codes 和：编码器和解码器。编码器通常是有损的，并返回每个输入向量的代码矩阵。decode uint8.
get_DistanceComputer 是返回对象的方法。DistanceComputer
量化器对象的状态是训练的结果。字段指示量化器生成的每个代码的字节数。Quantizercode_size .

量化器类型

支持的量化器类型有：

ScalarQuantizer：分别在线性范围内量化每个向量分量。

ProductQuantizer：对子向量执行向量量化

AdditiveQuantizer：将向量编码为码书条目的总和，详细信息请参见 Addtive Quantizers。可以以多种方式训练加法量化器，因此有子类ResidualQuantizer ,LocalSearchQuantizer, ProductAdditiveQuantizer.

有趣的是，每个量化器都是前一个量化器的超集。

索引训练

在介绍之前，先介绍一个概念叫索引的训练。索引需要训练的主要原因是为了构建一个数据结构，使得在进行相似性搜索时能够高效地找到最相似的向量。在训练过程中，索引会对输入的数据进行处理和组织，以便在搜索时能够快速定位到相似的向量。

具体来说，训练索引的过程通常包括以下步骤：

数据预处理：对输入的向量进行预处理，例如归一化、降维等操作，以便更好地表示数据。
构建数据结构：根据输入的向量数据，构建适合相似性搜索的数据结构，例如树结构、哈希表等。
优化参数：根据输入的数据特点和搜索需求，对索引的参数进行优化，以提高搜索效率和准确性。

训练索引的过程可能会耗费一定的时间和计算资源，但是通过训练，索引可以更好地适应输入数据的特征，从而提高搜索的效率和准确性。因此，在使用索引进行相似性搜索之前，通常需要先对索引进行训练。

Index类型（算法）

Flat ：暴力检索

优点：该方法是Faiss所有index中最准确的，召回率最高的方法，没有之一；
缺点：速度慢，占内存大。
适用情况：向量候选集很少（在50万以内），并且内存不紧张。
注：虽然都是暴力检索，faiss的暴力检索速度比一般程序猿自己写的暴力检索要快上不少，所以并不代表其无用武之地，建议有暴力检索需求的同学还是用下faiss。

构建方法：

dim, measure = 64, faiss.METRIC_L2
param = 'Flat'
index = faiss.index_factory(dim, param, measure)
index.is_trained                                   # 输出为True
index.add(xb)                                      # 向index中添加向量

IVFx Flat ：倒排暴力检索

优点：IVF主要利用倒排的思想，在文档检索场景下的倒排技术是指，一个key-word后面挂上很多个包含该词的doc，由于key-word数量远远小于doc，因此会大大减少了检索的时间。在向量中如何使用倒排呢？可以拿出每个聚类中心下的向量ID，每个中心ID后面挂上一堆非中心向量，每次查询向量的时候找到最近的几个中心ID，分别搜索这几个中心下的非中心向量。通过减小搜索范围，提升搜索效率。
缺点：速度也还不是很快。
适用情况：相比Flat会大大增加检索的速度，建议百万级别向量可以使用。通常可以采用 4096, 或者 16384 个聚类中心的 IVF_Flat 索引。
参数：IVFx中的x是k-means聚类中心的个数。

构建方法：

dim, measure = 64, faiss.METRIC_L2 
param = 'IVF100,Flat'                           # 代表k-means聚类中心为100,   
index = faiss.index_factory(dim, param, measure)
print(index.is_trained)                          # 此时输出为False，因为倒排索引需要训练k-means，
index.train(xb)                                  # 因此需要先训练index，再add向量
index.add(xb)

PQx ：乘积量化

优点：利用乘积量化的方法，改进了普通检索，将一个向量的维度切成x段，每段分别进行检索，每段向量的检索结果取交集后得出最后的Top-K。因此速度很快，而且占用内存较小，召回率也相对较高。
缺点：召回率相较于暴力检索，下降较多。
适用情况：内存及其稀缺，并且需要较快的检索速度，不那么在意召回率。
参数：PQx中的x为将向量切分的段数，因此，x需要能被向量维度整除，且x越大，切分越细致，时间复杂度越高。

构建方法：

dim, measure = 64, faiss.METRIC_L2 
param =  'PQ16' 
index = faiss.index_factory(dim, param, measure)
print(index.is_trained)                          
index.train(xb)                                 
index.add(xb)

IVFxPQy 倒排乘积量化

优点：工业界大量使用此方法，各项指标都均可以接受，利用乘积量化的方法，改进了IVF的k-means，将一个向量的维度切成x段，每段分别进行k-means再检索。
缺点：集百家之长，自然也集百家之短
适用情况：一般来说，各方面没啥特殊的极端要求的话，最推荐使用该方法！
参数：IVFx，PQy，其中的x和y同上。

构建方法：

dim, measure = 64, faiss.METRIC_L2  
param =  'IVF100,PQ16'
index = faiss.index_factory(dim, param, measure) 
print(index.is_trained)                          # 此时输出为False，因为倒排索引需要训练k-means， 
index.train(xb)                                  # 因此需要先训练index，再add向量 index.a

LSH 局部敏感哈希

原理：哈希对大家再熟悉不过，向量也可以采用哈希来加速查找，我们这里说的哈希指的是局部敏感哈希（Locality Sensitive Hashing，LSH），不同于传统哈希尽量不产生碰撞，局部敏感哈希依赖碰撞来查找近邻。高维空间的两点若距离很近，那么设计一种哈希函数对这两点进行哈希计算后分桶，使得他们哈希分桶值有很大的概率是一样的，若两点之间的距离较远，则他们哈希分桶值相同的概率会很小。
优点：训练非常快，支持分批导入，index占内存很小，检索也比较快。
缺点：召回率非常拉垮。
使用情况：候选向量库非常大，离线检索，内存资源比较稀缺的情况。

构建方法：

dim, measure = 64, faiss.METRIC_L2  
param =  'LSH'
index = faiss.index_factory(dim, param, measure) 
print(index.is_trained)                          # 此时输出为True
index.add(xb)

HNSWx、IndexHNSWFlat

这是一种基于图检索的改进方法，HNSWx中的x为构建图时每个点最多连接多少个节点，x越大，构图越复杂，查询越精确，当然构建index时间也就越慢，x取4~64中的任何一个整数。
优点：不需要训练，基于图检索的改进方法，检索速度极快，10亿级别秒出检索结果，而且召回率几乎可以媲美Flat，能达到惊人的97%。检索的时间复杂度为O(loglogn)，几乎可以无视候选向量的量级了。并且支持分批导入，极其适合线上任务，毫秒级别实时反应时间。
缺点：构建索引极慢，占用内存极大（是Faiss中最大的，大于原向量占用的内存大小）；添加数据不支持指定数据ID，不支持从索引中删除数据。
适用情况：不在乎内存，并且有充裕的时间来构建index。

构建方法：

dim, measure = 64, faiss.METRIC_L2   
param =  'HNSW64' 
index = faiss.index_factory(dim, param, measure)  
print(index.is_trained)                          # 此时输出为True 
index.add(xb)

结论

Faiss 是一个高效的向量数据库，用于相似性搜索和聚类。它能够快速处理大规模数据，并支持高维空间中的相似性搜索。Faiss 的工作原理是将向量库封装成一个 index 数据库，并使用 GPU 上的算法加速相似向量的检索。通过将图片和文件转换为向量，我们可以使用Faiss进行高效的搜索。这种方法不仅可以应用于图片和文件，还可以应用于任何可以表示为向量的数据，如音频，视频等。这使得Faiss成为处理大规模数据和进行相似性搜索的强大工具。