基于集合覆盖模型的冲突证据合成

米据生，胡志勇，李磊军，梁美社

(1.河北师范大学 数学与信息科学学院 河北 石家庄 050024；2.石家庄职业技术学院 河北 石家庄 050081)

0 引言

不确定性推理[1]处理的是不清晰、不确定、不完全的信息.在描述及精确融合不确定信息时，D-S证据理论[2-3]体现出极高的灵活性和高效性.在不确定性推理、多源信息融合和决策分析等领域，D-S证据理论也具有极大影响.Dempster定义的组合规则[4]在对证据进行融合和更新方面是非常有效的,它应用的前提条件是融合规则的各部分是清晰可靠的.然而在很多的实际应用中，这个条件往往过于苛刻.如果直接将Dempeter定义的组合规则用来处理不可靠的信息，特别是具有冲突的信息,最终得到的结果可能会与我们的直觉相悖[5].因此，冲突证据的合成受到学者们的重视，大量的研究工作[6-10]也在这一背景下开展.集合覆盖问题作为一个经典的最优化问题，在很多领域也都有着广泛的应用[11-12]，如人员调动、网络安全、资源分配等领域.文献[13]为解决实际生活中的问题，将集合覆盖问题同粗糙集理论[14-15]相结合提出了覆盖粗糙集模型，使得集合覆盖问题同信息系统的联系更加紧密.近年来利用集合覆盖的思想处理信息系统中的问题受到研究者的广泛关注[16-17].

本文提出了一种名为基于集合覆盖模型的冲突证据合成(CCEM)的方法，该方法运用了集合覆盖的思想及文献[18]中提出的概念支撑的思想.将带有冲突证据的信息系统用非冲突的信息系统来覆盖，之后利用概念支撑的思想定义每个子系统的权重，合成最终的概率指派函数，并给出具体的说明性实例.

1 预备知识

证据推理就是利用证据理论得到不确定推理.D-S合成公式可以综合不同专家的知识，从而在专家系统中得到普遍应用.下面介绍关于D-S证据理论的一些基本概念.

2 基于集合覆盖模型的冲突证据合成(CCEM)

首先给出冲突评价的定义.

定义3设mi和mj为定义在集合θ下的两个相互独立的基本概率指派函数.若存在集合A⊆θ,使得|mi(A)-mj(A)|>α，则称mi和mj为在α水平下的冲突评价，α为评价容忍度，α∈(0，2].

命题1{Mi|i=1,2，…，n}构成M的一个覆盖.

命题2Mi为非冲突的专家指派系统.

证明由于在专家i协调空间中，任意两个指派函数mj,mk∈Mi，都有|mi(A)-mj(A)|≤(α/2)和|mi(A)-mk(A)|≤(α/2)成立，则|mj(A)-mk(A)|=|mj(A)-mi(A)+mi(A)-mk(A)|≤|mi(A)-mj(A)|+|mi(A)-mk(A)|≤α,所以Mi为非冲突的专家指派系统.

由命题2可知，Mi中的基本概率指派函数都不冲突，因此可以对Mi中的基本概率指派函数运用定义2中的D-S合成公式进行合成.

定义5记mi为对专家i协调空间中的mass函数进行D-S合成后所得到的概率指派函数,集合Mi的基数|Mi|称为专家指派系统对指派函数mi的支撑[18],称βi=(|Mi|)/(|M|)为专家指派系统对指派函数mi的支持率.

可以看到，合成的专家协调空间复合函数m*并不一定满足mass函数的条件，下面将对m*进行修正，使得所有事件的指派和为1.

命题3m*是集合θ下的mass函数.

下面给出CCEM的算法.

输入: 关于集合θ的专家指派系统M，评价容忍度α.

输出: 合成的概率指派函数m*.

表1 专家指派表Tab.1 Expert Assignment Table

步骤1 生成专家协调空间M1，M2，…，Mn.

步骤2 对专家i协调空间中的mass函数进行D-S合成，得到其概率指派函数mi.

步骤3 计算专家指派系统中对指派函数mi的支持率βi.

步骤4 求得专家协调空间复合函数m*.

步骤5 计算最终合成的概率指派函数m*.

为了更好地理解本算法，下面给出一个具体的说明性实例.

例集合θ={a,b}，M={m1,m2,…,m5}是由5名专家构成的专家指派系统，它们之间的关系如表1所示.

当α=0.8时，可知m1与m2为两个冲突的证据.于是，可采用文章中定义的CCEM方法.首先，求出专家i协调空间.M1={m1,m3};M2={m2,m4};M3={m1,m3};M4={m2,m4,m5};M5={m4,m5}.

对上面5个信息系统运用D-S合成公式求得mi及其支持率βi为:

m1({a})=7/8,m1({b})=1/8,m1({θ})=0，β1=2/5；

m2({a})=17/97,m2({b})=75/194,m2({θ})=85/194，β2=2/5；

m3({a})=7/8,m3({b})=1/8,m3({θ})=0，β3=2/5；

m4({a})=17/81,m4({b})=205/324,m4({θ})=51/324，β4=3/5；

m5({a})=10/41,m5({b})=49/84,m5({θ})=15/84，β5=2/5.

专家协调空间复合函数m*为

m*({a})=2 133 814/2 147 580,m*({b})=1 875 467/2 147 580,m*({θ})=736 347/2 147 580.

合成的概率指派函数m*为

m*({a})=2 133 814/4 745 628，m*({b})=1 875 467/4 745 628，m*({θ})=736 347/4 745 628.

3 同经典D-S合成的比较

由上面的对比可知，直接运用D-S合成公式对专家指派系统进行概率合成，同CCEM中α=2时的结果相一致.

命题4CCEM是对Dempster定义的组合规则的一种扩展.

证明设M={m1,m2,…,mn}，为n个专家给出的关于集合θ的专家指派系统，直接运用D-S合成公式后的专家指派函数为m.在CCEM方法中，取α=2，则M1=M2=…=Mn=M，β1=β2=…=βn=1，m1=m2=…=mn=m，专家协调空间复合函数m*=nm.由此可得到合成的概率指派函数m*=nm/n=m.

4 对参数取值的说明

第三部分中限定评价容忍度α的取值范围为(0,2]，而0≤mi(A)≤1,0≤mj(A)≤1.故|mi(A)-mj(A)|≤1，即当α∈(1,2]时，可以认为整个信息系统是不冲突的.但是在CCEM的方法中，评价容忍度α还关系到专家协调空间的选取，当α取(1,2]中不同数值时，可能会造成专家i协调空间不同，进而导致最后合成的概率指派函数m*的不同.其实，这一点同我们自然语言的表述是一致的.当α∈(0,1]时，认为原来的专家指派空间中，专家意见相差较大，冲突比较激烈.当α∈(1,2]时，认为专家之间的意见大体是一致的，有一些小的分歧.而第三部分已经证明CCEM的方法是经典D-S合成的扩展，那么它不仅可以用于对带有冲突证据的专家指派系统进行证据合成，还可以用于对不带冲突的专家指派系统进行证据合成.所以不管专家意见本身冲突的大小，都可以应用CCEM的方法.并且即使专家意见大体一致，仅有小分歧，根据研究者对这些小分歧的容忍程度，最终合成的概率指派函数m*也应是不同的.

综上所述，当研究者认为专家意见相差较大时，取α∈(0,1]；当研究者认为专家意见大体一致时，取α∈(1,2].

5 算法分析

对证据理论的研究中，研究者们在经典D-S合成的基础上给出了很多处理冲突证据的方法，其中应用比较广泛的方法是Yager[7]合成、Murphy[8]合成以及孙全[17]定义的合成方法.本节运用这几种算法对文中例子进行合成对比得出CCEM方法的特点.Murphy合成是将n个专家对同一事件指派的平均值作为该事件的基本概率指派值，之后运用经典的D-S合成公式对新求得的指派函数迭代n-1次,合成最终的基本概率指派函数.但Murphy合成的结果只是对数据源进行了简单的平均，没有考虑到数据的可靠性问题.Yager合成是将所有的冲突证据全部赋给未知项，这样做虽然可以处理高冲突证据，但是可能会造成对冲突证据分配的不公.为此，文献[20]引入名为可信度的变量，重新对冲突证据进行分配.

表2 融合结果Tab.2 Combination results

下面将利用本文的例子对以上3种方法和本文方法的合成结果作对比，如表2所示.在基于集合覆盖模型的冲突证据合成(CCEM)的方法中，取α=0.8时的结果同运用其他方法得到的合成结果区别比较明显.并且在本文例子中，m1、m3给出事件{a}的指派值大于事件{b}，m2、m4、m5给出事件{a}的指派值小于事件{b}.对于事件θ，除m2给出的指派值较高，其他专家给出的指派值均较低.这与CCEM方法得到的对事件{a}、{b}的指派值相对平均且明显高于事件θ的情况较吻合.

值得注意的是，CCEM的方法可以通过控制评价容忍度α来改变专家协调空间.相较于其他的融合方法，CCEM的方法灵活性更高.在融合过程中，CCEM的方法更加注重数据之间的联系，使得信息表中的信息被利用的更加充分.

6 结束语

冲突证据的合成一直受到学界的重视.本文在已有的研究基础上，提出了一种基于集合覆盖模型的冲突证据合成(CCEM)方法.讨论了该方法同经典D-S合成方法的关系.CCEM的方法不仅可以用于对带有冲突证据的专家指派系统进行证据合成，还可以用于对不带冲突的专家指派系统进行证据合成.文章还给出了CCEM算法同其他算法的比较.由于mass函数同信任函数与似然函数关系紧密，如何在带有冲突证据的专家指派系统中求得信任函数与似然函数,将成为我们未来研究的课题.