MTruths：Web信息多真值發現方法

馬如霞 孟小峰 王 璐 史英杰

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

?

MTruths：Web信息多真值發現方法

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

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

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

真值發現；數據沖突；單值屬性；多值屬性；數據源質量

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

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

本文目標是解決多值屬性的真值發現問題，主要貢獻有3點：

1) 將多真值發現問題轉化為一個最優化問題.根據2個觀察：對象的真值情況應該盡可能與各數據源提供的觀察值接近；數據源的質量評估至關重要，其影響了真值發現的準確率，數據源的質量越高則其提供的對象屬性值列表與真值列表越相似.該優化問題的目標函數是：各對象的真值取值與數據源提供的該對象觀察值之間相似度權重之和達到最大，其中權重是數據源質量.通過該方法直接得到對象的真值列表，避免通過閾值的設置選擇對象真值.

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

3) 通過2個真實數據集上的實驗表明：在準確性方面，基于枚舉的方法和貪心算法均優于現有真值發現算法；在效率方面，貪心算法優于現有的真值發現方法.

1 相關工作

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

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

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

2 問題定義

下面我們首先介紹問題相關定義.

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

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

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

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

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

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

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

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

定義5. 多真值發現問題.從多個數據源提供的沖突數據中找到對象多值屬性的真值列表.

3 MTruths：多真值發現方法

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

Table 2 Variables of MTruths

3.1 數據源質量評估

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

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

(1)

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

(2)

第2種相似性計算方法為

(3)

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

(4)

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

(5)

對Qi進行標準化處理為

(6)

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

3.2 多真值發現

對象的真值選取結果應該最大程度地接近沖突數據集D提供的對象取值情況，即得到的真值向量與沖突數據集提供的值向量相似度達到最大，其目標函數為

(7)

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

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

1) 枚舉法

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

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

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

① forx=1 to 2Lj-1

② 將B設置為長度是Lj的零向量;

③i=1;

④ whilex!=0 do

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

⑥x=x2;

⑦ end while

⑧ fori=1 toM

⑨temp+=Qi×sim(Ai,j,B);

⑩ end for

2) 貪心算法

鑒于枚舉方法時間復雜性過高，當對象可能值集太大時，其算法執行效率低.為了減少需要比較的值向量數目，本文設計了一個對象真值選擇策略：以對象值為真的可能性高低先將對象進行排序，優先選擇正確可能性高的對象值作為真值.

對象值為真的可能性通過各數據源加權投票的方法度量：

(8)

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

算法2. 多真值發現的貪心算法(Greedy_M).

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

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

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

② fori=1 toLj

③ 根據式(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 算法流程框架

到目前為止，我們已經討論了數據源質量評估以及多真值計算方法.正如第3節所述，整個計算過程是數據源質量評估和多真值發現的一個迭代過程.我們下面給出MTruths算法的總流程.

算法3. 多真值發現算法總框架(MTruths).

輸入: 沖突集D、數據源集合S、對象集合O；

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

② do

③n=n+1;

④ forj=1 toN

⑥ end for

⑦ fori=1 toM

⑨ end for

⑩ until(滿足收斂條件)

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

4 實 驗

在2個真實數據集上，將本文提出的方法與現有真值發現方法從查準率、查全率、收斂速度、運行時間等方面進行對比.

4.1 實驗設計

4.1.1 對比算法

實驗對比于5個算法：

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

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

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

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

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

4.1.2 數據集

本文實驗使用2個真實數據集：圖書數據集，包含多個圖書銷售網站提供的圖書作者信息；電影數據集，其包含來自多個電影視頻網站的電影導演信息.

1) 圖書數據集

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

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

2) 電影數據集

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

4.1.3 度量指標

4.1.4 實驗環境

本節所有實驗硬件環境為：Intel?CoreTM2Quad2.67GHz處理器、4GB內存、Windows7操作系統.本文所有算法包括對比算法均使用Python語言實現，軟件開發環境為Python2.7，數據庫系統采用mysql5.6.17.

4.2 真值發現方法的準確性評估

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

Fig. 2 Precision, recall and F-score for the book data set.圖2 圖書數據集算法結果的查準率、查全率和F-Score

Fig. 3 Precision, recall and F-score for the movie data set.圖3 電影數據集算法結果的查準率、查全率和F-Score

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

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

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

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

總之，MTruths算法在準確性方面總體優于其他算法，且不受閾值影響.MTruths_Enum算法準確性略優于MTruths_Greedy.

4.3 真值發現方法效率評估

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

Table 3 Comparison of Runtime on Two Data Sets

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

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

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

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

5 結 論

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

[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

國家自然科學基金項目(61379050,91224008,61502279)；國家“八六三”高技術研究發展計劃基金項目(2013AA013204)；高等學校博士學科點專項科研基金項目(20130004130001)；中國人民大學科學研究基金項目(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