[Document Deduplication][1] MinHash

01-30

大規模數據集中的重複（完全重複或幾近重複）文本檢測有非常廣泛的應用場景，諸如網頁索引的排重，論文查重等等。這系列文章會介紹背後的部分技術。

假如現在我們手頭有兩個文本文檔（任何類型，網頁，論文，新聞）分別為D1, D2，我們要比較他們之間的相似度，應該如何比較？有很多種不同的方法[1]，其中一種比較方法是利用Jaccard Similarity Index，定義如下：

這個公式適用於比較兩個集合的相似度。我們可以把文檔D1，D2分別轉化成一個集合，然後套用這個公式算出相似度。

Shingling

這裡引出第一個關鍵概念Shingling，用於把一個文本文檔轉化成集合的表示形式。它的基本思路是採用sliding window。比如說，假如你的文本是abcdabd，那麼這段文本的2-shingles就是：

{"ab", "bc", "cd", "da", "bd"}

由於這是一個集合，所以「ab」只出現了一次，即使它的詞頻是2。這基本就是我們在NLP里說到的N-gram，只不過Context不一樣所以叫法也不一樣而已。

同樣的，除了在字母層面上應用sliding window之外，也可以在單詞層面上應用，這樣有助用捕捉高階層面的語義信息。比如你有一個網頁內容是：

<HTML><BODY>Hello World</BODY></HTML>

在單詞層面上求3-shingles就會變成

{"<HTML><BODY>", "<BODY>Hello", "Hello World", "World</BODY>", "</BODY></HTML>"}n

在實際應用中，我們會對集合中的每個元素進行哈希，轉化成一個整數存儲起來，因此最終得到的文檔的集合表示將會是一個整數的集合。如果我們假設哈希無衝突（也就是說每個Shingle跟整數的映射是一對一的）的話，那麼根據這個整數集合我們可以很方便的求出Jaccard Similarity。例子：

D1: {1, 2, 3, 500, 10000}nD2: {1, 2, 4, 600, 10000}nJaccard Index Similarity = 3 / 7n

MinHash as Jaccard Similarity Estimator

先上一個牛逼的定理（引理？）：

假如D1, D2是兩個集合，h(x)是任意一個哈希函數。假設沒有哈希衝突。
令 $x = min { h(d), forall d in D_1 }, y = min { h(d), forall d in D_2 }$
那麼 $Pr(x = y) = Jaccard(D_1, D_2)$

也就是說，隨便找個哈希函數，用這個哈希函數對集合元素哈希得到整數集合，從兩個哈希後的集合裡面各挑最小的一個整數出來，這個兩個整數相等的概率等於Jaccard Similarity。

那麼，再進一步的說，根據統計學裡面的大數定理，只要你找超多個不同的哈希函數，每個都算一下兩個集合哈希後的最小值是不是相等，然後你就可以用（能得到相等的哈希函數數量）/ （總哈希函數數量）去估計Jaccard Similarity了！

這也是實際應用中的做法，找k個哈希函數（k是一個自定義的參數，決定了Hash的緯度），然後把每個集合D轉化成k個哈希後最小值的表示。例子

D = {"Jon", "Snow", "Knows" "Nothing"}nh1(D) = {2, 34, 9, 100}nh1(D) = {33, 11, 2, 222}nh3(D) = {6, 666, 2333, 233333}n=> MinHash of D = [2, 2, 6]n

這個演算法還有一個變種：與其找k個不同的哈希函數，我們可以找一個哈希函數，但是取最小的k個值。更多細節可以參考[2]。

總結：這篇文章介紹了基本的演算法和概念，但是離實際應用還是有差距，因為這裡只介紹了如何進行兩兩比較。如果是一個非常大的數據集，那麼進行pair-wise的比對肯定是不現實的，如何才能做到快速搜索相似文檔呢？下一篇會講LSH，真正使得搜索變快，而LSH十分依賴於一個好的Hash Generation演算法，MinHash就是其中之一。

[1] 別的方法包括直接比較，詞頻比較，TF-IDF的比較，edit distance，等等

[2] MinHash - Wikipedia