對于web網頁去重的應用，如抄襲、鏡像等，通過將網頁表示為字符k-grams（或者k-shingles）的集合，把網頁去重的問題轉化為找到這些集合的交集。使用傳統的方法存儲這些巨大的集合以及計算它們之間的相似性顯然是不夠的，為此，對集合按某種方式進行壓縮，利用壓縮后的集合推斷原來集合的相似性。

?

Jaccard相似性：只關注集合之間的交集大小。

集合S和T的Jaccard相似性定義如下：

?

比如S = { a, b, c, d } and T = { c, d, e, f } , 那么SIM(S, T )= 2/6。

?

k-Shingles

一篇文檔可以看成是一個字符串，文檔的k-shingle為在該文檔中長度為k的所有子串。任意一篇文檔都可以表示為k-shingles的集合，比如“A document is a string of characters”這句話的所有3-shingles為{ ”A d”, ”do”, ”doc”, ”ocu”, ”cum”, ”ume”, ”men”, ”ent”, . . . , ”ers” }。如果k非常小，那么k個字符的序列會出現在大多數的文檔中，如k=1，許多文檔都有相同的字符，幾乎所有的文檔都有很高的相似性。如果k應該足夠大，那么對于給定的shingle出現在不同的文檔中的概率是非常低的。比如這兩個單詞“ document”和“monument”：

SIM( { d, o, c, u, m, e, n, t } , { m, o,n, u, m, e, n, t } ) = 6/8

SIM( { doc, ocu, cum, ume, men, ent } ,{mon, onu, num, ume, men, ent } ) = 3/9

?

對于電子郵件的語料庫，k=5就足夠了，因為在電子郵件中出現的英文字母和空白字符有27個，那么就會有27⁵ = 14 348 907 shingles，一般電子郵件的長度不會超過14 million個字符，所以k=5是一個合理的值。

?

Hashing Shingles

?

不使用子串直接作為shingles，而是使用hash函數將長度為k的字符串映射到哈希桶中，哈希桶的編號作為shingle，則表示文檔的集合轉化為含有哈希桶編號的集合。一篇文檔的9-shingle可以映射到[0,2³² - 1]。如果使用4-shingles，許多4字節的序列在一般的文檔中是找不到的，不同的shingles數量大約有20⁴=160 000，遠小于2³²。

?

Minhash技術

?

由于shingles的集合非常大，即使把它們映射hash成4字節，所需要的空間仍然是一篇文檔所占空間的4倍。對于million級別的文檔，就不能將所有shingle集合加載到內存。對于占用空間大集合，我們將其替換為占用空間較小的簽名（signatures）表示，并且signatures在一定程度上保留集合的相似性信息。

?

集合的特征矩陣

矩陣的列對應集合，行對應從文檔中（或者universal set）獲取到的元素，如果r行是c列的集合元素，就將矩陣的r行c列設置為1，否則為0。例如，universal set ：{ a, b, c, d, e }，S₁ = { a, d } , S₂ = { c } , S₃ = {b, d, e } , S₄ = { a, c, d } ，特征矩陣如下：

?

我們想要的signatures是通過對特征矩陣的一系列minhash計算所得到的，任何一列的minhash值為經過置換后第一個為1的元素對應行號（行號從0開始）。有點拗口，我們對上面的特征矩陣變換順序（?beadc?），得到新的特征矩陣：

上圖中特征矩陣的minhash值：h(S₁) = 2 (a)， h(S₂) =4 (c)， h(S₃) = 0 (b) 和h(S₄) = 2(a)。

?

Minhash和Jaccard相似性有重要的聯系：如果兩個集合S1和S2的Jaccard相似性是一樣的，那么以很高的概率保證它們的minhash值也是相等的。

?

計算signatures的步驟：

1>????對特征矩陣M做n次隨機置換；

2>????根據這些置換確定minhash函數h₁，h₂，… ,h_n；

3>????用列表示集合S，構建S的minhash的signature，(h₁(S), h₂ (S), . . . , h_n (S))；

4>????有上述步驟即可構建M的signature矩陣，即M的第i列被替換為第i列的minhash signature。

注意：signature矩陣和特征矩陣M有相同的列數，但是只有n行，要比M矩陣小的多。

?

顯然對一個很大的特征矩陣做置換是不可行的，但是可以通過隨機hash函數模擬隨機置換效果，將行號映射到桶的編號。具體方案為：隨機選擇n個hash函數h₁,h₂,…,h_n，SIG(i,c)為signature矩陣的元素，是由第i個hash函數和M的第c列確定：

SIG(i, c) = min { h_i(r) : forsuch r that c has 1 in row r }

?

舉例說明：

?

計算hash值（置換順序）：

?

根據公式SIG(i, c) = min { h_i(r) : forsuch r that c has 1 in row r }，計算signature：

通過signature矩陣估計Jaccard相似性：

SIM(S₁, S₂) = 0?? SIM(S₁, S₃) = 1/2?? SIM(S₁, S₄) = 1

而實際的相似性為：

SIM(S₁, S₂) = 0?? SIM(S₁, S₃) = 1/4?? SIM(S₁, S₄) = 2/3

參考資料

Finding similar items?

?

總結

以上是生活随笔為你收集整理的k-shingles与minhash技术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。