FAISS学习随笔记_nprobe 聚类中心

 

argument of the metric type：度量标准类型的参数  -------

PQ 即 Product Quantizer（乘积量化）, 相对与普通的Quantizer而言，普通Quantizer 将整个向量通过单次聚类达到量化，而Product Quantizer 则通过对向量分段，每段分别聚类得到多个量化结果（每段一个量化结果），这样的好处是同较小的码本来表达非常大量的码。比如8段，每段256个码，总共256*8 个码本就可以表达256的8次方个码，而普通Quantizer要表达256的8次方个码，码本同样需要这么大。

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。

Level1Quantizer：一级量化器

聚类：https://www.jiqizhixin.com/articles/the-6-clustering-algorithms-data-scientists-need-to-know

聚类分析（英语：Cluster analysis）亦称为群集分析，是对于统计数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离等。
 

Index成员：verbos（冗长等级）、metric_type(该索引用于搜索的指标类型,一般都取L2平方搜索    (squared L2 search))、is_trained(是否训练)、n_total(索引容器的总nb--可能是数据量的数目---数据集的大小)

faiss 的索引种类很多, 并且可以嵌套使用. 不同的索引有不同的实现方式及试用条件,根据数据集的特性和运行机器的性能来选择合适的索引是进行开发的第一步。

Faiss中有两个基础索引类Index、IndexBinary。

nprobe：查找聚类中心的个数（搜索空间），如果 nprobe=nlist，那么就是精确查找。通过nprobe参数控制速度/精度。

———————————***********我是分割线***********———————————

参数分析

IndexIVFPQ:基于PQ来压缩数据向量，但是有一定的精度损耗

quantizer（量化器）：可以选择不同的量化器，不同的量化器有不同的效果。首先把数据集切分成多个，我们定义Voronoi Cells，每个数据向量只能落在一个cell中。查询时只需要查询query向量落在cell中的数据了，降低了距离计算次数。需要另一个索引，称为quantizer，来判断向量属于哪个cell。

d（向量维度）：向量维度的选择。维度增加，那么计算量就会增加。

n_list（划分的子搜索空间、聚类中心的个数）：根据评估指标来选择最佳的聚类数目。

M（向量降维参数）：PQ算法是降维的，降维是根据向量的维度来选择降维参数，所以d必须是M的倍数。（量化器）

如果M过大，那么误差（精度损耗）就会越来越大。

nbits_per_idx（每个子空间存储8字节）：

IndexIVFPQ基于PQ来讲d维的向量降低为d/M维（即分成了n个cell），然后使用暴力搜索（基线）来判断查询向量是属于哪个cell的。

———————————***********我是分割线***********———————————

IndexFlatL2(暴力索引）：最基础的精确查找，基于L2距离（欧氏距离）进行brute-force搜索，要存储所有的向量数据

 

———————————***********我是分割线***********———————————

FAISS常见问题总结：https://zhuanlan.zhihu.com/p/107241260

FAISS:https://zhuanlan.zhihu.com/p/90768014

FAISS:https://www.jianshu.com/p/d35198c5bc23

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

使用GPU索引：https://www.cnblogs.com/houkai/p/9316129.html

FAISS：https://www.cnblogs.com/houkai/p/9316129.html

FAISS/IVFPQ基于GPU实现：https://github.com/facebookresearch/faiss/tree/master/gpu

FAISS各索引C++实现：https://github.com/facebookresearch/faiss/tree/master/tests