基于相異度矩陣的沖突證據合成算法

司 成，張紅旗，汪永偉，常德顯

（1.信息工程大學，河南 鄭州450001；2.河南省信息安全重點實驗室，河南 鄭州450001）

0 引 言

D－S證據理論是一種有效處理信息融合的數學工具，能夠有效辨別 “不知道”和 “不確定”的信息，減少信息的冗余，加強信息之間的互補關聯，提高決策的確定性，因此在信息融合、決策分析、目標識別等領域有著廣泛的應用［1－3］。

傳統的Dempster合成規則只能處理低沖突的證據，但在系統實際運行環境中，由于外界環境和人為因素的干擾，常常會產生沖突程度較高的證據，此時應用傳統的Dempster合成規則會得出有悖于常理的結論，稱為Zadeh悖論。針對這一悖論問題，大量研究工作在眾多領域中展開［4－8］。這些工作主要圍繞兩方面進行展開：一是基于修正融合證據源的方法，對證據源進行預處理，然后再用組合規則進行合成，代表方法有Murphy方法［9］、Tazid方法［10］和胡昌華方法［11］等，其中Murphy采用證據平均合成方法來處理沖突證據，但該方法沒有考慮證據之間的關聯性。Tazid等提出了采用加性策略代替乘性策略的合成方法，但證據收斂速度較慢，不利于最終決策。胡昌華等提出基于基本概率分配函數 （BPA）的pignistic變換的證據沖突度量標準，但僅僅考慮證據相信命題為真的可信度差異，沒有對證據之間的沖突程度進行衡量。二是基于改進合成規則的方法，修正沖突證據信任值的分配空間和權重，消除合成結果中悖論的影響，代表方法有Yager方法［12］、Dubois方法［13］和孫全方法［14］等，其中Yager將沖突信任分配到識別框架中，該方法在處理低沖突證據時比較合理，但對于高沖突證據的情況，就會出現信任分配不公、一票否決等問題。Dubois將沖突信任進行局部分配，有效避免了悖論的發生，但識別框架會保留較多的信任值，不利于最終決策。孫全將加權和均值結果用于證據合成，但合成結果無法用于準確決策。

通過上述分析，本文提出一種解決沖突證據合成問題的算法。首先，基于歐幾里德距離計算證據之間的相異程度，構造相異度矩陣；其次，計算證據的相異支持度、可信度和修正率，對證據進行修正；最后，將修正后的證據利用合成算法進行合成。實驗結果表明，該方法在決策一致性檢驗、決策確定性度量、決策目標識別點等方面均優于現有典型方法。

1 證據理論及其悖論

證據理論將其研究范圍定義為識別框架Θ，它是一種非空有限域，包含若干數量有限的互斥系統狀態元素。證據E 對焦元A 的支持程度用基本信任分配函數m（A）來表示，由于在某些實際環境中，用于采集數據證據源不同，得到的基本信任分配函數的數值也各不相同，此時就需要將其合并成一個基本信任分配函數。Dempster規則采用正交和運算進行合成，其定義如下［15］：

設｛E1，E2，…，En｝是同一識別框架Θ 上的n 個證據，｛m1，m2，…，mn｝是相應的基本信任分配函數，焦元為Ai（i＝1，2，…，n），則這n個證據合成后的基本信任分配函數為

2 基于相異度矩陣的證據合成方法

當一個證據源產生若干組證據時，稱這些證據為相關證據。在證據融合過程中，若不考慮證據間的這種相關性，將會導致合成結果的過估計，降低決策精度。因此，需要通過判斷每個證據和其它證據的相異程度來衡量證據之間的相關性。證據之間的距離是度量證據間相異程度的一種可行方法，如果證據之間的距離較大，說明證據之間存在較大的沖突，從而表示證據之間的相異程度也較大?；诖?，本文提出一種解決沖突證據合成問題的新算法，通過計算各證據間的相異度和每個證據的可信度，確定證據的修正率，利用合成算法對修正后的證據進行合成。

2.1 證據相異度度量

目前用于數值屬性相異程度的計算方法主要有3 種：歐幾里德距離、曼哈頓距離和閔可夫斯基距離。其中，歐幾里德距離因計算方法簡單、幾何意義明確，被廣泛應用于信號處理、數據挖掘等領域。基于此，本文利用歐幾里德距離來計算證據之間的相異度。下面給出證據相異度的定義。

定義1 證據相異度：在目標識別框架Θ 下，Ei和Ej為兩個實例證據，mi和mj為相應的基本信任分配函數，Ai和Bj為焦元，則證據Ei和Ej間的相異度可以表示為

其中，dij（mi，mj）表示證據Ei和Ej之間的相異度。假設存在n個證據，通過式 （2）可以計算證據Ei和Ej之間的相異度，并可表示為一個相異度矩陣的形式

將式 （3）各行相加，得到證據Ei和其它證據間的相異支持度DifSup（mi）

相異支持度指在全局范圍內，證據Ei和其它證據的差異程度。某一證據的相異支持度越高，其它證據對它的支持度越低，該證據的可信度越低。

為衡量各證據的重要程度，引入信息論中熵的概念進行計算，設證據Ei的熵為ENTi，則其值為

由式 （5）可知，證據的熵與可信度成反比，將式 （5）的結果進行歸一處理，得到證據Ei的可信度Crd（mi）

2.2 證據合成算法

由于證據源易受所處外界環境和自身內部條件等因素的干擾，產生的證據并不完全可靠，同時證據合成過程中的各證據的重要程度也各不相同，因此需要對證據的BPA值進行修正操作后再進行合成操作，這樣既繼承了Dempster規則良好的證據交換和結合性質，又提高了合成結果的可靠性。

定義2 相對可信度向量：n個證據的可信度向量Crd

設Crdmax＝max｛Crd1，Crd2，…，Crdn｝，可 得相對可信度向量Crd＊

定義3 證據修正率：由相對可信度向量Crd＊可確定證據BPA 值的修正率λi＝Crdi／Crdmax，i＝1，2，…，n。從而對證據的BPA 值進行修正

其中，m′i（Aj）表示修正后的證據，Aj表示第j 個焦元，容易證明m′i（Aj）滿足基本概率分配的3 個條件，證據修正率λi表示證據i的可信程度，且滿足λi∈［0，1］。當λi＝0時，表示證據完全不可信，無法為正確決策提供有價值的信息，因此將該證據的BPA 值全部分配給論域Θ，即m′i（Θ）＝1；當λi＝1時，表示證據完全可信，能夠完全為正確決策提供有價值的信息，因此不需要對該證據的BPA 值進行修正。

證據修正后的多證據合成規則為

式 （10）中沖突系數Kn′為

對于采集到的n 個證據，采用下列證據合成算法進行合成。

n個證據合成算法如圖1所示。

對于同時到達的n 個證據，采用式 （10）進行一次性合成得到最終結果；對于分時到達的n 個證據，令式 （10）中n＝2，進行n－1次兩兩證據合成，得到最終合成結果。n個證據合成算法的復雜度為O（n2）。

3 實驗算例分析

為驗證本文提出的融合方法的有效性，實驗選取Dempster、Yager、Murphy、Dubois和Tazid這5種典型的融合方法進行對比實驗。

3.1 實驗數據和結果

圖1 n個證據合成算法

實驗利用網絡安全態勢感知系統對網絡攻擊類型的識別結果進行仿真。假設，識別框架為Θ＝ ｛A ＝拒絕服務攻擊，B ＝漏洞掃描攻擊，C ＝腳本注入攻擊｝，某時刻利用網絡安全態勢感知系統獲取到的信息，構造5 個證據的BPA 見表1。

表1 基本概率分配值

通過式 （2）、式 （3）可得相異度矩陣為

通過相異度矩陣 （12）和式 （4）、式 （5）、式 （6）可得可信度向量為

相對可信度向量為

即為證據的修正率。

各種方法合成結果的對比見表2。

表2 不同合成方法結果對比

3.2 實驗分析

由表2可見，不同合成方法各有側重，需要借助一定的評價方法來進行對比說明。本文參考文獻 ［15］中所提出的合成規則評價方法和研究實際，對證據理論合成規則的優劣進行衡量，主要從以下3個方面進行評價：

（1）決策一致性檢驗?？春铣山Y果是否符合決策者依據自身經驗進行邏輯推理的結果，即能否正確得到預期結論。

（2）決策確定性度量?？醋C據合成后結果的信息量的不確定性是否減少，即單個焦元的最大可信度是否增大以及識別框架的可信度是否減小。

（3）決策目標識別點。用來評價合成規則對決策目標的識別效率，在能夠正確識別出決策目標的前提下，需要合成的證據越少，表明合成規則對決策目標的識別效率越高。

3.2.1 決策一致性檢驗

通過經驗和邏輯推理判斷，表1中的5個證據對命題A 的支持度最大，因此命題A 應該為最終決策的正確結論。表3列舉了利用各種合成方法進行決策的基本情況，其中“×”表示無法做出正確決策， “√”表示能夠做出正確決策。

表3 各種方法決策情況

如表3所示，Dempster方法和Yager方法無法做出正確決策，Murphy方法和Dubois方法只有合成4 個證據時才能正確決策，而Tazid方法和本文方法只需合成3個證據就可以做出正確的決策。Dempster方法無法處理沖突證據，一旦數據源受到外界或人為因素的干擾，造成某一證據對某個命題的支持度為0，無論后續證據對該命題的支持度有多大，合成結果都為0，這顯然與事實不符，因此無法得出正確的決策結果。Yager方法觀點有些狹隘，以為沖突證據提供的信息沒有任何價值，對沖突證據持完全否定的態度，并將沖突證據的信任值全部分配給論域Θ，隨著證據數目的增加，未知項m（Θ）的數值也不斷增大，造成合成結果的不確定性不斷增加，并且也同樣存在一票否決的缺點。Murphy方法將多個證據進行算術平均，沒有考慮各證據之間存在的互相關性，并且只有合成4 個證據時，才能對目標進行正確決策。Dubois方法為沖突焦元的并集命題分配了較多的沖突信任值，暫緩了對存在沖突的證據進行決策，但該方法顯得比較謹慎，且不滿足結合律，因此在合成之前需要提前確定證據的先后順序。Tazid方法和本文方法都能夠避免Zadeh悖論的產生，做出正確的決策，并且本文方法對命題A 分配的信任值最大，決策最為準確。

3.2.2 決策確定性度量

各種合成方法對命題A 和識別框架Θ 分配的信任值如圖2所示。

從圖2可以看出，Yager方法合成結果的不確定性很高，因此不具有實用性；Murphy方法、Dubois方法、Tazid方法和本文方法對命題A 分配的信任值都比較大，Dempster方法、Murphy方法、Tazid方法和本文方法對識別框架分配的信任值都比較小，合成結果很大程度上減少了不確定性。本文方法的最終結果m（A）＝0.9108，表明該方法的結論具有很大的確定性，決策結果比較準確。

圖2 各種合成方法對命題A 和識別框架Θ 的信任值

3.2.3 決策目標識別點

在能夠正確識別出決策目標的前提下，各種合成方法的決策目標識別點如圖3所示。

圖3 各種合成方法的決策目標識別點

由于Dempster方法和Yager方法無法正確識別出決策目標，所以這兩種方法不存在決策目標識別點。Murphy方法缺乏考慮證據之間存在的互相關性，因此和Dubois方法一樣，在合成4個證據時才能正確識別目標，因此決策目標識別點為4。Tazid方法和本文方法在合成3個證據時就能正確識別目標，因此決策目標識別點為3。Tazid方法由于采用加性策略，其合成證據的收斂速度較慢，不利于最終的正確決策。本文方法利用相異度矩陣來衡量證據之間的相異程度，充分考慮了焦元屬性間和證據之間的互相關性，降低了干擾證據的可信度，對證據之間的沖突敏感性反應較強，收斂速度較快，增強了合成效果。

4 結束語

各類網絡安全設備在運轉過程中會受到外界環境的各種不確定性因素的影響，導致告警和日志信息可能會產生相互沖突的證據，傳統的Dempster規則無法處理沖突證據合成產生的Zadeh悖論問題。針對這一問題，本文提出了基于相異度矩陣的沖突證據合成方法。通過與幾種典型合成方法的實驗對比，本文提出的合成方法收斂速度較快，決策結果的確定性較高，能夠有效解決沖突證據的合成問題。如何將本文所提出的方法應用于網絡安全態勢要素的融合是下一步研究的重點。

［1］ZENG Fuping，LU Manyan，ZHONG Deming.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.

［2］Bo Chen，Jicai Feng.Multisensor information fusion of pulsed GTAW based on improved D－S evidence theory ［J］.The International Journal of Advanced Manufacturing Technology，2014，71 （1）：91－99.

［3］XU Peida，DENG Yong，SU Xiaoyan，et al.A new method to determine basic probability assignment from training data［J］.Knowledge－Based Systems，2013，46：69－80.

［4］DENG Xinyang，DENG Yong.Multisensor information fusion based on dempster－shafer theory and power average operator［J］.Journal of Computational Information Systems，2013，9（16）：6417－6424.

［5］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）.［康兵義，李婭，鄧勇，等.基于區間數的基本概率指派生成方法及應用 ［J］.電子學報，2012，40 （6）：1092－1096.］

［6］Sebbak F，Chibani A，Amirat Y，et al.An evidential fusion approach for activity recognition in ambient intelligence environments ［J］.Robotics and Autonomous Systems，2013，61（11）：1235－1245.

［7］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］.電子與信息學報，2012，34 （4）：851－857.］

［8］Leung Y，JI Nannan，MA Jianghong.An integrated information fusion approach based on the theory of evidence and group decisionmaking［J］.Information Fusion，2012，8 （2）：1－13.

［9］CHEN Yanfei，XIA Xuezhi，GE Shun，et al.An approach to convict evidence combination based on two criteria optimization［J］.Journal of Computational Information Systems，2014，10（7）：2727－2734.

［10］Tazid A，Palash D，Hrishikesh B.A new combination rule for conflict problem of dempster－shafer evidence theory ［J］.International Journal of Energy，Information and Communications，2012，3 （1）：35－44.

［11］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）.［胡昌華，司小勝，周志杰，等.新的證據沖突衡量標準下的D－S 改進算法 ［J］.電子學報，2009，37 （7）：1578－1583.］

［12］Yager R R.On the fusion of imprecise uncertainty measures using belief structures［J］.Information Sciences，2011，181（15）：3199－3209.

［13］Ben Abdallah N，Mouhous－Voyneau N，Denoeux T.Combining statistical and expert evidence using belief functions：Application to centennial sea level estimation taking into account climate change ［J］.International Journal of Approximate Reasoning，2014，55 （1）：341－354.

［14］PANG Jinfeng，LIN Yun，LI Yibing，et al.A new DS combination method for dealing with conflict evidence effectively［J］.International Journal of Signal Processing，Image Processing and Pattern Recognition，2013，6 （5）：255－264.

［15］YANG Fengbao，WANG Xiaoxia.Combination of conflict for D－S evidence theory ［M］.Beijing：National Defense Industry Press，2010 （in Chinese）.［楊風暴，王肖霞.D－S證據理論的沖突證據合成方法 ［M］.北京：國防工業出版社，2010.］