海量數據的MapReduce相似度檢測

張 敏

(河南理工大學 測繪與國土信息工程學院，河南 焦作 454003)

0 引 言

隨著數字信息量的幾何式增長，數據占用空間越來越大。在過去的幾年里，存儲系統容量從數十GB發展到數百TB，甚至數PB[1]。隨著數據指數級增長，管理保存數據成本及數據中心空間和能耗也變得越來越嚴重。研究發現，保存的數據中有六成以上是冗余的，而且隨著時間的推移，這種問題會更加嚴重。為了緩解存儲系統的空間增長問題，最大程度地利用已有資源，重復數據查找刪除技術已成為一個熱門的研究課題。一方面，重復數據查找可以對存儲空間進行優化，消除分布在存儲系統中的相同文件或者數據塊。另一方面，可以減少在網絡中傳輸的數據量，進而降低能量消耗和網絡成本，并為數據復制大量節省網絡帶寬。

1 相關工作

相似重復記錄的檢測主要有排序合并法、建索引法、機器學習法和基于特定領域知識法，其中排序合并和建索引的方法是不依賴于特定應用領域的通用方法；文獻[2]采用排序合并的方法，根據用戶選定的若干個屬性字符串合并作為鍵進行排序后，采用固定大小的滑動窗口進行聚類來識別相似重復記錄；文獻[3]介紹的根據不同的屬性進行多路排序合并，并采用優先隊列取代固定大小的滑動窗口來進行聚類。這兩種方法之主要不足在于大數據量記錄及排序引起大量IO操作，成為算法運行效率的瓶頸；另一方面由于字符串排序對字符位置敏感，所以不能保證將相似的重復記錄放在鄰近的位置，因而決定了后來的聚類操作不一定能將相似記錄識別出來。采用R樹建索引的方法[4]中首先依據Fastmap方法選取若干個記錄作為軸(Pivot)，各個記錄依據這若干個軸計算它本身在多維空間中的坐標，然后采用R樹進行多維空間相似性連接來實現相似記錄的識別。但是由于Fastmap方法本身不可收縮性(Contractive)，因此這種映射方法會造成大量的數據丟失，且由于維度災難，也就決定了維度不能過高，使得這種方法不具有通用性。文獻[5]針對的是數據在線去重問題，它是在有干凈參照表的條件下進行數據清洗的方法。

通過向量空間模型(Vector Space Model,VSM)計算相似度，但這種方法存在的問題是需要對文本兩兩進行相似度比較，無法擴展到海量文本的處理。因此，若能結合海量數據的計算模型和VSM，先對文本進行分詞預處理，然后建立文本向量，把相似度的計算轉換成某種特征向量距離的計算(如Jaccard相似系數等)，則可以實現海量數據相似度檢測，從而解決海量數據的去重問題。

2 Simhash算法與云計算

2.1 Jaccard相似度

集合S和T之間的Jaccard相似度是指集合S和T的交集和并集之間的比值，即Jaccard_Sim(S,T)=|S∩T|/|S∪T|。例如：S={a,d}，T={a,c,d}，則Jaccard_Sim(S,T)=|{a,d}|/|{a,c,d}|=2/3。一篇文檔可能包含上成千上萬個元素，對大量的文檔，保存這些元素需要很大的空間，通過一種方法來減少元素個數，并且通過少量元素依然可以得到原來的Jaccard相似度，過程如下：

假設對元素集E={a,b,c,d,e}上的集合S1={a,d}，S2={a,c,d}，其特征矩陣為

定義f為E上的一個映射關系，將f作用于S1，S2上，其特征矩陣為

取m1為f(S1)中的最小值，即m1=min{f(a),f(d)}，m2為f(S2)中的最小值，即m2=min{f(a),f(c),f(d)}，則m1與m2相等的概率為：P(m1=m2)=P(min{f(a),(b)}=min{f(a),f(c),f(d)})=|{f(a),f(d)}|/|{f(a),f(c),f(d)}|=|{a,d}|/|{a,c,d}|=Jaccard_Sim(S1,S2)。

因此，令m1為S1的一個簽名，m2為S2的一個簽名，通過少量的簽名，能夠得Jaccard_Sim(S1,S2) 的一個近似值。將上面的映射關系f替換為一個E上的隨機哈希函數，這個結論依然成立。所以，對一篇文檔使用n個隨機哈希函數可以得到n個簽名，稱為文檔的最小哈希簽名，并且通過比較最小哈希簽名可以得到兩篇文檔間的Jaccard相似度。

對兩篇文檔[9]，如果它們相似，則它們的哈希值有較高的概率是相同的。有了文檔的最小哈希簽名，就能實現這種哈希方法，將包含b×r個值最小哈希簽名分為b等份，每份r個，對兩個文檔，定義P為兩個文檔至少含有1個相同份的概率，顯然，文檔間的Jaccard相似度越高，哈希簽名具有相同值的位數就越多，概率P就越大。

2.2 Simhash算法

SimHash通過產生簽名用來檢測原始內容的相似度。假設輸入的是一個文檔的特征集合，每個特征有一定的權重。特征可以是文檔中的詞，其權重可以是這個詞出現的次數，SimHash能夠將其映射到一個低維向量空間，并根據該低維向量產生一個很小的指紋；算法過程如下：

(1) 將一個f維的向量V初始化為0；f位的二進制數S初始化為0；

(2) 對每一個特征:用傳統的hash算法對該特征產生一個f位的簽名b。對i=1到f,如果b的第i位為1，則V的第i個元素加上該特征的權重；否則，V的第i個元素減去該特征的權重；

(3) 如果V的第i個元素大于0，則S的第i位為1，否則為0；

(4) 輸出S作為簽名。

與傳統的加密型哈希函數相比，SimHash擁有一個顯著特征，即越相似的原始信息會生成越相似的哈希值，也就是哈希值的海明距離越小。而傳統的哈希函數，為兩個不同的原始信息生成哈希值時，即使它們實際上很相近，計算得出的哈希值之間漢明距離也可能非常大，無法用于度量原始信息的相似度。

2.3 MapReduce

MapReduce[6]是一種高效的分布式編程模型，其工作機制如圖2所示,用于處理和生成大規模數據集的實現方式[7]。MapReduce中兩項核心操作為Map和Reduce操作，其Map操作獨立地對每個元素進行操作；Reduce操作對N個Map結果進行排序收集，也就是Map[1，2，…，N]的結果是Reduce操作的參數。在MapReduce編程模型中，只要沒有函數修改或依賴于全局變量，N個Map操作的執行順序可以是無序的；而且，Map和Reduce都以其他的函數作為輸入參數，正是因為可以同其他函數相結合，所以只要把Map和Reduce這兩個函數進行并行化處理，就無需面面俱到地把所有的函數全部考慮到，這樣便形成了一個以Map和Reduce為基礎的編程模型。該模型為用戶提供編寫與具體應用相關的函數的編程接口，用戶把計算需求歸結為Map和Reduce操作，通過這個接口提交到MapReduce系統上就可以獲得并行處理的能力，所以，這種特性使MapReduce模型非常適合于對大規模數據進行并行處理。

圖2 MapReduce工作機制

3 MapReduce下相似文檔查找流程及算法

根據MapReduce工作機制，提出MapReduce下以Simhash算法查找近似文本檢測流程，如圖3所示。海量文檔集存儲在Hadoop分布式文件系統(HDFS)中，術語集和文本-術語關系集存儲在分布式key-value系統HBase中，特征提取算法和相似度計算算法采用分布式計算模型Map/Reduce。此外，由于海量文檔集的文本數量眾多并且大小相對較小[9-10]，使用HDFS提供的SequenceFile InputFormat方法[11]，將文件名作為key、文件作為value，以key-value的形式將文本存儲在Sequence File。同樣，對提取出特征向量或指紋也以key-value的形式存儲在另外的Sequence File[12]。

(1) 預處理。主要包括: 預處理文本文件、存儲術語集和文本-術語對應關系[13]。由于文本文件的格式多樣性，為求統一，將各種格式的文本轉化為TXT文件。對術語集和文本-術語對應關系，使用HBase提供的應用程序接口將其存儲。

圖3 基于MapReduce的文本近似檢測流程

(2) 特征提取。首先將文本表示成詞頻向量，然后計算詞頻向量指紋。由于學習資源存在領域術語的特征，文本將表示為一個高維術語詞頻向量，然后再使用SimHash算法生成指紋。為提高特征提取算法的效率，用Map/Reduce模型提取文檔集特征。對給定的文檔集，特征提取Map/Reduce任務只需運行1次，輸入是文檔集，輸出是Sequence File，其中文件名作為key，文件的指紋作為value。

特征提取過程包括提取詞頻向量、生成SimHash指紋和生成Sequence File。提取詞頻向量提取詞頻向量是將文本轉換為一個n維詞頻向量；SimHash使用SimHash算法計算該詞頻向量的64 b SimHash指紋；生成SequenceFile得到文本的指紋后，將文件名作為key，其64 b SimHash指紋作為value，寫入Sequence File中。

(3) 相似度計算。用于比較待測文本和文檔集文本之間的相似度。它使用待測文本的指紋和文檔集特征提取輸出的SequenceFile作為輸入，采用各種相似度度量方法(例如對SimHash指紋則采用海明距離)，進行近似檢測[14]，算法的偽代碼如下所示：

Class Mapper{

method map(〈label,txtid〉,Vector)

write(〈label,txtid〉,Vector)

}

Class Reducer{

Matrix matrix;//每一行對應一個類別的向量和

int i=0;

String[]labels;

void setup(){

int i=0;

SequenceFile.Reader reader=new

SequenceFile.Reader(“exameDataSet”);

While(reader.next(key.value)){

matrix.assignRow(i,value);

labels[i]=key;

}

}

void map(〈label,txtid〉,vector){

double sim=0;//最大相似度值

String testLabel;//測試類標

for(int i=0;i〈ma.numRows;i++){

double cos=cos_sim(Vector,ma.getRow(i));

if(max〈cos)max=cos;

testLable=Lables[i];

write(lable,〈testLable,txtid〉;

}

4 實驗結果與驗證

本實驗基于河南理工大學高性能計算平臺進行，該平臺由曙光刀片機構建，共有共34個節點：1個管理節點，1個IO節點，32個計算節點，千兆存儲網絡。系統采用RedHat Linux構建高計算集群。單節點配置Intel Xeon E5504 2.00 GHz CPU，8 GB內存，120 GB硬盤。軟件配有J2SE 6.0，Hadoop 0.20.2，HBase-0.20.6等。在該環境下，選擇1個為NameNode作為控制節點、 6個DataNode參與計算任務。

為驗證近似文本檢測算法能夠適用于海量數據，算法將在兩個中文數據集上做實驗，第一是譚松波(TanCorp-10)等搜集的文檔[15]，共14 150篇、29.5 MB、包含10個類別，如表1所示；第二個數據集是搜狗新聞2008年上半年(SogouCS)國內外18個頻道[16]，提供URL和正文信息，共2 101 582篇文檔、3.33 GB、包含15個類別如表1、2所示。

表1 TanCorp-10數據集分布

表2 SogouCS數據集分布

4.1 執行時間對比

實驗分別在單機和Hadoop的全分布式環境下進行，采用90%作為訓練集，10%為測試集，執行時間如圖4所示。

圖4 單機和全分布式執行時

從上圖可知，對于小數據集(TanCorp)在分布式環境效果不明顯，其原因是：在小數據集下，Hadoop對數據是分塊處理的，默認64 MB為一個數據塊，如果存在大量小數據文件，這樣的小數據文件達不到Hadoop默認數據塊的大小時，就要按一個數據塊來進行處理。這樣處理帶來結果是：存儲大量小文件占據存儲空間，致使存儲效率不高、檢索速度也比大文件慢；而且進行MapReduce運算時，小文件消費計算能力。對于大數據集，設計的算法優勢明顯突出。

4.2 相似度計算時間對比

分別在上述兩個數據集使用Map/Reduce進行實驗，對比歐氏距離、余弦相似度、相關系數、SimHash的相似度計算的執行時間，其執行時間如表3所示。

表3 相似度時間對比表

從上表可知，在TanCorp-10中，相對于歐氏距離、余弦相似度和相關系數的相似度計算執行時間，SimHash的相似度計算的執行時間分別減少了137.5%、137.5%、143.8%；在SogouCSS中，執行時間分別減少了355.8%、381.4%、406.9%。這驗證了基于SimHash指紋的海明距離比較在時間上優于經典的文本相似度計算方法；也印證5.1節中，在處理大數據集上，MapReduce優勢明顯突出。

5 結 語

相對于以往相似重復記錄的檢測方法，本文提出了基于MapReduce的文本近似檢測流程，并設計了SimHash相似度算法，最后在實驗環境下進行了驗證。通過實驗可知，SimHash相似度的算法應用在MapReduce下，非常適合海量數據集的文檔相似度計算，極大降低了時間開銷，為解決海量數據去重問題提供一定的參考價值。

[1] Agrawal D, Bernstenin P, Bertino E,etal. Challenges and opportunities with big data-A community white paper developed by leading researchers across the United States[R/OL]. [2012-10-02]. http://cra.org/ccc/docs/init/bigdata/whitepaper.pdf

[2] 付印金, 肖 儂, 劉 芳. 重復數據刪除關鍵技術研究進展[J]. 計算機研究與發展, 2012,49(1):12-20.

FU Yin-jin, XIAO Nong, LIU Fang. Key technology research progress of duplicate data de-duplication [J]. Computer Research and Progress, 2012,49(1):12-20.

[3] 敖 莉, 舒繼武, 李明強,等. 重復數據刪除技術[J].電子學報, 2010,21(5): 916-918.

AO Li, SHU Ji-wu, LI Ming-qiang,etal. Duplicate data de-duplication technology [J]. Journal of electronic, 2010,21(5): 916-918.

[4] 韓京宇, 徐立臻. 一種大數據量的相似記錄檢測方法[J].計算機研究與發展, 2005,42(12):2207-2209.

HAN Jing-yu, XU Li-zhen. A kind of detection approach of duplicate recorder for massive data [J]. Computer Research and Progress, 2005,42(12):2207-2209.

[5] 李星毅,包從劍. 數據倉庫中的相似重復記錄檢測方法[J].電子科技大學學報, 2007,36(6):1273-1276.

LI Xing-yi, BAO Cong-jian. Detecting approach for similar duplicate recorder in data warehouse [J]. Journal of electronic technology university, 2007,36(6):1273-1276.

[6] 李建江,崔 健. MapReduce并行編程模型研究綜述[J].電子學報,2011,39(11): 2639-2645.

LI Jian-jiang, CUI Jian. Research review of parallel programming model [J]. Journal of electronic, 2011,39(11): 2639-2645.

[7] 陳 康,鄭緯民.云計算:系統實例與研究現狀[J].軟件學報,2009,20(5):1337-1348.

CHEN Kang, ZHENG Wei-min. Cloud computing: System instance and research situation [J]. Journal of software, 2009,20(5):1337-1348.

[8] 張組斌， 徐 欣， 龍 君,等. 文本相似度檢測的參數關聯和優化[J] 中文計算機系統, 2011, 32(5): 983-988.

ZHANG Zu-ping, XU Xin, LONG Jun,etal．Parameters correlation and optimization in text similarity measurement[J]．Journal of Chinese Computer Systems, 2011, 32(5): 983-988.

[9] 程國達, 蘇杭麗. 一種檢測漢語相似重復記錄的有效方法[J]. 計算機應用, 2005, 25(6): 1361-1365.

CHENG Gou-da, SU Hang-li. A kind of valid method of detecting Chinese similar recorder [J]. Computer application, 2005, 25(6): 1361-1365.

[10] Nature. Big Data [EB/OL]. [2012-10-02]. http://www.nature.com/news/specials/bigdata/index.html

[11] Shahri H H. Eliminating duplicates in information integration: an adaptive, extensible framework [J].IEEE Intelligent Systems, 2006, 12(5): 63-71.

[12] A Verma,N Zea,etal. Breaking the Mapreduce Stage Barrier. Proc of IEEE International Conference on Cluster Computing[C].Los Alamitos: IEEE Computer Society,2010:235-244.

[13] 朱恒民,王寧生.一種改進的相似重復記錄檢測方法[J].控制與決策, 2006, 21(7): 805-808.

ZHU Hen-min, WANG Ning-sheng. A kind of improved detecting method for similar duplicate recorder [J]. Control and decision, 2006, 21(7): 805-808.

[14] Paul S, Saravanan D V. Hash Partitioned Apriori in Parallel and Distribute Data Mining Environment with Dynamic Data Allocation Approach [C] //ICCSIT'08 Proceedings of the 2008 International Conference on Computer Science and Information Technology. 2008.