当前位置:   article > 正文

大规模向量检索库Faiss学习总结记录_faiss数据库教程

faiss数据库教程

因为最近要使用到faiss来做检索和查询,所以这里只好抽出点时间来学习下,本文主要是自己最近学习的记录,来源于网络资料查询总结,仅用作个人学习总结记录。

Faiss的全称是Facebook AI Similarity Search,是FaceBook的AI团队针对大规模相似度检索问题开发的一个工具,使用C++编写,有python接口,对10亿量级的索引可以做到毫秒级检索的性能。
简单来说,Faiss的工作,就是把我们自己的候选向量集封装成一个index数据库,它可以加速我们检索相似向量TopK的过程,其中有些索引还支持GPU构建,可谓是强上加强。

faiss官方项目地址在这里,如下所示:

 安装的话有cpu和gpu两个版本,根据自己需要选择即可,我直接使用的是cpu版本的:

pip install faiss-cpu==1.7.3

faiss整体流程图如下所示:

 Faiss检索相似向量TopK的工程基本都能分为三步:
1、得到向量库;
2、用faiss 构建index,并将向量添加到index中;
3、用faiss index 检索。

faiss库的运行是基于索引的,这个索引与传统数据库中的Index不同,它是包含向量集,训练和查询方法等的类。

Index类信息汇总如下表所示:

MethodClass nameindex_factoryMain parametersBytes/vectorExhaustiveComments
Exact Search for L2IndexFlatL2Flatd4*dyesbrute-force
Exact Search for Inner ProductIndexFlatIPFlatd4*dyesalso for cosine (normalize vectors beforehand)
Hierarchical Navigable Small World graph explorationIndexHNSWFlatNSWx,Flatd, M4*d + 8 * Mno
Inverted file with exact post-verificationIndexIVFFlatIVFx,Flatquantizer, d, nlists, metric4*dnoTake another index to assign vectors to inverted lists
Locality-Sensitive Hashing (binary flat index)IndexLSH-d, nbitsnbits/8yesoptimized by using random rotation instead of random projections
Scalar quantizer (SQ) in flat modeIndexScalarQuantizerSQ8ddyes4 bit per component is also implemented, but the impact on accuracy may be inacceptable
Product quantizer (PQ) in flat modeIndexPQPQxd, M, nbitsM (if nbits=8)yes
IVF and scalar quantizerIndexIVFScalarQuantizer

IVFx,SQ4

IVFx,SQ8

quantizer, d, nlists, qtypeSQfp16: 2 * d, SQ8: d or SQ4: d/2nothere are 2 encodings: 4 bit per dimension and 8 bit per dimension
IVFADC (coarse quantizer+PQ on residuals)IndexIVFPQIVFx,PQyquantizer, d, nlists, M, nbitsM+4 or M+8nothe memory cost depends on the data type used to represent ids (int or long), currently supports only nbits <= 8
IVFADC+R (same as IVFADC with re-ranking based on codes)IndexIVFPQRIVFx,PQy+zquantizer, d, nlists, M, nbits, M_refine, nbits_refineM+M_refine+4 or M+M_refine+8no

faiss 三个最基础的 index. 分别是 IndexFlatL2, IndexIVFFlat, IndexIVFPQ
搜索时,可以以查询向量为中心,返回距离在一定范围内的结果,如返回数据库中与查询向量距离小于0.3的结果。不是所有的Index都支持按距离检索,但是下面三种Index都支持,只支持在CPU使用。
一、IndexFlatL2 - 最基础的Index

Flat索引只是将向量简单的编码为固定大小的代码,并将它们存储在 ntotal * code_size的数组中,不对向量数据进行压缩或折叠等操作。在搜索时,对所有的索引向量依次与查询向量比较。

优点:该方法是Faiss所有index中最准确的,召回率最高的方法,没有之一;
缺点:速度慢,占内存大。
使用情况:向量候选集很少,在50万以内,并且内存不紧张。

  1. import numpy as np
  2. import faiss
  3. import time
  4. def demo_IndexFlatL2():
  5. d = 2048 # 2048维的数据
  6. nb = 2 # database size
  7. nq = 1 # nb of queries
  8. np.random.seed(1234)
  9. index = faiss.IndexFlatL2(d)
  10. print(index.is_trained)
  11. # 随机nb个数据插入索引
  12. xb = np.random.random((nb, d)).astype('float32')
  13. xb[:, 0] += np.arange(nb) / 1000.
  14. index.add(xb)
  15. # 再随机nb个数据插入索引
  16. xb1 = np.random.random((nb, d)).astype('float32')
  17. xb1[:, 0] += np.arange(nb) / 1000.
  18. index.add(xb1)
  19. print('index.ntotal:', index.ntotal)
  20. # 随机nq个数据用于查询
  21. xq = np.random.random((nq, d)).astype('float32')
  22. xq[:, 0] += np.arange(nq) / 1000.
  23. k = 4 # 查询距离最近的4个
  24. D, I = index.search(xq, k) # 返回值D是距离 I是索引
  25. print("I: ", I)
  26. # 按照距离查询
  27. dist = 1000 # 定义一个半径/阈值
  28. _, D, I = index.range_search(xb[[2], :], dist) # 用第2个向量查询
  29. print('range_search res:', I)
  30. # 删除元素,dtype=np.int64非常重要
  31. print('remove之前ntotal:', index.ntotal)
  32. index.remove_ids(np.asarray((2,3), dtype=np.int64))
  33. print('remove之后ntotal:', index.ntotal)
  34. if __name__ == '__main__':
  35. demo_IndexFlatL2()

二、更快的搜索 - IndexIVFFlat
为了加快搜索速度,可以将数据集分割成几部分。我们在d维空间中定义Voronoi单元格,并且每个数据库矢量都落入其中一个单元格中。在搜索时,只有查询x所在单元中包含的数据库向量y与少数几个相邻查询向量进行比较。(划分搜索空间)
这种类型的索引需要一个训练的过程,可以在与数据库向量具有相同分布的任何向量集合上执行。
这IndexIVFFlat还需要另一个索引,即量化器(quantizer),它将矢量分配给Voronoi单元。每个单元由一个质心定义,找到一个矢量所在的Voronoi单元包括在质心集中找到该矢量的最近邻居。这是另一个索引的任务,通常是索引IndexFlatL2。
搜索方法有两个参数:
nlist 划分单元的数量
nprobe 执行搜索访问的单元格数(不包括nlist)
nprobe 参数始终是调整结果速度和准确度之间折中的一种方式 。设置 nprobe = nlist 将给出与蛮力搜索(但会更慢)相同的结果。
优点:IVF主要利用倒排的思想,在文档检索场景下的倒排技术是指,一个kw后面挂上很多个包含该词的doc,由于kw数量远远小于doc,因此会大大减少了检索的时间。在向量中如何使用倒排呢?可以拿出每个聚类中心下的向量ID,每个中心ID后面挂上一堆非中心向量,每次查询向量的时候找到最近的几个中心ID,分别搜索这几个中心下的非中心向量。通过减小搜索范围,提升搜索效率。
缺点:速度也还不是很快。
使用情况:相比Flat会大大增加检索的速度,建议百万级别向量可以使用。
参数:IVFx中的x是k-means聚类中心的个数

  1. import numpy as np
  2. import faiss
  3. import time
  4. def demo_IndexIVFFlat():
  5. d = 64 # 向量维度
  6. nb = 200 # 向量集大小
  7. nq = 10000 # 查询次数
  8. np.random.seed(1234) # 随机种子,使结果可复现
  9. nlist = 100
  10. k = 4
  11. quantizer = faiss.IndexFlatL2(d) # the other index
  12. index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
  13. # here we specify METRIC_L2, by default it performs inner-product search
  14. xb = np.random.random((nb, d)).astype('float32')
  15. xb[:, 0] += np.arange(nb) / 1000.
  16. index.train(xb)
  17. index.add(xb) # 添加索引可能会有一点慢
  18. print('index.ntotal:', index.ntotal)
  19. xb1 = np.random.random((nb, d)).astype('float32')
  20. xb1[:, 0] += np.arange(nb) / 1000.
  21. index.train(xb1)
  22. index.add(xb1) # 添加索引可能会有一点慢
  23. print('index.ntotal:', index.ntotal)
  24. xq = np.random.random((nq, d)).astype('float32')
  25. xq[:, 0] += np.arange(nq) / 1000.
  26. D, I = index.search(xq, k) # 搜索
  27. print(I[-5:]) # 最初五次查询的结果
  28. index.nprobe = 10 # 执行搜索访问的单元格数 默认 nprobe 是1 ,可以设置的大一些试试
  29. D, I = index.search(xq, k)
  30. print(I[-5:]) # 最后五次查询的结果
  31. # 按照距离查询
  32. dist = 1000 # 定义一个半径/阈值
  33. _, D, I = index.range_search(xb[[2], :], dist) # 用第2个向量查询
  34. print('range_search res:', I)
  35. # 删除元素,dtype=np.int64非常重要
  36. print('remove之前ntotal:', index.ntotal)
  37. index.remove_ids(np.asarray((2,3), dtype=np.int64))
  38. print('remove之后ntotal:', index.ntotal)
  39. if __name__ == '__main__':
  40. demo_IndexIVFFlat()

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

  1. import numpy as np
  2. d = 64 # 向量维度
  3. nb = 100000 # index向量库的数据量
  4. nq = 10000 # 待检索query的数目
  5. np.random.seed(1234)
  6. xb = np.random.random((nb, d)).astype('float32')
  7. xb[:, 0] += np.arange(nb) / 1000. # index向量库的向量
  8. xq = np.random.random((nq, d)).astype('float32')
  9. xq[:, 0] += np.arange(nq) / 1000. # 待检索的query向量
  10. dim, measure = 64, faiss.METRIC_L2 
  11. param = 'IVF100,Flat'                           # 代表k-means聚类中心为100,   
  12. index = faiss.index_factory(dim, param, measure)
  13. print(index.is_trained)                          # 此时输出为False,因为倒排索引需要训练k-means,
  14. index.train(xb)                                  # 因此需要先训练index,再add向量
  15. index.add(xb)                      

四 、PQx :乘积量化

 乘积量化的核心思想还是聚类。其主要分为两个步骤,Cluster 和 Assign,也即聚类和量化。
乘积量化有个重要的参数m_split ,这个参数控制着向量被切分的段数,如图所示,假设每个向量的维度为128,每个向量被切分为4段,这样就得到了4个小的向量,对每段小向量分别进行聚类,聚类个数为256个,这就完成了Cluster。然后做Assign操作,先每个聚类进行编码,然后分别对每个向量来说,先切分成四段小的向量,对每一段小向量,分别计算其对应的最近的簇心,然后使用这个簇心的ID当做该向量的第一个量化编码,依次类推,每个向量都可以由4个ID进行编码。
每个ID可以由一个字节保存,每个向量只需要用4个字节就可以编码,这样就完成的向量的压缩,节省了大量的内存,压缩比率2000+。
这一步其实就是Faiss训练的部分,目的是为了获取索引Index。在完成向量压缩,获取索引之后,就要考虑如何进行向量查询,下图表示了某个查询向量Query进行查询时的操作流程:

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

  1. import numpy as np
  2. d = 64 # 向量维度
  3. nb = 100000 # index向量库的数据量
  4. nq = 10000 # 待检索query的数目
  5. np.random.seed(1234)
  6. xb = np.random.random((nb, d)).astype('float32')
  7. xb[:, 0] += np.arange(nb) / 1000. # index向量库的向量
  8. xq = np.random.random((nq, d)).astype('float32')
  9. xq[:, 0] += np.arange(nq) / 1000. # 待检索的query向量
  10. dim, measure = 64, faiss.METRIC_L2
  11. param = 'PQ16'
  12. index = faiss.index_factory(dim, param, measure)
  13. print(index.is_trained) # 此时输出为False,因为倒排索引需要训练k-means,
  14. index.train(xb) # 因此需要先训练index,再add向量
  15. index.add(xb)

五、更低的内存占用 - IndexIVFPQ
索引IndexFlatL2和IndexIVFFlat都存储完整的向量。 为了扩展到非常大的数据集,Faiss提供了基于产品量化器的有损压缩来压缩存储的向量的变体。压缩的方法基于乘积量化(Product Quantizer)。
在这种情况下,由于矢量没有精确存储,搜索方法返回的距离也是近似值。

  1. import numpy as np
  2. import faiss
  3. import time
  4. def demo_IndexIVFPQ():
  5. d = 64 # 向量维度
  6. nb = 100000 # 向量集大小
  7. nq = 10000 # 查询次数
  8. np.random.seed(1234) # 随机种子,使结果可复现
  9. xb = np.random.random((nb, d)).astype('float32')
  10. xb[:, 0] += np.arange(nb) / 1000.
  11. xq = np.random.random((nq, d)).astype('float32')
  12. xq[:, 0] += np.arange(nq) / 1000.
  13. nlist = 100
  14. m = 8
  15. k = 4
  16. quantizer = faiss.IndexFlatL2(d) # 内部的索引方式依然不变
  17. index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)
  18. # 每个向量都被编码为8个字节大小
  19. index.train(xb)
  20. index.add(xb)
  21. D, I = index.search(xb[:5], k) # 测试
  22. print(I)
  23. print(D)
  24. index.nprobe = 10 # 与以前的方法相比
  25. D, I = index.search(xq, k) # 检索
  26. print(I[-5:])
  27. # 按照距离查询
  28. dist = 1000 # 定义一个半径/阈值
  29. _, D, I = index.range_search(xb[[2], :], dist) # 用第2个向量查询
  30. print('range_search res:', I)
  31. # 删除元素,dtype=np.int64非常重要
  32. print('remove之前ntotal:', index.ntotal)
  33. index.remove_ids(np.asarray((2,3), dtype=np.int64))
  34. print('remove之后ntotal:', index.ntotal)
  35. if __name__ == '__main__':
  36. demo_IndexIVFPQ()

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

  1. import numpy as np
  2. d = 64 # 向量维度
  3. nb = 100000 # index向量库的数据量
  4. nq = 10000 # 待检索query的数目
  5. np.random.seed(1234)
  6. xb = np.random.random((nb, d)).astype('float32')
  7. xb[:, 0] += np.arange(nb) / 1000. # index向量库的向量
  8. xq = np.random.random((nq, d)).astype('float32')
  9. xq[:, 0] += np.arange(nq) / 1000. # 待检索的query向量
  10. dim, measure = 64, faiss.METRIC_L2
  11. param = 'IVF100,PQ16'
  12. index = faiss.index_factory(dim, param, measure)
  13. print(index.is_trained) # 此时输出为False,因为倒排索引需要训练k-means,
  14. index.train(xb) # 因此需要先训练index,再add向量 index.add(xb)

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

  1. import numpy as np
  2. d = 64 # 向量维度
  3. nb = 100000 # index向量库的数据量
  4. nq = 10000 # 待检索query的数目
  5. np.random.seed(1234)
  6. xb = np.random.random((nb, d)).astype('float32')
  7. xb[:, 0] += np.arange(nb) / 1000. # index向量库的向量
  8. xq = np.random.random((nq, d)).astype('float32')
  9. xq[:, 0] += np.arange(nq) / 1000. # 待检索的query向量
  10. dim, measure = 64, faiss.METRIC_L2
  11. param = 'LSH'
  12. index = faiss.index_factory(dim, param, measure)
  13. print(index.is_trained) # 此时输出为True
  14. index.add(xb)

八、HNSWx (最重要的放在最后说)
优点:该方法为基于图检索的改进方法,检索速度极快,10亿级别秒出检索结果,而且召回率几乎可以媲美Flat,最高能达到惊人的97%。检索的时间复杂度为loglogn,几乎可以无视候选向量的量级了。并且支持分批导入,极其适合线上任务,毫秒级别体验。
缺点:构建索引极慢,占用内存极大(是Faiss中最大的,大于原向量占用的内存大小)
参数:HNSWx中的x为构建图时每个点最多连接多少个节点,x越大,构图越复杂,查询越精确,当然构建index时间也就越慢,x取4~64中的任何一个整数。
使用情况:不在乎内存,并且有充裕的时间来构建index

  1. import numpy as np
  2. d = 64 # 向量维度
  3. nb = 100000 # index向量库的数据量
  4. nq = 10000 # 待检索query的数目
  5. np.random.seed(1234)
  6. xb = np.random.random((nb, d)).astype('float32')
  7. xb[:, 0] += np.arange(nb) / 1000. # index向量库的向量
  8. xq = np.random.random((nq, d)).astype('float32')
  9. xq[:, 0] += np.arange(nq) / 1000. # 待检索的query向量
  10. dim, measure = 64, faiss.METRIC_L2
  11. param = 'HNSW64'
  12. index = faiss.index_factory(dim, param, measure)
  13. print(index.is_trained) # 此时输出为True
  14. index.add(xb)

IndexBinary是二进制索引,其表示的向量集中每个维度只有 0 和 1 两种数值,查询时计算待查向量与DataBase的汉明距离。向量在内存中按字节存储,每个维度占用1bit,总的内存空间为(dimension / 8)bytes,所以这类向量只支持维度为8的整数倍的向量集,否则需要对向量进行扩展或压缩。
九、IndexBinaryFlat
穷举搜索,在查询时会计算索引集中所有向量,该索引针对256维向量进行了特殊优化。

  1. import faiss
  2. # 向量维度
  3. d = 256
  4. # 建立索引的向量,可视为DataBase
  5. db = ...
  6. # 需从Index中查询的目标向量
  7. queries = ...
  8. # 初始化Index
  9. index = faiss.IndexBinaryFlat(d)
  10. # 添加db到index中
  11. index.add(db)
  12. # 每个查询向量要检索的最近邻居数
  13. k = ...;
  14. # 查询索引, D是存放最近K个距离的容器, I是D中每个距离的向量在db中的下标
  15. D, I = index.search(queries, k)

十、IndexBinaryIVF
该索引会对向量进行聚类来加快查询速度。聚类搜索需要先进行训练,相当于无监督学习。训练过程主要是量化器学习对数据进行聚类,划分为nlist个簇。这里采用的聚类方法是按距离划分。IndexBinaryIVF索引查询与IndexBinaryFlat的方式不同,前者是基于聚类的。

  1. import faiss
  2. # 向量维度
  3. d = 256
  4. # 建立索引的向量,可视为DataBase
  5. db = ...
  6. # 训练用的向量集
  7. training = ...
  8. # 需从Index中查询的目标向量
  9. queries = ...
  10. # 初始化量化器
  11. quantizer = faiss.IndexBinaryFlat(d)
  12. # 设置向量集中簇的个数
  13. nlist = ...
  14. # 初始化索引
  15. index = faiss.IndexBinaryIVF(quantizer, d, nlist)
  16. # 设置每次查询的簇的数量
  17. index.nprobe = 4
  18. # 训练
  19. index.train(training)
  20. # 将向量集添加进索引
  21. index.add(db)
  22. # 每个查询向量要检索的最近邻居数
  23. k = ...
  24. # 查询索引, D是存放最近K个距离的容器, I是D中每个距离的向量在db中的下标
  25. D, I = index.search(queries, k)

混合索引表示使用了上述多种索引方法以增强查询性能。

十一、IndexPQ

  1. m = 16 # number of subquantizers
  2. n_bits = 8 # bits allocated per subquantizer
  3. pq = faiss.IndexPQ (d, m, n_bits) # Create the index
  4. pq.train (x_train) # Training
  5. pq.add (x_base) # Populate the index
  6. D, I = pq.search (x_query, k) # Perform a search

十二、IndexIVFPQ

  1. coarse_quantizer = faiss.IndexFlatL2 (d)
  2. index = faiss.IndexIVFPQ (coarse_quantizer, d,
  3. ncentroids, code_size, 8)
  4. index.nprobe = 5

十三、粗略PQ索引
乘积量化器(PQ)也可以作为初始索引,对应于多索引[The inverted multi-index, Babenko & Lempitsky, CVPR'12],对于具有m个段(每个段编码为c个质心)的PQ,反向列表的数量为c ^ m。因此,m = 2是唯一可行的选择。在FAISS中,相应的粗略量化器索引是MultiIndexQuantizer。该索引没有添加向量。因此,必须在IndexIVF上设置特定标志(quantizer_trains_alone)。

  1. nbits_mi = 12 # c
  2. M_mi = 2 # m
  3. coarse_quantizer_mi = faiss.MultiIndexQuantizer(d, M_mi, nbits_mi)
  4. ncentroids_mi = 2 ** (M_mi * nbits_mi)
  5. index = faiss.IndexIVFFlat(coarse_quantizer_mi, d, ncentroids_mi)
  6. index.nprobe = 2048
  7. index.quantizer_trains_alone = True

十四、预过滤PQ索引
比较汉明距离比使用PQ算法快6倍,但是通过对量化质心进行适当的重新排序,PQ码之间的汉明距离将与真实距离相关。通过在汉明距离上应用阈值,可以避免最昂贵的PQ代码比较。

设置阈值的原则:
阈值应在0和每个代码的位数之间(在这种情况下为128 = 16 * 8),并且代码遵循二项式分布;
阈值设置应小于代码位数的1/2。

  1. #
  2. #For an IndexPQ:
  3. #
  4. index = faiss.IndexPQ (d, 16, 8)
  5. # before training
  6. index.do_polysemous_training = true
  7. index.train (...)
  8. # before searching
  9. index.search_type = faiss.IndexPQ.ST_polysemous
  10. index.polysemous_ht = 54 # the Hamming threshold
  11. index.search (...)
  12. #
  13. #For an IndexIVFPQ:
  14. #
  15. index = faiss.IndexIVFPQ (coarse_quantizer, d, 16, 8)
  16. # before training
  17. index. do_polysemous_training = true
  18. index.train (...)
  19. # before searching
  20. index.polysemous_ht = 54 # the Hamming threshold
  21. index.search (...)

对于Index相关的内容整体总结如下所示:

 Faiss提供的索引多种多样,虽然它们都能完成既定的任务,但是对于不同的应用场景,表现的性能差异是非常大的。针对不同的应用场景,如何选择最好的索引,可以遵循下列因素:
【搜索量】
如果搜索量比较小(比如1000 - 10000),那么建立索引的时间在整个搜索过程中的占比会比较大,所以可以直接计算。
【结果精确度】
如果对结果要求绝对的准备,那么选择带有"Flat"关键字的索引。只有IndexFlatL2 或 IndexFlatIP能保证绝对的准确。它们为其他索引的结果提供了基准值。
【内存敏感性】
如果对内存没有要求,选择"HNSWx",其中x(4 - 64)表示每个向量的link数,x值越大,结果越精确,占用内存也越大;
要求不高,选择"... , Flat",其中"..."表示先对数据进行聚类。
要求比较高,选择"PCARx,...,SQ8"
对内存要求非常高,选择"OPQx_y,...,PQx"
【dataset大小】
小于1M, 选择"...,IVFx,..."
1M - 10M之间,选择 "...,IVF65536_HNSW32,..."
10M - 100M:之间, 选择"...,IVF262144_HNSW32,..."
100M - 1B:之间, 选择"...,IVF1048576_HNSW32,..."

Faiss的前后处理主要进行重新映射向量ID,对数据进行转换,并使用更好的索引对搜索结果重新排序等操作。

默认情况下Faiss按顺序将向量添加到索引,并设置ID。一些Index类实现了add_with_ids方法,其中除了向量之外,还可以提供64位向量ID。在搜索时,该类将返回存储的ID,而不是初始向量。映射ID可以使用IndexIDMap方法,该方法封装了另一个索引,并在添加和搜索时转换ID。它维护带有映射的表。

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

由于输入数据量过大等原因,在对数据进行索引前,往往需要进行数据转换,如压缩,降维等。所有的数据预转换方法都继承自VectorTransform类。该类对维度为d_in的输入向量进行转换,输出维度为d_out的输出向量。

数据预转换方法如下表:

【 PCAMatrix : 使用PCA降维】

将向量维度从2048D减到16字节

  1. # the IndexIVFPQ will be in 256D not 2048
  2. coarse_quantizer = faiss.IndexFlatL2 (256)
  3. sub_index = faiss.IndexIVFPQ (coarse_quantizer, 256, ncoarse, 16, 8)
  4. # PCA 2048->256
  5. # also does a random rotation after the reduction (the 4th argument)
  6. pca_matrix = faiss.PCAMatrix (2048, 256, 0, True)
  7. #- the wrapping index
  8. index = faiss.IndexPreTransform (pca_matrix, sub_index)
  9. # will also train the PCA
  10. index.train(...)
  11. # PCA will be applied prior to addition
  12. index.add(...)

【RemapDimensionsTransform:增加维度】
可以通过添加零值的方式给向量增加维度

  1. # input is in dimension d, but we want a multiple of M
  2. d2 = int((d + M - 1) / M) * M
  3. remapper = faiss.RemapDimensionsTransform (d, d2, true)
  4. # the index in d2 dimensions
  5. index_pq = faiss.IndexPQ(d2, M, 8)
  6. # the index that will be used for add and search
  7. index = faiss.IndexPreTransform (remapper, index_pq)

【IndexRefineFlat:重新排列搜索结果】
查询向量时,使用实际距离计算对搜索结果重新排序可能会很有用。以下示例使用IndexPQ搜索索引,然后通过计算实际距离对第一个结果进行排名:

  1. q = faiss.IndexPQ (d, M, nbits_per_index)
  2. rq = faiss.IndexRefineFlat (q)
  3. rq.train (xt)
  4. rq.add (xb)
  5. rq.k_factor = 4
  6. D, I = rq:search (xq, 10)

最后放上在总结学习过程中参考的博文【对所有作者表示感谢】:

https://blog.csdn.net/rangfei/category_10080429.html

Home · facebookresearch/faiss Wiki · GitHub

GitHub - facebookresearch/faiss: A library for efficient similarity search and clustering of dense vectors.

faiss 三种基础索引方式_faiss.indexflatl2_小殊小殊的博客-CSDN博客

Faiss入门及应用经验记录 - 知乎

https://blog.csdn.net/weixin_43791511/article/details/122513786

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/453052
推荐阅读
相关标签
  

闽ICP备14008679号