融合修復(fù)代價(jià)的不一致關(guān)系數(shù)據(jù)中相似重復(fù)記錄識(shí)別

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

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

融合修復(fù)代價(jià)的不一致關(guān)系數(shù)據(jù)中相似重復(fù)記錄識(shí)別

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

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0　引言

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

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

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

表1　Details表

表2　Patients表

函數(shù)依賴：

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

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

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

1　相關(guān)工作

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

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

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

2　數(shù)據(jù)修復(fù)代價(jià)計(jì)算

本節(jié)借鑒文獻(xiàn)［1］中所用到的數(shù)據(jù)修復(fù)、違反包、修復(fù)代價(jià)以及沖突類(lèi)的概念，在此簡(jiǎn)單介紹。

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

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

表3　違反包與候選修復(fù)代價(jià)

沖突類(lèi)的修復(fù)代價(jià)是指一種候選修復(fù)解決其對(duì)應(yīng)的違反包所產(chǎn)生的代價(jià)之和。從上表可以看出一個(gè)違反包可以有多個(gè)候選修復(fù)，而一個(gè)候選修復(fù)也可以解決多個(gè)違反包，如表1中r1可以同時(shí)修復(fù)C1、C2兩個(gè)違反包。如果該修復(fù)覆蓋的違反包越多，那么被修復(fù)對(duì)象錯(cuò)誤的可能性就越大。沖突類(lèi)的覆蓋修復(fù)代價(jià)是指沖突類(lèi)的修復(fù)代價(jià)/該沖突上某種候選修復(fù)能夠解決的違反包個(gè)數(shù)。但是，在修復(fù)的同時(shí)也會(huì)導(dǎo)致其他違反包的出現(xiàn)，產(chǎn)生新的沖突類(lèi)，表4為引起新沖突類(lèi)后產(chǎn)生的關(guān)聯(lián)覆蓋代價(jià)。

表4　覆蓋修復(fù)代價(jià)和關(guān)聯(lián)覆蓋修復(fù)代價(jià)

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

3　LIMBO概率矩陣

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

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

則整個(gè)值域V的模為|V|，由此可得一個(gè)n×|V|的矩陣M。如果構(gòu)成記錄xi的屬性值在V中出現(xiàn)，則在矩陣中標(biāo)記M［x，v］=1，否則標(biāo)記為0。因?yàn)槊織l記錄在每個(gè)屬性上存在一個(gè)值，數(shù)據(jù)庫(kù)表定義了m個(gè)屬性，則每條記錄在矩陣上標(biāo)記了m個(gè)1。然后將矩陣一般化，設(shè)每行出現(xiàn)的標(biāo)記之和為1，所以每個(gè)屬性值的概率為p（v|x）=1/m。

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

4　概率矩陣修改

本文是通過(guò)對(duì)不一致數(shù)據(jù)進(jìn)行修復(fù)，根據(jù)各違反包的修復(fù)代價(jià)來(lái)修改概率矩陣的，以下詳細(xì)給出在不同修復(fù)情況下概率改變的計(jì)算方法。

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

（1）違反包含依賴的修復(fù)一般都是成對(duì)出現(xiàn)，形如：

修改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）。對(duì)于t1、t2來(lái)說(shuō)t1［y］和t2［y］都是可能取到的值，所以將這兩個(gè)修復(fù)結(jié)合來(lái)看。

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

表6

表7　概率修改

表8

表9　修改概率可得

（2）修復(fù)為t［x］≠y時(shí)且修復(fù)代價(jià)最?。ū?0）及其概率修改計(jì)算（表11）

表10

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

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

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

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

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

利用傳統(tǒng)的K-means方法與本文方法進(jìn)行相似重復(fù)記錄檢測(cè)，并從三方面檢測(cè)本文算法：查準(zhǔn)率、查全率和算法運(yùn)行時(shí)間。

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

表12　修改后的概率矩陣

表13　實(shí)驗(yàn)數(shù)據(jù)CUSTOMER表結(jié)構(gòu)

圖1　兩種方法查準(zhǔn)率的比較

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

圖3　兩種方法在運(yùn)行時(shí)間上的比較

6　結(jié)語(yǔ)

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

［1］吳愛(ài)華.不一致關(guān)系數(shù)據(jù)庫(kù)上的初始信任標(biāo)記算法［J］.計(jì)算機(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)匹配的重復(fù)記錄檢測(cè)算法［C］.中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議（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］王宏志，樊文飛.復(fù)雜數(shù)據(jù)上的實(shí)體識(shí)別技術(shù)研究［J］.計(jì)算機(jī)學(xué)報(bào)，V01.34 No.10：1843～1852

［15］李默涵.多數(shù)據(jù)源環(huán)境下重復(fù)記錄檢測(cè)問(wè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）

國(guó)家自然科學(xué)基金項(xiàng)目（No.61202022）

1007-1423（2015）17-0003-07

10.3969/j.issn.1007-1423.2015.17.001

沈忱（1990-），女，上海人，碩士研究生，研究方向數(shù)據(jù)庫(kù)

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

吳愛(ài)華（1976-），女，江西人，副教授，研究方向數(shù)據(jù)質(zhì)量、數(shù)據(jù)挖掘、RFID數(shù)據(jù)流管理、Web Service和社區(qū)網(wǎng)絡(luò)等

2015-04-09

2015-05-21

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

重復(fù)記錄識(shí)別；概率；完整性約束

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.