基于隱馬爾可夫模型的多真值發現算法*

王會舉，李孟萱，黃衛衛，周秋怡

(中南財經政法大學信息與安全工程學院,湖北 武漢 430073)

1 引言

信息時代，多個數據源對同一對象的描述可能并不相同甚至相互之間存在矛盾和沖突，數據之間的不一致性無可避免。根據“垃圾進，垃圾出(Garbage in,Garbage out)”原則，錯誤數據極有可能導致錯誤的結論與決策。“數據豐富，信息貧乏”的困境反映出當前數據與信息量嚴重不對等、數據質量低劣、利用率不高等問題[1]。因此，從可能存在矛盾的觀測值中找到目標對象的真值，可以有效提高數據質量，保證數據使用人員分析和決策的準確性。然而，現實事物通常擁有多值屬性，如一部電影由多人主演甚至導演、一本圖書可能由多位專家共同創作。這類對象存在多值屬性的問題被稱為多真值發現問題。

本文基于圖模型構造了一個新的多真值發現算法，可有效提高真值發現算法的正確率。主要貢獻有以下3點：

(1)在傳統投票方法的基礎上，設計出改進的初始真值的確定CVote(Cluster Vote)算法，該算法能夠更好地應用于多真值發現研究。

(2)設計了真值發現中一種類似于隱馬爾可夫模型的轉移矩陣的“可靠性轉移矩陣”，并據此提出了基于圖模型的真值發現算法GraphTD(Graph Truth Discovery)。

(3)提出了針對多真值發現研究的效果評價指標體系，能夠從多個方面對真值發現的結果進行評價，并通過大量實驗驗證了GraphTD算法和CVote算法的有效性。

2 相關研究

為解決多源數據的沖突問題，研究者們進行了眾多研究，目前的真值發現方法可概括為3類，分別是迭代方式、概率模型方式和圖模型方式。

(1)迭代方式，即同時計算描述和數據源可靠的程度。Yin等[2]最早于2008年提出了真值發現的定義，并提出經典的TRUTHFINDER算法迭代計算對象的真值和數據源的可靠性。在此基礎上，國內外相關學者從不同角度對算法進行了改進。王繼奎等[3]提出了一種非對稱的數據值相似度計算方法，并基于明確度和敏感度，從被動錯誤和主動錯誤兩方面入手，提出了一種沖突數據源質量評價算法[4]。考明軍等[5]將數據源的權威性納入考慮范圍，對數據源在投票時的比重進行了調整，是對傳統的投票法的創新性改進。文獻[6,7]則基于EM(Expectation Maximization)算法構建出真值計算的最大似然函數，并迭代計算出對象的真實觀測值，為真值發現問題提供了一種新的研究思路。文獻[8-10]針對同一數據在不同數據源之間的復制特性，在數據源不獨立的基礎上，設計了基于數據間復制檢測的真值發現算法。

(2)概率模型方式。文獻[11,12]基于概率圖模型將真值發現用于藥物副作用發掘中；董微等[13]構造了基于貝葉斯公式的概率模型，并將真值發現應用到學術資源集成中；Wan等[14]提出了KDEm(Kernel Density Estimation from Multiple Sources)算法，該算法是一種全新的基于概率的研究方法，從變量的角度出發利用核密度估計計算得到對象的真值。Xin等[15]通過在新的多層概率模型中使用聯合推理來區分提取過程中的錯誤與Web源本身中的錯誤，以此來計算數據源的真實可信度水平。

(3)圖模型的方式。王繼奎等[16]將HITS(Hypertext-Induced Topic Search)中視圖的思想引入真值發現研究中，基于圖模型實現了對象觀測值集的建模，繼而設計了迭代式多真值計算算法。Yin等[17]提出了一種半監督的真值計算算法，該算法基于圖模型對描述之間的關系進行定義，并提出了基于圖模型的損失函數，明顯提高了真值發現的準確率。文獻[18,19]針對數據源的可靠性計算，考慮數據源的主動錯誤與被動錯誤，分別研究了基于圖和基于貝葉斯的迭代計算方法，有效提高了真值發現的準確率。Fang等[18，20,21]從數據源的角度出發，利用圖模型模擬了數據源之間的關系，并將數據的長尾現象等多種因素納入考慮范圍，是真值發現領域中一種全新的解決方案。

現有研究雖從各方面對真值發現進行了探索，但依然存在初始真值的選擇過于簡單、算法的復雜度較高、未考慮結果集排序、評價指標較為單一等問題。本文構造了一種圖模型上運算的真值發現算法，通過將真值發現問題轉換為圖模型并利用轉移矩陣進行求解，大大簡化了真值發現的計算過程。

3 GraphTD多真值發現算法

3.1 真值發現的定義

從存在矛盾或沖突的多個數據源中找到同一個對象最準確的觀測值即為真值發現問題。

為給出真值發現的數學定義，首先定義相關的概念和數學符號。本文可靠性、可信度、置信度表示同一含義，后文將不做具體區分。

o：表示待研究對象的屬性，比如作者是圖書的屬性之一。在本文的研究中，考慮的是對象的單一屬性，即在研究圖書時僅研究其作者屬性，不討論圖書出版社、頁數和國籍等屬性，因此，本文在后面的表述中，對象與對象的屬性將不再區分，表示的是相同的概念。O={o1,o2,…,oN}表示所有對象的集合。

s：表示數據源，數據源提供了各研究對象的觀測值。S={s1,s2,…,sK}是數據源的集合。

t：代表經算法計算得到的真值，也就是在對同一個對象的多個描述中，經計算后被認為是真值的f*(但該值不一定是對象的真值，只是在多個觀測之中選擇的最優解)。to表示對象o的真值。

p(f)：表示描述置信度的高低，也就是對象的觀測值是真值的概率，p(f)越大，該描述為真值的概率越高。p(f)的取值在[0,1]。

p(s)：代表了數據源可信度的高低，p(s)越大，表示數據源越值得信任，那么該數據源就越有可能提供對象的真值。p(s)的取值在[0,1]。

sim(fi,fj)：代表了2個觀測值fi和fj相互支持度，即當fi(fj)的觀測值為真時，fj(fi)觀測值也為真的概率。本文用相似度來計算支持度。

為從多個矛盾描述中找到對象的真值，本文做出如下假設：

假設1數據源越可靠，其提供的描述越可信，并更有可能成為真值。

假設2數據源提供的真值越多，該數據源越可靠。

假設3每個對象的真值為一個非空集合。

3.2 真值初始化算法CVote

投票(Vote)法是現有研究中最常使用的初始值選擇方法，直接選擇出現次數最多的描述作為對象的真值。然而，Vote法認為所有的數據源的可靠性是一致的，在數據集成的多源數據沖突問題中，簡單的Vote法很可能將錯誤的數據當作真值。此外，Vote法只能處理單真值問題，而無法處理多真值問題，具有很大局限性。因此本文提出一種改進的多真值發現CVote算法。

CVote算法采取細粒度投票機制，其核心思想為：將一個對象的K個描述的集合當做一個聚類；一個描述同其他描述的類內漢明距離和越小，越說明其他描述與該描述較相似，則該描述越有可能代表整體描述所表達的核心思想，因而越可能成為對象的初始真值。其計算方法為：對于每一個描述fi，選其為聚類中心點(初始真值)，計算其他描述與它的漢明距離之和SEi(i=1,2,…,K)。CVote算法如算法1所示。

算法1CVote

輸入：包含對象及多個數據源對對象的描述的數據集。

輸出：每個對象的真值。

步驟1取出數據庫中的N個對象及K個數據源對對象的描述。

步驟2對于N個對象：

將K個數據源的描述向量化；

步驟3對于K個數據源：

計算該數據源的描述與其他數據源的描述的漢明距離之和sumHamming[k]。

步驟4漢明距離之和最小時對應的數據源的描述就是對象的真值。

這里定義的多真值發現算法有2個基本點：(1)在計算真值時，該算法單獨考慮了描述中出現的每個值，而不是簡單地將描述作為一個整體。(2)將漢明距離之和最小時作為聚類中心點的觀測值當作對象的真值，漢明距離之和是選取對象真值的重要依據。

3.3 GraphTD真值發現圖模型構建

在GraphTD真值發現算法中，將對象的觀測值作為圖模型中的節點，并根據數據源和觀測值之間的關系，計算得到狀態轉移矩陣，用初始狀態和狀態轉移矩陣迭代計算得到描述為真的概率的收斂值。一個對象的真值是具有最高概率值的描述。

本文借鑒Yin 等[17]的做法，將描述作為節點，并通過在同一個對象的描述節點間和來自同一個數據源的節點間建立聯系邊，形成隱馬爾可夫模型中的一個時刻狀態。如圖1所示，f1和f3描述同一個對象o1，f2和f4描述同一個對象o2，f1、f2和f3、f4分別來自數據源s1和s2，依據前面所定義的規則，將描述了同一個對象的f1與f3、f2與f4分別連接起來，來自于同一個數據源的f1與f2、f3與f4分別連接起來。

Figure 1 Graphic model of object description

為方便真值發現算法的討論，下面給出GraphTD圖模型的正式定義。

定義2(GraphTD圖模型定義) GraphTD圖模型可表示為三元組G=(V,E,w)，其中V為觀測值集合，代表G的節點集；E=V×V代表觀測值節點間的依賴關系，構成了G的邊集；w為邊上的權重，構成了可靠性轉移矩陣。

定義3(可靠性轉移矩陣) 即隱馬爾可夫模型中的狀態轉移矩陣。可靠性轉移矩陣是計算對象真值的主要依據，可基于觀測值以及數據源之間的關系計算得出。

可靠性轉移矩陣的計算是構建圖模型后的關鍵步驟，本文依據邊之間的依賴關系即GraphTD圖模型中邊的權重，來確定可靠性轉移矩陣的元素值，根據觀測值之間的邊的類型(如描述同一個對象的邊類型，或來自同一個數據源的邊類型)計算得到。

權重的計算方法如下所示：

(1)對于來自于同一個數據源的觀測值(節點)fi→fj，它們之間的邊的權重為數據源的可信度乘以源節點的初始可信度，即p(si)·p(fi)；

(2)描述同一個對象的節點fi→fj，它們之間的邊的權重用源節點的可信度乘以節點間的支持度表示，即p(fi)·sim(fi,fj)，衡量節點間相似性的指標是漢明距離；

(3)若節點之間無連接，則轉移權重為0；

(4)在可靠性轉移矩陣中，用觀測值的初始可信度p(fi)表示。觀測值本身的轉移概率——也就是轉移矩陣的對角線上的值fi→fi。

根據前面所提到的邊的權重計算方法可以得到轉移矩陣A，將轉移矩陣按行歸一化后即可得到可靠性轉移矩陣A*。最后根據觀測值的初始置信度與可靠性轉移矩陣迭代計算，即可得到觀測值為真的概率收斂值。

3.4 GraphTD真值發現算法

本文采用布爾表示的方法將對象的描述向量化，采用漢明距離來計算描述的初始置信度與描述之間的相互支持度。同時分別對描述的可信度、數據源的可靠性和描述間的相似性進行定義。

(1)數據源的可靠性。

本文用數據源提供的所有觀測值的準確度的平均值表示數據源的可靠性。若用p(s)表示數據源的可靠性，F={f1,f2,…,fK}表示數據源的所有觀測值的集合，p(f)表示描述f為真值的概率，則數據源s的可靠性p(s)可由式(1)得出：

(1)

(2)描述的可信度。

初始狀態描述的可信度用描述與真值的相似度衡量。利用CVote算法得到對象的初始真值，并根據各觀測值與初始真值的相似度計算出各觀測值的可信度。描述同一個對象的數據用向量X表示，令真值的置信度為1，p(f)表示觀測值f的可靠性,則描述f的可靠性可用式(2)表示：

(2)

(3)描述間相似性。

同一個對象的不同觀測值的可靠性具有一定的關聯，本文采用漢明距離衡量描述之間的相似性，并據此表示描述之間的支持度。設fi和fj表示對同一個對象的描述，則fi與fj之間的相似性可用式(3)所示：

(3)

其中，m是fi與fj之間的漢明距離。

基于以上公式，得到初始狀態下觀測值的可靠性、數據源的置信度和觀測值之間的相似性后，可以根據GraphTD圖節點及邊關系計算出狀態轉移矩陣，然后迭代計算得到每個觀測值可信度的收斂值，最后依據收斂值大小選出對象真值。

3.5 GraphTD算法總體描述

GraphTD真值發現算法總體框架如圖2所示，算法核心思想是：基于可靠性轉移矩陣迭代計算得到每個觀測值置信度的收斂值，將對應收斂值最大的觀測值當做對象的描述真值。由于不同初始真值會導致產生不同的可靠性轉移矩陣，該算法的結果容易受到初始真值的影響。GraphTD算法的描述如算法2所述。

Figure 2 Overall framework of GraphTD

算法2GraphTD

輸入：包含對象及多個數據源對對象描述的數據集。

輸出：每個對象的真值。

步驟1確定對象的初始真值，并令初始真值的可信度為1。

步驟2計算對象的其他描述與初始真值的漢明距離，并計算其他描述的初始可信度。

步驟3根據描述的初始可信度計算數據源的可靠性。

步驟4根據數據源的可靠性、描述的可信度和描述之間的依賴關系來計算可靠性轉移矩陣。

步驟5用初始狀態描述的可信度乘以可靠性轉移矩陣，如果算法收斂，則結束，否則重復步驟4。

步驟6根據描述可信度的收斂值選擇對象的真值。

3.6 算法評價指標

現有研究一般僅用正確率來評價算法的好壞，維度較為單一。本文定義以下4個指標來更全面地衡量算法的性能。

定義4(錯誤率Acc0)Acc0衡量算法在真值發現時的錯誤率。

(4)

其中，ntotal_error為算法識別真值與對象真值完全不同的對象數。

定義5(正確率Acc1)Acc1衡量算法在真值發現時的正確率。

(5)

其中，ntotal_correct為算法識別真值與對象真值完全相同的對象數。

定義6(部分正確率Acc2)Acc2衡量算法在真值發現時的部分正確率。

(6)

其中，npartial_correct為算法識別出的真值僅是對象真值一部分的對象數。

定義7(部分錯誤率Acc3)Acc3衡量算法存在部分正確部分錯誤情況下的部分錯誤率。該指標與Acc2識別出的真值不完整但正確的情況不同，它的真值是部分正確的，而錯誤部分的真值中則包含錯誤數據，是不可靠的。

(7)

其中，npartial_error為算法識別真值部分錯誤的對象數。

4 實驗構建及分析

4.1 數據集獲取

本文通過網絡爬蟲技術，采集了中國圖書網、豆瓣讀書、淘書網、孔夫子舊書網和有路網等5個書籍電商網站的計算機相關書籍信息，對數據進行冗余剔除、規范化和數據合并等預處理操作后得到來自5個數據源的共89 897條不同書籍數據。

4.2 實驗結果及分析

為了驗證本文提出的CVote和GraphTD的有效性，本文在同一書籍作者數據集上分別實現了以下7種相關真值發現算法來與本文算法進行對比：

(1)Vote：基本的Native Vote投票算法。

(2)CVote：本文提出的真值初始化算法CVote。

(3)TFNoSup：不考慮描述之間相關關系的TRUTHFINDER算法。

(4)TF：Yin等[17]提出的經典TRUTHFINDER算法。

(5)AccuVote[22]：當前準確率最高的圖真值發現算法。

(6)GTDVote(GraphTD with Vote Initialization Algorithm)：以Vote作為初始化算法的類GraphTD算法。

(7)GraphTD：以CVote作為初始化算法的GraphTD多真值發現算法。

實驗中選取200條圖書記錄，并按照慣例，將圖書封面上的作者選為真值，通過人工收集的方式得到真值的標準集。表1是3本不同圖書的作者和各個算法在收集的數據集上計算得到的作者真值情況，根據這些數據，可以計算出各個算法的準確率——包括正確率、部分正確率、錯誤率、部分錯誤率。

根據3.6節定義的真值發現算法效果衡量指標，以人工收集的真值作為基準，對比分析算法識別的正確率。表2統計了各個算法的正確率、錯誤率、部分正確率和部分錯誤率。表2和圖3顯示了不同真值發現算法的對比結果。其中，Vote/CVote對比實驗結果顯示，CVote算法比Vote算法的正確率Acc1低，也就是在尋找與真值完全一致的觀測值上CVote算法比Vote算法表現稍差。但是,在部分正確率Acc2上，CVote算法優于Vote算法，通過對原始數據的觀察和比較可以發現，在得票相同的情況下，Vote算法會默認選擇第1個觀測值作為真值，該值由程序設置決定，較為隨機，因此當數據源不多時，Vote算法的結果具有偶然性。而CVote算法考慮了描述之間的相關關系，因而更傾向于選擇確定的真值，其抗干擾性更強。

Table 1 Objects truth values and truth values recognized by algorithms

Table 2 Statistics of recognition results of each algorithm

Figure 3 Results comparison of truth discovery algorithms

圖4將Acc2與Acc1的和當做算法的整體正確率。從圖4不難看出，CVote算法的表現要優于Vote算法，驗證了CVote算法的可行性。

Figure 4 Comparison of the overall correct rate and overall error rate of truth discovery algorithms

類似地，從TFNoSup/TF對比實驗中可知，TF算法的整體正確率和部分正確率均高于TFNoSup的，進一步證實了描述之間的相關關系對真值發現算法的準確率具有重要影響，這一點也體現在GTDVote/GraphTD的對比中。由圖3和圖4可以明顯看出，雖然GraphTD在整體正確率上基本等于GTDVote的，但其部分正確率遠高于GTDVote的，此結果與Vote與CVote的比較結果相同，說明對象最終真值的計算會受到初始真值的影響。考慮了描述間關系的算法往往具有更高的穩健性和抗干擾性，更能夠避免數據源帶來的偶然性問題。

此外，圖3中顯示，相比于傳統的Vote/CVote和TFNoSup/TF算法，GTDVote/GraphTD算法的整體正確率有明顯提升，僅比當前最準確的圖真值發現算法AccuVote的略低，但GTDVote/GraphTD的部分錯誤率Acc3相比于AccuVote的有一定下降，特別是GraphTD的部分錯誤率明顯低于AccuVote的。如果以Acc1與Acc2的和作為算法的整體正確率，Acc0與Acc3的和作為算法的整體錯誤率(如圖4所示)，則GraphTD的整體正確率高于AccuVote算法的，說明GraphTD算法具有一定的性能優勢。

5 結束語

本文基于隱馬爾可夫模型，設計了一個GraphTD多真值發現算法，并在真實數據集上對算法進行了驗證分析。實驗結果表明，GraphTD多真值發現算法可有效提高真值識別的準確率，具有較強的可推廣性。