周 星，刁興春，曹建軍

1.解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京 210007 2.南京電訊技術(shù)研究所，南京 210007

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

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

1.解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京 210007 2.南京電訊技術(shù)研究所，南京 210007

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

實(shí)體分辨；記錄對劃分；粗糙集

1 引言

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

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

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

文獻(xiàn)[6]為發(fā)現(xiàn)難分辨的記錄對，構(gòu)建了一個多分類器，當(dāng)對某個記錄對，分類器的投票出現(xiàn)最大分歧，即判斷該記錄對為相似和不相似的分類器一樣多時(shí)，該記錄對為難分辨的記錄對，它能提供最大的信息增益。該方法由于采用了多分類器，分辨出的記錄對與具體算法有關(guān)，且計(jì)算復(fù)雜性較高。

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

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

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

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

2 鄰域粗糙集

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

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

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

其中

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

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

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

此時(shí)，X的上下近似的定義為：

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

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

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

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

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

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

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

輸出 BR和NR。

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

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

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

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

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

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

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

4 實(shí)驗(yàn)

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

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

實(shí)驗(yàn)環(huán)境為1臺i7-4790 CPU，4 GB內(nèi)存的PC，實(shí)驗(yàn)平臺為MATLAB7.0。

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

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

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

測試記錄對的參數(shù)及對應(yīng)的pr如表1所示。

圖2 dblp_acm的記錄相似度比較

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

圖3 abt_buy的記錄相似度比較

表1 測試記錄對的參數(shù)及對應(yīng)的pr

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

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

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

圖4 amazon_gp的記錄相似度比較

表2 分類正確率比較

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

5 結(jié)論

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

[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]曹建軍，刁興春，汪挺，等.領(lǐng)域無關(guān)記錄對清洗研究綜述[J].計(jì)算機(jī)科學(xué)，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].軟件學(xué)報(bào)，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

國家自然科學(xué)基金（No.61070174）。

周星（1988—），男，博士生，主要研究方向?yàn)閿?shù)據(jù)工程、數(shù)據(jù)質(zhì)量，E-mail：zx0327@163.com；刁興春（1964—），男，研究員，博士生導(dǎo)師，主要研究方向?yàn)閿?shù)據(jù)工程；曹建軍（1975—），男，博士，碩士生導(dǎo)師，主要研究方向?yàn)閿?shù)據(jù)質(zhì)量、進(jìn)化算法。

2016-05-19

2016-07-19

1002-8331（2017）21-0072-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2016-11-21,http://www.cnki.net/kcms/detail/11.2127.TP.20161121.1655.024.html