基于隱馬爾可夫模型的多真值發(fā)現(xiàn)算法*

王會舉，李孟萱，黃衛(wèi)衛(wèi)，周秋怡

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

1 引言

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

3 GraphTD多真值發(fā)現(xiàn)算法

3.1 真值發(fā)現(xiàn)的定義

從存在矛盾或沖突的多個數(shù)據(jù)源中找到同一個對象最準確的觀測值即為真值發(fā)現(xiàn)問題。

為給出真值發(fā)現(xiàn)的數(shù)學定義，首先定義相關(guān)的概念和數(shù)學符號。本文可靠性、可信度、置信度表示同一含義，后文將不做具體區(qū)分。

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

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

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

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

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

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

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

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

假設2數(shù)據(jù)源提供的真值越多，該數(shù)據(jù)源越可靠。

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

3.2 真值初始化算法CVote

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

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

算法1CVote

輸入：包含對象及多個數(shù)據(jù)源對對象的描述的數(shù)據(jù)集。

輸出：每個對象的真值。

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

步驟2對于N個對象：

將K個數(shù)據(jù)源的描述向量化；

步驟3對于K個數(shù)據(jù)源：

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

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

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

3.3 GraphTD真值發(fā)現(xiàn)圖模型構(gòu)建

在GraphTD真值發(fā)現(xiàn)算法中，將對象的觀測值作為圖模型中的節(jié)點，并根據(jù)數(shù)據(jù)源和觀測值之間的關(guān)系，計算得到狀態(tài)轉(zhuǎn)移矩陣，用初始狀態(tài)和狀態(tài)轉(zhuǎn)移矩陣迭代計算得到描述為真的概率的收斂值。一個對象的真值是具有最高概率值的描述。

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

Figure 1 Graphic model of object description

為方便真值發(fā)現(xiàn)算法的討論，下面給出GraphTD圖模型的正式定義。

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

定義3(可靠性轉(zhuǎn)移矩陣) 即隱馬爾可夫模型中的狀態(tài)轉(zhuǎn)移矩陣?？煽啃赞D(zhuǎn)移矩陣是計算對象真值的主要依據(jù)，可基于觀測值以及數(shù)據(jù)源之間的關(guān)系計算得出。

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

權(quán)重的計算方法如下所示：

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

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

(3)若節(jié)點之間無連接，則轉(zhuǎn)移權(quán)重為0；

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

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

3.4 GraphTD真值發(fā)現(xiàn)算法

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

(1)數(shù)據(jù)源的可靠性。

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

(1)

(2)描述的可信度。

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

(2)

(3)描述間相似性。

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

(3)

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

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

3.5 GraphTD算法總體描述

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

Figure 2 Overall framework of GraphTD

算法2GraphTD

輸入：包含對象及多個數(shù)據(jù)源對對象描述的數(shù)據(jù)集。

輸出：每個對象的真值。

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

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

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

步驟4根據(jù)數(shù)據(jù)源的可靠性、描述的可信度和描述之間的依賴關(guān)系來計算可靠性轉(zhuǎn)移矩陣。

步驟5用初始狀態(tài)描述的可信度乘以可靠性轉(zhuǎn)移矩陣，如果算法收斂，則結(jié)束，否則重復步驟4。

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

3.6 算法評價指標

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

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

(4)

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

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

(5)

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

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

(6)

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

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

(7)

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

4 實驗構(gòu)建及分析

4.1 數(shù)據(jù)集獲取

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

4.2 實驗結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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算法的表現(xiàn)要優(yōu)于Vote算法，驗證了CVote算法的可行性。

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

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

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

5 結(jié)束語

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