D－S證據(jù)理論中沖突處理的新方法

汪永偉，劉育楠，楊英杰，司 成，劉 帥

（1.信息工程大學(xué)，河南 鄭州450004；2.河南省信息安全重點(diǎn)實(shí)驗(yàn)室，河南 鄭州450004）

0 引 言

D－S證據(jù)理論是貝葉斯理論的擴(kuò)展，又稱Dempster－Shafer理論 （DST），由Dempster于1967年提出，Shafer將其發(fā)展并整理成一套完整的數(shù)學(xué)推理理論[1，2]。證據(jù)理論具有嚴(yán)密的概率理論基礎(chǔ)、強(qiáng)大的不確定性描述能力和系統(tǒng)的合成與推理規(guī)則等獨(dú)特的屬性，在醫(yī)療診斷、風(fēng)險(xiǎn)評(píng)估、故障分析等領(lǐng)域得到了廣泛應(yīng)用[3－7]。但是，在高沖突證據(jù)合成過程中出現(xiàn)了一些不符合常理的現(xiàn)象。針對(duì)此問題，國內(nèi)外學(xué)者提出了許多DST的改進(jìn)方法[8－14]。孫全等提出了基于證據(jù)可信度的DST組合規(guī)則改進(jìn)方法，其本質(zhì)上是通過證據(jù)可信度來吸收證據(jù)沖突[9]。Yager等提出了將沖突信任在全集進(jìn)行分配的方法，采用與運(yùn)算對(duì)不沖突證據(jù)進(jìn)行合成[10]。Murphy等提出了先將證據(jù)的基本概率分配進(jìn)行平均處理，然后再進(jìn)行合成的方法[1]。梁昌勇等基于對(duì)證據(jù)一致性的考慮，提出了一種基于一致性證據(jù)沖突的證據(jù)合成規(guī)則[9]。Yee等提出了結(jié)合合取規(guī)則與析取規(guī)則的合成方法，在高沖突環(huán)境下，其將沖突信任主要分配給沖突相關(guān)焦元的并集，在低沖突環(huán)境下，其將沖突信任主要分配給沖突相關(guān)焦元的交集[11]。

綜上所述，現(xiàn)有的證據(jù)理論改進(jìn)方法大致可以分為兩類[13]:一是修改證據(jù)本身的方法，降低不可靠證據(jù)對(duì)融合結(jié)論的影響。這種方法在一定程度上解決了悖論問題，但是修改證據(jù)源會(huì)造成信息的丟失，使得人為因素參與證據(jù)組合，可能會(huì)扭曲證據(jù)本身的意圖。二是通過對(duì)沖突部分的信任在冪集空間或在相關(guān)元素進(jìn)行重新分配，從而消除各種悖論帶來的影響。這種方法本質(zhì)上是對(duì)DST合成規(guī)則的擴(kuò)張和修正，破壞了合成交換律和結(jié)合律特性，在證據(jù)源較多時(shí)，面臨合成效率和合成結(jié)論適應(yīng)性性等問題。為此，本文提出了一種新的證據(jù)合成方法，通過加性策略計(jì)算沖突焦元的支持信度，然后把證據(jù)中焦元的支持信度作為新的基本概率分配。實(shí)驗(yàn)表明，該方法在合成的準(zhǔn)確性和適應(yīng)性等方面優(yōu)于現(xiàn)有典型方法。

1 證據(jù)理論的基本概念及其悖論

證據(jù)理論是一種廣泛被采用處理互補(bǔ)信息和不確定信息的數(shù)據(jù)融合理論[14]。證據(jù)理論最重要的部分是識(shí)別框架（frame of discernment，F(xiàn)OD）和基 本 概 率 分 配 （basic probability assignment，BPA）。

定義1 識(shí)別框架Θ表示一個(gè)互斥又可窮舉元素的集合，即 Θ＝｛θ1，θ2，…θn｝ ，2θ表示 Θ所有子集的集合。

定義2 基本概率分配BPA是一個(gè)映射m:2Θ→[0，1]，且滿足下列條件

定義3 Dempster規(guī)則形式化定義如下:

設(shè)識(shí)別框架Θ的n個(gè)證據(jù)為 （E1，E2，…，En），其對(duì)應(yīng)的基本信任分配函數(shù)為mi（i＝1，2，3…，n），則對(duì)這n個(gè)證據(jù)得出的組合證據(jù)信度分配函數(shù)為

例1 設(shè)識(shí)別框架Θ＝｛A，B，C｝，已知兩條證據(jù)如表1所示。

表1 基本概率分配

通過直覺可以判定，證據(jù)1和證據(jù)2之間高度沖突，其支持的命題分別為A和C。依據(jù)D－S證據(jù)理論組合規(guī)則，對(duì)證據(jù)1和證據(jù)2進(jìn)行融合，結(jié)果為

可以看出，該結(jié)論是與直覺判定結(jié)果不符，兩個(gè)證據(jù)分別高度支持的命題A和命題C在融合后所分配的信任變?yōu)榱?，而原本信任度很低的命題B在合成后所獲得的信任達(dá)到了1，合成結(jié)果與常理完全相悖。這就是經(jīng)典的Zadeh悖論。

2 新的證據(jù)組合規(guī)則

悖論問題之所以產(chǎn)生，究其原因是因?yàn)榻?jīng)典證據(jù)理論中組合規(guī)則所采用的乘性策略過于偏激[12]。在現(xiàn)實(shí)生活中的群體決策過程中，當(dāng)多個(gè)專家進(jìn)行決策時(shí)，要對(duì)各專家的意見進(jìn)行綜合折衷考慮，拋棄彼此之間的某些分歧，從而獲得基本一致的觀點(diǎn)[14]。證據(jù)融合的過程類似于群體決策過程，每個(gè)證據(jù)相當(dāng)于一個(gè)專家。為此，本文提出了一種新的證據(jù)合成方法，即通過加性策略計(jì)算沖突焦元的支持信度，然后把證據(jù)中焦元的支持信度作為新的基本概率分配。設(shè)識(shí)別框架 Θ＝｛A1，A2，…，Ai，…，An｝，設(shè)有證據(jù)m1，m2則具體合成法則如下

m′（Ai）反映了兩證據(jù)對(duì)焦元Ai的支持程度，對(duì)其進(jìn)行歸一化處理，則可得兩證據(jù)對(duì)焦元Ai的支持信度

SUP（Ai）綜合的反映了兩證據(jù)對(duì)各焦元的認(rèn)可程度，因此可將其作為合成結(jié)論中的基本概率分配。即

若有n個(gè)證據(jù)E＝｛e1，e2，…，en｝參與合成，可采取兩兩證據(jù)合成的方法，具體合成算法如圖1所示。

依據(jù)新的合成規(guī)則，例1的合成結(jié)果如下

新合成方法的結(jié)果與直覺上的認(rèn)識(shí)是一致的，比較合理的表達(dá)了原始證據(jù)中信任的分布情況，避免了悖論問題的產(chǎn)生。由于合成過程中采用了加性策略，新的合成方法保持了原始合成規(guī)則中了交換律和結(jié)合律特性。

3 實(shí)例仿真

圖1 多證據(jù)合成算法

為了檢驗(yàn)本文所提出的組合方法的有效性，本文進(jìn)行了仿真實(shí)驗(yàn)，將本文的組合方法與典型的組合算法進(jìn)行對(duì)比分析與驗(yàn)證。實(shí)驗(yàn)中，分別選擇現(xiàn)有文獻(xiàn)中具有高沖突和低沖突特征的兩組算例[9，12]，識(shí)別框架為 Θ＝｛A，B，C｝。選擇這兩組算例的目的有兩個(gè):①方便與現(xiàn)有算法的對(duì)比，檢驗(yàn)本文算法與典型算法的優(yōu)劣。②分別驗(yàn)證算法在高沖突和低沖突環(huán)境下的性能，檢驗(yàn)本文算法的適應(yīng)性。

3.1 實(shí)驗(yàn)設(shè)置與實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)1:沖突程度較低的4組證據(jù)的基本概率分配情況如表2所示，各種證據(jù)合成算法的實(shí)驗(yàn)結(jié)果見表3。

實(shí)驗(yàn)2:沖突程度較高的4組證據(jù)的基本概率分配情況如表4所示，各種證據(jù)合成算法的實(shí)驗(yàn)結(jié)果見表5。

表2 4組低沖突證據(jù)的基本概率分配

表3 7種合成方法結(jié)果

3.2 實(shí)驗(yàn)分析與對(duì)比

楊風(fēng)暴[15]認(rèn)為，評(píng)價(jià)證據(jù)理論組合方法的優(yōu)劣主要從以下兩個(gè)方面來衡量:

表4 4組高沖突證據(jù)的基本概率分配

表5 7種合成方法結(jié)果

衡量標(biāo)準(zhǔn)一，看組合結(jié)果是否符合人們的邏輯推理，即是否能夠得到所預(yù)期的結(jié)論。

衡量標(biāo)準(zhǔn)二，看證據(jù)合成后不確定性有沒有減少，即單元素焦元的可信度之和有沒有增大。

衡量標(biāo)準(zhǔn)一實(shí)際上是檢驗(yàn)組合方法是否能夠避免Zadeh悖論，用于衡量組合方法的免疫能力，本文稱之為ZI（Zadeh Immunity）特性。衡量標(biāo)準(zhǔn)二實(shí)際上是檢驗(yàn)組合方法合成結(jié)果的區(qū)分能力，可信度之和越大，組合方法的區(qū)分能力越強(qiáng)，方法的性能越好，本文稱之為區(qū)分度。各種組合方法的Zadeh免疫性和區(qū)分度的比較結(jié)果如表6所示。

表6 7種合成方法ZI特性、區(qū)分度對(duì)比

表3和表5中，傳統(tǒng)的Dempster組合方法的合成結(jié)果明顯與直覺相悖，ZI特性較差；隨著證據(jù)的增多，Yager方法為全集分配的信任越來越大，單焦元所分配的信任逐步減小，決策結(jié)果的未知程度逐步增大；孫全方法和梁昌勇方法的變化情況基本相同，但是由于在處理沖突中，這兩種方法將較多的信任分配給了全集，單焦元所分配的信任較少，導(dǎo)致合成結(jié)果的收斂速度較慢。表3中，在證據(jù)明顯支持命題A的情況下，孫全方法為命題A所分配的信任僅為0.2132，明顯與直覺相悖。表5中，在高沖突證據(jù)合成時(shí)，梁昌勇方法為全集分配的信任更多，導(dǎo)致最終無法進(jìn)行決策；Tazid方法雖然在高沖突證據(jù)合成時(shí)獲得了較好的決策能力，但是在低沖突證據(jù)合成時(shí)效果并不理想；Yee方法由于采取了折扣操作，隨著證據(jù)的增加，單焦元分配的信任越來越少，信任逐步向全集擴(kuò)散，兩組測(cè)試分別達(dá)到了0.2421和0.2452，區(qū)分能力較差。

通過實(shí)驗(yàn)兩組結(jié)果可以看出，本文方法由于采用了加性策略，高沖突證據(jù)合成時(shí)采用的合成策略較為溫和，因此能夠有效避免悖論問題的產(chǎn)生。無論是在高沖突環(huán)境還是在低沖突環(huán)境下，本文方法都獲得了較為合理的基本概率分布，表現(xiàn)出了較好的融合能力，在合成結(jié)果的ZI特性、區(qū)分度和適應(yīng)性等方面優(yōu)于對(duì)比方法。

4 結(jié)束語

在處理高度沖突的證據(jù)信息時(shí)，經(jīng)典D－S證據(jù)理論在會(huì)產(chǎn)生有悖常理結(jié)論的情況，針對(duì)此問題，本文提出了一種新的證據(jù)合成方法。該方法借鑒了專家決策中的折衷思想，通過加性策略計(jì)算沖突焦元的支持信度，以支持信度作為合成結(jié)論中的基本概率分配，最后通過兩兩依次合成的方法實(shí)現(xiàn)多證據(jù)的合成。實(shí)例分析和實(shí)驗(yàn)結(jié)果表明，新的合成方法能夠有效解決零元悖論問題，且在合成的結(jié)果的準(zhǔn)確性、區(qū)分度和適應(yīng)性等方面優(yōu)于現(xiàn)有典型方法。

[1]Jean Dezert，Pei Wang，Albena Tchamova.On the validity of dempster－shafer theory[C]／／15th International Conference on Information Fusion，2012:655－660.

[2]HU Changhua，SI Xiaosheng，ZHOU Zhijie，et al.An improved D－S algorithm under the new measure criteria of evidence conflict[J].Acta Electronica Sinica，2009，37 （7）:1578－1583（in Chinese）.[胡昌華，司小勝，周志杰，等.新的證據(jù)沖突衡量標(biāo)準(zhǔn)下的 D－S改進(jìn)算法[J].電子學(xué)報(bào)，2009，37 （7）:1578－1583.]

[3]Andino Maseleno，Md Mahmud Hasan.The dempster－shafer theory algorithm and its application to insect diseases detection[J].International Journal of Advanced Science and Technology，2013 （50）:111－120.

[4]Pasha E，Mostafaei H R，Khalajc M，Khalaj F.Fault diagnosis of engine using information fusion based on dempster－shafer theory[J].Journal of Basic and Applied Scientific Research，2012，2 （2）:1078－1085.

[5]Chiara Foglietta，Andrea Gasparri，Stefano Panzieri.A networked evidence theory framework for critical infrastructure modeling[C]／／IFIP Advances in Information and Communication Technology，2012:205－215.

[6]Wen Jiang，Deqiang Han，Xin Fan，et al.Research on threat assessment based on dempster－shafer evidence theory[C]／／Green Communications and Networks，2012:975－984.

[7]Fuping Zeng，Manyan Lu，Deming Zhong.Using d－s evidence theory to evaluation of confidence in safety case[J].Journal of Theoretical and Applied Information Technology，2013，47（1）:184－189.

[8]FENG Haishan，XU Xiaobin，WEN Chenglin.A new fusion method of conflicting interval evidence based on the similarity measure of evidence[J].Journal of Electronics ＆Information Technology，2012，34 （4）:851－857 （in Chinese）.[馮海山，徐曉濱，文成林.基于證據(jù)相似性度量的沖突性區(qū)間證據(jù)融合方法[J].電子與信息學(xué)報(bào)，2012，34 （4）:851－857.]

[9]LIANG Changyong，YE Chunsen，ZHANG Enqiao.An evidence combination method based on consistence of conflict[J].Chinese Journal of Management Science，2010，18 （4）:152－156 （in Chinese）.[梁昌勇，葉春森，張恩橋.一種基于一致性證據(jù)沖突的證據(jù)合成方法[J].中國管理科學(xué)，2010，18 （4）:152－156.]

[10]Yager R R.On the fusion of imprecise uncertainty measures using belief structures[J].Information Sciences，2011，181（15）:3199－3209.

[11]Yee Leung，Nan－Nan Ji，Jiang－Hong Ma.An integrated information fusion approach based on the theory of evidence and group decision－making[J].Information Fusion，2012，8（2）:1－13.

[12]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.

[13]KANG Bingyi，LI Ya，DENG Yong，et al.Determination of basic probability assignment based on interval numbers and its application[J].Acta Electronica Sinica，2012，40 （6）:1092－1096（in Chinese）.[康兵義，李婭，鄧勇，等.基于區(qū)間數(shù)的基本概率指派生成方法及應(yīng)用[J].電子學(xué)報(bào)，2012，40 （6）:1092－1096.]

[14]Fu Chao，Shanlin Yang.Group consensus based on evidential reasoning approach using interval－valued belief structures[J].Knowledge－Based Systems，2012 （35）:201－210.

[15]YANG Fengbao，WANG Xiaoxia.Combination of conflict for D－S evidence theory[M].Beijing:National Defense Industry Press，2010 （in Chinese）.[楊風(fēng)暴，王肖霞.D－S證據(jù)理論的沖突證據(jù)合成方法[M].北京:國防工業(yè)出版社，2010.]