一、向量检索图解总结
二、概念与方法
2.1 基础概念
度量方式:欧式距离,cos距离,汉明距离,jaccard相似度
分类
- 基于空间划分
举例:乘积向量化,哈希等
优点:内存占用小,动态数据增删,召回较高
- 基于图划分
举例:NSW,HNSW
优点:召回高
缺点:内存占用打,数据动态删减不易
2.2 检索方法
2.2.1 基于空间
1. 基于树的方法
举例:KDTree算法
树的构建
选择方差最大的维度分裂,每次拆分成2个子树
查询
从根节点出发,执行深度优先遍历,以查找的点为圆心,单前遇到的树的节点的距离为半径画圆,过滤没有橡胶的圆,直到半径不再更新。
特点
复杂度:O(kn**((k-1)/k)),与k成线性关系,不适合高纬度向量召回
2. 基于hash的方法
举例:LSH,local sensitive hashing,局部敏感哈希
树的构建
方法:每个平面分隔,左边为0,右边为1,得到该平面的哈希值,多个平面来分隔,就可以得到完整的hash值了,有个特点,hash值相近的,在原始向量空间靠的也近,感觉也是一种降维的方法来求相似度。
查询:
从根节点开始往下找
特点:
局部敏感:相似样本的点对比远的点更容易发生碰撞
K
● 太小:很多点都在一个桶里面
● 太大:每个桶数据太小,需要增加L来增加召回
L
● 太小:召回不够
● 太大:计算量增加
Multiprobe LSH作用:T,在桶里面找邻近点可能不够,还在改桶的邻居里面也找找,可以减少L的数量,增加找到邻居的机会,T为邻居桶查找的数量
3.乘积量化
定义:
乘积向量化(product quantization),核心思想是分段和聚类,kmeans是pq乘积量化子空间数目为1的特例
构建,以128维的样本维度为例:
- 将其切分为4个子空间,每个子空间的维度为32维
- 对子向量采用kmeans对其进行聚类,例如聚类成256类,这样每个子空间有32维的维度,256个中心
- 训练样本的每个子段,都用子空间的聚类中心来近似,对应的编码为中心的id
查询,输入:128的查询向量
- 还是分词4个子段
- 计算每个子段到子空间所有聚类中心的距离,可以得到4*256个距离,存到cache里面,后续遇到具体样例的距离计算,可以通过查表得到。
时间
相对于brute-force search,只需要计算4*256词,几乎可以忽略此时间
内存
用一个相对比较短的编码来表示样本,内存消耗大大小于brute-force search
4. 倒排乘积量化 IVFPQ
背景:PQ乘积量化,还是需要计算4*256次,对每个样本,还是要挨个求和相加计算距离-> 有没有方法
方法:先聚类,以聚类为中心构建索引,然后后面的步骤和PQ一致,先划分成子空间,然后子空间聚类,然后再编码…
查询:先粗量化,快速定位属于哪个c_i,然后再在该兴趣区域按PQ乘积向量化距离计算方式计算距离
2.2.2 基于图
● 基于空间划分的缺点:
为了提高召回率,每个向量只会属于某个子区域,需要搜索较大的空间,导致计算量增加
● 基于图的方法概述
基础:邻居的邻居也可能是邻居
方法:KGraph,NSG,HNSW,NGT
1.NSW
- Regular graph:每个顶点邻居数目相同
- Random graph:每个顶点的邻居数目是随机的
- small world graph:介于上面两者之间
特点:
- 同质性:相似的顶点聚集在一起,相互连接具有相邻边
- 若链接:每个顶点上会有一些随机的边连接到网络中的顶点上
- 原理:构建small world graph->随机选择一个其实顶点->遍历邻居节点->选择与目标最近的顶点继续遍历->直到找到最近的顶点
查找:
从enter pointer顶点开始查找->查找绿色的邻居顶点,可以通过高速公路机制快速找到结果
缺点:
- 通过节点的随机插入引入随机性->构建出small world graph,但是图的构造不稳定,节点之间的差异大
- 先插入的顶点,链接的邻居节点,基本都比较远(弱连接属性强)
- 后插入的顶点,其连接的邻居节点,基本都比较近(弱连接属性弱)
- 聚类效应的点,后续插入的点可能都和其建立连接,对应节点的度可能比较高
2. HNSW
HSW缺点:
- 通过节点的随机插入引入随机性->构建出small world graph,但是图的构造不稳定,节点之间的差异大
- 先插入的顶点,链接的邻居节点,基本都比较远(弱连接属性强)
- 后插入的顶点,其连接的邻居节点,基本都比较近(弱连接属性弱)
- 聚类效应的点,后续插入的点可能都和其建立连接,对应节点的度可能比较高
如何构造更稳定的small world graph->NSW->对图进行分层->由粗到细的检索->HNSW
构建步骤:
- layer=0,包含数据集所有点
- layer=1,以50%的概率随机从layer0选择点构成
- layer=l,以50%的概率随机从layer l-1选择点构成
- 插入图时,先计算新顶点可以深入到第几层,在每层的NSW图中,找到m个邻居,并链接他们
查询:
从最高层开始检索,逐层往下,从而实现快速搜多
特点:
● cos距离效果很好,内积不佳
● 内积距离不满足三角不等式,dx+dy!>不一定大于dz,因距离没有传递性
免费体验阿里云高性能向量检索服务:https://www.aliyun.com/product/ai/dashvector