王洪亞等

摘 要：MinHash作為位置敏感哈希（LSH）算法中的一種，可以用來快速估算兩個集合的相似度，查找網絡上的重復網頁或者相似新聞網頁，MinHash算法使用Jaccard相似度來度量對象的相似程度。本文針對MinHash算法在分布式平臺上的實現和性能表現進行分析和研究，給出了MinHash的分布式算法。最后通過具體的實驗，驗證了提出的MinHash算法在處理實際問題上的正確性和準確性。

關鍵詞：MinHash；分布式；算法實現

中圖分類號：TP311 文獻標識號：A 文章編號：2095-2163（2014）06-

Abstract： MinHash is a kind of Locality Sensitive Hashing algorithm （LSH）， which can be used to quickly estimate the similarity of two sets to find the？duplicate？web pages or the similar news pages on the web. This paper focuses on the MinHash implementations and Performance in distributed platform， and devise the distributed MinHash algorithm. To verify the soundness of the new version， the paper conducts extensive experiments with several real datasets. Experimental results confirm the validity and accuracy of the proposed implementation.

Keywords： MinHash； Distributed； Algorithm Implementation

0 引 言

近年來，在很多應用設計中，面對和需要處理的往往是具有很高維度的，因而大數據研究領域也隨之創(chuàng)建與興起。怎樣海量的高維數據集合中快速尋獲與某一數據最相似（距離最近）的一個或多個數據即成為該領域的重點問題。如果是低維的小數據集，通過線性查找（Linear Search）就可以輕松解決；但如果是對一個海量的高維數據集采用線性查找匹配，時間開銷必然巨大，針對此一問題，就需要采用諸如索引的技術來加快查找過程，通?？蓪⑵浞Q為最近鄰查找（Nearest Neighbor Search）[1]。最近鄰查找是在很多重要實際應用中發(fā)揮了優(yōu)勢作用的經典技術。迄至目前為止，隨著數據量的不斷增大，數據維度的日漸增加，更多的新算法正陸續(xù)提出以用于解決在各類背景條件下出現的最近鄰查找問題。

在現實研究進程中，隨著精確最近鄰查找問題解決難度的增加，人們發(fā)現近似最近鄰查找的結果也能滿足實際的應用需求[2]，而將其與精確最近鄰查找相比，又能在效率上獲得很大的提高，因此近似最近鄰查找問題又相應地成為研發(fā)熱點。近似最近鄰查找是以犧牲查找精度為代價來換取查找效率的提高，從而達到將查找效率與查找結果折衷平衡的目的。位置敏感哈希（LSH）即可用于解決近似最近鄰查找問題，并在實際應用中獲得了顯著突出的效果，而且堪稱是解決維度災難的一個有效方法。LSH方法能夠以概率方式在保證一定查詢精確度的前提下實現快速的近似最近鄰查詢[1]。MinHash也是LSH 算法中的一種，多是用來快速估算兩個集合的相似，其中通過使用Jaccard相似度來度量對象的相似程度。具體來說，MinHash是由Andrei Broder首次提出，可用于在搜索引擎中檢測重復網頁或者查找相似新聞網頁以及文章[2，3]，MinHash算法的實際效果與其重要參數k、L密切相關，這些參數的設定與數據本身的性質是直接對應的。所以為了實現MinHash算法，對各種不同類型的高維數據集與MinHash算法的參數之間聯系而開展研究將具有重要的現實及理論意義。

基于上述討論，本文主要貢獻如下：

（1）研究分析MinHash算法在分布式開源平臺中應用的可行性，并發(fā)現MinHash算法在分布式平臺上將比非分布式平臺具有更大優(yōu)勢，尤其是當處理大規(guī)模數據集時。

（2）給出了MinHash算法的新的分布式模型，實現了分布式平臺中MinHash算法，并通過具體實驗進行了驗證以及說明。

1相關工作

LSH由Indyk等人最初提出用來解決近似最近鄰查找問題，其基本思想是使數據集中距離相近的點生成相同的哈希鍵值，也就是能哈希到一個桶中，而對數據集中距離較遠的點將生成不同的鍵值，從而哈希到不同的桶中[1]。經過實踐已經證明，LSH算法在空間占用以及時間查詢效率上較其他算法都具有明顯優(yōu)勢地位[4]。LSH方法就是以概率方式在保證一定查詢精確度的前提下實現快速的近似最近鄰查詢，并通過查全率和準確率而換取了空間或時間效率。

LSH的應用場景眾多，凡是需要進行大量數據之間的相似度（或距離）計算的場合都可以使用LSH來加快查找匹配速度，具體例示則如查找網絡上的重復網頁或者查找相似新聞網頁以及文章這些具體研究即需要LSH算法族中的MinHash來實現與完成。MinHash算法作為該算法族中的一個常用方法，其最基本應用即在于搜索引擎中檢測重復網頁等。

基于以上介紹，本文將針對MinHash算法在分布式平臺上的設計實現和性能方面表現進行分析與研究。并且由于位置敏感哈希（LSH）在高維數據空間近鄰查找性能的高效表現，該算法在實際研究中得到了眾多應用。只是目前全部已有算法的性能分析都是基于理論分析模型來實現估算，卻少有學者致力于理論分析模型在分布式平臺上的應用研究。

2 MinHash算法原理

LSH提供了一種在海量的高維數據集中查找與查詢數據點（Query data point）近似最相鄰的某個或某些數據點的有效方法。LSH并非一定能夠找到與查詢點最相鄰的數據，而是在盡量減少需要匹配的數據點個數的同時，卻能保證查找到最近鄰數據點的概率較大。MinHash算法則使用Jaccard相似度作為度量標準，可用于在搜索引擎中檢測重復網頁等。下面分別給出LSH算法和MinHash算法的具體論述和分析。

給定兩個有限集合A和B，這兩個集合具有相同MinHash簽名的概率定義可描述為如下函數：

以上函數即稱為MinHash函數。

MinHash算法的實現過程中，一般性做法就是對目標項進行多次哈希處理，使得相似項與不相似項相較而言，更具可能哈希到同一桶中。同時再將至少有一次哈希到同一桶中的文檔對視為候選對，而只需檢查這些候選對之間的相似度，再基于候選對集合找出真正的相似文檔。

對給定集合A、B，hmin（A）=hmin（B）成立的條件是中具有最小哈希值的元素也在中。這里有一個假設，h（x）是一個良好的哈希函數，具有良好的均勻性，并能將不同元素映射成不同的整數。所以有，Pr[hmin（A）=hmin（B）]=J（A，B），即集合A和B的相似度為集合A、B經過hash后最小哈希值相等的概率，而其成為候選對的概率則為1-（1-SL）K，其中S是集合A和B的Jaccard相似度[5]。

3 Mahout中MinHash算法實現

本文即在Mahout分布式平臺[6]中實現MinHash算法，由于Mahout中算法均由MapReduce算法模型來構造確定，因而基于此，MinHash算法主要包括MinHashDriver、MinHashMapper、MinHashReducer、HashFactory和HashFunction五個java文件。MinHash算法使用簡單工廠模式來運作并處理，其中MinHashDriver作為整個算法的驅動程序，所有的參數都在這個文件中指定或者獲取，而且還綁定了map程序為MinHashMapper和reduce程序為MinHashReducer；同時HashFunction作為算法的接口，將在MinHashMapper的map中重寫哈希函數。

具體地，MinHashDriver是在終端直接調用MinHash代碼實現的直接接口，其中指定了MinHash包運行的相關參數的讀取和設定，以及map和reduce程序的綁定。類HashFactory中指定HashType，在枚舉類型HashType中有LINEAR， POLYNOMIAL， MURMUR， MURMUR3四種子類；在本文的實驗中，使用這四種哈希類型驗證正確的MinHash算法，結果顯示差距不大，因此本文實驗使用默認的LINEAR類型。在HashFactory中調用LinearHash函數，生成numFunctions個hashFunction。

MinHash算法主要邏輯實現在MinHashMapper中，map程序讀入（key，value）格式數據，使用value中的token作為生成minHashValues的參數在for循環(huán)中獲得token， 通過對bytesToHash數組做移位操作，然后作為hash函數的參數生成hashIndex，最后再計算哈希函數值，并保留最小哈希值。將minHashValues值組合作為Bucket輸出，使用“-”將minHashValues連接起來，外層循環(huán)是lTable，內層循環(huán)是keyGroups，具體功能是：對每個文件做L次運算（分別映射到L個Bucket中），每個Bucket的格式為XXX-XXX，新的map的key是cluster，即Bucket，value是對應的文件名。

4 實驗

在這一節(jié)中，將使用數據集Reuters-21578，證明了Mahout平臺中原有MinHash算法的錯誤和修正后MinHash算法的正確，并給出實驗分析。本文實驗使用Dell PowerEdge T320服務器，操作系統(tǒng)是32位Ubuntu 11.04，Java 1.6，Mahout版本0.6，Hadoop版本0.20.0。需要注意的是，在安裝Mahout之前，需要安裝Maven3。路透社新聞數據集Reuters-21578 是文本分類研究經常使用的數據集。在整個數據集中有21 578個文檔，由135個類別組成，這些文檔在做預處理后才能使用Mahout中提供的序列化和向量化工具類。

在2.2節(jié)中，可以知道，給定兩個有限集合A和B，其成為候選對的概率為1-（1-SL）K，其中S是集合A和B的Jaccard相似度。函數1-（1-SL）K的圖像大致是S-曲線。曲線中候選概率為處對應的相似度就是閾值，而且還是L和K的函數，該閾值的一個近似估計是（1/L）1/k。表1給出了對給定參數L=4，k=2時，函數1-（1-SL）K的值與相似度S的變化關系。該表反映了不同Jaccard相似度對應的理想碰撞概率。

5 結束語

本文針對MinHash算法在分布式平臺上的實現和性能表現進行分析和研究。通過研究發(fā)現， MinHash算法在分布式平臺上比非分布式平臺有很大優(yōu)勢，尤其是在處理大規(guī)模數據集時。為此，即在深入研究MinHash算法原理和分布式平臺的基礎上，設計了MinHash的分布式算法。實驗結果表明本文給出的MinHash分布式算法在處理實際問題上的正確性和準確性，這也為今后的在分布式平臺上解決近似近鄰問題提供了一個新的思路。

參考文獻：

[1] INDYK P， MOTWANI R. Approximate nearest neighbors： towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM， 1998： 604-613.

[2] BRODER， ANDREI Z？.？On the resemblance and containment of documents， Compression and Complexity of Sequences： Proceedings[C]//Positano， Amalfitan Coast， Salerno， Italy， IEEE， June 11-13， 1997：？21–29.

[3] WANG H， CAO J， SHU L C， et al. Locality sensitive hashing revisited： filling the gap between theory and algorithm analysis[C]//Proceedings of the 22nd ACM international conference on Conference on information & knowledge management， ACM， 2013： 1969-1978.

[4] DATAR M， IMMORLICA N， INDYK P， et al. Locality- sensitive hashing scheme based on p-stable distributions[J]. SCG04， June 9-11， 2004.

[5] Rajaraman A， Ullman J D. Mining of massive datasets[M]. Cambridge University Press， 2012.

[6] Anil R， Dunning T， Friedman E. Mahout in action. Manning， 2011.