基于相异度矩阵的冲突证据合成算法

司 成，张红旗，汪永伟，常德显

（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）决策一致性检验。看合成结果是否符合决策者依据自身经验进行逻辑推理的结果，即能否正确得到预期结论。

（2）决策确定性度量。看证据合成后结果的信息量的不确定性是否减少，即单个焦元的最大可信度是否增大以及识别框架的可信度是否减小。

（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.］