基于MapReduce與兩層相關(guān)性聚類的實(shí)體解析方法

王 寧，黃 敏

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044）

基于MapReduce與兩層相關(guān)性聚類的實(shí)體解析方法

王 寧，黃 敏

（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京100044）

兩層相關(guān)性聚類算法由于引入公共鄰居，在解析的正確性及抗噪聲能力方面性能較好。但該算法分兩層執(zhí)行，在時(shí)間效率上不具優(yōu)勢(shì)。為此，提出將該算法在MapReduce框架下實(shí)現(xiàn)，利用分布式計(jì)算提高其執(zhí)行效率。通過(guò)設(shè)計(jì)輔助文件減少內(nèi)存消耗以及中間數(shù)據(jù)的輸出，給出分布式環(huán)境下的塊更新規(guī)則，并改寫(xiě)第二層的調(diào)整塊算法，將需要實(shí)時(shí)更新的數(shù)據(jù)統(tǒng)一計(jì)算后，根據(jù)更為顯著的關(guān)聯(lián)特征進(jìn)行處理。實(shí)驗(yàn)結(jié)果表明，與TT算法和DTT算法相比，該方法不僅能保證解析的準(zhǔn)確性，而且在時(shí)間效率上也有大幅提高。

相關(guān)性聚類；MapReduce模型；實(shí)體解析；大數(shù)據(jù)；數(shù)據(jù)集成；分布式計(jì)算

1 概述

實(shí)體解析［1］是指對(duì)現(xiàn)實(shí)世界中同一實(shí)體的不同表現(xiàn)形式進(jìn)行識(shí)別、連接和分組，它在數(shù)據(jù)庫(kù)管理、數(shù)據(jù)集成、機(jī)器學(xué)習(xí)中都有廣泛的應(yīng)用。大數(shù)據(jù)時(shí)代的到來(lái)，使得人們?nèi)ネ诰驍?shù)據(jù)的潛在價(jià)值。

大數(shù)據(jù)具有數(shù)據(jù)量大、數(shù)據(jù)更新速度快、數(shù)據(jù)源多樣和數(shù)據(jù)存在噪聲等特點(diǎn)［2］。其中，數(shù)據(jù)噪聲會(huì)造成部分?jǐn)?shù)據(jù)關(guān)聯(lián)和依賴的假象。相關(guān)性聚類是實(shí)體解析的一種基本方法，文獻(xiàn)［3］基于對(duì)數(shù)據(jù)噪聲的處理提出了一種兩層相關(guān)性聚類算法，用于提高實(shí)體解析的質(zhì)量。

兩層相關(guān)性聚類算法分為預(yù)分塊和調(diào)整塊兩層。與傳統(tǒng)的相關(guān)性聚類算法相比，該算法在準(zhǔn)確率和召回率上占有一定的優(yōu)勢(shì)，然而由于分兩層實(shí)現(xiàn)，它在時(shí)間效率上不如傳統(tǒng)算法。MapReduce是一種編程模型，它被廣泛用于處理大規(guī)模的數(shù)據(jù)集。然而在MapReduce框架下進(jìn)行數(shù)據(jù)分析和操作時(shí)，數(shù)據(jù)節(jié)點(diǎn)之間不能通信，即數(shù)據(jù)在處理過(guò)程中不能實(shí)時(shí)更新也無(wú)法實(shí)現(xiàn)共享，因此需要對(duì)兩層相關(guān)性聚類算法進(jìn)行改造，將需要實(shí)時(shí)更新的數(shù)據(jù)統(tǒng)一計(jì)算后根據(jù)明顯的關(guān)聯(lián)特征進(jìn)行處理，以適應(yīng)分布式架構(gòu)。為提高大數(shù)據(jù)環(huán)境下兩層相關(guān)性聚類算法的執(zhí)行效率，本文提出將該算法在MapReduce模型下實(shí)現(xiàn)，通過(guò)分布式計(jì)算提高其效率。本文的主要工作如下：在MapReduce模型下實(shí)現(xiàn)兩層相關(guān)性聚類算法，并結(jié)合MapReduce模型特點(diǎn)，設(shè)計(jì)適合分布式環(huán)境和聚類方案的數(shù)據(jù)格式及輔助文件。設(shè)計(jì)分布式環(huán)境下的鄰居相似度計(jì)算方法，設(shè)計(jì)新的鄰居數(shù)據(jù)結(jié)構(gòu)，以減少中間數(shù)據(jù)量和內(nèi)存消耗，提高計(jì)算效率。提出新的關(guān)聯(lián)規(guī)則并重新設(shè)計(jì)調(diào)整塊算法，使其在不低于原方法準(zhǔn)確率、召回率的基礎(chǔ)上實(shí)現(xiàn)分布式處理，并從理論上證明該方法的收斂性。

2 相關(guān)工作

2.1 兩層相關(guān)性聚類算法

相關(guān)性聚類［4］是實(shí)體解析的一種基本方法，因其是NP-hard問(wèn)題，很多近似算法被提出，以pivot［5］和vote［6］最為典型。兩層相關(guān)性聚類方法［3］由兩層算法實(shí)現(xiàn)：上層算法基于鄰居關(guān)系對(duì)數(shù)據(jù)進(jìn)行粗糙、允許重疊的預(yù)分塊處理；下層算法通過(guò)引入核的概念，精確定義了記錄與塊之間的關(guān)聯(lián)程度，以便準(zhǔn)確地判斷記錄歸屬，進(jìn)而提高相關(guān)性聚類的準(zhǔn)確度。該方法由于引入鄰居關(guān)系，抗噪聲能力明顯提高。

公共鄰居和核：對(duì)于記錄i與記錄j，其公共鄰居為CN（i，j）=N（i）∩N（j），若i和j構(gòu)成的邊形成一個(gè)分類，則其公共鄰居CN（i，j）為該分類的核。

鄰居相似度：兩層相關(guān)性聚類算法使用余弦相似度來(lái)計(jì)算鄰居相似度：

預(yù)分塊算法：每次選取鄰居相似度最大的記錄對(duì)，將該記錄對(duì)的公共鄰居的鄰居作為一個(gè)類，并將該記錄對(duì)的公共鄰居作為該類的核。

記錄與塊的關(guān)聯(lián)程度：如果記錄i屬于某一個(gè)塊，那么它應(yīng)該與該塊的核有很強(qiáng)的關(guān)聯(lián)，Ri（c）表示記錄i與塊c的關(guān)聯(lián)程度，其中：

調(diào)整塊算法：預(yù)分塊得到的結(jié)果中含有許多重疊部分，調(diào)整塊算法依賴于記錄序列，對(duì)于某一個(gè)記錄，將它歸并到與其有最大關(guān)聯(lián)程度的塊中。

2.2 MapReduce框架以及實(shí)體解析

Hadoop［7］分布式系統(tǒng)架構(gòu)包括HDFS分布式文件系統(tǒng)和MapReduce編程模型兩部分。HDFS擁有對(duì)數(shù)據(jù)讀寫(xiě)的高吞吐率，因此適合構(gòu)建大數(shù)據(jù)集上的應(yīng)用。MapReduce是一個(gè)用于大數(shù)據(jù)量計(jì)算的編程模型，其應(yīng)用程序最基本的組成部分包括一個(gè)Mapper類和一個(gè)Reducer類。

在大數(shù)據(jù)環(huán)境中，實(shí)體解析是一項(xiàng)計(jì)算方法多樣、計(jì)算量繁重的工作。采用MapReduce框架提高其計(jì)算效率成為目前較流行的研究方向。Kolb等人基于MapReduce構(gòu)建了一個(gè)用于大型數(shù)據(jù)集的dedoop實(shí)體解析系統(tǒng)［8-9］，通過(guò)幾種先進(jìn)的負(fù)載平衡策略來(lái)提高系統(tǒng)性能［10］。文獻(xiàn)［11］提出一種基于MapReduce的三階段相似集合連接方案，有效地分割數(shù)據(jù)和平衡工作量，并減少跨記錄的數(shù)據(jù)復(fù)制。文獻(xiàn)［12］提出了一種新穎的實(shí)體解析方法用于刪除冗余數(shù)據(jù)，該方法基于分塊技術(shù)實(shí)現(xiàn)。

3 基于MapReduce的兩層相關(guān)性聚類算法

3.1 系統(tǒng)框架

圖1給出基于MapReduce的兩層相關(guān)性聚類方法的框架，分?jǐn)?shù)據(jù)準(zhǔn)備（統(tǒng)計(jì)鄰居和計(jì)算鄰居相似度）、預(yù)分塊、調(diào)整塊（關(guān)聯(lián)程度的計(jì)算和記錄的添加與刪除）3層。第2層預(yù)分塊仍保留之前的分塊方案，本文的工作主要針對(duì)數(shù)據(jù)準(zhǔn)備階段和調(diào)整塊階段實(shí)現(xiàn)。

圖1 基于MapReduce的兩層相關(guān)性聚類方法框架

修改后的調(diào)整塊為兩層迭代算法，需要證明其收斂性。在算法執(zhí)行過(guò)程中，每次迭代對(duì)每條記錄，將它從與其關(guān)聯(lián)程度低的塊中刪除，因此，只需證明每個(gè)記錄最終有且僅有一個(gè)塊與其相關(guān)聯(lián)，即記錄最終僅出現(xiàn)一次，便可證明該算法是收斂的。定理及其證明保證了算法的收斂性。

定理 對(duì)于給定的記錄集合I=｛I1，I2，…，Ii｝，I上的α個(gè)分塊集合C=｛c1，c2，…，cα｝，I中每條記錄在C上重復(fù)劃分次數(shù)的集合N=｛n_I1，m，n_I2，m，…，n_ Ii，m｝，其中，n_It，m表示記錄It（1≤t≤i）經(jīng)過(guò)m次迭代后被重復(fù)劃分的次數(shù)。當(dāng)?shù)鷐（1≤m≤α）次后，N=｛1，1，…，1｝，即每條記錄僅屬于唯一一個(gè)分塊。

證明：對(duì)于α個(gè)分塊，每個(gè)記錄最多被重復(fù)劃分α次。在本文算法中，每次迭代至少將一條被重復(fù)劃分的記錄從與其關(guān)聯(lián)程度低的塊中刪除，即對(duì)?nˉIt，m∈N（1≤n_It，m≤α），當(dāng)n_It，m＞1時(shí)，n_It，m+1=n_It，m-β（1≤β≤α）。每經(jīng)過(guò)一次迭代，被重復(fù)劃分的次數(shù)至少會(huì)減少一次。因此，?m（1≤m≤α），迭代m次后，N=｛1，1，…，1｝。

3.2 鄰居文件及鄰居相似度

3.2.1 鄰居文件

每一階段均需要使用鄰居信息，為了減少map到reduce的中間數(shù)據(jù)量，將鄰居信息作為一個(gè)獨(dú)立的文件，供各階段使用。獲取鄰居文件的輸入數(shù)據(jù)為僅包含正邊的無(wú)向圖，該無(wú)向圖由文獻(xiàn)［4］中的方法得到。

對(duì)于一個(gè)僅包含正邊的無(wú)向圖，以其邊作為輸入，以記錄id作為key值，統(tǒng)計(jì)每一個(gè)記錄的鄰居，獲取鄰居文件的過(guò)程如圖2所示。對(duì)于每一條邊序列，在map階段交換記錄id形成中間數(shù)據(jù)，在reduce階段，以每一個(gè)id值形成分組，統(tǒng)計(jì)鄰居，形成鄰居文件。鄰居文件的輸出格式設(shè)計(jì)如下：

（記錄id索引/記錄鄰居1/記錄鄰居2/……）

圖2 獲取鄰居文件的MapReduce過(guò)程

3.2.2 鄰居相似度計(jì)算

本文計(jì)算有正邊相連的2個(gè)記錄的鄰居相似度。對(duì)于每條邊，通過(guò)記錄id索引查找鄰居文件獲得鄰居，計(jì)算鄰居相似度，算法過(guò)程如下：

算法1 鄰居相似度計(jì)算

鄰居相似度的計(jì)算采用MapReduce模型，主節(jié)點(diǎn)將鄰居文件上傳到緩存供各從節(jié)點(diǎn)下載使用，從緩存獲得鄰居文件的部分在map類的setup函數(shù)中實(shí)現(xiàn)（1行～3行），之后在map函數(shù)中通過(guò)id索引查詢鄰居文件，獲得鄰居信息并計(jì)算鄰居相似度（5行～8行），再通過(guò)reduce函數(shù)輸出（9行～10行）。

3.3 調(diào)整塊

原有的調(diào)整塊算法每將一個(gè)節(jié)點(diǎn)歸于某一個(gè)分塊或從某一個(gè)分塊中刪除，將會(huì)及時(shí)更新其他記錄與所在塊的關(guān)聯(lián)程度。然而，基于MapReduce的算法無(wú)法實(shí)時(shí)對(duì)數(shù)據(jù)進(jìn)行更新，因此采用迭代的方式對(duì)數(shù)據(jù)進(jìn)行處理，并盡可能地在一次迭代中處理更多的數(shù)據(jù)，以減少迭代次數(shù)。因此，本文定義了最大關(guān)聯(lián)程度、最小關(guān)聯(lián)程度、最大關(guān)聯(lián)塊和最小關(guān)聯(lián)塊來(lái)幫助判斷記錄的歸屬（定義1、定義2），并定義了相關(guān)運(yùn)算來(lái)操作塊中記錄的添加和刪除（定義3），同時(shí)為運(yùn)算提供判斷標(biāo)準(zhǔn)（定義4）。

定義1 對(duì)于記錄i以及與其相關(guān)聯(lián)的塊bK，表示i與bK的關(guān)聯(lián)程度。記錄i的最大關(guān)聯(lián)程度定義為i與其所關(guān)聯(lián)塊的關(guān)聯(lián)程度的最大值，記作maχ_c（i）；記錄i的最小關(guān)聯(lián)程度定義為i與其所關(guān)聯(lián)塊的關(guān)聯(lián)程度的最小值，記作m in_c（i）。即：定義2 對(duì)于記錄i，記錄i的最小關(guān)聯(lián)塊定義為與i有最小關(guān)聯(lián)程度的塊，記作min_b（i）；記錄i的最大關(guān)聯(lián)塊定義為與i有最大關(guān)聯(lián)程度的塊，記作maχ_b（i）。

定義3 設(shè)分塊C由非核記錄集C1和核的記錄集C2組成，記作C=｛C1，C2｝，其中C1=｛I1，I2，…，Ii｝，C2=｛Ii+1，Ii+2，…，IK｝。定義非核記錄It（1≤t≤i）對(duì)C的依附為C⊕It，C對(duì)記錄In（1≤n≤K）的排斥為C?In，其中：

定義4 給定記錄集合I=｛I1，I2，…，Ii｝和α個(gè)分塊集合C=｛c1，c2，…，cα｝，A表示與記錄進(jìn)行依附操作形成的新塊，B表示與記錄進(jìn)行排斥操作形成的新塊。對(duì)某條記錄It（1≤t≤i）及其所有關(guān)聯(lián)的塊cm（1≤m≤α），分布式環(huán)境下的塊更新規(guī)則定義如下：

（1）當(dāng)maχ_c（It）≠min_c（It）時(shí)，若min_c（It）＞0，則A=maχ_b｛It｝⊕It，B=min_b｛It｝?It；若若則

（2）當(dāng)maχ_c（It）=min_c（It） 時(shí)，若則

3.3.1 分布式壞境下的調(diào)整塊算法

調(diào)整塊分MR階段和內(nèi)存階段兩部分執(zhí)行。首先將預(yù)分塊P表示成＜key，value＞對(duì)的形式代入MR階段計(jì)算。調(diào)整塊算法的總循環(huán)如下：

算法2 調(diào)整塊算法總循環(huán)

對(duì)于預(yù)分塊階段產(chǎn)生的粗糙的、有重疊的分塊P，每一次循環(huán)都將計(jì)算記錄與所在塊的關(guān)聯(lián)程度，并根據(jù)關(guān)聯(lián)規(guī)則輸出處理文件（7行），在內(nèi)存中進(jìn)行添加和刪除（8行），當(dāng)每個(gè)記錄均只出現(xiàn)一次時(shí)，循環(huán)結(jié)束，此時(shí)可得到無(wú)重疊的分塊結(jié)果（9行）。

MR階段采用MapReduce模型實(shí)現(xiàn)，具體算法如下：

算法3 調(diào)整塊算法MR階段

Map函數(shù)通過(guò)鄰居信息和塊信息計(jì)算記錄與所在塊的關(guān)聯(lián)程度（5行～6行），并將結(jié)果以（記錄id，塊id/記錄與塊的關(guān)聯(lián)程度）的形式輸出（7行～8行）；reduce函數(shù)用于輸出需處理的記錄信息，map函數(shù)的輸出數(shù)據(jù)會(huì)將相同key值（記錄id）的數(shù)據(jù)合并，因此，首先找到每一個(gè)id的最大關(guān)聯(lián)程度、最小關(guān)聯(lián)程度、最大關(guān)聯(lián)塊、最小關(guān)聯(lián)塊及關(guān)聯(lián)程度小于0的記錄和所在塊的信息，存于待處理列表中（10行），再根據(jù)關(guān)聯(lián)規(guī)則進(jìn)行判斷（11行），最后從待處理列表中獲得每一個(gè)記錄的當(dāng)前重復(fù)次數(shù)（12行），再將信息整理后輸出（13行）。

3.3.2 調(diào)整塊算法的后處理

改進(jìn)后的調(diào)整塊算法很好地解決了MR中不能實(shí)時(shí)更新數(shù)據(jù)的問(wèn)題。但每一個(gè)記錄被重復(fù)劃分的次數(shù)不同，其迭代停止的順序也不同，這會(huì)導(dǎo)致許多單一記錄的產(chǎn)生。為了減少單一記錄形成的分塊，對(duì)分塊后的結(jié)果進(jìn)行再處理：首先，計(jì)算結(jié)果中單一記錄與其他各塊的關(guān)聯(lián)程度；然后，獲得與該單一記錄有最大關(guān)聯(lián)程度的分塊，若最大關(guān)聯(lián)程度大于0，則將該記錄加入到對(duì)應(yīng)的分塊中。

4 實(shí)驗(yàn)與評(píng)估

4.1 實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)部署的分布式環(huán)境由3個(gè)節(jié)點(diǎn)構(gòu)成，其中2個(gè)節(jié)點(diǎn)（1臺(tái)為主節(jié)點(diǎn)）為內(nèi)存16 GB，CPU 2.93 GHz，硬盤1 TB的Dell服務(wù)器，另外1個(gè)節(jié)點(diǎn)為內(nèi)存4 GB，CPU 2.73 GHz，硬盤1 TB的Dell服務(wù)器。實(shí)驗(yàn)所用的算法是在hadoop2.20.0和jdk1.7.0_06環(huán)境下實(shí)現(xiàn)的。

由于沒(méi)有合適規(guī)模的真實(shí)數(shù)據(jù)集，將cora數(shù)據(jù)集擴(kuò)大相應(yīng)的倍數(shù)，并增加數(shù)據(jù)噪聲形成實(shí)驗(yàn)數(shù)據(jù)集。Cora數(shù)據(jù)集包含對(duì)112篇不同文章的1 295個(gè)引用，共1 295×（1 295-1）/2=837 865個(gè)記錄對(duì)，擴(kuò)大數(shù)據(jù)集后，記錄對(duì)的數(shù)量已達(dá)到107數(shù)量級(jí)。

4.2 實(shí)驗(yàn)評(píng)估標(biāo)準(zhǔn)

準(zhǔn)確率、召回率和F-值常用于評(píng)估聚類算法，在非分布式環(huán)境下，兩層相關(guān)性聚類算法在這3個(gè)值上均優(yōu)于傳統(tǒng)算法。為適應(yīng)分布式環(huán)境，對(duì)調(diào)整塊算法進(jìn)行了改進(jìn)，因此需保證改進(jìn)后的算法在時(shí)間效率提高的基礎(chǔ)上，準(zhǔn)確率、召回率和F值均不低于原方法的評(píng)估結(jié)果。

4.3 實(shí)驗(yàn)結(jié)果與分析

4.3.1 有效性

為方便比較，稱原有的二層相關(guān)性聚類算法為Two-Tiered（TT），分布式環(huán)境下的改進(jìn)算法為DTwo-Tiered（DTT），經(jīng)過(guò)后處理的算法為DP-Tw o-Tiered（DPTT）。從表1可以看出，對(duì)于規(guī)模不大的cora數(shù)據(jù)集，DTT與TT相比，召回率比較高，準(zhǔn)確率偏低，綜合后的F值基本持平。

表1 DTT與TT在Cora數(shù)據(jù)集上的聚類效果對(duì)比

隨著數(shù)據(jù)量增加，DTT算法在這3個(gè)評(píng)價(jià)指標(biāo)上出現(xiàn)了變化：準(zhǔn)確率較高，基本保持在0.95以上，召回率卻在0.7徘徊，F(xiàn)值基本穩(wěn)定在0.8左右，如圖3所示。對(duì)結(jié)果中出現(xiàn)的單一記錄進(jìn)行再處理后（DPTT），在保持高的準(zhǔn)確率的基礎(chǔ)上，召回率和F值都有所提高，如圖4所示。

圖3 DTT的準(zhǔn)確率、召回率和F值隨數(shù)據(jù)量變化的情況

圖4 DTT與DPTT的結(jié)果有效性比較

4.3.2 時(shí)間效率

MapReduce模型的最大優(yōu)勢(shì)在于它能夠處理大數(shù)據(jù)量的運(yùn)算。與TT算法相比，DTT算法盡管采取迭代的方式進(jìn)行處理，但每迭代一次，計(jì)算量便會(huì)降低，且Hadoop自帶的文件系統(tǒng)具有較高的文件讀寫(xiě)速度，在查詢時(shí)間上占有優(yōu)勢(shì)。

圖5給出了調(diào)整塊階段運(yùn)行的總時(shí)間。隨數(shù)據(jù)量的增加，運(yùn)行總時(shí)間呈現(xiàn)比較平緩的增長(zhǎng)趨勢(shì)，但隨Hadoop節(jié)點(diǎn)數(shù)的增加，總時(shí)間在大幅降低。

圖5 數(shù)據(jù)量與運(yùn)行時(shí)間的關(guān)系

圖6 給出了平均運(yùn)行時(shí)間與迭代次數(shù)及Hadoop結(jié)點(diǎn)數(shù)的關(guān)系，其中，迭代次數(shù)對(duì)應(yīng)圖5中的數(shù)據(jù)量增長(zhǎng)。隨數(shù)據(jù)量的增加，記錄間的關(guān)聯(lián)關(guān)系變復(fù)雜，記錄被重復(fù)劃分的次數(shù)便會(huì)增加，因此，程序運(yùn)行的迭代次數(shù)也會(huì)增加，見(jiàn)圖6。但各節(jié)點(diǎn)數(shù)下，每個(gè)job的平均運(yùn)行時(shí)間基本保持穩(wěn)定或有小幅增長(zhǎng)，而對(duì)于最后2個(gè)同為108次迭代次數(shù)的5×107和6×107數(shù)據(jù)量，盡管后者的計(jì)算量遠(yuǎn)多于前者，但平均運(yùn)行時(shí)間的差值卻不大，說(shuō)明本文算法能很好地適應(yīng)分布式環(huán)境。

圖6 平均運(yùn)行時(shí)間與迭代次數(shù)及HadooP節(jié)點(diǎn)數(shù)的關(guān)系

5 結(jié)束語(yǔ)

在大數(shù)據(jù)壞境下，實(shí)體解析的算法不僅要求解析結(jié)果的正確性，同時(shí)也要確保較低的時(shí)間復(fù)雜度。本文基于MapReduce編程模型實(shí)現(xiàn)兩層相關(guān)性聚類算法，通過(guò)將調(diào)整塊算法改為兩層迭代模型，使其能適應(yīng)分布式環(huán)境，在保證解析質(zhì)量的基礎(chǔ)上，時(shí)間效率也大幅提高。今后考慮將預(yù)分塊算法在分布式框架上實(shí)現(xiàn)，以減少對(duì)內(nèi)存的依賴。預(yù)分塊算法的修改涉及到數(shù)據(jù)的劃分和實(shí)時(shí)更新問(wèn)題。此外，將針對(duì)調(diào)整塊迭代算法中的數(shù)據(jù)特點(diǎn)，調(diào)整關(guān)聯(lián)規(guī)則以減少算法的迭代次數(shù)，同時(shí)，設(shè)計(jì)適合調(diào)整塊的負(fù)載平衡策略，進(jìn)一步減少調(diào)整塊的運(yùn)行時(shí)間。

［1］ Lise G，Machanavajjhala A.Entity Resolution for Big Data［C］//Proceedings of the 19th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining.New York，USA：ACM Press，2013：214-222.

［2］ 維克托·邁爾·舍恩伯格，肯尼思·庫(kù)克耶.大數(shù)據(jù)時(shí)代［M］.盛陽(yáng)燕，周 濤，譯.杭州：浙江人民出版社，2012.

［3］ 王 寧，李 杰.大數(shù)據(jù)環(huán)境下用于實(shí)體解析的兩層相關(guān)性聚類算法［J］.計(jì)算機(jī)研究與發(fā)展，2014，51（9）：2108-2116.

［4］ Bansal N，Blum A，Chaw la S.Correlation Clustering［J］.Machine Learning，2004，56（1-3）：89-113.

［5］ Ailon N，Charikar M，Newman A.Aggregating Inconsistent Information：Ranking and Clustering［J］. Journal of the ACM，2008，55（5）：23-28.

［6］ Elsner M，Chamiak E.You Talking to M e？A Corpus and Algorithm for Conversation Disentanglement［C］// Proceedings of ACL'08.New York，USA：ACM Press，2008：834-842.

［7］ Hadoop［EB/OL］.（2014-08-18）.http：//hadoop. apache.org/.

［8］ Kolb L，Andreas T，Erhard R.Paralell Entity Resolution with Dedoop［J］.Datanbank-Spectum，2013，13（1）：23-32.

［9］ Kolb L，Andreas T，Erhard R.Dedoop：Efficient Deduplication with Hadoop［J］.Proceedings of the VLDB Endowment，2012，5（12）：1878-1881.

［10］ Kolb L，Andreas T，Erhard R.Load Balancing for MapReduce-based Entity Resolution［C］//Proceedings of ACM ICDE'12.New York，USA：ACM Press，2012：618-629.

［11］ Vernica E，Carey M J，Li Chen.Efficient Parallel Setsimilarity Joins Using MapReduce［C］//Proceedings of 2010 ACM SIGMOD International Conference on Management of Data.New York，USA：ACM Press，2010：156-165.

［12］ George P.Eliminating the Redundancy in Blockingbased Entity Resolution Methods［C］//Proceedings of the 11th Annual International ACM/IEEE Joint Conference on Digital Libraries.New York，USA：ACM Press，2011：325-335.

編輯 索書(shū)志

Entity Resolution Method Based on MapReduce and Two-tiered Correlation Clustering

WANG Ning，HUANG Min
（School of Computer and Inform ation Technology，Beijing Jiaotong University，Beijing 100044，China）

Correlation clustering is a basic method for entity resolution.By introducing the concept of common neighborhood into the correlation clustering problem，two-tiered correlation clustering method is superior to traditional approaches in term of accuracy and noise immunity.However，this method is not time efficient because of its two-tiered architecture.In order to im prove its efficiency in big data environment，this paper proposes a two-tiered correlation clustering method based on Map Reduce.Some auxiliary files are designed to decrease memory consumption and intermediate data output.New correlation rules for ad justing blocks are proposed and adjustment algorithm in bottom tier is redesigned so that block adjustment can be processed according to the most salient correlation features.Experimental results show that the resolution method is not only accurate but also time efficient for big data.

correlation clustering；MapReducemodel；entity resolution；big data；data integration；distributed Computing

10.3969/j.issn.1000-3428.2015.09.014

王 寧，黃 敏.基于MapReduce與兩層相關(guān)性聚類的實(shí)體解析方法［J］.計(jì)算機(jī)工程，2015，41（9）：80-84，91.

英文引用格式：W ang Ning，Huang M in.Entity Resolution Method Based on MapReduce and Two-tiered Correlation Clustering［J］.Computer Engineering，2015，41（9）：80-84，91.

1000-3428（2015）09-0080-05

A

TP391

國(guó)家自然科學(xué)基金資助項(xiàng)目（61370060）；江蘇省自然科學(xué)基金資助項(xiàng)目（BK 2011454）。

王 寧（1967-），女，副教授、博士，主研方向：Web數(shù)據(jù)集成，大數(shù)據(jù)管理，數(shù)據(jù)挖掘；黃 敏，碩士研究生。

2014-09-02

2014-11-04 E-m ail：nw ang@bjut.edu.cn