面向數(shù)據(jù)集成的多真值發(fā)現(xiàn)算法

陳烈鋒 許青林

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州，510006）

引 言

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

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

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

本文主要貢獻(xiàn)如下：

（1）基于啟發(fā)式思想，本文將多真值發(fā)現(xiàn)轉(zhuǎn)化為一個(gè)函數(shù)優(yōu)化問(wèn)題，目標(biāo)函數(shù)是每個(gè)實(shí)體的真值集與數(shù)據(jù)源對(duì)該實(shí)體提供的所有值集之間的相似度加權(quán)和達(dá)到最大，權(quán)重為數(shù)據(jù)源可信度。

（2）在計(jì)算實(shí)體真值的過(guò)程中，根據(jù)對(duì)目標(biāo)函數(shù)的求解并采用貪心策略來(lái)選取實(shí)體的真值。同時(shí)，我們定義一種非對(duì)稱的支持度計(jì)算方法來(lái)度量相似值之間的影響，并結(jié)合相似值的支持到描述值置信度的計(jì)算當(dāng)中，提高了真值發(fā)現(xiàn)的準(zhǔn)確率。

（3）通過(guò)多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文算法的準(zhǔn)確率優(yōu)于現(xiàn)有的真值發(fā)現(xiàn)算法。

1 文獻(xiàn)綜述

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

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

與上述多真值發(fā)現(xiàn)方法相比，本文算法有兩個(gè)創(chuàng)新點(diǎn)：（1）本文算法將多真值發(fā)現(xiàn)轉(zhuǎn)化為一個(gè)函數(shù)優(yōu)化問(wèn)題，通過(guò)對(duì)目標(biāo)函數(shù)的求解直接返回實(shí)體的真值列表；（2）本文算法考慮描述值不同表現(xiàn)形式的影響，提出一種非對(duì)稱的相似值支持度計(jì)算方法，結(jié)合相似值的支持到描述值可信度的計(jì)算當(dāng)中。

2 問(wèn)題描述

數(shù)據(jù)源通常會(huì)提供實(shí)體多個(gè)屬性的描述值信息，然而對(duì)于每個(gè)屬性來(lái)說(shuō)，數(shù)據(jù)源的可信度可能不同，因此每個(gè)屬性類型需要進(jìn)行單獨(dú)處理。本文假設(shè)實(shí)體只有一個(gè)屬性來(lái)簡(jiǎn)化討論。

本章首先給出一些相關(guān)定義，然后在此基礎(chǔ)上對(duì)本文所提問(wèn)題進(jìn)行形式化定義。

2.1 相關(guān)定義

定義1數(shù)據(jù)源為真值發(fā)現(xiàn)問(wèn)題提供相互沖突的數(shù)據(jù)，可以來(lái)自網(wǎng)站、數(shù)據(jù)庫(kù)等等。

定義2一個(gè)實(shí)體表示一個(gè)能在真實(shí)世界中被識(shí)別的、唯一的對(duì)象。例如：一本書(shū)或一部電影。

定義3一個(gè)數(shù)據(jù)源可以為一個(gè)實(shí)體提供多個(gè)描述值，這些值可以組成一個(gè)值集。

定義4實(shí)體的可能值集表示所有數(shù)據(jù)源對(duì)該實(shí)體提供的值集的并集。

定義5在實(shí)體的可能值集中，所有與真實(shí)世界一致的值構(gòu)成了一個(gè)真理集。

定義6實(shí)體的屬性上只有一個(gè)真值的稱為單真值發(fā)現(xiàn)問(wèn)題，不止一個(gè)真值的稱為多真發(fā)現(xiàn)問(wèn)題。本文研究的是多真值發(fā)現(xiàn)問(wèn)題。例如，電影可能有多個(gè)導(dǎo)演，一本書(shū)可能有多個(gè)作者。

定義7不同的數(shù)據(jù)源為同一個(gè)實(shí)體提供不同的值集，從而產(chǎn)生數(shù)據(jù)沖突。

2.2 問(wèn)題定義

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

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

本節(jié)譯述了方法細(xì)節(jié)，包括值集之間相似度的定義，多真值發(fā)現(xiàn)的框架以及相應(yīng)的算法。本節(jié)中使用的所有變量如表1所示。

表1 變量描述Tab.1 Variable description

3.1 值集之間的相似度計(jì)算

余弦相似度常用來(lái)計(jì)算文檔向量之間的相似性，將文本中的詞語(yǔ)映射到向量空間，形成文檔中詞頻與向量數(shù)據(jù)的映射關(guān)系，通過(guò)計(jì)算兩個(gè)向量之間的余弦相似度得出文檔之間的相似度。例如計(jì)算下面兩個(gè)句子的相似度：

A：“我愛(ài)母親，也愛(ài)父親”；

B：“我愛(ài)父親，更愛(ài)母親”。

首先對(duì)句子進(jìn)行分詞，得到分詞集合{我愛(ài)母親也父親更}，計(jì)算詞頻：

A：我1，愛(ài) 2，母親1，也 1，父親1，更0；

B：我1，愛(ài)2，母親1，也 0，父親1，更 1。

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

因此，本文將余弦相似度引入到值集之間的相似度計(jì)算當(dāng)中來(lái)。令向量A表示值集V的二值向量，A的長(zhǎng)度為實(shí)體可能值集V*的長(zhǎng)度，則向量A的第i個(gè)元素值為

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

通過(guò)余弦相似度來(lái)度量?jī)蓚€(gè)值向量之間的相似性為

3.2 數(shù)據(jù)源可信度計(jì)算與實(shí)體多真值發(fā)現(xiàn)

3.2.1 基本推導(dǎo)

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

實(shí)體的真實(shí)集應(yīng)該最大程度地接近沖突數(shù)據(jù)源提供的所有值集。為了找到最可能正確的真值集，結(jié)果應(yīng)該在所有數(shù)據(jù)源提供的值集中相似度達(dá)得最大。因此，提出本文多真值發(fā)現(xiàn)的目標(biāo)函數(shù)

到目前為止，已經(jīng)將多真理發(fā)現(xiàn)轉(zhuǎn)化為一個(gè)優(yōu)化問(wèn)題。根據(jù)目標(biāo)函數(shù)可以在實(shí)體的可能值集中選取置信度最高的幾個(gè)值成為真值。在多真值發(fā)現(xiàn)問(wèn)題中，實(shí)體可能值的置信度通常是不同的，置信度高的描述值會(huì)更大可能成為實(shí)體的真值。因此，本文采用一種貪心選擇策略：根據(jù)置信度的大小對(duì)實(shí)體的可能值進(jìn)行排序，然后優(yōu)先選擇高可信度的描述值作為實(shí)體的真值。

對(duì)于描述值v，通過(guò)各數(shù)據(jù)源的加權(quán)投票來(lái)計(jì)算其置信度

由式（5）得到實(shí)體每個(gè)可能值的置信度大小，從而生成置信度向量W。根據(jù)W按從大到小的順序?qū)⒖赡苤捣湃牒蜻x真值集，然后計(jì)算該真值集與實(shí)體的所有值集之間的相似度，保留相似度之和較大的真值集，最后相似度之和最大的真值集就是所求解。具體算法如算法1所示，算法的時(shí)間復(fù)雜度為O(ML)。

算法1實(shí)體真值發(fā)現(xiàn)

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

輸出：Truth

3.2.2 結(jié)合相似值的影響

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

令Z1，Z2分別表示描述值v1，v2包含的單詞集合，m，n分別表示Z1，Z2中的單詞個(gè)數(shù)，則v1對(duì)v2的支持度為

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

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

算法2相似值列表計(jì)算.

3.3 迭代計(jì)算

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

首先，為所有數(shù)據(jù)源的可信度設(shè)置初始值T0（T0為估計(jì)的平均可信度，本文設(shè)T0=0.9），然后開(kāi)始迭代計(jì)算。每次迭代分兩步：（1）使用從上一次迭代獲得的數(shù)據(jù)源可信度來(lái)計(jì)算實(shí)體的真值集；（2）使用上一次迭代獲得的真值集計(jì)算數(shù)據(jù)的源可信度。如此迭代直到算法達(dá)到穩(wěn)定狀態(tài)。穩(wěn)定狀態(tài)通過(guò)數(shù)據(jù)源可信度的變化來(lái)度量，用向量T來(lái)表示。使用余弦相似度來(lái)度量?jī)纱蔚gT的變化。如果只在迭代之后T只改變了一點(diǎn)點(diǎn)，則算法停止。

算法3算法框架.

輸入：S，E

輸出：{Truth|e∈E}

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

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

本節(jié)通過(guò)3個(gè)真實(shí)數(shù)據(jù)集比較了本文算法和現(xiàn)有的真值發(fā)現(xiàn)算法，并給出了實(shí)驗(yàn)結(jié)果。

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

4.1.1 對(duì)比算法

Voting：該方法基于投票，如果一個(gè)描述值獲得的票數(shù)占總票數(shù)的比例超過(guò)0.5，則認(rèn)為該值為真。

Truthfinder[1]：該方法能聯(lián)合推導(dǎo)數(shù)據(jù)源的可信度和值集的置信度，并考慮了不同值集之間的影響。

LTM[18]：該方法通過(guò)構(gòu)建一個(gè)概率圖模型來(lái)聯(lián)合推導(dǎo)實(shí)體描述值的置信度和數(shù)據(jù)源的可信度。

MBM[13]：該方法定義一種新的描述值之間的互相排斥，同時(shí)結(jié)合更優(yōu)的復(fù)制檢測(cè)到一個(gè)貝葉斯模型中來(lái)進(jìn)行真值發(fā)現(xiàn)。

MTD-hrd[14]：該方法通過(guò)結(jié)合兩種影響，非平衡的肯定和否定斷言的分布和描述值在同一值集共同出現(xiàn)的頻數(shù)來(lái)增強(qiáng)它的概率模型。

SmartMTD[16]：該方法通過(guò)對(duì)兩種類型的數(shù)據(jù)源關(guān)系進(jìn)行建模來(lái)計(jì)算數(shù)據(jù)源的可信度和探測(cè)數(shù)據(jù)源的惡意復(fù)制。

OptMTF：本文提出的多真值發(fā)現(xiàn)算法。

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

（1）圖書(shū)-作者數(shù)據(jù)集

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

（2）電影-導(dǎo)演數(shù)據(jù)集

從IMDB網(wǎng)站中提取了最流行的100部電影數(shù)據(jù)，包括電影和導(dǎo)演的名字。基于IMDB站點(diǎn)的權(quán)威性，將該站點(diǎn)的電影數(shù)據(jù)作為真值。然后根據(jù)選擇的電影名稱，采用了一種類似于文獻(xiàn)[1]的做法在谷歌上進(jìn)行搜索，提取了由不同站點(diǎn)提供的電影導(dǎo)演信息作為電影數(shù)據(jù)集。該數(shù)據(jù)集包括來(lái)自743個(gè)來(lái)源的403個(gè)導(dǎo)演的數(shù)據(jù)，平均每個(gè)電影有7個(gè)可能的導(dǎo)演。導(dǎo)演可能值的數(shù)量分布如圖1所示。

（3）父母-孩子數(shù)據(jù)集

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

4.1.3 度量指標(biāo)

使用3個(gè)指標(biāo)來(lái)評(píng)估算法的性能。對(duì)于所有這些指標(biāo)，較大的值表示更好的結(jié)果。

（1）精確率Precision，表示在所有實(shí)體預(yù)測(cè)的真值集合中，預(yù)測(cè)實(shí)際真值的平均百分比；

（2）召回率Recall，表示在所有實(shí)體實(shí)際的真值集合中，預(yù)測(cè)實(shí)際真值的平均百分比；

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

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

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

本節(jié)實(shí)驗(yàn)硬件環(huán)境為4 GB內(nèi)存,2.5 GHz Intel Core i5處理器和Windows 10操作系統(tǒng)。本文用JAVA語(yǔ)言實(shí)現(xiàn)了所有比較算法。

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

4.2.1 對(duì)比現(xiàn)有的真值發(fā)現(xiàn)算法

表2展示了不同算法在3個(gè)真實(shí)數(shù)據(jù)集上準(zhǔn)確度、召回率和的表現(xiàn)，已被加粗的是最優(yōu)的結(jié)果?？梢钥吹剑瑢?duì)比現(xiàn)有的真值發(fā)現(xiàn)算法，本文算法的F-score始終能達(dá)到最好的結(jié)果。由于在圖書(shū)數(shù)據(jù)集和父母數(shù)據(jù)集上消除了少量沖突的記錄，所有算法在這兩個(gè)數(shù)據(jù)集上準(zhǔn)確度較低。同時(shí)，由于電影數(shù)據(jù)集的記錄比其他兩個(gè)數(shù)據(jù)集多，所有算法在電影數(shù)據(jù)集上運(yùn)行的時(shí)間較長(zhǎng)。

Voting算法在3個(gè)數(shù)據(jù)集上準(zhǔn)確度較高，它的召回率是最低的，同時(shí)該算法的運(yùn)行時(shí)間是最低的。這是因?yàn)榇蠖鄶?shù)數(shù)據(jù)源只提供了小部分的完整真值集，同時(shí)Voting算法沒(méi)有考慮數(shù)據(jù)源的可信度，可信度高的數(shù)據(jù)源提供的值沒(méi)有得到更多的權(quán)重，因此降低了召回率。

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

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

除本文算法之外，MBM算法和SmartMTD算法跟其他算法相比也有較好的表現(xiàn)，這是因?yàn)榭紤]了數(shù)據(jù)源的否定斷言，從而提高真值發(fā)現(xiàn)的準(zhǔn)確率。雖然MTD-hrd算法和LTM算法也考慮了這層含義，但它們對(duì)潛在變量的先驗(yàn)分布做出了很強(qiáng)的假設(shè)。如果數(shù)據(jù)集不符合假設(shè)的分布，那么算法的表現(xiàn)將會(huì)很差。然而，現(xiàn)有的多真值發(fā)現(xiàn)算法沒(méi)有考慮值的不同表現(xiàn)形式，本文算法結(jié)合相似值對(duì)真值的影響來(lái)提高描述值置信度的計(jì)算精度，同時(shí)根據(jù)所提的目標(biāo)函數(shù)選取可信度較高的描述值作為實(shí)體的真值，無(wú)需對(duì)數(shù)據(jù)源做出先驗(yàn)假設(shè)，因此OptMTF算法實(shí)現(xiàn)了更高的準(zhǔn)確度。

4.2.2 相似值的影響

為了評(píng)估相似值的影響和結(jié)合相似值計(jì)算的重要性，實(shí)現(xiàn)了本文算法（即OptMTF）的另一個(gè)版本用于比較。

OptMTF-s：OptMTF的另一個(gè)版本，它沒(méi)有考慮相似值對(duì)模型的影響。

圖2展示了兩種實(shí)現(xiàn)方法在電影數(shù)據(jù)集上的比較。可以看到，OptMTF的準(zhǔn)確度和召回率明顯高于OptMTF-s，盡管其執(zhí)行時(shí)間稍長(zhǎng)點(diǎn)。圖3顯示了兩種方法在電影數(shù)據(jù)集上的迭代，這兩種方法都可以在幾次迭代之后達(dá)到收斂。這些數(shù)據(jù)證明了結(jié)合相似值支持的正確性。在現(xiàn)實(shí)中，同一個(gè)值具有不同表現(xiàn)形式的情況是很常見(jiàn)的。表3中列出了圖書(shū)“Rapid Contextual Design”(ISBN：0123540518)的作者的相似值。現(xiàn)有的多真值發(fā)現(xiàn)算法認(rèn)為它們是錯(cuò)誤的值，但它們并不是完全錯(cuò)誤的。它們通常是因?yàn)樾畔⒉煌暾蛉鄙倌承┎糠衷斐傻?，結(jié)合它們的支持能夠提高真值發(fā)現(xiàn)的準(zhǔn)確性。特別是采用非對(duì)稱的方法來(lái)計(jì)算值之間的支持度，使得完整值（即包含其他值）將獲得更高的支持度，它們會(huì)比其他值更優(yōu)先被選為真值。例如，當(dāng)“Jessamyn Burns Wendell”被加入真值集時(shí)，根據(jù)對(duì)目標(biāo)函數(shù)的計(jì)算，它的相似值“Jessamyn Wendell”幾乎不可能被加入真值集，即使該值的調(diào)和置信度和真值很接近，通過(guò)這種方法可以得到更準(zhǔn)確的真值結(jié)果。

圖2 兩種方法在電影數(shù)據(jù)集上的對(duì)比Fig.2 Comparison of two methods on movie dataset

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

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

在數(shù)據(jù)集成系統(tǒng)中，從沖突數(shù)據(jù)中找到正確的信息是至關(guān)重要的。本文提出了一個(gè)多真值發(fā)現(xiàn)算法OptMTF。該算法將多真值發(fā)現(xiàn)轉(zhuǎn)化為一個(gè)函數(shù)優(yōu)化問(wèn)題，其目標(biāo)是實(shí)體的真值集應(yīng)該與數(shù)據(jù)源對(duì)該實(shí)體提供的所有值集之間相似度最高。根據(jù)目標(biāo)函數(shù)對(duì)真值的選擇，設(shè)計(jì)了一個(gè)迭代算法來(lái)聯(lián)合推到數(shù)據(jù)源的可信度和實(shí)體的真值集，同時(shí)，考慮值不同表現(xiàn)形式的影響，結(jié)合相似值的支持來(lái)計(jì)算描述值的置信度，達(dá)到更好的真值發(fā)現(xiàn)效果。最后通過(guò)3個(gè)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明本文算法的有效性。

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