貝葉斯沖突Web數據可信度算法

王繼奎

(蘭州財經大學 電子商務綜合重點實驗室,甘肅 蘭州 730020)

?

貝葉斯沖突Web數據可信度算法

王繼奎

(蘭州財經大學 電子商務綜合重點實驗室,甘肅 蘭州 730020)

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

沖突Web 數據; 貝葉斯理論; 可信度；數據融合; DataCredibility

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

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

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

1 數據可信度問題的定義

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

令W={w1,w2,…,wn},W表示數據源集合,用i表示標號為i的數據源.

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

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

(1)

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

(2)

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

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

(3)

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

(4)

由于各數據源獨立提供觀察值,可得

(5)

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

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

(6)

因此,

定義1 數據源的可信度：

(7)

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

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

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

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

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

(8)

式中：ε取0.1左右的值.

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

由于

令

則

(9)

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

(10)

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

2 觀察值包含度

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

2.1 觀察值包含度

定義3 包含度[16]

上述定義中：1)是對包含度的規范化.2)是包含度與經典包含的協調性,經典包含僅是包含度為1的特殊情況.3)與4)是包含度的單調性.

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

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

(11)

2.2 觀察值包含度計算

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

D(d1/d2)=

(12)

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

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

(13)

式中：ρ為包含度閾值,即當包含度大于某一閾值時；做正修正；小于某一閾值時,做負修正.

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

3 數據可信度算法

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

3.1 算法流程

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

(14)

將數據源集合W和觀察值向量V看作頂點,將關聯矩陣Mk×n看作邊,則G(W∪V,M)是一個二部圖.矩陣M包含二部圖的結構信息.

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

(15)

R蘊涵了觀察值之間的包含度信息.

由式(10)得

C=MQ.

(16)

由式(14)得

C′=RC.

(17)

DataCredibility算法的流程如下：

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

Begin

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

for allwi∈W∥給所有數據源賦精確度初始值a0

ai=a0

Repeat ∥迭代計算

for allqj∈Q∥計算所有數據源質量

ifaj>0.5

else ifaj<0.5

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

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

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

根據式(3)計算A

Until 迭代次數大于t或A的變化小于λ

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

end

3.2 算法復雜度

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

4 實驗結果及分析

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

實驗采用以下指標度量算法的有效性.

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

(18)

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

4.1 真實數據集

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

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

4.2 精確度p、召回率r和F1測度指標對比

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

表1 各算法在6個指標上的性能對比

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%.這驗證了采用新的數據源可信性度量方式并使用包含度進行觀察值的可信度修正能夠顯著提高算法的有效性.

4.3 精確度回歸曲線

利用召回率r作為橫坐標,精確度p作為縱坐標,繪制精確度回歸曲線圖.利用精確度回歸曲線下的面積作為衡量各真值發現算法的有效性.實驗運行參數設置與4.2節相同.如圖1所示為根據實驗數據繪制的精確度回歸曲線圖.

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

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

5 結 語

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

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

[1] 董永權.Deep Web數據集成關鍵問題研究 [D]. 濟南：山東大學, 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] 張志強,劉麗霞,謝曉芹,等.基于數據源依賴關系的信息評價方法研究[J].計算機學報, 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邏輯網的兩階段數據沖突解決方法 [J]. 計算機學報, 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].計算機學報,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.

國家自然科學基金資助項目(51475097,61473194)；國家社科基金資助項目(14GSD95)；全國統計科研重點資助項目(2013LZ44)；隴原創新人才扶持計劃資助項目(14GSD95)；甘肅省財政廳高校基本科研業務費資助項目(GZ14007, GZ14023).

王繼奎(1978—),男,副教授,從事數據治理、數據集成、軟件過程技術與方法研究. 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