在数据挖掘任务中都涉及了海量数据的相似度计算，例如检索文档的相似度，用户之间的相似度等。这些数据通常维度很高，用 one-hot 编码的文档数据维度等于字典的大小，在数据量大，数据维度高的情况下，计算对象两两之间的相似度需要耗费大量的时间。本文介绍两种近似算法 Min Hashing (最小哈希) 和 Locality Sensitive Hashing (LSH，局部敏感哈希)，近似算法可以在牺牲部分精度下大大提升运行效率。

1.Min Hashing

假设给定两个文档 D1 和 D2，其特征向量采用 one-hot 编码，即如果一个位置为 1 则说明文档拥有对应的单词。

文档向量

我们可以用 Jaccard 系数计算两个向量的相似度，公式如下，A 和 B 是两个集合：

Jaccard 系数

Jaccard 系数是 A、B 交集的元素数量除以 A、B 并集的元素数量，因此上面的文档 D1、D2 相似度为 2/5。用 x 表示 A、B 共有的元素数量，y 表示 A、B 单独拥有的元素数量，则 Jaccard 系数可以改写为下面的公式：

Jaccard 系数

Min Hashing 是一种近似计算 Jaccard 系数的方法，主要的步骤如下：

对向量D1、D2 的维度进行 m 次随机排列找到重新排列后 D1、D2 第一个非 0 行的索引，用函数 h(D1)、h(D2) 表示

执行 m 次随机排列后，可以得到 D1、D2 的新特征向量，如下：

Min Hashing 后的特征向量

这一过程如下图所示，下图中 m=3：

Min Hashing 过程示例

得到新的特征向量 Sig(D1) 和 Sig(D2) 后可以计算每一个位置上相同 (即第一个非 0 行索引相同) 的概率 P=1/3，这个概率就是 Jaccard 系数的近似值。这主要是根据下面的原理：

Min Hashing 原理

这个原理可以证明，重新排列后两个向量 D1、D2 后，在每一个维度存在三种可能：

D1、D2 在这一个维度都是 1，对应了 Jaccard 公式中的 xD1、D2 只有一个向量在这一个维度是 1，对应了 Jaccard 公式中的 yD1、D2 在这一维度都是 0

Min Hashing 得到的新向量 Sig(D1) 是 D1 第一个不为 0 的行索引。则 Sig(D1) 和 Sig(D2) 第一个非 0 行索引相同的概率为 x/(x+y) 即 Jaccard 系数公式。

如果采用全排列 (即考虑所有的排列情况) 则 Min Hashing 可以得到准确的 Jaccard 值，但是在实际使用时为了提升效率，通常采用 m 次排列，可以将原向量转为长度为 m 的新向量。

2.LSH

Min Hashing 可以将原始的特征向量转为更低维度的 Sig 向量，减少计算两个对象之间相似度的时间。但是如果对象的数量 N 很大，计算所有对象之间相似度需要执行的次数为 O(N^2)，仍然需要耗费大量时间。

LSH 算法 (Locality Sensitive Hashing，局部敏感哈希) 的核心思想是先把数据粗略地进行分桶，使相似度高的数据尽可能出现在同一个桶内。分到同一个桶的数据互相视为 candidate 数据，后续计算相似度时只计算数据和其 candidate 数据的相似度 (即出现在同一个桶内的)。

LSH 先将 Min Hashing 得到的 Sig 向量划分为 b 段 (Bands)，每段的长度为 r。下面是将 Sig 向量分段的例子，其中每一列是一整个 Sig 向量，向量被划分为 4 个 Band (b=4)，每个 Band 长度为 3 (r=3)。

Sig 向量分段

然后利用哈希函数将每一个 Band 中的向量 (r 维向量) 分配到不同的桶里面，哈希函数的取值 (桶数量) 应该尽可能地多，使两个向量只在完全相同时才会有大概率被分到同一个桶里面。分桶的示意图如下：

LSH 算法分桶的过程

在上面的分桶过程中，每一个 Band 都使用同一个哈希函数，但是采用不同的桶。Band 1 的桶在顶部，Band 4 的桶在底部。在 Band 1 中，第 1 个数据和第 9 个数据分到了同一个桶里 (红色)，因此数据 1 和数据 9 互为 candidate 数据，即两个数据只要有一个 Band 被分到同一个桶，就是 candidate。

因为 LSH 分桶是近似的算法，因此会存在一些误差。我们希望可以减少 LSH 的 False Positive (相似度低的数据分到同一个桶) 和 False Negative (相似度高的数据没有分到同一个桶)。为了减少误差，首先需要计算出两个数据被分到同一个桶的概率。

假设有两个数据，他们真实的 Jaccard 系数为 s，LSH 算法把他们的 Sig 向量划分为 b 段，每段长度为 r。在介绍 Min Hashing 算法时，我们知道 Sig 向量保存的是重排列后第一个非 0 行的索引，因此两个数据的 Sig 向量在某一维度上取值相同的概率为 Jaccard 系数，即 s。则我们可以计算出这两个数据至少在一个 Band 里被分到同一个桶里面的概率：

分桶概率计算

上面公式的最后一行即为两个数据至少在一个 Band 里被分到同一个桶里的概率 P，给定 b 和 r，可以画出概率 P 随 Jaccard 系数 s 变化的图像，称为 S-curve，如下图所示。

S-curve

可以看到当 Jaccard 系数变得足够大的时候，两个数据被分到同一个桶的概率会大大增加 (接近 1)。因此一般使用的时候要事先设置好一个 Jaccard 系数的阈值 s，然后调整 b 和 r，使得相似度大于阈值 s 时，两个数据被分到同一个桶的概率最大。

3.参考文献

Mining of Massive Datasets 地址：