MinHash

参考链接：MinHash-WiKi

问题

MinHash 算法和 Bloom Filter 一样，利用哈希函数的随机性从概率上快速地解决问题，它试图解决的问题是：集合的相似性，给定两个含有元素的集合，它们有多相似。相似性度量使用 Jaccard similarity coefficient ：

$\mathbf{Jaccard\ similarity}(A,B)=\frac{\mid A \cap B \mid}{\mid A \cup B \mid}$

当两个集合不相交时，此值为 0；当它们相等时，此值为 1；否则严格在 0 和 1 之间。当 Jaccard 指数接近于 1 时，两个集合更相似（即具有较多共同成员）。MinHash 的目标是快速估计 J(A,B)，而无需显式计算交集和并集。

将 $h_{min}(S)$ 定义为集合 S 中具有最小哈希值的成员 $x$.
将 $h_{min}$ 应用于集合 A 和 B，并假设没有哈希冲突，我们可以看到，当且仅当 $A\cup B$ 中具有最小哈希值的元素位于交集 $A \cap B$ 中时，有$h_{min}(A) = h_{min}(B)$。这种情况成立的概率正好是 Jaccard 系数，因此：

$\operatorname{Pr}\left[h_{\min }(A)=h_{\min }(B)\right]=J(A, B)$

k-hash MinHash

使用 k 个 hash 函数的 MinHash 是经典表示，也很优雅。其做法是：对 A 和 B 中的每个元素进行哈希，并查看每个集合中最小哈希值。事实证明，这两个哈希相等的概率恰好是这两个集合的 Jaccard 相似度。注意，为了从一个概率样本中近似估计该概率，需要大量的样本。因此，在这个版本的 MinHash 中，需要使用 k 个哈希函数得到 k 组 $(h_{min}(A), h_{min}(B))$，如果其中有 y 组表示的最小哈希值相等，用 $y/k$ 来估计集合的相似度。

举例子说明，如果 A 和 B 是相同的，那么它们的最小哈希显然是相同的。如果它们是不相交的，并且假设没有哈希冲突，那么它们的最小哈希显然会不同。以 A 包含 B 并且大小为其两倍为例。那么很容易理解 B 的最小哈希有 50% 的机会成为 A 的最小哈希。

这个版本中，需要计算每个元素的 k 个不同哈希值，并且最后计算出概率。此外，该技术的误差为 $1/\sqrt(k)$ （级别），达到 10%误差水平需要 100 个哈希函数，1%误差需要 10000 个哈希函数。

one-hash MinHash

做法是：计算每个元素的哈希值，并将集合中的最小的 k 个哈希值存储起来，集合中最小的 k 个哈希值也用做该集合的签名，对应的 k 个元素记作 $h_{(k)}(S)$。然后根据两个签名对应集合来计算 Jaccard 相似度，期望误差界限与上面的版本相同。时间复杂度为 $O(n\log k)$ ，空间复杂度为 $O(k)$ 。

对于两个集合 A,B 来说：

$\begin{aligned} X &=h_{(k)}\left(h_{(k)}(A) \cup h_{(k)}(B)\right)=h_{(k)}(A \cup B)\\ Y &=X \cap h_{(k)}(A) \cap h_{(k)}(B) \\ J &\approx \frac{ |Y| }{k} \end{aligned}$

• 其中集合 $|Y|$ 就是：两个签名集合并集中最小的 k 个元素，位于其交集中的元素个数
• (有的版本实现中，简单地直接计算两个签名集合的 Jaccard 系数作为原始集合 Jaccard 系数的估计值)

说明：Min-wise independent hash functions

对于上述的哈希函数，需要具有最小值独立性，即对于任意集合 S，集合 S 中的元素经过哈希后得到的最小值是随机的，与集合 S 的具体元素无关。如通过随机置换实现，或者假设其具有伪随机性。

链接

• On the resemblance and containment of documents, Broder, 1997.pdf
• Dealing with Massive Data, Lecture1: Duplicate Detection.pdf
• CS494 Lecture Notes - MinHash