聚类算法和局部敏感哈希的区别？
检索图片和检索文章一样，我们首先需要用向量空间模型将图片表示出来，也就是将一个图片对象转化为高维空间中的一个点。这样图片检索问题就又变成了我们熟悉的高维空间的相似检索问题。
如果我们把每个图片中的像素点看作一个维度，把像素点的 RGB 值作为该维度上的值，那一张图片的维度会是百万级别的。这么高的维度，检索起来会非常复杂，我们该怎么处理呢？我们可以像提取文章关键词一样，对图片进行特征提取来压缩维度。
要想实现图片特征提取，我们有很多种深度学习的方法可以选择。比如，使用卷积神经网络（CNN）提取图片特征。这样，用一个 512 到 1024 维度的向量空间模型，我们就可以很好地描述图像了，但这依然是一个非常高的维度空间。因此，我们仍然需要使用一些近似最邻近检索技术来加速检索过程。
一种常用的近似最邻近检索方法，是使用局部敏感哈希对高维数据进行降维处理，将高维空间的点划到有限的区域中。这样，通过判断要查询的点所在的区域，我们就能快速取出这个区域的所有候选集了。
不过，在上一讲中我们也提到，局部敏感哈希由于哈希函数构造相对比较简单，往往更适合计算字面上的相似性（表面特征的相似性），而不是语义上的相似性（本质上的相似性）。这怎么理解呢？举个例子，即便是面对同一种花，不同的人在不同的地点拍出来的照片，在角度、背景、花的形状上也会有比较大的差异。也就是说，这两张图片的表面特征其实差异很大，这让我们没办法利用局部敏感哈希，来合理评估它们的相似度。
而且，局部敏感哈希其实是一种粒度很粗的非精准检索方案。以 SimHash 为例，它能将上百万的高维空间压缩到 64 位的比特位中，这自然也会损失不少的精确性。
因此，更常见的一种方案，是使用聚类算法来划分空间。和简单的局部敏感哈希算法相比，聚类算法能将空间中的点更灵活地划分成多个类，并且保留了向量的高维度，使得我们可以更准确地计算向量间的距离。好的聚类算法要保证类内的点足够接近，不同类之间的距离足够大。一种常见的聚类算法是 K-Means 算法（K- 平均算法）。
K-Means 聚类算法的思想其实很「朴素」，它将所有的点划分为 k 个类，每个类都有一个 类中心向量。在构建聚类的时候，我们希望每个类内的点都是紧密靠近类中心的。用严谨的数学语言来说，K-Means 聚类算法的优化目标是，类内的点到类中心的距离均值总和最短。因此，K-Means 聚类算法具体的计算步骤如下:
- 随机选择 k 个节点，作为初始的 k 个聚类的中心；
- 针对所有的节点，计算它们和 k 个聚类中心的距离，将节点归入离它最近的类中；
- 针对 k 个类，统计每个类内节点的向量均值，作为每个类的新的中心向量；
- 重复第 2 步和第 3 步，重新计算每个节点和新的类中心的距离，将节点再次划分到最近的类中，然后再更新类的中心节点向量。经过多次迭代，直到节点分类不再变化，或者迭代次数达到上限，我们停止算法。
以上，就是 K-Means 聚类算法的计算过程了，那使用聚类算法代替了局部敏感哈希以后，我们该怎么进行相似检索呢？
