基于可信度模型的重復(fù)主數(shù)據(jù)檢測算法

王繼奎，李少波

(1. 中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，成都 6 10041；2. 貴州大學(xué)省部共建現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴陽 5 50003；3. 蘭州商學(xué)院信息工程學(xué)院，蘭州 730 020)

基于可信度模型的重復(fù)主數(shù)據(jù)檢測算法

王繼奎1,2,3，李少波1,2

(1. 中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，成都 6 10041；2. 貴州大學(xué)省部共建現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴陽 5 50003；3. 蘭州商學(xué)院信息工程學(xué)院，蘭州 730 020)

針對(duì)來源于多個(gè)業(yè)務(wù)系統(tǒng)的重復(fù)主數(shù)據(jù)影響主數(shù)據(jù)質(zhì)量、主數(shù)據(jù)同步及主數(shù)據(jù)挖掘等問題，提出重復(fù)主數(shù)據(jù)檢測算法fastCdrDetection。從數(shù)據(jù)可信度的角度出發(fā)，在考慮數(shù)據(jù)源可信度、數(shù)據(jù)最后更新時(shí)間及數(shù)據(jù)長度的基礎(chǔ)上，建立主數(shù)據(jù)可信度模型，并實(shí)現(xiàn)可信記錄生成算法。設(shè)計(jì)非遞歸的字符串相似度計(jì)算算法FiledMatch，解決了由中文簡寫、縮寫、錯(cuò)誤拼寫造成的主數(shù)據(jù)重復(fù)問題，采用sourceKeys算法對(duì)來源于同一業(yè)務(wù)系統(tǒng)、具有同樣業(yè)務(wù)主鍵的重復(fù)記錄進(jìn)行預(yù)處理，從而提高重復(fù)主數(shù)據(jù)檢測效率。通過對(duì)某電網(wǎng)基建物資63萬余條供應(yīng)商存量數(shù)據(jù)及23萬余條模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明，與PQS算法相比，fastCdrDetection算法的召回率由74%提高到88%，準(zhǔn)確率由61%提高到95%，證明了算法的有效性。

多數(shù)據(jù)源；重復(fù)主數(shù)據(jù)；可信度模型；檢測算法；數(shù)據(jù)可信度

1 概述

重復(fù)主數(shù)據(jù)會(huì)對(duì)主數(shù)據(jù)質(zhì)量、主數(shù)據(jù)同步及主數(shù)據(jù)挖掘等操作產(chǎn)生不良影響[1]，如何檢測重復(fù)主數(shù)據(jù)是十分重要的研究課題。文獻(xiàn)[2]對(duì)重復(fù)記錄進(jìn)行了定義，文獻(xiàn)[3]提出識(shí)別相似重復(fù)記錄的5個(gè)基本步驟：數(shù)據(jù)預(yù)處理，縮小搜索空間，相似重復(fù)記錄識(shí)別，相似重復(fù)記錄清除和驗(yàn)證。文獻(xiàn)[4]提出由召回率與準(zhǔn)確率2個(gè)標(biāo)準(zhǔn)度量重復(fù)記錄識(shí)別的有效性。在字段識(shí)別方面，文獻(xiàn)[5]提出著名的S-W遞歸算法，文獻(xiàn)[6]對(duì)S-W算法進(jìn)行了改進(jìn)，加入了擴(kuò)大的遞歸變量，提高了運(yùn)行效率。文獻(xiàn)[7]提出非遞歸算法以及PCM算法。在實(shí)際應(yīng)用中，發(fā)現(xiàn)主數(shù)據(jù)重復(fù)主要由中文簡寫、縮寫、錯(cuò)誤拼寫造成，針對(duì)這3種情況，提出一種非遞歸的字符串相似度計(jì)算算法FieldMatch。目前的重復(fù)記錄檢測算法主要基于排序-比較-合并的思路，常用的算法有近鄰排序法SNM[8]、多趟近鄰排序法MPN[9]、優(yōu)先隊(duì)列算法PQS[10]。文獻(xiàn)[11]設(shè)計(jì)的Max-merge算法兼顧了閉包算法[12]相似的傳遞性與獨(dú)立性，對(duì)XML對(duì)象識(shí)別有較高的準(zhǔn)確率與召回率。本文從數(shù)據(jù)可信度的角度出發(fā)，建立主數(shù)據(jù)可信度模型，基于主數(shù)據(jù)可信度模型改進(jìn)了PQS算法，對(duì)每一個(gè)聚類采用可信記錄作為代表記錄參與相似度計(jì)算，以提高檢測算法的召回率與準(zhǔn)確率，并采用某電網(wǎng)公司的供應(yīng)商主數(shù)據(jù)存量數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

2 主數(shù)據(jù)重復(fù)記錄檢測模型

2.1 符號(hào)、縮寫及其含義

符號(hào)、縮寫及其含義如表1所示。

表1 符號(hào)、縮寫及其含義

2.2 術(shù)語定義

定義1屬性相似度：sim(ri.attrk, rj.attrk)表示記錄ri與rj的k屬性相似度；其計(jì)算方法是若2個(gè)屬性ri.attrk，rj.attrk是相似的，當(dāng)且僅當(dāng)2個(gè)字段的sim(ri.attrk, rj.attrk)＞t。ri.attrk.el代表i的k屬性的字符，score(ri.attrk, rj.attrk)表示記錄i的屬性k的字符與記錄j的屬性k的字符匹配值，score (ri.attrk, rj.attrk)∈[0,1]、|ri.attrk|＜|rj.attrk|。將ri.attrk，rj.attrk轉(zhuǎn)化為字符串，逐一掃描2個(gè)字符串?dāng)?shù)組，若字符相等，則score值為1，否則向后掃描rj.attrk；若ri.attrk掃描結(jié)束，則算法結(jié)束。

由于ri、rj具有相同的關(guān)系模式，因此|ri|=|rj|=n，相似度計(jì)算公式轉(zhuǎn)變?yōu)椋?/p>

其中，RD代表識(shí)別出的重復(fù)記錄的集合；RO代表實(shí)際重復(fù)記錄的集合。

定義4準(zhǔn)確率：

2.3 識(shí)別主數(shù)據(jù)重復(fù)記錄的規(guī)則

2.3.1 sourceKeys計(jì)算規(guī)則的記錄

規(guī)則1記錄i的sourceKeys由記錄的業(yè)務(wù)主鍵與記錄來源系統(tǒng)決定。

2.3.2 重復(fù)規(guī)則的記錄

關(guān)系R為重復(fù)關(guān)系，R’為不重復(fù)關(guān)系。

規(guī)則2若記錄的sourceKeys相同，則記錄為重復(fù)記錄。

規(guī)則3若2條記錄相似度大于閾值，則2條記錄重復(fù)。

2.4 多數(shù)據(jù)源可信度定義

定義5數(shù)據(jù)源可信度ri.sTScore。目前為簡便計(jì)算，ri.sTScore由系統(tǒng)賦初始值，ri.sTScore∈(0,1)。

定義6字段可信度ri.attrk.tScore。由字段的數(shù)據(jù)源、記錄的最后更新時(shí)間、字段長度共同決定。其依據(jù)為：

(1)從主數(shù)據(jù)系統(tǒng)的建設(shè)實(shí)踐中總結(jié)出長的字段更可信，主要是因?yàn)橹貜?fù)主數(shù)據(jù)很多是縮寫、簡寫造成的；

(2)在長度相同的基礎(chǔ)上，來源系統(tǒng)可信度大的數(shù)據(jù)更可信；

(3)字段長度與來源系統(tǒng)的可信度均相等，從實(shí)踐上發(fā)現(xiàn)這樣的重復(fù)主數(shù)據(jù)大多是來源于同一業(yè)務(wù)系統(tǒng)，這種情況下記錄的最后更新時(shí)間可以作為數(shù)據(jù)可信的依據(jù)，因?yàn)樽詈蟾碌臄?shù)據(jù)應(yīng)該是現(xiàn)實(shí)世界的真值，也更可信。

2.5 重復(fù)主數(shù)據(jù)檢測

重復(fù)主數(shù)據(jù)檢測模型如圖1所示。

圖1 重復(fù)主數(shù)據(jù)檢測模型

重復(fù)主數(shù)據(jù)檢測算法步驟具體如下：

(1)從各業(yè)務(wù)系統(tǒng)中抽取進(jìn)入主數(shù)據(jù)系統(tǒng)的存量數(shù)據(jù)。

(2)根據(jù)主數(shù)據(jù)的數(shù)據(jù)格式要求對(duì)存量數(shù)據(jù)進(jìn)行預(yù)處理，計(jì)算sourceKeys與matchKeys，并從源數(shù)據(jù)庫日志中獲取數(shù)據(jù)的lsDate，填充到待檢測數(shù)據(jù)集中。

(3)以matchkeys為第一排序關(guān)鍵字，sourceKeys為第二關(guān)鍵字升序排序。

(4)采用fastCdrDetection(Fast Cluster Duplicate Records Detection)算法進(jìn)行聚類，隊(duì)列每個(gè)節(jié)點(diǎn)的代表記錄為本聚類的可信記錄。

(5)輸出聚類記錄數(shù)大于1的聚類記錄。

3 fastCdrDetection檢測算法

算法1屬性相似度sim(ri.attrk, rj.attrk)算法

思路：屬性值數(shù)字型或boolean，完全相等，相似度為1，否則為0；其他類型統(tǒng)一處理成字符串。

屬性相似度計(jì)算是計(jì)算記錄相似度的基礎(chǔ)，目前主要有基本的字段匹配算法與遞歸的字段匹配算法2種，主要針對(duì)英文字符串的相似度研究。通過分析主數(shù)據(jù)管理系統(tǒng)中，常出現(xiàn)的不一致表現(xiàn)主要為縮寫、簡寫與錯(cuò)寫，采用FieldMatch字符串比較算法。

輸入帶比較的2個(gè)記錄的屬性值ri.attrk，rj.attrk

輸出相似度比較結(jié)果

f1Array，f2Array為ri.attrk，rj.attrk的字符串?dāng)?shù)組；k與m為指向f1Array，f2Array的指針，初始值為0；count統(tǒng)計(jì)字符相同的結(jié)果，初始值位0。

算法分析：將ri.attrk轉(zhuǎn)化為字符數(shù)組，每個(gè)字符即ri.attrk的原子串，將rj.attrk轉(zhuǎn)化為字符數(shù)組，掃描一遍2個(gè)數(shù)組，統(tǒng)計(jì)相同字符的個(gè)數(shù)。設(shè)ri.attrk對(duì)應(yīng)的數(shù)組長度為m，rj.attrk對(duì)應(yīng)的數(shù)組長度為n，最好情況需要比較min(m,n)，最壞情況需要比較max(m,n)。

算法2記錄相似度similarity(ri, rj)算法

思路：ri.soruceKey=rj.soruceKey表示ri，rj是來源于同一業(yè)務(wù)系統(tǒng)的同一實(shí)體，similarity(ri, rj)值為1；否則根據(jù)式(3)計(jì)算相似度。

算法3可信記錄生成算法getTrustedRecord

輸入待檢測記錄ri，聚類m的可信記錄trustedRecord(m)

輸出聚類m的可信記錄

參數(shù)：change: boolean，初始值位false。

思路：計(jì)算待檢測記錄ri與聚類m的可信記錄trusted-Record(m)的相似度；若相似度大于閾值，同一字段值不同，則選取可信度更高的字段值作為可信記錄的字段值，生成可信記錄。

算法分析：在計(jì)算聚類的代表記錄(可信記錄)時(shí)，需要根據(jù)可信度模型計(jì)算字段的可信度進(jìn)而生成可信記錄，與PQS算法相比會(huì)產(chǎn)生額外開銷。從實(shí)驗(yàn)結(jié)果可看出，處理10 146條供應(yīng)商數(shù)據(jù)fastCdrDetection算法耗時(shí)14 660 ms，而PQS算法耗時(shí)14 430 ms，平均每條數(shù)據(jù)fastCdrDetection算法多耗時(shí)0.022 7 ms。

算法4matchKeys生成算法

思路：根據(jù)主數(shù)據(jù)管理業(yè)務(wù)需要，選取特定字段或者字段集作為matchKeys生成字段，將各生成字段的轉(zhuǎn)換為字符串，然后連接起來作為matchKeys。

算法5 fastCdrDetection算法

思路：fastCdrDetection算法基于排序-檢測-合并思路。首先利用matchKeys作為第一排序關(guān)鍵字，sourceKeys作為第二排序關(guān)鍵字對(duì)記錄進(jìn)行排序。順序掃描記錄集，比較當(dāng)前記錄ri與優(yōu)先隊(duì)列包含的可信記錄，若在優(yōu)先隊(duì)列中有重復(fù)記錄，則將這條記錄合并入匹配記錄所在的聚類中，包含這個(gè)記錄的聚類進(jìn)入優(yōu)先隊(duì)列并有最高的優(yōu)先級(jí)；若掃描整個(gè)優(yōu)先隊(duì)列后發(fā)現(xiàn)ri不屬于任何一個(gè)聚類，則生成新的聚類加入優(yōu)先隊(duì)列，并使其具有最高優(yōu)先級(jí)。將ri加入該聚類中，成為該聚類的可信記錄。最后輸出所有聚類記錄數(shù)大于1的聚類記錄，即為重復(fù)記錄。

采用優(yōu)先隊(duì)列策略識(shí)別重復(fù)記錄的精度很大程度上依賴于排序所選擇的關(guān)鍵字，第一關(guān)鍵字的選擇要結(jié)合業(yè)務(wù)應(yīng)用場景，為了快速檢測來源于同一系統(tǒng)、具有同一業(yè)務(wù)主鍵的重復(fù)記錄，采用sourceKeys作為第二排序關(guān)鍵字。優(yōu)先隊(duì)列算法選擇進(jìn)入聚類的第一條記錄作為代表記錄，而fastCdrDetection算法采用可信記錄作為代表記錄，采用動(dòng)態(tài)的、不斷變好的可信記錄替換進(jìn)入聚類的第一條記錄作為聚類的代表記錄，提高了檢測結(jié)果的準(zhǔn)確率與召回率。

輸入排序后的記錄集recordSet

輸出重復(fù)記錄檢測結(jié)果

參數(shù)：PQ表示優(yōu)先隊(duì)列，maxPriority表示當(dāng)前最高優(yōu)先級(jí)。

算法分析：

由于采用了對(duì)來源于同一業(yè)務(wù)系統(tǒng)、具有同樣業(yè)務(wù)主鍵的重復(fù)記錄進(jìn)行了預(yù)先處理，在比較相似度時(shí)先比較記錄的sourceSystem，因此在實(shí)際應(yīng)用中fastCdrDetection算法具有更高的效率，來源于同一業(yè)務(wù)系統(tǒng)、具有同一業(yè)務(wù)主鍵的重復(fù)記錄越多，則算法效率越高；在記錄相似度計(jì)算時(shí)，采用本文聚類的可信記錄代替進(jìn)入聚類的第一條記錄，相似度計(jì)算結(jié)果也具有更高的準(zhǔn)確性。

4 實(shí)驗(yàn)與結(jié)果分析

由于優(yōu)先隊(duì)列算法項(xiàng)的代表記錄采用的是聚類的第一條記錄，導(dǎo)致記錄相似度比較的結(jié)果失真，算法的準(zhǔn)確率與召回率降低；fastCdrDetection檢測算法采用可信記錄代替作為聚類的代表記錄，并在檢測過程中首先檢測來源于同一數(shù)據(jù)源的數(shù)據(jù)的sourceKeys，能較快的檢測出來源于同一數(shù)據(jù)源的重復(fù)記錄。

實(shí)驗(yàn)驗(yàn)證程序采用Java語言編寫，在Win7 64位操作系統(tǒng)、Jre1.6環(huán)境下運(yùn)行。實(shí)驗(yàn)采用的數(shù)據(jù)為來源于物資基建系統(tǒng)供應(yīng)商主數(shù)據(jù)63萬余條及模擬噪聲數(shù)據(jù)23萬余條。主要對(duì)比PQS算法與fastCdrDetection算法的運(yùn)行時(shí)間、召回率、準(zhǔn)確率。

4.1 相似度算法對(duì)比

fastCdrDetection算法使用的字符串相似度算法是非遞歸的基于位置編碼的匹配算法，屬性相似度算法對(duì)比實(shí)驗(yàn)以PCM算法為對(duì)比對(duì)象。取某電網(wǎng)公司前1 000條供應(yīng)商名稱作為測試數(shù)據(jù)進(jìn)行測試。

(1)算法準(zhǔn)確率

實(shí)驗(yàn)表明，PCM由于采取了罰分的手段，針對(duì)中文識(shí)別，識(shí)別準(zhǔn)確率不穩(wěn)定；FieldMatch算法是基于統(tǒng)計(jì)的方法，順次掃描2個(gè)字符串，指針一直向后掃描不回歸，如果存在不一致的字符，則匹配結(jié)束。針對(duì)主數(shù)據(jù)管理系統(tǒng)常出現(xiàn)的中文縮寫、簡寫等情況，F(xiàn)ieldMatch相似度比較的準(zhǔn)確度更高。實(shí)驗(yàn)結(jié)果表明，F(xiàn)ieldMatch針對(duì)主數(shù)據(jù)中文識(shí)別準(zhǔn)確率隨著閾值的提高而逐漸穩(wěn)步提高。圖2中字段相似度閾值t∈(0,1]，算法準(zhǔn)確率P∈(0,1]。

圖2 算法準(zhǔn)確率對(duì)比

(2)算法召回率

對(duì)比實(shí)驗(yàn)表明，F(xiàn)ieldMatch一直比PCM算法召回率高。通過分析真實(shí)數(shù)據(jù)發(fā)現(xiàn)，由于PCM算法采取了罰分的思路，導(dǎo)致一些表示同一供應(yīng)商實(shí)體的數(shù)據(jù)沒有被識(shí)別出來，而FieldMatch則能較好地識(shí)別。圖3中字段相似度閾值t∈(0,1]，算法召回率R∈(0,1]。

圖3 算法召回率對(duì)比

(3)算法識(shí)別出的重復(fù)聚類數(shù)對(duì)比

實(shí)驗(yàn)結(jié)果表明，PCM算法識(shí)別出的聚類數(shù)始終比FieldMatch算法少，隨著閾值的增加2種算法識(shí)別出的重復(fù)聚類數(shù)不斷減少。通過分析發(fā)現(xiàn)隨著閾值的增加屬性相似的要求變得越來越高，導(dǎo)致重復(fù)的聚類數(shù)不斷減少。由于PCM是基于位置的罰分算法，使得計(jì)算所得的相似度低于FieldMatchs算法，因此實(shí)驗(yàn)結(jié)果表明，F(xiàn)ieldMatch算法在相同閾值設(shè)置的情況下發(fā)現(xiàn)的重復(fù)聚類數(shù)比PCM算法多。圖4中字段相似度閾值t∈(0,1]，聚類個(gè)數(shù)n是一個(gè)整數(shù)。

圖4 算法識(shí)別出的聚類數(shù)對(duì)比

4.2 P QS算法與fastCdrDetection算法對(duì)比

實(shí)驗(yàn)采用數(shù)據(jù)為供應(yīng)商數(shù)據(jù)，總計(jì)10 146條，記錄相似度閾值為0.9，屬性相似度閾值為0.8，通過人工識(shí)別重復(fù)記錄數(shù)位42條，PQS算法與fastCdrDetection算法性能對(duì)比如表2所示。

表2 算法性能對(duì)比

可以看出，在同樣運(yùn)行參數(shù)的情況下，fastCdrDetection算法比PQS算法的召回率與準(zhǔn)確率高。通過分析實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn)，由于fastCdrDetection算法采用基于可信度計(jì)算，利用更好的記錄代替PQS算法第一條記錄(或者是最后一條)參與相似度計(jì)算，相似度計(jì)算的結(jié)果更接近實(shí)際結(jié)果，因此算法的召回率與準(zhǔn)確率較高。然而，fastCdrDetection采用更好的記錄替代PQS的代表記錄，因此運(yùn)算時(shí)間比PQS算法略長。但由于采用sourceKeys快速計(jì)算記錄的相似度，隨著來源于同一源系統(tǒng)的重復(fù)記錄的增加，會(huì)縮短fastCdr-Detection的運(yùn)算時(shí)間。

4.3 運(yùn)行參數(shù)對(duì)算法的影響

采用某電網(wǎng)公司基建物資聯(lián)系人表中的前6 0 00條數(shù)據(jù)進(jìn)行測試，數(shù)據(jù)規(guī)模對(duì)算法性能的影響如表3所示。

表3 數(shù)據(jù)規(guī)模對(duì)算法性能的影響

由表3可以看出，隨著規(guī)模的增加，每條記錄的處理時(shí)間也在不斷增加，聚類數(shù)也在增加，這說明對(duì)海量數(shù)據(jù)必須進(jìn)行分組處理，并合理控制優(yōu)先隊(duì)列的長度。

5 結(jié)束語

重復(fù)主數(shù)據(jù)檢測是主數(shù)據(jù)集成的熱門研究課題，從數(shù)據(jù)可信度的角度出發(fā)，在考慮了數(shù)據(jù)源可信度、數(shù)據(jù)最后更新時(shí)間及數(shù)據(jù)長度的基礎(chǔ)上建立了主數(shù)據(jù)可信度模型，并實(shí)現(xiàn)可信記錄生成算法。本文提出一種非遞歸的字符串相似度計(jì)算FieldMatch算法，較好地解決了由中文簡寫、縮寫、錯(cuò)誤拼寫造成的主數(shù)據(jù)重復(fù)問題。針對(duì)來源于同一數(shù)據(jù)源的重復(fù)主數(shù)據(jù)，設(shè)計(jì)sourceKeys進(jìn)行預(yù)處理，提高算法效率，并提出fastCdrDetection主數(shù)據(jù)重復(fù)記錄檢測算法，對(duì)每一個(gè)聚類采用可信記錄作為代表記錄參與相似度計(jì)算，從而提高檢測算法的召回率與準(zhǔn)確率。采用某電網(wǎng)公司的供應(yīng)商主數(shù)據(jù)存量數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與PQS相比，fastCdrDetection算法的召回率由74%提高到88%，準(zhǔn)確率由61%提高到95%，證明了fastCdrDetection聚類算法有較高的召回率及準(zhǔn)確率。目前可信度模型僅考慮了主數(shù)據(jù)字段的長度、來源系統(tǒng)的可信度及記錄最后更新時(shí)間因素，今后將對(duì)數(shù)據(jù)源的可信度生成算法進(jìn)行研究。

[1] Hernandez M A, Stolfo S J. Real-world D ata is D irty: Data Cleansing and th e Merge/Purge Problem[J]. Data Ming and Knowledge Discovery, 1998, 2(1): 9-37.

[2] 韓京宇, 徐立臻, 董逸生. 數(shù)據(jù)質(zhì)量研究綜述[J]. 計(jì)算機(jī)科學(xué), 2008, 35(2): 1-5.

[3] Batin C, Scannapieca M. Data Quality: Concepts, Methodologies and Techniques[M]. New York, USA: Springer-Verlag, 2006.

[4] 陳 偉, 丁秋林. 可擴(kuò)展數(shù)據(jù)清理平臺(tái)的研究[J]. 電子科技大學(xué)學(xué)報(bào), 2006, 35(1): 100-103.

[5] Smith T F, Waterman M S. Identification of C ommon Molecular Subseque nces[J]. Journal of Molecular Biology, 198 1, 147(1): 195-197.

[6] Nawaz Z, Bertelsk A. Acceleration of Simth-Waterman Using Recursive V ariable Expansion[C]//Proceedings o f the 1 1th EUROMICRO Conference on Digital System Design Architectures, Methods and Tools. Parma, Italy: IEEE Press, 2008: 915-922.

[7] 張 永, 遲忠先, 閆德勤. 數(shù)據(jù)倉庫ETL中相似重復(fù)記錄的檢測方法及應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用, 2006, 26(4): 880-882.

[8] Hernandez M, Stolfo S. The Merge/Purge Problem for Large Databases[C]//Proceedings of ACM SIGMOD International Conference on Management of Data. San Jose, USA: [s. n.], 1995: 127-138.

[9] 李 堅(jiān), 鄭 寧. 對(duì)基于MPN數(shù)據(jù)清洗算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用與軟件, 2008, 25(2): 245-247.

[10] Monge A, Elkan C. An Efficient Domain Independent Algorithm for Detecting A pproximately D uplicate Database Records[C]//Proceedings of SI GMOD Workshop on Data Mining and Knowledge Discovery. Tucson, USA: [s. n.], 1997: 23-29.

[11] 李亞坤, 王宏志. 基于實(shí)體描述屬性技術(shù)的XML重復(fù)對(duì)象檢測方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(11): 2132- 2141.

[12] Whang S E, Menestrina D, Georgiaet K. Entity Resolution with Iterative Blocking[C]//Proceedings of the 35th SI GMOD International Conference on Management of Data. New York, USA: ACM Press, 2009: 219-231.

編輯 陸燕菲

Duplicate Master Data Detection Algorithm Based on Credibility Model

WANG Ji-kui1,2,3, LI Shao-bo1,2

(1. Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu 610041, China; 2. Key Laboratory of Advanced Manufacturing Technology, Ministry of Education, Guizhou University, Guiyang 550003, China; 3. College of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China)

To avoid the effect of duplicate master data from multiple business systems on the quality, synchronization of the master data as well as master data mining, this paper propose a fastCdrDetec tion(Fast Cluster Duplicate Record s Detection) algo rithm, in wh ich a duplicate master data detection model and a credible record ge nerating algorithm are included, c onsidering data source reliabil ity, data refresh time and data length. A non-recursive algorithm FiledMatch is established for character string similar ity calculation. Aiming at the eliminating problems caused by abbreviations and wrong spellings in Chinese input, a sourceKeys algorithm is constructed for pretreatment of duplicate records arising from a same business system and sharing same business keys to achieve high efficiency in duplicate master data detection. Experiments are carried on a power grid with 630 thousand records of raw material and 230 thousand simulated data records. Result shows that the recall rate of the fastCdrDetection algorithm is 88%, while the PQS algorithm is 74%, and the accuracy is 95% to 61%. The effectiveness of the algorithm is verified.

multiple data source; duplicate master data; credibility model; detection algorithm; data credibility

10.3969/j.issn.1000-3428.2014.05.007

國家科技支撐計(jì)劃基金資助項(xiàng)目(2012BAF12B14)。

王繼奎(1978－)，男，副教授、博士研究生，主研方向：數(shù)據(jù)管理，軟件過程技術(shù)，智能計(jì)算；李少波，教授、博士生導(dǎo)師。

2013-04-02

2013-05-27E-mail：wjkweb@163.com

1000-3428(2014)05-0031-05

A

TP311