向量数据库|第1期|从零开始学习

1、向量数据库中的基本概念

1.1 什么是余弦

余弦函数是一种三角函数，在直角三角形中，某个锐角的余弦为：临边与斜边的比值，如下图cosA=b/c。引申到任意三角形中，即余弦定理：a2 =b2+c2-2bc*cosA，任意三角形的任一边的平方等于其他两边的平方和减去这两边与夹角余弦乘积的两倍。该公式转换下，余弦为：cosA=( b2+c2- a2 )/2bc

1.2 向量

万物皆向量，比如经常看到的地铁指示牌“前方500米”，就是一个向量，给出我们信息：方向和大小。可以将向量表示在平面直角坐标系中：

这仅是一个二维向量，那么所谓的“向量数据”：由多个数值组成的序列，可以表示一个数据量的大小和方向。通过embedding技术，图像、声音、文本可以表示为一个高维的向量。比如一个图片可以转换成一个由像素值构成的向量。

注：简单来讲embedding是一种将高维数据转换成较低维的向量表示的技术。比如显示的地理地形信息远超过三维，但是地图通过颜色和等高线等来最大化表现现实的地理信息。

1.3 向量间的加减法和点积

1）向量加法

同原点的情况下，可以做一个平行四边形（平行四边形法则），如上图所示，红色的对角线即为c=a+b

当然，也可以根据三角形原则，将b向右平移，和向量a形成一个首尾相接，那么a+b结果即为和向量a起使点相同，指向平移后的向量b。

2）向量减法

a-b可以认为是a+(-b) ,-b和向量b大小相同，方向相反。

3）向量点积

1.4 向量间的相似度

向量间的相似度用于衡量两个向量在数值上的接近程度。相似度计算是向量分析的核心工作之一。常用的相似度计算方法：余弦相似度、内积和欧式距离。

1）余弦相似度

余弦相似度是一种衡量两个向量之间相似程度的量度，通过计算两个向量夹角的余弦值来评估。返回到向量减法小节，(a-b)·(a-b)=c·c,左边继续展开，a·a-a·b-b·a+b·b=a·a-2a·b+b·b；假设ab夹角为A：c·c=a·a+b·b-2|a|·|b|cosA。那么|a|·|b|cosA=2a·b，所以cosA=(a·b)/(|a|·|b|)，即两个向量的余弦就等于他们的点积除以他们模长的乘积。如此，只要植到向量的值，就可以得出他们之间的余弦相似性了。需要注意，使用余弦相似性时，长度不重要，方向才重要，也就是两个向量之间的夹角大小，夹角为0，表示两个向量完全相同或者指向同一个方向；若是90度，则方向完全不相似，没有相关性；若为180度，则方向相反。

2）欧式距离

也就是欧几里得空间中两点之间的直线距离，可以直观地表示两点之间的远近程度。两个向量的欧式距离，通过计算对应分量插值的平方和，再开方得到，它关注的是向量之间的绝对距离，适用于比较两个向量再空间中的相对位置：

其中，n表示他是n维向量，上图表示两个向量在第i维度上的分量差平方和，然后在开方就是两个向量的欧式距离。

1.5 准确率、精确率与召回率

准确率就是被正确预测出来的数量除以所有样本。精确率和召回率的分母与准确率的分母不一样。

精确率的分母是预测到的正类，它的提出为了让模型现有的预测结果尽可能不出错，你可以漏检但不能预测不对。地震模型为例，以天为单位记某一天地震为正样本，不地震为负样本，需要预测接下来100天的地震情况。假设知道第20和第30天会地震，其余时间不会地震。为了不误报地震，仅预测了第20天可能发生地震，那么此时精确率：1/1=100%。

再比如预测了第10天、第20天、第30天、第40天、第50天地震，那么此时的精确率：2/5=40%。

也就是说精确率的分母是预测到的正类数，分子为预测到的正类中预测对的数量。

召回率：分母是原本的正类，他的提出是让模型预测到所有想被预测到的样本（多预测一些错的也是可以接受的）。假设知道第20、第25天、第30天和第40天会地震，其余时间不会地震比如预测了第10天、第20天、第35天、第40天、第50天地震，那么此时的召回率：2/4=50%，即分母为原本真正会地震的天数，分子为预测结果中正确的天数。

1.6 KNN与ANN检索

1）KNN（k-nearest neighbors）即K近邻算法，以下面例子说明

假设有以下一组二维数据点，每个数据点有两个特征(x和y坐标)以及对应的类别（红色和蓝色）：

x	y	类别
2	4	红色
3	5	红色
5	7	蓝色
6	8	蓝色
7	9	蓝色

现在要对一个新的数据点（4，6）进行分类，首先确定K值，假设K为3，计算新数据点与每个已有数据点的距离，可以使用欧式距离公式，与每个点的距离分别为： $2\sqrt{2}$ 、 $\sqrt{2}$ 、 $\sqrt{2}$ 、 $2\sqrt{2}$ 、 $3\sqrt{2}$ ；找出距离最近的K=3个数据点，这里是(3,4)、(5,7)、(4,4)，他们类别都是红色，通过投票所以数据点(4,6)被分类是红色。

缺点：必须计算与数据库中每个向量的举例，如果必须搜索数百万个向量，这将非常低效。

2）ANN（Approximate nearest neighbor）相似最近邻

这里我们以局部敏感哈希来说明，局部敏感哈希的核心思想是通过设计特殊的哈希函数，使得相似的对象在经过哈希后有较大概率被映射到相同的哈希桶中，而不相似的对象被映射相同的哈希桶的概率较小。

举例：假设有一个包含许多二维数据点的数据集：(1,2)、(3,4)、(5,6)、(7,8)、(9,10)，现在要为查询点Q=(4,5)找近似最近邻。首先构建hash函数，将所有数据集通过hash函数构建到hash表中，然后Q点也用通用的hash函数进行计算。假设(1,2)、(3,4)被映射到桶A，(5,6)、(7,8)被映射到桶B，(9,10)被映射到桶C；计算Q的哈希值，确定所在桶，假设映射到A，从A中取出数据点(1,2)、(3,4)，计算他们与Q的举例，假设(3,4)的距离最近，暂时将(3,4)作为近似最近邻；为了提高准确性，可以进一步检查相邻桶比如B的数据点，计算B中的数据与Q的距离，若发现有比(3,4)更近的，则更新近似最近邻。

通过这种方式，可以在相对较短的时间内找到较为接近的数据点。

2、为什么出现向量数据库

传统数据库技术，不管是关系型还是非关系型，他们都是面向结构化数据的存储和高效访问而设计的。而我们社会中，更多数据没办法简单抽象出来并结构化，比如书中大量文本数据、音乐中的音频、图像数据等。向量数据与传统的结构话数据的四个差异：1）维数差异：向量数据格式的维度比较多，无法简单将向量数据各维度拆分后存储到传统数据库的行和列里面。2）字段内相关性差异：向量数据多个维度之间的数据相关性很强，往往需要多个字段组合计算才能比较准确地衡量两个向量的相似度。3）优化手段差异：向量数据的格式单一，每个维度的数据往往是固定格式数据（浮点数、二进制整数等），比如对于相关的数学运算可以更好地利用CPU缓存机制加速，也可以利用CPU/GPU硬件特性等。4）使用方法差异：例如对于文本数据，传统数据格式基于关键词进行精确匹配，不会理解词语背后的语义，而向量数据的匹配基于语义理解。

另外，对于音频、图片、视频这些非结构化数据，传统的关系型数据库更难进行索引。为更好接近向量数据的存储、索引和查询，有必要结合向量数据的特点设计专门的向量数据库。

3、向量数据库核心能力

向量数据库需要对向量数据进行各种操作：

向量检索：根据给定向量，找出数据库中与之最相似的向量。比如用户输入一张图片进行搜索时，先将这个图片转换成一个向量，通过向量之间的近似检索，找到与输入图片最相似的图片
向量聚类：根据给定的相似度度量，将数据库中的向量进行分类，例如根据图片的内容或风格将图片分成不同主题
向量降维：根据给定的目标维度，将数据库中的高维向量转成低维向量，以便可视化或压缩存储
向量计算：根据给定算法或模型，对数据库中的向量进行计算或分析

我们下面主要介绍向量数据库中的索引。向量数据库通常通过向量索引提高对向量数据的访问和查询效率。业界主流向量数据库通常支持扁平索引、HNSW索引和IVF索引等向量索引方法。

3.1、扁平索引

将原始的向量数据平坦地摆放到内存中，不增加任何辅助机制。在检索时需要计算每个向量与目标向量的相似性，也称为“暴力索引”，本质上就是全内存+KNN检索，召回率100%，但是对与大规模数据集查询效率低

3.2、HNSW索引

Hierarchical Navigable Small World，分层导航小世界，是一种经典的图结构索引。优势在于性能和召回率都比较稳定。用于支撑ANN索引的一种方式。

首先需要了解什么是NSW：将每个点在入库时和它最近的若干个点建立索引，也就是互为邻居。当图构建完毕时，每个点都可以很快地访问到自己最近的几个邻居。

1）在下图二维空间上构建一个NSW索引，该层有一个entry点，找一个最近邻，下图中的红色点。需要找到search向量（蓝色点）的最近邻

寻找最近邻的直观方法：首先找entry点相邻的点中距离search vector最近的点，如下图所示，假设该点时1st；然后找1st相邻的点中距离search vector最近点，假设时2nd；依次类推，假设2nd的所有邻居距离search vector都没有2nd近，搜索结束，2nd就作为最近邻结果

2）insert流程和search流程类似。首先找到待插入向量最近的k个邻居，这里假设为3，那么就和这3个最近的邻居构建索引，即添加一个边

假设度为5，但是这里看到添加后，如下图黄色的两个点超过了，那么就需要进行裁剪

同样计算黄色的两个点的k-nearest邻居，这里的k就是度5，如下图，将虚线部分去掉，最终构建出NSW索引

HNSW在NSW索引上添加了分层架构，可以让检索更快。这个idead和调表结构类似，底层即0层的NSW包含所有信息。随机选一些向量放到上层（越上层向量越少，并且也是NSW索引），搜索从最上层开始，使用该层的最近邻作为下层的entry点：

1）索引查询：首先从layer2开始，找到该层的最近邻点，将其作为layer1的entry点；在layer1层找entry点的最近邻；依次类推知道最底层layer0，找到k-nearest邻居（下图是3-nearest）

2）插入：插入前需要决定插入那一层，HNSW论文中使用的计算方法：

如下图所示，我们决定在level1这一层插入：

在level1层找到最近的k个邻居，这里是2个，然后建立索引，也就是将他们连接起来；然后继续到下一层，也就是level0，同样的方法找到最近的2个邻居

当然，这里会有一个问题，如下图所示：每层中的度是有阈值的，若超过就需要进行裁剪；在插入Q之前A和B之间有连接，插入Q后若A的度超过了，进行裁剪时需要裁剪掉A和B之间的线，那么R1和R2的范围就产生了孤岛，如果entry点在R2，查询节点在R1，就永远找不到合适的结果。HNSW为解决这个问题，设计了新的搜索算法，假设被重构点的top k近邻全部挤在一起，就舍弃其中几个，选择保留相对较远的其他近邻。

如下图所示：选择保留R到C的连接（索引）

3.3、IVF索引

倒排文件索引，首先对向量数据进行聚类，然后在聚类内部构建一个倒排索引信息，并且可以叠加量化和压缩算法。查询精度相对较低，召回率低，需要预先构建聚类算法，实时性相对较差。

什么是倒排索引呢？以文本文档搜索为例，若要搜索包含给定单词的文档，正排索引会存储每个文档的单词列表（文档号-->该文档中的单词），需要检索每个文档才能找到相关文档。而倒排索引则是单词-->文档的映射，每个单词都有一个该单词所在的文档索引列表。可以将搜索限制在选定的映射列表中。

通常IVF和FLAT会结合在一起，即IVF-FLAT索引，这种索引定义了集群中心，对于每个集群中心都有属于该集群的向量索引列表，只需要选定特定集群，就可以加快搜索速度。当然，召回率就相对较低了。

下面介绍下IVF-FLAT索引的构建：

1）假设我们在二维空间有向量，如下图所示

2）可以使用K-means算法找到上面向量的质心（聚类概念），每个质心对应一个桶，每个桶存储一簇向量。到两个质心欧式距离相等的点构成边，表示每个桶的分隔线：

3）现在有了质心，算法就可以遍历所有向量，并根据距向量最近的质心将它们放入相应的桶中：

4）INSERT

找到距离向量最近的质心并将向量放入该桶中，下图例子，红色顶点加入到A桶

5）查询

以下图为例，红色顶点是用户想要查找的基准向量，他有5个最近邻。如果我们近从A桶中查找（红色顶点所在桶），会找到桶A的5个顶点。然而，有可能在A桶的邻居B桶中存在到基准探测向量更近的点。因此，为了提高查找的准确性，最好探查多个桶以得到更近准确的最近邻。

索引查找中，您需要探测指定数量个质心桶，从每个桶中检索k个最近邻居（我们称之为本地结果），并进行top-n排序以获得k个最近邻居（全局结果）。

参考

https://www.modb.pro/doc/129775
https://zhuanlan.zhihu.com/p/708821188
https://www.modb.pro/doc/131625
https://www.modb.pro/doc/134473
https://www.modb.pro/db/1765287755676979200
https://www.modb.pro/db/103254
https://cloud.baidu.com/doc/VDB/s/5lvesvssy
https://www.timescale.com/blog/nearest-neighbor-indexes-what-are-ivfflat-indexes-in-pgvector-and-how-do-they-work/
https://www.datastax.com/guides/what-is-a-vector-index
https://zhuanlan.zhihu.com/p/712991028