基于鄰域粗糙集的實體分辨記錄對劃分

周 星，刁興春，曹建軍

1.解放軍理工大學 指揮信息系統學院，南京 210007 2.南京電訊技術研究所，南京 210007

基于鄰域粗糙集的實體分辨記錄對劃分

周 星1，刁興春2，曹建軍2

1.解放軍理工大學 指揮信息系統學院，南京 210007 2.南京電訊技術研究所，南京 210007

現有的實體分辨方法在準確性和效率上各有所長，將易分辨和難分辨的記錄對分開，為下一步分別應用不同分辨方法提供基礎。對待劃分的記錄對，利用變精度鄰域粗糙集分別計算相似記錄對和不相似記錄對的上下近似集，得到全體記錄對的上下近似集及對應的邊界，處于邊界域的記錄對即為難分辨的記錄對，其余為易分辨的記錄對。分析了變精度鄰域粗糙集中的包含度閾值和距離閾值對于記錄對劃分的影響。利用實驗比較難分辨、易分辨和原始記錄對在利用相似度閾值分類和利用KNN分類時的準確性，說明了劃分的有效性。

實體分辨；記錄對劃分；粗糙集

1 引言

實體分辨的主要任務是找出相同或不同數據源中描述同一客觀實體的不同對象[1]，它通常包括三個步驟：索引、記錄對比較和相似度向量分類。索引聚合可能重復的記錄以提升分辨效率；記錄對比較運用字段相似度函數計算記錄對各個字段的相似度，生成字段相似度向量；相似度向量分類根據字段相似度向量將記錄對分為匹配、不匹配和可能匹配[2]，其中可能匹配是指記錄對可能為匹配，也可能為不匹配，通常需要專家參與以進一步確定。這類方法又稱為基于屬性的方法（Feature Based Similarly，FBS）。

Kalashnikov等為提高實體分辨的準確性，提出了一種基于關聯關系的數據清洗（Relationship-based Data Cleaning，RelDC）方法，他利用無向圖對數據庫進行建模，得到實體關系圖，再利用實體之間的關系進行分辨[3-4]。

曹建軍等比較了FBS和RelDC方法，指出FBS方法效率較高，但是在某些記錄對上的分辨準確性較低，RelDC準確性較高，但是由于需要構建實體關系圖，復雜性較高，因此他指出需要構建一種選擇方法，即為難分辨的記錄對選擇RelDC方法，為其余記錄對選擇FBS方法[5]，這種選擇的前提是區分難分辨的記錄對和易分辨的記錄對。

文獻[6]為發現難分辨的記錄對，構建了一個多分類器，當對某個記錄對，分類器的投票出現最大分歧，即判斷該記錄對為相似和不相似的分類器一樣多時，該記錄對為難分辨的記錄對，它能提供最大的信息增益。該方法由于采用了多分類器，分辨出的記錄對與具體算法有關，且計算復雜性較高。

文獻[7]首先利用云模型[8]計算各記錄相似度對應相似或不相似概念的置信度，根據置信度求出相似記錄對和不相似記錄對的記錄相似度閾值，并認為大于相似記錄對的記錄相似度閾值，則為相似；小于不相似記錄對的記錄相似度閾值，則為不相似；二者之間的則既可能為相似也可能為不相似，對應記錄對為難分辨的記錄對。但是云模型假設了記錄相似度呈近似正態分布，并且其僅通過記錄相似度來判斷記錄對是否相似，僅能發現線性可分或不可分的情況，不能發現非線性可分或不可分的情況。

文獻[9]假設記錄相似度呈正態分布，并利用三倍方差選擇難分辨的記錄對，即記錄相似度大于相似記錄對的記錄相似度的均值減去三倍方差，則認為相似，記錄相似度小于不相似記錄對的記錄相似度的均值加上三倍方差，則認為不相似。這種方法的好處是實現簡單，但是缺點不僅和文獻[7]中的一樣，而且記錄相似度呈正態分布的假設還更為嚴格。

粗糙集中的邊界域[10]表示根據已有知識，不能明確屬于哪一類的樣本，它不需要假設樣本的分布，且所求出的難以分類的樣本與學習算法無關，效率較高，因此本文選擇粗糙集對記錄對進行劃分。

由于實體分辨中，字段相似度為[0，1]區間的連續值，因此本文采用文獻[11]中提出的鄰域粗糙集查找難分辨的記錄對。

2 鄰域粗糙集

粗糙集用一個四元組S=(U,A,V,f)表示一個信息系統，其中U是一個稱為論域的非空有限對象集合，A是一個非空有限屬性集合，V=∪a∈AVa，Va是屬性a的值域，f:U×A→V是一個從論域U，屬性集合A到值域V的信息函數。當A=C?D，C是條件屬性集合，D是決策屬性集合時，該信息系統稱為決策信息系統[12]。

對于離散值，每一個非空子集B都決定了一個不可分辨關系，RB={(x,y)∈U×U|f(x,a)=f(y,a),?a∈B}，其中U是論域，B是屬性集合，x，y是論域上的對象，不可分辨關系是粗糙集理論的基礎；對于連續值，利用鄰域關系將不可分辨關系擴展為：RB={(x,y)∈U×U|Δa(x,y)≤δ,?a∈B}，其中 B 是屬性集合，Δ 是距離函數，δ是距離閾值。應用鄰域關系的決策信息系統稱為鄰域決策信息系統。

給定鄰域決策信息系統S=(U,C?D,V,f)，令X1,X2,…,XN為對應決策1到N的對象集合，δB(xi)={y∈U|Δa(x,y)≤δ,?a∈B}為 xi在特征空間 B?C 上的鄰域對象集合，D相對于屬性集合B的下近似集和上近似集的定義如下[11]：

其中

該定義對于噪聲比較敏感，因此，文獻[13]提出了變精度粗糙集，它引入包含度對鄰域粗糙集進行泛化。給定論域中的兩個集合A、B，包含度的定義如下：

D相對于屬性集合B的決策邊界域定義為[9]：

其中A≠?，||?為集合的基。

此時，X的上下近似的定義為：

其中，k稱為包含度閾值，取值范圍為0.5≤k≤1。

3 基于鄰域粗糙集的記錄對劃分

本文利用變精度鄰域粗糙集求解記錄對的邊界域，并認為處于邊界域的記錄對為邊界記錄對，對應難分辨的記錄對；余下的記錄對為正常記錄對，對應易分辨的記錄對。其算法流程如下：

輸入 匹配記錄對M和不匹配記錄對U，包含度閾值k，距離閾值δ。

步驟1計算匹配記錄對M和不匹配記錄對U的字段相似度向量X1和X2。

步驟2根據公式（5）分別計算 X1和X2的上下近似集

步驟4根據公式（3）計算邊界域，以及處于邊界域的記錄對BR，余下為正常域內的記錄對NR。

輸出 BR和NR。

算法過程即是首先分別求出相似記錄對和不相似記錄對的上下近似集，再得到全體記錄對的上下近似集，最后根據定義，求出邊界域。

變精度和鄰域關系的引入將導致找出的邊界域的記錄對為難分辨的記錄對的置信度下降。對于變精度粗糙集，包含度閾值k的影響較大，k越大，正常域里的記錄對屬于易分辨的記錄對的置信度越高，但是將使得邊界記錄對占比 pr過大，其中

另一方面，鄰域關系對置信度影響也較大。當距離閾值δ為0時，僅完全相同的記錄對被判定為相似，因此所有記錄對均為正常記錄對，此時兩個記錄對同為相似或不相似的置信度最高，pr為0。距離閾值δ越小，置信度越大，但是也將導致 pr過大。

為說明包含度閾值k和距離閾值δ與邊界記錄對占比 pr的關系，以文獻[14]中的amazon_gp數據集為例。使δ在0～0.5以0.02的步長進行變化，k在0.5～1以0.02的步長進行變化，計算相應的pr，得出如圖1所示的關系。

圖1 邊界記錄對占比pr和包含度閾值k及距離閾值δ的關系

從圖1可知，pr與k呈遞增關系，且隨著δ增加，pr相對k增長更快。然而，并不是所有的記錄對都呈現嚴格遞增關系，部分記錄對存在波動。

綜合來看，k趨于1，δ趨于0時，利用粗糙集查找出的邊界記錄對確為難分辨記錄對的置信度最高。如果記錄對中難分辨記錄對過多，可以選擇將δ設置為盡量小；如果為了使求出的邊界記錄對不要太多，可以將k設置較小。

4 實驗

本文采用文獻[14]中用到的dblp_acm、abt_buy和amazon_gp數據集。對數值型字段，利用sim(a,b)=計算相似度，對字符型字段，利用Jaccard相似度[15]計算相似度，將相似記錄對的類標設為1，不相似記錄對的類標設為-1，根據各數據中的 pr和k及δ的關系，選擇合適的k和δ。

為比較記錄對劃分對實體分辨的影響，將記錄對分為正常記錄對、邊界記錄對和原始記錄對，比較各組記錄對在利用相似度閾值分類和利用KNN分類時的準確性，以說明記錄對劃分的有效性。利用相似度閾值分類，即認為相似度大于該閾值則為相似，小于該閾值則為不相似。利用KNN分類，即利用KNN算法將記錄對分為相似和不相似兩類。

實驗環境為1臺i7-4790 CPU，4 GB內存的PC，實驗平臺為MATLAB7.0。

4.1 記錄對劃分對記錄相似度閾值的影響

為比較記錄對劃分對利用相似度閾值分類的影響，利用線性回歸計算各字段的權重，將各字段相似度加權得到記錄相似度。

利用MATLAB畫出正常記錄對、邊界記錄對和原始記錄對中的相似記錄對和不相似記錄對的記錄相似度的散點圖，以直觀、定性地表示記錄對劃分對用相似度閾值進行分類的影響。

測試記錄對的參數及對應的pr如表1所示。

圖2 dblp_acm的記錄相似度比較

從圖2～4可知，盡管由于變精度的存在，位于正常域的記錄對，相似記錄對和不相似記錄對的記錄相似度存在部分交叉，但是相比原始記錄對，存在交叉的記錄對已經大幅減少，更有利于用相似度閾值進行分類；而邊界域的記錄對存在交叉的變多，更難用相似度閾值進行分類。

圖3 abt_buy的記錄相似度比較

表1 測試記錄對的參數及對應的pr

4.2 記錄對劃分對分類正確率的影響

對正常記錄對、邊界記錄對和原始記錄對，分別利用KNN分類器運行10輪5折交叉檢驗驗證分類的準確性，取K 為5。

對各記錄對，求出分類正確率的均值和標準差，并采用置信度為0.05的雙邊t檢驗，將正常記錄對、邊界記錄對與原始記錄對進行對比，若結果明顯好（差），則用●（○）標記，最好的結果加粗表示，最后一行表示win/tie/loss統計結果。正確率比較如表2所示。

圖4 amazon_gp的記錄相似度比較

表2 分類正確率比較

從表2可知，正常記錄對相比原始記錄對，分類正確率得到了提高，而邊界記錄對相比原始記錄對，分類正確率顯著降低，進一步說明了記錄對劃分的有效性。

5 結論

本文利用變精度鄰域粗糙集對實體分辨記錄對進行劃分，為對易分辨的記錄對和難分辨的記錄對分別應用不同的分辨方法提供基礎。分析了變精度鄰域粗糙集中的包含度閾值和距離閾值對于記錄對劃分后邊界記錄對占比的影響，為每個記錄對選擇合適的參數。比較各組記錄對在利用相似度閾值分類和利用KNN分類時的準確性，說明方法的有效性。

[1]Elmagarmid A K，Ipeirotis P G，Verykios V S.Duplicate record detection：A survey[J].IEEE Transactions on Knowledge and Date Engineering，2007，19（1）：1-16.

[2]Christen P.A survey of indexing techniques for scalable record linkage and deduplication[J].IEEE Transactions on Knowledge and Date Engineering，2012，24（5）：1537-1555.

[3]Kalashnikov D V，Mehrotra S.Domain-independent data cleaning via analysis of entity-relationship graph[J].ACM Transactions on Database Systems，2006，31（2）：716-767.

[4]Kalashnikov D V，Nuray-Turan R，Mehrotra S.Adaptive connection strength models for relationship-based entity resolution[J].ACM Journal of Data and Information Quality，2012，4（2）.

[5]曹建軍，刁興春，汪挺，等.領域無關記錄對清洗研究綜述[J].計算機科學，2010，37（5）：26-29.

[6]Tejada S，Knoblock C A，Minton S.Learning domainindependent string transformation weights for high accuracy identification[C]//ACM SIGKDD，Edmonton，2002.

[7]Zhou Xing，Diao Xingchun，Cao Jianjun.A data cleaning switch technology based on cloud model[C]//International Conference on Information Quality，Xi’an，China，2014.

[8]李德毅，劉常昱，杜鹢，等.不確定性人工智能[J].軟件學報，2004，15（11）：1583-1594.

[9]Zhou Xing，Diao Xingchun，Cao Jianjun.A high accurate multiple classifier system for entity resolution using resampling and ensemble selection[J].Mathematical Problems in Engineering，2015（2）：1-6.

[10]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11（5）：341-356.

[11]Hu Qinghua，Yu Daren，Liu Jinfu，et al.Neighborhood rough set based heterogeneous feature subset selection[J].Information Sciences，2008：3577-3594.

[12]Liang Jiye，Wang Feng，Dang Chuangyin，et al.A group incremental approach to feature selection applying rough set technique[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（2）：294-308.

[13]Ziarko W.Variable precision rough sets model[J].Journal of Computer and System Sciences，1993，46（1）：39-59.

[14]Papadakis G，Koutrika G，Palpanas T，et al.Meta-blocking：Taking entity resolution to the next level[J].IEEE Transactions on Knowledge and Data Engineering，2014，26（8）：1946-1960.

[15]Xiao Chuan，Wang Wei，Lin Xuemin，et al.Efficient similarity joins for near-duplicate detection[J].ACM Transactions on Database Systems，2011，36（3）.

ZHOU Xing1,DIAO Xingchun2,CAO Jianjun2

1.School of Command Information System,PLA University of Science and Technology,Nanjing 210007,China 2.Nanjing Telecommunication Technology Institute,Nanjing 210007,China

Record pairs partition for entity resolution based on neighborhood rough set.Computer Engineering and Applications,2017,53（21）：72-76.

The present approaches of entity resolution vary in effectiveness and efficiency,normal record pairs and ambiguous record pairs are separated,so that different approaches can be applied to them.As to the record pairs to be partitioned,variable precision neighborhood rough set is used to compute the lower and upper approximation of similar record pairs and dissimilar record pairs respectively,to get the approximation sets and boundary region of all record pairs,and those record pairs in the boundary region are regarded as ambiguous,the rest are normal.How the thresholds of inclusion degree and distance in the variable precision neighborhood rough set affect the effectiveness of data partition is analyzed.Experiments are conducted to compare the accuracy of the normal,ambiguous and original record pairs while using similarity threshold and KNN to resolute,showing the effectiveness of partition.

entity resolution;record pair partition;rough set

A

TP311

10.3778/j.issn.1002-8331.1605-0266

國家自然科學基金（No.61070174）。

周星（1988—），男，博士生，主要研究方向為數據工程、數據質量，E-mail：zx0327@163.com；刁興春（1964—），男，研究員，博士生導師，主要研究方向為數據工程；曹建軍（1975—），男，博士，碩士生導師，主要研究方向為數據質量、進化算法。

2016-05-19

2016-07-19

1002-8331（2017）21-0072-05

CNKI網絡優先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.1655.024.html