基于可信度模型的重復主數據檢測算法

王繼奎，李少波

(1. 中國科學院成都計算機應用研究所，成都 6 10041；2. 貴州大學省部共建現代制造技術教育部重點實驗室，貴陽 5 50003；3. 蘭州商學院信息工程學院，蘭州 730 020)

基于可信度模型的重復主數據檢測算法

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

(1. 中國科學院成都計算機應用研究所，成都 6 10041；2. 貴州大學省部共建現代制造技術教育部重點實驗室，貴陽 5 50003；3. 蘭州商學院信息工程學院，蘭州 730 020)

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

多數據源；重復主數據；可信度模型；檢測算法；數據可信度

1 概述

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

2 主數據重復記錄檢測模型

2.1 符號、縮寫及其含義

符號、縮寫及其含義如表1所示。

表1 符號、縮寫及其含義

2.2 術語定義

定義1屬性相似度：sim(ri.attrk, rj.attrk)表示記錄ri與rj的k屬性相似度；其計算方法是若2個屬性ri.attrk，rj.attrk是相似的，當且僅當2個字段的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轉化為字符串，逐一掃描2個字符串數組，若字符相等，則score值為1，否則向后掃描rj.attrk；若ri.attrk掃描結束，則算法結束。

由于ri、rj具有相同的關系模式，因此|ri|=|rj|=n，相似度計算公式轉變為：

其中，RD代表識別出的重復記錄的集合；RO代表實際重復記錄的集合。

定義4準確率：

2.3 識別主數據重復記錄的規則

2.3.1 sourceKeys計算規則的記錄

規則1記錄i的sourceKeys由記錄的業務主鍵與記錄來源系統決定。

2.3.2 重復規則的記錄

關系R為重復關系，R’為不重復關系。

規則2若記錄的sourceKeys相同，則記錄為重復記錄。

規則3若2條記錄相似度大于閾值，則2條記錄重復。

2.4 多數據源可信度定義

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

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

(1)從主數據系統的建設實踐中總結出長的字段更可信，主要是因為重復主數據很多是縮寫、簡寫造成的；

(2)在長度相同的基礎上，來源系統可信度大的數據更可信；

(3)字段長度與來源系統的可信度均相等，從實踐上發現這樣的重復主數據大多是來源于同一業務系統，這種情況下記錄的最后更新時間可以作為數據可信的依據，因為最后更新的數據應該是現實世界的真值，也更可信。

2.5 重復主數據檢測

重復主數據檢測模型如圖1所示。

圖1 重復主數據檢測模型

重復主數據檢測算法步驟具體如下：

(1)從各業務系統中抽取進入主數據系統的存量數據。

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

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

(4)采用fastCdrDetection(Fast Cluster Duplicate Records Detection)算法進行聚類，隊列每個節點的代表記錄為本聚類的可信記錄。

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

3 fastCdrDetection檢測算法

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

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

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

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

輸出相似度比較結果

f1Array，f2Array為ri.attrk，rj.attrk的字符串數組；k與m為指向f1Array，f2Array的指針，初始值為0；count統計字符相同的結果，初始值位0。

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

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

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

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

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

輸出聚類m的可信記錄

參數：change: boolean，初始值位false。

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

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

算法4matchKeys生成算法

思路：根據主數據管理業務需要，選取特定字段或者字段集作為matchKeys生成字段，將各生成字段的轉換為字符串，然后連接起來作為matchKeys。

算法5 fastCdrDetection算法

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

采用優先隊列策略識別重復記錄的精度很大程度上依賴于排序所選擇的關鍵字，第一關鍵字的選擇要結合業務應用場景，為了快速檢測來源于同一系統、具有同一業務主鍵的重復記錄，采用sourceKeys作為第二排序關鍵字。優先隊列算法選擇進入聚類的第一條記錄作為代表記錄，而fastCdrDetection算法采用可信記錄作為代表記錄，采用動態的、不斷變好的可信記錄替換進入聚類的第一條記錄作為聚類的代表記錄，提高了檢測結果的準確率與召回率。

輸入排序后的記錄集recordSet

輸出重復記錄檢測結果

參數：PQ表示優先隊列，maxPriority表示當前最高優先級。

算法分析：

由于采用了對來源于同一業務系統、具有同樣業務主鍵的重復記錄進行了預先處理，在比較相似度時先比較記錄的sourceSystem，因此在實際應用中fastCdrDetection算法具有更高的效率，來源于同一業務系統、具有同一業務主鍵的重復記錄越多，則算法效率越高；在記錄相似度計算時，采用本文聚類的可信記錄代替進入聚類的第一條記錄，相似度計算結果也具有更高的準確性。

4 實驗與結果分析

由于優先隊列算法項的代表記錄采用的是聚類的第一條記錄，導致記錄相似度比較的結果失真，算法的準確率與召回率降低；fastCdrDetection檢測算法采用可信記錄代替作為聚類的代表記錄，并在檢測過程中首先檢測來源于同一數據源的數據的sourceKeys，能較快的檢測出來源于同一數據源的重復記錄。

實驗驗證程序采用Java語言編寫，在Win7 64位操作系統、Jre1.6環境下運行。實驗采用的數據為來源于物資基建系統供應商主數據63萬余條及模擬噪聲數據23萬余條。主要對比PQS算法與fastCdrDetection算法的運行時間、召回率、準確率。

4.1 相似度算法對比

fastCdrDetection算法使用的字符串相似度算法是非遞歸的基于位置編碼的匹配算法，屬性相似度算法對比實驗以PCM算法為對比對象。取某電網公司前1 000條供應商名稱作為測試數據進行測試。

(1)算法準確率

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

圖2 算法準確率對比

(2)算法召回率

對比實驗表明，FieldMatch一直比PCM算法召回率高。通過分析真實數據發現，由于PCM算法采取了罰分的思路，導致一些表示同一供應商實體的數據沒有被識別出來，而FieldMatch則能較好地識別。圖3中字段相似度閾值t∈(0,1]，算法召回率R∈(0,1]。

圖3 算法召回率對比

(3)算法識別出的重復聚類數對比

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

圖4 算法識別出的聚類數對比

4.2 P QS算法與fastCdrDetection算法對比

實驗采用數據為供應商數據，總計10 146條，記錄相似度閾值為0.9，屬性相似度閾值為0.8，通過人工識別重復記錄數位42條，PQS算法與fastCdrDetection算法性能對比如表2所示。

表2 算法性能對比

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

4.3 運行參數對算法的影響

采用某電網公司基建物資聯系人表中的前6 0 00條數據進行測試，數據規模對算法性能的影響如表3所示。

表3 數據規模對算法性能的影響

由表3可以看出，隨著規模的增加，每條記錄的處理時間也在不斷增加，聚類數也在增加，這說明對海量數據必須進行分組處理，并合理控制優先隊列的長度。

5 結束語

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

[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] 韓京宇, 徐立臻, 董逸生. 數據質量研究綜述[J]. 計算機科學, 2008, 35(2): 1-5.

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

[4] 陳 偉, 丁秋林. 可擴展數據清理平臺的研究[J]. 電子科技大學學報, 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] 張 永, 遲忠先, 閆德勤. 數據倉庫ETL中相似重復記錄的檢測方法及應用[J]. 計算機應用, 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] 李 堅, 鄭 寧. 對基于MPN數據清洗算法的改進[J].計算機應用與軟件, 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] 李亞坤, 王宏志. 基于實體描述屬性技術的XML重復對象檢測方法[J]. 計算機學報, 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

國家科技支撐計劃基金資助項目(2012BAF12B14)。

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

2013-04-02

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

1000-3428(2014)05-0031-05

A

TP311