沈忱，曾衛(wèi)明，吳愛華

（上海海事大學信息工程學院，上?！?01306）

融合修復代價的不一致關系數據中相似重復記錄識別

沈忱，曾衛(wèi)明，吳愛華

（上海海事大學信息工程學院，上海201306）

0　引言

不一致數據是有錯誤的、違反了完整性約束的數據［1］，其中最常見的就是同一個現實實體在數據集合中用多條不完全相同的記錄表示，這類記錄被稱為相似重復記錄。相似重復記錄廣泛存在于現實應用中，如：數據整合［2］、RFID無線網絡［3］、數據抽?。?］等。在多源數據的集成中，因為某些單個數據庫本地數據的拼寫錯誤，如把記錄屬性值“Google”拼寫成“Gogle”，或者多種數據源的語言表達習慣的不同，如把出生日期“1990-10-27”表示成“1990/10/27”或者“27/10/1990”、信息更新不夠及時等原因，以致計算機誤認為是不同的記錄。對這類數據進行操作時，會得到錯誤的、矛盾的查詢結果，給用戶帶來困擾，極大地降低了數據利用價值。在相似重復記錄識別的現有方法中，人工糾正耗時耗力，不適用于規(guī)模較大的應用；各類智能數據清洗算法無法保證數據修復的正確性。

相似重復記錄的識別是不一致數據查詢處理中要解決的關鍵問題。本質上這是一個統(tǒng)計問題，根據記錄之間的相似性將可能指向同一實體的多條記錄歸為同一類。一種典型的數據分類方法是聚類［5］。其中最常用的方法就是K-means劃分算法。首先隨機選取K個點作為初始聚類中心，然后根據數據點到聚類中心的最短距離來劃分數據，根據新劃分的類更新聚類中心，直至準則函數不再改變?yōu)橹?。對于數據點的距離計算方法最常見的是編輯距離。編輯距離是指字符串s1轉化為字符串s2所需的最小操作次數，然后利用編輯距離來計算字段之間的相似度。因為編輯距離的操作對象是字符串，這種計算方式對于數值型字段而言是存在問題的。數值型字段只需要進行相加減就可以知道數值之間的差異度，例如人的年齡，19與20相差1歲，但是按照編輯距離的概念將兩者視為字段來處理，那么結果是兩者完全不相似的。所以基于統(tǒng)計的編輯距離計算并未考慮數據類型的多樣性，只能針對一些拼寫錯誤的字段。編輯距離的矛盾之處還體現在，究竟是按照單個字段進行匹配計算還是將整條記錄視為整體進行操作。如果按照單個字段進行匹配，要如何分配字段的權重才能體現它對于記錄標識的關鍵性。例如，姓名并不能唯一指定成績，而根據學號可以得到學生的性別。所以根據數據依賴，為字段賦予權重，從數值上體現某些字段的關鍵性對于記錄匹配是有很大幫助的。另一種常見分類方法是基于概率的樸素貝葉斯方法［6］：在統(tǒng)計資料的基礎上，依據某些特征，計算各個類別的概率，從而實現分類。這個方法的前提條件是默認所有的特征都是條件獨立的，并且已知各個分類的先驗概率。這個方法可以大大簡化計算，但“所有特征彼此獨立”這個假設，在現實中不太可能成立，在關系型數據庫中，字段與字段之間必然存在著某種聯(lián)系，某個特征值的出現必定會影響另一個特征值出現的概率，這種聯(lián)系可以為相似重復記錄的識別提供很多信息。

如表1所示，Details表中的記錄t2，t3，如果使用聚類進行相似重復記錄識別，選擇t3為聚類中心，那么這兩條記錄的距離非常近，可以聚為一類，但是根據函數依賴可得這兩條記錄指向的是兩個不同實體。

表1　Details表

表2　Patients表

函數依賴：

圖1含有不一致數據的Patient表、Details表及其上的完整性約束。

通過以上分析，相似重復記錄的識別帶來了以下挑戰(zhàn)：一方面，忽略了字段之間的語義關系。例如聚類算法是通過計算記錄之間的相似度來進行分類的方法，這是基于統(tǒng)計的方式；基于概率的樸素貝葉斯記錄匹配方式的使用前提條件就是字段之間相互獨立。函數依賴體現了數據之間的某種依賴關系，可以幫助判斷在不一致數據中哪些屬性值產生了矛盾。違反的約束越多，這個數據錯誤的概率就越大，那么在數據集合中存在的可能性就越小。完整性約束作為先驗知識，可以根據數據間的依賴關系為不一致數據提供額外信息，充分利用這些信息可以幫助識別相似重復記錄。另一方面，字段的數據類型多種多樣，只使用一種相似度計算方式顯得非常局限；若根據字段的特點設定多種計算方式也非常繁瑣，如果將屬性值都轉換為數值型就方便很多。

鑒于以上觀察，本文以相似重復記錄為研究對象，以函數依賴為基礎，提出了一種新的重復記錄識別方法。本文的貢獻可以歸納為以下幾點：①研究了以完整性約束作為先驗知識對字段存在概率的影響；②提出了一種能統(tǒng)一衡量記錄之間相似度的方法；③充分考慮了字段語義之間的關系，提出新的識別方法。

1　相關工作

近些年來，研究人員針對重復記錄識別問題做了很多研究工作。文獻［7］是早期重復記錄識別工作的研究綜述。文獻［8～13］均為統(tǒng)計方式，根據記錄內容的相似度來判斷記錄是否重復。文獻［8］將整條記錄視為字符串，通過編輯距離計算，得到記錄之間的相似度，但編輯距離只適用于有拼寫錯誤的字符串；文獻［9］以N-gram值為基礎進行檢測，每一個記錄都有一個N-gram值，按照［10］的方法進行排序聚類，但N值的設定對結果影響很大［15］；文獻［11］以鍵為單位進行檢測，鍵是由記錄的一些相關字段構成的，檢測前先按照鍵進行排序，在對其進行相似重復記錄檢測時使用了滑動窗口的方法，但是滑動窗口大小的選取會影響到聚類結果。由于數據的多樣性，每種方法各有側重，沒有一種方法是完全適用于所有情況的。文獻［12～13］基于二分圖的最優(yōu)匹配處理異構模式數據，提出了能夠有效表達異構模式記錄的相似性，并對原有算法進行了改進，增加了識別技術的高效性；文獻［14］是復雜數據上的實體識別技術的研究綜述。

以上方法都忽略了關系型數據之間的聯(lián)系，并未將完整性約束考慮在內，僅僅通過記錄間的相似度或者是比較獨特的方式來進行相似重復記錄識別。在關系型數據庫中，必須要考慮完整性約束提供的額外信息，通過這些信息可以幫助識別。同時，數據類型的多樣性為相似度計算增加了困難。

為了克服上述方法中的不足之處，本文提出了一種新的相似重復記錄探測方法。該方法結合了數據修復以及概率模型。首先，將原始數據庫表表示為初始概率模型，并利用自定義的完整性約束作為先驗知識發(fā)現不一致數據，找出不一致數據上的候選修復，根據候選修復對屬性值上的概率進行修改。最后使用概率進行相似度計算，盡可能多地找到相似重復記錄。

2　數據修復代價計算

本節(jié)借鑒文獻［1］中所用到的數據修復、違反包、修復代價以及沖突類的概念，在此簡單介紹。

在不一致數據庫中，違反了完整性約束的分量或元組就是需要修復的對象。一般通過刪除、增加或修改記錄的屬性值對修復對象進行修復操作，本文為了計算方便，并未考慮刪除和增加整條記錄的操作。如表1所示，t1與t2違反了函數依賴，存在矛盾之處，構成了沖突類。沖突類就是不一致數據庫中存在的矛盾，一個矛盾就是一個沖突類。違反包是由違反了數據庫D中任一約束的元組或元組集構成，在違反包上進行的一系列修復操作的組合是該違反包上的候選修復。違反包中的成員都是違反了完整性約束的，修復的任務是為了找到那個導致最多矛盾的目標值，我們的目的是根據這個目標值的候選修復所消耗的代價來決定候選修復存在的概率。

表1存在下面幾個違反包：C1：｛（t1、t5），ic2｝；C2：｛（t1、t5），ic3｝；C3｛（t3），ic7｝；C4｛（t4），ic8｝；C5｛（t4），ic7｝，根據違反包與候選修復概念，得到表3：

表3　違反包與候選修復代價

沖突類的修復代價是指一種候選修復解決其對應的違反包所產生的代價之和。從上表可以看出一個違反包可以有多個候選修復，而一個候選修復也可以解決多個違反包，如表1中r1可以同時修復C1、C2兩個違反包。如果該修復覆蓋的違反包越多，那么被修復對象錯誤的可能性就越大。沖突類的覆蓋修復代價是指沖突類的修復代價/該沖突上某種候選修復能夠解決的違反包個數。但是，在修復的同時也會導致其他違反包的出現，產生新的沖突類，表4為引起新沖突類后產生的關聯(lián)覆蓋代價。

表4　覆蓋修復代價和關聯(lián)覆蓋修復代價

本文所提出的相似重復記錄識別方法與概率有關，這里先簡單介紹一下候選修復是如何影響屬性值出現的概率的。在完全無錯的數據庫中，每個字段都有它的值域，每條記錄的字段在這個值域上的取值應該是百分之百正確的。但是在含有不一致數據的數據庫中，記錄違反的約束個數，消耗的修復代價以及覆蓋修復代價都會影響到屬性值存在的概率。例如，在確定的情況下，一個人的性別不是“男”就是“女”，即取到“男”的概率為100%，“女”的概率為0，反之亦然。而在不確定的情況下，性別字段中的 “男”“女”取值應該各占50%。但是假設根據修復方案可得：取到“男”比取到“女”修復的錯誤更多，且取值概率可以達到80%，此時可以修改該記錄在性別字段上的 “男”概率為80%，“女”為20%。利用候選修復的關聯(lián)覆蓋代價來更改屬性值存在的概率。

3　LIMBO概率矩陣

在相似重復記錄識別問題上已經有過很多研究。聚類是其中一種最為常用的方法，利用記錄之間的距離進行比較。但是一些描述性的屬性值，例如 “男”、“女”這類分類屬性（Categorical Attribute）是沒有直接測量方式能夠計算出它們之間的距離的。本文將每個記錄的屬性值用概率表示，當所有值都用概率替代后，就可以將其視為數值型進行計算。。

關系型數據庫表以行和列的形式組織數據。每列屬性都包含了特定類型的信息，多列屬性構成了每條記錄。令數據集合T上有N條記錄，則T=｛x1，x2，…，xn｝，屬性集合A=｛A1，A2，…，Am｝，則記錄xi=｛xi1，xi2，…，xim｝。令Vi為屬性Ai的值域，不同屬性值域上的相同的屬性值被認為是2個值，那么整個數據集合的值域可以表示為：

則整個值域V的模為|V|，由此可得一個n×|V|的矩陣M。如果構成記錄xi的屬性值在V中出現，則在矩陣中標記M［x，v］=1，否則標記為0。因為每條記錄在每個屬性上存在一個值，數據庫表定義了m個屬性，則每條記錄在矩陣上標記了m個1。然后將矩陣一般化，設每行出現的標記之和為1，所以每個屬性值的概率為p（v|x）=1/m。

根據表1所示的不一致數據庫表，并結合概率模型的概念得到初始概率矩陣如表5所示。由于篇幅原因只表示了Details表中No.和Name的初始概率矩陣。

4　概率矩陣修改

本文是通過對不一致數據進行修復，根據各違反包的修復代價來修改概率矩陣的，以下詳細給出在不同修復情況下概率改變的計算方法。

根據候選修復歸納每條記錄在每個字段上出現的修復種類，選取每條記錄每個字段上的最優(yōu)修復，以下例子是根據上文表1、表2后所得：

（1）違反包含依賴的修復一般都是成對出現，形如：

修改t1［y］，使得t1［y］=t2［y］和，修改t2［y］，使得t1［y］=t2［y］（表6）及其概率修改（表7），或者修改t1［x］，使得t1［x］≠t2［x］和，修改t2［x］，使得t1［x］≠t2［x］（表8）及其概率修改（表9）。對于t1、t2來說t1［y］和t2［y］都是可能取到的值，所以將這兩個修復結合來看。

表5　Details表中No.和Name字段的初始概率矩陣

表6

表7　概率修改

表8

表9　修改概率可得

（2）修復為t［x］≠y時且修復代價最?。ū?0）及其概率修改計算（表11）

表10

表11　概率修改：將原值的概率置為0，其余值均分概率

根據以上概率修改計算過程可得以下整體概率修改表格 （表12），由于篇幅有限只展示Details表中的No.與Name字段上的概率。概率矩陣根據記錄的修復代價修改完成后，所有數據都以數值型呈現，大大方便了記錄之間相似度的比較。

5　實驗

實驗環(huán)境：Intel Core SU3500（1.4GHz）；2GB內存；Windows 7+SP1操作系統(tǒng)；數據庫軟件為SQL Server 2008；程序用Java語言編寫。

實驗數據：以TPC-H［18］數據庫為基礎，選取CUSTOMER表中5個字段，基本數據格式如表4所示，約束設置參照tpch2170中所規(guī)定的，并在此基礎上改編成適應本實驗的完整性約束，共設置7個約束。數據量分別取100、1000、10000、100000條，通過軟件和人工方式對以上數據進行處理，向數據集中插入不一致數據。

利用傳統(tǒng)的K-means方法與本文方法進行相似重復記錄檢測，并從三方面檢測本文算法：查準率、查全率和算法運行時間。

從圖1和圖2中可以看出，本文提出的方法不論是在查準率還是查全率上都要高于傳統(tǒng)的K-means方放。隨著數據量的增大，兩種方法在查準率和查全率上都有所下降，但本文所提出的方法仍然要比傳統(tǒng)K-means的比例高。這主要是因為本文方法根據完整性約束為不一致數據提供了更多的語義聯(lián)系，使得記錄之間在某種概率上擁有了更多相似的屬性值。從圖3可以看出本文提出的方法在運行時間上隨著數據量的增大而增大，且高于傳統(tǒng)K-means，這是因為在進行相似重復記錄識別之前需要對數據進行處理，要找出數據集中違反了完整性約束的記錄，并對它們進行修復代價計算以及對概率矩陣進行修改，而傳統(tǒng)K-means并不需要對數據進行以上操作。

表12　修改后的概率矩陣

表13　實驗數據CUSTOMER表結構

圖1　兩種方法查準率的比較

圖2　兩種方法查全率的比較

圖3　兩種方法在運行時間上的比較

6　結語

數據重復問題是影響數據質量的關鍵問題。本文將數據修復與概率模型相結合，通過實驗驗證了這個方法的可行性。本文的方法將字段之間的比較轉化為數值型概率計算，克服了字段屬性不易于計算的缺點。又根據完整性約束獲得記錄之間的額外信息。本方法在修復過程中并未考慮刪除和增加一條記錄的候選修復，在后續(xù)研究過程中，需要增加對這兩種修復的概率模型修改。

［1］吳愛華.不一致關系數據庫上的初始信任標記算法［J］.計算機研究與發(fā)展，2010：208～214

［2］JL Alberto，AO Mendelzon.Merging Database Under Constraints［J］.International Journal Of Cooperative，1993

［3］M Hua，J Pei，X Lin.Ranking Queries on Uncertain Data［J］.Database System.Volume 42，2011：9～32

［4］A.McCallum.Information Extraction：Distilling Structured Data from Unstructured Text［J］.ACM Queue，2005，3（9）：48～57

［5］Charu C.Aggarwal，Chandan K.Reddy.Data Clustering Algorithms and Application［M］.CRC Press.2013

［6］H.B.Newcombe，J.M.Kennedy，S.Axford，and A.James.Automatic Linkage of Vital Records.Science，vol.130，no.3381：954-959，Oct.1959

［7］A.K.Elmagarmid，P.G.Ipeirotis，V.S.Verykios.Duplicate Record Detection：A Survey［J］.TKDE，2007，19（1）：1～16

［8］Monge A，Elkan C.An Efficient Domain-Independent Algorithm for Detecting Approximately Duplicate Database Records［C］.Proc. SIGMOD Workshop Data Mining and Knowledge Discovery，ACM Press，1997：267～27

［9］Gravano L，Ipeirotis P G，Jagadish H V，et al.Using Q-grams in a DBMS for Approximate String Processing［C］.IEEE Data Eng.Bull，2001，24（4）：28～34

［10］Hernández M A，Stolfo S J.The Merge/Purge Problem for Large Databases［C］.Proc.1995 ACM SIGMOD Int.Conf.Management of Data，ACM Press，1995：127～13

［11］A.E.Monge and C.P.Elkan."The Field Matching Problem：Algorithms and Applications."Proc.Second Int’l Conf.Knowledge Discovery and Data Mining（KDD'96），pp.267～270，1996

［12］李默涵，王宏志，李建中，高宏.一種基于二分圖最優(yōu)匹配的重復記錄檢測算法［C］.中國數據庫學術會議（NDBC），2009，46（z2）：339-345

［13］Li Mohan，Wang Hongzhi，Li Jianzhong，GaoHong.Efficient Duplicate Record Dection Based on Similarity Estimation［C］.In Web-Age Information Management（WAIM 2010），2010，6814：595-607

［14］王宏志，樊文飛.復雜數據上的實體識別技術研究［J］.計算機學報，V01.34 No.10：1843～1852

［15］李默涵.多數據源環(huán)境下重復記錄檢測問題的研究［D］，2011，6184：595～607

［16］Periklis Andritsos，Panayiotis Tsaparas，Ren'ee J.Miller，Kenneth C.Sevcik.LIMBO：Scalable Clustering of Categorical Data［C］.Advances in Database Technology-EDBT 2004.Volume 2992，2004：123～146

［17］Periklis Andritsos，Panayiotis Tsaparas，Ren'ee J..Clean Answers over Dirty Databases：A Probabilistic Approach［C］.In：ICDE，p. 30（2006）

［18］TPC Benchmark H：Standard Specification.2009.http：//www.tpc.org/tpch

［19］Philip Bohannon，Wenfei Fan，Michael Flaster.A Cost Based Model and Effective Heuristic for Repairing Constraints by Value Modification［C］.SIGMOD 2005

Duplicate Detection；Probabilistic；Integrity Constraints

Similar Duplicate Identification in Inconsistencies Relationship Data of Fusion Repair Cost

SHEN Chen，ZENG Wei-ming，WU Ai-hua
（College of Information Technology，Shanghai Maritime University，ShangHai 201306）

國家自然科學基金項目（No.61202022）

1007-1423（2015）17-0003-07

10.3969/j.issn.1007-1423.2015.17.001

沈忱（1990-），女，上海人，碩士研究生，研究方向數據庫

曾衛(wèi)明（1971-），男，安徽人，教授，研究方向圖像處理與模式識別、數據挖掘、腦科學與人工智能等

吳愛華（1976-），女，江西人，副教授，研究方向數據質量、數據挖掘、RFID數據流管理、Web Service和社區(qū)網絡等

2015-04-09

2015-05-21

采用對不一致數據上的修復以及將記錄上的屬性值用概率表示來解決不一致數據庫中相似重復記錄的識別。目前對重復記錄識別的研究都是直接對不一致數據進行比較的。利用完整性約束對數據進行修復的概念，找到不一致的分量，發(fā)現在其上的其余可能值，充分考慮字段之間的語義關系；利用LIMBO概率模型，用數值型概率表示分類數據，克服記錄不便于計算的缺點。

重復記錄識別；概率；完整性約束

Uses repairs of inconsistent and data and attributes of values expressed as probabilities to detect duplicate records in database.Researches on identification of duplicate are now being directly compared with inconsistent data.To increase similarities between records，uses integrity constraints to fix data finding inconsistent component and more possible values on them based on the concepts of data recovery. Uses LIMBO probabilistic model，values will be converted into numeric overcoming the disadvantages of which is not easy to calculate.