随着传感器技术的发展,在实际决策问题中,多元信息被越来越多地使用. 一方面这些信息需要被融合起来以做出决策,另一方面这些信息都会受测量不精确、 扰动及某些未知因素的影响,从而在不同程度上具有不同形式的不确定性. 如何表示并融合这些含有不确定性的信息进而形成决策是一个重要问题. 目前已有多种不确定处理方法,其中证据理论通常被认为是贝叶斯理论的一种拓展,具有较好的理论基础,它可以不需要先验知识,并能区分不知道与不确定,因而对问题的描述更加灵活准确,是一种良好的不确定性推理方法,已在目标识别[1, 2]、 故障诊断[3, 4]与模式识别[5, 6]等领域得到了广泛应用.
证据理论中证据合成规则是一个核心内容,Dempster规则是最早提出的,并且具有一些良好的性质,是目前最为常用的方法. 然而面对高度冲突证据,该规则可能出现有违直观的结果[7]. 针对这一问题,许多学者进行了研究并提出了一系列的改进方法. 这些方法大体可以分为两类: 一类认为Dempster规则存在缺陷,需对其进行修正[8, 9, 10, 11, 12, 13]; 另一类认为原因不在于Dempster规则,而是对问题建模不准确,需要对证据进行预处理,然后再进行组合[14, 15, 16, 17, 18, 19]. 这些方法都各有一定的合理性,但也存在一定问题. 对规则的修改多数破坏了Dempster规则的结合律,而对证据进行预处理则改变了证据的特异性,并且没有区分考虑证据的可靠性与重要性[20]. 文[20]认为证据的可靠性反映的是产生证据的信息源的可靠程度,是客观属性; 而证据的重要性反映的是不同信息对决策结果的影响程度,如分类问题中不同属性对分类正确率的贡献经常有很大差异,一定程度上含有决策者的主观因素. 在此基础上,Yang等提出一种新的证据合成规则——证据推理(ER)规则. 该规则对证据进行预处理后使用Dempster规则合成,不仅满足交换律和结合律,并且预处理过程中证据的特异性保持不变,从而是一个广义的概率推理过程. 目前,该规则已在故障诊断、 多属性决策等领域取得了广泛应用.
当融合一组证据时,ER规则不要求归一化证据权重,但某些情况下权重归一化有利于获取更合理的结果; 而在证据预处理方面,虽然加权信度分配与证据折扣不同,但形式上具有很大相似性. 虽然ER规则考虑了证据的重要性与可靠性,但从复合权重的定义上看,可靠性只是作为重要性的一个调节因子,可能会出现不可靠证据提供有用信息的不合理情况. 基于以上几方面问题,本文对权重归一化的影响、 ER规则与证据折扣方法的关系及ER规则存在的问题及解决方法进行分析论述.
2 证据理论与ER规则证据理论是由Dempster[21]提出,后经Shafer[22]发展建立起来的不确定推理理论. 证据合成方法是一个核心研究内容,一直受到广泛关注. ER规则是近期提出的一种方法,因能有效融合具有不同重要性及可靠性的证据,能更好地与实际情况相吻合,被广泛应用.
2.1 证据理论设Θ为N个互斥元素θ1,…,θN构成的识别框架,其所有子集构成的集合(即幂集)记作Ω. 若函数m: Ω→[0,1],满足$\sum\limits_{A\subset \Theta }^{{}}{{}}$m(A)=1,m(∅)=0,其中∅表示空集,则称m为一个基本概率赋值(basic probability assignment,BPA),也称为mass函数. m(A)反映的是对命题A的直接支持程度. 若m(A)>0,则称A为焦元.
若m1、 m2为识别框架Θ上的2个BPA函数,则利用Dempster规则融合的结果仍然是Θ上的一个BPA函数,其合成结果如下:
针对证据不完全可靠的情形,Shafer提出证据折扣方法予以处理. Smets[23]进一步从理论上分析了此方法的合理性. 设m是定义在框架Θ上的一个BPA函数,记折扣因子为α,则折扣后的证据可表示为
ER规则使用一种新的证据预处理方法,即加权信度分配(weighted belief distribution,WBD). 设mi的权重为wi,则其WBD定义为
与证据折扣不同,这里1-wi不是分配给了识别框架Θ,而是赋给框架的幂集Ω,表示的是受m权重限制而保留未分配的信度值; 它可以重新分配给框架中的任意子集,具体视其它证据的权重而定.
考虑到可靠性与重要性的区别,文[20]进一步提出一种考虑可靠性的加权信度分配(weighted belief distribution with reliability,WBDR)方法. 设mi的权重和可靠性分别为wi和ri,则对应的WBDR定义为
该式与WBD在形式上一致,证据可靠性实际上是重要性的一个修正因子.
将原始BPA表示成WBD或者WBDR之后,ER规则使用Dempster规则对证据进行合成运算:
若有L>2条证据,则在证据逐一融合过程中应保持Ω作为一个焦元,直到L条证据都完成融合,才将剩余信度(Ω)按比例重新分配给其它焦元.
3 ER规则性质研究ER规则是将ER算法[24]从贝叶斯信任函数拓展到一般的信任函数. 在ER算法中,权重要求是归一化的,即∑wi=1. ER规则取消了这一限制条件. 但权重归一化与否肯定会导致不同的结果,何时需要归一化是个问题. 证据折扣与WBD在证据预处理上有很大相似性,且都使用Dempster规则合成证据,结果必然也存在相似性.
3.1 权重归一化的影响当有多条证据时,权重归一化操作会使得所有权重等比例下降. 为方便分析,首先考虑2条证据并且权重相等的情况.
定理1 若m1、 m2是框架Θ上的2个BPA,权重分别为w1和w2,且w1=w2=w. 记m=m1⊕m2,mw=${\hat{m}}$1⊕${\hat{m}}$2,${\bar{m}}$=(m1+m2)/2,则随w减小,mw将趋近于${\bar{m}}$.
证明 记Σ=$\sum\limits_{B\cap C=A}^{{}}{{}}$m1(B)m2(C),根据ER规则可得
m可视为mw的一种特殊情况,即w=1. 现w从1开始减小,若m(A)>(A),则其信度值将下降; 反之若m(A)<(A),则其信度值将上升. 又
定理1的结论很容易推广到L>2条证据的情形. 类似上述证明过程,若2条证据不相等,则当它们的权重等比例下降时,融合结果趋近于原证据的加权平均.
例1 设框架Θ={θ1,θ2,θ3}上定义有2个BPA函数:
m1和m2的权重分别为w1=0.8,w2=0.9,记mw=${\hat{m}}$1⊕${\hat{m}}$2,=(w1m1+w2m2)/(w1+w2). 对w1和w2同乘以比例系数λ,则mw-${\bar{m}}$随λ的变化趋势如图 1所示. 可见,随λ减小,mw逐渐向m1和m2的加权平均趋近.
由以上结论可知,在融合一组证据,尤其是证据较多的情况下,归一化权重将导致所有证据权重都很小,从而使得融合结果非常接近于加权平均证据,不利于信度的收敛. 因此,当一组证据之间相互冲突不是很大或冲突证据的权值较小,适宜直接使用原始权重进行融合; 但是当证据存在很大冲突,并且冲突证据的权值很大时,对权重归一化后再融合得到的结果更为合理.
例2 设框架为Θ={θ1,θ2,θ3},m1、 m2为2个BPA函数,其定义为
直接使用原始权重,ER规则的合成结果为m({θ1})=0.671,m({θ2})=0.011,m({θ3})=0.318. 虽然m1对θ1的支持程度与m2对θ3的支持程度相同,且2条证据的权重也非常接近,但是合成结果对θ1和θ3的支持却差距很大. 若对权重归一化后再融合,则其结果为m({θ1})=0.522,m({θ2})=0.010,m({θ3})=0.468. 因m1权重略大,故对θ1的支持也略大,与直观要求更为相符.
此外,根据定理1结论,当使用ER规则融合多条证据且权重需要归一化时,例如在扩展置信规则库(extended belief rule base,EBRB)[25],可使用加权平均作为近似以进一步简化计算.
3.2 ER规则与证据折扣的关系证据折扣方法对所有焦元的信度按固定比例折扣,剩余信度赋予框架作为全局不确定性,可重新分配给任意子集; ER规则也是对所有焦元乘以权重,但剩余信度不是赋予框架,而是其幂集,该信度在合成过程中同样可以重新分配给任意子集. 事实上,Θ和Ω在融合过程中扮演着相同的角色,只在最终是否重新分配的问题上有所区别.
定理2 若m1、 m2是定义在Θ上的2个BPA函数,α1、 α2及w1、 w2分别是它们的折扣因子和权重系数. 记mα=m1α1⊕m2α2,mw=${\hat{m}}$1⊕${\hat{m}}$2,mw是将${\hat{m}}$w(Ω)重新分配后的结果. 若α1=w1,α2=w2,则:
证明 根据式(1)和式(3)可得
通过循环使用上述结论,可将其推广至多条证据的合成. 对一组证据m1,…,mN,记其权重分别为w1,…,wN. 2种方法的合成结果分别表示为mα=m1α1⊕…⊕mNαN,mw=${\hat{m}}$1⊕…⊕${\hat{m}}$N. 若αi=wi,i=1,…,N,则
利用ER规则合成证据时,Ω也被视为一个焦元参与运算,一定程度上增加了计算的复杂度. 而根据以上结论,可直接使用证据折扣方法获取ER规则的合成结果,步骤如下:
1) 令αi=wi,通过式(3)进行折扣,得到miαi.
2) 使用Dempster规则合成折扣后的证据,得${\hat{m}}$w=mα及冲突系数K.
3) 通过式(9)对w进行归一化处理,并令mw(Θ)=1-$\sum\limits_{A\subset \Theta ,A\ne \Theta }^{{}}{{}}$mw(A).
该方法在证据折扣的基础上,增加了一步归一化过程,不仅相对简化了计算,而且在算法实现上可直接利用已有的证据折扣算法.
4 ER规则的问题与改进虽然WBDR兼顾了证据的重要性及可靠性,但是两者并不是同等对待,而是利用可靠性对证据权重进行调整:${\tilde{m}}$ i=wi/(1+wi-ri). 该方法以证据的重要性为根本,如果证据可靠则进一步增大权重,反之则减小其权重,但无论在哪种情况下复合权重总大于0. 然而事实上证据的可靠性也很重要,如果一条证据的可靠性不能得到保障,则无论其重要性如何,其信息都不能作为参考依据. 因此WBDR表示方法存在一定问题. 例如,当ri=0时,${\tilde{m}}$i=wi/(1+wi)>0,即使证据完全不可靠,它在融合过程中仍有一定的作用; 当ri=1时,${\tilde{m}}$i=1,如果证据都是可靠的,则它们的相对重要性将不再被考虑,这显然也是不合理的. 一般地,若信息完全不可靠则在融合中不应采用,若信息可靠,则根据其重要性决定影响的大小.
根据以上分析,本文认为证据的可靠性和重要性都很重要,只有既可靠又重要的证据才能有较大影响,故使用两者乘积作为等效证据权重,修改后的WDBR定义如下:
与原始WBDR不同,式(11)中重要性和可靠性地位相同,当ri=0或wi=0时,${\tilde{m}}$i在融合中不起作用,即完全不可靠或者对问题决策没有作用的信息不影响融合结果; 当ri=1或wi=1时,等效权重由另一因素决定.
下面以文[20]中例2为例,对ER规则与修改后的方法进行比较.
例1 设m1,m2,m3是框架Θ={θ1,θ2,θ3}上定义的3个BPA,如表 1中第2~4行所示. 它们对应的可靠性和重要性权重分别为r1=0.8,r2=0.5,r3=0.2; w1=0.9,w2=0.3,w3=0.6. 利用ER规则和修改后的规则合成证据,结果如表 1中第5行和第7行所示.
∅ | θ1 | θ2 | θ1,θ2 | θ3 | θ1,θ3 | θ2,θ3 | Θ | |
m1 | 0 | 0.8 | 0 | 0.1 | 0 | 0.1 | 0 | 0 |
m2 | 0 | 0.4 | 0.3 | 0.2 | 0 | 0 | 0.1 | 0 |
m3 | 0 | 0.1 | 0.3 | 0 | 0.5 | 0 | 0 | 0.1 |
ER,1 | 0 | 0.706 1 | 0.083 5 | 0.074 3 | 0.067 1 | 0.053 6 | 0.007 1 | 0.008 3 |
ER,2 | 0 | 0.401 9 | 0.229 4 | 0.045 0 | 0.250 0 | 0.020 6 | 0.011 0 | 0.042 2 |
ER改,1 | 0 | 0.751 6 | 0.039 1 | 0.092 7 | 0.027 9 | 0.079 1 | 0.005 4 | 0.004 1 |
ER改,2 | 0 | 0.284 4 | 0.253 4 | 0.043 1 | 0.326 9 | 0.016 3 | 0.013 1 | 0.062 8 |
此时,最可靠的证据对应的证据权重也是最大的,所以两种方法的合成结果比较接近. 由于m2可靠性较高但权重最小,而m3虽然权重较大但可靠性太低,修改后的方法中它们所起的作用略有降低,使得对θ1的支持略有上升.
现若将m1和m3的可靠性互换,即r1=0.2,r3=0.8. 两种方法对应的合成结果分别如表 1中第6行和第8行所示. 在此情况下,权重最大的证据同时也是最不可靠的,势必导致合成结果的不确定性增大. 尽管ER规则对命题θ2和θ3的支持有所增大,但是θ1仍较有优势. 而修改规则对3个基本命题的支持更为接近,θ3略有优势,这是因为m1虽权重最大但几乎不可靠,m2本身具有较大不确定性且权重很小,而m3此时不仅是最可靠的且其权重也较大,故起主导作用.
修改后的规则同样满足文[20]中给出的4条合成公理,以下给出证明. 设有证据m1,…,mL,权重和可靠性满足0<wi<1,0<ri<1,i=1,…,L,记m=${\hat{m}}$1⊕…⊕${\hat{m}}$L.
定理3 如果子集A满足对∀B⊃A有mi(B)=0,i=1,…,L,则m(A)=0.
证明 根据ER合成规则可知:
定理4 如果mi(A)=1,mi(B)=0,∀B⊂Θ,B≠A,i=1,…,L,则融合结果中m(A)=1,m(B)=0,∀B≠A.
证明 ${\hat{m}}$(B)=k$\sum\limits_{{B_i} \subset \Theta or{B_i} = \Omega ,1 \le i \le L{\rm{|}}{B_1} \cap \cdots \cap {B_L} = B{\rm{ }}}^{} {} $1(B1)…${\hat{m}}$L(BL),若B≠A,则对任意一组B1,…,BL至少存在一个i满足A≠Bi,即存在${\hat{m}}$i(Bi)=0. 因此m(B)=0,∀B≠A.
因只有${\hat{m}}$(A)>0,${\hat{m}}$(Ω)只能重新分配给子集A,所以有m(A)=1.
定理5 记Θ+为所有L个BPA的焦元及焦元子集构成的集合,即Θ+={B|B⊂A,∀mi(A)>0,A⊂Θ,i=1,…,L},则融合结果中m(B)=0,B⊄Θ+且$\sum\limits_{A\subset {{\Theta }^{+}}}^{{}}{{}}$m(A)=1.
证明 由Θ+的定义可知,若B⊄Θ+,则对∀mi(A)>0,有B⊄A. 而B1∩…∩BL=B意味着B⊂Bj,1≤j≤L,因此Bj∉Θ+,mj(Bj)=0,
对任一焦元A因${\hat{m}}$1(Ω)…${\hat{m}}$i-1(Ω)${\hat{m}}$i(A)${\hat{m}}$i+1(Ω)…mL(Ω)>0,故${\hat{m}}$(A)>0. 同理,不同证据的焦元的交集融合后信度也为正. 而由于${\hat{m}}$(B)=0,B⊄Θ+,故${\hat{m}}$(Ω)只能重新分配给Θ+中信度不为0的子集,所以$\sum\limits_{A\subset {{\Theta }^{+}}}^{{}}{{}}$m(A)=1.
定理6 若至少存在一个i满足mi(A)>0,则m(A)>0.
证明 若mi(A)>0,则有${\hat{m}}$ (A)≥${\hat{m}}$1(Ω)…${\hat{m}}$i-1(Ω)·${\hat{m}}$i(A)${\hat{m}}$i+1(Ω)…mL(Ω)>0. 故m(A)>${\hat{m}}$(A)>0.
5 结论证据推理规则通过WBD和WBDR分别建模表征证据的重要性与可靠性. 本文就ER规则中权重变化对证据合成结果的影响进行分析,据此可根据实际情况考虑是否需归一化权重,而在权重归一化的场合下可考虑能否使用加权平均近似合成结果. 证明了ER规则和证据折扣方法存在紧密联系,即两者的合成结果除框架之外,所有焦元的信度都只相差一个比例系数,故可通过证据折扣实现ER算法,一定程度上简化了计算. 针对ER规则中可能出现不可靠证据仍在融合中有一定作用的问题,提出了一种改进方法,通过算例说明了其有效性,并证明修改后的方法仍满足4条证据合成公理.
[1] | 邓鹏华, 毕义明, 刘卫东, 等. 改进的证据理论在目标识别中的应用[J]. 系统工程与电子技术, 2008, 30(7): 1295-1297. Deng P H, Bi Y M, Liu W D, et al. Applications of a modified evidence theory in target recognition[J]. Systems Engineering and Electronics, 2008, 30(7): 1295-1297. |
[2] | 耿涛, 卢广山, 张安. 基于直觉模糊证据合成的多传感器目标识别[J]. 控制与决策, 2012, 27(11): 1725-1728, 1734. Geng T, Lu G S, Zhang A. Intuitionistic fuzzy evidence combination algorithm for multi-sensor target recognition[J]. Control and Decision, 2012, 27(11): 1725-1728, 1734. |
[3] | 徐晓滨, 王玉成, 文成林. 评估诊断证据可靠性的信息融合故障诊断方法[J]. 控制理论与应用, 2011, 28(4): 504-510. Xu X B, Wang Y C, Wen C L. Information-fusion method for fault diagnosis based on reliability evaluation of evidence[J]. Control Theory & Applications, 2011, 28(4): 504-510. |
[4] | Basir O, Yuan X H. Engine fault diagnosis based on multi-sensor information fusion using Dempster-Shafer evidence theory[J]. Information Fusion, 2007, 8(4): 379-386. |
[5] | Liu Z G, Pan Q, Dezert J. A new belief-based K-nearest neighbor classification method[J]. Pattern Recognition, 2013, 46(3): 834-844. |
[6] | 李芳, 李一媛, 王冲. 不确定数据的决策树分类算法[J]. 计算机应用, 2009, 29(11): 3092-3095. Li F, Li Y Y, Wang C. Uncertain data decision tree calssification algorithm[J]. Journal of Computer Applications, 2009, 29(11): 3092-3095. |
[7] | Zadeh L A. On the validity of Dempster's rule of combination of evidence[M]. Berkely, CA, USA: University of California, 1979. |
[8] | 孙全, 叶秀清, 顾伟康. 一种新的基于证据理论的合成公式[J]. 电子学报, 2000, 28(8): 117-119. Sun Q, Ye X Q, Gu W K. A new combination rules of evidence theory[J]. Acta Electronica Sinica, 2000, 28(8): 117-119. |
[9] | 陈圣群, 王应明. 基于Pignistic概率距离的最优证据合成法[J]. 信息与控制, 2013, 42(2): 213-217, 228. Chen S Q, Wang Y M. Optimal combination of evidence based on Pignistic probability distance[J]. Information and Control, 2013, 42(2): 213-217, 228. |
[10] | Smets P, Kennes R. The transferable belief model[J]. Artificial Intelligence, 1994, 66(2): 191-234. |
[11] | Smets P. Analyzing the combination of conflicting belief functions[J].. Information Fusion, 2007, 8(4): 387-412. |
[12] | Dezert J, Smarandache F. Advances and applications of DSmT for information fusion (collected works)[M]. 2nd ed Rehoboth, USA: American Research Press, 2006. |
[13] | Lefevre E, Colot O, Vannoorenberghe P. Belief function combination and conflict management[J]. Information Fusion, 2002, 3(2): 149-162. |
[14] | Deng Y, Shi W K, Zhu Z F. Combining belief functions based on distance of evidence[J]. Decision Support Systems, 2004, 38(3): 489-493. |
[15] | Schubert J. Conflict management in Dempster-Shafer theory using the degree of falsity[J]. International Journal of Approximate Reasoning. 2011, 52(3): 449-460. |
[16] | Liu Z G, Dezert J, Pan Q. Combination of sources of evidence with different discounting factors based on a new dissimilarity measure[J]. Decision Support Systems, 2011, 52(1): 133-141. |
[17] | 韩德强, 韩崇昭, 邓勇, 等. 基于证据方差的加权证据组合[J]. 电子学报, 2011, 39(z1): 153-157. Han D Q, Han C Z, Deng Y, et al. Weighted combination of conflicting evidence based on evidence variance[J]. Acta Electronica Sinica, 2011, 39(z1): 153-157. |
[18] | 周哲, 徐晓滨, 文成林, 等. 冲突证据融合的优化方法[J]. 自动化学报, 2012, 38(6): 976-985. Zhou Z, Xu X B, Wen C L, et al. An optimal method for combining conflicting evidences[J]. Acta Automatica Sinica, 2012, 38(6): 976-985. |
[19] | 柯小路, 马荔瑶, 王永, 等. 证据理论的模糊折扣方法[J]. 小型微型计算机系统, 2015, 36(2): 285-289. Ke X L, Ma L Y, Wang Y, et al. A fuzzy discounting method for evidence theory[J]. Journal of Chinese Computer Systems, 2015, 36(2): 285-289. |
[20] | Yang J B, Xu D L. Evidential reasoning rule for evidence combination[J]. Artificial Intelligence, 2013, 205: 1-29. |
[21] | Dempster A P. Upper and lower probabilities induced by a multivalued mapping[J]. Annals of Mathematical Statistics, 1967, 38(2): 325-340. |
[22] | Shafer G A. A mathematical theory of evidence[M]. Princeton, NJ, USA: Princeton University Press, 1976. |
[23] | Smets P. Belief functions-the disjunctive rule of combination and the generalized bayesian theorem[J]. International Journal of Approximate Reasoning. 1993, 9(1): 1-35. |
[24] | Yang J B, Xu D L. On the evidential reasoning algorithm for multiple attribute decision analysis under uncertainty[J]. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2002, 32(3): 289-304. |
[25] | Liu J, Martinez L, Calzada A, et al. A novel belief rule base representation, generation and its inference methodology[J]. Knowledge-Based Systems, 2013, 53: 129-141. |