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证据理论的一些基本概念.

定义1^[7]  设θ为一个非空有限集合，P(θ)为θ的幂集.集函数m:P(θ)→[0, 1]，若满足以下条件:(1) m(∅)=0；(2) $\sum\limits_{A \subseteq \theta } {m\left( A \right)} $=1, 则称m为一个mass函数.m(A)表示对事件A的支持程度.mass函数通常也被叫做基本概率指派函数.

定义2^[19]  设m₁和m₂为定义在集合θ下的两个相互独立的基本概率指派函数.称⊕为两个相互独立的基本概率指派函数的合成运算，那么m₁⊕m₂(A)= $\frac{1}{N}\sum\limits_{B \cap C = A} {{m_1}\left( B \right){m_2}\left( C \right)} $，其中$N = \sum\limits_{B \cap C \ne \emptyset } {{m_1}\left( B \right){m_2}\left( C \right)} $.为方便起见，把m₁⊕m₂(A)简记为m(A).值得注意的是，m(A)仍构成集合θ下的一个基本概率指派函数.对于n个指派函数的情况，利用迭代的思想，同样可以合成θ下的一个基本概率指派函数m₁⊕m₂⊕…⊕m_n(A)=$\frac{1}{N}\sum\limits_{\bigcap\limits_{i = 1}^n {{E_j} = A} } {\prod\limits_{i = 1}^n {{m_i}\left( {{E_j}} \right)} } $，其中：$N = \sum\limits_{\bigcap\limits_{i = 1}^n {{E_j} \ne \varphi } } {\prod\limits_{i = 1}^n {{m_i}\left( {{E_j}} \right) > 0} } $,E_j⊆θ.

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

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

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

定义4  θ为一个非空有限集，M={m₁, m₂, …, m_n}为n个专家给出的专家指派系统, m_i为第i个专家给出的关于集合θ的mass函数, 称M_i⊆M为专家i协调空间，若M_i满足以下条件:(1) m_i∈M_i；(2)对∀A⊆θ, ∀m_j∈M_i, 有|m_i(A)-m_j(A)|≤ $\frac{\alpha }{2}$.

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

证明  由定义4可知，n个专家构成的专家指派系统，有n个专家协调空间M₁，M₂，…，M_n与之对应，并且m_i∈M_i，而M={m₁, m₂, …, m_n}.自然有$\bigcup\limits_{i = 1}^n {{M_i}} \supseteq M$.因此，{M_i|i=1, 2，…，n}构成M的一个覆盖.

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

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

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

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

定义6  称函数m^*为专家协调空间复合函数，m^*(A)=$\sum\limits_{i = 1}^n {{\beta _i}{m^i}\left( A \right)} $.

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

定义7  函数m_*为定义在集合θ下的合成的概率指派函数，m_*(A)=m^*(A)/($\sum\limits_{B \subseteq \theta } {{m^ * }\left( B \right)} $)，A⊆ θ.

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

证明  (1)由于任意的概率指派函数m_i(∅)=0，所以对任意的i，mⁱ(∅)=0.而m^*(∅)=$\sum\limits_{i = 1}^n {{\beta _i}{m^i}\left( \emptyset \right)} $，可求得m^*(∅)=0.于是有m_*(∅)=0/($\sum\limits_{B \subseteq \theta } {{m^ * }\left( B \right)} $)，所以m_*(∅)=0.

(2) $\sum\limits_{A \subseteq \theta } {{m_ * }\left( A \right)} $=($\sum\limits_{A \subseteq \theta } {{m^ * }\left( A \right)} $)/($\sum\limits_{B \subseteq \theta } {{m^ * }\left( B \right)} $)=1.因此，m_*构成集合θ下的mass函数.

下面给出CCEM的算法.

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

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

步骤1  生成专家协调空间M₁，M₂，…，M_n.

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

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

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

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

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

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

当α=0.8时，可知m₁与m₂为两个冲突的证据.于是，可采用文章中定义的CCEM方法.首先，求出专家i协调空间.M₁={m₁, m₃}; M₂={m₂, m₄}; M₃={m₁, m₃}; M₄={m₂, m₄, m₅}; M₅={m₄, m₅}.

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

$ \begin{array}{*{20}{c}} {{m^1}\left( {\{ a\} } \right) = 7/8, {m^1}\left( {\{ b\} } \right) = 1/8, {m^1}\left( {\{ \theta \} } \right) = 0, {\beta _1} = 2/5;}\\ {{m^2}\left( {\{ a\} } \right) = 17/97, {m^2}\left( {\{ b\} } \right) = 75/194, {m^2}\left( {\{ \theta \} } \right) = 85/194, {\beta _2} = 2/5;}\\ {{m^3}\left( {\{ a\} } \right) = 7/8, {m^3}\left( {\{ b\} } \right) = 1/8, {m^3}\left( {\{ \theta \} } \right) = 0, {\beta _3} = 2/5;}\\ {{m^4}\left( {\{ a\} } \right) = 17/81, {m^4}\left( {\{ b\} } \right) = 205/324, {m^4}\left( {\{ \theta \} } \right) = 51/324, {\beta _4} = 3/5;}\\ {{m^5}\left( {\{ a\} } \right) = 10/41, {m^5}\left( {\{ b\} } \right) = 49/84, {m^5}\left( {\{ \theta \} } \right) = 15/84, {\beta _5} = 2/5.} \end{array} $

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

$ {m^*}\left( {\{ a\} } \right) = 2\ 133\ 814/2\ 147\ 580, {m^*}\left( {\{ b\} } \right) = 1\ 875\ 467/2\ 147\ 580, {m^*}\left( {\{ \theta \} } \right) =\\ 736\ 347/2\ 147\ 580. $

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

$ {m_*}\left( {\{ a\} } \right) = 2\ 133\ 814/4\ 745\ 628, {m_*}\left( {\{ b\} } \right) = 1\ 875\ 467/4\ 745\ 628, {m_*}\left( {\{ \theta \} } \right) =\\ 736\ 347/4\ 745\ 628. $

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

将CCEM的方法同经典D-S合成的方法进行对比.首先，对上节例中的专家指派系统直接进行D-S合成.由定义2，$N = \sum\limits_{\bigcap\limits_{j = 1}^5 {{E_j} \ne \varphi } } {\prod\limits_{i = 1}^5 {{m_i}\left( {{E_j}} \right)} } $=1 089/2 592.进而可以求得运用经典D-S合成公式后的专家指派函数m为m({a})=833/1 089，m({b})=256/1 089，m({θ})=0.在CCEM的方法中，取α=2，可求得M₁=M₂=M₃=M₄=M₅=M={m₁, m₂, …, m₅}，β₁=β₂=β₃=β₄=β₅=1.于是有m¹=m²=m³=m⁴=m⁵=m，m^*({a})=4 165/1 089，m^*({b})=1 280/1 089，m^*({θ})=0.并求得合成的概率指派函数m_*为m_*({a})=833/1 089，m_*({b})=256/1 089，m_*({θ})=0.

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

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

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

4 对参数取值的说明

第三部分中限定评价容忍度α的取值范围为(0, 2]，而0≤m_i(A)≤1, 0≤m_j(A)≤1.故m_i(A)-m_j(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]引入名为可信度的变量，重新对冲突证据进行分配.

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

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

6 结束语

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