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 算法类似的方法来估计您提出的距离函数。

对于某些散列函数，计算over和h(x)的最小值。表示这些值和。MinHash 算法依赖于这样一个事实，即. 我们可以观察到的概率是。然后我们可以计算这两个概率的比率。hABh_min(A)h_min(B)h_min(A) = h_min(B)(A & B) / (A | B)h_min(A) <= h_min(B)A / (A | B)(A & B) / A

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