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

馬如霞 孟小峰 王 璐 史英杰

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

Web已成為一個(gè)浩瀚的信息海洋，其信息分散在不同的數(shù)據(jù)源中.不同數(shù)據(jù)源常常為同一對(duì)象實(shí)體提供沖突的屬性值.如何從這些沖突屬性值中找到真值被稱為真值發(fā)現(xiàn)問題.根據(jù)屬性值數(shù)量可將對(duì)象屬性分為單值屬性和多值屬性，現(xiàn)有的多數(shù)真值發(fā)現(xiàn)算法對(duì)單值屬性的真值發(fā)現(xiàn)比較有效.針對(duì)多值屬性的真值發(fā)現(xiàn)問題，提出了一個(gè)多真值發(fā)現(xiàn)方法MTruths，該方法將多真值發(fā)現(xiàn)問題轉(zhuǎn)化為一個(gè)最優(yōu)化問題，其目標(biāo)是：各對(duì)象的真值與各數(shù)據(jù)源提供的觀察值之間的相似性加權(quán)和達(dá)到最大.對(duì)象真值求解過(guò)程中，提出2種方法求真值列表的最優(yōu)解：基于枚舉的方法和貪心算法.與已有方法不同的是MTruths可以直接得到對(duì)象的多個(gè)真值.最后，通過(guò)圖書和電影2個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，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)信息量正以驚人的速度急劇增長(zhǎng)，儼然成為一個(gè)巨大的信息庫(kù).Web已經(jīng)滲透到人們?nèi)粘Ｉa(chǎn)、生活的方方面面，逐漸成為人們獲取信息的重要來(lái)源.人們?cè)谙硎軄?lái)自Web豐富信息的同時(shí)，也受到信息質(zhì)量問題的困擾，大量錯(cuò)誤、過(guò)時(shí)、不完整、虛假信息充斥于網(wǎng)絡(luò).其中，信息沖突問題尤為突出，不同數(shù)據(jù)源為相同對(duì)象同一屬性提供沖突的值.例如，不同圖書網(wǎng)站為同一本書提供了不同的作者信息，如表1所示；各航空網(wǎng)站為同一航班提供不同的登機(jī)時(shí)間、在線零售商為同一商品提供了不一致的產(chǎn)品規(guī)格說(shuō)明等.這些沖突信息可能由于輸入錯(cuò)誤、信息過(guò)期、語(yǔ)義理解不一致、抽取程序錯(cuò)誤等各種原因造成，給用戶帶來(lái)誤導(dǎo)甚至造成巨大損失.如何從不同數(shù)據(jù)源提供的沖突信息中找到正確信息是提高Web信息質(zhì)量亟待解決的問題，該問題也被稱為真值發(fā)現(xiàn)問題[1].

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

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

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

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

3) 通過(guò)2個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明：在準(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ì)量和對(duì)象真值.該方法基于啟發(fā)式：高質(zhì)量數(shù)據(jù)源提供的對(duì)象值更可能為真，提供越多真值的數(shù)據(jù)源其質(zhì)量越高.后續(xù)一系列相關(guān)研究工作都是在此工作基礎(chǔ)之上考慮不同場(chǎng)景、不同影響因素、不同的對(duì)象真值和數(shù)據(jù)源可信性計(jì)算方法對(duì)基本算法進(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)考慮對(duì)象難易程度對(duì)真值發(fā)現(xiàn)的影響[5]，通過(guò)估計(jì)每個(gè)對(duì)象真值判斷的難易程度，避免數(shù)據(jù)源從相對(duì)容易的事實(shí)那里獲得過(guò)高的可信性分值；3)真值發(fā)現(xiàn)的在線處理[9-10]，解決很多真值發(fā)現(xiàn)方法由于其時(shí)間和空間復(fù)雜度只適合一次計(jì)算的問題；4)考慮屬性值之間相互關(guān)系，如屬性值之間的相似性[1-2]等；5)考慮數(shù)據(jù)源不同的質(zhì)量評(píng)估方法[3,5,8]，一個(gè)好的數(shù)據(jù)源質(zhì)量模型是解決真值發(fā)現(xiàn)的關(guān)鍵.

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

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

2 問題定義

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

定義1. 多值屬性.表示對(duì)象在某一特定屬性上可以有多個(gè)值.

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

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

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

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

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

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

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

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

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

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

Table 2 Variables of MTruths

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

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

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

(1)

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

(2)

第2種相似性計(jì)算方法為

(3)

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

(4)

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

(5)

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

(6)

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

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

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

(7)

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

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

1) 枚舉法

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

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

輸出: 對(duì)象oj真值向量A*,j.

① forx=1 to 2Lj-1

② 將B設(shè)置為長(zhǎng)度是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) 貪心算法

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

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

(8)

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

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

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

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

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

② fori=1 toLj

③ 根據(jù)式(8)計(jì)算對(duì)象oj第i個(gè)值為真的概率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ì)量評(píng)估以及多真值計(jì)算方法.正如第3節(jié)所述，整個(gè)計(jì)算過(guò)程是數(shù)據(jù)源質(zhì)量評(píng)估和多真值發(fā)現(xiàn)的一個(gè)迭代過(guò)程.我們下面給出MTruths算法的總流程.

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

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

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

② do

③n=n+1;

④ forj=1 toN

⑥ end for

⑦ fori=1 toM

⑨ end for

⑩ until(滿足收斂條件)

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

4 實(shí) 驗(yàn)

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

4.1.1 對(duì)比算法

實(shí)驗(yàn)對(duì)比于5個(gè)算法：

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

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

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

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

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

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

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

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

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

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

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

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

4.1.3 度量指標(biāo)

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

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

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

原始Voting、TruthFinder和LTM算法只能返回每個(gè)屬性值為真的可能性，并不能返回對(duì)象的真值列表，需要為它們?cè)O(shè)定一個(gè)閾值K，當(dāng)概率大于K時(shí)判定該屬性值為真.實(shí)驗(yàn)中，我們討論了K分別為25%,50%,75%時(shí)真值發(fā)現(xiàn)方法的準(zhǔn)確性差異.我們?cè)趫D書數(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.針對(duì)多值屬性問題，MTruths算法既考慮了查準(zhǔn)率也兼顧到查全率，因此在2個(gè)數(shù)據(jù)集中MTruths算法的查準(zhǔn)率和查全率比較均衡.而其他算法由于受到閾值或者單真值假設(shè)的影響，其算法的查準(zhǔn)率和查全率差異較大.MTruths_Enum和MTruths_Greedy相比，前者的查準(zhǔn)率、查全率和F-score均略高于后者，但總體差距很小.

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

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

LTM算法考慮了多真值問題，在圖書數(shù)據(jù)集上算法準(zhǔn)確性僅次于MTruths.但由于該算法假設(shè)了數(shù)據(jù)的服從某種概率分布，針對(duì)不同的數(shù)據(jù)集需要調(diào)整參數(shù)，因此算法的準(zhǔn)確性將受到數(shù)據(jù)的分布以及參數(shù)的影響.在電影數(shù)據(jù)集上，由于標(biāo)準(zhǔn)集同時(shí)提供了導(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)方法效率評(píng)估

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

Table 3 Comparison of Runtime on Two Data Sets

圖4顯示了MTruths的枚舉算法和貪心算法在電影數(shù)據(jù)集上的收斂速度.本文算法在迭代過(guò)程的收斂條件是：采用2次迭代得到的數(shù)據(jù)源質(zhì)量向量余弦相似性來(lái)衡量2次迭代結(jié)果的變化情況，相似性越大則變化越小，當(dāng)變化達(dá)到一定閾值則迭代停止.從圖3可以看出2個(gè)算法都可以快速收斂.經(jīng)過(guò)多次實(shí)驗(yàn)，我們的算法在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í)行時(shí)間隨對(duì)象可能值集大小變化情況

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

5 結(jié) 論

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

國(guó)家自然科學(xué)基金項(xiàng)目(61379050,91224008,61502279)；國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2013AA013204)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目(20130004130001)；中國(guó)人民大學(xué)科學(xué)研究基金項(xiàng)目(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