基于高沖突修正的D-S證據融合方法

,, ,

(1.山東師范大學 信息科學與工程學院,濟南 250358; 2.山東省分布式計算機軟件新技術重點實驗室,濟南 250358; 3.山東財經大學 數學與數量經濟學院,濟南 250014)

0 概述

D-S(Dempster-Shafer)證據理論是由Dempster提出,后由其學生Shafer做進一步推廣,最終形成的一種處理不確定性推理問題的完善理論。在處理不確定信息方面,D-S證據理論目前已在圖像處理、故障診斷、人工智能等多個領域得到了廣泛的應用[1-2],與此同時算法也被不斷地改進[3-5]。D-S證據理論雖然在處理不確定信息方面得到了廣泛的應用,但仍存在一些問題,例如:當信息源之間存在高沖突證據時,可能會出現直觀分析結果與計算結果相悖的結論,文獻[6-7]中所列舉的例子有力地證明了這一點,由此也說明,原有方法在計算高沖突的證據時存在一定的缺陷,需要對證據源或組合規則進行修正。文獻[8]提出了一種將沖突系數分配給各焦元的方法,雖然該方法實現了對高沖突證據的處理,削弱了高沖突證據對融合結果的影響,也提高了聚焦效果,但由于該方法對所有證據都進行了沖突系數的分配,導致了源證據的失真。文獻[9]提出一種基于迭代合成的D-S證據理論改進方法,雖然得到了較好的融合結果,但其迭代次數是不確定的,并且時間復雜度較大。文獻[10]方法主要對高沖突的證據進行了修正,但在對比正常數據時其效果沒有原始方法收斂速度快。文獻[11]提出了一種沖突再分配的方法。該方法對證據分類并根據折扣系數來處理高沖突的證據,可以在一定程度上對證據源進行有效處理,但增加了計算的復雜度。

針對以上方法的不足,本文提出一種綜合考慮證據信任度和虛假度的D-S證據融合方法。該方法對判定為高沖突的證據進行修正,在保證原始組合規則優勢的基礎上,削弱證據間的沖突程度。

1 D-S證據理論及分析

1.1 D-S證據理論

定義1基本概率分配

對任意A∈Θ,若m(A)>0,則稱A為焦元,組合公式如下:

A≠?

(1)

其中,K是歸一化常數,如式(2)所示。

(2)

在上式中,Aij是mi的焦元,mi(Aij)表示第i個證據源中第j個焦元的基本概率賦值。

K的取值范圍為[0,1],當K=0時證據間完全沖突,此時Dempster組合規則不能使用;當K=1時證據間完全不沖突,此時Dempster組合規則能產生最好的效果;當0

1.2 D-S組合規則分析

D-S證據理論不是在任何情況下都適用的,當證據間的沖突較大時就有可能出現與事實相悖的結論。沖突的形成是多方面的,比如傳感器的故障、一些外界因素的干擾等都有可能造成證據源出現問題,從而導致融合結果出現與事實相悖的結論。因此,應在融合之前對干擾信息進行處理,以達到理想的融合結果。

例1在辨識框架Θ={A,B,C}下有2條證據E1和E2,其基本概率賦值為:

E1:m1(A)=0.99,m1(B)=0.01,m1(C)=0

E2:m2(A)=0,m2(B)=0.01,m2(C)=0.99

通過分析可以看出,證據E1幾乎完全支持A,證據E2幾乎完全支持C。對于B,2個證據的支持程度都不高,即B的可信度不高。通過式(1)的計算得到m(A)=m(C)=0,m(B)=0.000 1/k=1,計算結果是支持B,這與事實不相符,可信度較低的B經過融合后得到了最大信任度,顯然這有悖常理。在這里即使加上一條m3(A)=0.99,m3(B)=0.01,m3(C)=0,合成的結果仍然為m(A)=0,結果仍是錯誤的。通過計算沖突度k=0.999 9,可以表明其為高沖突證據,造成高沖突的原因可能是高沖突的證據源或是D-S證據理論合成規則的不足,另外單純的D-S證據理論本身的不足也可能會造成證據的高沖突。

2 高沖突證據修正方法

2.1 Pignistic概率

定義2Pignistic概率

在識別框架Θ={Θ(1),Θ(2),…,Θ(n)}下,Θ中的每個單子集都是獨立的,若滿足[6]:

(3)

則稱BetPmi(Θj)為基本信任分配mi下的Pignistic概率。其中,|A|表示A中所包含元素的個數。

Pignistic概率是一種對子集元素的分配,例如辨識框架Θ={a,b,c},T={{a,b},{b,c},{a,b,c}},m1={0.5,0.2,0.3},利用Pignistic概率計算:

2.2 證據的相似度

定義3相似度

在識別框架Θ下,有2個證據分別為m1、m2,通過Pignistic概率轉換后兩證據之間的相似度計算公式為:

(4)

證據的相似度描述的是兩證據間的相似程度,其取值范圍為[0,1],取值越大說明兩證據間的相似度越大,沖突就越小。

當有多個證據存在時,證據間的相似度可組成如式(5)所示的相似度矩陣。

(5)

由式(4)易得,矩陣中的對角線表示的是證據本身的相似度,因此,對角線上的值都為1,而由于計算相似度是標量計算,因此矩陣關于正對角線對稱。

2.3 信任度

定義4信任度

證據的信任度用于描述其他證據對某一證據的信任程度,表示證據在整體證據中被支持的程度。

假設有n個證據體m1,m2,…,mn,則每個證據的信任度計算公式為:

(6)

通過計算得到每條證據的信任度,組成如式(7)所示的信任度向量。

CrdPm=[CrdPm1,CrdPm2,…,CrdPmi]

(7)

2.4 虛假度

定義5虛假度

虛假度用于描述證據在整體中的虛假程度,證據的虛假度是與信任度相對的,信任度越小其虛假度越大。

在統一識別框架Θ下,多個證據源的沖突如式(8)所示。

(8)

從證據源中去掉第j個證據源后剩余證據的沖突如式(9)所示。

(9)

從式(9)很容易看出0≤kj≤k0≤1,因此,定義證據的虛假度為:

(10)

當只有m1和m22個證據時,Fal(m1)=Fal(m2)=k0。

由式(10)可知:當k0=kj時,Fal(mj)=0,這說明第j條證據的虛假度為0,對沖突系數k0沒有影響,同時也說明第j條證據不是造成沖突的主要原因;當kj=1時,k0=1,則k0=kj,Fal(mj)=0,這就說明第j條證據對全局沖突沒有影響;當k0=1,kj<1時,Fal(mj)=1,這表明第j條證據是造成全局沖突的主要原因,在融合時應當減小其對融合結果的影響;當0

2.5 證據修正

證據的信任度描述的是其他證據對本證據的支持程度,支持度越大,與其他證據的變化趨勢就越相近,即本證據越可靠,在融合過程中不需要對其進行修改。證據虛假度描述的是和其他證據間的不一致性,如果證據的虛假度越大,那么與其他證據的沖突也就越大,證據的可靠性越差,因此,在融合前應證據進行修正以減小其在融合過程中的影響。

證據焦元分配的權重為:

τi=CrdPmi-Fmi

為保證τi>0,可以將τi加1,因此,權重系數可表示為:

τi=CrdPmi-γ×Fmi+1

(11)

對式(11)進行歸一化處理后得到:

(12)

本文以Ti作為權重系數對高沖突證據進行加權平均處理,以降低其對融合結果的影響。

在式(11)中γ的取值為1或2,取值的主要依據是沖突系數,在加權平均之前如果其沖突系數大于0.99,則γ的取值為2,如果小于等于0.99,則γ的取值為1。當證據的信任度較小時,應最大限度地降低高沖突證據的虛假度,提高其信任度。通過降低高沖突證據的虛假度也使其收斂速度得到了提高。對于高沖突證據的判定,本文通過設置閾值來進行判斷,其值根據經驗或經過訓練得到,計算步驟如下:

1)將n個證據利用式(3)轉換成基本概率賦值;

2)根據式(4)計算證據間的相似度,并根據式(6)計算證據的信任度,組成信任度矩陣;

3)利用式(10)計算證據的虛假度;

4)對得到的信任度和虛假度進行排序,根據所給閾值判定高沖突證據;

5)對高沖突的證據進行加權平均;

6)利用Dempster組合規則進行證據融合。

3 實驗與結果分析

為驗證本文算法的有效性,本文進行了2組實驗:第1組實驗數據來源于文獻[7],主要是將本文算法和典型算例及改進算法在融合結果的收斂速度上進行對比;第2組實驗數據來源于文獻[9],主要是對不含有高沖突證據和含有高沖突證據的情況進行對比。

3.1 實驗1

現有6個不同性質的傳感器對空中某個目標進行觀測識別,設辨識框架Θ={A:民航機,B:轟炸機,C:戰斗機},將5個傳感器對觀測目標所獲取的信息轉化為識別框架下的基本概率賦值,在識別框架下得到5條證據:

m1(A)=0.50,m1(B)=0.20,m1(C)=0.30

m2(A)=0.00,m2(B)=0.85,m2(C)=0.15

m3(A)=0.65,m3(B)=0.10,m3(C)=0.30

m4(A)=0.65,m4(B)=0.25,m4(C)=0.10

m5(A)=0.55,m5(B)=0.10,m5(C)=0.35

上述5條證據的實驗結果對比如表1所示。

表1 融合結果對比

從表1中最終的融合結果可以看出:Dempster方法和文獻[4]方法認為是轟炸機,從上述描述分析可知應當為民航機,計算結果與分析結果不同,因此,可判定前兩種方法存在一定的缺陷。在本文算法中,由于沖突系數k的值為0.999 1大于0.99,因此將參數γ的值設為2,在對證據的信任度和虛假度排序之后,將信任度小于0.5同時虛假度大于0.5的證據進行加權平均,其他證據不做調整。通過分析得出證據m1～m5都被認為是民航機,經過計算得出他們的信任度都大于0.5,虛假度較小。證據m2被認為轟炸機的可能性比較大,顯然與其他證據存在較大的分歧,因此,可斷定證據m2為不可靠證據,通過計算得到證據m2的信任度為0.148 4,虛假度為0.991 9,與分析結果相符,因此,判定證據m2為高沖突證據,應對其進行加權平均修正。

本文實驗運用7種方法對5組證據進行計算,其中前4種是比較傳統的方法,后3種是對傳統方法的改進,從實驗結果容易得出前兩種方法都存在一票否決的情況,與事實不相符,其他方法雖然不存在一票否決的情況,但另外通過5種方法的對比(如圖1所示)可以看出,本文方法在判定目標后的收斂速度較其他4種方法要快。

3.2 實驗2

沖突證據和無沖突證據的對比實驗使用如下數據:

無沖突證據:

m1(A)=0.5,m1(B)=0.2,m1(C)=0.3

m2(A)=0.5,m2(B)=0.3,m2(C)=0.2

m3(A)=0.6,m3(B)=0.1,m3(C)=0.3

m4(A)=0.8,m4(B)=0.1,m4(C)=0.1

高沖突證據:

m1(A)=0.5,m1(B)=0.2,m1(C)=0.3

m2(A)=0.0,m2(B)=0.9,m2(C)=0.1

m3(A)=0.6,m3(B)=0.1,m3(C)=0.3

m4(A)=0.8,m4(B)=0.1,m4(C)=0.1

2種情況下的實驗結果比較如表2所示。

表2 有沖突證據和無沖突證據情況的對比

實驗2通過對不含有沖突證據和高沖突證據情況進行實驗對比,得到以下結論:本文方法在沒有沖突證據時與傳統的D-S證據理論有相同的融合結果,其結果較其他4種方法也是最優的,因此可以得出,本文方法具有較好的使用性和較強的變通性。

通過上述2組實驗結果的比較可以看出,本文方法不僅在收斂速度上得到了大幅提高,同時適用于高沖突的證據和不含沖突的證據,在不含有沖突證據的情況下具有傳統D-S證據理論的優勢。

4 結束語

本文提出一種高沖突證據判定和修正方法。結合信任度和虛假度綜合判定是否為高沖突證據,對結果加權修正后再利用Dempster組合規則進行證據融合。實驗結果表明，本文方法能夠正確判斷高沖突證據，并且具有較快的收斂速度,可適用于大規模的證據融合。由于焦元較多時可能會出現數據爆炸現象，因此下一步研究將加入分類處理過程，得到有效信息后再進行證據融合。

[1] QUOST B,MASSON M H,DENCEUX T.Classifier Fusion in the Dempster-Shafer Framework Using Optimized t-norm Based Combination Rules[J].International Journal of Approximate Reasoning,2011,52(3):353-374.

[2] CHEN Q,WHITBROOK A,ROADKNIGHT U A C.Data Classification Using the Dempster-Shafer Method[J].Journal of Experimental & Theoretical Artificial Intelligence,2014,26(4):493-517.

[3] ZADEH L A.A Simple View of the Dempster-Shafer Theory of Evidence and Its Implication for the Rule of Combination[J].AI Magazine,1986,7(2):85-90.

[4] YAGER R R.On the Dempster-Shafer Framework and New Combination Rules[J].Information Sciences,1987,41(2):93-137.

[5] DANIEL M.The DSm Approach as a Special Case of the Dempster-Shafer Theory[M]//MELLOULI K.Symbolic and Quantitative Approaches to Reasoning with Uncertainty.Berlin,Germany:Springer,2007:381-392.

[6] 畢文豪,張 安,李 沖.基于新的證據沖突衡量的加權證據融合方法[J].控制與決策,2016,31(1):73-78.

[7] 宋亞飛,王曉丹,雷 蕾,等.基于信任度和虛假度的證據組合方法[J].通信學報,2015,36(5):102-107.

[8] 曲圣杰,程詠梅,潘 泉,等.沖突再分配DSmT及解決證據間矛盾的新方法[J].控制與決策,2009,24(12):1856-1860.

[9] 胡海亮,鐘求喜,劉 瀏.基于迭代合成的D-S證據理論改進方法[J].計算機應用研究,2016,33(10):2985-2987,3044.

[10] 盧正才,覃 征.證據合成的一般框架及高度沖突證據合成方法[J].清華大學學報(自然科學版),2011,51(11):1611-1615,1626.

[11] 柯小路,馬荔瑤,朱 儒,等.證據理論的模糊折扣方法[J].小型微型計算機系統,2015,36(2):285-289.

[12] 孫 全,葉秀清,顧偉康.一種新的基于證據理論的合成公式[J].電子學報,2000,28(8):117-119.

[13] MURPHY C K.Combining Belief Functions when Evidence Conflicts[J].Decision Support Systems,2000,29(1):1-9.

[14] 鄧 勇,施文康,朱振福.一種有效處理沖突證據的組合方法[J].紅外與毫米波學報,2004,23(1):27-32.

[15] 韓德強,楊 藝,韓崇昭.DS證據理論研究進展及相關問題探討[J].控制與決策,2014,29(1):1-11.