王洪亞等

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

關(guān)鍵詞：MinHash；分布式；算法實現(xiàn)

中圖分類號：TP311 文獻(xiàn)標(biāo)識號：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 引 言

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

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

基于上述討論，本文主要貢獻(xiàn)如下：

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

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

1相關(guān)工作

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

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

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

2 MinHash算法原理

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

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

以上函數(shù)即稱為MinHash函數(shù)。

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

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

3 Mahout中MinHash算法實現(xiàn)

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

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

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

4 實驗

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

[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.