向量索引算法综述：四种度量方式与主流索引结构

系统梳理向量检索：欧式距离、余弦、内积与海明距离四种度量方式的适用场景，以及暴力计算、基于树、基于哈希、基于倒排与基于图等索引结构在减少候选集与降低单向量计算复杂度上的取舍。

向量检索

向量检索是一种基于向量空间模型的信息检索技术，它通过将数据（如文本、图像、音频等）转换为高维向量，然后计算向量之间的相似度来找到与查询最相似的数据。

向量度量

常见的向量度量有四种：欧式距离、余弦、内积、海明距离

• 欧式距离：常用于图片检索。
• 余弦相似度：常用于人脸识别。
• 内积：多用于推荐系统。
• 海明距离：适用于向量较小的大规模视频检索场景。
  向量检索与传统检索思维框架本质上没区别，其重点在于向量索引结构。主要包含两方面：

1. 减少候选向量集，传统文本检索用倒排索引过滤无关文档，向量检索则建立索引结构过滤不相关向量；
2. 降低单个向量计算复杂度，传统文本检索用漏斗模型，而向量检索对高维向量进行量化、近似计算，最后在小数据集上排序原始向量。

   向量索引方法

向量索引是一个研究得比较多的问题，学术上对应的专有名词叫Approximate Nearest Neighbor Search (ANNS)，即近似最近邻搜索。

向量索引的定义：向量索引是指通过某种数学量化模型，对向量构建一种时间和空间都比较高效的数据索引结构，使得我们能够实时地获取跟查询向量尽可能最相近的K个向量。从定义可以看到，要设计一种高效的向量索引模型，应该满足3个基本条件，即：

• 实时查询，支持海量（百亿、千亿级别）规模库量级的实时查询；
• 存储高效，要求构建的向量索引模型数据压缩比高，达到大幅缩减内存使占用的目的；
• 召回精度好，top@K有比较好的召回率，跟暴力搜索（brute-force search）的结果相比；

  类型	代表方法	原理与特点
  暴力计算	Brute-force	直接全量计算，保证100%召回但复杂度高，适用于人脸识别等严苛场景
  树	KDTree, BallTree, VPTree	按空间划分（超平面/球面/距离中值），依赖三角形不等式剪枝，回溯导致性能较低 allen。
  哈希	LSH（局部敏感哈希）	依赖哈希碰撞：相近向量哈希值相同概率高，需针对不同度量设计哈希函数（内积无直接LSH）allen。
  倒排	聚类倒排、BOW	聚类生成中心点，向量归属最近中心点建立倒排；BOW处理局部特征 allen。
  图	HNSW, NSG, KGraph	核心思想：邻居的邻居也可能是邻居。HNSW借鉴跳表分层，上层为下层缩影，通过图遍历缩小搜索范围 allen。

暴力计算

暴力计算具有简单但复杂度高的特点。在计算召回时，其结果是基准数据。人脸识别场景常要求 100% 召回率，此时通常直接采用暴力计算。

基于树的向量索引方法

基于树的方法有很多种，比较典型的有KDTree、BallTree、VPTree，类比传统的二叉树，树结构无非是在建树的时候是决定往左还是往右扩展，不同的向量树索引在于按照什么标准去决策，

• KDTree会选取向量中某个方差最大的维度取中值作为判定标准，也就是以超平面去划分空间；
• BallTree则以球面去划分空间；
• VPTree会先选取一个制高点，然后计算每个点和制高点的距离，取距离中值作为判定标准；

基于哈希的向量索引方法

https://ansvver.github.io/lsh_minhash.html

哈希，顾名思义，就是将连续的实值散列化为0、1的离散值。局部敏感哈希（LSH）不同于传统哈希，它借助碰撞查找近邻。当哈希函数满足：若两点距离小于等于 d1，哈希值相同概率至少 p1；若两点距离大于等于 d2，哈希值相同概率至多 p2，则称其为（d1,d2,p1,p2）- sensitive。简言之，高维空间中近邻点哈希值大概率相同，远距离点则概率小，且不同距离度量对应不同哈希函数，非所有距离度量都能实现 LSH。

基于倒排的向量索引方法

传统倒排索引按文档是否包含词建立索引结构。而向量建立倒排索引是通过聚类，将向量空间分为 K 个区域，各区域以中心点代替，向量归入最近中心点对应的倒排，从而形成索引结构。

BOW 是一种基于倒排的索引，其原理是：对图像提取几百个局部特征后聚类形成中心点，建立索引时将图片局部特征归类到最近中心点建立倒排，检索时依命中的次数过滤结果。

基于图的的向量索引方法

基于图的方法是向量检索研究热点，与传统基于空间划分的索引结构不同，它通过 “邻居的邻居也可能是邻居” 的朴素思想，将最近邻查找转化为图遍历，利用连通性针对性考察部分向量，降低考察范围。近年来出现 KGraph、NSG、HNSW、NGT 等图索引方法，区别主要在构建过程，而检索步骤基本一致：选入口点、遍历图、收敛。评判图索引质量的特性有三个：邻居点接近 K 近邻、邻居点数量少（出度低）、图连通性好（入度高）。

Hierarchical Navigable Small World Graphs (HNSW) 是Yury A. Malkov提出的一种基于图索引的方法，它是Yury A. Malkov在他本人之前工作NSW上一种改进，通过采用层状结构，将边按特征半径进行分层，使每个顶点在所有层中平均度数变为常数，从而将NSW的计算复杂度由多重对数(Polylogarithmic)复杂度降到了对数(logarithmic)复杂度。HNSW的主要贡献如下：

• 图输入节点明确的选择
• 使用不同尺度划分链接
• 使用启发式方式来选择最近邻
  网络图以连续插入的方式构建。对于每一个要插入的元素，采用指数衰变概率分布函数来随机选取整数最大层。

• 图构建元素插入过程（Algorithm 1）：从顶层开始贪心遍历graph，以便在某层A中找到最近邻。当在A层找到局部最小值之后，再将A层中找到的最近邻作为输入点（entry point），继续在下一层中寻找最近邻，重复该过程；
• 层内最近邻查找（Algorithm 2）：贪心搜索的改进版本；
• 在搜索阶段，维护一个动态列表，用于保持ef个找到的最近邻元素
  以逐步递减的特性半径对其进行路由（第一层地球->第二层亚洲—>第三层中国->第四层北京->海淀区），到了第0层后，再在局部区域做更精细的搜索。

import faiss
import numpy as np


num_vectors = 100000
dim = 96

# 创建100,000个向量，每个向量的维度是96
vectors = np.random.rand(num_vectors, dim)

M = 16
efcons = 200
# 初始化HNSW索引签名
index = faiss.IndexHNSWFlat(dim, M, faiss.METRIC_L2)
index.hnsw.efConstruction = efcons
# 构建索引
index.add(vectors)

# 生成1,000条等维数查询向量
queries = np.random.rand(1000, dim)
k = 10
# 使用HNSW索引查询
D, I = index.search(queries, k)
# D的规模为1,000 * 10，代表各query和10NN之间的距离；I的规模与D相同，表示最近邻的ID
print(D)

基于量化的向量索引方法

矢量量化方法，即Vector Quantization，其具体定义为：将一个向量空间中的点用其中的一个有限子集来进行编码的过程。高维向量经索引结构裁剪后，单个计算量仍大，量化技术可将其大值空间量化为小值范围来减少计算量。常用的量化一般包括PQ（及其优化OPQ、LOPQ）和二值两种。

乘积量化

乘积量化(Product Quantization，PQ)是Herve Jegou在2011年提出的一种非常经典实用的矢量量化索引方法，在工业界向量索引中已得到广泛的引用，并作为主要的向量索引方法，在Faiss有非常高效的实现。乘积量化的核心思想是分段（划分子空间）和聚类，或者说具体应用到ANN近似最近邻搜索上，KMeans是PQ乘积量化子空间数目为1的特例。PQ乘积量化生成码本和量化的过程可以用如下图示来说明：

在训练阶段，针对N个训练样本，假设样本维度为128维，我们将其切分为4个子空间，则每一个子空间的维度为32维，然后我们在每一个子空间中，对子向量采用K-Means对其进行聚类(图中示意聚成256类)，这样每一个子空间都能得到一个码本。这样训练样本的每个子段，都可以用子空间的聚类中心来近似，对应的编码即为类中心的ID。

在查询阶段，PQ同样在计算查询样本与dataset中各个样本的距离，只不过这种距离的计算转化为间接近似的方法而获得。PQ乘积量化方法在计算距离的时候，有两种距离计算方式，一种是对称距离，另外一种是非对称距离。非对称距离的损失小(也就是更接近真实距离)，实际中也经常采用这种距离计算方式。下面过程示意的是查询样本来到时，以非对称距离的方式(红框标识出来的部分)计算到dataset样本间的计算示意：

从上面这个过程可以很清楚地看出PQ乘积量化能够加速索引的原理：即将全样本的距离计算，转化为到子空间类中心的距离计算。比如上面所举的例子，原本brute-force search的方式计算距离的次数随样本数目N成线性增长，但是经过PQ编码后，对于耗时的距离计算，只要计算4*256次，几乎可以忽略此时间的消耗。另外，从上图也可以看出，对特征进行编码后，可以用一个相对比较短的编码来表示样本，自然对于内存的消耗要大大小于brute-force search的方式。

import numpy as np
import faiss

np.random.seed(42)
d = 128
nb = 1000000  
nq = 10  
data = np.random.random((nb, d)).astype('float32')
queries = np.random.random((nq, d)).astype('float32')

# 设置PQ参数
m = 8  # number of subquantizers
k = 256  # number of centroids per subquantizer

# 创建索引
quantizer = faiss.IndexFlatL2(d)  # 用于PQ的量化器
index = faiss.IndexPQ(d, m, k)
index.train(data)  # 训练索引
index.add(data)  # 添加数据到索引

# 查询
k = 5  
D, I = index.search(queries, k)  

# 输出结果
print("查询结果的索引:\n", I)
print("查询结果的距离:\n", D)

倒排乘积量化

倒排PQ乘积量化(IVFPQ)是PQ乘积量化的更进一步加速版。其加速的本质逃不开在最前面强调的是加速原理：brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。

在PQ乘积量化之前，增加了一个粗量化过程。具体地，先对N个训练样本采用KMeans进行聚类，这里聚类的数目一般设置得不应过大，一般设置为1024差不多，这种可以以比较快的速度完成聚类过程。得到了聚类中心后，针对每一个样本x_i，找到其距离最近的类中心c_i后，两者相减得到样本x_i的残差向量(x_i-c_i)，后面剩下的过程，就是针对(x_i-c_i)的PQ乘积量化过程。

import numpy as np
import faiss

np.random.seed(42)
d = 128  
nb = 1000000  
nq = 10  
data = np.random.random((nb, d)).astype('float32')
queries = np.random.random((nq, d)).astype('float32')

# 设置IVFPQ参数
nlist = 100  # coarse quantizer的聚类数
m = 8  # number of subquantizers
k = 256  # number of centroids per subquantizer

# 创建索引
quantizer = faiss.IndexFlatL2(d) 
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, k)

# 训练索引
index.train(data)
index.add(data)

# 设置要搜索的中心数
index.nprobe = 10  # 在查询时考虑的nlist个数

# 查询
topk = 5  
D, I = index.search(queries, topk) 

# 输出结果
print("查询结果的索引:\n", I)
print("查询结果的距离:\n", D)

最优乘积量化

最优乘积量化（Optimal Product Quantization, OPQ）是PQ的一种改进版本。其改进体现在，致力于在子空间分割时，对各子空间的方差进行均衡。在具体实现的时候，我们可以将Optimal的过程实现为一个组件。

通常，用于检索的原始特征维度较高，所以实际在使用PQ等方法构建索引的时候，常会对高维的特征使用PCA等降维方法对特征先做降维处理，这样降维预处理，可以达到两个目的：一是降低特征维度；二是在对向量进行子段切分的时候要求特征各个维度是不相关的，做完PCA之后，可以一定程度缓解这个问题。但是这么做了后，在切分子段的时候，采用顺序切分子段仍然存在一定的问题，这个问题可以借用ITQ中的一个二维平面的例子加以说明：

如上面a图所示，对于PCA降维后的二维空间，假设在做PQ的时候，将子段数目设置为2段，即切分成x和y两个子向量，然后分别在x和y上做聚类（假设聚类中心设置为2）。对a图和c图聚类的结果进行比较，可以明显的发现，a图在y方向上聚类的效果明显差于c图，而PQ又是采用聚类中心来近似原始向量（这里指降维后的向量），也就是c图是我们需要的结果。这个问题可以转化为数据方差来描述：在做PQ编码时，对于切分的各个子空间，我们应尽可能使得各个子空间的方差比较接近，最理想的情况是各个子空间的方差都相等。上图a图中，x和y各个方向的方差明显是差得比较大的，而对于c图，x和y方向各个方向的方差差不多是比较接近的。

OPQ致力于解决的问题正是对各个子空间方差的均衡。具体到方法上，OPQ借鉴了ITQ的思想，在聚类的时候对聚类中心寻找对应的最优旋转矩阵，使得所有子空间中各个数据点到对应子空间的类中心的L2损失的求和最小。OPQ在具体求解的时候，分为非参求解方法和带参求解方法，具体为：

• 非参求解方法。跟ITQ的求解过程一样。
• 带参求解方法。带参求解方法假设数据服从高斯分布，在此条件下，最终可以将求解过程简化为数据经过PCA分解后，特征值如何分组的问题。在实际中，该解法更具备高实用性。
  从上面可以看到，倒排乘积量化IVFPQ可以视为1阶段的MSVQ和PQ的结合版本，而OPQ是PQ对子空间方差均衡的改进。基于这样一种普适性的视角，可以构建一种矢量量化框架，MSVQ、PQ、OPQ中的O，都是该矢量量化框架中的基础组件。

参考

https://yongyuan.name/blog/vector-ann-search.html

https://zhuanlan.zhihu.com/p/264367144

https://github.com/datawhalechina/what-is-vs