algorithm - 将距离设置为 MinHashing 算法的相似性度量

Question

我目前正在使用 MinHashing 技术进行文档聚类。但是，我没有得到想要的结果，因为 MinHash 是对 Jaccard similarity 的粗略估计，它不符合我的要求。

这是我的场景:

我有大量的书籍，如果将单个页面作为查询给出，我需要找到从中获取该页面的相应书籍。限制是，我有整本书的特征，不可能逐页获取书籍的特征。在这种情况下，如果书太大，Jaccard 相似性会给出较差的结果。我真正想要的是查询页面和书籍之间的距离(反之亦然)。即:

给定 2 组 A、B:我想要从 A 到 B 的距离，

dis(A->B) =  (A & B)/A

是否有相似的距离度量给出从集合 A 到集合 B 的距离。此外，是否仍然可以使用具有这种相似性度量的 MinHashing 算法？

Answer 1

我们可以使用与 MinHash 算法类似的方法来估计您提出的距离函数。

对于一些哈希函数 h(x) , 计算 h 的最小值在 A和 B .表示这些值 h_min(A)和 h_min(B) . MinHash 算法依赖于 h_min(A) = h_min(B) 的概率是(A & B) / (A | B) .我们可以观察到 h_min(A) <= h_min(B) 的概率是A / (A | B) .然后我们可以计算 (A & B) / A作为这两个概率的比率。

就像在常规的 MinHash 算法中一样，我们可以通过重复采样来近似这些概率，直到达到所需的方差。