search

vieyahn2017 / iBlog

44 stars 0 forks source link

12.10 faiss是为稠密向量提供高效相似度搜索和聚类的框架。 #339

Closed vieyahn2017 closed 4 months ago

vieyahn2017 commented 4 years ago

faiss是为稠密向量提供高效相似度搜索和聚类的框架。 https://github.com/facebookresearch/faiss

vieyahn2017 commented 4 years ago

手把手教你安装Faiss（Linux） https://www.jianshu.com/p/24b8cb642c83

faiss c++源码编译 https://blog.csdn.net/u014448054/article/details/95616804

vieyahn2017 commented 4 years ago 
yum install gcc
gcc --version
yum install gcc-c++

yum install gcc-gfortran

unzip OpenBLAS-develop.zip
cd OpenBLAS-develop/
make FC=gfortran
make install

ls /opt
ln -s /opt/OpenBLAS/lib/libopenblas.so  /usr/lib/libopenblas.so
ln -s /opt/OpenBLAS/lib/libopenblas.so.0  /usr/lib/libopenblas.so.0

vi /etc/profile
LD_LIBRARY_PATH=/opt/OpenBLAS/lib
export LD_LIBRARY_PATH

source /etc/profile

yum install lapack

cp example_makefiles/makefile.inc.Linux ./makefile.inc

./configure --without-cuda

# 之后进行编译用例测试，若无报错即代表数学库安装成功
make misc/test_blas
./misc/test_blas

make
make install

make demos
./demos/demo_sift1M

运行./misc/test_blas 测试blas时出现下方情况是正常的，不是错误哦


BLAS test

errors=

 0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 0.000 -0.000  0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000 -0.000 -0.000  0.000  0.000  0.000
 0.000  0.000  0.000  0.000  0.000 -0.000  0.000 -0.000 -0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000
 0.000  0.000  0.000  0.000  0.000 -0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000
 0.000  0.000  0.000  0.000 -0.000  0.000 -0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000
 0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000 -0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000  0.000
 0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000  0.000 -0.000
 0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000 -0.000  0.000  0.000  0.000  0.000
 0.000  0.000  0.000 -0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000 -0.000  0.000  0.000  0.000  0.000  0.000
 0.000  0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000  0.000 -0.000  0.000  0.000  0.000  0.000  0.000
Intentional Lapack error (appears only for 64-bit INTEGER):

info=0000064b00000000
Lapack uses 32-bit integers
vieyahn2017 commented 4 years ago

步骤四：测试Faiss，参考INSTALL.md上的测试用例，这里就不赘述了

A bit longer example runs and evaluates Faiss on the SIFT1M dataset. To run it, please download the ANN_SIFT1M dataset fromhttp://corpus-texmex.irisa.fr/ and unzip it to the subdirectory sift1M at the root of the source directory for this repository. Then compile and run the following (after ensuring you have installed faiss):

make demos

./demos/demo_sift1M

This is a demonstration of the high-level auto-tuning API. You can try setting a different index_key to find the indexing structure that gives the best performance.
vieyahn2017 commented 4 years ago

facebook faiss的安装测试 https://blog.csdn.net/sparkexpert/article/details/68922168

vieyahn2017 commented 4 years ago

./demos/demo_sift1M [0.000 s] Loading train set [0.105 s] Preparing index "IVF4096,Flat" d=128 [0.106 s] Training on 100000 vectors WARNING clustering 100000 points to 4096 centroids: please provide at least 159744 training points [59.785 s] Loading database [64.620 s] Indexing database, size 1000000128 [124.308 s] Loading queries [124.347 s] Loading ground truth for 10000 queries [124.406 s] Preparing auto-tune criterion 1-recall at 1 criterion, with k=100 nq=10000 [124.442 s] Preparing auto-tune parameters [124.442 s] Auto-tuning over 1 parameters (12 combinations) 0/12: cno=0 nprobe=1 bounds [perf<=1.000 t>=0.000] perf 0.415 t 1.299 (1 runs) 1/12: cno=11 nprobe=2048 bounds [perf<=1.000 t>=1.299] perf 0.992 t 586.314 (1 runs) 2/12: cno=6 nprobe=64 bounds [perf<=0.992 t>=1.299] perf 0.976 t 24.872 (1 runs) 3/12: cno=5 nprobe=32 bounds [perf<=0.976 t>=1.299] perf 0.947 t 12.977 (1 runs) 4/12: cno=9 nprobe=512 bounds [perf<=0.992 t>=24.872] perf 0.992 t 174.236 (1 runs) 5/12: cno=3 nprobe=8 bounds [perf<=0.947 t>=1.299] perf 0.802 t 4.167 (1 runs) 6/12: cno=7 nprobe=128 bounds [perf<=0.992 t>=24.872] perf 0.989 t 49.152 (1 runs) 7/12: cno=10 nprobe=1024 bounds [perf<=0.992 t>=174.236] skip 8/12: cno=2 nprobe=4 bounds [perf<=0.802 t>=1.299] perf 0.684 t 2.621 (1 runs) 9/12: cno=8 nprobe=256 bounds [perf<=0.992 t>=49.152] perf 0.992 t 86.642 (1 runs) 10/12: cno=1 nprobe=2 bounds [perf<=0.684 t>=1.299] perf 0.551 t 1.681 (1 runs) 11/12: cno=4 nprobe=16 bounds [perf<=0.947 t>=4.167] perf 0.889 t 7.181 (1 runs) [1075.675 s] Found the following operating points: Tested 11 operating points, 11 ones are optimal: cno=-1 key= perf=0.0000 t=0.000 cno=0 key=nprobe=1 perf=0.4147 t=1.299 cno=1 key=nprobe=2 perf=0.5508 t=1.681 cno=2 key=nprobe=4 perf=0.6838 t=2.621 cno=3 key=nprobe=8 perf=0.8016 t=4.167 cno=4 key=nprobe=16 perf=0.8892 t=7.181 cno=5 key=nprobe=32 perf=0.9474 t=12.977 cno=6 key=nprobe=64 perf=0.9763 t=24.872 cno=7 key=nprobe=128 perf=0.9888 t=49.152 cno=8 key=nprobe=256 perf=0.9920 t=86.642 cno=9 key=nprobe=512 perf=0.9921 t=174.236 [1075.678 s] Setting parameter configuration "nprobe=2" on index [1075.679 s] Perform a search on 10000 queries [1077.261 s] Compute recalls R@1 = 0.5508 R@10 = 0.5533 R@100 = 0.5533

vieyahn2017 commented 4 years ago

faiss的一些相关调研

https://www.jianshu.com/p/b9b422b3b119

需求背景 目前有项目会涉及到向量的存储和计算，以前的传统搜索引擎lucene系产品和其他数据库貌似都无法没有比较良好有效的解决方案。对于机器学习领域来说，大部分经过训练后的模型都是以特征向量的方式呈现的，所以特征向量的存储和搜索也就是必要的了。

依赖相关 faiss facebook开源的一个库，C++编写，提供了python接口，专门提供了向量存储搜索等相关服务 anconda python的一种科学计算的环境，facebook会将包推送到anconda，用这个解释器可以大大方便安装faiss，反正我是没手动编译成功 pycharm 不解释 测试标准 维度：128/256 数据量级：100万/500万/1千万 关注点：效率 内存占用

维度 数据量 平均查询耗时(取最优) (ms) 内存占用(GB) 128 100万 0.024 1.552 128 500万 0.047 5.504 128 1千万
256 100万 0.042 2.528 256 500万
256 1千万
以目前我的笔记本的内存条的情况只足够跑出上面这3种情况，但基本可以反映出内存和耗时的增长情况，其中耗时大部分情况下不是问题，内存如果上服务器影响也不大。

其他问题 以下是一些我关心的问题找到的官方回答或者从文档中翻出来的点

工程人员的悲哀就是永远只会想着这个东西能不能用，怎么高并低延不要蹦。。

Q.faiss索引是否支持动态增删 Concurrent search/add or add/add are not supported. There is no locking mechanism in place to protect against this, so the calling code should maintain a lock. 不支持并发搜索/添加或添加/添加。 没有锁定机制来防止这种情况，因此调用代码应保持锁定。

上面的文档也没有很明确的说明是否可以动态增删，只是说会有同步危险，

If punctual removals are needed it is probably more efficient to maintain a blacklist of vectors outside the index code 如果需要准时删除，则在索引代码之外维护向量黑名单可能更有效 HNSW does not require training and does not support removing vectors from the index. HNSW不支持从索引中删除向量 Q.为什么查询单个向量比查询批量向量慢 Matrix-matrix multiplications are often much faster than the corresponding amount of matrix-vector multiplications. 矩阵 - 矩阵乘法通常比相应的矩阵 - 向量乘法量快得多。 Q.是否可以将生成的索引从RAM固化到硬盘中 可以通过以下两个方法来进行存储和读取

tmpindex = 'index/tmp.index' faiss.write_index(index, tmpindex)

index = faiss.read_index(tmpindex) Q.HNSW使用什么距离索引 目前没有找到HNSW索引提供可以更改索引距离类型的API，从官方wiki上介绍如何选择索引类型时找到依据如下 Choosing an index is not obvious, so here are a few essential questions that can help in the choice of an index. They are mainly applicable for L2 distances. 选择索引并不明显，因此这里有一些基本问题可以帮助选择索引。 它们主要适用于L2距离。

Q.HNSW如何让id和矢量数据关联 使用id_map，方式如下

index = faiss.IndexHNSWFlat(d, 32) # build the index index2 = faiss.IndexIDMap(index) index2.add_with_ids(xb, ids) D, I = index2.search(xq, 20) 这样查出来的结果才能和id对的上，知道查回来了哪条结果

vieyahn2017 commented 4 years ago

faiss 相似特征向量搜索

https://blog.csdn.net/imliutao2/article/details/81943765

1，支持两种相似性计算方法：L2距离（即欧式距离）和点乘（归一化的向量点乘即cosine相似度）；

2，按照是否编码压缩数据可以分为两类算法，使用压缩的算法可以在单台机器上处理十亿级别的向量规模；

3，并非线程安全的——不支持并行添加向量或搜索与添加的并行；仅在CPU模式下支持并行搜索；

4，只有继承了IndexIVF 的算法才支持向量的 remove() 操作，但由于是连续存储，remove的时间复杂度是 O(n)，建议另外维护一个列表记录被删除的或尚存的向量；

5，faiss 针对批量搜索做了优化；

6，IndexPQ, IndexIVFFlat, IndexIVFPQ, IndexIVFPQR 需要训练；

7，不支持重新训练，建议新建一个索引；

8，只接受 32-bit 浮点类型的输入数据；

9，使用 index = faiss.index_factory(dim, "PCA32,IVF100,PQ8") 这种形式创建索引更灵活，此处类型参数可解释为：使用PCA降维将原始向量降至32维，使用 IVF 建立索引，子list（即bucket 分桶）个数为 100，使用 Product Quantizer (乘积量化) 将每个向量压缩编码成 8 字节；等价于

num_list = 64
dim = 64
bytes_per_vector = 8
bits_per_sub_vector = 8

quantizer = faiss.IndexFlatL2(dim)
index = faiss.IndexIVFPQ(quantizer, dim, num_list, bytes_per_vector, bits_per_sub_vector)

10，索引类型的选择

如果需要精确的搜索结果，不要降维、不要量化，使用 Flat，同时，使用Flat 意味着数据不会被压缩，将占用同等大小的内存； 如果内存很紧张，可以使用 PCA 降维、PQ 量化编码，来减少内存占用，最终占用的内存大小约等于 <降维后的向量维度> <量化后的每个向量的字节数> <向量个数>； 如果量化编码后的字节数大于64，推荐使用SQx 替换PQx，准确度相同但速度会更快；为了便于量化编码，可以使用 OPQx_y 先对向量做线性变换，y 必须是编码后字节数x的倍数，但最好小于维度dim和4x； 如果总向量个数 N 小于 1百万，推荐使用 IVFx ，x 的选值介于 4sqrt(N) 和 16sqrt(N) 之间，训练数据的大小至少要是x的30倍；如果总向量个数 N 大于 1百万、小于 1千万，推荐使用 IMI2x10，实际内部聚类个数是 2 ^ (2 10)，将需要64 * 2 ^ 10 个向量参与训练；如果总向量个数 N 大于 1千万、小于 1亿，推荐使用 IMI2x12；如果总向量个数 N 大于 1亿、小于 10亿，推荐使用 IMI2x14；IMI方法不支持GPU； IndexIVF 天生支持 add_with_ids 方法，对于不支持 add_with_ids方法的类型，可以使用IndexIDMap 辅助

index = faiss.IndexFlatL2(xb.shape[1]) 
ids = np.arange(xb.shape[0])
index.add_with_ids(xb, ids)  # this will crash, because IndexFlatL2 does not support add_with_ids
index2 = faiss.IndexIDMap(index)
index2.add_with_ids(xb, ids) # works, the vectors are stored in the underlying index

4，常见问题：

暴力搜索比较慢，解决方法：

export OMP_WAIT_POLICY=PASSIVE

参考：

https://github.com/facebookresearch/faiss

https://github.com/facebookresearch/faiss/wiki/Troubleshooting

https://github.com/facebookresearch/faiss/wiki/FAQ

vieyahn2017 commented 4 years ago

Faiss教程：基础

https://www.cnblogs.com/houkai/p/9316136.html

Faiss对一些基础算法提供了非常高效的实现：k-means、PCA、PQ编解码。

聚类 假设2维tensor x：

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

中心点放在kmeans.centroids中，目标函数的值放在kmeans.obj中。返回查询数据最近的中心点：

D, I = kmeans.index.search(x, 1)

返回某个测试数据集中离各个中心点最近的15个点。

index = faiss.IndexFlatL2 (d)
index.add (x)
D, I = index.search (kmeans.centroids, 15)

通过调整索引可以放到GPU上运行。

PCA降维 从40维降低到10维度

# 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_py(mt)
# print this to show that the magnitude of tr's columns is decreasing
print (tr ** 2).sum(0)

ProductQuantizer(PQ)

d = 32  # data dimension
cs = 4  # code size (bytes)

# train set 
nt = 10000
xt = np.random.rand(nt, d).astype('float32')

# dataset to encode (could be same as train)
n = 20000
x = np.random.rand(n, d).astype('float32')

pq = faiss.ProductQuantizer(d, cs, 8)
pq.train(xt)

# encode 
codes = pq.compute_codes(x)

# decode
x2 = pq.decode(codes)

# compute reconstruction error
avg_relative_error = ((x - x2)**2).sum() / (x ** 2).sum()

标量量化器（每一维度量化）

d = 32  # data dimension

# train set 
nt = 10000
xt = np.random.rand(nt, d).astype('float32')

# dataset to encode (could be same as train)
n = 20000
x = np.random.rand(n, d).astype('float32')

# QT_8bit allocates 8 bits per dimension (QT_4bit also works)
sq = faiss.ScalarQuantizer(d, faiss.ScalarQuantizer.QT_8bit)
sq.train(xt)

# encode 
codes = sq.compute_codes(x)

# decode
x2 = sq.decode(codes)

# compute reconstruction error
avg_relative_error = ((x - x2)**2).sum() / (x ** 2).sum()

选择索引的策略 推荐使用index_factory，通过参数创建索引。

Flat 提供数据集的基准结果，不压缩向量，也不支持添加id；如果需要 add_with_ids，使用“IDMap,Flat”参数。 无需训练，支持GPU. Faiss的索引都是放在RAM中的，所以也就要考虑到内存的占用。

HNSWx 足够的内存，小的数据集。每个向量的links数目x范围[4,64]，通过efSearch参数折中速度和精度，每个向量的内存占用为d4+x2*4个字节。 不支持add_with_ids（如需要添加IDMap），无需训练，不支持从索引中移除向量，不支持GPU

xxx,Flat xxx表示提前为数据做了聚类，如IVFFlat，通过nprobe这种速度和精度，支持GPU（聚类方法也支持的情况下）。

PCARx,...,SQ8 存储整改向量占用资源太多，可以PCA降到x维度；SQ每项用一个字节表示。这样每个向量只占用x个字节的存储空间。不支持GPU。

OPQx_y,...,PQx PQx中x是字节数，通常<=64，如果更大采用SQ更为高效。OPQ是对数据做了线性变换更利于数据压缩，y表示：x的倍数、y<=d且y<4*x（推荐）。x表示OPQ中的分割参数，y才是最终切分结果。支持GPU。

从数据集大小的角度（数据量、训练数据大小）：

少于1百万，使用...,IVFx,... 数据集大小为N，x为[4sqrt(N),16sqrt(N)]。使用K-menas进行聚类，我们需要[30x,256x]个向量进行训练（当然越多越好）。支持GPU。

1百万 < N < 1千万，使用...,IMI2x10,... IMI在训练数据集中通过kmeans得到2^10个中心点。但它是对向量的前后两半分别进行的聚类，也就是得到的2^10^2=2^20个中心描述。我们需要64*2^10个训练样本。不支持GPU。

1千万 < N < 1个亿，使用...,IMI2x12,... 同上，只是增加了聚类数。

1亿 < N < 10亿，使用...,IMI2x14,... 同上

vieyahn2017 commented 4 years ago

faiss的一些相关调研 https://www.jianshu.com/p/b9b422b3b119

faiss 相似特征向量搜索 https://blog.csdn.net/imliutao2/article/details/81943765

Faiss教程：基础 https://www.cnblogs.com/houkai/p/9316136.html

vieyahn2017 commented 4 years ago

Faiss流程与原理分析 https://www.cnblogs.com/yhzhou/p/10568728.html

faiss简介及示例 https://blog.csdn.net/kanbuqinghuanyizhang/article/details/80774609

facebook Faiss的基本使用示例(逐步深入） https://blog.csdn.net/sparkexpert/article/details/68922307

vieyahn2017 commented 4 years ago

Faiss流程与原理分析

https://www.cnblogs.com/yhzhou/p/10568728.html

1、Faiss简介 Faiss是Facebook AI团队开源的针对聚类和相似性搜索库，为稠密向量提供高效相似度搜索和聚类，支持十亿级别向量的搜索，是目前最为成熟的近似近邻搜索库。它包含多种搜索任意大小向量集（备注：向量集大小由RAM内存决定）的算法，以及用于算法评估和参数调整的支持代码。Faiss用C++编写，并提供与Numpy完美衔接的Python接口。除此以外，对一些核心算法提供了GPU实现。相关介绍参考《Faiss：Facebook 开源的相似性搜索类库》

2、Faiss安装

3、Faiss原理及示例分析 3.1 Faiss核心算法实现 Faiss对一些基础的算法提供了非常高效的实现

聚类Faiss提供了一个高效的k-means实现 PCA降维算法 PQ(ProductQuantizer)编码/解码

3.2 Faiss功能流程说明 通过Faiss文档介绍可以了解faiss的主要功能就是相似度搜索。如下图所示，以图片搜索为例，所谓相似度搜索，便是在给定的一堆图片中，寻找出我指定的目标最像的K张图片，也简称为KNN（K近邻）问题。

为了解决KNN问题，在工程上需要实现对已有图库的存储，当用户指定检索图片后，需要知道如何从存储的图片库中找到最相似的K张图片。基于此，我们推测Faiss在应用场景中具备添加功能和搜索功能，有了添加相应的修改和删除功能也会接踵而来，从上述分析看，Faiss本质上是一个向量（矢量）数据库。

对于数据库来说，时空优化是两个永恒的主题，即在存储上如何以更少的空间来存储更多的信息，在搜索上如何以更快的速度来搜索出更准确的信息。如何减少搜索所需的时间？在数据库中很最常见的操作便是加各种索引，把各种加速搜索算法的功能或空间换时间的策略都封装成各种各样的索引，以满足各种不同的引用场景。

3.3 组件分析 Faiss中最常用的是索引Index，而后是PCA降维、PQ乘积量化，这里针对Index和PQ进行说明，PCA降维从流程上都可以理解。

3.3.1 索引Index Faiss中有两个基础索引类Index、IndexBinary，下面我们先从类图进行分析。

下面给出Index和IndexBinary的类图如下所示：

Faiss提供了针对不同场景下应用对Index的封装类，这里我们针对Index基类进行说明。

基础索引的说明参考：Faiss indexes涉及方法解释、参数说明以及推荐试用的工厂方法创建时的标识等。

索引的创建提供了工厂方法，可以通过字符串灵活的创建不同的索引。

index = faiss.index_factory(d,"PCA32,IVF100,PQ8 ") 该字符串的含义为：使用PCA算法将向量降维到32维, 划分成100个nprobe (搜索空间), 通过PQ算法将每个向量压缩成8bit。

其他的字符串可以参考上文给出的Faiss indexes链接中给出的标识。

3.3.1.1 索引说明 此部分对索引id进行说明，此部分的理解是基于PQ量化及Faiss创建不同的索引时选择的量化器而来，可能会稍有偏差，不影响对Faiss的使用操作。

默认情况，Faiss会为每个输入的向量记录一个次序id，也可以为向量指定任意我们需要的id。部分索引类（IndexIVFFlat/IndexPQ/IndexIVFPQ等）有add_with_ids方法，可以为每个向量对应一个64-bit的id，搜索的时候返回此id。此段中说明的id从我的角度理解就是索引。（备注：id是long型数据，所有的索引id类型在Index基类中已经定义，参考类图中标注，typedef long idx_t; ///< all indices are this type）

示例：

import numpy as np
import faiss                   # make faiss available

# 构造数据
import time
d = 64                           # dimension
nb = 1000000                      # database size
nq = 1000000                       # 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.

# 为向量集构建IndexFlatL2索引，它是最简单的索引类型，只执行强力L2距离搜索
index = faiss.IndexFlatL2(d)   # build the index
# #此处索引是按照默认方式，即faiss给的次序id为主
# #可以添加我们需要的索引方式，因IndexFlatL2不支持add_with_ids方法，需要借助IndexIDMap进行映射，代码如下
# ids = np.arange(100000, 200000)  #id设定为6位数整数，默认id从0开始，这里我们将其设置从100000开始
# index2 = faiss.IndexIDMap(index)
# index2.add_with_ids(xb, ids)
#
# print(index2.is_trained)
# # index.add(xb)                  # add vectors to the index
# print(index2.ntotal)
# k = 4   # we want to see 4 nearest neighbors
# D, I = index2.search(xb[:5], k) # sanity check
# print(I)     # 向量索引位置
# print(D)     # 相似度矩阵

print(index.is_trained)
index.add(xb)                  # add vectors to the index
print(index.ntotal)
k = 4   # we want to see 4 nearest neighbors
# D, I = index.search(xb[:5], k) # sanity check
# # print(xb[:5])
# print(I)     # 向量索引位置
# print(D)     # 相似度矩阵

D, I = index.search(xq, 10)     # actual search
# xq is the query data
# k is the num of neigbors you want to search
# D is the distance matrix between xq and k neigbors
# I is the index matrix of k neigbors
print(I[:5])                   # neighbors of the 5 first queries
print(I[-5:]) # neighbors of the 5 last queries

#从index中恢复数据，indexFlatL2索引就是将向量进行排序
# print(xb[381])
# print(index.reconstruct(381))

3.3.1.2 索引选择 此部分没做实践验证，对Faiss给的部分说明进行翻译过来作为后续我们使用的一个参考。

如果关心返回精度，可以使用IndexFlatL2，该索引能确保返回精确结果。一般将其作为baseline与其他索引方式对比，以便在精度和时间开销之间做权衡。不支持add_with_ids，如果需要，可以用“IDMap”给予任意定义id。

如果关注内存开销，可以使用“..., Flat“的索引，"..."是聚类操作，聚类之后将每个向量映射到相应的bucket。该索引类型并不会保存压缩之后的数据，而是保存原始数据，所以内存开销与原始数据一致。通过nprobe参数控制速度/精度。

对内存开销比较关心的话，可以在聚类的基础上使用PQ成绩量化进行处理。

3.3.1.3 检索数据恢复 Faiss检索返回的是数据的索引及数据的计算距离，在检索获得的索引后需要根据索引将原始数据取出。

Faiss提供了两种方式，一种是一条一条的进行恢复，一种是批量恢复。

给定id，可以使用reconstruct进行单条取出数据；可以使用reconstruct_n方法从index中回批量复出原始向量（备注：该方法从给的示例看是恢复连续的数据（0，10），如果索引是离散的话恢复数据暂时还没做实践）。

上述方法支持IndexFlat, IndexIVFFlat (需要与make_direct_map结合), IndexIVFPQ(需要与make_direct_map结合)等几类索引类型。

3.3.2 PCA降维

具体的算法流程没有进行深入的了解，可以参考看：《PCA 降维算法详解 以及代码示例》，待后续算法学习中在进行深入了解。

基于3.2节中对Faiss流程的说明，简要说下对Faiss中PCA的理解。

PCA通过数据压缩减少内存或者硬盘的使用以及数据降维加快机器学习的速度。从数据存储的角度，图片处理中通过PCA可以将图片从高维空间（p维）转换到低维空间（q维, 其中p > q ），其具体操作便是是将高维空间中的图片向量（np）乘以一个转换矩阵（pq），得到一个低维空间中的向量（n*q）。

为了使得在整个降维的过程中信息丢失最少，我们需要对待转换图片进行分析计算得到相应的转换矩阵（p*q）。也就是说这个降维中乘以的转换矩阵是与待转换图片息息相关的。回到我们的Faiss中来，假设我期望使用PCA预处理来减少Index中的存储空间，那在整个处理流程中，除了输入搜索图库外，我必须多输入一个转换矩阵，但是这个转换矩阵是与图库息息相关的，是可以由图库数据计算出来的。如果把这个转换矩阵看成一个参数的话，我们可以发现，在Faiss的一些预处理中，我们会引入一些参数，这些参数又无法一开始由人工来指定，只能通过喂样本来训练出来，所以Index中需要有这样的一个train() 函数来为这种参数的训练提供输入训练样本的接口。

3.3.3 Product quantization(乘积量化PQ) Faiss中使用的乘积量化是Faiss的作者在2011年发表的论文，参考：《Product Quantization for Nearest Neighbor Search》

PQ算法可以理解为首先把原始的向量空间分解为m个低维向量空间的笛卡尔积，并对分解得到的低维向量空间分别做量化。即是把原始D维向量（比如D=128）分成m组（比如m=4），每组就是D∗=D/m维的子向量（比如D∗=D/m=128/4=32），各自用kmeans算法学习到一个码本，然后这些码本的笛卡尔积就是原始D维向量对应的码本。用qj表示第j组子向量，用Cj表示其对应学习到的码本，那么原始D维向量对应的码本就是C=C1×C2×…×Cm。用k∗表示子向量的聚类中心点数或者说码本大小，那么原始D维向量对应的聚类中心点数或者说码本大小就是k=(k∗)m。