貝葉斯沖突Web數(shù)據(jù)可信度算法

王繼奎

(蘭州財經(jīng)大學(xué) 電子商務(wù)綜合重點(diǎn)實驗室,甘肅 蘭州 730020)

?

貝葉斯沖突Web數(shù)據(jù)可信度算法

王繼奎

(蘭州財經(jīng)大學(xué) 電子商務(wù)綜合重點(diǎn)實驗室,甘肅 蘭州 730020)

Web數(shù)據(jù)融合的關(guān)鍵是判定沖突Web數(shù)據(jù)的可信度.已有算法只采用觀察值之間的相似關(guān)系而忽視包含關(guān)系對可信度進(jìn)行修正,針對這一問題,在分析觀察值本身特性的基礎(chǔ)上定義觀察值包含度,提出利用觀察值包含度對觀察值可信度進(jìn)行修正的模型.將觀察值看作隨機(jī)變量,觀察值的可信度問題可歸結(jié)為觀察值的后驗概率分布問題.在貝葉斯分析的基礎(chǔ)上,定義數(shù)據(jù)源可信度,推導(dǎo)出數(shù)據(jù)源可信度與觀察值可信度之間的關(guān)系模型；并提出基于貝葉斯理論的沖突Web數(shù)據(jù)可信度算法DataCredibility.實驗結(jié)果表明,與基準(zhǔn)算法相比,DataCredibility獲得了更高的精確度、召回率及F1測度值.

沖突Web 數(shù)據(jù); 貝葉斯理論; 可信度；數(shù)據(jù)融合; DataCredibility

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展,Web已經(jīng)成為一個巨大的、分布廣泛的和全球化的信息中心[1].目前整個Web有超過200 000TB的信息量,而且仍在快速地增長[2].2004年4月,UIUC大學(xué)推測出整個Web上大約有45.0萬個Web數(shù)據(jù)庫以及30.7萬個有數(shù)據(jù)庫的站點(diǎn)[3].依據(jù)文獻(xiàn)[4]的調(diào)查,美國的消費(fèi)者對網(wǎng)上信息的信任度很低,甚至連可信度最高的網(wǎng)上資源、公司網(wǎng)站也僅有22%的美國人信任.Dalvi等[5]研究了Web上數(shù)據(jù)的冗余問題,但是沒有考慮數(shù)據(jù)的一致性問題.Li等[6]對股票與機(jī)票兩個領(lǐng)域的數(shù)據(jù)一致性進(jìn)行了研究,結(jié)果表明：70%的實體有不止一個值,大部分是由于各種歧義造成的；而其中的30%看起來是完全錯誤的.

如何確定Web數(shù)據(jù)的可信度成為研究的焦點(diǎn)問題,研究者針對這一問題進(jìn)行了大量的研究.Yin等[7]首次將從多個沖突值中選擇一個作為真值的沖突解決策略稱為真值發(fā)現(xiàn)問題,并提出基準(zhǔn)算法TruthFinder,觀察值的可信度取決于其相關(guān)數(shù)據(jù)源的可信度,而數(shù)據(jù)源的可信度取決于其提供的觀察值的可信度,利用兩者關(guān)系迭代計算,直到算法收斂,或者達(dá)到迭代次數(shù)閾值.同時,TruthFinder也考慮了觀察值之間的相似關(guān)系,并通過觀察值之間的相似關(guān)系修正觀察值的可信度.Galland等[8]在TruthFinder的基礎(chǔ)上提出了Cosine、2-Estimates和3-Estimates算法、NormalizedSources算法.Cosine算法利用觀察值與真值之間的余弦相似度度量觀察值的可信度,將觀察值的數(shù)據(jù)源的平均可信度作為觀察值的可信度,將可信度最高的作為真值.2-Estimates和3-Estimates算法使用了數(shù)據(jù)源的錯誤率與觀察值的真值2個估計器,2-Estimates迭代地計算了真值的可信度以及數(shù)據(jù)源提供錯誤觀察值的概率.真值的可信度通過提供真值的數(shù)據(jù)源的可信度(1-錯誤率)計算.3-Estimates算法在2-Estimates的基礎(chǔ)上考慮了觀察值的獲取難度.NormalizedSources算法則考慮了數(shù)據(jù)源提供觀察值數(shù)量的情況.Pasternack等[9]提出了一個考慮先驗概率的真值發(fā)現(xiàn)算法框架.J?sang等[10]研究了數(shù)據(jù)源信任傳播的機(jī)制.張志強(qiáng)等[11]在文獻(xiàn)[7]的基礎(chǔ)上改進(jìn)了數(shù)據(jù)源權(quán)威度評價方法.張永新等[12]根據(jù)所有觀察值的離散程度分兩階段處理.Zhao等[13]基于貝葉斯理論提出了將真值發(fā)現(xiàn)問題歸結(jié)為參數(shù)估計問題,提出了一種多真值發(fā)現(xiàn)算法.Ravali等[14]考慮了數(shù)據(jù)源的相關(guān)性,并將之應(yīng)用在真值發(fā)現(xiàn)中.Li等[15]提出了一種基于數(shù)據(jù)源可信度置信區(qū)間的真值發(fā)現(xiàn)算法.這些工作主要從數(shù)據(jù)源與觀察值之間的結(jié)構(gòu)關(guān)系進(jìn)行研究,對于觀察值之間的關(guān)系研究甚少.

針對已有算法只采用觀察值之間相似關(guān)系而忽視包含關(guān)系對可信度進(jìn)行修正這一問題,本文利用數(shù)據(jù)源精確度定義數(shù)據(jù)源可信度,推導(dǎo)出數(shù)據(jù)源可信度與觀察值可信度之間的關(guān)系模型；定義觀察值包含度,提出利用觀察值包含度對觀察值可信度進(jìn)行修正的模型,在此基礎(chǔ)上提出基于貝葉斯的沖突Web數(shù)據(jù)可信度算法DataCredibility,并在通用數(shù)據(jù)集Books-Authors上進(jìn)行實驗.

1 數(shù)據(jù)可信度問題的定義

為簡化討論,假設(shè)實體只有1個屬性,并假設(shè)只有1個屬性真值.

令W={w1,w2,…,wn},W表示數(shù)據(jù)源集合,用i表示標(biāo)號為i的數(shù)據(jù)源.

令E={o1,o2,…,ol},E表示觀察的集合,oj,j∈[1,l]表示標(biāo)號為j的觀察,用v(oj)表示觀察值,e(v(oj))表示被觀察對象,s(oj)表示提供觀察oj的數(shù)據(jù)源.

設(shè)離散隨機(jī)變量X∈{x1,x2,…,xn}代表可能觀察值,其中有1個真值,n-1個錯誤值.p(X=x)表示X在取值空間上的先驗概率分布.

(1)

假設(shè)數(shù)據(jù)源提供不同錯誤觀察值的概率符合均勻分布,則

(2)

式中：a為數(shù)據(jù)源的精確度,用數(shù)據(jù)源提供觀察值v(o)=x的條件概率表示.

同時,數(shù)據(jù)源的精確度也可以用其提供的觀察值為真值的概率的算術(shù)平均值表示,即

(3)

式中：m為數(shù)據(jù)源提供的觀察值個數(shù),vk(o)為數(shù)據(jù)源提供的第k個觀察值.

(4)

由于各數(shù)據(jù)源獨(dú)立提供觀察值,可得

(5)

式中：Wo(x)為觀察值為x的數(shù)據(jù)源集合,Wo為所有提供觀察值的數(shù)據(jù)源集合.

由貝葉斯公式及式(1)、(2)、(5)可得

(6)

因此,

定義1 數(shù)據(jù)源的可信度：

(7)

式中：q為數(shù)據(jù)源可信度,即q由數(shù)據(jù)源提供真值的概率與提供錯誤值的概率的比值決定.

1)當(dāng)a=0.5時,數(shù)據(jù)源未提供有利于判斷真值的觀察值,則q=0.即一個人說的話正確與錯誤的概率相等,那么這個人就沒有任何可信度,其提供的證據(jù)也沒有任何價值.

2)當(dāng)a>0.5時,數(shù)據(jù)源提供真值的概率大于提供錯誤值的概率,則q>0.即一個人說真話的概率大于說假話的概率,那么這個人說的話就有一定的可信度,說真話的概率越大,則說假話的概率越小,可信度越大.

3)當(dāng)a<0.5時,數(shù)據(jù)源提供真值的概率小于提供錯誤值的概率,則q<0.即一個人說假話的概率大于說真話的概率,那么這個人說的話就有負(fù)的可信度,說假話的概率越大,則說真話的概率越小,可信度也就越小.

由于a∈[0,1],實現(xiàn)時為了避免a接近0或1的時候q過小或過大,對q的計算進(jìn)行修正,則

(8)

式中：ε取0.1左右的值.

定義2 觀察值x的可信度c(x)

由于

令

則

(9)

即c(x)由提供觀察值x的數(shù)據(jù)源的可信度決定.后驗概率分布p(X=x)∝c(x),令

(10)

對同一實體的觀察值的可信度歸一化,歸一化后的結(jié)果即為觀察值為真的后驗概率.其中∑o(y)=o(x)c(y)為歸一化因子.

2 觀察值包含度

觀察值的可信度不僅取決于數(shù)據(jù)源的可信度,也與觀察值之間的關(guān)系有關(guān).文獻(xiàn)[6]采用了觀察值之間的相似關(guān)系對觀察值的可信度進(jìn)行了修正.然而數(shù)據(jù)之間的關(guān)系不只是相似關(guān)系,在Web世界中,大量存在對同一客觀實體正確但不完全的觀察值,觀察值之間存在包含關(guān)系.

2.1 觀察值包含度

定義3 包含度[16]

上述定義中：1)是對包含度的規(guī)范化.2)是包含度與經(jīng)典包含的協(xié)調(diào)性,經(jīng)典包含僅是包含度為1的特殊情況.3)與4)是包含度的單調(diào)性.

設(shè)F為一個字符串集合,di,dj∈F,設(shè)si與sj分別為字符串di,dj的詞項集合,若si?sj,則稱dj包含di,用didj表示,為二元運(yùn)算符.由偏序集定義可知,(F,)為偏序集.

定義5 偏序集(F,)上的包含度

(11)

2.2 觀察值包含度計算

設(shè)s1(bi),s2(bj)分別表示描述d1,d2的詞項集合s1,s2中的元素；m,n代表s1,s2中包含的詞項個數(shù),n≠0.描述包含度的計算公式為

D(d1/d2)=

(12)

2.3 包含度對觀察值可信度的修正

綜合考慮數(shù)據(jù)源的可信度以及觀察值之間的包含度,修正后觀察值的可信度c′(x)如下：

(13)

式中：ρ為包含度閾值,即當(dāng)包含度大于某一閾值時；做正修正；小于某一閾值時,做負(fù)修正.

在DataCredibility算法實現(xiàn)中ρ=1,即如果觀察值不能包含被觀察值,則被觀察值對觀察值作負(fù)修正.與基于相似度的修正不同,基于包含度的修正是非對稱的.

3 數(shù)據(jù)可信度算法

在未知數(shù)據(jù)源精確度的先驗概率的情況下,統(tǒng)一賦予每個數(shù)據(jù)源相同的初始精確度a0>0.5.

3.1 算法流程

令A(yù)=[a1,a2,…,an]表示數(shù)據(jù)源精確度向量,Q=[q1,q2,…,qn]表示數(shù)據(jù)源可信度向量,V=[v1,v2,…,vk]表示觀察值向量,C=[c1,c2,…,ck]和C′=[c′1,c′2,…,c′k]分別表示修正前和修正后的觀察值可信度向量,M表示數(shù)據(jù)源與觀察值之間的關(guān)聯(lián)矩陣矩陣：

(14)

將數(shù)據(jù)源集合W和觀察值向量V看作頂點(diǎn),將關(guān)聯(lián)矩陣Mk×n看作邊,則G(W∪V,M)是一個二部圖.矩陣M包含二部圖的結(jié)構(gòu)信息.

令R表示觀察值包含度矩陣：

(15)

R蘊(yùn)涵了觀察值之間的包含度信息.

由式(10)得

C=MQ.

(16)

由式(14)得

C′=RC.

(17)

DataCredibility算法的流程如下：

輸入：W、A、M、精確度初始值a0、迭代次數(shù)閾值t、收斂閾值λ=10-5

Begin

計算包含度矩陣R∥利用式(13)計算包含度矩陣

for allwi∈W∥給所有數(shù)據(jù)源賦精確度初始值a0

ai=a0

Repeat ∥迭代計算

for allqj∈Q∥計算所有數(shù)據(jù)源質(zhì)量

ifaj>0.5

else ifaj<0.5

C←MQ∥利用式(17)計算修正前的觀察值可信度向量

C′←RC∥利用式(18)計算修正后的觀察值可信度向量

C←C′∥保存觀察值可信度向量中間結(jié)果}

根據(jù)式(3)計算A

Until 迭代次數(shù)大于t或A的變化小于λ

輸出C,A∥可信度最大的觀察值判斷為真值

end

3.2 算法復(fù)雜度

設(shè)數(shù)據(jù)源集合W的有i個元素,觀察值V向量有m個元素.因為數(shù)據(jù)源的個數(shù)往往比其提供的觀察值的個數(shù)小的多,通常m遠(yuǎn)大于i.包含度矩陣R的計算取決于實體個數(shù)與每個實體的沖突觀察值個數(shù).設(shè)每個實體平均有k個觀察值,則每個觀察值與其他k-1個觀察值沖突.計算矩陣R的時間復(fù)雜度為m/k×k×(k-1),表示為O(mk)；計算向量C的時間復(fù)雜度為i×m,表示為O(im),計算向量C′計算的時間復(fù)雜度為O(ik2),即O(mk).考慮到算法的迭代實現(xiàn),設(shè)迭代次數(shù)為t,則DataCredibility算法的時間復(fù)雜度為O(mk+tmk).由于m遠(yuǎn)大于k、t,DataCredibility算法對觀察值個數(shù)m有近似線性的時間復(fù)雜度.算法的空間復(fù)雜度也為O(m).

4 實驗結(jié)果及分析

實驗對比算法為2-Estimates[8]、3-Estimates[8]、NormalizedSources[8]、TruthFinder[7].

實驗采用以下指標(biāo)度量算法的有效性.

1)精確度p、召回率r、F1測度：精確度p度量了算法正確判定為真值的比例；召回率r度量了算法正確判定為真值的觀察值占所有真值的比例；F1測度綜合考慮了上述2者的結(jié)果,由下式計算:

(18)

2)精確度回歸曲線：從1個觀察值開始,每次增加1個觀察值,并計算各算法精確度p和召回率r,將r作為x坐標(biāo),p作為y坐標(biāo),繪制散點(diǎn)圖.利用曲線下的面積作為衡量算法有效性的指標(biāo).

4.1 真實數(shù)據(jù)集

實驗采用Books-Authors數(shù)據(jù)集[17],包括1 265本計算機(jī)科學(xué)與工程相關(guān)的書籍,895個數(shù)據(jù)源以及33 971個條目.真值通過查看書籍封面獲得.

實驗選取數(shù)據(jù)集Books-Authors中給定真值的100本書對應(yīng)的觀察值進(jìn)行實驗，其中包含237個數(shù)據(jù)源,共有2 455個觀察,651個觀察值,有85個真值.將數(shù)據(jù)集中的作者列表信息利用分詞工具分割成多個詞項.比如將“hoos,holger h.;stutzle, thomas”分割成2條描述“hoos,holger h.”與“stutzle, thomas”.

4.2 精確度p、召回率r和F1測度指標(biāo)對比

為了使結(jié)果具有可比性,采取了與文獻(xiàn)[6]相同的運(yùn)行參數(shù).實驗運(yùn)行參數(shù)設(shè)置為初始精確度a0=0.8,迭代次數(shù)閾值為10,ε=0.1,包含度閾值ρ=1,收斂閾值λ=10-5.DataCredibility算法與以及2-Estimates、3-Estimates、TruthFinder、NormalizedSources算法在錯誤率e、棄真數(shù)量N1、取偽數(shù)量N2、精確度p、召回率r和F1測度指標(biāo)上的性能如表1所示,其中最優(yōu)結(jié)果用加粗字體表示.

表1 各算法在6個指標(biāo)上的性能對比

Tab.1 Performance comparison of algorithms on six indicators

算法eN1N2prF12-Estimates0.1157140.890.330.483-Estimates0.1643580.840.490.62NormalizedSources0.1129440.890.660.76TruthFinder0.1540560.850.530.65DataCredibility0.1024390.900.720.80

由表1可知,算法DataCredibility 的p、r、F1分別為0.90、0.72、0.80均為最好.DataCredibility算法與NormalizedSources算法的有效性最接近,與其相比F1提高了4%,r提高了6%,p提高了1%.這驗證了采用新的數(shù)據(jù)源可信性度量方式并使用包含度進(jìn)行觀察值的可信度修正能夠顯著提高算法的有效性.

4.3 精確度回歸曲線

利用召回率r作為橫坐標(biāo),精確度p作為縱坐標(biāo),繪制精確度回歸曲線圖.利用精確度回歸曲線下的面積作為衡量各真值發(fā)現(xiàn)算法的有效性.實驗運(yùn)行參數(shù)設(shè)置與4.2節(jié)相同.如圖1所示為根據(jù)實驗數(shù)據(jù)繪制的精確度回歸曲線圖.

圖1 不同算法對應(yīng)的精確度回歸曲線Fig.1 Precision recall curves of different algorithms

由圖1可得,算法TruthFinder、3-Estimates、2-Estimates、NormalizedSources對應(yīng)的曲線面積分別為0.45、0.58、0.48、0.62；而DataCredibility算法對應(yīng)的曲線面積為0.66,相比于前4種算法分別提高了46.7%、13.8%、37.5%、6.45%.這驗證了算法DataCredibility的有效性.

5 結(jié) 語

與現(xiàn)有TruthFinder、3-Estimates、2-Estimates、NormalizedSources算法相比,本文提出的DataCredibility算法在精確度、召回率、F1測度3個度量指標(biāo)方面均獲得了較好結(jié)果,驗證了算法的有效性.這對于Web場景下觀察值之間包含等不對稱關(guān)系的可信度度量很有價值.

DataCredibility算法適用于字符型數(shù)據(jù),對數(shù)字、日期等類型數(shù)據(jù)不適用；該算法與TruthFinder等迭代算法一樣,對數(shù)據(jù)源初始可信度值敏感；同時,該算法沒有考慮數(shù)據(jù)融合中的數(shù)據(jù)動態(tài)變化特性,這些問題有待進(jìn)一步研究.

[1] 董永權(quán).Deep Web數(shù)據(jù)集成關(guān)鍵問題研究 [D]. 濟(jì)南：山東大學(xué), 2010. DONG Yong-quan. Key problem of deep web data integration [D]. Jinan: Shandong University, 2010.

[2] FETTERLY D, MANASSE M, NAJORK M, et al. A large-scale study of the evolution of web pages [C] ∥ In proceedings of the 12th international conference on World Wide Web. Budapest: ACM, 2003: 669-678.

[3] CHANG K C C, HE B, LI C, et al. Structured databases on the web: observations and implications [J]. ACM Sigmod Record, 2004, 33(3): 61-70.

[4] ENRIGHT A. Consumers trust information found online less than offline messages [J]. Internet Retailer, 2010, 25.

[5] DALVI N, MACHANAVAJJHALA A, PANG B. An analysis of structured data on the web [C] ∥ In proceedings of the 38th International Conference on Very Large DataBases. Istanbul: ACM, 2012: 680-691.

[6] LI X, DONG X L, LYONS K, et al. Truth finding on the deep web: Is the problem solved？ [C] ∥ In proceedings of the 38th International Conference on Very Large DataBases. Istanbul: ACM, 2012: 97-108.

[7] YIN X X, HAN J W, YU P S. Truth discovery with multiple conflicting information providers on the Web [J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(6): 796-808.

[8] GALLAND A, ABITEBOUL S, MARIAN A, et al. Corroborating information from disagreeing views [C] ∥ In proceedings of the third ACM international conference on Web search and data mining. New York: ACM, 2010: 131-140.

[9] PASTERNACK J, ROTH D. Knowing what to believe (when you already know something) [C] ∥ In proceedings of the International Conference on Computational Linguistics. Beijing: ACM, 2010: 877-885.

[10] J?SANG A, MARSH S, POPE S. Exploring different types of trust propagation [C] ∥ International Conference on Trust Management. Berlin Heidelberg: Springer, 2006: 179-192.

[11] 張志強(qiáng),劉麗霞,謝曉芹,等.基于數(shù)據(jù)源依賴關(guān)系的信息評價方法研究[J].計算機(jī)學(xué)報, 2012, 35(11):2392-2402. ZHANG Zhi-qiang, LIU Li-xia, XIE Xiao-qin, et al. Information evaluation based on source dependence [J]. Chinese Journal of Computers, 2012, 35(11): 2392-2402.

[12] 張永新,李慶忠,彭朝暉.基于Markov邏輯網(wǎng)的兩階段數(shù)據(jù)沖突解決方法 [J]. 計算機(jī)學(xué)報, 2012, 35(1): 101-111. ZHANG Yong-xin, LI Qing-zhong, PENG Zhao-hui. 2-stage data conflict resolution based on Markov logic networks [J]. Chinese Journal of Computers, 2012, 35(1): 101-111.

[13] ZHAO B, RUBINSTEIN B I, GEMMELL J, et al. A bayesian approach to discovering truth from conflicting sources for data integration [C] ∥ In proceedings of the 38th International Conference on Very Large DataBases. Istanbul: ACM, 2012, 5(6): 550-561.

[14] RAVALI P, ANISH D S, DSONG X L, et al. Fusing data with correlations [C] ∥ In proceedings of the SIGMOD, Snowbird: ACM, 2014: 433-444.

[15] LI Q, LI Y, GAO J, et al. A confidence-aware approach for truth discovery on long-tail data [C] ∥ In proceedings of the 41th International Conference on Very LargeDataBases. Kohala Coast: ACM, 2015: 425-436.

[16] 曲開社,翟巖慧.偏序集,包含度與形式概念分析[J].計算機(jī)學(xué)報,2006,29(2): 219-226. QU Kai-she, ZHAI Yan-hui. Posets, inclusion degree theory and FCA [J]. Chinese Journal of Computers, 2006.29(2): 219-226.

[17] YIN X, DONG L. Data sets for data fusion experiments (III. Book) [EB/OL]. (2012-12-07) [2015-10-01]. http:∥lunadong.com/ fusionDataSets.htm.

Bayesian conflicting Web data credibility algorithm

WANG Ji-kui

(KeyLaboratoryofelectroniccommerce,LanzhouUniversityofFinanceandEconomics,Lanzhou730000,China)

The key of Web data fusion is to judge the credibility of conflicting Web data. The credibility of observing values was only rectified by their similarity relations, while the inclusion relations was ignored in existed algorithms. To solve this problem, the concept of inclusion degree was defined based on the characteristic analysis of the observing values; a modified model was proposed to rectify the credibility of observing values using inclusion degree was proposed. Taking the observing values as random variables, the reliability problem of the observation values could be attributed to a posterior probability distribution problem. Bayesian theory was adopted to define the conception of data source credibility, to derive the relationship model for data source credibility and observing value credibility, and to propose the Bayesian conflicting Web data credibility algorithm: DataCredibility. The experiment results show that the proposed DataCredibility algorithm achieves better accuracy, recall rate and F1 measure value compared with the baseline algorithms.

conflicting Web data; Bayesian theory; credibility; data fusion; DataCredibility

2015-10-11.

國家自然科學(xué)基金資助項目(51475097,61473194)；國家社科基金資助項目(14GSD95)；全國統(tǒng)計科研重點(diǎn)資助項目(2013LZ44)；隴原創(chuàng)新人才扶持計劃資助項目(14GSD95)；甘肅省財政廳高?；究蒲袠I(yè)務(wù)費(fèi)資助項目(GZ14007, GZ14023).

王繼奎(1978—),男,副教授,從事數(shù)據(jù)治理、數(shù)據(jù)集成、軟件過程技術(shù)與方法研究. ORCID： 0000-0001-5926-7007. E-mail: wjkweb@163.com

10.3785/j.issn.1008-973X.2016.12.019

TP 311

A

1008-973X(2016)12-2380-06