如何用乘积量化实现“拍照识花”功能？高效的图片检索技术，那它究竟是怎么实现的呢？
聚类算法 和 局部敏感哈希 的区别
检索图片和检索文章一样，首先需要用向量空间模型将图片表示出来，也就是将一个图片对象转化为高维空间中的一个点。这样图片检索问题就又变成了我们熟悉的高维空间的相似检索问题。<br /> 把每个图片中的像素点看作一个维度，把像素点的 RGB 值作为该维度上的值，那一张图片的维度会是百万级别的。这么高的维度，检索起来会非常复杂，该怎么处理呢？我们可以像提取文章关键词一样，对图片进行特征提取来压缩维度。<br /> 要想实现图片特征提取，有很多种深度学习的方法可以选择。比如，使用卷积神经网络（CNN）提取图片特征。这样，用一个 512 到 1024 维度的向量空间模型，我们就可以很好地描述图像了，但这依然是一个非常高的维度空间。因此，仍然需要使用一些近似最邻近检索技术来加速检索过程。常见的一种方案，是使用聚类算法来划分空间。<br />
局部敏感哈希的不足
一种常用的近似最邻近检索方法，是使用局部敏感哈希对高维数据进行降维处理，将高维空间的点划到有限的区域中。这样，通过判断要查询的点所在的区域，我们就能快速取出这个区域的所有候选集了。上一讲中我们也提到，局部敏感哈希由于哈希函数构造相对比较简单，往往更适合计算字面上的相似性（表面特征的相似性），而不是语义上的相似性（本质上的相似性）。这怎么理解呢？举个例子，即便是面对同一种花，不同的人在不同的地点拍出来的照片，在角度、背景、花的形状上也会有比较大的差异。也就是说，这两张图片的表面特征其实差异很大，这让我们没办法利用局部敏感哈希，来合理评估它们的相似度。
而且，局部敏感哈希其实是一种粒度很粗的非精准检索方案。以 SimHash 为例，它能将上百万的高维空间压缩到 64 位的比特位中，这自然也会损失不少的精确性。类聚算法
和简单的局部敏感哈希算法相比，聚类算法能将空间中的点更灵活地划分成多个类，并且保留了向量的高维度，使得我们可以更准确地计算向量间的距离。好的聚类算法要保证类内的点足够接近，不同类之间的距离足够大。一种常见的聚类算法是 K-Means 算法（K- 平均算法）。
K-Means 聚类算法的思想其实很“朴素”，它将所有的点划分为 k 个类，每个类都有一个类中心向量。在构建聚类的时候，我们希望每个类内的点都是紧密靠近类中心的。用严谨的数学语言来说，K-Means 聚类算法的优化目标是，类内的点到类中心的距离均值总和最短。
K-Means 聚类算法具体的计算步骤如下:
- 随机选择 k 个节点，作为初始的 k 个聚类的中心；
- 针对所有的节点，计算它们和 k 个聚类中心的距离，将节点归入离它最近的类中；
- 针对 k 个类，统计每个类内节点的向量均值，作为每个类的新的中心向量；
- 重复第 2 步和第 3 步，重新计算每个节点和新的类中心的距离，将节点再次划分到最近的类中，然后再更新类的中心节点向量。经过多次迭代，直到节点分类不再变化，或者迭代次数达到上限，停止算法。
使用聚类算法进行相似检索
检索流程
首先，对于所有的数据，先用聚类算法将它们划分到不同的类中。在具体操作之前，会给聚类的个数设定一个目标。假设聚类的个数是 1024 个，那所有的点就会被分到这 1024 个类中。这样，就可以用每个聚类的 ID 作为 Key，来建立倒排索引了。
建立好索引之后，当要查询一个点邻近的点时，可直接计算该点和所有聚类中心的距离，将离查询点最近的聚类作为该点所属的聚类。因此，以该聚类的 ID 为 Key 去倒排索引中查询，就可以取出所有该聚类中的节点列表了。然后，遍历整个节点列表，计算每个点和查询点的距离，取出 Top K 个结果进行返回。检索中会出现的两个问题
最近的聚类中的节点数非常多。这个时候，我们就计算该聚类中的所有节点和查询点的距离，这个代价会很大。这该怎么优化呢？
可以参考二分查找算法不断划分子空间划分的思路，使用层次聚类将一个聚类中的节点，再次划分成多个聚类。这样，在该聚类中查找相近的点时，我们通过继续判断查询点和哪个子聚类更相近，就能快速减少检索空间，从而提升检索效率了。
该聚类中的候选集不足 Top K 个，或者担心聚类算法的相似判断不够精准，导致最近的聚类中的结果不够好？
那我们还可以再去查询次邻近的聚类，将这些聚类中的候选集取出，计算每个点和查询点的距离，补全最近的 Top K 个点。
乘积量化_压缩向量
为什么要压缩向量
对于向量的相似检索，除了检索算法本身以外，优化存储空间也很重要。以 1024 维的向量为例，因为每个向量维度值是一个浮点数（浮点数就是小数，一个浮点数有 4 个字节），所以一个向量就有 4K 个字节。如果是上亿级别的数据，光是存储向量就需要几百 G 的内存，这会导致向量检索难以在内存中完成检索。 因此，为了能更好地将向量加载到内存中，我们需要压缩向量的表示。
比如说，可以用聚类中心的向量代替聚类中的每个向量。这样，类内的每个点都可以用这个类的 ID 来代替和存储，我们也就节省了存储每个向量的空间开销。那计算查询向量和原始样本向量距离的过程，也就可以改为计算查询向量和对应聚类中心向量的距离了。
想要压缩向量，我们往往会使用向量量化（Vector Quantization）技术。其中，我们最常用的是乘积量化（Product Quantization）技术。乘积量化的原理
量化：指的就是将一个空间划分为多个区域，然后为每个区域编码标识。
比如说：一个二维空间 可以被划为两块，那我们只需要 1 个比特位就能分别为这两个区域编码了，它们的空间编码分别是 0 和 1。那对二维空间中的任意一个点来说，它要么属于区域 0，要么属于区域 1。
这样就可以用 1 个比特位的 0 或 1 编码，来代替任意一个点的二维空间坐标 了 。假设 x 和 y 是两个浮点数，各 4 个字节，那它们一共是 8 个字节。如果将 8 个字节的坐标用 1 个比特位来表示，就能达到压缩存储空间的目的了。前面说的用聚类 ID 代替具体的向量来进行压缩，也是同样的原理。
乘积：指的是高维空间可以看作是由多个低维空间相乘得到的。
还是以二维空间
乘积量化的好处：
将高维空间分解成多个低维空间的乘积的好处在于，它能降低数据的存储量。比如说，二维空间是由一维的 x 轴和 y 轴相乘得到。x 轴上有 4 个点 x1 到 x4，y 轴上有 4 个点 y1 到 y4，这四个点的交叉乘积，会在二维空间形成 16 个点。但是，如果我们仅存储一维空间中，x 轴和 y 轴的各 4 个点，一共只需要存储 8 个一维的点，这会比存储 16 个二维的点更节省空间。
总结来说，对向量进行乘积量化，其实就是将向量的高维空间看成是多个子空间的乘积，然后针对每个子空间，再用聚类技术分成多个区域。最后，给每个区域生成一个唯一编码，也就是聚类 ID。
- 乘积量化压缩样本向量的具体操作过程
以1024 维的浮点数向量为样本向量 为例：
- 将它分为 4 段，这样每一段就都是一个 256 维的浮点向量；
- 在每一段的 256 维的空间里，用聚类算法将这 256 维空间再划分为 256 个聚类；
- 用 1 至 256 作为 ID，来为这 256 个聚类中心编号。这样，我们就得到了 256 4 共 1024 个聚类中心，每个聚类中心都是一个 256 维的浮点数向量（256 4 字节 = 1024 字节）；
- 储存这 1024 个聚类中心向量。
这样，对于这个空间中的每个向量，就不需要再精确记录它在每一维上的权重了。我们只需要将每个向量都分为四段，让每段子向量都根据聚类算法找到所属的聚类，然后用它所属聚类的 ID 来表示这段子向量就可以了。
因为聚类 ID 是从 1 到 256 的，所以只需要 8 个比特位就可以表示这个聚类 ID 了。由于完整的样本向量有四段，因此用 4 个聚类 ID 就可以表示一个完整的样本向量了，也就一共只需要 32 个比特位。因此，一个 1024 维的原始浮点数向量（共 1024 * 4 字节）使用乘积量化压缩后，存储空间变为了 32 个比特位，空间使用只有原来的 1/1024。存储空间被大幅降低之后，所有的样本向量就有可能都被加载到内存中了。
计算 查询向量 和 压缩样本向量的距离（相似性）
这样，我们就得到了一个压缩后的样本向量，它是一个 32 个比特位的向量。这个时候，如果要我们查询一个新向量和样本向量之间的距离，也就是它们之间的相似性，我们该怎么做呢？这里我要强调一下，一般来说，要查询的新向量都是一个未被压缩过的向量。也就是说在我们的例子中，它是一个 1024 维的浮点向量。
具体步骤如下：
- 首先，我们在对所有样本点生成聚类时，需要记录下聚类中心向量的向量值，作为后面计算距离的依据。由于 1024 维向量会分成 4 段，每段有 256 个聚类。因此，共需要存储 1024 个聚类中所有中心向量的数据。
- 然后，对于查询向量，我们也将它分为 4 段，每段也是一个 256 维的向量。对于查询向量的每一段子向量，我们要分别计算它和之前存储的对应的 256 个聚类中心向量的距离，并用一张距离表存下来。由于有 4 段，因此一共有 4 个距离表。
- 当计算查询向量和样本向量的距离时，我们将查询向量和样本向量都分为 4 段子空间。然后分别计算出每段子空间中，查询子向量和样本子向量的距离。这时，我们可以用聚类中心向量代替样本子向量。这样，求查询子向量和样本子向量的距离，就转换为求查询子向量和对应的聚类中心向量的距离。那我们只需要将样本子向量的聚类 ID 作为 key 去查距离表，就能在 O(1) 的时间代价内知道这个距离了。
- 将得到的四段距离按欧氏距离的方式计算，合并起来，即可得到查询向量和样本向量的距离，距离计算公式：
以上，就是计算查询向量和样本向量之间距离的过程了。原本两个高维向量的复杂的距离计算，被 4 次 O(1) 时间代价的查表操作代替之后，就变成了常数级的时间代价。因此，在对压缩后的样本向量进行相似查找的时候，即便是使用遍历的方式进行计算，时间代价也会减少许多。
而计算查询向量到每个聚类中心的距离，也只需要在查询开始的时候计算一次，就可以生成 1024 个距离表，在后面对比每个样本向量时，这个对比表就可以反复使用了。
对乘积量化进行倒排索引
尽管使用乘积量化的方案，已经可以用很低的代价来遍历所有的样本向量，计算每个样本向量和查询向量的距离了。但是依然能用更高效的检索技术代替遍历，来提高检索效率。因此，可以将聚类、乘积量化和倒排索引综合使用，让整体检索更高效。
- 建立索引的过程
- 使用 K-Means 聚类，将所有的样本向量分为 1024 个聚类，以聚类 ID 为 Key 建立倒排索引；
- 对于每个聚类中的样本向量，计算它们和聚类中心的差值，得到新的向量。你也可以认为这是以聚类中心作为原点重新建立向量空间，然后更新该聚类中的每个样本向量；
- 使用乘积量化的方式，压缩存储每个聚类中新的样本向量。
这样，我们就同时结合了聚类、乘积量化和倒排索引的检索技术，使得我们能在压缩向量节省存储空间的同时，也通过快速减少检索空间的方式，提高了检索效率。通过这样的组合技术，我们能解决大量的图片检索问题。比如说，以图搜图、拍照识物，人脸识别等等。
实际上，除了图像检索领域，在文章推荐、商品推荐等推荐领域中，我们也都可以用类似的检索技术，来快速返回大量的结果。尤其是随着 AI 技术的发展，越来越多的对象需要用特征向量来表示。所以，针对这些对象的检索问题，其实都会转换为高维空间的近似检索问题，那今天讲的内容就完全可以派上用场了。
总结
主要介绍了在高维向量空间中实现近似最邻近检索的方法。相对于局部敏感哈希，使用聚类技术能实现更灵活的分类能力，并且聚类技术还支持层次聚类，它能更快速地划分检索空间。
此外，对于高维的向量检索，如何优化存储空间也是我们需要考虑的一个问题。这个时候，可以使用乘积量化的方法来压缩样本向量，让我们能在内存中运行向量检索的算法。
那为了进一步提高检索率和优化存储空间，我们还能将聚类技术、乘积量化和倒排索引技术结合使用。这也是目前图像检索和文章推荐等领域中，非常重要的设计思想和实现方案。
讨论
1. 为什么使用聚类中心向量来代替聚类中的样本向量，我们就可以达到节省存储空间的目的？
2. 如果二维空间中有 16 个点，它们是由 x 轴的 1、2、3、4 四个点，以及 y 轴的 1、2、3、4 四个点两两相乘组合成的。那么，对于二维空间中的这 16 个样本点，如果使用乘积量化的思路，你会怎么进行压缩存储？当我们新增了一个点 (17,17) 时，它的查询过程又是怎么样的？
若有收获，就点个赞吧
0 人点赞
