利用屬性集相關(guān)性與源誤差的多真值發(fā)現(xiàn)方法研究

盧 菁,胡 成,劉 叢

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海 200093)

1 引 言

Web正在以前所未有的速度增長.隨著電子商務(wù)和社會媒體的快速發(fā)展,越來越多的用戶和應(yīng)用依賴于在線數(shù)據(jù)作為信息需求的主要資源.然而Web數(shù)據(jù)不是完全正確的,來源往往會提供錯誤的或相互矛盾的信息.如表1所示,在線書商對于《社會計算:社區(qū)發(fā)現(xiàn)和社會媒體挖掘》一書的作者列表提供了不一致的信息.

表1 各網(wǎng)站提供的作者信息
Table 1 Author information provided by websites

數(shù)據(jù)源作者列表當(dāng)當(dāng)唐磊,文益民,閉應(yīng)洲京東唐磊華章圖書唐磊,劉歡一號店文益民

其中,華章圖書提供了正確并且完整的作者列表,京東提供了正確但不完整的作者列表,當(dāng)當(dāng)提供的作者列表中一部分是錯誤的,而一號店則提供了完全錯誤的作者列表.可以發(fā)現(xiàn),不同網(wǎng)站為同一書籍的作者提供了大量的沖突數(shù)據(jù).我們將從不同的、相互沖突的來源獲得最完整和準(zhǔn)確的合并記錄稱為多真值發(fā)現(xiàn)問題.

當(dāng)前研究主要集中于單真值發(fā)現(xiàn)問題上,文獻[1]首次提出并定義了真值發(fā)現(xiàn)問題,基于事實和數(shù)據(jù)源之間相互依賴的關(guān)系提出了一種基于迭代機制聯(lián)合推導(dǎo)數(shù)據(jù)源質(zhì)量和真值的可信度算法TruthFinder,并且用相似度度量事實之間的相互影響.文獻[2]通過將用戶已知的特定事實轉(zhuǎn)化為約束條件,對數(shù)據(jù)集進行檢索提出了Investment等算法.文獻[3]提出了一種概率數(shù)據(jù)模型,考慮事實的難易程度,避免數(shù)據(jù)源從相對容易的事實獲得過高的可信度分值.文獻[1-3]考慮影響真值發(fā)現(xiàn)的各種因素,但均忽略了數(shù)據(jù)源間存在相互依賴的關(guān)系.文獻[4]通過檢測數(shù)據(jù)源提供錯誤數(shù)據(jù)的冗余程度來處理數(shù)據(jù)源間的復(fù)制關(guān)系,提出的算法能捕獲到兩兩數(shù)據(jù)源間的一階復(fù)制,但處理相互復(fù)制、傳遞復(fù)制時,準(zhǔn)確率會降低.文獻[5]通過觀察數(shù)據(jù)源聯(lián)合召回率和聯(lián)合假真率來處理相互復(fù)制和傳遞復(fù)制,但僅考慮了數(shù)據(jù)復(fù)制導(dǎo)致虛假數(shù)據(jù)間的正相關(guān),無法處理正確數(shù)據(jù)間的負(fù)相關(guān).文獻[6]認(rèn)為基于提取器提取規(guī)則的不同,對比在源獨立條件和源相關(guān)條件下,聯(lián)合召回率與聯(lián)合假真率的比值,提出了PrecRec和PrecRecCorr算法.文獻[7]提出同一數(shù)據(jù)源提供的不同類別數(shù)據(jù)應(yīng)該具有不同的可信度分值,提出了CTruthFinder算法.文獻[8]提出一種圖概率模型LTM,利用假陽性和假陰性,對數(shù)據(jù)源兩個方面進行建模,可自動推斷真實數(shù)據(jù)和源質(zhì)量.缺陷是數(shù)據(jù)必須符合Beta分布,否則效率將下降.文獻[9]認(rèn)為對象的真值與數(shù)據(jù)源提供的觀察值間相似性加權(quán)和達到最大時可直接得到真值列表.文獻[4-9]均忽略了數(shù)據(jù)源質(zhì)量評估的有效性受到數(shù)據(jù)源提供事實總數(shù)的影響,當(dāng)數(shù)據(jù)源僅提供少量事實時,算法對數(shù)據(jù)源質(zhì)量評估不準(zhǔn)確.數(shù)據(jù)源提供的事實數(shù)量差異很大,少數(shù)大規(guī)模數(shù)據(jù)源提供大量的信息,信息分布呈長尾現(xiàn)象.文獻[10]提出一種加權(quán)聚合框架,將多個數(shù)據(jù)源提供事實的加權(quán)組合建模為真值,通過解決優(yōu)化問題尋求數(shù)據(jù)源權(quán)重的最佳分配,降低事實數(shù)量對數(shù)據(jù)源評估的影響.然而文獻[10]僅能處理數(shù)值類型的單真值發(fā)現(xiàn)問題,對于非數(shù)值類型的多真值發(fā)現(xiàn)問題未見探討.

針對以上問題,本文首先根據(jù)信息量對數(shù)據(jù)源進行分類.對于頭部數(shù)據(jù)源,通過屬性集相關(guān)性給予相應(yīng)屬性集置信度補償,易于區(qū)別正確和錯誤數(shù)據(jù),發(fā)現(xiàn)潛在的真值集合.對于尾部數(shù)據(jù)源,通過源誤差衡量源的可靠程度,誤差小的數(shù)據(jù)源獲得更高的權(quán)值分配,將真值發(fā)現(xiàn)問題轉(zhuǎn)化為一個全局優(yōu)化問題,找到最佳的權(quán)值分配后,得到最接近真實事實的真值集合.本文貢獻如下:

1)通過信息量的概念衡量數(shù)據(jù)源的規(guī)模,對數(shù)據(jù)源進行分類.提出屬性集值向量的概念,描述數(shù)據(jù)源為對象提供的多個屬性值分布情況;

2)針對頭部數(shù)據(jù)源提供的屬性集,利用屬性集值向量間的相關(guān)性,給予相互支持以及互補的正確屬性集更多置信度補償,提出了迭代計算數(shù)據(jù)源可信度以及屬性集置信度的多真值發(fā)現(xiàn)算法MTDAC(Multi-truth Discovery by Attribute Correlation);

3)對尾部數(shù)據(jù)源,利用數(shù)據(jù)源誤差來反映數(shù)據(jù)源的可靠程度,將真值發(fā)現(xiàn)問題轉(zhuǎn)化為一個全局優(yōu)化問題,提出了迭代計算數(shù)據(jù)源的權(quán)重值以及對象真值集合的多真值發(fā)現(xiàn)算法MTDSE(Multi-truth Discovery By Source Error);

4)在實際數(shù)據(jù)集上的實驗證明了本文算法的有效性.

2 系統(tǒng)框架

2.1 相關(guān)概念

定義1.對象可能值集V*,j:所有數(shù)據(jù)源對于某個對象的特定屬性提供的所有屬性值集合.例如,如表1所示,《社會計算社區(qū)發(fā)現(xiàn)和社會媒體挖掘》的作者列表可能值集是{唐磊,文益民,閉應(yīng)洲,劉歡}.

定義2.屬性集值向量vi,j:二值向量.數(shù)據(jù)源提供關(guān)于某個對象的觀察值在對象可能值集上的分布情況.表示數(shù)據(jù)源si為對象oj提供的值向量.向量長度為該對象可能值集的長度,如果數(shù)據(jù)源提供了對象可能值集上的第i個屬性值,那么該對象向量值的第i個元素設(shè)置為1,否則為0.

定義3.數(shù)據(jù)源信息量P(si):表示數(shù)據(jù)源提供的屬性集個數(shù)占數(shù)據(jù)集中全部屬性集的百分比,如公式(1)所示:

(1)

其中,m表示實際數(shù)據(jù)集中數(shù)據(jù)源的總個數(shù),|O(si)|表示數(shù)據(jù)源si提供的屬性集個數(shù).對所有數(shù)據(jù)源的P(si)由大到小排序,根據(jù)二八法則,當(dāng)規(guī)模較大數(shù)據(jù)源組成的集合提供信息量占比超過數(shù)據(jù)集信息量80%時,該集合中的數(shù)據(jù)源為頭部數(shù)據(jù)源,其余為尾部數(shù)據(jù)源.

2.2 系統(tǒng)架構(gòu)圖

本文系統(tǒng)架構(gòu)圖如圖1所示,通過以下七個步驟發(fā)現(xiàn)真值集合:

圖1 系統(tǒng)總體框架Fig.1 General system frame

1.對數(shù)據(jù)集進行預(yù)處理,根據(jù)數(shù)據(jù)量對數(shù)據(jù)源進行分類.頭部數(shù)據(jù)源執(zhí)行步驟(2),尾部數(shù)據(jù)源執(zhí)行步驟(5).

2.初始化數(shù)據(jù)源可信度T(s)及相關(guān)參數(shù),計算屬性集的置信度A*(v).

3.根據(jù)A*(v),重新計算數(shù)據(jù)源可信度T(s).

3基于屬性集相關(guān)性的多真值發(fā)現(xiàn)方法(MTDAC)

3.1 頭部數(shù)據(jù)源的可信度計算

定義T(si)為頭部數(shù)據(jù)源si的可信度,A(vi,j)為數(shù)據(jù)源si為對象oi提供屬性集的置信度,T(si)可通過計算該頭部數(shù)據(jù)源si提供的所有屬性集置信度均值來表示.如公式(2)所示:

(2)

其中,NSi表示由數(shù)據(jù)源si提供的所有屬性集,|NSi|表示數(shù)據(jù)源si提供屬性集的總數(shù)量.

3.2 屬性集的置信度計算

如圖2所示,一個屬性集合的置信度應(yīng)該由提供它的頭部數(shù)據(jù)源以及關(guān)于相同對象的其他屬性集合來確定.假設(shè)s1和s2相互獨立,分析沒有相關(guān)事實的簡單情況,V1是關(guān)于對象o1的唯一屬性集.其置信度A(vi,1)可以計算為:

(3)

圖2 屬性間的相互影響Fig.2 Influences among attribute sets

W(V1)表示提供屬性集V1的數(shù)據(jù)源集合.

1-T(si)的值很小,可能會導(dǎo)致下溢.為了方便計算,使用對數(shù)重新定義了屬性集的置信度:

σ(vi,1)=
-ln(1-A(vi,1))

(4)

3.3 屬性集間的相關(guān)性

數(shù)據(jù)源s3提供的屬性集V3與V1相似,則說它們是正相關(guān)的,如果V3是由許多高可信度數(shù)據(jù)源提供,V1應(yīng)該得到置信度評分補償.本文采用了包含信息缺失的相似性計算方法,即數(shù)據(jù)源提供的屬性集都不包含某特定屬性,那么它們之間也是存在相似性的.假設(shè)圖2中,三個屬性集值向量分別為v1,1(1,0,1,0,0),v3,1(1,0,1,0,1),v4,1(1,1,1,1,0),信息檢索中采用兩向量之間的內(nèi)積來計算相似性,v1,1,v3,1,v4,1兩兩之間的內(nèi)積都為2,但顯然v1,1與v3,1之間更相似.

文獻[12]定義包含信息缺失的相似性計算方法:

(5)

根據(jù)圖2,考慮屬性集間的正相關(guān)性以及對相似性計算方法的優(yōu)化,定義正相關(guān)檢測函數(shù),給予置信度評分補償:

(6)

ρ是正相關(guān)因子控制屬性集互相影響的參數(shù),ρ的取值越大,正相關(guān)的屬性集間會獲得更多置信度評分補償.

數(shù)據(jù)源提供包含錯誤信息的屬性集之間有很大不同,它們之間相似性不會很高.包含錯誤信息的屬性集,它們組成的集合在所有屬性集中占比會很低.假設(shè)在表1中,京東提供的作者信息為唐磊,當(dāng)當(dāng)提供的為劉歡.兩數(shù)據(jù)源都提供了包含部分正確信息的屬性集,但它們的屬性集值向量是負(fù)相關(guān)的.提供正確信息的屬性集組成的集合在所有屬性集中占比不低.設(shè)置負(fù)相關(guān)相似性閾值α,判斷屬性集是否屬于同一集合,當(dāng)sim(vi,j,vn,j)大于α?xí)r,函數(shù)f(x)取值為1,否則為0,統(tǒng)計該集合中屬性集個數(shù).觀察此集合在所有屬性集中所占比例,給予相應(yīng)置信度評分補償.定義負(fù)相關(guān)檢測函數(shù),如公式(7)所示:

(7)

γ是負(fù)相關(guān)因子,控制屬性集集合數(shù)目對置信度評分的影響.|Oj|表示所有數(shù)據(jù)源為對象Oj提供的屬性集總數(shù).

結(jié)合φ(vi,j)對屬性集的置信度公式(4)進行改進:

σ*(vi,j)=σ(vi,j)+ω(vi,j)+φ(vi,j)

(8)

3.4 基于屬性集相關(guān)性的多真值發(fā)現(xiàn)算法(MTDAC)

算法1.基于屬性集相關(guān)性的多真值發(fā)現(xiàn)算法(MTDAC).

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

輸出:真值集合X={n,v*,n|n∈O};

1.相關(guān)參數(shù)的初始化;

2.FOR EACH Si∈S

3. T(Si)←T0;

5. FOR EACH oj∈O

6.根據(jù)數(shù)據(jù)源si為對象oj屬性值提供情況,初始化屬性集值向量vi,j;

7. 根據(jù)式(8)計算屬性集的置信度評分;

8. 根據(jù)式(2)重新計算數(shù)據(jù)源的可信度評分;

12. RETURN真值集合X{n,v*,n|n∈O}.

4基于源誤差的多真值發(fā)現(xiàn)方法(MTDSE)

4.1 數(shù)據(jù)源的誤差

本文使用文獻[10]中源誤差的概念融合屬性集值向的概念,處理包含數(shù)值、字符串類型的多真值發(fā)現(xiàn)問題.屬性集值向量v*,n表示對象n的真值集合,定義如下:

(9)

當(dāng)找到TSi權(quán)重最優(yōu)分配時,v*,n為最為可能接近對象的真值集合.我們使用數(shù)據(jù)源提供的所有信息與初始化真值之間的差異作為數(shù)據(jù)源的誤差,定義如下:

(10)

4.2 數(shù)據(jù)源權(quán)值的最佳分配

誤差反映了數(shù)據(jù)源的可靠程度,誤差小的高質(zhì)量數(shù)據(jù)源應(yīng)該獲得更高的權(quán)重分配[11].權(quán)重的最佳分配可轉(zhuǎn)化為全局優(yōu)化問題,在所有數(shù)據(jù)源權(quán)重值和為1的條件下,尋求目標(biāo)函數(shù)g(TSi)的最小值:

目標(biāo)函數(shù)是凸函數(shù)的線性組合,因此目標(biāo)函數(shù)也為凸函數(shù),定能找到最優(yōu)解使得目標(biāo)函數(shù)取得最小值.在保證全局優(yōu)化問題取值最小的前提下,可以找到最佳的權(quán)重分配:

(11)

算法2.基于源誤差的長尾數(shù)據(jù)多真值發(fā)現(xiàn)算法(MTDSE)

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

輸出:真值集合X={n,v*,n|n∈O};

2.FOR EACH si∈S;

6.REPEAT

8. 根據(jù)等式(9)結(jié)合源的權(quán)重值TSi重新計算v*,n;

13. RETURN真值集合X{n,v*,n|n∈O}.

5 合并策略與綜合輸出

6 實驗結(jié)果與分析

6.1 實驗環(huán)境

本節(jié)所有實驗硬件環(huán)境為:Intel? CoreTMi7-6700HQ 2.60GHz處理器、8G內(nèi)存、Windows8操作系統(tǒng).本文所有算法包括對比算法均使用Java語言實現(xiàn),JKD版本為JDK6.0,數(shù)據(jù)庫系統(tǒng)采用MySQL5.5.

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

本文采用的數(shù)據(jù)集是通過爬蟲程序獲取的圖書作者數(shù)據(jù)集,該數(shù)據(jù)集包括書名、ISBN、圖書銷售網(wǎng)站(數(shù)據(jù)源)、作者列表.利用信息量進行計算,對數(shù)據(jù)源進行分類.京東圖書等47個頭部數(shù)據(jù)源提供的信息量為80.8%,微店等403個尾部數(shù)據(jù)源提供的信息量為19.2%.我們對原始數(shù)據(jù)集進行去重處理,并對作者列表的格式進行了統(tǒng)一的修復(fù),避免因格式不一致導(dǎo)致的數(shù)據(jù)檢測問題.經(jīng)預(yù)處理后,數(shù)據(jù)集包含了2245本圖書、450個圖書銷售網(wǎng)站(數(shù)據(jù)源)、8829條作者信息、22972條沖突數(shù)據(jù)記錄.我們還隨機選擇100本圖書,搜索該100本圖書的封面作者信息,對該100本圖書的作者列表進行手工校準(zhǔn),作為標(biāo)準(zhǔn)集.

6.3 評價指標(biāo)

6.4 參數(shù)對算法的影響

對MTDAC算法中參數(shù)初始化進行討論,如圖3(a)所示,正相關(guān)因子ρ>0.1時,對算法的準(zhǔn)確率影響很小,算法的F-Score波動范圍不超過5%,因為在大多數(shù)真實數(shù)據(jù)集中正確數(shù)據(jù)的占比要高于錯誤數(shù)據(jù),且數(shù)據(jù)源提供的正確數(shù)據(jù)大都是相同或者相似的.正相關(guān)因子ρ=0.5時,算法的表現(xiàn)最佳,設(shè)置ρ=0.5.在正相關(guān)因子ρ不變的情況下,不斷調(diào)整負(fù)相關(guān)因子γ的值,觀察MTDAC算法的準(zhǔn)確率變化,實驗結(jié)果如圖3(b)所示.隨著γ不斷增加,算法對負(fù)相關(guān)數(shù)據(jù)的敏感程度提高,算法的準(zhǔn)確率也呈現(xiàn)遞增的趨勢.γ=0.7時,MTDAC算法在圖書作者數(shù)據(jù)集上得到最佳表現(xiàn),準(zhǔn)確率為0.811.γ在區(qū)間(0.7,0.9]時,對負(fù)相關(guān)數(shù)據(jù)的敏感程度過高,錯誤數(shù)據(jù)的置信度評分也得到一定提高,引入了錯誤數(shù)據(jù),導(dǎo)致算法的準(zhǔn)確率降低.

圖3 參數(shù)對MTDAC算法準(zhǔn)確率的影響Fig.3 Influence of parameters on the accuracy of MTDAC

其次,觀察不同的參數(shù)取值對算法召回率的影響,實驗結(jié)果如圖4(a)所示,在區(qū)間(0.1,0.5]上,隨著正相關(guān)因子ρ不斷增加,算法的召回率呈快速上升趨勢.因為通過正相關(guān)檢測函數(shù),提供包含部分正確信息的屬性集會得到置信度評分補償,利于MTDAC算法發(fā)現(xiàn)更加完整的真值集合.在正相關(guān)因子ρ不變的情況下,調(diào)整負(fù)相關(guān)因子γ的值,觀察算法召回率的變化,實驗結(jié)果如圖4(b)所示,在區(qū)間(0.5,0.9]上時,算法的召回率波動范圍不超過6%,在γ=0.75時,算法的召回率達到峰值.因為存在負(fù)相關(guān)的屬性集集合在所有屬性集中占比較低,樣本數(shù)目少,負(fù)相關(guān)檢測函數(shù)給予的置信度補償相對較低.因此,負(fù)相關(guān)因子γ對算法的召回率影響很小.結(jié)合圖3在保證算法準(zhǔn)確率的同時,獲得相對較高的召回率,初始化ρ=0.5,γ=0.7.

圖4 參數(shù)對MTDAC算法召回率的影響Fig.4 Influence of parameters on the recall of MTDAC

最后,分別在參數(shù)ρ、γ取得最優(yōu)值的情況下,觀察參數(shù)對算法F1的影響,實驗結(jié)果如圖5所示,在ρ=0.5,γ=0.7時,算法的綜合表現(xiàn)最佳,F1=0.806.

圖5 參數(shù)對MTDAC算法綜合表現(xiàn)的影響Fig.5 Influence of parameters on the F1 of MTDAC

6.5 MTDAC、MTDSE與傳統(tǒng)算法的對比

本文設(shè)置閾值K=0.5,即屬性值為真的概率大于0.5時,該屬性值為真值.首先觀察各算法對頭部數(shù)據(jù)源提供的事實,各算法的表現(xiàn)如圖6(a)所示.基準(zhǔn)算法Voting的查全率明顯低于其他算法,TruthFinder算法查全率較高,但準(zhǔn)確率較低,導(dǎo)致F-Score并不高.MTDAC算法考慮了屬性集間更為復(fù)雜的相關(guān)性,算法的準(zhǔn)確率比MTruths算法高出2.5%,算法的綜合表現(xiàn)優(yōu)于其它算法.

圖6 算法在頭尾數(shù)據(jù)源上的綜合表現(xiàn)Fig.6 Algorithm performance on head and tail data sources

其次,觀察各算法針對尾部數(shù)據(jù)源提供的事實,各算法的表現(xiàn)如圖6(b)所示.由于數(shù)據(jù)量小,屬性集間關(guān)系稀疏,各算法的綜合表現(xiàn)都有明顯下降,Voting算法下降幅度達到12%,其余算法的綜合表現(xiàn)降低了7%到9%之間.MTDSE算法在處理尾部數(shù)據(jù)源提供的信息時,算法的綜合表現(xiàn)要優(yōu)于各對比算法.由此可見,傳統(tǒng)算法在處理尾部數(shù)據(jù)源提供的事實時,得到的真值集合往往不是準(zhǔn)確的.

圖7 算法在完整數(shù)據(jù)集上的綜合表現(xiàn)Fig.7 Algorithm performance on complete data set

最后,觀察各算法以及同時使用MTDAC算法和MTDSE算法在完整的圖書作者數(shù)據(jù)集上的表現(xiàn),結(jié)果如圖7所示.兩種算法的結(jié)合使用獲得了最佳表現(xiàn),傳統(tǒng)算法由于沒有考慮實際數(shù)據(jù)集中事實對象在數(shù)據(jù)源上的分布可能呈現(xiàn)長尾現(xiàn)象,對數(shù)據(jù)源進行統(tǒng)一處理,導(dǎo)致算法的綜合表現(xiàn)不佳.

實驗證明了本文提出的基于屬性集相關(guān)性和源誤差的多真值發(fā)現(xiàn)方法的有效性,較傳統(tǒng)真值發(fā)現(xiàn)算法在真實的長尾數(shù)據(jù)集上的表現(xiàn)有顯著提升.

7 結(jié)束語

本文首先利用信息量衡量數(shù)據(jù)源的規(guī)模,對數(shù)據(jù)源進行分類.針對頭部數(shù)據(jù)源提供的屬性集,利用相關(guān)性給予相應(yīng)屬性集置信度補償,提高了真值發(fā)現(xiàn)的準(zhǔn)確率,提出了基于屬性集相關(guān)性的多真值發(fā)現(xiàn)算法MTDAC.針對尾部數(shù)據(jù)源,利用源誤差的概念,將真值發(fā)現(xiàn)問題轉(zhuǎn)化為一個全局優(yōu)化問題,降低事實數(shù)量對數(shù)據(jù)源評估的影響,提出了多真值發(fā)現(xiàn)算法MTDSE.通過合并策略對兩算法執(zhí)行后得到的真值集合進行合并,作為綜合輸出.最后,通過實驗驗證了本文算法的有效性.在未來的工作中,針對動態(tài)變化的數(shù)據(jù)集,將致力于真值發(fā)現(xiàn)的時效性研究,提高算法的綜合性能.