向量数据库技术系列一-基本原理

一、前言

    随着AI大模型的发展，向量数据库也迎来了重要的发展机遇，是近几年最火热的技术之一，本系列将带您一起了解向量数据库的技术原理，介绍当前主流开源向量数据库(Milvus,Chroma,Faiss,Weaviate)的应用和基本操作，并通过案例进行进一步学习实操。

二、什么是向量数据库

     我们知道，传统的数据库比如Mysql，MongoDB，ClickHouse等，存储的是结构化或者半结构化的数据，通过Sql或类Sql语句进行检索，检索出来的结果也是精确匹配。比如：

    可以通过"select * from xx where 职业='网络直播'"，快速检索到职业为网红的人员记录。

     在AI和大数据时代，这种检索结果不一定能满足我们的要求，比如，我们要检索出于网络直播相似职业的人员记录，显然，从常识上判断，小帅的直播带货职业最相似的，这种我们称之为"相似检索",利用传统的数据库是无法实现，而向量数据库就是实现相似检索的数据库。

    作为数据库，最核心的功能是存储和检索，向量数据库也不类外，存储的是向量，实现的是向量的相似检索。接下来我们了解这两部分的内容。

三、向量

1、什么是向量

 在数学中，向量是相对于标量的，它即有大小，又有方向，也称之为矢量。一般是用带箭头的线段表示，比如在二维空间中，向量可以用二维坐标表示。

向量可以扩展到多维空间，成为多维向量。

2、向量距离

向量是多维空间中的一个矢量，计算两个向量之间的距离，有以下几种方法。

(1)、欧式距离

欧式距离就是计算向量在空间的实际距离，以二维空间为例，两个向量点的距离，根据勾股定理。

扩展到多维空间，公式如下：

(2)、余弦距离

     余弦距离使用向量的夹角的余弦值表示，夹角越小，余弦值越大。夹角为0时相似度为1，夹角90度时，相似度为0，夹角180时相似度为-1，因此余弦相似度的取值范围为[-1,1]。

相比欧氏距离，余弦距离更加注重两个向量在方向上的差异，而不是位置上的差异。

(3)向量内积

向量a[a1,a2,...,an]与向量b[b1,b2...,bn]内积的计算公式如下：

内积的结果是一个标量。内积又可以表示为（两者之间的推算可自行参考：https://zhuanlan.zhihu.com/p/616207329）：

其几何意义为，a向量在b向量上的投影，再与b向量的模相乘，当为0时，

当为时，

由此可见，向量内积不仅体现了方向，还考虑了模长，一定程度上内积是包含了余弦距离的要素。

3、向量化

    如果要做向量检索，首先要将目标向量化。在现实世界中，我们要描述一个目标，通常会使用多个属性去描述，比如前面讲的职业，可以用工作时间，薪资待遇，所属行业等等属性形容。将这些属性量化，每个属性看做一维，就可以用多维空间中的向量来表示目标，这个过程就是向量化，而描述目标的属性，就叫做特征属性。如：

将目标向量化后，相似检索就可以转化为计算向量距离，距离越近，就越相似。

四、相似度检索算法

     向量的相似检索就是在一堆向量中，找出与目标最接近的向量，比如检索出于"up主"最相似的3个职业，或者从一堆用户中，查找出与目标用户最类似的人群等等。

影响相似算法三个要素，检索速度，检索质量，资源占用，好的算法一定是这三者的平衡。

1、暴力检索

最先想到的应该就是暴力检索，目标向量与所有的向量计算距离，最后返回最相似的几条。

    这种算法的优势是检索出来的结果质量高，但是速度和资源占用就很低效。一般是用于数据量和维度都少的情况。

2、基于聚类的最近邻算法(ANN)

    暴力检索效率低主要原因是因为与每个候选的向量进行比较，搜索范围过大。那有没有减少搜索范围的方法呢？

   我们知道在传统的数据库中，通过创建索引字段(比如时间)，这样在查询时，通过给定索引字段值减少搜索范围。那么在向量检索中，也可以通过聚类实现这一目的。

    具体的做法是，将向量通过聚类算法(如k-means),划分为多个聚类中心，每个中心都会有一个质心(红色标记)

    先与各个质心比较距离，找出最近的聚类中心，然后在与中心中向量进行比较。

     这种检索方式，虽然能提升效率，但是也会使得检索质量大大折扣。比如下面的向量，通过聚类检索后，定位到A中心，但实际上和C中心的向量1最近。

    为了这种边缘问题，提升检索精确度，一般优化方式有：

1、加大聚类中心的数量，尽可能减少这种边缘点的存在。但中心数量多，又会影响效率，所以这两者之间需要有平衡。 

2、同时搜索多个聚类中心，扩大搜索范围，比如同时搜索中心A，C两个中心。这是也就是Faiss算法。

3、基于倒排索引的算法(IVF)

      倒排索引是相对于传统的正向索引的一种数据结构，在传统的正向索引中，每个文档对应一个列表，包含该文档中出现的所有关键词。而在倒排索引中，这种结构被反转，每个关键词对应一个列表，包含包含该关键词的所有文档。我们熟悉的Elasticsearch就是采用这种索引，提升文件的检索效率。

    在向量数据库，使用倒排索引，一般都需要借助聚类的方法，也可以认为是聚类方式一种补充和后续。

      聚类完成后，将空间划分为m个子聚类中心，每个子聚类中心中的所有向量与该中心的质心的映射关系建立倒排索引。检索到向量最近的聚类中心后，通过倒排索引，就可以快速查询出该子空间的所有的向量，计算出最近邻的K个向量。

    倒排索引是向量检索中最常用的算法。

4、位置敏感哈希(LSH)

    除了k-means聚类算法，位置敏感哈希(LSH,也成局部敏感哈希),也是一种聚类算法。

    典型的Hash算法，是希望不同值，通过hash函数出来的结果也不同，即使有相同(碰撞)，也要使其发生的概率越小越好。而位置敏感哈希，刚好相反，是希望位置相邻的值，hash出来的结果应该一样，放入到同一个桶中，实现聚类。

    接下来，我们来演示下LSH如何实现的。还是以二维向量为例。

     有A，B，C三个向量，从直观上看，A，B两个向量更加接近，那么hash后出来的结果相同或者接近，才能实现我们聚类的目的。

首先，随机生成一条线，以该线为界限，右边空间编码为1，左边向量为0

那么可以得出C的编码为1，A，B的编码为0。以此类推，再生成一条线。

C的编码变为11，A，B的编码为00。

可以想一下，如果要使A，B的编码不同，那么这个直线就需要从A，B之间穿过，如下图：

 此时，C的编码为111，A的编码是000，B的编码为001。

由于AB的距离较近，而AC，BC的距离较远，而我们的直线又是随机生成的，就意味着穿过AC，BC的概率要大于穿过AB的距离。所以，最终的得出的编码，AB更加相似。最终的编码如下：

A：0001001101

B：0011001001

C：1110110100

按照编码段分为5个段，每一段按照编码值，放到不同的桶中。

可以看到AB再1，3，5的位置，在一个桶中。

在三维空间，切割线就换成切割面，在高维空间，就使用超平面，原理类似。

在目标检索中，可以找出与目标重合度最多桶的向量，就为最相似向量。

5、基于树的算法(KD)

      在传统的数据库中，常用树做索引，比如B+树。那么在向量检索中，也可以构造成一颗树，其中KD树就是一种，我们还是已二维平面为例，介绍其设计思想。如下图：

现有如下6个点，并按照x轴进行排序(1,4),(2,3),(4,2),(5,6),(6,2),(7,1)

1、取中位数点(5,6),以此点做垂直轴，将平面一份为二，右边的都大于5，左边的都小于5。

2、构造以(5,6)为根节点的树

3、再分别对左右树以Y轴排序进行排序，左边:(4,2),(2,3),(1,4)，右边:(7,1),(6,2)，找出中位数(2,3)和（6,2）。

4、分别以这两点做水平线，将左右平面分为上下两部分。以左边为例，上部分大于3，下部分小于3.

5、 继续构造左右部分的树，如下：

此时，每个枝上只剩下一个节点，称为叶子节点，就无需继续了。到此树就构造完毕。 

有了KD树，就可以通过二叉树算法进行快速检索出相似向量。

6、基于图的算法(HNSM)

     我们先看NSM（Navigating Small World）它实际是一种图算法。空间中的向量使用线段连接起来，从而形成一张图。其中连线的方式方式有如下定义：

• 所有的节点必须有相邻的节点；
• 相邻的节点必须有连线；
• 邻近友元的个数作为超参，由用户指定。

  有了这张图够，我们要找一个目标向量P的最近的向量，就可以按照这个图搜索。

   首先随机找一个entry point，然后计算该entry point以及其邻居节点与P的距离，确定最短距离的节点后，再按照这个方式循环往复，最后找到一个节点point，其邻居节点与P的距离都大于该point与P的距离，那么这个节点point就是目标项目的最近向量。

     这种图搜索其实是一种贪心算法，如果选择的entry point选择的目标P距离较远，就会导致搜素的路径边长，海量节点的情况下，效率会大大折扣。

   NSM方法又进行了一些改进。选择一些非相邻的节点，也进行连接，如下面红色的线。

 那么在搜索的过程中就可以先通过红色的长线快速导航，再通过短线进行再进行精确搜索。

   这种先粗后细，先快后慢的算法即确保了搜索的效率，有兼顾了搜索的精确性。

    HNSM是NSM的一个变种，它将长线变成了分层，底层包含了所有节点，越往上节点节点越稀疏，搜索时，从最上层开始，每层通过NSM算法，搜索最形似的节点，然后继续往下一层，从该节点的邻居节点找出最相似，依次往下，直到最后一层，找到最近的向量节点。

HNSM相比较NSM，更加的稳定，效率也更高。

五、量化

     之前你可能了解大模型的量化技术，通过降低模型参数的精度，将浮点数转换为整数或定点数，从而实现模型的压缩和优化，虽然损失一部分精度，但是能加快推理速度以及减少内存的开销。

     对于向量的量化，其目的也是类似，其量化的方法主要包括SQ（ ScalarQuantization ）和PQ（ Product Quantization ）。

    SQ，与大模型的量化方式有点类似，是将每一个维度量化成指定位数的一个数，比如将32位的int量化成8位的int，通过损失一定的精度，缩减存储成本。

   PQ，是通过降维的方式来实现。这里我们重点讲下这个方法。

   前面分析了聚类算法，通过聚类的质心代表整个聚类，可以大大提升检索效率。但随着向量数量和维度的增加，所需要的聚类数据就会越多，我们来分析。

比如在一维空间中，下面向量可以聚类成2个子空间。

如果这些向量投射到二维空间中，可能被聚类成6个子空间，且向量越稀疏，划分的子空间个数越多。

    可以想象下，实际工程中，上千维，千万级的向量是很常见的，那么聚类的子空间是惊人的，存储这些聚类的质心，就得耗费大量的内存，这就是维度灾难。

   既然维度越低，聚类的数量就越少，那么是不是通过降维的方式来实现呢，PQ就是采用这种思路实现的，具体的做法如下：

首先，将向量的维度进行切割，比如128维的，切割为4段，每段32维。

再在每个子维度空间中做独立的聚类，比如构建256个聚类中心。

     这样聚类中心就为4*256个。聚类中心个数大大减少，所需要的内存资源也减少。

     在检索时，同样将待检索的向量量化为4个子维度段，如[m1,m2,m3,m4]，然后每个维度段独立查询计算向量与库里面向量的距离，如d1为查询向量第一段子向量与其ID为m1的簇心的距离，d2，d3，d4同理，最终距离d=d1+d2+d3+d4。

其实可以思考下，量化后的检索是将指数级计算变成了加法。

量化是可以相似度检索算法结合一起使用，比如倒排索引结合PQ，就是IVF_PQ。

六、总结

  本章节主要介绍了向量的基本概念，以及向量检索的基本算法。我们来总结下这些算法：

(1)暴力检索，检索的精度最高，适合在小规模，百万级数据集上场景。

(2)聚类检索，检索的精度比较准确，但会消耗算力，耗时也较长。

(3)倒排索引，一般与量化算法结合，在精确，速度和内存消耗方便达到一定平衡，使用较广泛。

(4)位置敏感哈希，这种方法使用的较少。

(5)基于树的算法，这种方法使用的较少。

(6)、基于图的算法，结果较准确，速度快，但消耗内存，适合对搜索效率有很高要求的场景。

 附件

向量数据库技术系列一-基本原理

向量数据库技术系列二-Milvus介绍

向量数据库技术系列三-Chroma介绍

向量数据库技术系列四-FAISS介绍

向量数据库技术系列五-Weaviate介绍