计算Minhash的证明

Question

我正在阅读MinHash技术来估计两个集合之间的相似度:给定集合A和B，h是散列函数，hmin( S )是集合S的最小散列，即hmin(S)=s中s的min(h(S))。我们有这样的等式：

p(hmin(A)=hmin(B))=|A∩B| / |A∪B|

这意味着A的最小散列等于B的最小散列的概率是A和B的Jaccard相似性。

我试着证明上面的等式，并提出我自己的证明:对于a和b，使得h(a)=hmin(A)∈h(b)=hmin(B)。因此，如果hmin(A)=hmin(B)，则h(a)=h(b)。假设散列函数h可以将关键字散列为不同的散列值，因此h(a)=h(b)当且仅当a=b，其概率为|A∩B| / |A∪B|。然而，我的证明并不完整，因为哈希函数可以为不同的键返回相同的值。因此，我请求您帮助找到一个无论哈希函数如何都可以应用的证明。

Answer 1

我不能确定你确切的问题是什么。

但是，如果您正在寻找一种方法来证明：

A的最小散列等于B的最小散列的

概率是A和B的Jaccard相似度。

试着看看Mining of Massive Datasets, by Anand Rajaraman and Jeff Ullman的3.3.3节

Answer 2

可以将散列函数看作是提供(A∪B)的随机排列的一种手段。现在，考虑一下这个排列。

使用您选择的排列p，将(A∪B)中的每个可能元素作为表中的一行。和两列A和B，如下所示：

A = {1, 3, 5, 6}
B = {2, 3, 4, 6}
p = {5, 6, 1, 2, 4, 3}

下表：

   A  B
5  1  0
6  1  1
1  1  0
2  0  1
4  0  1
3  1  1

只有两种类型的行，X:其中A和B是1。Y:其中A != B

总共有(A，∪，B)行。但是只有Y类型的(A∩B)行。第一行是Y类型之一的可能性是Y/(X+Y)。或者Prhmin (A ) = hmin(B) =(A∩B)/(A∪B)。

这正是Nilesh linked这本书所说的，但我试图用另一个例子来解释。

Answer 3

“不管哈希函数是什么”，都无法证明这一点。只要考虑一下:你可以使用一个非常糟糕的散列函数，它会产生非常频繁的冲突(比如简单地将所有值进行二进制a运算)。MinHash将不再近似于Jaccard相似性，但会报告更高的相似性。我所见过的MinHash的证据都假设哈希冲突将是非常罕见的，甚至可以忽略不计。