设置距离作为MinHashing算法的相似性度量

我目前正在使用MinHashing技术进行文档聚类。但是，由于MinHash是Jaccard similarity的粗略估计，因此我没有得到期望的结果，并且它不适合我的要求。设置距离作为MinHashing算法的相似性度量

这是我的情景：

我有一个巨大的一套书，如果一个页面是作为一个查询，我需要找到从自获得该页面对应的书籍。限制是，我拥有整本书的功能，并且不可能获得书籍的逐页功能。在这种情况下，如果书太大，Jaccard的相似性会导致较差的结果。我真正想要的是查询页面和书籍之间的距离（反之亦然）。那就是：

由于2台A，B：我想从A到B的距离，

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

是否有给出了从集合A的距离设置B.而且类似的距离度量，它仍然是这种相似性度量可以使用MinHashing算法吗？

来源

2015-08-16 Maggie

你能提供你的实施细节吗？你使用了哪些哈希函数？他们有多少人？ –

我正在使用这个MinHash实现512个排列。 https://github.com/ekzhu/datasketch – Maggie

[也发布在CS.SE上]（http://cs.stackexchange.com/q/45320/755）。请[不要在多个网站上发布相同的问题]（http://meta.stackexchange.com/q/64068）。每个社区都应该诚实地回答问题，不要浪费任何人的时间。 –

我们可以使用与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算法一样，我们可以通过重复采样来近似这些概率，直到达到期望的方差。

来源

2015-08-17 08:14:27 augurar

设置距离作为MinHashing算法的相似性度量

回答

相关问题