設置距離作爲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算法的相似性度量

回答

相關問題