基于集合覆蓋模型的沖突證據(jù)合成

米據(jù)生，胡志勇，李磊軍，梁美社

(1.河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河北 石家莊 050024；2.石家莊職業(yè)技術(shù)學(xué)院 河北 石家莊 050081)

0 引言

不確定性推理[1]處理的是不清晰、不確定、不完全的信息.在描述及精確融合不確定信息時(shí)，D-S證據(jù)理論[2-3]體現(xiàn)出極高的靈活性和高效性.在不確定性推理、多源信息融合和決策分析等領(lǐng)域，D-S證據(jù)理論也具有極大影響.Dempster定義的組合規(guī)則[4]在對(duì)證據(jù)進(jìn)行融合和更新方面是非常有效的,它應(yīng)用的前提條件是融合規(guī)則的各部分是清晰可靠的.然而在很多的實(shí)際應(yīng)用中，這個(gè)條件往往過(guò)于苛刻.如果直接將Dempeter定義的組合規(guī)則用來(lái)處理不可靠的信息，特別是具有沖突的信息,最終得到的結(jié)果可能會(huì)與我們的直覺(jué)相悖[5].因此，沖突證據(jù)的合成受到學(xué)者們的重視，大量的研究工作[6-10]也在這一背景下開(kāi)展.集合覆蓋問(wèn)題作為一個(gè)經(jīng)典的最優(yōu)化問(wèn)題，在很多領(lǐng)域也都有著廣泛的應(yīng)用[11-12]，如人員調(diào)動(dòng)、網(wǎng)絡(luò)安全、資源分配等領(lǐng)域.文獻(xiàn)[13]為解決實(shí)際生活中的問(wèn)題，將集合覆蓋問(wèn)題同粗糙集理論[14-15]相結(jié)合提出了覆蓋粗糙集模型，使得集合覆蓋問(wèn)題同信息系統(tǒng)的聯(lián)系更加緊密.近年來(lái)利用集合覆蓋的思想處理信息系統(tǒng)中的問(wèn)題受到研究者的廣泛關(guān)注[16-17].

本文提出了一種名為基于集合覆蓋模型的沖突證據(jù)合成(CCEM)的方法，該方法運(yùn)用了集合覆蓋的思想及文獻(xiàn)[18]中提出的概念支撐的思想.將帶有沖突證據(jù)的信息系統(tǒng)用非沖突的信息系統(tǒng)來(lái)覆蓋，之后利用概念支撐的思想定義每個(gè)子系統(tǒng)的權(quán)重，合成最終的概率指派函數(shù)，并給出具體的說(shuō)明性實(shí)例.

1 預(yù)備知識(shí)

證據(jù)推理就是利用證據(jù)理論得到不確定推理.D-S合成公式可以綜合不同專家的知識(shí)，從而在專家系統(tǒng)中得到普遍應(yīng)用.下面介紹關(guān)于D-S證據(jù)理論的一些基本概念.

2 基于集合覆蓋模型的沖突證據(jù)合成(CCEM)

首先給出沖突評(píng)價(jià)的定義.

定義3設(shè)mi和mj為定義在集合θ下的兩個(gè)相互獨(dú)立的基本概率指派函數(shù).若存在集合A?θ,使得|mi(A)-mj(A)|>α，則稱mi和mj為在α水平下的沖突評(píng)價(jià)，α為評(píng)價(jià)容忍度，α∈(0，2].

命題1{Mi|i=1,2，…，n}構(gòu)成M的一個(gè)覆蓋.

命題2Mi為非沖突的專家指派系統(tǒng).

證明由于在專家i協(xié)調(diào)空間中，任意兩個(gè)指派函數(shù)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為非沖突的專家指派系統(tǒng).

由命題2可知，Mi中的基本概率指派函數(shù)都不沖突，因此可以對(duì)Mi中的基本概率指派函數(shù)運(yùn)用定義2中的D-S合成公式進(jìn)行合成.

定義5記mi為對(duì)專家i協(xié)調(diào)空間中的mass函數(shù)進(jìn)行D-S合成后所得到的概率指派函數(shù),集合Mi的基數(shù)|Mi|稱為專家指派系統(tǒng)對(duì)指派函數(shù)mi的支撐[18],稱βi=(|Mi|)/(|M|)為專家指派系統(tǒng)對(duì)指派函數(shù)mi的支持率.

可以看到，合成的專家協(xié)調(diào)空間復(fù)合函數(shù)m*并不一定滿足mass函數(shù)的條件，下面將對(duì)m*進(jìn)行修正，使得所有事件的指派和為1.

命題3m*是集合θ下的mass函數(shù).

下面給出CCEM的算法.

輸入: 關(guān)于集合θ的專家指派系統(tǒng)M，評(píng)價(jià)容忍度α.

輸出: 合成的概率指派函數(shù)m*.

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

步驟1 生成專家協(xié)調(diào)空間M1，M2，…，Mn.

步驟2 對(duì)專家i協(xié)調(diào)空間中的mass函數(shù)進(jìn)行D-S合成，得到其概率指派函數(shù)mi.

步驟3 計(jì)算專家指派系統(tǒng)中對(duì)指派函數(shù)mi的支持率βi.

步驟4 求得專家協(xié)調(diào)空間復(fù)合函數(shù)m*.

步驟5 計(jì)算最終合成的概率指派函數(shù)m*.

為了更好地理解本算法，下面給出一個(gè)具體的說(shuō)明性實(shí)例.

例集合θ={a,b}，M={m1,m2,…,m5}是由5名專家構(gòu)成的專家指派系統(tǒng)，它們之間的關(guān)系如表1所示.

當(dāng)α=0.8時(shí)，可知m1與m2為兩個(gè)沖突的證據(jù).于是，可采用文章中定義的CCEM方法.首先，求出專家i協(xié)調(diào)空間.M1={m1,m3};M2={m2,m4};M3={m1,m3};M4={m2,m4,m5};M5={m4,m5}.

對(duì)上面5個(gè)信息系統(tǒng)運(yùn)用D-S合成公式求得mi及其支持率βi為:

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

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

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

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

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

專家協(xié)調(diào)空間復(fù)合函數(shù)m*為

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

合成的概率指派函數(shù)m*為

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

3 同經(jīng)典D-S合成的比較

由上面的對(duì)比可知，直接運(yùn)用D-S合成公式對(duì)專家指派系統(tǒng)進(jìn)行概率合成，同CCEM中α=2時(shí)的結(jié)果相一致.

命題4CCEM是對(duì)Dempster定義的組合規(guī)則的一種擴(kuò)展.

證明設(shè)M={m1,m2,…,mn}，為n個(gè)專家給出的關(guān)于集合θ的專家指派系統(tǒng)，直接運(yùn)用D-S合成公式后的專家指派函數(shù)為m.在CCEM方法中，取α=2，則M1=M2=…=Mn=M，β1=β2=…=βn=1，m1=m2=…=mn=m，專家協(xié)調(diào)空間復(fù)合函數(shù)m*=nm.由此可得到合成的概率指派函數(shù)m*=nm/n=m.

4 對(duì)參數(shù)取值的說(shuō)明

第三部分中限定評(píng)價(jià)容忍度α的取值范圍為(0,2]，而0≤mi(A)≤1,0≤mj(A)≤1.故|mi(A)-mj(A)|≤1，即當(dāng)α∈(1,2]時(shí)，可以認(rèn)為整個(gè)信息系統(tǒng)是不沖突的.但是在CCEM的方法中，評(píng)價(jià)容忍度α還關(guān)系到專家協(xié)調(diào)空間的選取，當(dāng)α取(1,2]中不同數(shù)值時(shí)，可能會(huì)造成專家i協(xié)調(diào)空間不同，進(jìn)而導(dǎo)致最后合成的概率指派函數(shù)m*的不同.其實(shí)，這一點(diǎn)同我們自然語(yǔ)言的表述是一致的.當(dāng)α∈(0,1]時(shí)，認(rèn)為原來(lái)的專家指派空間中，專家意見(jiàn)相差較大，沖突比較激烈.當(dāng)α∈(1,2]時(shí)，認(rèn)為專家之間的意見(jiàn)大體是一致的，有一些小的分歧.而第三部分已經(jīng)證明CCEM的方法是經(jīng)典D-S合成的擴(kuò)展，那么它不僅可以用于對(duì)帶有沖突證據(jù)的專家指派系統(tǒng)進(jìn)行證據(jù)合成，還可以用于對(duì)不帶沖突的專家指派系統(tǒng)進(jìn)行證據(jù)合成.所以不管專家意見(jiàn)本身沖突的大小，都可以應(yīng)用CCEM的方法.并且即使專家意見(jiàn)大體一致，僅有小分歧，根據(jù)研究者對(duì)這些小分歧的容忍程度，最終合成的概率指派函數(shù)m*也應(yīng)是不同的.

綜上所述，當(dāng)研究者認(rèn)為專家意見(jiàn)相差較大時(shí)，取α∈(0,1]；當(dāng)研究者認(rèn)為專家意見(jiàn)大體一致時(shí)，取α∈(1,2].

5 算法分析

對(duì)證據(jù)理論的研究中，研究者們?cè)诮?jīng)典D-S合成的基礎(chǔ)上給出了很多處理沖突證據(jù)的方法，其中應(yīng)用比較廣泛的方法是Yager[7]合成、Murphy[8]合成以及孫全[17]定義的合成方法.本節(jié)運(yùn)用這幾種算法對(duì)文中例子進(jìn)行合成對(duì)比得出CCEM方法的特點(diǎn).Murphy合成是將n個(gè)專家對(duì)同一事件指派的平均值作為該事件的基本概率指派值，之后運(yùn)用經(jīng)典的D-S合成公式對(duì)新求得的指派函數(shù)迭代n-1次,合成最終的基本概率指派函數(shù).但Murphy合成的結(jié)果只是對(duì)數(shù)據(jù)源進(jìn)行了簡(jiǎn)單的平均，沒(méi)有考慮到數(shù)據(jù)的可靠性問(wèn)題.Yager合成是將所有的沖突證據(jù)全部賦給未知項(xiàng)，這樣做雖然可以處理高沖突證據(jù)，但是可能會(huì)造成對(duì)沖突證據(jù)分配的不公.為此，文獻(xiàn)[20]引入名為可信度的變量，重新對(duì)沖突證據(jù)進(jìn)行分配.

表2 融合結(jié)果Tab.2 Combination results

下面將利用本文的例子對(duì)以上3種方法和本文方法的合成結(jié)果作對(duì)比，如表2所示.在基于集合覆蓋模型的沖突證據(jù)合成(CCEM)的方法中，取α=0.8時(shí)的結(jié)果同運(yùn)用其他方法得到的合成結(jié)果區(qū)別比較明顯.并且在本文例子中，m1、m3給出事件{a}的指派值大于事件，m2、m4、m5給出事件{a}的指派值小于事件.對(duì)于事件θ，除m2給出的指派值較高，其他專家給出的指派值均較低.這與CCEM方法得到的對(duì)事件{a}、的指派值相對(duì)平均且明顯高于事件θ的情況較吻合.

值得注意的是，CCEM的方法可以通過(guò)控制評(píng)價(jià)容忍度α來(lái)改變專家協(xié)調(diào)空間.相較于其他的融合方法，CCEM的方法靈活性更高.在融合過(guò)程中，CCEM的方法更加注重?cái)?shù)據(jù)之間的聯(lián)系，使得信息表中的信息被利用的更加充分.

6 結(jié)束語(yǔ)

沖突證據(jù)的合成一直受到學(xué)界的重視.本文在已有的研究基礎(chǔ)上，提出了一種基于集合覆蓋模型的沖突證據(jù)合成(CCEM)方法.討論了該方法同經(jīng)典D-S合成方法的關(guān)系.CCEM的方法不僅可以用于對(duì)帶有沖突證據(jù)的專家指派系統(tǒng)進(jìn)行證據(jù)合成，還可以用于對(duì)不帶沖突的專家指派系統(tǒng)進(jìn)行證據(jù)合成.文章還給出了CCEM算法同其他算法的比較.由于mass函數(shù)同信任函數(shù)與似然函數(shù)關(guān)系緊密，如何在帶有沖突證據(jù)的專家指派系統(tǒng)中求得信任函數(shù)與似然函數(shù),將成為我們未來(lái)研究的課題.