海量數(shù)據(jù)的MapReduce相似度檢測(cè)

張 敏

(河南理工大學(xué) 測(cè)繪與國(guó)土信息工程學(xué)院，河南 焦作 454003)

0 引 言

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

1 相關(guān)工作

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

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

2 Simhash算法與云計(jì)算

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。一篇文檔可能包含上成千上萬個(gè)元素，對(duì)大量的文檔，保存這些元素需要很大的空間，通過一種方法來減少元素個(gè)數(shù)，并且通過少量元素依然可以得到原來的Jaccard相似度，過程如下：

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

定義f為E上的一個(gè)映射關(guān)系，將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的一個(gè)簽名，m2為S2的一個(gè)簽名，通過少量的簽名，能夠得Jaccard_Sim(S1,S2) 的一個(gè)近似值。將上面的映射關(guān)系f替換為一個(gè)E上的隨機(jī)哈希函數(shù)，這個(gè)結(jié)論依然成立。所以，對(duì)一篇文檔使用n個(gè)隨機(jī)哈希函數(shù)可以得到n個(gè)簽名，稱為文檔的最小哈希簽名，并且通過比較最小哈希簽名可以得到兩篇文檔間的Jaccard相似度。

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

2.2 Simhash算法

SimHash通過產(chǎn)生簽名用來檢測(cè)原始內(nèi)容的相似度。假設(shè)輸入的是一個(gè)文檔的特征集合，每個(gè)特征有一定的權(quán)重。特征可以是文檔中的詞，其權(quán)重可以是這個(gè)詞出現(xiàn)的次數(shù)，SimHash能夠?qū)⑵溆成涞揭粋€(gè)低維向量空間，并根據(jù)該低維向量產(chǎn)生一個(gè)很小的指紋；算法過程如下：

(1) 將一個(gè)f維的向量V初始化為0；f位的二進(jìn)制數(shù)S初始化為0；

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

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

(4) 輸出S作為簽名。

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

2.3 MapReduce

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

圖2 MapReduce工作機(jī)制

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

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

(1) 預(yù)處理。主要包括: 預(yù)處理文本文件、存儲(chǔ)術(shù)語集和文本-術(shù)語對(duì)應(yīng)關(guān)系[13]。由于文本文件的格式多樣性，為求統(tǒng)一，將各種格式的文本轉(zhuǎn)化為TXT文件。對(duì)術(shù)語集和文本-術(shù)語對(duì)應(yīng)關(guān)系，使用HBase提供的應(yīng)用程序接口將其存儲(chǔ)。

圖3 基于MapReduce的文本近似檢測(cè)流程

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

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

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

Class Mapper{

method map(〈label,txtid〉,Vector)

write(〈label,txtid〉,Vector)

}

Class Reducer{

Matrix matrix;//每一行對(duì)應(yīng)一個(gè)類別的向量和

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;//測(cè)試類標(biāo)

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 實(shí)驗(yàn)結(jié)果與驗(yàn)證

本實(shí)驗(yàn)基于河南理工大學(xué)高性能計(jì)算平臺(tái)進(jìn)行，該平臺(tái)由曙光刀片機(jī)構(gòu)建，共有共34個(gè)節(jié)點(diǎn)：1個(gè)管理節(jié)點(diǎn)，1個(gè)IO節(jié)點(diǎn)，32個(gè)計(jì)算節(jié)點(diǎn)，千兆存儲(chǔ)網(wǎng)絡(luò)。系統(tǒng)采用RedHat Linux構(gòu)建高計(jì)算集群。單節(jié)點(diǎn)配置Intel Xeon E5504 2.00 GHz CPU，8 GB內(nèi)存，120 GB硬盤。軟件配有J2SE 6.0，Hadoop 0.20.2，HBase-0.20.6等。在該環(huán)境下，選擇1個(gè)為NameNode作為控制節(jié)點(diǎn)、 6個(gè)DataNode參與計(jì)算任務(wù)。

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

表1 TanCorp-10數(shù)據(jù)集分布

表2 SogouCS數(shù)據(jù)集分布

4.1 執(zhí)行時(shí)間對(duì)比

實(shí)驗(yàn)分別在單機(jī)和Hadoop的全分布式環(huán)境下進(jìn)行，采用90%作為訓(xùn)練集，10%為測(cè)試集，執(zhí)行時(shí)間如圖4所示。

圖4 單機(jī)和全分布式執(zhí)行時(shí)

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

4.2 相似度計(jì)算時(shí)間對(duì)比

分別在上述兩個(gè)數(shù)據(jù)集使用Map/Reduce進(jìn)行實(shí)驗(yàn)，對(duì)比歐氏距離、余弦相似度、相關(guān)系數(shù)、SimHash的相似度計(jì)算的執(zhí)行時(shí)間，其執(zhí)行時(shí)間如表3所示。

表3 相似度時(shí)間對(duì)比表

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

5 結(jié) 語

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

[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] 付印金, 肖 儂, 劉 芳. 重復(fù)數(shù)據(jù)刪除關(guān)鍵技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)研究與發(fā)展, 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] 敖 莉, 舒繼武, 李明強(qiáng),等. 重復(fù)數(shù)據(jù)刪除技術(shù)[J].電子學(xué)報(bào), 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] 韓京宇, 徐立臻. 一種大數(shù)據(jù)量的相似記錄檢測(cè)方法[J].計(jì)算機(jī)研究與發(fā)展, 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] 李星毅,包從劍. 數(shù)據(jù)倉(cāng)庫(kù)中的相似重復(fù)記錄檢測(cè)方法[J].電子科技大學(xué)學(xué)報(bào), 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].電子學(xué)報(bào),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ì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào),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] 張組斌， 徐 欣， 龍 君,等. 文本相似度檢測(cè)的參數(shù)關(guān)聯(lián)和優(yōu)化[J] 中文計(jì)算機(jī)系統(tǒng), 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] 程國(guó)達(dá), 蘇杭麗. 一種檢測(cè)漢語相似重復(fù)記錄的有效方法[J]. 計(jì)算機(jī)應(yīng)用, 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ìn)的相似重復(fù)記錄檢測(cè)方法[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.