MinHash算法-复杂度待整理

1 MinHash简介

传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上相当于伪随机数产生算法。传统hash算法产生的两个签名，如果相等，说明原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别极大。从这个意义上来说，要设计一个hash算法，对相似的内容产生的签名也相近，是更为艰难的任务，因为它的签名值除了提供原始内容是否相等的信息外，还能额外提供不相等的原始内容的差异程度的信息。

MinHash[1]也是LSH的一种，可以用来快速估算两个集合的相似度。MinHash由Andrei Broder提出，最初用于在搜索引擎中检测重复网页。它也可以应用于大规模聚类问题。

2 MinHash原理

Jaccard index

Jaccard index[2]是用来计算相似性，也就是距离的一种度量标准。假如有集合A、B，那么

J(A,B)=（A intersection B）/ （A union B)

也就是说，集合A,B的Jaccard系数等于A,B中共同拥有的元素数与A,B总共拥有的元素数的比例。很显然，Jaccard系数值区间为[0,1]。

MinHash

先定义几个符号术语：

h(x): 把x映射成一个整数的哈希函数。

hmin(S)：集合S中的元素经过h(x)哈希后，具有最小哈希值的元素。

那么对集合A、B，hmin(A) = hmin(B)成立的条件是A ∪ B 中具有最小哈希值的元素也在 ∩ B中。这里

有一个假设，h(x)是一个良好的哈希函数，它具有很好的均匀性，能够把不同元素映射成不同的整数。

所以有，Pr[hmin(A) = hmin(B)] = J(A,B)，即集合A和B的相似度为集合A、B经过hash后最小哈希值相

等的概率。

有了上面的结论，我们便可以根据MinHash来计算两个集合的相似度了。一般有两种方法：

第一种：使用多个hash函数

为了计算集合A、B具有最小哈希值的概率，我们可以选择一定数量的hash函数，比如K个。然后用这K个hash函数分别对集合A、B求哈希值，对

每个集合都得到K个最小值。比如Min(A)k={a1,a2,...,ak}，Min(B)k={b1,b2,...,bk}。

那么，集合A、B的相似度为|Min(A)k ∩ Min(B)k| / |Min(A)k ∪ Min(B)k|，即Min(A)k和Min(B)k中相同元素个数与总的元素个数的比例。

第二种：使用单个hash函数

第一种方法有一个很明显的缺陷，那就是计算复杂度高。使用单个hash函数是怎么解决这个问题的呢？请看：

前面我们定义过 hmin(S)为集合S中具有最小哈希值的一个元素，那么我们也可以定义hmink(S)为集合S中具有最小哈希值的K个元素。这样一来，

我们就只需要对每个集合求一次哈希，然后取最小的K个元素。计算两个集合A、B的相似度，就是集合A中最小的K个元素与集合B中最小的K个元素

的交集个数与并集个数的比例。