婁鑫坡，孔玉靜

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

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

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

1 算法提出

1.1 總體思路

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

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

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

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

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

1.2 FMLASH-1算法

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

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

步驟二：map函數(shù)交換key和value值，然后使用一個(gè)reduce函數(shù)在value的基礎(chǔ)之上對(duì)所有標(biāo)記進(jìn)行排序，最后輸出整個(gè)排過(guò)序的全局標(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對(duì)應(yīng)的集合；

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

Output(token，num)；

}

Reduce(token，iter){

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

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

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

}

Step 2：

Map(Text key，IntWritable num){

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

}

Reduce(IntWrtiable key){

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

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

}

1.3 FMLASH-2算法

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

Setup(){

使用DistributedCache加載token列表list；

}

Map(TWrittable key，Text line){

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

Output(K，line)；

}

Reduce(token，iter){

List <-NULL；

For line in iter{

func=PositionalFilter；

If(func)

List <-line；

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

If(sim >δ)

Output(RID，line，sim)；

}

}

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

1.4 FMLASH-3算法

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

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

步驟二：map函數(shù)把輸入數(shù)據(jù)傳輸給reduce函數(shù)，進(jìn)行集合項(xiàng)的模糊匹配度關(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){

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

}

Step 2：

Map(Text key，Text record){

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

}

Reduce(Text key，iter){

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

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

}

2 實(shí)驗(yàn)及結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境

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

2.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

2.3 結(jié)果分析

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

圖2 匹配閾值與運(yùn)行時(shí)間

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

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

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

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

圖3 節(jié)點(diǎn)數(shù)與運(yùn)行時(shí)間

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

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

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

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

3 結(jié)論

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

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

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