陳烈鋒 許青林

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

引 言

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

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

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

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

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

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

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

1 文獻(xiàn)綜述

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

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

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

2 問題描述

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

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

2.1 相關(guān)定義

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

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

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

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

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

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

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

2.2 問題定義

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

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

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

表1 變量描述Tab.1 Variable description

3.1 值集之間的相似度計算

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

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

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

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

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)。通過計算兩個向量的余弦相似度即可得兩個句子的相似度。

因此，本文將余弦相似度引入到值集之間的相似度計算當(dāng)中來。令向量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 數(shù)據(jù)源可信度計算與實體多真值發(fā)現(xiàn)

3.2.1 基本推導(dǎo)

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

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

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

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

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

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

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

輸出：Truth

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

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

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

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

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

算法2相似值列表計算.

3.3 迭代計算

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

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

算法3算法框架.

輸入：S，E

輸出：{Truth|e∈E}

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

4 實 驗

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

4.1 實驗設(shè)計

4.1.1 對比算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1.3 度量指標(biāo)

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

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

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

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

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

4.1.4 實驗環(huán)境

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

4.2 實驗結(jié)果

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

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

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

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

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

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

4.2.2 相似值的影響

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

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

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

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

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

5 結(jié)束語

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

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