胡海亮　鐘求喜

(國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院　湖南 長沙 410073)

?

基于證據(jù)可信度的D-S理論改進(jìn)方法

胡海亮鐘求喜

(國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院湖南 長沙 410073)

摘要針對(duì)當(dāng)前D-S理論改進(jìn)方法中可信度計(jì)算不夠準(zhǔn)確的問題，通過引入證據(jù)源可靠度，提出一種新的證據(jù)可信度計(jì)算方法。給出基于新可信度計(jì)算方法的三個(gè)改進(jìn)合成公式，能夠處理高度沖突的證據(jù)，并快速收斂到合理結(jié)果。通過算例對(duì)可信度計(jì)算方法的準(zhǔn)確性和改進(jìn)合成公式的有效性進(jìn)行了驗(yàn)證。

關(guān)鍵詞證據(jù)理論合成規(guī)則沖突證據(jù)可信度

0引言

Dempster-Shafer(D-S)證據(jù)理論首先由Dempster[1]于1967年提出，后經(jīng)Shafer[2]系統(tǒng)化完善，成為一種重要的不確定性推理方法。證據(jù)理論是對(duì)經(jīng)典概率論的推廣，具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，能夠清楚地表示“不知道”和“不確定”的數(shù)據(jù)信息。在精確反映證據(jù)聚合程度方面具有很強(qiáng)的靈活性，并能得到較好的融合結(jié)果，已成為信息融合、模式識(shí)別和決策分析等領(lǐng)域重要的信息處理工具[17-20]。

但D-S證據(jù)理論存在一個(gè)突出問題，就是無法有效處理高度沖突的證據(jù)。國內(nèi)外學(xué)者針對(duì)這一問題進(jìn)行了大量研究和改進(jìn)，本文在總結(jié)分析現(xiàn)有研究成果的基礎(chǔ)上，給出了基于可信度的三個(gè)改進(jìn)的證據(jù)合成公式。這三個(gè)公式在處理高度沖突證據(jù)時(shí)，都能得到比較直觀合意的結(jié)果。

1D-S證據(jù)理論及改進(jìn)方法概述

在D-S證據(jù)理論中，辨識(shí)框架Θ={θ1,θ2,…,θn}是一個(gè)元素互不相容的可列集，基本概率賦值(BPA)是一個(gè)函數(shù)m:2Θ→[0,1]，并滿足以下條件：

不同的證據(jù)具有不同的基本概率賦值，當(dāng)有多條證據(jù)時(shí)，就可以通過Dempster合成規(guī)則進(jìn)行證據(jù)合成，合成公式如下：

(1)

其中A∈2Θ,A≠φ，表示證據(jù)中的焦元，K∈[0,1]，被稱為沖突因子，表示證據(jù)間的沖突程度。

由上述合成公式可知傳統(tǒng)的D-S證據(jù)理論無法合成K=1時(shí)的證據(jù)。但當(dāng)K→1時(shí)，也可能得到不合理的結(jié)果。Zadeh[3]給出了一個(gè)經(jīng)典的例子。兩個(gè)醫(yī)生對(duì)同一個(gè)病人進(jìn)行診斷，病人所患病癥可能為腦膜炎(M)、腦挫傷(C)和腦腫瘤(T)，則辨識(shí)框架Θ={M,C,T}，兩個(gè)醫(yī)生的診斷結(jié)果分別為：

m1(M)=0.99m1(T)=0.01

m2(C)=0.99m2(T)=0.01

此時(shí)K=0.9999，合成結(jié)果為：m(T)=1，很明顯不合理。

對(duì)式(1)進(jìn)行變換可得：

(2)

從式(2)可以看出Dempster合成規(guī)則將沖突因子(實(shí)際上就是合成后空集的基本概率賦值)，按照非空焦元所占的不同比重進(jìn)行了再分配。這樣做是因?yàn)镈-S證據(jù)理論是基于閉世界的假設(shè)，合成后空集的基本概率賦值要置零。由于沖突證據(jù)在合成的過程中會(huì)相互削弱對(duì)應(yīng)焦元的基本概率賦值，相應(yīng)焦元在沖突因子分配時(shí)得到的份額就會(huì)很少，特殊情況下為零。這也是Zadeh特例產(chǎn)生的根本原因，即在證據(jù)合成中出現(xiàn)了一票否決的現(xiàn)象。

針對(duì)上述問題，國內(nèi)外學(xué)者提出了大量改進(jìn)方法，但基本思想可以分為三類。第一類是修改Dempster組合規(guī)則。根據(jù)修改程度的不同又可以分為以下幾種：①完全推倒重建，如文獻(xiàn)[4,5]等，雖然這些方法在處理沖突證據(jù)時(shí)表現(xiàn)出了更好的效果，但缺乏堅(jiān)實(shí)的數(shù)學(xué)理論支撐；②基于開世界假設(shè)的方法，打破傳統(tǒng)的認(rèn)知框架，把沖突因子分配給了空集，如文獻(xiàn)[6]等，他們認(rèn)為D-S證據(jù)理論中的辨識(shí)框架不夠完備，空集包含了尚未認(rèn)識(shí)的元素，這些方法超出了人們的認(rèn)知范疇，也不能從根本上解決問題；③在閉世界假設(shè)下修改沖突因子分配方式的方法，如文獻(xiàn)[7]，把沖突因子全部分配給了辨識(shí)框架，處理方式顯得保守，Dubois等[8]把沖突因子只分配給了產(chǎn)生沖突的焦元，孫全等[9]、李弼程等[10]則把沖突因子按一定比重分配給了所有焦元，效果都要優(yōu)于文獻(xiàn)[7]。第二類是修改證據(jù)模型。文獻(xiàn)[11-13]，基本思想是通過平均或加權(quán)的方式重置證據(jù)的基本概率賦值，削弱證據(jù)之間的沖突程度，但文獻(xiàn)[11]沒有考慮證據(jù)的重要性問題，導(dǎo)致收斂速度慢，文獻(xiàn)[12，13]雖然都考慮了證據(jù)權(quán)值，但單純基于證據(jù)體本身計(jì)算出的權(quán)值不一定可靠。第三類方法是修改組合規(guī)則和證據(jù)模型相結(jié)合的方法。如文獻(xiàn)[14,15]，這些方法都是先計(jì)算證據(jù)的可信度，根據(jù)證據(jù)的可信度修正基本概率賦值函數(shù)，在合成時(shí)再按照一定的比重分配沖突因子，但在證據(jù)可信度的計(jì)算上仍是基于證據(jù)體本身，忽略了證據(jù)源的可靠性。

針對(duì)現(xiàn)有方法中存在的問題，本文給出了證據(jù)可信度新的計(jì)算方法和三種改進(jìn)的合成公式，并用算例驗(yàn)證了它們的有效性。

2綜合證據(jù)源可靠度的可信度計(jì)算方法

當(dāng)前很多研究基于證據(jù)之間的距離計(jì)算出證據(jù)的可信度[21-25]，但是這個(gè)可信度只能反應(yīng)每個(gè)證據(jù)在一次融合中與其他證據(jù)的相似程度，沒有考慮證據(jù)來源的可靠性，即證據(jù)的歷史可信度。因此并不能準(zhǔn)確反應(yīng)證據(jù)的可信程度，應(yīng)該綜合這兩個(gè)方面來計(jì)算證據(jù)的可信度。我們把基于證據(jù)距離的可信度稱作證據(jù)體支持度，記為Su，把歷史可信度稱作證據(jù)源可靠度，記為Re，最終的證據(jù)可信度記為Cr。

2.1證據(jù)體支持度的計(jì)算方法

證據(jù)體的支持度同現(xiàn)有文章中基于證據(jù)距離的可信度是一個(gè)概念，因此可以采用同樣的計(jì)算方法，本文采用Jousselme[16]距離，它能夠很好地刻畫不同證據(jù)之間的差異性。

設(shè)辨識(shí)框架Θ={θ1,θ2,…,θn}，2Θ={A1,A2,…,A2n}，N個(gè)證據(jù)e1,e2,…,eN及其基本概率賦值函數(shù)m1,m2,…,mN，證據(jù)體支持度的計(jì)算方法如下：

第1步計(jì)算證據(jù)之間的Jousselme距離：

第2步計(jì)算證據(jù)之間的相似度sij及每個(gè)證據(jù)的總相似度Si：

第3步進(jìn)行歸一化處理，得到每個(gè)證據(jù)的證據(jù)體支持度：

2.2證據(jù)源可靠度的計(jì)算方法

一個(gè)可靠性高的證據(jù)源應(yīng)總能以較大概率辨識(shí)目標(biāo)，并具有很強(qiáng)的抗干擾能力。我們可以通過構(gòu)造訓(xùn)練數(shù)據(jù)，測試出證據(jù)源的辨識(shí)正確率，用其表示證據(jù)源可靠度。假設(shè)數(shù)據(jù)集Da={o1,o2,…,oλ}，N個(gè)證據(jù)源，則證據(jù)源可靠度的計(jì)算方法如下：

第1步從Da中任取一目標(biāo)oi，經(jīng)N個(gè)證據(jù)源辨識(shí)得到N個(gè)辨識(shí)函數(shù)；

第2步判斷每個(gè)辨識(shí)函數(shù)中目標(biāo)焦元的基本概率賦值是否最大，若是，相應(yīng)證據(jù)源的辨識(shí)成功數(shù)加1；

第3步重復(fù)第1步、第2步，直到所有的目標(biāo)辨識(shí)完畢，得到每個(gè)證據(jù)源總的辨識(shí)成功數(shù)nj；

2.3證據(jù)可信度的計(jì)算及BPA的修正

證據(jù)體支持度反映的是此次融合的每條證據(jù)的可信程度，而證據(jù)源可靠度可以看成每條證據(jù)的歷史可信度，綜合這兩個(gè)方面給出證據(jù)可信度的計(jì)算公式：

(3)

其中，α+β=1,α≥0,β≥0。α,β是權(quán)值，可以根據(jù)我們對(duì)證據(jù)體支持度和證據(jù)源可靠度的看重程度調(diào)整大小，如α=0，此時(shí)只考慮證據(jù)源可靠度，反之β=0，則只考慮證據(jù)體支持度。

根據(jù)每個(gè)證據(jù)可信度可按照Shafer折扣法修正證據(jù)的基本概率賦值函數(shù)：

(4)

3證據(jù)合成公式改進(jìn)

借鑒文獻(xiàn)[10]方法，給出的第一個(gè)合成公式：

(5)

第二個(gè)改進(jìn)的合成公式是基于修改證據(jù)模型和合成規(guī)則相結(jié)合的思想，通過式(4)修正證據(jù)模型后的公式：

(6)

第三個(gè)改進(jìn)合成公式類似文獻(xiàn)[13]方法：

(7)

4算例驗(yàn)證

下面用算例來驗(yàn)證這三個(gè)改進(jìn)合成公式的有效性。對(duì)于Zadeh給出的例子，在不考慮證據(jù)源可靠度的情況下，式(5)和式(6)都能夠得到比較合理的融合結(jié)果，但式(7)需要額外證據(jù)的支持?，F(xiàn)在假設(shè)獲得了兩個(gè)醫(yī)生的歷史診斷成功率分別為：0.95、0.65。根據(jù)證據(jù)源可靠度的定義，歷史診斷成功率可以作為他們診斷結(jié)果的證據(jù)源可靠度，由于兩條證據(jù)的相互距離是相等的，在證據(jù)可信度的計(jì)算中可以不考慮證據(jù)支持度，令α=0，則用三個(gè)改進(jìn)公式得到的融合結(jié)果如表1所示。

表1　對(duì)Zadeh特例的融合結(jié)果

三個(gè)改進(jìn)公式給出融合結(jié)果都比較合理，其中式(7)的收斂速度最快，但對(duì)腫瘤的基本概率賦值略有增大，式(6)收斂速度居中，對(duì)腫瘤的基本概率賦值也有所下降，相對(duì)更為合理。

第二個(gè)算例的數(shù)據(jù)來自文獻(xiàn)[13]，為計(jì)算簡單，令β=0，這時(shí)證據(jù)可信度就等于證據(jù)體支持度，式(7)退化為文獻(xiàn)[13]。假設(shè)融合系統(tǒng)的辨識(shí)框架為Θ={A,B,C}，框架中各命題元素表示目標(biāo)類型，5條證據(jù)的基本概率賦值函數(shù)如下：

利用本文的三種改進(jìn)合成公式和其他方法的合成結(jié)果如表2所示。

表2　β=0時(shí)的融合結(jié)果

由于第二條證據(jù)的存在，整個(gè)證據(jù)體的沖突因子很大，但證據(jù)體總體上支持辨識(shí)目標(biāo)為A。從融合結(jié)果上看，D-S方法、文獻(xiàn)[7]方法都不能得到好的融合結(jié)果。其他融合方法中目標(biāo)A的基本概率賦值都是最大。由于引入了證據(jù)可信度，相比文獻(xiàn)[10]方法，本文式(5)的收斂速度要快，第二個(gè)改進(jìn)公式雖然從修改證據(jù)模型和組合規(guī)則兩個(gè)方面進(jìn)行了改進(jìn)，但融合效果不是太好。在此次融合中比較三類修改方法，修改證據(jù)源的方法效果最好，換成其他數(shù)據(jù)是否還是這樣的結(jié)果有待驗(yàn)證。

在上面的證據(jù)中第二條證據(jù)同其他證據(jù)的差異較大，但這并不能說明該證據(jù)是錯(cuò)誤的，還要看其證據(jù)源可靠度。如果該證據(jù)的證據(jù)源可靠度也很低，則可推斷其是一條錯(cuò)誤的證據(jù)。而我們通過引入證據(jù)源可靠度就能更好地削弱錯(cuò)誤證據(jù)的干擾，假設(shè)五條證據(jù)的證據(jù)源可靠度分別為：{0.8,0.6,0.9,0.9,0.9}，同時(shí)令：α=β=0.5，由于其他融合算法都沒有考慮證據(jù)源可靠度，它們的融合結(jié)果不會(huì)改變，而用本文的三種方法得到的融合結(jié)果如表3所示。很明顯，通過引入證據(jù)源可靠度，表2比表3的融合效果都要更好。

表3　β≠0時(shí)的融合結(jié)果

上述計(jì)算是假設(shè)第二條證據(jù)的證據(jù)源可靠度很低，但這并不一定成立。相反，可能第二條證據(jù)的證據(jù)源可靠度很高，而其他證據(jù)源的可靠度很低?？紤]一種極端情況，產(chǎn)生第二條證據(jù)的證據(jù)源總能成功識(shí)別目標(biāo)，其他證據(jù)源成功辨識(shí)目標(biāo)的概率都很低，假設(shè)五條證據(jù)的證據(jù)源可靠度分別為：{0.3,1.0,0.3,0.3,0.3}，此時(shí)正確的目標(biāo)就很可能是C，其他的算法都不能得到合理的結(jié)果，若令α=0，則用式(5)會(huì)得到如下的結(jié)果：

m(A)=0.31159m(B)=0.15809m(C)=0.53032

融合結(jié)果比較合理。雖然這是極端情況，但從一定程度上反映了引入證據(jù)源可靠度的必要性和新方法計(jì)算出的證據(jù)可信度的準(zhǔn)確性。

5結(jié)語

傳統(tǒng)的D-S證據(jù)理論在處理高沖突證據(jù)時(shí)常會(huì)得到反直觀的結(jié)果。本文基于證據(jù)可信度提出的三種改進(jìn)方法在沖突證據(jù)的處理上能夠得到較好的融合效果，而且在證據(jù)可信度的計(jì)算中考慮了證據(jù)源的可靠性。相較其他方法中的證據(jù)可信度能夠更加準(zhǔn)確地衡量每個(gè)證據(jù)的可信程度，也使融合系統(tǒng)更加靈活。

理論上通過調(diào)整證據(jù)體支持度和證據(jù)源可靠度的權(quán)值總能得到合理的融合結(jié)果，但如何確定權(quán)值還需要尋找一個(gè)客觀的計(jì)算方法。三個(gè)改進(jìn)公式總體上都是有效的，但在不同的場景表現(xiàn)效果有些差別，需要根據(jù)實(shí)際情況和具體需求選擇合適的改進(jìn)公式。

參考文獻(xiàn)

[1] Dempster A P.Upper and lower probabilities induced by a multivalued mapping[J].Annals of mathematical statistics,1967,38(2):325-339.

[2] Shafer G.A mathematical theory of evidence[M].Princeton:Princeton University Press,1976.

[3] Zadeh L.A Review of books:A mathematical theory of evidence[J].AI Magazine,1984,5(3):81-83.

[4] Tazid Ali,Palash Dutta,Hrishikesh Boruah.A New Combination Rule for Conflict Problem of Dempster-Shafer Evidence Theory[J].International Journal of Energy, Information and Communications,2012,3(1):35-40.

[5] 鄭孝勇,姚景順,劉維國,等.一種數(shù)據(jù)融合算法的初步提出[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2003,33(1):54-59.

[6] 王俊松,李建林.D-S證據(jù)理論改進(jìn)方案綜述[J].信息化研究,2011,37(6):4-6.

[7] Yager R.On the Dempster—Shafer framework and new combination rules[J].Information Sciences,1987,41(6):93-137.

[8] Dubois D,Prade H.A survey of belief revision and updating rules in various uncertainty models[J].International Journal of Intelligent Systems,1994,9(6):61-100.

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

[10] 李弼程,王波,魏俊,等.一種有效的證據(jù)理論合成公式[J].數(shù)據(jù)采集與處理,2002,17(1):34-36.

[11] Murphy C.Combining belief functions when evidence conflicts[J].Decision Support systems,2000,29(7):1-9.

[12] Deng Y,Shi W K,Zhu Z F,et al.Combining belief functions based on distance of evidence[J].Decision Support Systems,2004,38(3):489-493.

[13] 劉海燕,趙宗貴,劉熹.D-S證據(jù)理論中沖突證據(jù)的合成方法[J].電子科技大學(xué)學(xué)報(bào),2008,37(5):701-704.

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

[15] 李仕峰,楊乃定,張?jiān)埔?區(qū)分證據(jù)重要性及分配證據(jù)沖突的新方法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(7):1867-1872.

[16] Jousselme A L,Grenier D,Bosse E.A new distance between two bodies of evidence[J].Information Fusion,2001,2(2):91-101.

[17] 肖人彬,王雪,費(fèi)奇,等.相關(guān)證據(jù)合成方法的研究[J].模式識(shí)別與人工智能,1993,6(3):227-234.

[18] 徐從富,耿衛(wèi)東,潘云鶴.面向數(shù)據(jù)融合的DS方法綜述[J].電子學(xué)報(bào),2001,29(3):393-396.

[19] 尹慧琳,王磊.D-S證據(jù)推理改進(jìn)方法綜述[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(4):22-24.

[20] 韓德強(qiáng),楊藝,韓崇昭.DS證據(jù)理論研究進(jìn)展及相關(guān)問題探討[J].控制與決策,2014,29(1):1-11.

[21] 王進(jìn)花,吳迪,曹潔,等.基于證據(jù)分類的加權(quán)沖突證據(jù)組合[J].計(jì)算機(jī)科學(xué),2013,40(1):247-250.

[22] 張克芳,王萬請(qǐng),生擁宏,等.一種新的證據(jù)復(fù)合折扣合成方法[J].信息工程大學(xué)學(xué)報(bào),2014,15(2):219-225.

[23] 張盛剛,李巍華,丁康.基于證據(jù)可信度的證據(jù)合成新方法[J].控制理論與應(yīng)用,2009,26(7):812-814.

[24] 李仕峰,楊乃定,張?jiān)埔?區(qū)分證據(jù)重要性及分配證據(jù)沖突的新方法[J].系統(tǒng)工程理論與實(shí)踐,2013,33(7):1867-1872.

[25] 黃青,陳以,陳燕蘭.一種改進(jìn)的基于權(quán)重系數(shù)的證據(jù)合成方法[J].傳感器與微系統(tǒng),2012,31(7):14-16.

AN IMPROVED METHOD FOR D-S THEORY BASED ON EVIDENCE CREDIBILITY

Hu HailiangZhong Qiuxi

(School of Computer,National University of Defence Technology,Changsha 410073,Hunan,China)

AbstractAiming at the inaccuracy of credibility calculation in current D-S theory improvement methods, we propose a new calculation method for evidence credibility by introducing evidence source reliability, and then gave three improved synthetic formulas, which are based on new method, capable of handling the highly conflicting evidence and fast converging to a reasonable outcome. Through numerical examples we verified the accuracy of credibility calculation method and the effectiveness of improved synthetic formulas.

KeywordsEvidence theoryCombination rulesConflicting evidencesCredibility

收稿日期：2014-11-21。國家自然科學(xué)基金項(xiàng)目(61202482，6147 2437)；國家高技術(shù)研究發(fā)展計(jì)劃項(xiàng)目(2012AA01A5060)。胡海亮，碩士生，主研領(lǐng)域：信息融合，信息安全。鐘求喜，研究員。

中圖分類號(hào)TP3

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.06.003