利用復(fù)合型沖突表示的快速加權(quán)證據(jù)融合方法*

白東穎，王剛，李松，姚小強

（1.第二炮兵工程大學(xué)，西安710025；2.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安710051）

利用復(fù)合型沖突表示的快速加權(quán)證據(jù)融合方法*

白東穎1，2，王剛2，李松2，姚小強2

（1.第二炮兵工程大學(xué)，西安710025；2.空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安710051）

針對經(jīng)典D-S證據(jù)理論在處理大規(guī)模沖突證據(jù)組合時的悖論問題及計算量指數(shù)增長問題，提出了一種利用經(jīng)典沖突系數(shù)與證據(jù)距離共同度量沖突大小的快速加權(quán)融合方法。該方法通過分析單一沖突表示方法的不足，提出了復(fù)合沖突系數(shù)，同時，給出了證據(jù)中心及當(dāng)前中心距離的定義，并用當(dāng)前中心距離與沖突系數(shù)一起確定證據(jù)權(quán)重。算例實驗結(jié)果表明本算法有效地解決了經(jīng)典證據(jù)理論中的悖論問題并顯著地提高了融合速度。

證據(jù)理論，沖突系數(shù)，證據(jù)中心，中心距離

0 引言

D-S證據(jù)理論［1-2］作為一種不確定性推理方法，通過引入信任函數(shù)，區(qū)分了不確定與不知道的差異，在多源信息融合中具有廣泛的應(yīng)用。然而，D-S理論在對高沖突證據(jù)組合時，會出現(xiàn)有悖人類直覺的結(jié)論［3-4］。國內(nèi)外學(xué)者提出的改進方法總的來說可以分為3類：修改傳統(tǒng)證據(jù)理論模型框架、修改證據(jù)組合規(guī)則、修改證據(jù)源模型。

修改證據(jù)源模型的代表人物是Murphy［5］和Haenni［6］。他們認為修改證據(jù)源方法較之于修改模型框架及組合規(guī)則更為合理。因此，本文從修改證據(jù)源角度來處理D-S規(guī)則組合時的悖論問題。證據(jù)源修正最具代表性的是Murphy平均法，但該方法并未考慮各個證據(jù)之間的關(guān)聯(lián)。

在Murphy基礎(chǔ)上，依據(jù)各種方法來量化證據(jù)間的沖突進而獲得證據(jù)可信度作為修改證據(jù)源的權(quán)重指標(biāo)是多數(shù)改進方法的思路［7-9］，但這些方法僅從單一角度對沖突進行表示，有時會出現(xiàn)“死角”現(xiàn)象；同時，衡量沖突往往需要用證據(jù)間距離進行相似性度量［10-11］，當(dāng)證據(jù)規(guī)模較大時，會出現(xiàn)計算量指數(shù)增長。

基于以上兩方面問題，本文嘗試?yán)媒?jīng)典證據(jù)理論中的沖突系數(shù)［1］與證據(jù)距離［12］共同度量沖突大小，進而獲取證據(jù)權(quán)重，用修改后的證據(jù)源進行合成。同時提出，用中心距離代替兩兩證據(jù)距離，縮短大規(guī)模證據(jù)融合時的計算量。

1 D-S證據(jù)理論及典型悖論問題

1.1 Dempster-Shafer組合規(guī)則［2］

設(shè)Θ為一識別框架，則函數(shù)m：2Θ→［0，1］滿足以下條件①m（φ）=0；②0≤m（A）≤1；③=1；則稱m為識別框架Θ上的基本置信分配（Basic Belief Assignment，BBA）函數(shù)。

定義1：設(shè)m1（·）和m2（·）是2Θ上的兩個相互獨立的BBA（基本概率分配函數(shù)），定義組合后的BBA：m（·）=［m1⊕m2］（·）為

式（1）中，⊕為直和運算，也稱正交和（orthogonal）運算。

1.2 Zadeh悖論［13］

例1：設(shè)識別框架Θ={A，B，C}，BBA分別為：

用D-S組合規(guī)則合成結(jié)果：m12（A）=0，m12（B）=1，k=0.999 9，無論后續(xù)證據(jù)如何支持某一焦元，結(jié)果始終為m（A）=m（C）=0，m（B）=1。小概率事件m（B）經(jīng)過融合結(jié)果變?yōu)楸厝皇录?。該結(jié)果有悖于人類直覺。

1.3 信任偏移悖論［14］

例2：設(shè)識別框架Θ={θ1，θ2，…，θn}，BBA為m1（θ1）=0.06，m1（Θ）=0.94，mi（θ1）=0.06，mi（Θ）=0.94（i=1，2，3，…，n）用D-S組合規(guī)則合成結(jié)果：m（θ1）=1-0.94n，m（θ2）=0.94n，當(dāng)n值較大時，合成后m（θ1）就變得很大。如n→50時，m（θ1）=0.954 7，這顯然是錯誤的。

2 單一證據(jù)——沖突表示方法存在的問題

2.1 沖突系數(shù)k的局限性

在經(jīng)典證據(jù)理論中，沖突系數(shù)k是用來衡量沖突大小的，k值越大，說明證據(jù)間的沖突越大。但如果證據(jù)間交集不為空，單純用k表示證據(jù)沖突會出現(xiàn)與直覺相悖的情況。

例3：設(shè)辨識框架為Θ={θ1，θ2，θ3，θ4}；系統(tǒng)兩條證據(jù)分別為：m1（θ1）=m1（θ2）=m1（θ3）=m1（θ4）=0.25；m2（θ1）=m2（θ2）=m2（θ3）=m2（θ4）=0.25；則經(jīng)典沖突系數(shù)k=0.75，其實這兩個證據(jù)相同，直覺判斷沖突為零。

例4：設(shè)辨識框架為Θ={θ1，θ2，θ3，θ4}；系統(tǒng)兩條證據(jù)分別為m1（θ1∪θ4）=0.9；m1（θ2∪θ3∪θ4）=0.1；m2（θ1∪θ4）=0.1；m2（θ2∪θ3∪θ4）=0.9；可得，沖突系數(shù)為0，但實際上對于焦元θ1、θ2或者θ3而言，這兩個證據(jù)的沖突是非常大的。

2.2 證據(jù)距離度量沖突的局限性

Jousselme［12］提出用證據(jù)距離描述沖突并計算證據(jù)間相似度作為證據(jù)權(quán)重。之后，各種基于J氏距離的改進方法相繼提出，但這些方法均需計算兩兩證據(jù)距離，計算量較大。此外，J氏距離雖然表示了證據(jù)間相容焦元基本置信值分配的差異，但有時會出現(xiàn)與直覺相悖的情況。

例5：設(shè)辨識框架為Θ={θ1，θ2，θ3}；系統(tǒng)3條證據(jù)分別為m1（θ1）=0.5，m1（θ2）=m1（θ3）=0.25；m2（θ1）=m2（θ2）=0.25，m1（θ3）=0.5；m3（θ1）=m3（θ2）=0.1，m3（θ3）= 0.8。直觀推斷證據(jù)1與證據(jù)2的沖突應(yīng)大于證據(jù)2與證據(jù)3的沖突，而計算得d12=0.25，d23=0.45。所以在用J氏距離度量沖突時也存在著“死角”。

針對單一沖突表示的局限性，LIU W［15］于2006年提出，用經(jīng)典沖突系數(shù)k和博弈信度距離difBetP作為一個二元組來描述證據(jù)沖突，其后蔣雯［16］指出difBetP距離無法有效區(qū)分對系統(tǒng)未知和對系統(tǒng)各命題支持度相等這兩種不同情況，加之difBetP距離不滿足距離函數(shù)三公理，提出用經(jīng)典沖突系數(shù)k和J氏距離來描述證據(jù)沖突并定義容忍極限ε作為判斷沖突的參數(shù)，但對ε的設(shè)定并未給出一個準(zhǔn)則與評價體系。劉準(zhǔn)釓［17］用證據(jù)距離和矛盾因子的幾何均值來表示沖突大小，但對于信任偏移悖論中k值總是為零的情況，得到的沖突大小為零，這并不符合實際，并且在計算J氏距離與k時，需求出兩兩證據(jù)距離以及兩兩證據(jù)沖突系數(shù)，當(dāng)證據(jù)數(shù)量急劇增加時，會出現(xiàn)計算量指數(shù)級爆炸問題。

3 復(fù)合型沖突表示方法

實際應(yīng)用中，各傳感器對證據(jù)的獲取是有先后順序的，融合實質(zhì)上是一個先前證據(jù)融合結(jié)果與新加入證據(jù)再次融合的過程。為此，本文采取動態(tài)融合處理的策略，即每次都用新加入的證據(jù)與前一步組合結(jié)果進行融合，得到新的合成結(jié)果，并提出一種利用復(fù)合型沖突度量的動態(tài)加權(quán)證據(jù)融合方法。首先利用給出的證據(jù)中心定義，在計算證據(jù)距離時，僅計算每條證據(jù)與證據(jù)中心的距離，在計算經(jīng)典沖突系數(shù)k時，僅計算每條證據(jù)與證據(jù)中心的沖突系數(shù)，以減少兩兩求解的計算量，其次，提出利用當(dāng)前中心距離與經(jīng)典沖突系數(shù)k來共同表征沖突，并給出了復(fù)合型沖突大小及生成證據(jù)權(quán)重的表達式，最后用Dempster組合規(guī)則合成。

定義2Jousselme［12］距離：若m1和m2是在識別框架Θ上的兩個BPA，則m1和m2的距離可以表示為

D為一個2N×2N階矩陣，其中的元素為

將式（2）代入式（3）可得

定義3證據(jù)中心：因為證據(jù)是序貫式加入的，證據(jù)中心在不斷地更新，給出的當(dāng)前證據(jù)中心為

定義4當(dāng)前中心距離：一個新證據(jù)加入組合結(jié)果序列后，若與證據(jù)中心距離越大，說明此證據(jù)成為干擾的可能性越大，其作用應(yīng)該受到抑制。分別計算新加入證據(jù)與加入前后證據(jù)中心的距離，并求出幾何均值作為當(dāng)前中心距離，更能客觀反應(yīng)當(dāng)前新入證據(jù)與已有證據(jù)的差異性。定義新入證據(jù)與當(dāng)前證據(jù)中心ci的距離為；新入證據(jù)與加入之前的證據(jù)中心ci-1的距離，ci-1），當(dāng)前中心距離為。

定義5復(fù)合沖突系數(shù)ξ：為當(dāng)前中心距離d與沖突系數(shù)k的算術(shù)平均值，。

4 利用復(fù)合型沖突表示的動態(tài)加權(quán)證據(jù)修正

（2）第3步至第k步：

f、Dempster組合規(guī)則可得當(dāng)前第i步的組合結(jié)果記為：

5 算例實驗與討論

為驗證本文算法解決典型悖論問題的效果，分別與經(jīng)典的修改證據(jù)源方法進行對比。其中D-S為經(jīng)典合成方法，Murphy平均法［5］是最具代表性的證據(jù)修正方法，鄧勇［8］及韓德強［7］方法利用的是單一沖突表示方法：在計算兩兩證據(jù)間J氏距離的基礎(chǔ)上，確定各個證據(jù)權(quán)重并合成。

實驗環(huán)境為Intel酷睿2.50 GHz，內(nèi)存2 GB的PC機，VS2010軟件平臺。耗時取10次重復(fù)實驗的平均值。

算例1：Zadeh悖論

設(shè)識別框架Θ={θ1，θ2，θ3}，BBA分別為：

m1（θ1）=0.99，m1（θ2）=0.01，m1（θ3）=0；

m2（θ1）=0，m2（θ2）=0.01，m2（θ3）=0.99；

mi（θ1）=0.99，mi（θ2）=0.01，mi（θ3）=0（i=1，2，3，…，n）；

表1為針對Zadeh悖論各種證據(jù)組合方法的結(jié)果。除DS方法外，其余方法均可有效解決Zadeh悖論。其中Murphy、鄧勇方法收斂速度較快，韓德強方法與本文方法收斂速度較慢，但這并未影響對支持命題的決策。同其他方法一樣，本文方法在第3個證據(jù)加入時，便可以得出正確結(jié)論。需要指出的是，算法的收斂速度并不是越快越好，過快的收斂速度對于違背直覺的結(jié)果來說更加速了錯誤決策的發(fā)生。算例2充分說明了這一點。

表1 各種證據(jù)組合方法的結(jié)果比較

算例2：信任偏移悖論

設(shè)識別框架Θ={θ1，θ2，…，θn}，BBA為m1（θ1）= 0.06，m1（Θ）=0.94，mi（θ1）=0.06，mi（Θ）=0.94，（i=2，3，…，n），本例著重驗證在大規(guī)模證據(jù)合成時，算法能否以較短的計算時間更加有效地抑制悖論的發(fā)生，因此，令識別框架中的焦元數(shù)為50。

表2 證據(jù)組合結(jié)果比較

在算例2中，Dempster方法、Murphy方法、鄧勇方法在新加入第12個證據(jù)時，就已經(jīng)發(fā)生了信任偏移，此時m（θ1）=0.524 1，之后的合成結(jié)果向原本支持度很小的焦元θ1快速收斂，這更加劇了信任偏移的發(fā)生。韓德強方法中，隨著證據(jù)數(shù)目的增多，對焦元θ1的基本概率指派也不斷增加，雖然增速較前3種方法大大降低，但當(dāng)證據(jù)數(shù)目急劇增加到一定程度時，信任偏移始終無法避免。本文算法中，當(dāng)證據(jù)數(shù)目小于20時，和韓德強方法一樣，對焦元θ1的基本概率指派也在緩慢增加，到達了極值之后，隨著新證據(jù)的加入，對焦元θ1的基本概率指派開始緩慢減小，組合結(jié)果逐漸向符合人類直覺的方向收斂，雖然收斂速度比較平緩，但相比韓方法，徹底避免了信任偏移的發(fā)生。這是因為復(fù)合型沖突度量方法能夠彌補單一沖突表示的“死角”問題，進而生成的證據(jù)權(quán)重更加全面地反應(yīng)了各個證據(jù)的重要重度；另外，文中定義的證據(jù)中心隨著相同證據(jù)的加入時時更新，并不斷向基本概率指派中占優(yōu)的焦元Θ逐步靠近，從而有效抑制了信任偏移。從融合速度上來說，本文算法由于增加了證據(jù)中心及當(dāng)前中心距離的計算，相較于Dempster方法、Murphy方法耗時更多，如圖1所示，但與鄧勇、韓德強方法相比，并不需要求解兩兩證據(jù)距離。因此，在大規(guī)模證據(jù)融合時，能夠避免信任偏移的發(fā)生并且耗時較短。本文算法更適用于證據(jù)規(guī)模較大時的穩(wěn)妥保守型決策場合，并且證據(jù)數(shù)目越多，合成效果越好。

圖1 各種方法組合證據(jù)序列2時的耗時趨勢圖

6 結(jié)束語

為解決利用經(jīng)典DS規(guī)則進行大規(guī)模證據(jù)融合時的出現(xiàn)的悖論問題，從分析單一沖突表示方法的缺陷入手，提出一種利用復(fù)合沖突表示解決大規(guī)模證據(jù)合成時的DS快速加權(quán)融合算法。理論分析和數(shù)值實驗結(jié)果表明，該方法在解決Zadeh悖論問題時，具有較好的收斂性；特別是在解決信任偏移悖論問題時，相較于其他算法，能夠徹底避免信任偏移的發(fā)生。同時，在大規(guī)模證據(jù)融合時，算法顯示了更快地計算速度。

［1］Dempster A P.Upper and Lower Probabilities Induced by a Multi-valued 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］Destercke S，Burger T.Revisiting the Notion of Conflicting Belief Functions［C］//Proc of the 2nd Int Conf on Belief Functions.Compiègne，2012：153-160.

［4］Yang J P.A Novel Information Fusion Method Based on Dempster-Shafer Evidence Theory for Conflict Resolution［J］.Intelligent Data Analysis，2011，15（3）：399-411.

［5］Murphy C K.Combining Belief Functions When Evidence Conflicts［J］.Decision Support Systems，2000，29（1）：1-9.

［6］Haenni R.Are Alternatives to Dempster’s Rule of Combination Real Alternative Comments on“About the Belief Function Combination and the Conflict Management Problem”［J］. Information Fusion，2002，3（4）：237-239.

［7］韓德強，鄧勇，韓崇昭，等.基于證據(jù)方差的加權(quán)證據(jù)組合［J］.電子學(xué)報，2011，39（3A）：153-157.

［8］鄧勇，施文康，朱振福.一種有效處理沖突證據(jù)的組合方法［J］.紅外與毫米波學(xué)報，2004，23（1）：27-32.

［9］吳俊，程詠梅，曲圣杰，等.基于三級信息融合結(jié)構(gòu)的多平臺多雷達目標(biāo)識別算法［J］.西北工業(yè)大學(xué)學(xué)報2012，30（3）：367-372.

［10］Han D Q，Deng Y，Han C Z，et al.Weighted Evidence Combination Based on Distance of Evidence and Uncertainty Measure［J］.J of Infrared and MillimeterWaves，2011，30（5）：396-400.

［11］Atiye S J，Babak N A，Augustin T.Information-based Dissimilarity Assessment in Dempster-Shafer theory［J］. Knowledge-Based System，2013（54）：114-127.

［12］Jousselme A L，Grenier D，Bosse E.A New Distance Between two Bodies of Evidence［J］.Information Fusion，2001，2（2）：91-101.

［13］Zadeh L.On the Validity of Dempster’s Rule of Combination［R］.Memo M 79/24，Univ.of California，Berkeley，1979.

［14］張所地，王拉娣.Dempster-Shafer合成法則的悖論［J］.系統(tǒng)工程理論與實踐，1997，17（5）：82-85.

［15］Liu W.Analyzing the Degree of Conflict Among Belief Functions［J］.Artificial Intelligence，2006，170（11）：909-924.

［16］蔣雯，張安，鄧勇.改進的二元組沖突表示方式［J］.紅外與激光工程，2009，38（5）：936-940.

［17］劉準(zhǔn)釓，程詠梅，潘泉，等.基于證據(jù)距離和矛盾因子的加權(quán)證據(jù)合成法［J］.控制理論與應(yīng)用，2009，26（12）：1439-1442.

A Method of Fast Weighted Evidence Combination Exhibited by Compound Conflict

BAI Dong-ying1，2，WANG Gang2，LI Song2，YAO Xiao-qiang2
（1.Second Artillery Engineering University，Xi’an 710025，China；
2.Air and Missile Defense College，Air Force Engineering University，Xi’an 710051，China）

Aiming at the paradox of D-S evidence theory and computation’s exponential growth in dealing with large–scale conflict evidence combination，a new weighted evidence combination method is proposed，which uses conflict coefficient and evidence distance in order to measure the conflict. Through the analysis of single conflict representation’s weaknesses，compound conflict coefficient has been put forward，meanwhile，the evidence centre and current centre distance are defined，evidence weight is determined with current centre distance and conflict coefficient.The experiment results show that the algorithm settles the paradox effectively，at the same time，computing speed has been greatly enhanced.

D-S evidence，conflict coefficient，evidence centre，centre distance

TP212.9

A

1002-0640（2015）12-0022-05

2014-12-18

2015-02-16

國家自然科學(xué)基金資助項目（61102109）

白東穎（1982-），女，陜西寶雞人，博士研究生。研究方向：智能信息處理和機器學(xué)習(xí)。