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

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

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

0 引 言

D－S證據(jù)理論是一種有效處理信息融合的數(shù)學(xué)工具，能夠有效辨別 “不知道”和 “不確定”的信息，減少信息的冗余，加強(qiáng)信息之間的互補(bǔ)關(guān)聯(lián)，提高決策的確定性，因此在信息融合、決策分析、目標(biāo)識(shí)別等領(lǐng)域有著廣泛的應(yīng)用［1－3］。

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

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

1 證據(jù)理論及其悖論

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

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

2 基于相異度矩陣的證據(jù)合成方法

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

2.1 證據(jù)相異度度量

目前用于數(shù)值屬性相異程度的計(jì)算方法主要有3 種：歐幾里德距離、曼哈頓距離和閔可夫斯基距離。其中，歐幾里德距離因計(jì)算方法簡(jiǎn)單、幾何意義明確，被廣泛應(yīng)用于信號(hào)處理、數(shù)據(jù)挖掘等領(lǐng)域?；诖耍疚睦脷W幾里德距離來計(jì)算證據(jù)之間的相異度。下面給出證據(jù)相異度的定義。

定義1 證據(jù)相異度：在目標(biāo)識(shí)別框架Θ 下，Ei和Ej為兩個(gè)實(shí)例證據(jù)，mi和mj為相應(yīng)的基本信任分配函數(shù)，Ai和Bj為焦元，則證據(jù)Ei和Ej間的相異度可以表示為

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

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

相異支持度指在全局范圍內(nèi)，證據(jù)Ei和其它證據(jù)的差異程度。某一證據(jù)的相異支持度越高，其它證據(jù)對(duì)它的支持度越低，該證據(jù)的可信度越低。

為衡量各證據(jù)的重要程度，引入信息論中熵的概念進(jìn)行計(jì)算，設(shè)證據(jù)Ei的熵為ENTi，則其值為

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

2.2 證據(jù)合成算法

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

定義2 相對(duì)可信度向量：n個(gè)證據(jù)的可信度向量Crd

設(shè)Crdmax＝max｛Crd1，Crd2，…，Crdn｝，可 得相對(duì)可信度向量Crd＊

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

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

證據(jù)修正后的多證據(jù)合成規(guī)則為

式 （10）中沖突系數(shù)Kn′為

對(duì)于采集到的n 個(gè)證據(jù)，采用下列證據(jù)合成算法進(jìn)行合成。

n個(gè)證據(jù)合成算法如圖1所示。

對(duì)于同時(shí)到達(dá)的n 個(gè)證據(jù)，采用式 （10）進(jìn)行一次性合成得到最終結(jié)果；對(duì)于分時(shí)到達(dá)的n 個(gè)證據(jù)，令式 （10）中n＝2，進(jìn)行n－1次兩兩證據(jù)合成，得到最終合成結(jié)果。n個(gè)證據(jù)合成算法的復(fù)雜度為O（n2）。

3 實(shí)驗(yàn)算例分析

為驗(yàn)證本文提出的融合方法的有效性，實(shí)驗(yàn)選取Dempster、Yager、Murphy、Dubois和Tazid這5種典型的融合方法進(jìn)行對(duì)比實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)和結(jié)果

圖1 n個(gè)證據(jù)合成算法

實(shí)驗(yàn)利用網(wǎng)絡(luò)安全態(tài)勢(shì)感知系統(tǒng)對(duì)網(wǎng)絡(luò)攻擊類型的識(shí)別結(jié)果進(jìn)行仿真。假設(shè)，識(shí)別框架為Θ＝ ｛A ＝拒絕服務(wù)攻擊，B ＝漏洞掃描攻擊，C ＝腳本注入攻擊｝，某時(shí)刻利用網(wǎng)絡(luò)安全態(tài)勢(shì)感知系統(tǒng)獲取到的信息，構(gòu)造5 個(gè)證據(jù)的BPA 見表1。

表1 基本概率分配值

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

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

相對(duì)可信度向量為

即為證據(jù)的修正率。

各種方法合成結(jié)果的對(duì)比見表2。

表2 不同合成方法結(jié)果對(duì)比

3.2 實(shí)驗(yàn)分析

由表2可見，不同合成方法各有側(cè)重，需要借助一定的評(píng)價(jià)方法來進(jìn)行對(duì)比說明。本文參考文獻(xiàn) ［15］中所提出的合成規(guī)則評(píng)價(jià)方法和研究實(shí)際，對(duì)證據(jù)理論合成規(guī)則的優(yōu)劣進(jìn)行衡量，主要從以下3個(gè)方面進(jìn)行評(píng)價(jià)：

（1）決策一致性檢驗(yàn)?？春铣山Y(jié)果是否符合決策者依據(jù)自身經(jīng)驗(yàn)進(jìn)行邏輯推理的結(jié)果，即能否正確得到預(yù)期結(jié)論。

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

（3）決策目標(biāo)識(shí)別點(diǎn)。用來評(píng)價(jià)合成規(guī)則對(duì)決策目標(biāo)的識(shí)別效率，在能夠正確識(shí)別出決策目標(biāo)的前提下，需要合成的證據(jù)越少，表明合成規(guī)則對(duì)決策目標(biāo)的識(shí)別效率越高。

3.2.1 決策一致性檢驗(yàn)

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

表3 各種方法決策情況

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

3.2.2 決策確定性度量

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

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

圖2 各種合成方法對(duì)命題A 和識(shí)別框架Θ 的信任值

3.2.3 決策目標(biāo)識(shí)別點(diǎn)

在能夠正確識(shí)別出決策目標(biāo)的前提下，各種合成方法的決策目標(biāo)識(shí)別點(diǎn)如圖3所示。

圖3 各種合成方法的決策目標(biāo)識(shí)別點(diǎn)

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

4 結(jié)束語

各類網(wǎng)絡(luò)安全設(shè)備在運(yùn)轉(zhuǎn)過程中會(huì)受到外界環(huán)境的各種不確定性因素的影響，導(dǎo)致告警和日志信息可能會(huì)產(chǎn)生相互沖突的證據(jù)，傳統(tǒng)的Dempster規(guī)則無法處理沖突證據(jù)合成產(chǎn)生的Zadeh悖論問題。針對(duì)這一問題，本文提出了基于相異度矩陣的沖突證據(jù)合成方法。通過與幾種典型合成方法的實(shí)驗(yàn)對(duì)比，本文提出的合成方法收斂速度較快，決策結(jié)果的確定性較高，能夠有效解決沖突證據(jù)的合成問題。如何將本文所提出的方法應(yīng)用于網(wǎng)絡(luò)安全態(tài)勢(shì)要素的融合是下一步研究的重點(diǎn)。

［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）.［康兵義，李婭，鄧勇，等.基于區(qū)間數(shù)的基本概率指派生成方法及應(yīng)用 ［J］.電子學(xué)報(bào)，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ù)相似性度量的沖突性區(qū)間證據(jù)融合方法 ［J］.電子與信息學(xué)報(bào)，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）.［胡昌華，司小勝，周志杰，等.新的證據(jù)沖突衡量標(biāo)準(zhǔn)下的D－S 改進(jìn)算法 ［J］.電子學(xué)報(bào)，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）.［楊風(fēng)暴，王肖霞.D－S證據(jù)理論的沖突證據(jù)合成方法 ［M］.北京：國(guó)防工業(yè)出版社，2010.］