面向數據集成的多真值發現算法

陳烈鋒 許青林

（廣東工業大學計算機學院，廣州，510006）

引 言

隨著網絡技術的飛速發展以及智能設備的廣泛使用，數據以前所未有的速度生成和創建。然而，在大數據改變現代社會許多層面的同時，我們也經?？梢杂^察到不同的數據源對同一實體提供了相互沖突的描述。這些沖突往往是由于輸入錯誤、數據過時、記錄丟失等原因造成的[1-2]，如果應用于實際可能會造成巨大的損害和經濟損失。例如，數據在醫療系統中被用于藥物推薦或者在股票市場上數據被用于股票價格預測[3]。給定一個大規模數據，手工確定數據的真實性是不現實的，而真值發現方法能從多個數據源中找到最符合現實的真值來解決沖突，因此成為研究熱門。

到目前為止，已有大量工作來處理真值發現問題?，F有的算法[1-2,4-12]大多能通過迭代的方法來聯合推導數據源的可信度和描述值的置信度，它們綜合考慮各種方面的影響如數據源的依賴關系，先驗知識和數據源的質量等來提高真理發現的準確率。當前算法通常假設每個實體只有一個真值，然而在現實世界中，實體擁有多個真值的情況可能更為常見。例如，一本書通常有多個作者，一部電影可能有幾位導演。盡管先前的算法通過將某個數據源上提供的一組值簡單地看作一個值集，并選擇置信度最高的值集作為真值集，以此來處理多真值發現問題，但是不同的數據源提供的值集通常是有關聯的：同一個實體上兩個數據源提供的值集之間可能存在重疊，并不是完全沖突的。例如，數據源“Powell’s Books”給圖書“Rapid Contextual Design”提供值集V1={Karen Holtzblatt}，而數據源“Barnes&Noble”提供值集V2={Karen Holtzblatt，Jessamyn Wendell，Shell Wood}。采用投票的思想，V1和V2各得 1 票，但如果將值集里的值分開進行投票，值“Karen Holtzblatt”得2票，其他值得1票，因此該值成為真值的可能性更大，如果忽略這層含義將會降低真值發現的準確性。

在多真值發現問題中，由于可能涉及大量的數據源和實體，想獲得完整的真值集是很困難的。例如，文獻[1]通過手工檢查每本書的封面制作用來實驗的圖書作者數據集，花費了大量的時間和精力。因此需要一種無監督的方法來解決真相發現問題。多真值發現問題的另一個挑戰是數據源的質量（即可信度）是未知的；因對數據源的了解很少，且數據源的質量通常是不同的。如果不評估和區分它們，真值發現算法很容易被低質量的數據源誤導。為了解決這些挑戰，文獻[13-17]已經提出了一些方法來處理多值實體，然而它們并沒有考慮描述值不同表現形式的影響，忽略了相似值對實體真值的支持。例如，“Jessamyn Wendell”和“Jessamyn Burns Wendell”可能是同一作者姓名的不同表現形式，因此它們是相互支持的，忽略這些值的影響可能會降低真值發現的準確率。

本文主要貢獻如下：

（1）基于啟發式思想，本文將多真值發現轉化為一個函數優化問題，目標函數是每個實體的真值集與數據源對該實體提供的所有值集之間的相似度加權和達到最大，權重為數據源可信度。

（2）在計算實體真值的過程中，根據對目標函數的求解并采用貪心策略來選取實體的真值。同時，我們定義一種非對稱的支持度計算方法來度量相似值之間的影響，并結合相似值的支持到描述值置信度的計算當中，提高了真值發現的準確率。

（3）通過多個數據集上的實驗表明，本文算法的準確率優于現有的真值發現算法。

1 文獻綜述

目前真值發現問題已有了廣泛的研究。最簡單的方法是采用基于投票的方法，當實體的某個描述值所獲得的票數達到某個閾值時，該值則被認為是真值。然而，該方法沒有考慮數據源的可信度對描述值置信度的影響。文獻[2]提出了一種可以迭代計算數據源可信度和描述值置信度的算法TruthFinder。該算法基于啟發式思想：可信度越高的數據源提供的描述值置信度越高，同時提供越多高置信度描述值的數據源的可信度也越高，因此可以利用兩者的關系進行迭代計算。之后在這一思想基礎上，研究人員通過考慮不同場景或不同影響因素對基本算法進行擴展。文獻[3-7]考慮數據源之間的依賴關系，如復制關系[3-6]和分組關系[7]等，顯著提高了真值發現的準確率。文獻[6]考慮信息的時效性，作者采用隱馬爾科夫模型來判斷數據源之間的復制關系和復制時間，建立一個貝葉斯模型從數據源中聚合信息從而確定信息的真實性。文獻[9]通過估計實體每個描述值的獲取難度從而避免數據源從獲取難度較低的描述值中獲得較高的可信度。文獻[10]通過將先驗知識引入到真值發現中而得到更高的精度。文獻[11-12]可以進行真值發現的在線計算。文獻[8-9]對數據源可信度采取不同的度量方法來提高真值發現的準確率。

盡管真值發現問題已經進行了大量研究，然而大多數研究集中在單真值發現問題，多真值發現問題的研究相對較少[18]。文獻[13]通過構建一個概率圖模型LTM來聯合推導實體描述值的置信度和數據源可信度，是第一個處理多真值發現的模型。然而，該模型假設數據源的準確率和召回率服從某一特定分布，如果真實數據集不滿足假設的分布，該算法的效率則受到很大影響。文獻[14]通過分析多真值發現問題的特性，結合數據源對描述值置信度的影響和一種更優的拷貝檢測技術到貝葉斯模型中，提高了真值發現的效率。文獻[15]也提出了一種考慮多值實體的概率模型，然而該模型需要初始化多個參數，如每個實體真值的個數和假值的個數等，對真值發現的準確率有一定影響。文獻[16]設計3種模型（即副產品模型、聯合模型和合成模型）用于增強現有的真實發現算法。最近，Fang等[17]提出了一種基于圖的模型，通過對兩類數據源關系的建模來估計數據源的可信度和檢測數據源之間的惡意復制，并考慮實體流行度對真值發現的影響，提高了真值發現的準確率。然而，上述方法沒有考慮實體描述值的不同表現形式，忽略了相似值對實體真值的影響。

與上述多真值發現方法相比，本文算法有兩個創新點：（1）本文算法將多真值發現轉化為一個函數優化問題，通過對目標函數的求解直接返回實體的真值列表；（2）本文算法考慮描述值不同表現形式的影響，提出一種非對稱的相似值支持度計算方法，結合相似值的支持到描述值可信度的計算當中。

2 問題描述

數據源通常會提供實體多個屬性的描述值信息，然而對于每個屬性來說，數據源的可信度可能不同，因此每個屬性類型需要進行單獨處理。本文假設實體只有一個屬性來簡化討論。

本章首先給出一些相關定義，然后在此基礎上對本文所提問題進行形式化定義。

2.1 相關定義

定義1數據源為真值發現問題提供相互沖突的數據，可以來自網站、數據庫等等。

定義2一個實體表示一個能在真實世界中被識別的、唯一的對象。例如：一本書或一部電影。

定義3一個數據源可以為一個實體提供多個描述值，這些值可以組成一個值集。

定義4實體的可能值集表示所有數據源對該實體提供的值集的并集。

定義5在實體的可能值集中，所有與真實世界一致的值構成了一個真理集。

定義6實體的屬性上只有一個真值的稱為單真值發現問題，不止一個真值的稱為多真發現問題。本文研究的是多真值發現問題。例如，電影可能有多個導演，一本書可能有多個作者。

定義7不同的數據源為同一個實體提供不同的值集，從而產生數據沖突。

2.2 問題定義

假設有數據源集合S={s1,s2,s3,…,sm}，這里m表示數據源的數量。聯合提供實體集合E={e1,e2,e3,…,en}，n表示實體的數量。在多真值發現問題中，數據源s可以給實體e提供一個值集，用V表示。實體e的可能值集則是S對e提供的所有值集的并集，用表示，同時用L表示V*的長度。實體e可以有多個真值，用Truth表示該實體的真值集，Truth是V*的子集。由此，本文問題可以定義為：給定一個沖突數據源集合S和一個實體集合E，本文的任務是為每個實體在該實體的可能值集V*中找到真值集Truth。

3 多真值發現算法

本節譯述了方法細節，包括值集之間相似度的定義，多真值發現的框架以及相應的算法。本節中使用的所有變量如表1所示。

表1 變量描述Tab.1 Variable description

3.1 值集之間的相似度計算

余弦相似度常用來計算文檔向量之間的相似性，將文本中的詞語映射到向量空間，形成文檔中詞頻與向量數據的映射關系，通過計算兩個向量之間的余弦相似度得出文檔之間的相似度。例如計算下面兩個句子的相似度：

A：“我愛母親，也愛父親”；

B：“我愛父親，更愛母親”。

首先對句子進行分詞，得到分詞集合{我愛母親也父親更}，計算詞頻：

A：我1，愛 2，母親1，也 1，父親1，更0；

B：我1，愛2，母親1，也 0，父親1，更 1。

得出詞頻向量A(1,2,1,1,1,0)和B(1,2,1,0,1,1)。通過計算兩個向量的余弦相似度即可得兩個句子的相似度。

因此，本文將余弦相似度引入到值集之間的相似度計算當中來。令向量A表示值集V的二值向量，A的長度為實體可能值集V*的長度，則向量A的第i個元素值為

式中，V*[i]表示V*的第i個元素。例如：可能值集合V*={a,b,c,d,e}，值集V={a,c,d}，則V的二值向量A=(1,0,1,1,0)。

通過余弦相似度來度量兩個值向量之間的相似性為

3.2 數據源可信度計算與實體多真值發現

3.2.1 基本推導

數據源可信度越高，則其提供的值集與實體的真值集相似度越高，反之，兩者的相似度越低。因此，本文通過計算數據源提供的所有值集與實體真值集的平均相似度來度量數據源的可信度，用A*表示實體的真值集，可得

實體的真實集應該最大程度地接近沖突數據源提供的所有值集。為了找到最可能正確的真值集，結果應該在所有數據源提供的值集中相似度達得最大。因此，提出本文多真值發現的目標函數

到目前為止，已經將多真理發現轉化為一個優化問題。根據目標函數可以在實體的可能值集中選取置信度最高的幾個值成為真值。在多真值發現問題中，實體可能值的置信度通常是不同的，置信度高的描述值會更大可能成為實體的真值。因此，本文采用一種貪心選擇策略：根據置信度的大小對實體的可能值進行排序，然后優先選擇高可信度的描述值作為實體的真值。

對于描述值v，通過各數據源的加權投票來計算其置信度

由式（5）得到實體每個可能值的置信度大小，從而生成置信度向量W。根據W按從大到小的順序將可能值放入候選真值集，然后計算該真值集與實體的所有值集之間的相似度，保留相似度之和較大的真值集，最后相似度之和最大的真值集就是所求解。具體算法如算法1所示，算法的時間復雜度為O(ML)。

算法1實體真值發現

輸入：V*,{t(s)|s∈S}

輸出：Truth

3.2.2 結合相似值的影響

在現實中，同一個值有不同表現形式的情況是很常見的，例如，“Shell Wood”和“Wood”很可能是同個真值的不同表現形式?，F有的多真值發現算法忽略了它們對真值的支持。同時，“Shell Wood”包含“Wood”，所以“Shell Wood”有更高的概率成為一個真值。在實際中，許多錯誤的值可能是由于數據不完整或缺少某系部分造成的，然而它們可以用來提高真值的置信度，從而提升真值發現的準確率。因此，本文提出了一種非對稱的支持度計算方法：

令Z1，Z2分別表示描述值v1，v2包含的單詞集合，m，n分別表示Z1，Z2中的單詞個數，則v1對v2的支持度為

式中，isSame(Z1[i],Z2[j])∈{0,1}，兩個單詞相等時取值1，否則取值 0。例如, 當v1=“Wood”，v2=“Shell Wood”時，sup(v1,v2)=1但是sup(v2,v1)=1/2。v2有更高的概率成為真值。因此，根據式（6）可以對描述值的置信度進行修正，定義調和置信度

式中，ρ是一個0和1之間的參數，控制相似值的影響。為了獲得值v的調和置信度c*,需要得到它的相似值列表?；趩l式思想：一個描述值的不同表現形式與該描述值不可能出現在同一值集中。因此，采用一種簡單的方法，值v相似值列表中的值需滿足兩個條件：（1）對值v的支持度大于零。（2）不會出現在包含v的值集中。例如，“o’leary timothy j”根據條件1有兩個相似值“o’leary linda i”和“timothy j”。然而，“o’leary timothy j”和“o’leary linda i”同時出現在一個值集中，因此很有可能是不同的值，根據條件（2），排除了“o’leary linda i”。具體算法如算法2所示。

算法2相似值列表計算.

3.3 迭代計算

如上所述，若知道數據源的可信度，那么可以推導實體的真值集，反之亦然。與TruthFinder算法類似，采用迭代的方法來聯合推導數據源的可信度和實體的真值集。算法一開始并不知道關于數據源和真值集的信息，但每次迭代都進一步了解數據源的質量信息和實體的真值集，直到滿足收斂條件時算法則會停止。下面給出了算法的總體流程。

首先，為所有數據源的可信度設置初始值T0（T0為估計的平均可信度，本文設T0=0.9），然后開始迭代計算。每次迭代分兩步：（1）使用從上一次迭代獲得的數據源可信度來計算實體的真值集；（2）使用上一次迭代獲得的真值集計算數據的源可信度。如此迭代直到算法達到穩定狀態。穩定狀態通過數據源可信度的變化來度量，用向量T來表示。使用余弦相似度來度量兩次迭代之間T的變化。如果只在迭代之后T只改變了一點點，則算法停止。

算法3算法框架.

輸入：S，E

輸出：{Truth|e∈E}

如果算法迭代K次，則本文算法的時間復雜度為O(KMNL)。

4 實 驗

本節通過3個真實數據集比較了本文算法和現有的真值發現算法，并給出了實驗結果。

4.1 實驗設計

4.1.1 對比算法

Voting：該方法基于投票，如果一個描述值獲得的票數占總票數的比例超過0.5，則認為該值為真。

Truthfinder[1]：該方法能聯合推導數據源的可信度和值集的置信度，并考慮了不同值集之間的影響。

LTM[18]：該方法通過構建一個概率圖模型來聯合推導實體描述值的置信度和數據源的可信度。

MBM[13]：該方法定義一種新的描述值之間的互相排斥，同時結合更優的復制檢測到一個貝葉斯模型中來進行真值發現。

MTD-hrd[14]：該方法通過結合兩種影響，非平衡的肯定和否定斷言的分布和描述值在同一值集共同出現的頻數來增強它的概率模型。

SmartMTD[16]：該方法通過對兩種類型的數據源關系進行建模來計算數據源的可信度和探測數據源的惡意復制。

OptMTF：本文提出的多真值發現算法。

4.1.2 數據集

（1）圖書-作者數據集

從O’Reilly官網中提取了一部分已出版的圖書數據，包括書名、作者、出版年份、ISBN，并將這些數據當作真值。隨機抽取100本圖書，以ISBN為關鍵字，在abebooks.com網站上爬取相關圖書數據作為圖書數據集。為使問題更具挑戰性，刪除了只有輕微沖突的記錄。處理后的數據集共包含來自685個數據源的10 583個沖突記錄，平均每本書有8個可能的作者。作者可能值的數量分布如圖1所示。

（2）電影-導演數據集

從IMDB網站中提取了最流行的100部電影數據，包括電影和導演的名字?；贗MDB站點的權威性，將該站點的電影數據作為真值。然后根據選擇的電影名稱，采用了一種類似于文獻[1]的做法在谷歌上進行搜索，提取了由不同站點提供的電影導演信息作為電影數據集。該數據集包括來自743個來源的403個導演的數據，平均每個電影有7個可能的導演。導演可能值的數量分布如圖1所示。

（3）父母-孩子數據集

采用文獻[10]的做法在維基百科上提取與父母孩子相關的數據，同時使用最后一次編輯結果作為真值。與處理圖書-作者數據集的方法類似，我們移除了較小沖突的數據。最終數據集有1 202個人的孩子的數據，平均每個人有6個可能的孩子信息。孩子可能值的數量分布如圖1所示。

4.1.3 度量指標

使用3個指標來評估算法的性能。對于所有這些指標，較大的值表示更好的結果。

（1）精確率Precision，表示在所有實體預測的真值集合中，預測實際真值的平均百分比；

（2）召回率Recall，表示在所有實體實際的真值集合中，預測實際真值的平均百分比；

圖1 實體可能值集大小的分布Fig.1 Distribution of size of entity possible value sets

（3）調和平均值F-score，精確率和召回率的調和平均值，范圍從0到1。其計算公式為

4.1.4 實驗環境

本節實驗硬件環境為4 GB內存,2.5 GHz Intel Core i5處理器和Windows 10操作系統。本文用JAVA語言實現了所有比較算法。

4.2 實驗結果

4.2.1 對比現有的真值發現算法

表2展示了不同算法在3個真實數據集上準確度、召回率和的表現，已被加粗的是最優的結果?？梢钥吹?，對比現有的真值發現算法，本文算法的F-score始終能達到最好的結果。由于在圖書數據集和父母數據集上消除了少量沖突的記錄，所有算法在這兩個數據集上準確度較低。同時，由于電影數據集的記錄比其他兩個數據集多，所有算法在電影數據集上運行的時間較長。

Voting算法在3個數據集上準確度較高，它的召回率是最低的，同時該算法的運行時間是最低的。這是因為大多數數據源只提供了小部分的完整真值集，同時Voting算法沒有考慮數據源的可信度，可信度高的數據源提供的值沒有得到更多的權重，因此降低了召回率。

表2 不同方法的比較Tab.2 Comparison of different methods

TtruthFinder算法考慮了數據源的可信度和值集之間的相互影響，但其在圖書數據集上的表現比Voting算法更差，這可能歸因于該算法的單真值假設。需注意的是，在本文實驗中，Voting算法是基于單個描述值而不是整個值集來計算票數的。例如，如果值集（A，B）得到2票，而值集（A，C）得到3票，那么A理應得到5票。

除本文算法之外，MBM算法和SmartMTD算法跟其他算法相比也有較好的表現，這是因為考慮了數據源的否定斷言，從而提高真值發現的準確率。雖然MTD-hrd算法和LTM算法也考慮了這層含義，但它們對潛在變量的先驗分布做出了很強的假設。如果數據集不符合假設的分布，那么算法的表現將會很差。然而，現有的多真值發現算法沒有考慮值的不同表現形式，本文算法結合相似值對真值的影響來提高描述值置信度的計算精度，同時根據所提的目標函數選取可信度較高的描述值作為實體的真值，無需對數據源做出先驗假設，因此OptMTF算法實現了更高的準確度。

4.2.2 相似值的影響

為了評估相似值的影響和結合相似值計算的重要性，實現了本文算法（即OptMTF）的另一個版本用于比較。

OptMTF-s：OptMTF的另一個版本，它沒有考慮相似值對模型的影響。

圖2展示了兩種實現方法在電影數據集上的比較?？梢钥吹?，OptMTF的準確度和召回率明顯高于OptMTF-s，盡管其執行時間稍長點。圖3顯示了兩種方法在電影數據集上的迭代，這兩種方法都可以在幾次迭代之后達到收斂。這些數據證明了結合相似值支持的正確性。在現實中，同一個值具有不同表現形式的情況是很常見的。表3中列出了圖書“Rapid Contextual Design”(ISBN：0123540518)的作者的相似值?，F有的多真值發現算法認為它們是錯誤的值，但它們并不是完全錯誤的。它們通常是因為信息不完整或缺少某些部分造成的，結合它們的支持能夠提高真值發現的準確性。特別是采用非對稱的方法來計算值之間的支持度，使得完整值（即包含其他值）將獲得更高的支持度，它們會比其他值更優先被選為真值。例如，當“Jessamyn Burns Wendell”被加入真值集時，根據對目標函數的計算，它的相似值“Jessamyn Wendell”幾乎不可能被加入真值集，即使該值的調和置信度和真值很接近，通過這種方法可以得到更準確的真值結果。

圖2 兩種方法在電影數據集上的對比Fig.2 Comparison of two methods on movie dataset

圖3 兩種方法在電影數據集上的迭代Fig.3 Iteration of two methods on movie database

5 結束語

在數據集成系統中，從沖突數據中找到正確的信息是至關重要的。本文提出了一個多真值發現算法OptMTF。該算法將多真值發現轉化為一個函數優化問題，其目標是實體的真值集應該與數據源對該實體提供的所有值集之間相似度最高。根據目標函數對真值的選擇，設計了一個迭代算法來聯合推到數據源的可信度和實體的真值集，同時，考慮值不同表現形式的影響，結合相似值的支持來計算描述值的置信度，達到更好的真值發現效果。最后通過3個真實數據集上的實驗表明本文算法的有效性。

表3 幾個真值的相似值表Tab.3 Table of similar values of several true values