王繼奎，李少波

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

0 引 言

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

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

1 TRFinder算法

1.1 主數(shù)據(jù)集成模型

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

（1）主數(shù)據(jù)管理系統(tǒng)與業(yè)務系統(tǒng)進行模式匹配，為數(shù)據(jù)抽取提供字段映射機制；

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

（3）若存在重復主數(shù)據(jù)，根據(jù)主數(shù)據(jù)真值發(fā)現(xiàn)算法生成主數(shù)據(jù)。

主數(shù)據(jù)集成模型如圖1所示。

圖1 主數(shù)據(jù)集成模型

1.2 規(guī) 則

1.2.1 符號及含義

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

表1 符號、縮寫及意義

1.2.2 假設

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

1.3 imp （fi－＞fj）的計算

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

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

（1）數(shù)值日期型

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

對于日期型的計算首先要統(tǒng)一數(shù)據(jù)格式。目前日期型的數(shù)據(jù)是最容易出現(xiàn)不同數(shù)據(jù)格式的。

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

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

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

所以文獻 ［11］提出的中文計算方法與英文計算方法是一樣的。實踐中發(fā)現(xiàn)相似數(shù)據(jù)主要由簡寫、少寫、錯誤拼寫造成的，針對這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：計算義原詞的相似度。

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

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

輸出：相似度比較結果

f1Array，f2Array為a1，a2的字符串數(shù)組；k與m為指向f1Array，f2Array的指針，初始值為0，count統(tǒng)計字符相同的結果，初始值位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轉化為字符數(shù)組，每個字符即為s1的義原詞，將a2轉化為字符數(shù)組，掃描一遍兩個數(shù)組，統(tǒng)計相同字符的個數(shù)。設：a1對應的數(shù)組長度為m，a2，對應的數(shù)組長度為n，最好情況需比較min（m，n），最壞情況需要比較 max（m，n）。

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

輸入：數(shù)據(jù)值s1，s2

輸出：s2對s1的支持度

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

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

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

1.4 算法模型

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

TRFinder模型如圖2所示。

1.5 TRFinder算法

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

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

輸入：給定屬性的數(shù)據(jù)值數(shù)組values，數(shù)據(jù)源可信度數(shù)組c，可信度調節(jié)參數(shù)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：數(shù)據(jù)可信值算法

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

輸出：數(shù)據(jù)值可信度數(shù)組ds

參數(shù)：數(shù)據(jù)源可信度向量T，修正后的數(shù)據(jù)源可信度數(shù)組fixT，修正后的可信度值數(shù)組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算法

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

輸出：可信記錄數(shù)組tRecord［］

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

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

（3）輸出可信記錄tRecord

2 實驗驗證

圖2 TRFinder模型

2.1 初始化參數(shù)對算法的影響

提供基建系統(tǒng)s1、物資系統(tǒng)s2、營銷系統(tǒng)s3這3個數(shù)據(jù)源的一條重復供貨范圍數(shù)據(jù)：

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

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

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

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

r與ρ對數(shù)據(jù)源可信度的影響見表2。

表2 r與ρ對數(shù)據(jù)源可信度的影響

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

2.2 迭代收斂的情況

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

迭代次數(shù)對數(shù)據(jù)源準確度的影響見表3。

表3 迭代次數(shù)對數(shù)據(jù)源準確度的影響

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

2.3 與其他算法比較

TRFinder主要是針對主數(shù)據(jù)管理系統(tǒng)的需求思考產生的，TRFinder算法與TrustFinder及NEWACCU等算法的不同之處主要體現(xiàn)在兩點：

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

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

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

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

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

表4 web世界的數(shù)據(jù)

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

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

表5 不同算法準確度對比

表6 模擬數(shù)據(jù)

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

2.3.2 算法準確率比較

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

books＿authors數(shù)據(jù)集上的部分實驗結果見表7。

表7 books＿authors數(shù)據(jù)集上的部分實驗結果

通過查看書籍的封面，確定真值為：｛｛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數(shù)據(jù)集上準確率對比見表8。

表8 不同算法books＿authors數(shù)據(jù)集上準確率對比

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

3 結束語

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

［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）.［考明軍，張煒，高宏.沖突數(shù)據(jù)中的真值發(fā)現(xiàn)算法 ［J］.計算機研究與發(fā)展，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）.［張志強，劉麗霞，謝曉琴，等.基于數(shù)據(jù)源依賴關系的數(shù)據(jù)源信息評價方法研究 ［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.