基于偏差的冲突证据融合的改进方法*

张齐 刘群

(华南理工大学计算机系统结构研究所,广东广州 510640)

Dempster-Shafer(D-S)证据理论是一种不确定推理方法,其为不确定性的表达与合成提供了一种很好的方法.它满足比概率论弱的公理,并能区分不确定与不知道的差异,当先验概率已知时,证据理论就变成概率论,当先验概率很难获取时,证据理论比概率论合适.它提供了D-S组合规则[1]代替Bayes公式进行证据组合.

但是证据理论中表示不确定性的概率分配函数没有统一的构成方法,而且作为其理论基石之一的Dempster组合规则存在不足之处,在合成高度冲突的证据时,往往会得到错误的结论.国内外对此进行了广泛的研究,并提出了许多改进算法[2-13].研究冲突证据组合算法的目的是化解证据之间的冲突,将冲突证据进行重新分配,以获得合理的组合结果.

本研究比较了国内外学者对证据组合规则和融合模型的改进方法.并在此基础上提出了一种新的处理冲突证据的融合方法.该方法通过计算各证据到命题平均支持度的偏差,来检测和消除冲突证据,然后对最后结果进行了修正,以处理来自不同识别框架的证据的合成.

1 D-S证据理论及其缺陷

1.1 D-S证据理论基础

给定识别框架Θ,领域内命题 Q的基本概率分配(BPA)用函数m:2Θ→[0,1]表示,称为mass函数,它满足

式中:为空集.命题的信任函数Bel定义为

命题Q的似然函数(Pl)定义为

由信任函数和似然函数的定义可知:Bel(Q)表示对Q为真的信任程度,Pl(Q)表示对Q为非假的信任程度,Pl(Q)-Bel(Q)表示对Q不确定的程度.因此,区间(Bel(Q),Pl(Q))很好地描述了Q的可信程度.

对同一命题Q,从不同来源可以得到多个BPA函数,需要对它们进行组合,组合的方法是正交和运算,定义如下:

设m1,m2,…,mn是n个mass函数,框架内命题总数为r,则其正交和m=m1⊕m2⊕…⊕mn为

K的大小反映了不同证据的冲突程度,K越大,证据冲突程度就越大,反之越小.1-K称为归一化因子,它的存在避免了将非零的概率赋给空集的可能.D-S组合规则符合结合律,合成结果不依赖于组合的顺序.

1.2 证据理论的缺陷

设识别框架Θ={A,B,C}的BPA函数如下:

(1)对于证据m1,m1(A)=0.99,m1(B)= 0.01,m1(C)=0.00.

(2)对于证据m2,m2(A)=0.00,m2(B)= 0.01,m2(C)=0.99.

此例中,尽管两证据对 B的支持程度很低,但最终融合结果认为B为真,与常理相悖.

同时,mass函数的微小变化会使组合结果产生急剧变化.如对上述m1函数略加修改,使m1(A)= 0.98,m1(B)=0.01,m1(C)=0.01,m2不变,则会得到m(B)=m1⊕m2(B)=0.01,组合结果几乎与之前相反.这反映了D-S合成规则在此情况下的不稳定性和对mass函数的敏感性.归根结底,导致上述缺陷的核心问题就是错误分配了冲突信息.

2 对D-S组合规则的改进

Yager[2]提出的改进方法是把冲突证据分配给识别框架下的完备命题集合,即把冲突证据的基本概率数归到不确定性集合,他认为冲突证据不能提供任何有用的信息.孙全等[3]认为冲突证据是部分可用的,应该将总冲突按一定比例分配给所有证据的焦元集合.文献[4]引入自冲突概念来刻画概率分配函数的自相矛盾程度,提出了一种权重分配策略.类似的改进规则还可参见文献[5-6].

从以上这些改进证据组合规则的方法可知,改进主要是集中于冲突项如何分配.通过引入冲突证据的加权因子ω(Q,m),m={m1,m2,…,mn}来确定证据组合后命题Q的mass函数:

这就是处理冲突证据的改进组合公式的一般形式.然而这种方法存在的主要问题是:①当识别框架中命题的数目很大时,需要计算每个组合算子冲突证据的加权因子,且加权因子的计算量很大;②这种方法不满足组合运算的结合律,将使组合结果依赖于证据组合顺序,这是该方法的最大缺点.文献[7]提出了一种计算证据可靠性的新方法,但它的组合公式是基于给不同的证据赋予权重,仍然属于式(5)的范畴,存在的问题没有得到解决.

3 对融合模型的改进

对融合模型进行改进的方法认为:D-S组合规则本身没有失效,当证据高度冲突时,应该首先对冲突证据进行预处理,然后再使用D-S组合规则.

文献[8]已证明,在解决组合冲突证据过程中引起的失效问题时,修改融合模型比修改组合公式更为有效.

实际上各个证据源存在着不同程度的不可靠性,常称为折扣系数,并将之作为权值修正证据的质量函数.文献[9]提出用未知扰动来表示折扣系数,通过最小化元知识来确定每条证据的未知扰动值,然后将折扣证据进行组合.该方法存在的问题是需要事先确定元知识和量化的证据优先级,这在证据很多时很难实现.文献[11]和[12]在文献[10]的基础上引入证据间距离的概念来表示折扣系数.然而这种方法计算量大,当目标框架复杂,证据多时尤为明显,而且收敛速度较慢.文献[13]对求证据距离的公式进行了改进,虽然降低了一些计算复杂性,但收敛速度进一步变慢.

4 新的冲突证据融合方法

本研究对冲突证据融合方法做了进一步改进,即通过计算各证据到命题平均支持度的偏差来检测和消除冲突证据,并对最后结果进行了修正.算法流程具体步骤如下:

1)证据的冲突检测.

若证据只有2条,直接跳到步骤4).

先计算出证据对各命题总的支持程度:

式中:n为证据总数.找出使Sj最大的命题,构成命题集L={Lk,k=1,2,…,u}(若只有一个命题Sj最大,则L只有一个元素,若有多个命题 Sj同为最大,则L有多个元素,记为u).L中的元素称为关键命题,因为识别目标存在于L中.再计算证据对L中各命题的平均支持度:

各证据与Ek的偏差为

依次检测Dik是否符合冲突条件,若存在1≤i≤n,1≤k′≤u,使Dik′符合冲突条件,则证据mi为冲突证据,不必再向后检测,若某证据通过 L中所有命题的冲突检测,则其为非冲突证据.检测方法如下:

阈值α的选取与BPA函数的数据准确度有关,准确度越高,支持同一事件的焦元就越集中,α越大.把Dik≤0的证据称为有利证据,Dik＞0的证据称为不利证据,α可以取值为有利证据的条数.

对证据重新排序,得到M={mi,i=1,2,…,v, v+1,…,n},其中从第v+1条证据开始,就是冲突证据了,即M′={mi,i=v+1,v+2,…,n}是冲突证据集.

2)对冲突证据进行合成.

文献[14]把冲突证据直接做平均加成,这是不妥当的,更合适的做法是设置权值.因为各冲突证据的可利用价值不一样,证据冲突越大,可利用价值越小.权值的计算方法如下:

对于冲突证据集M′={mi,i=v+1,v+2,…, n}中的每一个mi,其权重为

把冲突证据合成,得到

这样证据由n条变为v+1条,即{mi,i=1,2,…,v+1}.

3)再次进行冲突检测.

返回步骤1),再次进行证据的冲突检测.

若存在1条以上的冲突证据,返回步骤2);

若只存在 1条冲突证据,把这条证据和正常证据中Dik′最大的证据进行步骤 2)中的加权合成,若其为0,则直接平均合成.返回步骤1);

若不存在冲突证据,进入步骤4).

4)结果修正.

经过前 3步的工作,冲突证据得到了消除,得到的证据集为M″={mi,i=1,2,…,v′}.

虽然M″中已不含冲突证据,但若在 M″中∃i,j, i=1,2,…,v′,j=1,2,…,r,使mi(Hj)=0且mi(Θ)= 0,利用D-S合成规则,不管其他证据对 Hj的支持度如何,最后证据合成的结果都是m(Hj)=0.文献[12]认为,这是由于证据 mi其实是来自少了命题Hj的另一识别框架的证据,而D-S规则组合不同识别框架上的证据时只给各证据共同的命题进行信度分配,所以无论对Hj的BPA函数为何值,只要有一条证据为0就会导致最终合成结果m(Hj)=0.这也是1.2的例子中m(A)和m(C)为0的原因.

以上分析说明,若一个证据对某命题的支持度为0(概率分配数为 0),则可看成该证据的识别框架没有这个命题,从而把原证据集的证据分在不同的框架下.而不同框架下的证据,即使按照前文所述的方法检测确认不存在冲突,也不能直接按 D-S规则进行合成,应该先对证据进行修正.方法如下:

把M″分成不同框架F={F1,F2,…,Fx}(Fi代表i框架下的证据条数,共x个框架,i=1,2,…,x).先在各框架内部用D-S规则进行合成,得到x个结果mi,i=1,2,…,x.然后找出F中的最大值Fmax,把为新证据m′的权重,对 m′进行修正,得ii到对应的m″i,修正公式如下:

最后应用D-S组合规则,得到最终结果.

5 数据实验结果与分析

假设识别系统中有 7个传感器,候选目标为{A,B,C},在某时刻获得的关于候选目标的BPA如表1所示.

表1 7个传感器获得的关于3个候选目标的BPATable 1 BPAs of three targets obtained by 7 sensors

从表 1中可以直观看出,传感器 2和 4与其他传感器获得的证据存在明显冲突.表 2示出了分别使用传统D-S组合规则、文献[12]的方法和文献[14]的方法及文中提出的方法进行证据合成的结果.

表2 不同方法的融合结果Table 2 Fusion resu lts of differentmethods

先关注前4次合成.一方面,由于受到冲突证据的影响,传统D-S组合规则多数情况下得不到正确的结果,而其他 3种方法能得到正确结果.另一方面,文中方法的收敛性最好,也即随着支持 A的证据越来越多,能使融合结果更快地向A聚焦.从计算复杂性来说,文献[12]的方法是最大的,它需要计算两两证据间的距离,n个证据要计算次,而文献[14]的方法只需要进行平均值运算,计算量最小,本方法加入了基于偏差的权值运算,由于计算方法简单,没有带来高的复杂性,却能使合成结果更具收敛性和可靠性.

对于最后一次合成,因为m7(B)=0.00,据前文所述,可以把证据m7看做来自识别框架{A,C}的证据,文献[14]把它和其他证据直接进行 D-S合成,导致命题 B的概率分配数为 0,这是不够准确的.文中提出的方法通过修正,使命题 B分配到应有的概率,结果不但更加精确,还比文献[12]更趋近于识别目标.

6 结语

本研究提出的利用偏差处理冲突证据的改进算法有效地解决了传统D-S证据合成规则组合冲突证据时的缺陷,同时也保证了非冲突证据的有效合成.与其他改进方法相比,本方法在收敛性、可靠性和计算复杂性方面具有优势.

[1] Dempster A P.A generalization of Bayesian inference [J].Journal of the Royal Statistiacal Society,Series B, 1968,30(3):205-247.

[2] Yager R R.On the Dempster-Shafer framework and new combination ru les[J].Information Science,1989,41 (2):93-137.

[3] 孙全,叶秀清,顾伟康.一种新的基于证据理论的合成公式[J].电子学报,2000,28(8):117-119.

Sun Quan,Ye Xiu-qing,Gu Wei-kang.A new combination rules of evidence theory[J].Acta Electronica Sinica, 2000,28(8):117-119.

[4] 吴根秀.冲突证据组合方法 [J].计算机工程,2005,31 (9):151-154.

Wu Gen-xiu.An approach for combining conflict evidences[J].Computer Engineering,2005,31(9):151-154.

[5] 向阳,史习智.证据理论合成规则的一点修正 [J].上海交通大学学报,1999(3):357-360.

Xiang Yang,Shi Xi-zhi.Modification on combination rules of evidence theory[J].Journal of Shanghai Jiaotong University,1999(3):357-360.

[6] 李弼程,王波,魏俊.一种有效的证据理论合成公式[J].数据采集与处理,2002,17(1):33-36.

Li Bi-cheng,Wang Bo,Wei Jun.An efficient combination rule ofevidence theory[J].Journalof Data Acquisition＆Processing,2002,17(1):33-36.

[7] MihaiCristian Florea,Anne-Laure Jousselme,Éloi Bossé, et al.Robust combination ru les for evidence theory[J]. In formation Fusion,2009,10(2):183-197.

[8] 张玉琢,余英.D-S证据理论中冲突证据组合分析[J].云南师范大学学报:自然科学版,2007,27(4): 29-32.

Zhang Yu-zhuo,Yu Ying.Analysis of conflict evidence combination about D-S evidential theory[J].Journal of Yunnan Normal University:Natural Sciences Edition, 2007,27(4):29-32.

[9] 林作铨,牟克典,韩庆.基于未知扰动的冲突证据合成方法[J].软件学报,2004(8):1150-1156.

Lin Zuo-quan,Mu Ke-dian,Han Qing.An approach to combination of conflicting evidences by disturbance of ignorance[J].Journal of Software,2004(8):1150-1156.

[10] Murphy C K.Combining belief function when evidence conflicts[J].Decision Support Systems,2000,29(1): 1-9.

[11] 邓勇,施文康,朱振福.一种有效处理冲突证据的组合方法[J].红外与毫米波学报,2004,23(1):27-32.

Deng Yong,Shi Wen-kang,Zhu Zhen-fu.Efficient combination approach of conflict evidence[J].Journal Infrared Millimeter and Waves,2004,23(1):27-32.

[12] 刘海燕,赵宗贵,刘熹.D-S证据理论中冲突证据的合成方法[J].电子科技大学学报,2008,37(5):701-704.

Liu Hai-yan,Zhao Zong-gui,Liu Xi.Combination of conflict evidences in D-S theory[J].Journal of University of Electronic Science and Technology of China,2008,37 (5):701-704.

[13] 张军,涂国平.加权平均法解决证据理论中的失效问题[J].微计算机信息,2007,23(33):202-203.

Zhang Jun,Tu Guo-ping.Weighted averaging approach to conflictevidence in D-Sevidence theory[J].Microcomputer In formation,2007,23(33):202-203.

[14] 关欣,衣晓,孙晓明,等.有效处理冲突证据的融合方法[J].清华大学学报:自然科学版,2009,49(1): 138-141.

Guan Xin,Yi Xiao,Sun Xiao-ming,et al.Efficient fusion app roach for conflicting evidence[J].Journal of Tsinghua University:Science and Technology,2009,49(1): 138-141.