分布式平臺(tái)下MinHash算法研究與實(shí)現(xiàn)

王洪亞等

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

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

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

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

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

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

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

1相關(guān)工作

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

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

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

2 MinHash算法原理

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)

在這一節(jié)中，將使用數(shù)據(jù)集Reuters-21578，證明了Mahout平臺(tái)中原有MinHash算法的錯(cuò)誤和修正后MinHash算法的正確，并給出實(shí)驗(yàn)分析。本文實(shí)驗(yàn)使用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ù)集。在整個(gè)數(shù)據(jù)集中有21 578個(gè)文檔，由135個(gè)類別組成，這些文檔在做預(yù)處理后才能使用Mahout中提供的序列化和向量化工具類。

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

5 結(jié)束語

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

參考文獻(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.