海量數(shù)據(jù)的一種集合模糊匹配關(guān)聯(lián)算法

婁鑫坡，孔玉靜

(河南城建學(xué)院 計算機(jī)與數(shù)據(jù)科學(xué)學(xué)院，河南 平頂山 467036)

按照數(shù)據(jù)類型的不同，匹配度關(guān)聯(lián)問題可分為字符串關(guān)聯(lián)、向量關(guān)聯(lián)和集合關(guān)聯(lián)。其中，集合數(shù)據(jù)的關(guān)聯(lián)操作一般是指利用索引結(jié)構(gòu)對原始數(shù)據(jù)進(jìn)行分組，然后對各個分組內(nèi)的數(shù)據(jù)進(jìn)行匹配度關(guān)聯(lián)操作，最后對各個分組的結(jié)果進(jìn)行匯總并得到最終結(jié)果。眾多學(xué)者都對面向集合數(shù)據(jù)的匹配度關(guān)聯(lián)查詢問題進(jìn)行過研究，并且提出了相關(guān)的關(guān)聯(lián)算法[1-3]。其中，比較具有代表性的算法是MRSimJoin[4]，是針對集合數(shù)據(jù)源進(jìn)行關(guān)聯(lián)，即自關(guān)聯(lián)。該算法從集合中隨機(jī)選K個數(shù)據(jù)作為中樞，然后利用中樞數(shù)據(jù)對集合進(jìn)行劃分，形成k個分區(qū)，在k個分區(qū)內(nèi)并行地進(jìn)行K值匹配度關(guān)聯(lián)操作以加快算法效率。但MRSimJoin對數(shù)據(jù)的關(guān)聯(lián)是一次性的，即每次操作都是從頭開始。另外，由于實際應(yīng)用中數(shù)據(jù)的差異性，在劃分分區(qū)時容易出現(xiàn)數(shù)據(jù)的傾斜問題，直接導(dǎo)致各Datanode負(fù)載不均衡。

本文提出海量數(shù)據(jù)下的一種集合模糊匹配關(guān)聯(lián)算法，針對數(shù)據(jù)增加時關(guān)聯(lián)操作效率變低的問題，該算法在Hadoop固有的分塊策略基礎(chǔ)之上對其分塊策略再進(jìn)一步優(yōu)化，即在分塊后再分階段處理。針對數(shù)據(jù)處理過程中失真問題，如同一人名或者地址在不同的集合中會出現(xiàn)一定的差異[5-6]，即使匹配了也不可能總是做到精確的匹配，實際上是滿足某個匹配閾值的。即給定兩個記錄文件R和S、度量函數(shù)sim和一個模糊匹配度閾值，該值隨著情況改變而動態(tài)改變，找出兩個集合中的所有記錄對S.a和R.a，且滿足sim(S.a，R.a)≥k(模糊值)[7-8]。針對該問題，F(xiàn)MLASH算法提出了更廣泛的適用度模糊匹配計算方法，即使用一定的標(biāo)準(zhǔn)函數(shù)度量集合之間的模糊匹配度，對于滿足度量標(biāo)準(zhǔn)的數(shù)據(jù)再進(jìn)行關(guān)聯(lián)操作。通過與當(dāng)前存在的較好處理集合數(shù)據(jù)的匹配關(guān)聯(lián)算法對比，F(xiàn)MLASH算法在集合數(shù)據(jù)的匹配關(guān)聯(lián)領(lǐng)域表現(xiàn)出了更廣闊的應(yīng)用前景。

1 算法提出

1.1 總體思路

在Hadoop平臺下進(jìn)行集合模糊匹配度關(guān)聯(lián)時，最主要的一個問題是如何對數(shù)據(jù)進(jìn)行分區(qū)并且復(fù)制數(shù)據(jù)，本文提出的算法思想首先基于關(guān)鍵字通過網(wǎng)絡(luò)對數(shù)據(jù)進(jìn)行哈希分區(qū)，擁有相同關(guān)鍵字的數(shù)據(jù)被分到同一個分組，但對于需要進(jìn)行關(guān)聯(lián)的屬性值不能直接用作關(guān)鍵字來進(jìn)行分區(qū)操作，相反，使用從其他屬性值中產(chǎn)生的簽名作為分區(qū)關(guān)鍵字，只有當(dāng)關(guān)聯(lián)的屬性值具有至少一個公共簽名時才有可能匹配。簽名可以是一個字符串中各個單詞的列表，也可以是匹配字符串長度的變化區(qū)間。

本文算法主要分三個階段，各個階段對應(yīng)一個子算法(即FMLASH-x算法，x=1，2，3)。

第一個階段為標(biāo)記生成算法(FMLASH-1)，主要用來生成全局標(biāo)記集合，在后續(xù)階段的算法中需要使用這些標(biāo)記對數(shù)據(jù)進(jìn)行分區(qū)。

第二個階段為RID生成算法(FMLASH-2)，集合中每一項都對應(yīng)一個ID，在本階段將會生成匹配項的ID數(shù)據(jù)對，在第三個階段將會使用這些數(shù)據(jù)對生成匹配項。

第三個階段主要為匹配項生成算法(FMLASH-3)，使用第二個階段的數(shù)據(jù)對并通過掃描原始數(shù)據(jù)，最終輸出集合中的匹配項。

1.2 FMLASH-1算法

FMLASH-1算法基本思想是對原始數(shù)據(jù)進(jìn)行處理，然后產(chǎn)生全局標(biāo)記集合，包含兩個步驟。

步驟一：map函數(shù)的輸入為原始數(shù)據(jù)集合，抽取集合中每一項的關(guān)聯(lián)屬性值并進(jìn)行標(biāo)記，同時輸出(token，1)數(shù)據(jù)對。為了減輕網(wǎng)絡(luò)之間數(shù)據(jù)的流量，使用combine函數(shù)計算map所產(chǎn)生標(biāo)記的次數(shù)。

步驟二：map函數(shù)交換key和value值，然后使用一個reduce函數(shù)在value的基礎(chǔ)之上對所有標(biāo)記進(jìn)行排序，最后輸出整個排過序的全局標(biāo)記列表。

其中偽代碼描述如下：

Step 1：

原始數(shù)據(jù)D；

Map(Writtable key，Text line){

從line中抽取關(guān)聯(lián)屬性(token)并標(biāo)記；

Output(token，1)；

}

Combine(token，iter){

使用iter遍歷map階段輸出token對應(yīng)的集合；

統(tǒng)計token出現(xiàn)的次數(shù)(num)；

Output(token，num)；

}

Reduce(token，iter){

使用iter遍歷從不同結(jié)點發(fā)送token的結(jié)果；

對于token進(jìn)行全局統(tǒng)計；

Output(token，num)，將結(jié)果輸出到多個文件，每個文件包含部分token；

}

Step 2：

Map(Text key，IntWritable num){

Output(num，key)，將結(jié)果輸入到一個reduce節(jié)點上；

}

Reduce(IntWrtiable key){

匯總所有token信息，利用框架自帶排序功能；

按照key由小到大輸出value的值，即token，output(token，NULL)；

}

1.3 FMLASH-2算法

FMLASH-2算法主要用來產(chǎn)生匹配的RID對，即匹配的項所對應(yīng)的標(biāo)示ID，算法包含一個Hadoop階段。在執(zhí)行map函數(shù)之前，首先調(diào)用DistributedCache函數(shù)加載FMLASH-1階段產(chǎn)生的token標(biāo)記集合，map函數(shù)的輸入為原始數(shù)據(jù)集，然后逐條檢索原始數(shù)據(jù)集，對于每一項抽取標(biāo)識ID和關(guān)聯(lián)屬性值，標(biāo)記關(guān)聯(lián)屬性并按照對應(yīng)頻率進(jìn)行排序，為了計算每一項之間的模糊匹配度，map函數(shù)抽取每一項的前綴并計算其長度，為每一項生成(key，value)數(shù)據(jù)對(key為前綴值，value為原始數(shù)據(jù)項)。對于由map函數(shù)所產(chǎn)生的數(shù)據(jù)對，reduce函數(shù)應(yīng)用位置過濾規(guī)則進(jìn)行過濾，對于通過過濾的集合項進(jìn)行驗證并輸出(RID1，RID2，SimValue)。算法的偽碼描述中：TWritable為一個新定義的數(shù)據(jù)類型，成員為第一階段生成的標(biāo)記，該數(shù)據(jù)類型compare方法按照標(biāo)記的頻率大小排序，PositionalFilter為位置過濾函數(shù)，δ為模糊匹配度閾值，其值根據(jù)需要可以動態(tài)調(diào)整。偽代碼描述如下：

Setup(){

使用DistributedCache加載token列表list；

}

Map(TWrittable key，Text line){

If(line中包含集合list中的項K)

Output(K，line)；

}

Reduce(token，iter){

List <-NULL；

For line in iter{

func=PositionalFilter；

If(func)

List <-line；

計算line同List中每一條記錄RID的模糊匹配度sim；

If(sim >δ)

Output(RID，line，sim)；

}

}

算法中的sim用來計算集合數(shù)據(jù)的模糊匹配度，主要使用的是Jaccard系數(shù)，例如：集合S={A，B，C，D，E}，R={F，B，C，D，E}，S和R的Jaccard計數(shù)為| S1∩S2 |/| S1∪S2 | = 4/6= 0.67，當(dāng)模糊匹配度閾值不同時，所求的結(jié)果也不相同，若δ=0.75，由于R和S的Jaccard系數(shù)為0.67小于δ，因此判定R和S匹配。

1.4 FMLASH-3算法

FMLASH-3算法利用FMLASH-2階段產(chǎn)生的RID數(shù)據(jù)對和原始數(shù)據(jù)集合產(chǎn)生模糊匹配度關(guān)聯(lián)結(jié)果，該算法又包含兩個步驟。

步驟一：map函數(shù)獲得原始數(shù)據(jù)集合和第二個階段產(chǎn)生的RID數(shù)據(jù)對，對于前者，輸出(RID，record)，對于后者，輸出兩個(key，value)數(shù)據(jù)對，分別用兩個RID作為key值，value為整個RID對和模糊匹配度，reduce函數(shù)根據(jù)key值對數(shù)據(jù)進(jìn)行聚合。

步驟二：map函數(shù)把輸入數(shù)據(jù)傳輸給reduce函數(shù)，進(jìn)行集合項的模糊匹配度關(guān)聯(lián)操作并輸出結(jié)果。

其偽代碼描述如下：

Step 1：

Setup(){

使用DistributedCache加載FMLASH-2算法輸出的RID列表(rd1，rd2，sim)；

}

Map(LongWritable key，Text line){

Output(RID，line)；

Output(rd1，(rd1，rd2)，sim)；

Output(rd2，(rd1，rd2)，sim)；

}

Reduce(IntWritable id，iter){

對于相同rd的記錄record和(rd1，rd2)，sim，Output((rd，rd2)，(record，sim))；

}

Step 2：

Map(Text key，Text record){

將key相同的記錄發(fā)送到同一個reduce上；

}

Reduce(Text key，iter){

一個key對應(yīng)兩條記錄rd1對應(yīng)的記錄record1和rd2對應(yīng)的記錄record2；

Output(NULL，(rd1，record1，rd2，record2))；

}

2 實驗及結(jié)果分析

2.1 實驗環(huán)境

實驗平臺基于Windows7操作系統(tǒng)，硬件環(huán)境由9臺普通PC組成一個集群，1臺為Namenode，8臺為Datanode，內(nèi)存4GB，CPU型號Intel Core24核2.67GHz。軟件環(huán)境為操作系統(tǒng)CentOS-6.4-x86_64，Hadoop版本為hadoop-2.4.1，采用Myeclipse-8.5.0集成開發(fā)環(huán)境，JDK為JDK-7u79。

2.2 實驗數(shù)據(jù)

針對本文提出的模糊匹配度關(guān)聯(lián)算法FMLASH，可采用三組實驗分析該算法的效率：第一組實驗主要測試數(shù)據(jù)集大小變化以及匹配閾值變化對算法效率的影響；第二組實驗主要測試不同節(jié)點數(shù)對算法效率的影響；第三組主要測試算法的可擴(kuò)展性。

采用的對比算法為MRSimJoin算法，實驗中使用兩個數(shù)據(jù)集，分別為DBLP[9]和CITESEERX[10]。DBLP主要包含3 600多家出版物信息，需要對XML文件進(jìn)行一定的預(yù)處理操作，比如移除標(biāo)簽、輸出每一條出版物信息，形式為，平均記錄長度為259字節(jié)，數(shù)據(jù)集大小為2 024 278條記錄。CITESEERX主要包含3 891 161條記錄，記錄的平均長度為1 374字節(jié)，對數(shù)據(jù)集的預(yù)處理和DBLP數(shù)據(jù)集相同，其中每條記錄包含一個抽象字段和對應(yīng)會議的URL。

2.3 結(jié)果分析

(1)第一組實驗中使用DBLP數(shù)據(jù)集，通過改變數(shù)據(jù)規(guī)模以及模糊匹配閾值δ來觀察FMLASH算法的計算效率，并與MRSimJoin算法進(jìn)行比對并加以分析。在DBLP數(shù)據(jù)集上兩個算法的運行時間對比如圖1所示，此時匹配閾值δ=3，橫坐標(biāo)表示數(shù)據(jù)集大小(MB)，縱坐標(biāo)表示運行時間。

圖2 匹配閾值與運行時間

由圖1可知：當(dāng)數(shù)據(jù)集大小為50 M時，F(xiàn)MLASH算法運行時間為4 198 s，MRSimJoin算法運行時間為5 123 s。由于MRSimJoin算法對數(shù)據(jù)的模糊匹配度關(guān)聯(lián)操作是一次性的，每次操作均是重新開始，并且算法隨機(jī)選取聚類中心，對數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行聚類并進(jìn)行分區(qū)劃分，然后在各個分區(qū)被分配到各個節(jié)點進(jìn)行關(guān)聯(lián)操作，因此運行時間大于前者。此外，隨著數(shù)據(jù)集的增大，兩種算法整體的運行時間呈增長趨勢。

當(dāng)數(shù)據(jù)規(guī)模一定時，匹配閾值δ的改變會對運行時間造成影響。匹配閾值變化時兩種算法運行時間的對比如圖2所示，橫坐標(biāo)表示匹配閾值，縱坐標(biāo)表示運行時間(s)。

由圖2可知：當(dāng)匹配閾值較小時，匹配對的判定比較嚴(yán)苛，滿足匹配條件的數(shù)據(jù)比較少，但隨著匹配閾值的增加，匹配的數(shù)據(jù)對個數(shù)開始增加，兩種算法的運行時間也隨著增加，表明匹配閾值對算法的效率也有一定的影響。

(2)第二組實驗中使用CITESEERX數(shù)據(jù)集，通過增加節(jié)點數(shù)來測試算法的性能。兩種算法在不同節(jié)點數(shù)上運行時間的變化情況如圖3所示，橫坐標(biāo)表示節(jié)點數(shù)，縱坐標(biāo)表示運行時間(s)。

圖3 節(jié)點數(shù)與運行時間

圖4 (數(shù)據(jù)大小，節(jié)點數(shù))與運行時間

由圖3可知：隨著節(jié)點數(shù)的增加，算法的運行時間都呈下降趨勢。因為隨著節(jié)點數(shù)的增多，單個節(jié)點負(fù)載雖降低，但集群的整體計算能力增加。由于MRSimJoin算法的主要思想是對數(shù)據(jù)進(jìn)行劃分，而FMLASH算法直接對數(shù)據(jù)進(jìn)行處理，所以后者的運行時間明顯少于前者。

(3)第三組實驗，由于Hadoop具有強大的并行處理能力，希望算法可以具有高效的擴(kuò)展性，即同步增加節(jié)點數(shù)和數(shù)據(jù)集時，算法的運行時間不會受到影響。算法的可擴(kuò)展性如圖4所示，橫坐標(biāo)表示數(shù)據(jù)集大小和節(jié)點數(shù)，縱坐標(biāo)表示運行時間。

由圖4可知：理想情況下，當(dāng)數(shù)據(jù)集與節(jié)點數(shù)同步增加時，運行消耗時間基本不變；當(dāng)節(jié)點數(shù)不變而數(shù)據(jù)集增大時，運行時間增加。但實際結(jié)果是數(shù)據(jù)集與節(jié)點數(shù)同步增加時，運行時間也增加，只是增加幅度不明顯；當(dāng)節(jié)點數(shù)不變而數(shù)據(jù)集增大時，運行時間增加的速度比理想型慢。

3 結(jié)論

海量數(shù)據(jù)條件下集合的模糊匹配度關(guān)聯(lián)技術(shù)雖然已經(jīng)取得了一些創(chuàng)新性成果，但是尚有很多問題有待進(jìn)一步研究：

(1)在線實時的海量關(guān)聯(lián)技術(shù)。Hadoop平臺因為其簡單、易用以及其容錯性，經(jīng)常用于解決海量數(shù)據(jù)條件下的模糊匹配度關(guān)聯(lián)問題。但另一方面，Hadoop平臺屬于一種批處理模型，對于需要實時處理的問題并不適用。所以，如何在線實時對海量數(shù)據(jù)進(jìn)行模糊匹配度關(guān)聯(lián)有待進(jìn)一步研究。

(2)支持多種數(shù)據(jù)類型的海量數(shù)據(jù)關(guān)聯(lián)技術(shù)。本文算法主要針對集合數(shù)據(jù)，另外相關(guān)的研究也主要集中在字符串和向量數(shù)據(jù)類型。但在現(xiàn)實生活中還有很多其他數(shù)據(jù)類型，如XML文檔、圖和直方圖等，數(shù)據(jù)類型的差別可能導(dǎo)致現(xiàn)有的模糊匹配度關(guān)聯(lián)算法并不適用于這些新型數(shù)據(jù)，如何對現(xiàn)有的算法進(jìn)行擴(kuò)展從而支持這些新型數(shù)據(jù)也需要進(jìn)一步研究。