王 寧,黃 敏
(北京交通大學計算機與信息技術(shù)學院,北京100044)
基于MapReduce與兩層相關(guān)性聚類的實體解析方法
王 寧,黃 敏
(北京交通大學計算機與信息技術(shù)學院,北京100044)
兩層相關(guān)性聚類算法由于引入公共鄰居,在解析的正確性及抗噪聲能力方面性能較好。但該算法分兩層執(zhí)行,在時間效率上不具優(yōu)勢。為此,提出將該算法在MapReduce框架下實現(xiàn),利用分布式計算提高其執(zhí)行效率。通過設(shè)計輔助文件減少內(nèi)存消耗以及中間數(shù)據(jù)的輸出,給出分布式環(huán)境下的塊更新規(guī)則,并改寫第二層的調(diào)整塊算法,將需要實時更新的數(shù)據(jù)統(tǒng)一計算后,根據(jù)更為顯著的關(guān)聯(lián)特征進行處理。實驗結(jié)果表明,與TT算法和DTT算法相比,該方法不僅能保證解析的準確性,而且在時間效率上也有大幅提高。
相關(guān)性聚類;MapReduce模型;實體解析;大數(shù)據(jù);數(shù)據(jù)集成;分布式計算
實體解析[1]是指對現(xiàn)實世界中同一實體的不同表現(xiàn)形式進行識別、連接和分組,它在數(shù)據(jù)庫管理、數(shù)據(jù)集成、機器學習中都有廣泛的應(yīng)用。大數(shù)據(jù)時代的到來,使得人們?nèi)ネ诰驍?shù)據(jù)的潛在價值。
大數(shù)據(jù)具有數(shù)據(jù)量大、數(shù)據(jù)更新速度快、數(shù)據(jù)源多樣和數(shù)據(jù)存在噪聲等特點[2]。其中,數(shù)據(jù)噪聲會造成部分數(shù)據(jù)關(guān)聯(lián)和依賴的假象。相關(guān)性聚類是實體解析的一種基本方法,文獻[3]基于對數(shù)據(jù)噪聲的處理提出了一種兩層相關(guān)性聚類算法,用于提高實體解析的質(zhì)量。
兩層相關(guān)性聚類算法分為預(yù)分塊和調(diào)整塊兩層。與傳統(tǒng)的相關(guān)性聚類算法相比,該算法在準確率和召回率上占有一定的優(yōu)勢,然而由于分兩層實現(xiàn),它在時間效率上不如傳統(tǒng)算法。MapReduce是一種編程模型,它被廣泛用于處理大規(guī)模的數(shù)據(jù)集。然而在MapReduce框架下進行數(shù)據(jù)分析和操作時,數(shù)據(jù)節(jié)點之間不能通信,即數(shù)據(jù)在處理過程中不能實時更新也無法實現(xiàn)共享,因此需要對兩層相關(guān)性聚類算法進行改造,將需要實時更新的數(shù)據(jù)統(tǒng)一計算后根據(jù)明顯的關(guān)聯(lián)特征進行處理,以適應(yīng)分布式架構(gòu)。為提高大數(shù)據(jù)環(huán)境下兩層相關(guān)性聚類算法的執(zhí)行效率,本文提出將該算法在MapReduce模型下實現(xiàn),通過分布式計算提高其效率。本文的主要工作如下:在MapReduce模型下實現(xiàn)兩層相關(guān)性聚類算法,并結(jié)合MapReduce模型特點,設(shè)計適合分布式環(huán)境和聚類方案的數(shù)據(jù)格式及輔助文件。設(shè)計分布式環(huán)境下的鄰居相似度計算方法,設(shè)計新的鄰居數(shù)據(jù)結(jié)構(gòu),以減少中間數(shù)據(jù)量和內(nèi)存消耗,提高計算效率。提出新的關(guān)聯(lián)規(guī)則并重新設(shè)計調(diào)整塊算法,使其在不低于原方法準確率、召回率的基礎(chǔ)上實現(xiàn)分布式處理,并從理論上證明該方法的收斂性。
2.1 兩層相關(guān)性聚類算法
相關(guān)性聚類[4]是實體解析的一種基本方法,因其是NP-hard問題,很多近似算法被提出,以pivot[5]和vote[6]最為典型。兩層相關(guān)性聚類方法[3]由兩層算法實現(xiàn):上層算法基于鄰居關(guān)系對數(shù)據(jù)進行粗糙、允許重疊的預(yù)分塊處理;下層算法通過引入核的概念,精確定義了記錄與塊之間的關(guān)聯(lián)程度,以便準確地判斷記錄歸屬,進而提高相關(guān)性聚類的準確度。該方法由于引入鄰居關(guān)系,抗噪聲能力明顯提高。
公共鄰居和核:對于記錄i與記錄j,其公共鄰居為CN(i,j)=N(i)∩N(j),若i和j構(gòu)成的邊形成一個分類,則其公共鄰居CN(i,j)為該分類的核。
鄰居相似度:兩層相關(guān)性聚類算法使用余弦相似度來計算鄰居相似度:
預(yù)分塊算法:每次選取鄰居相似度最大的記錄對,將該記錄對的公共鄰居的鄰居作為一個類,并將該記錄對的公共鄰居作為該類的核。
記錄與塊的關(guān)聯(lián)程度:如果記錄i屬于某一個塊,那么它應(yīng)該與該塊的核有很強的關(guān)聯(lián),Ri(c)表示記錄i與塊c的關(guān)聯(lián)程度,其中:
調(diào)整塊算法:預(yù)分塊得到的結(jié)果中含有許多重疊部分,調(diào)整塊算法依賴于記錄序列,對于某一個記錄,將它歸并到與其有最大關(guān)聯(lián)程度的塊中。
2.2 MapReduce框架以及實體解析
Hadoop[7]分布式系統(tǒng)架構(gòu)包括HDFS分布式文件系統(tǒng)和MapReduce編程模型兩部分。HDFS擁有對數(shù)據(jù)讀寫的高吞吐率,因此適合構(gòu)建大數(shù)據(jù)集上的應(yīng)用。MapReduce是一個用于大數(shù)據(jù)量計算的編程模型,其應(yīng)用程序最基本的組成部分包括一個Mapper類和一個Reducer類。
在大數(shù)據(jù)環(huán)境中,實體解析是一項計算方法多樣、計算量繁重的工作。采用MapReduce框架提高其計算效率成為目前較流行的研究方向。Kolb等人基于MapReduce構(gòu)建了一個用于大型數(shù)據(jù)集的dedoop實體解析系統(tǒng)[8-9],通過幾種先進的負載平衡策略來提高系統(tǒng)性能[10]。文獻[11]提出一種基于MapReduce的三階段相似集合連接方案,有效地分割數(shù)據(jù)和平衡工作量,并減少跨記錄的數(shù)據(jù)復(fù)制。文獻[12]提出了一種新穎的實體解析方法用于刪除冗余數(shù)據(jù),該方法基于分塊技術(shù)實現(xiàn)。
3.1 系統(tǒng)框架
圖1給出基于MapReduce的兩層相關(guān)性聚類方法的框架,分數(shù)據(jù)準備(統(tǒng)計鄰居和計算鄰居相似度)、預(yù)分塊、調(diào)整塊(關(guān)聯(lián)程度的計算和記錄的添加與刪除)3層。第2層預(yù)分塊仍保留之前的分塊方案,本文的工作主要針對數(shù)據(jù)準備階段和調(diào)整塊階段實現(xiàn)。
圖1 基于MapReduce的兩層相關(guān)性聚類方法框架
修改后的調(diào)整塊為兩層迭代算法,需要證明其收斂性。在算法執(zhí)行過程中,每次迭代對每條記錄,將它從與其關(guān)聯(lián)程度低的塊中刪除,因此,只需證明每個記錄最終有且僅有一個塊與其相關(guān)聯(lián),即記錄最終僅出現(xiàn)一次,便可證明該算法是收斂的。定理及其證明保證了算法的收斂性。
定理 對于給定的記錄集合I={I1,I2,…,Ii},I上的α個分塊集合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)過m次迭代后被重復(fù)劃分的次數(shù)。當?shù)鷐(1≤m≤α)次后,N={1,1,…,1},即每條記錄僅屬于唯一一個分塊。
證明:對于α個分塊,每個記錄最多被重復(fù)劃分α次。在本文算法中,每次迭代至少將一條被重復(fù)劃分的記錄從與其關(guān)聯(lián)程度低的塊中刪除,即對?nˉIt,m∈N(1≤n_It,m≤α),當n_It,m>1時,n_It,m+1=n_It,m-β(1≤β≤α)。每經(jīng)過一次迭代,被重復(fù)劃分的次數(shù)至少會減少一次。因此,?m(1≤m≤α),迭代m次后,N={1,1,…,1}。
3.2 鄰居文件及鄰居相似度
3.2.1 鄰居文件
每一階段均需要使用鄰居信息,為了減少map到reduce的中間數(shù)據(jù)量,將鄰居信息作為一個獨立的文件,供各階段使用。獲取鄰居文件的輸入數(shù)據(jù)為僅包含正邊的無向圖,該無向圖由文獻[4]中的方法得到。
對于一個僅包含正邊的無向圖,以其邊作為輸入,以記錄id作為key值,統(tǒng)計每一個記錄的鄰居,獲取鄰居文件的過程如圖2所示。對于每一條邊序列,在map階段交換記錄id形成中間數(shù)據(jù),在reduce階段,以每一個id值形成分組,統(tǒng)計鄰居,形成鄰居文件。鄰居文件的輸出格式設(shè)計如下:
(記錄id索引/記錄鄰居1/記錄鄰居2/……)
圖2 獲取鄰居文件的MapReduce過程
3.2.2 鄰居相似度計算
本文計算有正邊相連的2個記錄的鄰居相似度。對于每條邊,通過記錄id索引查找鄰居文件獲得鄰居,計算鄰居相似度,算法過程如下:
算法1 鄰居相似度計算
鄰居相似度的計算采用MapReduce模型,主節(jié)點將鄰居文件上傳到緩存供各從節(jié)點下載使用,從緩存獲得鄰居文件的部分在map類的setup函數(shù)中實現(xiàn)(1行~3行),之后在map函數(shù)中通過id索引查詢鄰居文件,獲得鄰居信息并計算鄰居相似度(5行~8行),再通過reduce函數(shù)輸出(9行~10行)。
3.3 調(diào)整塊
原有的調(diào)整塊算法每將一個節(jié)點歸于某一個分塊或從某一個分塊中刪除,將會及時更新其他記錄與所在塊的關(guān)聯(lián)程度。然而,基于MapReduce的算法無法實時對數(shù)據(jù)進行更新,因此采用迭代的方式對數(shù)據(jù)進行處理,并盡可能地在一次迭代中處理更多的數(shù)據(jù),以減少迭代次數(shù)。因此,本文定義了最大關(guān)聯(lián)程度、最小關(guān)聯(lián)程度、最大關(guān)聯(lián)塊和最小關(guān)聯(lián)塊來幫助判斷記錄的歸屬(定義1、定義2),并定義了相關(guān)運算來操作塊中記錄的添加和刪除(定義3),同時為運算提供判斷標準(定義4)。
定義1 對于記錄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 對于記錄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)對C的依附為C⊕It,C對記錄In(1≤n≤K)的排斥為C?In,其中:
定義4 給定記錄集合I={I1,I2,…,Ii}和α個分塊集合C={c1,c2,…,cα},A表示與記錄進行依附操作形成的新塊,B表示與記錄進行排斥操作形成的新塊。對某條記錄It(1≤t≤i)及其所有關(guān)聯(lián)的塊cm(1≤m≤α),分布式環(huán)境下的塊更新規(guī)則定義如下:
(1)當maχ_c(It)≠min_c(It)時,若min_c(It)>0,則A=maχ_b{It}⊕It,B=min_b{It}?It;若若則
(2)當maχ_c(It)=min_c(It) 時,若則
3.3.1 分布式壞境下的調(diào)整塊算法
調(diào)整塊分MR階段和內(nèi)存階段兩部分執(zhí)行。首先將預(yù)分塊P表示成<key,value>對的形式代入MR階段計算。調(diào)整塊算法的總循環(huán)如下:
算法2 調(diào)整塊算法總循環(huán)
對于預(yù)分塊階段產(chǎn)生的粗糙的、有重疊的分塊P,每一次循環(huán)都將計算記錄與所在塊的關(guān)聯(lián)程度,并根據(jù)關(guān)聯(lián)規(guī)則輸出處理文件(7行),在內(nèi)存中進行添加和刪除(8行),當每個記錄均只出現(xiàn)一次時,循環(huán)結(jié)束,此時可得到無重疊的分塊結(jié)果(9行)。
MR階段采用MapReduce模型實現(xiàn),具體算法如下:
算法3 調(diào)整塊算法MR階段
Map函數(shù)通過鄰居信息和塊信息計算記錄與所在塊的關(guān)聯(lián)程度(5行~6行),并將結(jié)果以(記錄id,塊id/記錄與塊的關(guān)聯(lián)程度)的形式輸出(7行~8行);reduce函數(shù)用于輸出需處理的記錄信息,map函數(shù)的輸出數(shù)據(jù)會將相同key值(記錄id)的數(shù)據(jù)合并,因此,首先找到每一個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ī)則進行判斷(11行),最后從待處理列表中獲得每一個記錄的當前重復(fù)次數(shù)(12行),再將信息整理后輸出(13行)。
3.3.2 調(diào)整塊算法的后處理
改進后的調(diào)整塊算法很好地解決了MR中不能實時更新數(shù)據(jù)的問題。但每一個記錄被重復(fù)劃分的次數(shù)不同,其迭代停止的順序也不同,這會導(dǎo)致許多單一記錄的產(chǎn)生。為了減少單一記錄形成的分塊,對分塊后的結(jié)果進行再處理:首先,計算結(jié)果中單一記錄與其他各塊的關(guān)聯(lián)程度;然后,獲得與該單一記錄有最大關(guān)聯(lián)程度的分塊,若最大關(guān)聯(lián)程度大于0,則將該記錄加入到對應(yīng)的分塊中。
4.1 實驗環(huán)境和實驗數(shù)據(jù)
實驗部署的分布式環(huán)境由3個節(jié)點構(gòu)成,其中2個節(jié)點(1臺為主節(jié)點)為內(nèi)存16 GB,CPU 2.93 GHz,硬盤1 TB的Dell服務(wù)器,另外1個節(jié)點為內(nèi)存4 GB,CPU 2.73 GHz,硬盤1 TB的Dell服務(wù)器。實驗所用的算法是在hadoop2.20.0和jdk1.7.0_06環(huán)境下實現(xiàn)的。
由于沒有合適規(guī)模的真實數(shù)據(jù)集,將cora數(shù)據(jù)集擴大相應(yīng)的倍數(shù),并增加數(shù)據(jù)噪聲形成實驗數(shù)據(jù)集。Cora數(shù)據(jù)集包含對112篇不同文章的1 295個引用,共1 295×(1 295-1)/2=837 865個記錄對,擴大數(shù)據(jù)集后,記錄對的數(shù)量已達到107數(shù)量級。
4.2 實驗評估標準
準確率、召回率和F-值常用于評估聚類算法,在非分布式環(huán)境下,兩層相關(guān)性聚類算法在這3個值上均優(yōu)于傳統(tǒng)算法。為適應(yīng)分布式環(huán)境,對調(diào)整塊算法進行了改進,因此需保證改進后的算法在時間效率提高的基礎(chǔ)上,準確率、召回率和F值均不低于原方法的評估結(jié)果。
4.3 實驗結(jié)果與分析
4.3.1 有效性
為方便比較,稱原有的二層相關(guān)性聚類算法為Two-Tiered(TT),分布式環(huán)境下的改進算法為DTwo-Tiered(DTT),經(jīng)過后處理的算法為DP-Tw o-Tiered(DPTT)。從表1可以看出,對于規(guī)模不大的cora數(shù)據(jù)集,DTT與TT相比,召回率比較高,準確率偏低,綜合后的F值基本持平。
表1 DTT與TT在Cora數(shù)據(jù)集上的聚類效果對比
隨著數(shù)據(jù)量增加,DTT算法在這3個評價指標上出現(xiàn)了變化:準確率較高,基本保持在0.95以上,召回率卻在0.7徘徊,F(xiàn)值基本穩(wěn)定在0.8左右,如圖3所示。對結(jié)果中出現(xiàn)的單一記錄進行再處理后(DPTT),在保持高的準確率的基礎(chǔ)上,召回率和F值都有所提高,如圖4所示。
圖3 DTT的準確率、召回率和F值隨數(shù)據(jù)量變化的情況
圖4 DTT與DPTT的結(jié)果有效性比較
4.3.2 時間效率
MapReduce模型的最大優(yōu)勢在于它能夠處理大數(shù)據(jù)量的運算。與TT算法相比,DTT算法盡管采取迭代的方式進行處理,但每迭代一次,計算量便會降低,且Hadoop自帶的文件系統(tǒng)具有較高的文件讀寫速度,在查詢時間上占有優(yōu)勢。
圖5給出了調(diào)整塊階段運行的總時間。隨數(shù)據(jù)量的增加,運行總時間呈現(xiàn)比較平緩的增長趨勢,但隨Hadoop節(jié)點數(shù)的增加,總時間在大幅降低。
圖5 數(shù)據(jù)量與運行時間的關(guān)系
圖6 給出了平均運行時間與迭代次數(shù)及Hadoop結(jié)點數(shù)的關(guān)系,其中,迭代次數(shù)對應(yīng)圖5中的數(shù)據(jù)量增長。隨數(shù)據(jù)量的增加,記錄間的關(guān)聯(lián)關(guān)系變復(fù)雜,記錄被重復(fù)劃分的次數(shù)便會增加,因此,程序運行的迭代次數(shù)也會增加,見圖6。但各節(jié)點數(shù)下,每個job的平均運行時間基本保持穩(wěn)定或有小幅增長,而對于最后2個同為108次迭代次數(shù)的5×107和6×107數(shù)據(jù)量,盡管后者的計算量遠多于前者,但平均運行時間的差值卻不大,說明本文算法能很好地適應(yīng)分布式環(huán)境。
圖6 平均運行時間與迭代次數(shù)及HadooP節(jié)點數(shù)的關(guān)系
在大數(shù)據(jù)壞境下,實體解析的算法不僅要求解析結(jié)果的正確性,同時也要確保較低的時間復(fù)雜度。本文基于MapReduce編程模型實現(xiàn)兩層相關(guān)性聚類算法,通過將調(diào)整塊算法改為兩層迭代模型,使其能適應(yīng)分布式環(huán)境,在保證解析質(zhì)量的基礎(chǔ)上,時間效率也大幅提高。今后考慮將預(yù)分塊算法在分布式框架上實現(xiàn),以減少對內(nèi)存的依賴。預(yù)分塊算法的修改涉及到數(shù)據(jù)的劃分和實時更新問題。此外,將針對調(diào)整塊迭代算法中的數(shù)據(jù)特點,調(diào)整關(guān)聯(lián)規(guī)則以減少算法的迭代次數(shù),同時,設(shè)計適合調(diào)整塊的負載平衡策略,進一步減少調(diào)整塊的運行時間。
[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] 維克托·邁爾·舍恩伯格,肯尼思·庫克耶.大數(shù)據(jù)時代[M].盛陽燕,周 濤,譯.杭州:浙江人民出版社,2012.
[3] 王 寧,李 杰.大數(shù)據(jù)環(huán)境下用于實體解析的兩層相關(guān)性聚類算法[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.
編輯 索書志
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)性聚類的實體解析方法[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
國家自然科學基金資助項目(61370060);江蘇省自然科學基金資助項目(BK 2011454)。
王 寧(1967-),女,副教授、博士,主研方向:Web數(shù)據(jù)集成,大數(shù)據(jù)管理,數(shù)據(jù)挖掘;黃 敏,碩士研究生。
2014-09-02
2014-11-04 E-m ail:nw ang@bjut.edu.cn