基于证据距离和不确定度的冲突数据融合算法
2018-05-21严志军
严志军,陶 洋
重庆邮电大学 通信与信息工程学院,重庆 400065
1 引言
在无线传感器网络实际的应用中,传感器采集到的数据经常是不精确和不确定的,如何有效地解决不确定信息一直是研究的热点,许多研究者提出了很多数学理论,如证据理论[1]、模糊集理论[2]、粗糙集理论[3]等,其中,由Dempster和Shafer提出来的D-S证据理论能够有效解决在缺乏先验概率的条件下数据不精确和不确定的问题[4-5],并且广泛应用于信息融合领域[6-9]。
但是,不同的传感器采集到的数据之间可能会出现冲突的现象,当直接利用Dempster融合规则处理冲突信息时,会出现悖论的融合结果。因此如何有效地处理无线传感器网络中数据冲突的问题,将是不可避免的[10-12]。Murphy提出在融合之前对证据进行修正,首先对信度函数进行平均化,之后再对数据进行融合的一种方法[13]。但是,这种证据平均的融合方法仅仅简单地对证据进行平均化,并没有考虑证据之间的联系。因此,并不能够很好地处理由错误数据引起的数据冲突的情况。邓勇教授则对融合规则进行提升,提出了一种加权平均的融合方法[14],虽然在一定程度上克服了Murphy规则的缺陷,但是却忽视了证据本身对最后权重的影响;而文献[15]则引入向量空间的概念,运用冲突证据的表示方法来解决数据冲突的问题,但是此方法仅考虑了不同证据信度分配结果的相似程度而忽略了其他因素对证据可信度的影响,如证据本身的不确定性。
基于以上分析,本文运用证据距离对证据之间的冲突性进行度量,将证据分为可信证据与不可信证据两类;接着运用信度熵对证据本身的不确定度进行估计,结合这两类因素对证据进行权重分配,对原始证据的基本信度值进行修正,最后运用Dempster融合规则进行融合,提出了一种基于证据距离和不确定度的冲突数据融合算法。提出的方法既考虑了证据之间的相互关联性,又考虑了证据本身的不确定性,因此能够很好地处理冲突数据融合的问题。
2 相关理论介绍
2.1 证据理论基本概念
证据理论(Evidence Theory)[16],是一种很好的对不确定性进行建模和推理的数学理论,设识别框Θ={w1,w2,…,wc},基本信度分配函数(BBA),即质量函数,m:2Θ→[0,1],满足以下条件:
其中,A是2Θ的一个子集,m(A)即为命题A的基本信度值,表示证据对命题A的支持度,每个命题都有对应的BBA,且BBA之间相互独立,对于∀A⊆Θ,A≠∅,Dempster组合规则定义为:
其中,i表示第i个证据。证据之间的冲突程度k定义为:
相比其他融合规则,贝叶斯融合需要事先了解概率分布,即需要知道先验概率;同样,基于模糊集理论的融合方法也需要事先了解不同模糊集的隶属函数,但是Dempster融合规则可以在事先不知道先验概率的条件下,对不确定、不精确的数据进行建模[17];并且,对来自于不同传感器数据源得到的不同证据,能够简单高效地融合多个证据,并且最终能够得到更加准确的融合结果。
2.2 证据距离
相对距离表示了证据体之间的相互支持度。其中使用较广泛、认可度高的是Jousselme提出来的证据距离表示方法[18]。
两个证据体m1()和m2()之间的距离dBOE(m1,m2)定义如下:
其中,m1和m2分别表示证据体m1()和m2()的向量形式。是2Θ×2Θ的矩阵:
当有多个证据时,任意两个证据体之间的距离可以以证据矩阵DM的形式表示,定义如下:
两个证据之间的距离越大,表示两个证据之间相互支持度就越低。如果一个证据体与其他证据高度冲突,则它应该对最后的融合结果有较小的影响。
2.3 信度熵
信度熵[19]能够有效地对信息的不确定度进行度量。设定假设集Ai,对应的信度函数为m, ||Ai表示集合Ai的元素个数,集合Ai信度熵计算如下:
当信度值仅分配给单元素集时,信度熵此时直接是香农熵,此时信度熵函数为:
如果一个证据体的信度熵越小,则相应的可靠度也越高,在最后的融合过程中,占据的权重也越大;相反,如果一个证据的信度熵越大,则不可靠度越高,占据的权重也越低。
3 基于证据距离和不确定度的冲突数据融合算法
假设有n个证据,mi,i=1,2,…,n,对于证据的预处理过程可以表示如下:
其中,wi是证据mi对应的权重。wimi可以认为是mi的折扣,m可以认为是原证据的加权平均证据。这n个证据是所有获得焦元的平均加权。因此如何构建合适的权重wi将是核心问题。
上文提到,假如一个证据与其他证据的证据距离越小,则表明它与其他证据的冲突性也较小,可将这类证据称之为可信任证据;相反,假如一个证据与其他证据的证据距离越大,则表明它与其他证据的冲突性也越大,可将此类证据称之为不可信证据。对于可信任证据,熵值越小,则表明不可确定度也越小,证据本身也更明确,更有利于最后的决策融合。因此,在融合过程中,此类证据应该占更大的权重。而对于不可信证据,熵值越小,对应的不确定度也越小,证据体本身也更明确。但是,因为与可信任证据和其他证据具有冲突性,为了得到更准确的融合结果,将分配较小的权重给不可信证据。基于此思想,提出了奖励函数与惩罚函数的概念,以此来创建合适的权重。
定义1(奖励函数)定义为:
其中为归一化后的信度熵,满足奖励函数具有如下的特性:
特性1奖励函数总是大于0,即αr>0。
特性2奖励函数是单调递减函数。
证明 根据指数函数的特性,很明显,奖励函数是单调递减的函数。它随着熵值的增大而减少,随着熵值的减少而增大,符合可信函数的特性,因此用来创建可信函数的权重。
定义2(惩罚函数)定义为:
这里,信度熵,满足惩罚函数有如下的特性
特性1惩罚函数永远大于0,即αj>0。
特性2惩罚函数是一个单调递增的函数。
证明 假设有任意两个变量
因为,根据指数函数的特性有:是说,惩罚函数是单调递增的函数,可用来为不可信证据创建权重。
假设有n个证据体,每个证据体权重的推导过程如下:
步骤1通过公式(4)和(5)可以计算任意两个证据mi和mj之间的距离矩阵:
其中i,j=1,2,…,n。
步骤2计算证据体mi的平均证据距离
步骤3计算证据体全局距离d:
步骤4判断证据是可信证据或者非可信证据:如果>d,则mi为可信证据;如果 <d,则mi为非可信证据。
步骤5计算信度熵Ed(mi),i=1,2,…,n,并且进行归一化处理:
步骤6为可信证据与不可信证据分配相应的权重αr和αj,i,j=1,2,…,n,对于可信证据使用公式(10)计算其相应的权重,对于非可信证据使用公式(11)计算其相应的权重。
步骤7最后对计算得到的权重进行归一化处理,得到证据最终的权重wi,计算如下:
通过以上推导,计算得到了每个证据合理的权重值,再根据公式(9)计算多源证据的加权平均证据m。最后通过Dempster融合规则对修正后的证据源进行BBA融合,得到最终的融合结果。
需要指出的是,当证据仅有两个证据时,此时,证据距离是失效的,此时的权重的计算方式如下:
步骤1计算信度熵Ed(mi),i=1,2,使用公式(16)对其进行归一化。
步骤2通过奖励函数计算权重αi1:
步骤3通过惩罚函数计算权重αi2:
其中是最大归一化信度值。
步骤4计算平局权重αi:
即为最终的权重wi,最后计算加权平均证据,使用Dempster融合规则进行融合。
4 仿真与分析
为了验证文中提出的算法的性能,本文将采用文献[20]中的完整算例进行仿真分析与对比。设有3个目标待识别,即识别框为:Θ={A,B,C},收集到5个证据对其进行判别:
首先,根据公式(5)和(6)计算距离矩阵得:
运用公式(14)计算平均证据距离,i=1,2,3,4,5,0.298 6。
接着运用公式(15)计算全局证据距离d的结果如下:d=0.403 74。可知,m1,m3,m4,m5归为可信证据,而m2为不可信证据。通过公式(8)计算每个证据体所对应的信度熵为:
再通过公式(16)计算归一化信度熵:
通过公式(18)与(19)分别计算可信证据与不可信证据的权重αi,i=1,2,3,4,5,通过公式(17)归一化权重得:w1,w2,w3,w4,w5,如表1所示。
表1 归一化权重
计算出每个证据的权重之后,通过平均权重对原始数据进行修正,得出以下修正后的BBA,如表2所示。
在得到修正后的BBA之后,再利用Dempster融合规则对多个证据进行融合,得到最终的融合结果,如表3所示。
在使用本文提出的融合算法计算出最终融合结果之后,再使用四种应用广泛的融合规则计算出相应的融合结果,并且进行对比,具体的融合结果以及仿真对比图如图1,2所示。
图1 基于不同融合规则的m(A)的BBA
图2 基于不同融合规则的m(B)的BBA
从仿真结果图1以及表4可以得出尽管5个证据源中有4个证据源支持目标A,但是由于冲突证据S2,Dempster融合规则融合后得出一个错误的结果。很明显,Dempster融合不能够很好地处理数据冲突的问题。
从仿真图2可以得出,由于不可信证据S2,只有本文提出的基于不确定度和信度熵的融合方法分配较小的信度给目标B,然而其他的融合方法都分配较多的信度给B。同时还可以得出,当有三个证据源时,Dempster规则、Deng规则,以及Murphy法则融合结果并不能为融合中心提供决策,因为这三种法则分配给目标A的信度值都小于0.5,其他的目标B,C,AC的信度值分配较多,只有Han融合规则和本文提出的融合规则分配给A的信度值高于0.5,并且新的融合法则分配给目标A的值高达0.827 4,然后Han法则只有0.518 8。当有5个证据源进行融合时,证据源越多,信度值分配得越合理,新的融合方法将信度值基本上分配给了目标A,高达0.990 4。
表2 使用平均权重修正后的BBA
表3 融合后的结果
因此,当证据高度冲突时,经典的Dempster融合规则融合的结果将会产生严重的悖论,不能够很好地反映真实的情况。随着证据体的增加,尽管Murphy简单平均融合规则、Deng加权平均融合规则以及Han融合规则都能够给出一个合理的融合结果,但是,本文提出的基于证据距离和不确定度的冲突数据融合规则性能都比这几种融合法则优秀。
5 结束语
本文对使用经典证据理论进行融合的过程中,当遇到高冲突的数据时,融合结果会产生悖论等问题进行详细的分析,以往的研究更多的是考虑证据之间的相互关联性,而忽视了证据本身对融合性能的影响。本文通过一种新的信度熵的方法对证据本身的不确定性进行度量,最后的实验结果证明提出的基于证据距离和不确定度估计的冲突数据融合方法能够更有效地处理冲突数据融合的问题。
:
[1]Dempster A P.Upper and lower probabilities induced by a multivalued mapping[J].Ann Math Stat,1967,38(2):325-339.
[2]Klein L A.Sensor and data fusion:a tool for information assessment and decision making[M].Bellingham’WA:SPIE Press,2004.
[3]Pawlak Z.Rough sets[J].International Journal of Computer and Information Sciences,1982,11(5):341-356.
[4]Su X,Mahadevan S,Han W,et al.Combining dependent bodies of evidence[J].Appl Intell,2016,44(3):634-644.
[5]Jiang W,Yang Y,Luo Y,et al.Determining basic probability assignment based on the improved similarity measures of generalized fuzzy numbers[J].International Journal of Computers Communications&Control,2015,10(3).
[6]LLiu Z G,Pan Q,Dezert J.A belief classification rule for imprecise data[J].Applied Intelligence,2014,40(2):214-228.
[7]Wang X,Huang J Z.Editorial:uncertainty in learning from big data[J].Fuzzy Sets&Systems,2014,258:1-4.
[8]Jiang W,Wei B,Xie C,et al.An evidential sensor fusion method in fault diagnosis[J].Advances in Mechanical Engineering,2016,8(3).
[9]Yang Y,Han D.A new distance-based total uncertainty measure in the theory of belief functions[J].Knowledge-Based Systems,2015,94:114-123.
[10]Xu Xiaobin,Liu Ping,Sun Yanbo,et al.Fault diagnosis based on the updating strategy of interval-valued belief structures[J].Chinese Journal of Electronics,2014,23(4):753-760.
[11]Moosavian A,Khazaee M,Najafi G,et al.Spark plug fault recognition based on sensor fusion and classifier combination using Dempster-Shafer evidence theory[J].Applied Acoustics,2015:120-129.
[12]Yu C,Yang J,Yang D,et al.An improved conflicting evidence combination approach based on a new supporting probability distance[J].Expert Systems with Applications,2015,42(12):5139-5149.
[13]Murphy C K.Combining belief functions when evidence conflicts[J].Decision Support Systems,2000,29(1):1-9.
[14]Yong D,Shi W K,Zhu Z F,et al.Combining belief functions based on distance of evidence[J].Decision Support Systems,2004,38(3):489-493.
[15]Zhang Z,Liu T,Chen D,et al.Novel algorithm for identifying and fusing conflicting data in wireless sensor networks[J].Sensors,2014,14(6):9562-9581.
[16]Jameslnglis.A mathematical theory of evidence[J].Technometrics,1976,20(1).
[17]Su X,Mahadevan S,Xu P,et al.Handling of dependence in Dempster-Shafer theory[J].International Journal of Intelligent Systems,2015,30(4):441-467.
[18]Jousselme A L,Grenier D,Bossé É.A new distance between two bodies of evidence[J].Information Fusion,2001,2(2):91-101.
[19]Deng Y.Deng entropy:a generalized Shannon entropy to measure uncertainty[J/OL].Vixra.org,2015.
[20]Han D Q,Yong D,Han C Z,et al.Weighted evidence combination based on distance of evidence and uncertainty measure[J].Journal of Infrared&Millimeter Waves,2012,30(5):396-400.