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

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

1 引言

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

sim(fi,fj)：代表了2個(gè)觀測(cè)值fi和fj相互支持度，即當(dāng)fi(fj)的觀測(cè)值為真時(shí)，fj(fi)觀測(cè)值也為真的概率。本文用相似度來(lái)計(jì)算支持度。

為從多個(gè)矛盾描述中找到對(duì)象的真值，本文做出如下假設(shè)：

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

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

假設(shè)3每個(gè)對(duì)象的真值為一個(gè)非空集合。

3.2 真值初始化算法CVote

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

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

算法1CVote

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

輸出：每個(gè)對(duì)象的真值。

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

步驟2對(duì)于N個(gè)對(duì)象：

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

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

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

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

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

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

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

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

Figure 1 Graphic model of object description

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)描述的可信度。

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

(2)

(3)描述間相似性。

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

(3)

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

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

3.5 GraphTD算法總體描述

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

Figure 2 Overall framework of GraphTD

算法2GraphTD

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

輸出：每個(gè)對(duì)象的真值。

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

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

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

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

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

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

3.6 算法評(píng)價(jià)指標(biāo)

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

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

(4)

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

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

(5)

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

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

(6)

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

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

(7)

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

4 實(shí)驗(yàn)構(gòu)建及分析

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

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

4.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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的和當(dāng)做算法的整體正確率。從圖4不難看出，CVote算法的表現(xiàn)要優(yōu)于Vote算法，驗(yàn)證了CVote算法的可行性。

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

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

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

5 結(jié)束語(yǔ)

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