馬如霞 孟小峰 王 璐 史英杰

1(中國人民大學(xué)信息學(xué)院 北京 100872)2(首都師范大學(xué)教育技術(shù)系 北京 100048)3(北京服裝學(xué)院信息工程學(xué)院 北京 100029)(maruxia@126.com)

?

MTruths：Web信息多真值發(fā)現(xiàn)方法

馬如霞1,2孟小峰1王 璐1史英杰3

1(中國人民大學(xué)信息學(xué)院 北京 100872)2(首都師范大學(xué)教育技術(shù)系 北京 100048)3(北京服裝學(xué)院信息工程學(xué)院 北京 100029)(maruxia@126.com)

Web已成為一個浩瀚的信息海洋，其信息分散在不同的數(shù)據(jù)源中.不同數(shù)據(jù)源常常為同一對象實(shí)體提供沖突的屬性值.如何從這些沖突屬性值中找到真值被稱為真值發(fā)現(xiàn)問題.根據(jù)屬性值數(shù)量可將對象屬性分為單值屬性和多值屬性，現(xiàn)有的多數(shù)真值發(fā)現(xiàn)算法對單值屬性的真值發(fā)現(xiàn)比較有效.針對多值屬性的真值發(fā)現(xiàn)問題，提出了一個多真值發(fā)現(xiàn)方法MTruths，該方法將多真值發(fā)現(xiàn)問題轉(zhuǎn)化為一個最優(yōu)化問題，其目標(biāo)是：各對象的真值與各數(shù)據(jù)源提供的觀察值之間的相似性加權(quán)和達(dá)到最大.對象真值求解過程中，提出2種方法求真值列表的最優(yōu)解：基于枚舉的方法和貪心算法.與已有方法不同的是MTruths可以直接得到對象的多個真值.最后，通過圖書和電影2個真實(shí)數(shù)據(jù)集上的實(shí)驗表明，MTruths的2種實(shí)現(xiàn)方法的準(zhǔn)確性以及貪心算法的效率優(yōu)于現(xiàn)有真值發(fā)現(xiàn)方法.

真值發(fā)現(xiàn)；數(shù)據(jù)沖突；單值屬性；多值屬性；數(shù)據(jù)源質(zhì)量

互聯(lián)網(wǎng)信息量正以驚人的速度急劇增長，儼然成為一個巨大的信息庫.Web已經(jīng)滲透到人們?nèi)粘Ｉa(chǎn)、生活的方方面面，逐漸成為人們獲取信息的重要來源.人們在享受來自Web豐富信息的同時，也受到信息質(zhì)量問題的困擾，大量錯誤、過時、不完整、虛假信息充斥于網(wǎng)絡(luò).其中，信息沖突問題尤為突出，不同數(shù)據(jù)源為相同對象同一屬性提供沖突的值.例如，不同圖書網(wǎng)站為同一本書提供了不同的作者信息，如表1所示；各航空網(wǎng)站為同一航班提供不同的登機(jī)時間、在線零售商為同一商品提供了不一致的產(chǎn)品規(guī)格說明等.這些沖突信息可能由于輸入錯誤、信息過期、語義理解不一致、抽取程序錯誤等各種原因造成，給用戶帶來誤導(dǎo)甚至造成巨大損失.如何從不同數(shù)據(jù)源提供的沖突信息中找到正確信息是提高Web信息質(zhì)量亟待解決的問題，該問題也被稱為真值發(fā)現(xiàn)問題[1].

真值發(fā)現(xiàn)問題已有一系列研究工作.其最簡單直觀的方法是采用投票的方法，當(dāng)獲得的票數(shù)占總票數(shù)比例達(dá)到某個閾值時認(rèn)為該屬性值為真.由于數(shù)據(jù)源質(zhì)量存在差異，因此在投票時需要考慮數(shù)據(jù)源的質(zhì)量因素，可將數(shù)據(jù)源質(zhì)量作為先驗知識，采用加權(quán)投票的方法得到真值.但當(dāng)大多數(shù)數(shù)據(jù)源都發(fā)生錯誤時，投票方法很難得到正確的結(jié)果.并且在實(shí)際中，往往沒有數(shù)據(jù)源質(zhì)量的先驗知識，為此文獻(xiàn)[1-5]采用無監(jiān)督的方法迭代地計算各屬性值可信性以及數(shù)據(jù)源質(zhì)量.為了簡化問題很多方法提出“對象屬性真值唯一性”假設(shè)，并且最終選擇可信性分值最大或者為真概率最大的屬性值作為真值，此類方法適用于單值屬性的真值求解問題.然而，實(shí)際生活中的多值屬性比比皆是，如一本圖書可以有多個作者、一部電影可以有多個主演、一個人可以有多個電話號碼等.針對這些多值屬性，不但要確保所找到真值的正確性，而且要盡可能找到所有真值，我們稱該問題為多真值發(fā)現(xiàn)問題.與投票方法類似，解決此問題最直觀的方法是設(shè)置閾值：選擇TopN個可信性分值的屬性值作為真值，或者選擇為真概率大于K的屬性值作為真值.但是，閾值K的選擇是一個挑戰(zhàn)性的問題，其直接影響算法的查準(zhǔn)率和查全率，例如：屬性值為真概率的閾值選擇越大查準(zhǔn)率越高，但查全率隨之降低.

本文目標(biāo)是解決多值屬性的真值發(fā)現(xiàn)問題，主要貢獻(xiàn)有3點(diǎn)：

1) 將多真值發(fā)現(xiàn)問題轉(zhuǎn)化為一個最優(yōu)化問題.根據(jù)2個觀察：對象的真值情況應(yīng)該盡可能與各數(shù)據(jù)源提供的觀察值接近；數(shù)據(jù)源的質(zhì)量評估至關(guān)重要，其影響了真值發(fā)現(xiàn)的準(zhǔn)確率，數(shù)據(jù)源的質(zhì)量越高則其提供的對象屬性值列表與真值列表越相似.該優(yōu)化問題的目標(biāo)函數(shù)是：各對象的真值取值與數(shù)據(jù)源提供的該對象觀察值之間相似度權(quán)重之和達(dá)到最大，其中權(quán)重是數(shù)據(jù)源質(zhì)量.通過該方法直接得到對象的真值列表，避免通過閾值的設(shè)置選擇對象真值.

2) 真值計算過程中，我們首先提出了一個枚舉的方法求最優(yōu)解，但該方法的時間復(fù)雜度為對象可能值集大小的指數(shù)量級.為了提高算法的執(zhí)行效率，我們提出了一個貪心算法求近似解，將時間復(fù)雜度從可能值集長度的指數(shù)量級降到線性量級.

3) 通過2個真實(shí)數(shù)據(jù)集上的實(shí)驗表明：在準(zhǔn)確性方面，基于枚舉的方法和貪心算法均優(yōu)于現(xiàn)有真值發(fā)現(xiàn)算法；在效率方面，貪心算法優(yōu)于現(xiàn)有的真值發(fā)現(xiàn)方法.

1 相關(guān)工作

Yin等人[1]首次提出真值發(fā)現(xiàn)問題，并提出一種迭代機(jī)制聯(lián)合推導(dǎo)數(shù)據(jù)源質(zhì)量和對象真值.該方法基于啟發(fā)式：高質(zhì)量數(shù)據(jù)源提供的對象值更可能為真，提供越多真值的數(shù)據(jù)源其質(zhì)量越高.后續(xù)一系列相關(guān)研究工作都是在此工作基礎(chǔ)之上考慮不同場景、不同影響因素、不同的對象真值和數(shù)據(jù)源可信性計算方法對基本算法進(jìn)行了各種擴(kuò)展：1)考慮數(shù)據(jù)源之間相互依賴關(guān)系提高真值發(fā)現(xiàn)的準(zhǔn)確率，如拷貝關(guān)系[2-3,6- 7]、隱含分組結(jié)構(gòu)關(guān)系[4]和關(guān)聯(lián)關(guān)系[8]；2)考慮對象難易程度對真值發(fā)現(xiàn)的影響[5]，通過估計每個對象真值判斷的難易程度，避免數(shù)據(jù)源從相對容易的事實(shí)那里獲得過高的可信性分值；3)真值發(fā)現(xiàn)的在線處理[9-10]，解決很多真值發(fā)現(xiàn)方法由于其時間和空間復(fù)雜度只適合一次計算的問題；4)考慮屬性值之間相互關(guān)系，如屬性值之間的相似性[1-2]等；5)考慮數(shù)據(jù)源不同的質(zhì)量評估方法[3,5,8]，一個好的數(shù)據(jù)源質(zhì)量模型是解決真值發(fā)現(xiàn)的關(guān)鍵.

上述真值發(fā)現(xiàn)方法中，文獻(xiàn)[1-6,9-10]的真值計算模型均基于單真值假設(shè)，部分計算模型不適用于對象的多真值計算.另外由于這些算法只是返回各屬性值的可信性分值，如何根據(jù)可信性分值選擇多個真值仍是一個挑戰(zhàn).而本文提出的多真值發(fā)現(xiàn)算法，可以直接返回對象的真值列表.

文獻(xiàn)[8,11]可以處理多真值發(fā)現(xiàn)問題.文獻(xiàn)[11]將數(shù)據(jù)源質(zhì)量和對象屬性值正確性作為隱含變量構(gòu)建一個概率圖模型(LTM)自動推導(dǎo)對象屬性值可信性和數(shù)據(jù)源質(zhì)量，它是第1個可以處理多值屬性真值發(fā)現(xiàn)的方法.LTM方法假設(shè)數(shù)據(jù)源的準(zhǔn)確率和召回率服從Beta分布，據(jù)此推導(dǎo)屬性值為真的概率. 如果真實(shí)數(shù)據(jù)集不滿足假設(shè)的分布，則LTM算法的效率則受到很大影響.與LTM方法不同，本文將多真值問題轉(zhuǎn)化為最優(yōu)化問題，因此對真實(shí)數(shù)據(jù)集的分布沒有限制.文獻(xiàn)[8]基于貝葉斯方法對數(shù)據(jù)源之間的關(guān)系進(jìn)行建模，從而提高真值發(fā)現(xiàn)算法的準(zhǔn)確率，該模型中考慮了多真值發(fā)現(xiàn)問題.與本文方法不同的是：該方法采用監(jiān)督學(xué)習(xí)的方法，通過訓(xùn)練數(shù)據(jù)直接計算數(shù)據(jù)源的質(zhì)量，進(jìn)而推導(dǎo)屬性值為真的概率；而本文采用無監(jiān)督的迭代機(jī)制聯(lián)合推導(dǎo)數(shù)據(jù)源質(zhì)量和對象真值列表.另外，文獻(xiàn)[8, 11]均返回屬性值為真的概率，因此選擇真值列表時同樣需要確定選擇概率值大于閾值K的屬性值為真值，而本文提出的方法可直接返回對象真值列表避免閾值的選擇問題.

2 問題定義

下面我們首先介紹問題相關(guān)定義.

定義1. 多值屬性.表示對象在某一特定屬性上可以有多個值.

例1. 如表1所示，圖書作者屬性就是一個多值屬性.一本書可以同時有多個作者.每個數(shù)據(jù)源可以為同一對象的某個屬性提供多個屬性值.例如Barnes & Noble數(shù)據(jù)源為Rapid Contextual Design圖書提供了3個作者.

定義2. 對象可能值集.所有數(shù)據(jù)源為該對象提供屬性值的集合，即各數(shù)據(jù)源為該對象提供的屬性值集合的并集.

例2. 如表1所示，Rapid Contextual Design的可能值集是所有數(shù)據(jù)源為其提供的作者集合{Karen Holtzblatt, Jessamyn Wendell, Shelley Wood,Jessamyn Burns Wendell,Wood}.

定義3. 對象值向量.該向量為二值向量，描述了給定數(shù)據(jù)源提供的對象觀察值在對象可能值集上的分布情況.

對象值向量的獲得方法是：向量長度為該對象可能值集的長度，如果數(shù)據(jù)源提供了對象可能值集上的第i個對象值，則其對象值向量的第i個元素設(shè)置為1，否則設(shè)置為0.

例3. 如表1所示，根據(jù)例1中得到的對象可能值集，數(shù)據(jù)源Barnes & Noble的對象值向量為(1,1,1,0,0).

定義4. 數(shù)據(jù)源質(zhì)量.表示數(shù)據(jù)源提供對象值的準(zhǔn)確性.這里我們采用數(shù)據(jù)源提供的對象值與對象真值之間總體的相似性來衡量，即如果數(shù)據(jù)源提供的對象值情況越接近于對象真值則其質(zhì)量越高.

定義5. 多真值發(fā)現(xiàn)問題.從多個數(shù)據(jù)源提供的沖突數(shù)據(jù)中找到對象多值屬性的真值列表.

3 MTruths：多真值發(fā)現(xiàn)方法

我們的目標(biāo)是找到最可能正確的對象屬性值集合{Truthi|1≤i≤N}，得到的結(jié)果應(yīng)該盡可能與沖突集中數(shù)據(jù)源提供的對象值情況相似.但是不同的數(shù)據(jù)源其質(zhì)量不同，高質(zhì)量數(shù)據(jù)源提供的對象值與真值的相似度越高，而低質(zhì)量的數(shù)據(jù)源其相似度越低.考慮到實(shí)際應(yīng)用中數(shù)據(jù)源的質(zhì)量一般沒有先驗知識提供，因此本文采用無監(jiān)督的迭代方法計算，每次迭代過程分2步進(jìn)行：1)通過上次迭代獲得的數(shù)據(jù)源質(zhì)量計算真值情況；2)通過本次迭代獲得的真值情況計算數(shù)據(jù)源的質(zhì)量.接下來我們首先介紹數(shù)據(jù)源質(zhì)量的評估方法，然后介紹多真值發(fā)現(xiàn)方法.本節(jié)中所使用的所有變量如表2所示：

Table 2 Variables of MTruths

3.1 數(shù)據(jù)源質(zhì)量評估

數(shù)據(jù)源質(zhì)量越高則其提供的對象觀察值與對象真值越相似，反之其質(zhì)量越低則兩者相似性越低.因此，本文通過數(shù)據(jù)源提供的對象觀察值與對象真值之間的相似性來度量數(shù)據(jù)源質(zhì)量.

針對多值屬性，每個對象可能有多個真值，并且每個數(shù)據(jù)源可以為每個對象提供多個值，因此本文采用二值向量表示對象的取值情況.令向量Ai,j表示數(shù)據(jù)源si為對象oj提供的值向量.向量Ai,j的長度為對象oj可能值集V*,j的長度Lj.向量Ai,j中第l個元素的取值為

(1)

為了計算數(shù)據(jù)源提供的對象觀察值與真值之間的相似性，首先需要定義不同值向量之間相似性計算公式.我們計算值向量之間相似性時，不但考慮數(shù)據(jù)源對象值肯定的相似，還考慮其對象值否定的相似性.信息檢索中常采用向量內(nèi)積的方法計算2個文檔向量相似性，但由于其只考慮對象值肯定的相似性，而忽略了否定相似性.例如2個向量(1,0,0,1,0)和(1,0,1,1,0)內(nèi)積結(jié)果為2，表示有2個同為1的元素，但是未考慮同為0的元素相似性.本文提出2種向量相似性計算方法考慮了屬性值否定相似性因素.方法1可采用向量余弦相似性度量2向量之間相似性：

(2)

第2種相似性計算方法為

(3)

其中,向量Di,j描述Ai,j與A*,j中對應(yīng)元素是否相同，計算方法為

(4)

計算數(shù)據(jù)源質(zhì)量我們使用數(shù)據(jù)源提供的所有對象的值與其真值之間的相似性度量：

(5)

對Qi進(jìn)行標(biāo)準(zhǔn)化處理為

(6)

通過上述方法評估數(shù)據(jù)源質(zhì)量.接下來，根據(jù)取得的數(shù)據(jù)源質(zhì)量信息進(jìn)一步計算對象的真值集合.

3.2 多真值發(fā)現(xiàn)

對象的真值選取結(jié)果應(yīng)該最大程度地接近沖突數(shù)據(jù)集D提供的對象取值情況，即得到的真值向量與沖突數(shù)據(jù)集提供的值向量相似度達(dá)到最大，其目標(biāo)函數(shù)為

(7)

由于迭代過程中計算對象真值時數(shù)據(jù)源質(zhì)量已經(jīng)確定，且本文提出的2個相似性函數(shù)均為凸函數(shù)，所以目標(biāo)函數(shù)是凸函數(shù)的線性組合，故該目標(biāo)函數(shù)也為凸函數(shù)，定能找到一個最優(yōu)解使得目標(biāo)函數(shù)取最大值.

下面我們提出2種求最優(yōu)解的方法：枚舉法、貪心算法.

1) 枚舉法

算法1. 基于枚舉的方法(Enum_M).

輸入: 所有數(shù)據(jù)源為對象oj提供的值集V*,j、各數(shù)據(jù)源質(zhì)量{Qi|1≤i≤M};

輸出: 對象oj真值向量A*,j.

① forx=1 to 2Lj-1

② 將B設(shè)置為長度是Lj的零向量;

③i=1;

④ whilex!=0 do

⑤B[i++]=x%2;

⑥x=x2;

⑦ end while

⑧ fori=1 toM

⑨t(yī)emp+=Qi×sim(Ai,j,B);

⑩ end for

2) 貪心算法

鑒于枚舉方法時間復(fù)雜性過高，當(dāng)對象可能值集太大時，其算法執(zhí)行效率低.為了減少需要比較的值向量數(shù)目，本文設(shè)計了一個對象真值選擇策略：以對象值為真的可能性高低先將對象進(jìn)行排序，優(yōu)先選擇正確可能性高的對象值作為真值.

對象值為真的可能性通過各數(shù)據(jù)源加權(quán)投票的方法度量：

(8)

根據(jù)式(8)生成對象oj各值為真的可能性向量Wj.

算法2. 多真值發(fā)現(xiàn)的貪心算法(Greedy_M).

輸入: 所有數(shù)據(jù)源為對象oj提供的值集V*,j、各數(shù)據(jù)源質(zhì)量信息{Qi|1≤i≤M};

輸出: 對象oj的真值向量A*,j.

① 初始化temp_max=0,A*,j以及B為零向量;

② fori=1 toLj

③ 根據(jù)式(8)計算對象oj第i個值為真的概率wj,i;

④ end for

⑤i=1;

⑥ do

⑦l=SelectTop(Wj,i);

⑧change=false,temp=0,B[l]=1;

⑨ fork=1 toM

⑩temp+=Qk×sim(Ak,j,B);

3.3 算法流程框架

到目前為止，我們已經(jīng)討論了數(shù)據(jù)源質(zhì)量評估以及多真值計算方法.正如第3節(jié)所述，整個計算過程是數(shù)據(jù)源質(zhì)量評估和多真值發(fā)現(xiàn)的一個迭代過程.我們下面給出MTruths算法的總流程.

算法3. 多真值發(fā)現(xiàn)算法總框架(MTruths).

輸入: 沖突集D、數(shù)據(jù)源集合S、對象集合O；

輸出: 對象真值集{Truthi|1≤i≤N};

② do

③n=n+1;

④ forj=1 toN

⑥ end for

⑦ fori=1 toM

⑨ end for

⑩ until(滿足收斂條件)

令迭代次數(shù)為K次，則采用枚舉方法的迭代算法MTruths_Enum的時間復(fù)雜度為O(KNM2Lj)，采用貪心算法的迭代算法MTruths_Greedy的時間復(fù)雜度為O(KNMLj).

4 實(shí) 驗

在2個真實(shí)數(shù)據(jù)集上，將本文提出的方法與現(xiàn)有真值發(fā)現(xiàn)方法從查準(zhǔn)率、查全率、收斂速度、運(yùn)行時間等方面進(jìn)行對比.

4.1 實(shí)驗設(shè)計

4.1.1 對比算法

實(shí)驗對比于5個算法：

1) Voting-K.采用投票機(jī)制計算真值.在所有為該對象提供屬性值的數(shù)據(jù)源中，如果百分比超過K的數(shù)據(jù)源提供了該屬性值，則該屬性值為一個真值.

2) TruthFinder-K. TruthFinder[1]方法在計算屬性值為真的概率時假設(shè)每個對象只有唯一真值，最終選取為真概率最高的屬性值作為真值.為了選擇多個真值，本文選擇概率值大于K的所有屬性值作為真值.

3) LTM-K. LTM算法[11]對數(shù)據(jù)源的2類錯誤(錯誤肯定和錯誤否定)進(jìn)行建模，提出一個概率圖模型來自動推導(dǎo)屬性值為真的概率.LTM-K取屬性值為真概率大于K的屬性值作為真值.該算法的參數(shù)設(shè)置采用文獻(xiàn)建議的默認(rèn)參數(shù).

4) MTruths_Enum.本文提出的一種MTruths算法，其中對象真值發(fā)現(xiàn)時采用枚舉方法判斷真值列表.

5) MTruths_Greedy.在真值列表發(fā)現(xiàn)步驟中為了提高算法效率提出的貪心算法.

4.1.2 數(shù)據(jù)集

本文實(shí)驗使用2個真實(shí)數(shù)據(jù)集：圖書數(shù)據(jù)集，包含多個圖書銷售網(wǎng)站提供的圖書作者信息；電影數(shù)據(jù)集，其包含來自多個電影視頻網(wǎng)站的電影導(dǎo)演信息.

1) 圖書數(shù)據(jù)集

第1個真實(shí)數(shù)據(jù)集采用文獻(xiàn)[2]使用的數(shù)據(jù)集.該數(shù)據(jù)集爬取了圖書網(wǎng)站abebooks.com的圖書信息，包括書名、ISBN、作者列表和數(shù)據(jù)源(圖書銷售網(wǎng)站).我們對原始數(shù)據(jù)集進(jìn)行了去重處理，并對來自不同數(shù)據(jù)源的作者列表中的分隔符進(jìn)行了統(tǒng)一以便對作者列表進(jìn)行分割.經(jīng)過處理后的數(shù)據(jù)集包含1 265本圖書、894個數(shù)據(jù)源、5 741個不同的作者名、119 579條沖突記錄.據(jù)統(tǒng)計，大量數(shù)據(jù)源僅提供很少的圖書信息，平均每個數(shù)據(jù)源提供28本圖書.圖書的作者可能值集大小分布情況如圖1所示，大部分圖書的作者可能值集大小區(qū)間為[1,7]，平均可能值集大小為4.5.隨機(jī)選擇100本圖書對作者進(jìn)行手工標(biāo)注，將其作為標(biāo)準(zhǔn)集.

Fig. 1 Distribution of the number of attribute values for objects.圖1 對象可能值集大小分布

2) 電影數(shù)據(jù)集

電影的導(dǎo)演屬性是一個多值屬性，一部電影可以有多個導(dǎo)演.我們根據(jù)新浪娛樂的互動資料庫中電影列表列出的電影，從11個視頻和影評網(wǎng)站搜索這些電影的導(dǎo)演信息，采用電影名稱和電影上映年代區(qū)分同名問題.針對一部電影有多個名稱問題，根據(jù)網(wǎng)站提供的電影別名和年代信息判斷是否為同一部電影.通過上述方法獲得的數(shù)據(jù)集中包含：12 407部電影實(shí)體、24 567個不同的導(dǎo)演名以及包含來自11個數(shù)據(jù)源的114 006條沖突記錄.平均每個數(shù)據(jù)源提供4 980個電影信息.電影導(dǎo)演屬性可能值集大小的分布情況如圖1所示，大部分電影的導(dǎo)演可能值集大小區(qū)間為[1, 5]，可能值集最大為25.為了評估真值發(fā)現(xiàn)方法的質(zhì)量，我們隨機(jī)選擇了100部電影對其導(dǎo)演信息進(jìn)行手工標(biāo)注，對于進(jìn)口電影導(dǎo)演同時提供中英文名2種形式，將其作為標(biāo)準(zhǔn)集.

4.1.3 度量指標(biāo)

4.1.4 實(shí)驗環(huán)境

本節(jié)所有實(shí)驗硬件環(huán)境為：Intel?CoreTM2Quad2.67GHz處理器、4GB內(nèi)存、Windows7操作系統(tǒng).本文所有算法包括對比算法均使用Python語言實(shí)現(xiàn)，軟件開發(fā)環(huán)境為Python2.7，數(shù)據(jù)庫系統(tǒng)采用mysql5.6.17.

4.2 真值發(fā)現(xiàn)方法的準(zhǔn)確性評估

原始Voting、TruthFinder和LTM算法只能返回每個屬性值為真的可能性，并不能返回對象的真值列表，需要為它們設(shè)定一個閾值K，當(dāng)概率大于K時判定該屬性值為真.實(shí)驗中，我們討論了K分別為25%,50%,75%時真值發(fā)現(xiàn)方法的準(zhǔn)確性差異.我們在圖書數(shù)據(jù)集和電影數(shù)據(jù)集上分別比較了Voting-K，TruthFinder-K，LTM-K，MTruths_Enum，MTruths_Greey的查準(zhǔn)率、查全率和F-score，結(jié)果如圖2和圖3所示:

Fig. 2 Precision, recall and F-score for the book data set.圖2 圖書數(shù)據(jù)集算法結(jié)果的查準(zhǔn)率、查全率和F-Score

Fig. 3 Precision, recall and F-score for the movie data set.圖3 電影數(shù)據(jù)集算法結(jié)果的查準(zhǔn)率、查全率和F-Score

總之，MTruths算法的F-score優(yōu)于其他算法.在圖書數(shù)據(jù)集上，MTruths算法的查準(zhǔn)率較Truth-Finder和LTM算法高出17%;Voting-50%和Voting-75%的算法查準(zhǔn)率雖然稍高于MTruths，但其查全率卻顯著低于MTruths.在電影數(shù)據(jù)集中，MTruths算法同樣獲得了較好的F-score.針對多值屬性問題，MTruths算法既考慮了查準(zhǔn)率也兼顧到查全率，因此在2個數(shù)據(jù)集中MTruths算法的查準(zhǔn)率和查全率比較均衡.而其他算法由于受到閾值或者單真值假設(shè)的影響，其算法的查準(zhǔn)率和查全率差異較大.MTruths_Enum和MTruths_Greedy相比，前者的查準(zhǔn)率、查全率和F-score均略高于后者，但總體差距很小.

Voting算法根據(jù)提供屬性值的數(shù)據(jù)源比例判斷真值，比例越高的屬性值則越可能為真，因此隨著閾值K的增加其查準(zhǔn)率逐漸增高，而查全率顯著降低.在2個數(shù)據(jù)集上，Voting算法當(dāng)K=75%時雖然有很高的查準(zhǔn)率，但查全率均低于35%，因此很難為對象找出完整的真值列表.

TruthFinder方法的查全率低于文獻(xiàn)[11]的實(shí)驗結(jié)果，其原因是度量查全率的標(biāo)準(zhǔn)不同.本文僅當(dāng)作者名與標(biāo)準(zhǔn)集中的姓名完全相同則認(rèn)為正確，而文獻(xiàn)[11]考慮了姓名的部分正確問題，因此本文對正確性的評判標(biāo)準(zhǔn)更為嚴(yán)格.TruthFinder方法假設(shè)了真值唯一，可以將最可能為真的屬性值與其他屬性值區(qū)分開來，但對需要找到多個真值時，則需要通過閾值的設(shè)定完成.在電影數(shù)據(jù)集中，隨著閾值K的變化，TruthFinder方法的查準(zhǔn)率和查全率發(fā)生了顯著變化.

LTM算法考慮了多真值問題，在圖書數(shù)據(jù)集上算法準(zhǔn)確性僅次于MTruths.但由于該算法假設(shè)了數(shù)據(jù)的服從某種概率分布，針對不同的數(shù)據(jù)集需要調(diào)整參數(shù)，因此算法的準(zhǔn)確性將受到數(shù)據(jù)的分布以及參數(shù)的影響.在電影數(shù)據(jù)集上，由于標(biāo)準(zhǔn)集同時提供了導(dǎo)演的中文名和英文名，但大多數(shù)數(shù)據(jù)源僅提供其中一種，雖然其他算法的查全率也有所降低但不顯著，但LTM算法的查全率顯著降低，從而影響了其算法的準(zhǔn)確性.

總之，MTruths算法在準(zhǔn)確性方面總體優(yōu)于其他算法，且不受閾值影響.MTruths_Enum算法準(zhǔn)確性略優(yōu)于MTruths_Greedy.

4.3 真值發(fā)現(xiàn)方法效率評估

由于閾值K對算法Voting-K，TruthFinder-K，LTM-K的影響僅僅體現(xiàn)在算法查準(zhǔn)率、查全率和F-score的計算上，對算法執(zhí)行時間影響很小.因此在對比算法時間時，我們僅列出K=50%的執(zhí)行時間，如表3所示.Voting算法最為高效，其次是MTruths_Greedy.由于MTruths_Enum算法是枚舉算法，圖書數(shù)據(jù)集上算法運(yùn)行時間達(dá)到70.4 min.但是，MTruths_Enum算法的F-Score在所有算法中也是最高的，為了獲得更好的結(jié)果在離線的環(huán)境下這樣的時長也是可以接受的.TruthFinder-50%方法在2個數(shù)據(jù)集上的運(yùn)行時間差異很大，主要是因為運(yùn)行時間不僅與數(shù)據(jù)量有關(guān)還與收斂速度相關(guān)，在圖書數(shù)據(jù)集上TruthFinder-50%方法迭代了40次收斂，而在電影數(shù)據(jù)集上其迭代7次收斂，故電影數(shù)據(jù)集上的運(yùn)行時間遠(yuǎn)遠(yuǎn)少于圖書數(shù)據(jù)集.

Table 3 Comparison of Runtime on Two Data Sets

圖4顯示了MTruths的枚舉算法和貪心算法在電影數(shù)據(jù)集上的收斂速度.本文算法在迭代過程的收斂條件是：采用2次迭代得到的數(shù)據(jù)源質(zhì)量向量余弦相似性來衡量2次迭代結(jié)果的變化情況，相似性越大則變化越小，當(dāng)變化達(dá)到一定閾值則迭代停止.從圖3可以看出2個算法都可以快速收斂.經(jīng)過多次實(shí)驗，我們的算法在5次迭代后即可滿足收斂條件.

Fig. 4 Convergence rate of iterations on movie data set.圖4 電影數(shù)據(jù)集上迭代的收斂速度

Fig. 5 Time with increasing the size of possible values sets of objects selected.圖5 算法執(zhí)行時間隨對象可能值集大小變化情況

對比MTruths_Enum和MTruths_Greedy算法執(zhí)行時間隨對象可能值集大小變化的情況.如圖5所示，在2個數(shù)據(jù)集上分別選擇對象可能值集分別小于等于3,6,9,12,15,18,21,24的對象集合.算法MTruths_Enum的執(zhí)行時間隨對象可能值集大小呈指數(shù)級增長.MTruths_Greedy時間復(fù)雜度是對象可能值集大小的線性量級，因此其效率遠(yuǎn)遠(yuǎn)高于MTruths_Enum算法，但該算法的查全率、查準(zhǔn)率和F-score略低于MTruths_Enum.因此，在實(shí)際應(yīng)用中，當(dāng)數(shù)據(jù)集的對象可能值集較大時，可以選擇貪心算法.

5 結(jié) 論

Web中存在大量沖突信息，如何從沖突信息中找到正確信息是數(shù)據(jù)集成領(lǐng)域研究的一個重要問題.同時，多值屬性普遍存在，很多對象的屬性存在多個真值.然而，已有真值發(fā)現(xiàn)方法多數(shù)針對單值屬性.針對多真值發(fā)現(xiàn)問題，本文提出一個MTruths方法將該問題轉(zhuǎn)化成一個最優(yōu)化問題.根據(jù)觀察，對象真值應(yīng)盡可能與沖突集提供的觀察值相似.因此，所求的對象真值應(yīng)該使其與各數(shù)據(jù)源提供的屬性值相似度加權(quán)和達(dá)到最大.另外，計算真值過程中，我們考慮了數(shù)據(jù)源質(zhì)量對真值發(fā)現(xiàn)的影響.通過迭代的方法，聯(lián)合推導(dǎo)數(shù)據(jù)源質(zhì)量和對象真值.本文分別提出枚舉方法和貪心算法求真值集的最優(yōu)解.通過2個真實(shí)數(shù)據(jù)集上的實(shí)驗結(jié)果表明，這2種方法在準(zhǔn)確性方面均優(yōu)于已有真值發(fā)現(xiàn)方法，貪心算法在效率方面優(yōu)于已有真值發(fā)現(xiàn)方法.

[1]Yin Xiaoxin, Han J, Yu P S.Truth discovery with multiple conflicting information providers on the Web[J]. IEEE Trans on Knowledge and Data Engineering, 2008, 20(6): 796-808

[2]Dong X L, Berti-Equille L, Srivastava D. Integrating conflicting data: The role of source dependence [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 550-561

[3]Dong X L, Berti-Equille L, Srivastava D. Truth discovery and copying detection in a dynamic world [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 562-573

[4]Qi Guojun, Aggarwal C C, Han J, et al. Mining collective intelligence in diverse groups[C] //Proc of the 22nd Int Conf on World Wide Web. New York: ACM, 2013: 1041-1052

[5]Galland A, Abiteboul S, Marian A, et al. Corroborating information from disagreeing views [C] //Proc of the 3rd ACM Int Conf on Web Search and Data Mining. New York: ACM, 2010: 131-140

[6]Blanco L, Crescenzi V, Merialdo P, et al. Probabilistic models to reconcile complex data from inaccurate data sources[C] //Proc of the 22nd Int Conf on Advanced Information Systems Engineering. Berlin: Springer, 2010: 83-97

[7]Li Xian, Dong X L, Kenneth L, et al. Scaling up copy detection[C] //Proc of the 31st Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 89-100

[8]Pochampally R, Sarma A D, Dong X L, et al. Fusing data with correlations[C] //Proc of the 2014 Int Conf on Management of Data. New York: ACM, 2014: 433-444

[9]Liu Xuan, Dong X L, Ooi B C, et al. Online data fusion[J]. Proceedings of the VLDB Endowment, 2011, 4(11): 932-943

[10]Zhao Zhou, Cheng J, Ng W. Truth discovery in data streams: A single-pass probabilistic approach[C] //Proc of the 23rd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2014: 1589-1598

[11]Zhao Bo, Rubinstein B I P, Gemmell J, et al. A Bayesian approach to discovering truth from conflicting sources for data integration[J]. Proceedings of the VLDB Endowment, 2012, 5(6): 550-561

Ma Ruxia, born in 1977. PhD candidate at Renmin University of China. Student member of China Computer Federation. Lecturer in Capital Normal University. Her main research interests include Web data management, the credibility of Web information etc.

Meng Xiaofeng, born in 1964. Professor and PhD supervisor at Renmin University of China. Executive member of China Computer Federation. His main research interests include cloud data management, Web data management, flash-based databases, privacy protection etc.

Wang Lu, born in 1986. PhD candidate at Renmin University of China. Her main research interests include spatial database and location privacy management (luwang@ruc.edu.cn).

Shi Yingjie, born in 1983. PhD. Her main research interests include Web data management, cloud data management, online aggregation techniques over big data.

MTruths：An Approach of Multiple Truths Finding from Web Information

Ma Ruxia1,2, Meng Xiaofeng1, Wang Lu1, and Shi Yingjie3

1(School of Information, Renmin University of China, Beijing 100872)2(DepartmentofEducationTechnology,CapitalNormalUniversity,Beijing100048)3(SchoolofInformationEngineering,BeijingInstituteofFashionTechnology,Beijing100029)

Web has been a massive information repository on which information is scattered in different data sources. It is common that different data sources provide conflicting information for the same entity. It is called the truth finding problem that how to find the truths from conflicting information. According to the number of attribute values, object attributes can be divided into two categories: single-valued attributes and multiple-valued attributes. Most of existing truth finding work is designed for truth finding on single-valued attributes. In this paper, a method called MTruths is proposed to resolve truth finding problem for multiple-valued attributes. We model the problem using an optimization problem. The objective is to maximize the total weight similarity between the truths and observations provided by data sources. In truth finding process, two methods are proposed to find the optimal solution: an enumeration algorithm and a greedy algorithm. Experiments on two real data sets show that the correctness of our approache and the efficiency of the greedy algorithm outperform the existing state-of-the-art techniques.

truth finding; data conflicting; single-valued attributes; multi-valued attributes; quality of data sources

2015-06-30；

2015-10-13

國家自然科學(xué)基金項目(61379050,91224008,61502279)；國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2013AA013204)；高等學(xué)校博士學(xué)科點(diǎn)專項科研基金項目(20130004130001)；中國人民大學(xué)科學(xué)研究基金項目(11XNL010) This work was supported by the National Natural Science Foundation of China (61379050,91224008,61502279), the National High Technology Research and Development Program of China (863 Program) (2013AA013204), the Specialized Research Fund for the Doctoral Program of Higher Education of China (20130004130001), and the Research Funds of Renmin University of China (11XNL010).

孟小峰(xfmeng@ruc.edu.cn)

TP311