證據距離的選取對沖突證據組合影響的研究

周永慶,韓德強,楊藝

(1.西安交通大學電子與信息工程學院,710049,西安; 2.西安交通大學機械結構強度與振動國家重點實驗室,710049,西安; 3.西安交通大學航天航空學院,710049,西安)

在Dempster-Shafer(DS)證據理論[1]中,獨立證據可以依據證據組合規則進行證據組合。當證據之間存在沖突時,證據組合后的結果往往與實際直覺相悖[2],針對這一情況,出現了許多改進的證據組合規則[3-8],其中有一類是基于證據間距離的沖突證據組合規則[3-5],這類算法用證據之間的距離度量證據之間的相似性,依據相似性得到證據的權值,對證據進行加權融合。在此類方法中,證據距離度量方式對證據組合有重要的影響。

隨著證據理論的研究深入,涌現了諸多證據之間距離的度量定義[9],如Jousselme距離[10]、基于Pignistic概率的距離[11]、基于模糊隸屬度的距離[12]和基于信任區間的距離[13]等。在既有的基于證據間距離的沖突證據組合研究中,上述距離定義方式均有所采用。鄧勇等人依據證據間的Jousselme距離得到證據可靠度,用證據可靠度對證據進行加權融合獲取平均證據,再將平均證據進行組合[3]。肖建于等人則基于Pignistic概率距離得到證據的權重,求得平均證據后再進行組合[4]。劉志成等人則依據修正的City Block距離獲取證據的權重[5]。在這些方法中,只選取了某一種證據間的距離度量方式,沒有對不同的證據距離度量方式進行對比。

為了探究不同的證據距離度量方式對沖突證據組合的影響,從而選取適合加權證據組合權重生成的距離定義,本文將各種距離度量方式應用于基于證據距離修正證據組合的方法中,對比了在不同的距離度量方式下,證據可靠度的大小和將平均證據組合后所得組合結果之間的差異,分析了產生差異的原因。采用4個算例的實驗結果表明,在證據組合過程中,與其他的證據距離相比,采用本文方法選取的證據距離所求得的證據可靠度更符合實際,體現證據差異更有效。

1 證據理論概述

設Θ為辨識框架,若集函數m:2Θ→[0,1]滿足

(1)

則稱m為Θ上的Mass函數。Mass函數實際上就是對各種假設的評價權值。其中,使得m(A)>0的A稱為焦元。

在辨識框架Θ上的某個命題A的信任函數(belief function)定義為

(2)

似真度函數(plausibility function)定義為

(3)

區間[bel(A),pl(A)]為信任區間,用以表示對命題(焦元)A的不確定程度。

Dempster組合規則也稱證據組合公式,其定義為:設統一辨識框架上的兩個獨立證據,其相應的mass函數分別為m1和m2,?A?Θ,A≠?,則組合之后證據為

(4)

在將證據進行融合之后,需要將融合結果的mass函數轉化為概率以便于進行決策。Mass函數轉化為概率有多種方法,一種經典的方法為Smets提出的Pignistic概率轉換方法[14]

(5)

2 沖突證據組合方法

2.1 證據沖突現象

當證據之間存在較大沖突的時候,應用Dempster組合規則融合后得到的結果往往與直觀結果相違背。以下為Zadeh所舉的經典算例[2]。

兩名醫生為同一個病人看病,該病人可能得的病為腦膜炎(M)、腦震蕩(C)和腦腫瘤(T),即辨識框架為Θ={M,C,T}。兩名醫生給出的各種病癥的可能結果如下

m1({M})=0.99;m1({T})=0.01

m2({C})=0.99;m2({T})=0.01

將以上兩個獨立證據應用Dempster組合規則進行融合,得到融合后的結果為m({T})=1,此時的沖突系數K=0.999 9。

在這個例子中,兩名醫生均認為該病人所得的病是腦腫瘤(T)這件事的可能性很低,但是應用Dempster組合規則融合后的結果卻表明該病人得的病只可能是腦腫瘤(T),這與兩名醫生的判斷均相悖,不符合直觀結果。這個例子表明,在證據存在較高沖突的情況下,應用Dempster組合規則得到的結果會反直觀。此外,Dempster組合規則并不滿足冪等性,即使證據體都相同,組合過程中也會產生信任偏移[15],在某些情況下還會出現證據吸收的問題[16]。

針對證據沖突問題,一種觀點歸因于融合規則本身的缺陷,對融合規則進行了修正,如在Yager提出的規則[6]中,將沖突賦給全集;Dubois等則將焦元的并集引入到證據組合規則中[7]。另一種觀點認為該問題是由證據本身的不準確、不可靠所造成的,因此應該對證據進行進一步修正,如Murphy采用求平均的方式來對證據進行修正[8],鄧勇、肖建于、劉志成等人則基于證據距離來構造證據權值,對證據進行加權融合[3-5]等。

2.2 基于證據距離的證據修正與組合方法

在基于證據距離的證據修正與組合方法中,鄧勇等人所提出的方法具有代表性。在該方法中,核心概念為證據可靠度,它描述了證據的可靠程度。用證據可靠度作為權值來對證據進行加權,得到融合后的證據。關于證據可靠性的評估,學者們做了許多的研究。Elouedi等人依據可傳遞信任模型,基于加權后的平均證據應與數據真值距離最小,利用優化方法得到證據可靠度[17]。邢清華等人把各個焦元信任區間的長度之和作為目標函數,通過極小化目標函數得到證據可靠度[18]。付耀文等人借鑒沖突處理中的Dubois & Prade規則,將由沖突得到的折扣量按局部沖突的大小分配給涉及各局部沖突的集合的并,得到證據可靠度[19]。

在鄧勇等人的方法中,證據可靠度是基于證據距離構建的,其構建過程如下[3]

sim(mi,mj)=1-d(mi,mj)

(6)

(7)

(8)

式中:cred(mi)為證據mi的可靠度;d(mi,mj)表示證據mi與mj間的證據距離。

得到各個證據的可靠度之后,就可以用證據可靠度作為權值對證據進行加權融合,得到平均證據。

假設有s個證據,則平均證據為

(9)

然后,應用Dempster組合規則對平均證據mave自身組合s-1次。

在該方法中,證據可靠度的求取與證據距離緊密相關。隨著證據理論的研究深入,出現了一系列的證據距離定義。不同的距離應用于證據修正,效果或有不同。本文將針對證據距離的不同,對于證據修正與組合效果的影響開展分析研究。在下一節中,將首先介紹幾類常用的證據距離,并將不同的證據距離應用于沖突證據組合的方法中進行比較。

3 基于不同證據距離的加權證據融合

3.1 證據距離度量方式

證據距離用來描述證據之間的差異性或者相似性,兩組證據之間的距離越大,表明它們之間的差異性越大,相似性越低。幾類常用的證據距離度量方式有Jousselme距離[10]、Tessem距離[11]、基于隸屬度函數的距離[12]和基于信任區間的距離[13]。

3.1.1 Jousselme距離 Jousselme距離[10]的求取過程如下

(10)

3.1.2 Tessem距離 在Tessem的研究中[11],證據距離的度量是基于pignistic概率的。Mass函數轉化為Pignistic概率的公式如下

(11)

Tessem距離定義如下

(12)

3.1.3 基于隸屬度函數的距離[12]在模糊理論中,隸屬度函數描述了元素屬于某一模糊集合的程度。若μA:Θ→[0,1],θ→μA(θ)是在辨識框架Θ上的給定映射,則A是Θ上的模糊集合,μA(θ)是模糊集合A的隸屬度函數,μA(θ)在沒有混淆時簡記為μ(θ)。μ(θi)為單點焦元θi的隸屬度函數,μ(θi)可以取θi的信任函數或者似真度函數μ(θi)=bel(θi),或μ(θi)=pl(θi),則基于隸屬度函數的證據距離定義為

(13)

式中:符號∧為取小運算(合取);符號∨為取大運算(析取)。

在一個有限的辨識框架中,若單點焦元的隸屬度函數之和小于1,則隸屬度函數等價于相應焦元的信任函數,若隸屬度函數之和大于1,則隸屬度函數等價于相應焦元的似真度函數[20]。就實際操作而言,在證據函數中,如果混合焦元多,單點焦元少,此時若使用單點焦元的信任函數作為隸屬度函數,會出現較多的0元素,求取距離時實用性較差,因此更傾向于使用似真度函數作為單點焦元的隸屬度函數。本文的實驗中選取μ(θi)=pl(θi)。

3.1.4 基于信任區間的距離 本課題組以往的工作中設計了一種基于信任區間的距離[13]。若一個焦元在兩個證據中的信任區間([bel(A),pl(A)])分別為[a1,b1]和[a2,b2],則基于信任區間的距離定義為

(14)

基于所有信任區間的兩個mass函數之間的距離為

(15)

式中:Ai為焦元;B1(Ai)和B2(Ai)分別表示m1和m2中焦元Ai的信任區間;Nc=1/2n-1是歸一化因子。

3.2 算例

為了研究證據距離度量方式對證據可靠度以及證據組合結果的影響,設計如下算例。

算例1設辨識框架為Θ={A,B,C},利用6個不同信息源得到的證據函數如下。

m1:m1(A)=0.65,m1(B)=0.2,m1(C)=0.15;

m2:m2(A)=0.55,m2(B)=0.25,m2(C)=0.2;

m3:m3(A)=0.5,m3(B)=0.3,m3(C)=0.2;

m4:m4(A)=0.3,m4(B)=0.35,m4(C)=0.35;

m5:m5(A)=0.1,m5(B)=0.3,m5(C)=0.6;

m6:m6(B)=0.8,m6(C)=0.2。

直觀來看,6組證據中第1、2、3組證據相似,其中m(A)最高,第4組證據中m(A)、m(B)、m(C)大小接近,第5組證據中m(C)最高,第6組證據中m(B)最高。

使用鄧勇的方法,在不同的證據距離度量方式下求得的各證據可靠度如表1所示。

表1 算例1中不同證據距離度量方式下證據可靠度對比

得到證據可靠度后,運用證據可靠度進行加權得到平均證據如表2所示。

表2 算例1中不同證據距離度量方式下的平均證據

應用Dempster組合規則對平均證據自身組合5次,得到融合后的mass函數如表3所示。

表3 算例1中不同證據距離度量方式下組合結果對比

表1中證據可靠度對比結果顯示,根據4種證據距離度量方式得到的前4組證據的可靠度均比后兩組證據的可靠度高,且最后一組證據的可靠度最小。由于證據可靠度是依據證據之間的相似度得到的,假設多數人給出的信息是可靠的,那么某一條證據與其他證據之間的相似度越高,該條證據的可靠度越大。綜合6組證據來看,前3組證據之間的相似度大,它們之間相互支持,因此得到的前3組證據的可靠度高,第4組證據中m(A)、m(B)、m(C)大小接近,后兩組證據與前4組證據以及它們中的另一組證據的差異性都很大,所以后兩組證據的可靠度較低。表1給出的結果與直觀結論相符。

在只有單點焦元有值的情況下,焦元的BetP與mass函數值相等。表3中組合結果對比顯示,所有度量方式下組合結果中P(A)都是最大,原因在于前3組證據中的m(A)均為最高,它們之間相互支持,得到的證據可靠度高,加權后平均證據中的m(A)也是最大。在此算例中4種距離度量方式下的證據組合結果在決策方面并無差異。

算例2設辨識框架為Θ={A,B,C},利用6個不同信息源得到的證據函數如下。

m1:m1(A)=0.4,m1(B)=0.3,m1(A∪C)=0.3;

m2:m2(A)=0.5,m2(B)=0.2,m2(A∪B∪C)=0.3;

m3:m3(A)=0.7,m3(B)=0.2,m3(A∪B)=0.1;

m4:m4(A)=0.6,m4(B)=0.3,m4(B∪C)=0.1;

m5:m5(A)=0.2,m5(B)=0.7,m5(A∪C)=0.1;

m6:m6(B)=0.7,m6(C)=0.1,m6(A∪B)=0.2。

與算例1不同的是,算例2中加入了混合焦元,這6組證據中前4組證據相似,其中m(A)大于m(B),后兩組證據中m(B)最大。在不同的證據距離度量方式下求得各證據的可靠度,如表4所示。

表4中證據可靠度對比結果顯示:在所有的證據距離度量方式下,前4組證據的可靠度均大于后兩組證據的可靠度;前4組證據彼此之間的相似度高,支持度大,在假設多數人意見可靠的前提下得到的證據可靠度高,這與直觀結果相符合;后兩組證據與前4組證據之間的差異較大,可靠度較低。表4給出的結果與直觀結論相符。

表4 算例2中不同證據距離度量方式下證據可靠度對比

運用證據可靠度對證據進行加權,得到平均證據,如表5所示。

表6組合結果中,m(A∪C)很小,可以認為A、B、C的BetP與A、B、C的mass函數值相等。4種距離度量方式下給出的組合結果相似,其中P(A)大于P(B),P(C)最小。原因在于前4組證據中m(A)最大,它們相互支持,證據可靠度高,在加權的過程中對平均證據的貢獻較大,因此平均證據中的m(A)也是最大,如表5所示。表6中的組合結果表明,在證據中存在混合焦元的情況下,4種距離度量方式下的證據組合結果在決策方面也沒有差異。

表6 算例2中不同證據距離度量方式下組合結果對比

3.2.3 有關證據距離的分析與探討 嚴謹的證據距離應滿足以下4條性質[13]:

(1)非負性,d(x,y)≥0;

(2)非退化性,d(x,y)=0?x=y;

(3)對稱性,d(x,y)=d(y,x);

(4)三角不等式,d(x,y)+d(y,z)≥d(x,z)。

在3.1節提及的4種證據距離中,dJ、dBI是嚴謹的證據距離[10,13],滿足全部4條性質。dF、dT不是嚴謹的證據距離。算例1和算例2中4種證據距離度量方式下證據可靠度以及證據組合結果均直觀、合理,但是在這4種證據距離中,dF、dT這兩種距離在計算的過程中進行了框架的切換。其中,dT將證據函數轉化到概率框架下計算,dF則將證據函數轉化到模糊理論的框架下計算,在框架切換的過程中產生了信息損失[13],由此造成了dF、dT的不嚴謹性。為了進一步分析證據距離對證據可靠度的影響,舉出下面兩個算例。

算例3設辨識框架為Θ={A,B,C},利用6個不同信息源得到的證據函數如下。

m1:m1(A)=0.45,m1(B)=0.35,m1(C)=0.05,m1(A∪B)=0.1,m1(A∪B∪C)=0.05;

m2:m2(A)=0.4,m2(B)=0.3,m2(C)=0.1,m2(A∪B)=0.2;

m3:m3(A)=0.5,m3(B)=0.4,m3(A∪B∪C)=0.1;

m4:m4(A)=0.48,m4(B)=0.38,m4(C)=0.02,m4(A∪B)=0.04,m4(A∪B∪C)=0.08;

m5:m5(A)=0.5,m5(B)=0.5;

m6:m6(B)=0.8,m6(C)=0.2。

在這6組證據中,前4組證據相似,其中m(A)略大于m(B),m(C)最小。第5組證據中m(A)與m(B)相同,與前4組證據有一定的相似度。第6組證據中m(B)遠大于m(C),與前5組證據的差異較大。在不同證據距離度量方式下得各證據的可靠度，如表7所示。

表7 算例3中不同證據距離度量方式下證據可靠度對比

從表7中的證據可靠度對比結果來看,4種證據距離度量方式下得到的前5組證據的可靠度都比較高,最后一組證據的可靠度很低。在假設多數人的信息可靠的前提下與直觀結果相吻合。

在dF度量方式下,前4組證據的可靠度相同,且與后兩組證據的可靠度相差較大,但是前4組證據并不相同。事實上基于隸屬度函數的距離與證據之間的差異并不是一一對應的,如果證據中單點焦元的信任函數或者似真度函數相同,那么在dF度量方式下他們之間的距離為零,即dF不滿足非退化性。本例中前4組證據單點焦元的似真度函數相同,即

pl(A)=0.6; pl(B)=0.5; pl(C)=0.1

則依據式(13),m1、m2之間的距離為

類似地,求得這4條證據中任意兩條證據之間的距離為零,從而得到這4組證據的可靠度相同。這表明dF度量方式并不能體現出某些證據之間的差異。由此得到的可靠度必然存在偏差。可見證據距離的不嚴謹會對證據可靠度產生影響。

算例4設辨識框架為Θ={A,B,C},利用6個不同信息源得到的證據函數如下。

m1:m1(A)=0.4,m1(B)=0.4,m1(C)=0.2;

m2:m2(A∪B)=0.8,m2(C)=0.2;

m3:m3(A)=0.4,m3(B)=0.2,m3(B∪C)=0.4;

m4:m4(A)=0.2,m4(C)=0.2,m4(A∪B∪C)=0.6;

m5:m5(C)=0.65,m5(A∪B∪C)=0.35;

m6:m6(A)=0.35,m6(C)=0.65。

在這6組證據中:第1組證據的m(A)、m(B)相同,且大于m(C),第3組證據中m(A)大于m(B);第2組證據中m(C)很小,m(A∪B)較大;第4組證據中m(A)、m(C)相同,均很小,第5組證據中m(C)較大,第6組證據中m(A)小于m(C);第1、第3、第4組證據較為相似。在不同的證據距離度量方式下求得各證據的可靠度，如表8所示。

表8 算例4中不同證據距離度量方式下證據可靠度對比

從表8中的證據可靠度對比結果來看,在dJ、dF、dBI度量方式下得到的第1、3、4組的證據可靠度較大,剩余3組的證據可靠度較小。

在dT度量方式下得到的前3組證據的可靠度相同,但是前3組證據并不相同。事實上,Tessem距離是根據pignistic概率求得的,如果證據的pignistic概率相同,那么在Tessem距離的度量方式下,證據之間的差異就是零。即dT不滿足非退化性。本例的前3條證據中,各條證據之間單點焦元的pignistic概率都相同,即

P(A)=0.4;P(B)=0.4;P(C)=0.2

則依據式(12),m1、m2之間的距離為

dT(m1,m2)=max{|0.4-0.4|,|0.4-0.4|,|0.2-0.2|}=0

類似地,求得這3條證據中任意兩條證據之間的距離為零,且其他證據到這3條證據的距離都相等,從而得到這3組證據的可靠度相同。這表明,dT度量方式下距離與證據之間的差異也不是一一對應的。可見,證據距離的不嚴謹會對證據可靠度產生影響。

證據可靠度以及證據組合的合理性受到諸多因素影響,如果基于證據距離構造可靠度并用于證據組合,距離的選取只是其中的一個因素,使用嚴謹的證據距離并不能夠保證得到的證據可靠度和證據組合結果最優。本文關注證據距離對證據可靠度和證據組合的影響,算例表明嚴謹的證據距離能夠更好地表征證據之間的差異,在基于證據距離生成證據可靠度時結果更符合直觀。

4 結 論

本文提出一種將不同的證據距離度量方式應用在加權證據組合中的對比方法,對不同證據距離下的加權證據組合過程進行分析比較。實驗結果表明,不同的證據距離度量方式對證據可靠度的求取有影響,其中使用dF、dT度量方式在算例中得到的證據可靠度不能體現出證據之間的差異,這與dF、dT的不嚴謹性有關。本文建議選擇dJ、dBI這兩種嚴謹的證據距離。

對于證據沖突問題,本文的解決方式是修改證據體。在未來的工作中,我們將更加關注有關修改證據規則的研究,關注當存在證據沖突時,各類證據距離度量方式對修改后的證據規則的影響。

參考文獻:

[1] SHAFER G. A mathematical theory of evidence [M]. Princeton,NJ,USA: Princeton University Press,1976: 1-10.

[2] ZADEH L A. Review of Shafer’s a mathematical theory of evidence [J]. AI Magazine,1984,5(3): 81-83.

[3] DENG Yong,SHI Wenkang,ZHU Zhenfu,et al. Combining belief functions based on distance of evidence [J]. Decision Support Systems,2004,38(3): 489-493.

[4] 肖建于,童敏明,朱昌杰,等. 基于pignistic概率距離的改進證據組合規則 [J]. 上海交通大學學報,2012,46(4): 636-641.

XIAO Jianyu,TONG Minming,ZHU Changjie,et al. Improved combination rule of evidence based on pignistic probability distance [J]. Journal of Shanghai Jiaotong University,2012,46(4): 636-641.

[5] 劉志成,喬慧,何佳洲. 基于加權證據距離的高度沖突證據組合方法 [J]. 計算機工程與應用,2014,50(3): 103-107.

LIU Zhicheng,QIAO Hui,HE Jiazhou. Combination approach of highly conflicting evidence based on weighted distance of evidence [J]. Computer Engineering & Applications,2014,50(3): 103-107.

[6] YAGER R R. On the Dempster-Shafer framework and new combination rules [J]. Information Science,1987,41(2): 93-137.

[7] DUBOIS D,PRADE H. Representation and combination of uncertainty with belief functions and possibility measures [J]. Computational Intelligence,1988(4): 244-264.

[8] MURPHY C K. Combining belief functions when evidence conflicts [J]. Decision Support Systems,2000,29(1): 1-9.

[9] JOUSSELME A L,PATRICK M. Distance in evidence theory: comprehensive survey and generalization [J]. International Journal of Approximate Reasoning,2012,53(2): 118-145.

[10] JOUSSELME A L,GRENIER D,BOSSé E. A new distance between two bodies of evidence [J]. Information Fusion,2001,2(2): 91-101.

[11] TESSEM B. Approximations for efficient computation in the theory of evidence [J]. Artificial Intelligence,1993,61(2): 315-329.

[12] HAN Deqiang,DEZERT J,HAN Chongzhao,et al. New dissimilarity measures in evidence theory [C]//Proceedings of the 14th International Conference on Information Fusion. Piscataway,NJ,USA: IEEE,2011: 5977681.

[13] HAN Deqiang,DEZERT J,YANG Yi. Belief interval-based distance measures in the theory of belief functions [J]. IEEE Transactions on Systems Man & Cybernetics Systems,2016,99: 1-18.

[14] SMETS P. Data fusion in the transferable belief model [C]// Proceedings of the 3rd International Conference on Information Fusion. Piscataway,NJ,USA: IEEE Computer Society,2000: 21-33.

[15] 楊藝,韓德強,韓崇昭. 基于多準則排序融合的證據組合方法 [J]. 自動化學報,2012,38(5): 823-831.

YANG Yi,HAN Deqiang,HAN Chongzhao. Evidence combination based on multi-criteria rank-level fusion [J]. Acta Automatica Sinica,2012,38(5): 823-831.

[16] 楊風暴,王肖霞. D-S證據理論的沖突證據合成方法 [M]. 北京: 國防工業出版社,2010,70-71.

[17] ELOUEDI Z,MELLOULI K,SMETS P. Assessing sensor reliability for multisensor data fusion within the transferable belief model [J]. IEEE Transactions on Systems Man & Cybernetics: Part B Cybernetics,2004,34(1): 782-787.

[18] 邢清華,劉付顯. 基于證據折扣優化的沖突證據組合方法 [J]. 系統工程與電子技術,2009,31(5): 1158-1161.

XING Qinghua,LIU Fuxian. New combination rule of conflict evidence based on optimized evidence discount [J]. Systems Engineering & Electronics,2009,31(5): 1158-1161.

[19] 付耀文,賈宇平,楊威,等. 傳感器動態可靠性評估與證據折扣 [J]. 系統工程與電子技術,2012,34(1): 212-216.

FU Yaowen,JIA Yuping,YANG Wei,et al. Sensor dynamic reliability evaluation and evidence discount [J]. Systems Engineering & Electronics,2012,34(1): 212-216.

[20] DE FERIET J K. Interpretation of membership functions of fuzzy sets in terms of plausibility and belief [J]. Fuzzy Information and Decision Processes,1982(1): 93-98.

[本刊相關文獻鏈接]

魏港明,劉真,李林峰,等.加入用戶對項目屬性偏好的奇異值分解推薦算法.2018,52(5):101-107.[doi:10.7652/xjtuxb201805015]

蔣逸飛,張俊,何勇,等.面向裂紋擴展的連結型剛體-彈簧離散元模型.2018,52(4):48-54.[doi:10.7652/xjtuxb201804 007]

趙振沖,王曉丹.引入拒識的最小風險彈道目標識別.2018,52(4):132-138.[doi:10.7652/xjtuxb201804019]

衛博雅,壽業航,蔣雯.一種可視化的加權平均信息融合方法.2018,52(4):145-149.[doi:10.7652/xjtuxb201804021]

姜洪權,王崗,高建民,等.一種適用于高維非線性特征數據的聚類算法及應用.2017,51(12):49-55.[doi:10.7652/xjtuxb201712008]

周亞東,陳凱悅,冷俊園,等.軟件定義網絡流表溢出脆弱性分析及防御方法.2017,51(10):53-58.[doi:10.7652/xjtuxb 201710009]