0

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

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

这意味着A的最小哈希等于B的最小哈希的概率是A和B的Jaccard相似度。

我试图证明上述等式并提出我自己的证明：对于 a∈A 和 b∈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|。但是，我的证明并不完整，因为哈希函数可以为不同的键返回相同的值。所以，我请求你帮助找到一个可以应用的证明，不管散列函数。

4

4 回答 4

0

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

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

A的最小哈希等于B的最小哈希的概率是A和B的Jaccard相似度。

尝试查看Anand Rajaraman 和 Jeff Ullman 的大规模数据集挖掘的第 3.3.3 节

于 2013-05-10T21:00:39.540 回答
0

将散列函数视为提供 (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) 行。但只有 (A ∩ B) 行是 Y 类型。第一行是 Y 类型之一的机会是 Y/(X+Y)。或 Pr[hmin(A) = hmin(B)] = (A ∩ B)/(A ∪ B)。

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

于 2015-12-08T00:30:18.620 回答
0

“无论散列函数如何”都无法证明这一点。试想一下：您可以使用一个非常糟糕的哈希函数，它会产生极其频繁的冲突（例如简单地将所有值二进制与运算在一起）。MinHash 将不再近似 Jaccard 相似性，但会报告更高的相似性。我所见过的 MinHash 证明假设哈希冲突将非常罕见以至于微不足道。

于 2018-02-19T04:20:34.557 回答
0

假设碰撞永远不会发生，或者可以忽略不计。你只需为你的哈希选择一个长度，这样它们碰撞的机会就会变得任意小。本文描述了各种项目数量和散列大小的界限。https://en.wikipedia.org/wiki/Birthday_attack

于 2018-11-19T21:14:59.577 回答