基于MapReduce與兩層相關性聚類的實體解析方法

王 寧，黃 敏

（北京交通大學計算機與信息技術學院，北京100044）

基于MapReduce與兩層相關性聚類的實體解析方法

王 寧，黃 敏

（北京交通大學計算機與信息技術學院，北京100044）

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

相關性聚類；MapReduce模型；實體解析；大數據；數據集成；分布式計算

1 概述

實體解析［1］是指對現實世界中同一實體的不同表現形式進行識別、連接和分組，它在數據庫管理、數據集成、機器學習中都有廣泛的應用。大數據時代的到來，使得人們去挖掘數據的潛在價值。

大數據具有數據量大、數據更新速度快、數據源多樣和數據存在噪聲等特點［2］。其中，數據噪聲會造成部分數據關聯和依賴的假象。相關性聚類是實體解析的一種基本方法，文獻［3］基于對數據噪聲的處理提出了一種兩層相關性聚類算法，用于提高實體解析的質量。

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

2 相關工作

2.1 兩層相關性聚類算法

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

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

鄰居相似度：兩層相關性聚類算法使用余弦相似度來計算鄰居相似度：

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

記錄與塊的關聯程度：如果記錄i屬于某一個塊，那么它應該與該塊的核有很強的關聯，Ri（c）表示記錄i與塊c的關聯程度，其中：

調整塊算法：預分塊得到的結果中含有許多重疊部分，調整塊算法依賴于記錄序列，對于某一個記錄，將它歸并到與其有最大關聯程度的塊中。

2.2 MapReduce框架以及實體解析

Hadoop［7］分布式系統架構包括HDFS分布式文件系統和MapReduce編程模型兩部分。HDFS擁有對數據讀寫的高吞吐率，因此適合構建大數據集上的應用。MapReduce是一個用于大數據量計算的編程模型，其應用程序最基本的組成部分包括一個Mapper類和一個Reducer類。

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

3 基于MapReduce的兩層相關性聚類算法

3.1 系統框架

圖1給出基于MapReduce的兩層相關性聚類方法的框架，分數據準備（統計鄰居和計算鄰居相似度）、預分塊、調整塊（關聯程度的計算和記錄的添加與刪除）3層。第2層預分塊仍保留之前的分塊方案，本文的工作主要針對數據準備階段和調整塊階段實現。

圖1 基于MapReduce的兩層相關性聚類方法框架

修改后的調整塊為兩層迭代算法，需要證明其收斂性。在算法執行過程中，每次迭代對每條記錄，將它從與其關聯程度低的塊中刪除，因此，只需證明每個記錄最終有且僅有一個塊與其相關聯，即記錄最終僅出現一次，便可證明該算法是收斂的。定理及其證明保證了算法的收斂性。

定理 對于給定的記錄集合I=｛I1，I2，…，Ii｝，I上的α個分塊集合C=｛c1，c2，…，cα｝，I中每條記錄在C上重復劃分次數的集合N=｛n_I1，m，n_I2，m，…，n_ Ii，m｝，其中，n_It，m表示記錄It（1≤t≤i）經過m次迭代后被重復劃分的次數。當迭代m（1≤m≤α）次后，N=｛1，1，…，1｝，即每條記錄僅屬于唯一一個分塊。

證明：對于α個分塊，每個記錄最多被重復劃分α次。在本文算法中，每次迭代至少將一條被重復劃分的記錄從與其關聯程度低的塊中刪除，即對?nˉIt，m∈N（1≤n_It，m≤α），當n_It，m＞1時，n_It，m+1=n_It，m-β（1≤β≤α）。每經過一次迭代，被重復劃分的次數至少會減少一次。因此，?m（1≤m≤α），迭代m次后，N=｛1，1，…，1｝。

3.2 鄰居文件及鄰居相似度

3.2.1 鄰居文件

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

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

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

圖2 獲取鄰居文件的MapReduce過程

3.2.2 鄰居相似度計算

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

算法1 鄰居相似度計算

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

3.3 調整塊

原有的調整塊算法每將一個節點歸于某一個分塊或從某一個分塊中刪除，將會及時更新其他記錄與所在塊的關聯程度。然而，基于MapReduce的算法無法實時對數據進行更新，因此采用迭代的方式對數據進行處理，并盡可能地在一次迭代中處理更多的數據，以減少迭代次數。因此，本文定義了最大關聯程度、最小關聯程度、最大關聯塊和最小關聯塊來幫助判斷記錄的歸屬（定義1、定義2），并定義了相關運算來操作塊中記錄的添加和刪除（定義3），同時為運算提供判斷標準（定義4）。

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

定義3 設分塊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）及其所有關聯的塊cm（1≤m≤α），分布式環境下的塊更新規則定義如下：

（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 分布式壞境下的調整塊算法

調整塊分MR階段和內存階段兩部分執行。首先將預分塊P表示成＜key，value＞對的形式代入MR階段計算。調整塊算法的總循環如下：

算法2 調整塊算法總循環

對于預分塊階段產生的粗糙的、有重疊的分塊P，每一次循環都將計算記錄與所在塊的關聯程度，并根據關聯規則輸出處理文件（7行），在內存中進行添加和刪除（8行），當每個記錄均只出現一次時，循環結束，此時可得到無重疊的分塊結果（9行）。

MR階段采用MapReduce模型實現，具體算法如下：

算法3 調整塊算法MR階段

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

3.3.2 調整塊算法的后處理

改進后的調整塊算法很好地解決了MR中不能實時更新數據的問題。但每一個記錄被重復劃分的次數不同，其迭代停止的順序也不同，這會導致許多單一記錄的產生。為了減少單一記錄形成的分塊，對分塊后的結果進行再處理：首先，計算結果中單一記錄與其他各塊的關聯程度；然后，獲得與該單一記錄有最大關聯程度的分塊，若最大關聯程度大于0，則將該記錄加入到對應的分塊中。

4 實驗與評估

4.1 實驗環境和實驗數據

實驗部署的分布式環境由3個節點構成，其中2個節點（1臺為主節點）為內存16 GB，CPU 2.93 GHz，硬盤1 TB的Dell服務器，另外1個節點為內存4 GB，CPU 2.73 GHz，硬盤1 TB的Dell服務器。實驗所用的算法是在hadoop2.20.0和jdk1.7.0_06環境下實現的。

由于沒有合適規模的真實數據集，將cora數據集擴大相應的倍數，并增加數據噪聲形成實驗數據集。Cora數據集包含對112篇不同文章的1 295個引用，共1 295×（1 295-1）/2=837 865個記錄對，擴大數據集后，記錄對的數量已達到107數量級。

4.2 實驗評估標準

準確率、召回率和F-值常用于評估聚類算法，在非分布式環境下，兩層相關性聚類算法在這3個值上均優于傳統算法。為適應分布式環境，對調整塊算法進行了改進，因此需保證改進后的算法在時間效率提高的基礎上，準確率、召回率和F值均不低于原方法的評估結果。

4.3 實驗結果與分析

4.3.1 有效性

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

表1 DTT與TT在Cora數據集上的聚類效果對比

隨著數據量增加，DTT算法在這3個評價指標上出現了變化：準確率較高，基本保持在0.95以上，召回率卻在0.7徘徊，F值基本穩定在0.8左右，如圖3所示。對結果中出現的單一記錄進行再處理后（DPTT），在保持高的準確率的基礎上，召回率和F值都有所提高，如圖4所示。

圖3 DTT的準確率、召回率和F值隨數據量變化的情況

圖4 DTT與DPTT的結果有效性比較

4.3.2 時間效率

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

圖5給出了調整塊階段運行的總時間。隨數據量的增加，運行總時間呈現比較平緩的增長趨勢，但隨Hadoop節點數的增加，總時間在大幅降低。

圖5 數據量與運行時間的關系

圖6 給出了平均運行時間與迭代次數及Hadoop結點數的關系，其中，迭代次數對應圖5中的數據量增長。隨數據量的增加，記錄間的關聯關系變復雜，記錄被重復劃分的次數便會增加，因此，程序運行的迭代次數也會增加，見圖6。但各節點數下，每個job的平均運行時間基本保持穩定或有小幅增長，而對于最后2個同為108次迭代次數的5×107和6×107數據量，盡管后者的計算量遠多于前者，但平均運行時間的差值卻不大，說明本文算法能很好地適應分布式環境。

圖6 平均運行時間與迭代次數及HadooP節點數的關系

5 結束語

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

［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］ 維克托·邁爾·舍恩伯格，肯尼思·庫克耶.大數據時代［M］.盛陽燕，周 濤，譯.杭州：浙江人民出版社，2012.

［3］ 王 寧，李 杰.大數據環境下用于實體解析的兩層相關性聚類算法［J］.計算機研究與發展，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與兩層相關性聚類的實體解析方法［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數據集成，大數據管理，數據挖掘；黃 敏，碩士研究生。

2014-09-02

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