多數據源沖突的主數據真值發現算法

王繼奎，李少波

（1.中國科學院 成都計算機應用研究所，四川 成都610041；2.貴州大學 現代制造技術教育部重點實驗室，貴州 貴陽550003；3.蘭州商學院 信息工程學院，甘肅 蘭州730020）

0 引 言

數據沖突問題在數據處理領域中早就被提了出來［1］，文獻 ［2－4］在解決數據沖突問題時，往往假設數據源都是獨立的，相互之間沒有關聯。2007年Yin［5］等人首次提出了web環境下多數據源存在依賴的情況下沖突的問題，提出了數據值支持度的概念，就客觀實體的單個屬性如作者姓名的真值發現進行研究，提出了TruthFinder算法，該算法考慮了不同屬性值之間的相互支持關系，通過不同數據值之間的支持度及數據源的準確度修正數據值的可信度，通過數據值的可信度重新計算數據源的準確度，進行迭代計算，設置數據源可信度變化閾值作為算法終止條件。2009年Dong［6，7］等人對數據源存在拷貝的進行了研究，并提出了考慮數據源存在拷貝的情況下數據源及數據值可信度的計算方法。文獻 ［8］考慮了動態數據的真值發現。2010年考明軍［9］等人提出了數據源權威性的概念，采用不同的概率投票方法，將數據源的可信性和數據值的準確性之間的關系運用在投票的思想中，同時考慮不同數據值之間的影響。2012年張志強［10］等人在提出了NEWACCU算法，主要是采用的數據源的準權威度與數據值的投票率的均值作為數據源的可信度參與計算，并對數據值的不同表現形式進行了處理。

主數據集成的過程中經常會出現同一客觀實體有不同描述的情況，應該綜合考慮這些描述，并通過一定的算法生成最可信記錄。目前的沖突數據解決算法關于數據值支持度的計算通常采用字符串相似度算法，由于數據值支持度的計算對整個真值發現算法的有效性有關鍵影響，數據值支持度的計算方法的改進會導致真值發現算法的改進。從主數據集成的業務角度出發，提出了一種非對稱的數據值支持度算法，較好的解決了主數據沖突中常出現的簡寫、少寫、位置調換、錯誤書寫等問題；提出了TRFinder迭代算法，該算法考慮了數據源的可信度和沖突數據值非對稱支持度；在TRFinder算法的基礎上給出了主數據生成的算法。最后通過文獻 ［9］使用的books＿authors數據集及模擬數據集對Vote算法、TruthFinder算法與TRFinder算法進行了對比實驗，結果表明TRFinder算法可以發現更多的客觀對象的真值；即使不是真值也保留了更多地真值信息；算法的準確度由Vote算法的42%、Truth－Finder算法的71%，提升到了81%，驗證了算法的有效性。

1 TRFinder算法

1.1 主數據集成模型

主數據集成一般分為數據模式匹配、重復記錄檢測、主數據生成3個階段。

（1）主數據管理系統與業務系統進行模式匹配，為數據抽取提供字段映射機制；

（2）檢測組件在數據加載的過程中進行重復主數據檢測；

（3）若存在重復主數據，根據主數據真值發現算法生成主數據。

主數據集成模型如圖1所示。

圖1 主數據集成模型

1.2 規 則

1.2.1 符號及含義

符號、縮寫及意義見表1。

表1 符號、縮寫及意義

1.2.2 假設

假設4：t（s）＝g（f），f∈F（s）。假設1表明客觀實體屬性真值唯一；假設2表明真值來源于數據源；假設3說明不同數據源提供的錯誤值不一樣；假設4說明數據源的準確度取決于其提供的數據值的可信度。

1.3 imp （fi－＞fj）的計算

目前的真值發現算法均是基于投票的思想，后來的算法考慮了數據源準確度、數據源可能存在拷貝關系、不同數據值的相似度的因素改進了樸素的投票算法，取得了顯著的成果。

數據值的可信度取決于提供數據值的數據源的準確度、其它數據值對其的支持度。文獻 ［5，6］把所有類型看作字符串，采取了對稱的相似度計算Simth－Waterman算法［11］，以相似度代替支持度；本文采取非對稱的算法計算字符串的支持度，并針對不同的數據類型設置了不同的閾值。

（1）數值日期型

式中：β∈｛0，1｝，對于數值做以下處理，若兩個數值相等，則支持度為1，否則為0。這種情況下數據值可信度的計算是對稱的。

對于日期型的計算首先要統一數據格式。目前日期型的數據是最容易出現不同數據格式的。

（2）字符串型：β取值為字符串相似的閾值。其它的數據類型統一處理成字符串型進行處理。通過分析目前不同數據值多是因為縮寫、少寫、或者錯寫造成的。目前算法使用的字符串相似度計算函數為傳統的非恒定相似度系數評價方法 （Jaccard系數）即

式中：q——兩個字符串共有的單詞數，r——字s2種存在，s1中不存在的單詞數，s標識字符串s1存在，s2中不存在的單詞數。但是在現實中 （中國，中華人民共和國）是相同的概念，如果將每個字符看作一個詞，計算的結果將是2／（2＋5）＝28.6%，顯然與其實際的相似度相差甚遠；又如 （廣東省經緯網絡科技有限公司，山東省經緯網絡科技有限公司）完全是不同的實體，但是通過計算相似度為12／（12＋1＋1）＝85.7%，與實際情況也相去甚遠。文獻［11］專門針對中文提出了一種新的計算公式

這個公式與英文計算方法是完全相同的，令

所以文獻 ［11］提出的中文計算方法與英文計算方法是一樣的。實踐中發現相似數據主要由簡寫、少寫、錯誤拼寫造成的，針對這3種情況，提出了一種非對稱的支持度算法

比如供貨范圍s1＝ “軟件、硬件”，s2＝ “軟件”，則imp（s2→s1）＝1，而imp （s1→s2）＝0.5，所以支持度的計算是非對稱的。該算法比較好的解決了少寫、簡寫、錯誤拼寫的問題。若采用文獻 ［9］采用的算法，imp （s2→s1）＝imp （s1→s2）＝2／（5＋2－2）＝0.4。從直觀上來看s1更加可信。

算法1：計算義原詞的相似度。

使用前首先對兩個字符串按照一定的規則進行分詞，然后排序，將每個分詞看作一個義原詞。

輸入：待比較的兩個義原詞a1，a2

輸出：相似度比較結果

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

（1）char［］f1Array＝a1.toCharArray（）；

（2）char［］f1Array＝a2.toCharArray（）；

（3）int k＝0；

（4）int m＝0；

（5）int count＝0；

（6）while（k＜f1Array.length）｛

（7）int l＝m；

（8）while（l＜f2Array.length）｛

（9）if（f1Array ［k］＝＝f2Array ［l］）｛

（10）m＋＋；

（11）count＋＋；

（12）break；

（13）｝else｛

（14）l＋＋；

（15）｝｝

（16）k＋＋；

（17）｝

return（double）count／f2Array.length；

算法分析：將a1轉化為字符數組，每個字符即為s1的義原詞，將a2轉化為字符數組，掃描一遍兩個數組，統計相同字符的個數。設：a1對應的數組長度為m，a2，對應的數組長度為n，最好情況需比較min（m，n），最壞情況需要比較 max（m，n）。

算法2：非對稱支持度算法

輸入：數據值s1，s2

輸出：s2對s1的支持度

（1）將字符串s1，s2進行分詞，構成義原詞集合w1，w2。采用算法1進行義原詞相似度計算。

（2）采用非恒定相似度系數評價方法計算式 （6）的q。

（3）采用式 （6）計算imp（s2→s1）。

1.4 算法模型

由于主數據來源的業務系統數據是獨立的業務系統，不存在業務系統之間相互拷貝的情況；在進入主數據系統這一刻的業務數據應該各業務系統的最可信數據，這一點由各提供數據的業務系統保證，所以不考慮數據的動態特性。算法模型主要關注不同數據值之間的支持度、數據源的準確度及主數據 （golden record）的生成。attr表示主數據屬性數組，t為數據源準確度矩陣，imp為屬性值相似度矩陣，j表示當前計算的為第j個屬性，α為數據源可信度變化閾值。

TRFinder模型如圖2所示。

1.5 TRFinder算法

1.5.1 算法3：支持度矩陣imp的算法

算法依據為文獻 ［5］式 （6）、式 （11）

輸入：給定屬性的數據值數組values，數據源可信度數組c，可信度調節參數r

輸出：支持度矩陣imp

（1）double ［］［］imp＝new double ［values.length］［values.length］；

（2）for （int i＝0；i＜values.length；i＋＋）

（3）｛

（4）for （int j＝0；j＜values.length；j＋＋）

（5）｛

（6）ret［i］［j］＝FieldImpValue （values ［i］，values［j］）＊c ［i］＊r；

（7）｝｝

（8）return imp；

1.5.2 算法4：數據可信值算法

輸入：數據值矩陣A，支持度矩陣B，數據源可信度矩陣t，迭代次數times

輸出：數據值可信度數組ds

參數：數據源可信度向量T，修正后的數據源可信度數組fixT，修正后的可信度值數組fixt

（1）for（int j＝0；j＜t.length；j＋＋）｛

（2）T ［j］＝－java.lang.Math.log （1－t ［j］）；｝

（3）int count＝0；

（4）while（count＜times）｛

（5）fixT＝calMatrix （B，T）；

（6）for（int k＝0；k＜fixT.length；k＋＋）｛

（7）ds ［k］＝1－java.lang.Math.exp （－fixT ［k］）；

（8）ds ［k］ ＝1／ （1＋java.lang.Math.exp （－ds［k］））；｝

（9）preT＝t；

（10）t＝calMatrix （A，ds）；

（11）for（int j＝0；j＜t.length；j＋＋）｛

（12）T ［j］＝－java.lang.Math.log （1－t ［j］）；｝

（13）count＋＋；｝

（14）return ds；

1.5.3 算法5：TRFinder算法

輸入：數據值數組FValues［］［］，數組的列數i代表屬性個數，數組的行數j代表數據源數量

輸出：可信記錄數組tRecord［］

（1）for（int k＝0；k＜j；k＋＋）

（2）利用算法3計算k屬性的可信度值數組可信度值最大的數據值添加到tRecord

（3）輸出可信記錄tRecord

2 實驗驗證

圖2 TRFinder模型

2.1 初始化參數對算法的影響

提供基建系統s1、物資系統s2、營銷系統s3這3個數據源的一條重復供貨范圍數據：

f（s1）＝ ｛計算機軟件系統開發及應用服務；計算機網絡工程、系統信息安全服務；計算機及智能綜合布線、技術咨詢；電子電器設備、計算機及其配件、消耗品、軟件產品銷售｝。

f（s2）＝ ｛計算機及智能綜合布線、技術咨詢；電子電器設備、計算機及其配件、消耗品、軟件產品銷售｝。

f（s3）＝ ｛電子電器設備、計算機及其配件、消耗品、軟件產品銷售｝。

初始化參數令t（s1）＝t（s2）＝t（s3）＝r，修正系數設置為0.3，迭代次數設置為10次。

r與ρ對數據源可信度的影響見表2。

表2 r與ρ對數據源可信度的影響

從以上結果可以看出不同的初始值對可信度記錄的生成沒有影響，體現了算法具有很強的魯棒性。

2.2 迭代收斂的情況

r＝0.9，ρ＝0.8，迭代次數為8次，其余條件采用2.1的。

迭代次數對數據源準確度的影響見表3。

表3 迭代次數對數據源準確度的影響

表3顯示算法收斂的很快，在第8次迭代，精確到10－5方的情況下s1，s2，s3的可信度變化情況為0，小于10－5，算法終止。在僅僅提供一個值的情況下，數據源的可信度及為數據值的可信度，最可信的數據應該為s1提供的數據即 “計算機軟件系統開發及應用服務；計算機網絡工程、系統信息安全服務；計算機及智能綜合布線、技術咨詢；電子電器設備、計算機及其配件、消耗品、軟件產品銷售”，從直觀上看，這個數據比另兩數據更加全面，也攜帶了更多的信息。通過這個例子也展示了文中提出的不對稱支持度計算方法的優越性。

2.3 與其他算法比較

TRFinder主要是針對主數據管理系統的需求思考產生的，TRFinder算法與TrustFinder及NEWACCU等算法的不同之處主要體現在兩點：

（1）字符串支持度計算上，實現上TRFinder采用了非對稱的支持度計算算法。

（2）針對不同的數據類型提供了不同的支持度算法。

2.3.1 不同字符串支持度算法對結果影響

主要比較TrustFinder、ACCU、NEWACCU算法所使用的編輯距離的對稱算法與本文使用的基于統計與位置的改進PCM算法。

對于書籍 《web數據挖掘》，通過百度搜索，從不同的網站獲取作者信息如下，數據源初始準確度均為0.8，可信度調節參數設為0.9。web世界的數據見表4。

表4 web世界的數據

不同算法準確度對比見表5。

開始運行時，每個數據源只提供一個數據，所以數據值的可信度與數據源的可信度是一致的。程序運行結果顯示TrustFinder選擇 ｛劉兵 （Liu.B）｝作為可信數據，而TRFinder算法選擇了 ｛（美國）劉兵 （Liu.B）譯者：俞勇｝作為可信數據，而通過查看原書的封面發現 ｛Bing Liu著 ；俞勇，薛貴榮，韓定一譯｝才是真值，盡管如此，直觀的來看TRFinder選擇的真值依然比TrustFinder算法信息更加全面，更加可信。為驗證縮寫、少寫，及位置調換對算法的影響，用以下模擬數據進行實驗。模擬數據見表6。

表5 不同算法準確度對比

表6 模擬數據

運算結果顯示：TrustFinder算法選擇了 ｛Bing Liu著；俞勇，韓定一譯｝做為可信數據，而TRFinder算法選擇了｛Bing Liu著；俞勇，薛貴榮，韓定一譯｝做為真值，實驗驗證了TRFinder算法比TrustFinder等算法使用的對稱算法更容易發現真值。也保留了更多地真值信息。

2.3.2 算法準確率比較

為了使實驗結果具有可比性，算法準確性驗證采取與原實驗相同的books＿authors數據集 （特別感謝哈工大張志強教授提供的驗證數據集）。設置數據源初始可信度為0.8，相似度支持因子為0.7。

books＿authors數據集上的部分實驗結果見表7。

表7 books＿authors數據集上的部分實驗結果

通過查看書籍的封面，確定真值為：｛｛o＇leary，timothy j.； o＇leary，linda i.｝；｛yacht，carol； crosson，susan｝；｛haag，stephen； perry，james t.； sosinsky，barrie；estevez，efren｝；｛scambray，joel； mcclure，stuart｝；｛courage，catherine； baxter，Kathy｝； ｛goldman，ron；gabriel，richard p.｝； ｛makofske，david； almeroth，kevin｝； ｛dann，wanda p.； cooper，stephen； pausch，randy｝；｛geary，david； horstmann，cay｝；｛shaffer，clifford a.｝；｝

不同算法books＿authors數據集上準確率對比見表8。

表8 不同算法books＿authors數據集上準確率對比

對比以上數據可以發現，TRFinder算法的準確率比TruthFinder算法提高了10個百分點，比Vote算法提高了39個百分點。通過針對部分數據進行實際分析發現，不對稱支持度算法使具有更多信息量的值留了下來。多數的網站只列出了部分作者，沒有完全的作者信息，所以使用Vote算法選出的很多不是真值；而TruthFinder使用了基于編輯距離的字符串相似度算法替代支持度算法，計算的結果經常遺漏作者；而TRFinder算法考慮了支持度計算的非對稱特性，計算的結果雖然也有與書籍封面不一致的數據，從選出的部分數據來看，沒有遺漏任何作者信息，特別是針對經常出現的簡寫、少寫及位置調換等常見現象真值發現的準確度更高。

3 結束語

針對主數據管理中出現的多業務系統數據沖突的問題，總結了目前典型的解決數據沖突的方法，結合主數據管理的業務需求及應用場景，提出了一種新的計算不同數據值支持度的非對稱算法，較好的解決了目前主數據集成中常出現的簡寫、少寫、位置調換、錯誤書寫等問題，并提出了用于解決主數據生成的TRFinder算法。從實驗效果上看，TRFinder比Vote算法及TrustFinder算法具有更高的準確率，較全面地保留了真值的信息。目前的實現算法中沒有考慮數據的動態特性，擬進一步就數據的動態特性進行研究。

［1］Bleiholder J，Naumann F.Conflict handing strategies in an integrated information system ［C］／／Edinburgh，UK：Proceedings of the International Workshop on Information Integration on the Web，2006：36－41.

［2］Naumann F，Bilke A，Bleiholder J，et al.Data fusion in threesteps：Resolving schema，tuple，and value inconsistencies［J］.IEEE Data Engineering Bulletin，2006，29 （2）：21－31.

［3］Whang Steven Euijong，Menestrina David，Koutrika Georgiaet al.Entity resolution with iterative blocking ［C］／／Rhod.Rhode Island，USA：Proceedings of the 35th SIGMOD Internatational Conference on Management of Data，2009：219－231.

［4］Panse F，keulen M V，Keijzer A D，et al.Duplicate detection in probabilistic data ［C］／／LongBeach，CA：Proceedings of 26th International Confernece on Data Engineering Workshop，2010：179－182.

［5］Yin X，Han J，Yu P S.Truth discovery with multiple conicting information providers on the Web ［J］.IEEE Transactions on Knowledge and Engineering，2008，20 （6）：796－808.

［6］Dong X L，Berti Equille L，Srivastava D.Integrating conflicting data：The role of source dependence［J］.PVLDB，2009，2 （1）：550－561.

［7］Dong X L，Naumann F.Data fusion resolving data conflicts for integration ［J］.PVLDB，2009，2 （2）：1654－1655.

［8］Dong X L，Berti Equille L，Srivastava D.Truth discovery and copying detection in a dynamic world ［J］.PVLDB，2009，2（1）：562－573.

［9］KAO Mingjun，ZHANG Wei，GAO Hong.Truth discovery methods in conflict data integration ［J］，Journal of Computer Research and Development，2010，47 （Suppl.）：188－192 （in Chinese）.［考明軍，張煒，高宏.沖突數據中的真值發現算法 ［J］.計算機研究與發展，2010，47 （增刊）：188－192.］

［10］ZHANG Zhiqiang，LIU Lixia，XIE Xiaoqin，et al.Information evaluation based on source dependence ［J］.Chinese Journal of Computers，2012，35 （11）：2392－2402 （in Chinese）.［張志強，劉麗霞，謝曉琴，等.基于數據源依賴關系的數據源信息評價方法研究 ［J］.計算機學報，2012，35 （11）：2392－2402.］

［11］Nawaz Z，Al－Ars Z，Bertels K，et al.Accelerationa of simth－waterman using recursive variable expansion ［C］／／Parma，Italy：Proceedings of the 11th EUROMICRO Conference on Digital System Design Architectures，Methods and Tools，2008：915－922.