证据特征提取及其在证据理论改进中的应用
第38卷增刊 2004年10月
上海交通大学学报
JOUR NAL OF SHANGHAI JIAOT ONG UNI VER SITY
Vol.38Sup. Oct.2004
收稿日期:2003-09-17
基金项目:国防重点实验室基金资助项目(51476040103JW13)
作者简介:杜 峰(1977-),男,湖北宜都人,博士生,研究方向为信息自动检测与处理.施文康(联系人),男,教授,博士生导师,
电话(Tel.):021-********;E-mail:wksh i@https://www.wendangku.net/doc/5810106945.html,.
文章编号:1006-2467(2004)S 1-0164-05
证据特征提取及其在证据理论改进中的应用
杜 峰, 施文康, 邓 勇
(上海交通大学电子信息与电气工程学院,上海200030)
摘 要:尽管DS 证据理论可以有效地处理不确定性信息,但是在证据高度冲突情况下,经典DS 证据组合规则因归一化过程往往会产生有悖常理的融合结果.为此,很多学者提出了许多不同的修改方法,可以归为两类:修改组合规则和修改证据.在总结这两类修改思路的基础上,分析了几种代表性的改进方法,同时通过引入证据距离,对证据源进行特征提取,提出了相应的改进方案.理论分析和数值实验结果表明,改进后的3种方法不仅能充分体现相应的改进思想,而且可以更好地实现证据组合,较快地收敛真实目标,得到合理的融合结果.关键词:证据理论;组合规则;权重;特征提取;证据距离中图分类号:O 21;T P 274 文献标识码:A
Fe ature Extra ction of Evide nce and Its Applica tion in
M odifica tion of Evidence Theory
DU Feng , SH I Wen -ka ng , DEN G Yong
(School of Electrical &Information Eng.,Shanghai Jiaotong Univ.,Shanghai 200030,China)Abstra ct :The classical DS evidence theory involves counter -intuitive behaviours when the high conflict in-formation exists.On the base of the two modification ideas,the modification of combination rules and the modification of evidence sources,this paper analyzed some typical existing modification methods and pro-posed to extr act the intrinsic char acter istics of the existing evidence sources by using evidence distance the-ory .With the application of the extracted feature ,three modification methods were proposed .From the results of the numer ical examples,the three proposed methods can not only realize the modification ideas,but also provide reasonable results with good conver gence efficiency.
Key words :evidence theory ;combination rule ;weighting factor ;feature extraction ;evidence distance
DS 证据理论已广泛用于信息融合和不确定推理等领域[1,2],它具有坚实的数学基础,能在不需要先验概率的情况下,以简单的推理形式,得出较好的融合结果.随着研究的深入,人们发现DS 证据理论在处理冲突证据时,因组合规则中的归一化过程会出现违背常理的结论[3].鉴于此,很多学者在证据理论改进方面做了很多工作,提出了许多不同的改进
思想和方法.通过分析,这些改进方法可以分为两类,一类是认为Dempster 组合规则有问题,需要修改组合规则,如Yager [4]方法、Dubios [5]方法等,另一类则认为组合规则没有问题,是给出的证据源需要修改,如Murphy [6]
方法等.引起问题的关键原因是冲突信息的存在,但冲突信息的存在是很复杂的,上述两类思想实际上是从不同的角度处理冲突信
息.本文在总结这两类修改思路的基础上,分析了相应的代表性的改进方法及其存在的问题,从而通过引入证据距离,对证据源进行特征提取,利用提取的特征对证据理论进行相应的修改,得到了合理的修改方案.
1 证据组合规则修改方法
关于DS证据理论的基本概念,本文不再赘述.由Dempster组合规则中归一化过程可以看出,组合规则将冲突信息完全抛弃,在数学结果上就引出不合常理问题.为此,很多学者认为在组合规则中,冲突信息不能简单地被抛弃,而应重新分配,即组合规则需要修改.典型的代表是Yager[4]的修改方法: m Y(A)=m∩(A) P A A(
m Y(()=m(()+m(5)
(1) 由式(1)可以看出,当两个证据高度冲突时, Yager将冲突信息全部划分给全域,也就是未知项m((),以等待新的证据再作判断.该方法虽能合成高冲突的证据,符合认知逻辑,但仍存在问题.
例1 设辨识框架(={A,B,C},证据源:
S1: m1(A)=0.99, m1(B)=0.01
m1(C)=0
S2: m2(A)=0, m2(B)=0.01
m2(C)=0.99
由Yager公式组合可得,m(5)=0.9999,m Y(A)= 0,m Y(B)=0.0001,m Y(C)=0,m Y(()=0.9999.该融合结果避免了出现违反常理的判断,但当有新证据源:
S3: m3(A)=0.99, m3(B)=0.01
m3(C)=0
加入时,或者后面有更多的支持A的证据源(如等同于S3的S4,…)加入时,合成的结果可表示为
m Y(A)=m Y(C)=0
m Y(B)→0, m Y(()→1
由此可见,在绝大多数证据源支持A的条件下,某一个证据源否定A,融合结果必然否定A.
针对Yager公式新引入的问题,一种很自然的想法是不全部将冲突信息分配给未知项m((),认为冲突信息部分可以利用.基于这一思想,文献[7]中通过定义证据可信度的概念,将冲突信息的一部分加权融合,一部分划分给未知领域,提出了新的组合公式,得出了较为合理的结果.该方法认为冲突信息有一部分可以利用,并取决于所定义的证据可信度函数,计算表明合成结果好于Yager公式合成的结果.所定义的证据可信度实际上是冲突信息的可利用度,但仍存在问题:
(1)所定义的可信度函数公式E具有一定的随意性,采用不同的函数关系作为可信度函数,可得出不同的融合结果.在例1中,当有上述4个证据源时,m(()=0.999901,k-=0.504,采用E=e-k-计算可得证据可信度E为0.604,若采用E=10-k-,E可下降为0.313,若采用E=1.1-k-,E又可上升到0.953.由于融合结果极大地依赖于方法中所定义的证据可信度E,这几种情况下的融合结果明显不一致.这就引出了一个新的问题,即在实际运用过程中如何确定适合的可信度函数.
(2)由其计算结果可以看出,当存在3个及3个以上证据源时,融合结果收敛到一致信息的速度比较慢,这对于在实时性要求比较高的目标辨识的过程中是不理想的.
(3)认为所有的证据源具有相同的可信度,而在例1中,证据源S2与其他证据源冲突较大,其可信度应该比其他证据源的可信度要低得多,而改进的公式无法体现出这一点.
另一个想法是认为冲突信息全部可以利用,按各个子集的平均支持程度全部分配给子集,意味着哪个子集的概率指派数值之和大,它所分配的份额就大,不存在未知项的分配,可称为一种强势决策思想.在文献[8]中定义了证据源的平均支持程度,把证据冲突信息量按各个命题的平均支持程度加权进行分配,以解决文献[7]中存在的上述问题(1),得到了新的组合公式.实际上,这种解决问题的思想已经和文献[7]中的不一样,它未保留Yager的思想,去掉了对未知项的分配.这种思想是一种朴素的加权平均策略,融合的结果与将所有证据源平均后的结果相近,但和文献[7]公式中的一样,存在着上述问题(3).
2 证据源修改方法
针对修改的组合规则,Haenni[9]指出,从实际应用角度看,都存在一个指定证据分配权重的问题,而且都不满足交换律和结合律,计算量问题将成为实际应用的瓶颈;从哲学的观点出发,修改组合规则可看成“用X方法解决模型Y,得到了违反直觉的结果Z,认为方法X是错误的”.显然这是不科学的,因为有可能是模型Y的不适合.因此,部分学者认为,Dempster的组合规则有其坚强的数学基础,是没有问题的,问题出在所给证据源上,需要通过修改降低冲突信息量后,再利用Dempster规则进行组合.典型的代表方法是Murphy的方法.Murphy[6]
165
增刊杜 峰,等:证据特征提取及其在证据理论改进中的应用
认为,在证据组合前,应将所有证据进行平均,然后将平均后的证据源进行组合.
运用Murphy 的方法所得的结果要好于直接运用Dempster 组合规则所得到的结果,而且这种方法保留了Dempster 组合规则的交换律和结合律.但可以看出,Murphy 是将各个证据源等同看待,每个证据源的权重都是一样的.然而,正如前面分析的,在实际系统中每个证据源的权重是不一样的,因而同样存在着文献[7]公式中的上述问题(3).
3 证据特征提取
为了提取证据特征,本文引入了文献[10]中提出的证据距离.每个证据源S i 看成一个2N
的行向量S i ,则两个证据源S i 、S j 之间的距离表示为
d (S i ,S j )=
12
(S i -S j )D =
(S i -S j )T
(2)
式中,D =为一个2N
×2N
的矩阵,其中
D =(A ,B )=?A ∩B ?/?A ∪B ?
A 、
B 为证据源中的子集.值得指出的是,该证据距
离不同于寻常意义上的欧式距离或马氏距离,文献[10]中有详细论证,这里不再赘述.引入证据距离后,两个证据源之间的相似度可表示为
sim(S i ,S j )=1-d (S i ,S j )
(3)
本文认为证据和证据之间的距离在某种意义上反映了证据的支持程度,两者的距离愈小,说明它们判断愈靠近;距离愈大,两者的差别愈大.而且,相互相似的证据越多,说明证据的判断越接近事物的本质,证据源的整体可信度越高.同时,如果证据中的一个能被其他证据支持,那么它的可信度应该增加,否则,它的可信度应该降低,即降低它对融合结果的影响.定义证据源整体的相似半径为
sim R =
∑K
i =1,i sim 2 (i ,j ) (4) 在证据都一致的情况下,意味着每个证据源都给出相同的判断,证据群体的相似半径表示为 sim R = C 2K ×1 2 (5) 当然,在实际中是一种理想群体情况.对于现有的证据源,群体可信度E 可表示为 E = ∑K i =1,i sim 2 (i ,j ) C 2K ×1 2 (6) 因而,E 表示现有证据源群体从整体上对理想的证据群体的逼近程度,以作为划分冲突信息的依据.如果每个证据源的判断都完全矛盾,即E =0,则证据源的群体可信度为0,冲突信息完全分配给未 知项,这与在各证据源完全相互矛盾时,很难作出判决是一致的.单个证据源S i 的支持度可定义为 sup(S i )= ∑K j =1,j ≠l sim(S i ,S j ) (7) 该证据源S i 的可信度定义为 cred i =sup(S i ) /∑K i =1 sup(S i ) (8) 通过上述分析,可提取证据源的两个有用特征:群体可信度E 和归一化了的第i 个证据的可信度cred i . 4 基于证据特征的证据理论改进 基于冲突信息量部分可以利用的思想,认为冲突信息的分配取决于所提取证据源群体可信度和单个证据源可信度的两个特征因素.基于此,本文提出 改进的冲突信息分配方案,即改进后的组合规则: m (A )=m ∩(A )+m (5)E ∑K i =1 (m i (A )cred i ) P A A (m (()=m (()+m (5)(1-E ) (9) 式中:cred i 表示第i 个证据的可信度,由式(8)确定;E 定义为证据源的群体可信度,由式(6)确定.可以看出,当每个证据源都完全矛盾时,提出的式(9)就完全退化为Yager 的公式,将冲突信息完全分配给未知领域. 基于冲突信息全部可以分配的思想,如同文献[8]中的方法,考虑不同证据源具有不同的可信度,提出如下改进公式: m (A )=m ∩(A )+m (5)∑K i =1 (m i (A )cred i ) P A A (m (()=0 (10) 式中,cred i 由式(8)确定. 基于修改证据源的思想,针对Murphy 的方法,本文认为对证据源不能进行简单的平均,而是赋予不同的可信度.修改后的证据源每个子集的概率指派表示为 mae(m )= ∑K i =1 (cred i ×m i )(11) 式中,cred i 由式(8)确定.然后,再将修改后的证据 运用Dempster 规则进行K 次组合. 5 数值实验 为了验证融合效果,对于本文提出的3种改进方案进行了数值实验仿真验算,并分别与现有的基 166 上 海 交 通 大 学 学 报 第38卷 于相应思想的改进方法进行了对比. 例2 设辨识框架(={A,B,C},证据源: S1: m1(A)=0.98, m1(B)=0.01 m1(C)=0.01 S2: m2(A)=0, m2(B)=0.01 m2(C)=0.99 S3: m3(A)=0.9, m3(B)=0 m3(C)=0.1 S4: m4(A)=0.9, m4(B)=0 m4(C)=0.1 其中S1、S3、S4都在很大程度上支持A,S2支持C. DS证据组合规则、Yager公式、文献[7]中的公式和本文式(9)融合的结果如表1所示.由表可见,多个证据源S1、S2、S3、S4时,DS证据理论、Yager 公式的融合结果都不合常理.根据文献[7]中的公式,当来了证据源S4后,m(A)=0.42,m(B)= 0.003,m(C)=0.181,m(()=0.396,即支持A的仍小于50%.严格来说,这意味着在3个证据表明是A,而一个否定A情况下,仍不能作出有效决策.根据式(9),当来了证据源S4后,m(A)=0.5967, m(C)=0.0713,m(()=0.3297,肯定判断为A接近60%,已可以作出有效决策.对比可以看出,式(9)收敛到一致信息要快于文献[7]中的公式.通过证据特征提取所求得的证据源群体可信度和个体可信度,这两个参数合理地反映证据源本身的固有特征,以此进行冲突信息分配,避免了人为的主观性,同时也降低了伪证据对融合结果的影响. 表1 融合结果对比 Ta b.1 The f usion r esults with diff er ent methods S1,S2,m(5)=0.99 S1,S2,S3,m(5)=0.99901 S1,S2,S3,S4,m(5)=0.999901 DS公式m(A)=0,m(B)=0.01m(A)=m(B)=0,m(C)=1m(A)=m(B)=0,m(C)=1 m(C)=0.99,m(()=0m(()=0m(()=0 Yager公式m(A)=0,m(B)=0.0001m(A)=m(B)=0m(C)=0.00099m(A)=m(B)=0,m(C)=0.000099 m(C)=0.0099,m(()=0.99m(()=0.99901m(()=0.999901 文献[7]公式m(A)=0.18,m(B)=0.004m(A)=0.321,m(B)=0.003m(A)=0.42,m(B)=0.003 m(C)=0.194,m(()=0.622m(C)=0.188,m(()=0.488m(C)=0.181,m(()=0.396 本文式(9)m(A)=0.0097,m(B)=0.0003m(A)=0.4683,m(B)=0.0027m(A)=0.5967,m(B)=0.0023 m(C)=0.0189,m(()=0.9711m(C)=0.061,m(()=0.4679m(C)=0.0713,m(()=0.3297 利用例2,DS证据组合规则、Yager公式、文献[8]中的合成公式和本文的公式(9)融合的结果如表2所示.由表可见,改进后的式(10),不仅能解决多个高冲突证据的融合问题,也能很快地收敛到一致信息,而且充分体现了强势决策的思想,融合结果优于文献[8]中普通加权平均的结果. 表2 融合结果对比 Ta b.2 The f usion r esults with diff er ent methods S1,S2,m(5)=0.99 S1,S2,S3,m(5)=0.99901 S1,S2,S3,S4,m(5)=0.999901 DS公式m(A)=0,m(B)=0.01m(A)=m(B)=0,m(C)=1m(A)=m(B)=0,m(C)=1 m(C)=0.99,m(()=0m(()=0m(()=0 Yager公式m(A)=0,m(B)=0.0001m(A)=m(B)=0,m(C)=0.00099m(A)=m(B)=0,m(C)=0.000099 m(C)=0.0099,m(()=0.99m(()=0.99901m(()=0.999901 文献[8]公式m(A)=0.4851,m(B)=0.01m(A)=0.626,m(B)=0.0067m(A)=0.6949,m(B)=0.005 m(C)=0.5049,m(()=0m(C)=0.3673,m(()=0m(C)=0.3001,m(()=0 本文式(10)m(A)=0.4851,m(B)=0.01m(A)=0.881,m(B)=0.0051m(A)=0.8902,m(B)=0.0034 m(C)=0.5049,m(()=0m(C)=0.1139,m(()=0m(C)=0.1064,m(()=0 例3 设辨识框架(={A,B,C},证据源: S1: m1(A)=0.5,m1(B)=0.2,m1(C)=0.3 S2: m2(A)=0,m2(B)=0.9,m2(C)=0.1 S3: m3(A)=0.55,m3(B)=0.1,m3(C)=0.35S4: m4(A)=0.55,m4(B)=0.1,m4(C)=0.35 S5: m5(A)=0.55,m4(B)=0.1,m5(C)=0.35其中:S1、S3、S4、S5的判断比较相近;S2的判断与其他证据源的出入较大. 167 增刊杜 峰,等:证据特征提取及其在证据理论改进中的应用 通过例3,本文将DS证据组合规则、Murphy 方法和本文提出的基于式(11)的改进Murphy方法进行了数据融合对比实验,验算结果如表3所示.由表可知,运用Muphy方法和本文提出的基于式(11)的改进方法所得到的融合结果明显好于DS合成公式的融合结果,显得更为合理和有效;而本文提出的公式和Murphy方法相比,由于考虑到不同证据源具有不同的权重,降低了伪证据的影响,能以较快的速度收敛到一致信息,比Murphy简单加权平均方法的效率要高. 表3 融合结果对比 Ta b.3 The f usion r esults with diff er ent methods S1,S2 S1,S2,S3 S1,S2,S3,S4 S1,S2,S3,S4,S5 DS公式m(A)=0m(A)=0m(A)=0m(A)=0 m(B)=0.8571m(B)=0.6316m(B)=0.3288m(B)=0.1228 m(C)=0.1429m(C)=0.3684m(C)=0.6712m(C)=0.8772 M urphy方法m(A)=0.1543m(A)=0.35m(A)=0.6027m(A)=0.7958 m(B)=0.7469m(B)=0.5224m(B)=0.2627m(B)=0.0932 m(C)=0.0988m(C)=0.1276m(C)=0.1346m(C)=0.111 基于式(11)的改进方法 m(A)=0.1543m(A)=0.4861m(A)=0.773m(A)=0.89 m(B)=0.7469m(B)=0.3481m(B)=0.0628m(B)=0.086 m(C)=0.0988m(C)=0.1657m(C)=0.16m(C)=0.1005 6 结 语 鉴于DS证据理论在冲突信息比较大的情况下融合出现的问题,本文在分析已有的改进思想的基础上,通过引入证据距离,提取了证据源的固有特征.针对几种不同的改进方法和存在的问题,成功地将所提取的证据特征应用于证据理论的修改中.理论分析和数值实验结果表明,应用了证据特征提取的修改方法,不仅解决高冲突信息量的多证据融合问题,同时具有较好的收敛效率.对比实验表明,本文所提出的3种修改方案得到的融合结果要显得更为合理. 参考文献: [1] Shafer G.T he Dempst er-Sha fer theory of evidence [M].P rinceton,NJ:Pr incet on Univer sity P ress, 1976. [2] Beynon M,Cur ry B,Mor gan P.T he Dempster- Shafer t heory of evidence:an alt ernative appr oach to multicrit eria decision modeling[J].Omega,2000, 28:37-50. [3] Zadeh L.A simple view of the Dempster-Shafer the- or y of evidence and its implication for the r ule of combination[J].AI Maga zine,1986,7:85-90. [4] Ya ger R.On the dempster shafer fra mework and new combination r ules[J].I nfor mation Sciences, 1987,41:93-137. [5] Dubois D,P rade H.Representation and combination of uncert ainty with belief functions and possibilit y measur es[J].Com putational Intelligence,1998,4: 244-264. [6] M ur phy https://www.wendangku.net/doc/5810106945.html,bining belief funct ions when evi- dence conflicts[J].Decision Suppor t Systems,2000, 29:1-9. [7] 孙 全,叶秀清,顾伟康.一种新的基于证据理论的 合成公式[J].电子学报,2000,28(8):117-119. SUN Qua n,YE Xiu-qing,GU Wei-kang.A new combina tion r ule of evidence theor y[J].Acta Elec- tr onica Sinica,2000,28(8):117-119. [8] 李弼程,王 波,魏 俊,等.一种有效的证据理论合 成公式[J].数据采集与处理,2002,17(1):33-36. LI Bi-cheng,WANG Bo,WEI Jun,et al.An effi- cient combina tion r ule of evidence theor y[J].J our- nal of Data Acquisition&Pr ocessing,2002,17(1): 33-36. [9] Haenni R.Ar e alternatives to Dempster's rule of combina tion real alter natives?Com ment s on“About t he belief funct ion combinat ion and the conflict man- agement problem”—Lefevre et a l[J].Inf or mation F usion,2002,3:237-239. [10] Jousselme A,Grenier D,Bosse E.A new distance between two bodies of evidence[J].I nfor mation Fu- sion,2001,2:91-101. 168 上 海 交 通 大 学 学 报第38卷