張齊 劉群

(華南理工大學(xué)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究所,廣東廣州 510640)

Dempster-Shafer(D-S)證據(jù)理論是一種不確定推理方法,其為不確定性的表達(dá)與合成提供了一種很好的方法.它滿足比概率論弱的公理,并能區(qū)分不確定與不知道的差異,當(dāng)先驗(yàn)概率已知時(shí),證據(jù)理論就變成概率論,當(dāng)先驗(yàn)概率很難獲取時(shí),證據(jù)理論比概率論合適.它提供了D-S組合規(guī)則[1]代替Bayes公式進(jìn)行證據(jù)組合.

但是證據(jù)理論中表示不確定性的概率分配函數(shù)沒(méi)有統(tǒng)一的構(gòu)成方法,而且作為其理論基石之一的Dempster組合規(guī)則存在不足之處,在合成高度沖突的證據(jù)時(shí),往往會(huì)得到錯(cuò)誤的結(jié)論.國(guó)內(nèi)外對(duì)此進(jìn)行了廣泛的研究,并提出了許多改進(jìn)算法[2-13].研究沖突證據(jù)組合算法的目的是化解證據(jù)之間的沖突,將沖突證據(jù)進(jìn)行重新分配,以獲得合理的組合結(jié)果.

本研究比較了國(guó)內(nèi)外學(xué)者對(duì)證據(jù)組合規(guī)則和融合模型的改進(jìn)方法.并在此基礎(chǔ)上提出了一種新的處理沖突證據(jù)的融合方法.該方法通過(guò)計(jì)算各證據(jù)到命題平均支持度的偏差,來(lái)檢測(cè)和消除沖突證據(jù),然后對(duì)最后結(jié)果進(jìn)行了修正,以處理來(lái)自不同識(shí)別框架的證據(jù)的合成.

1 D-S證據(jù)理論及其缺陷

1.1 D-S證據(jù)理論基礎(chǔ)

給定識(shí)別框架Θ,領(lǐng)域內(nèi)命題 Q的基本概率分配(BPA)用函數(shù)m:2Θ→[0,1]表示,稱為mass函數(shù),它滿足

式中:為空集.命題的信任函數(shù)Bel定義為

命題Q的似然函數(shù)(Pl)定義為

由信任函數(shù)和似然函數(shù)的定義可知:Bel(Q)表示對(duì)Q為真的信任程度,Pl(Q)表示對(duì)Q為非假的信任程度,Pl(Q)-Bel(Q)表示對(duì)Q不確定的程度.因此,區(qū)間(Bel(Q),Pl(Q))很好地描述了Q的可信程度.

對(duì)同一命題Q,從不同來(lái)源可以得到多個(gè)BPA函數(shù),需要對(duì)它們進(jìn)行組合,組合的方法是正交和運(yùn)算,定義如下:

設(shè)m1,m2,…,mn是n個(gè)mass函數(shù),框架內(nèi)命題總數(shù)為r,則其正交和m=m1⊕m2⊕…⊕mn為

K的大小反映了不同證據(jù)的沖突程度,K越大,證據(jù)沖突程度就越大,反之越小.1-K稱為歸一化因子,它的存在避免了將非零的概率賦給空集的可能.D-S組合規(guī)則符合結(jié)合律,合成結(jié)果不依賴于組合的順序.

1.2 證據(jù)理論的缺陷

設(shè)識(shí)別框架Θ={A,B,C}的BPA函數(shù)如下:

(1)對(duì)于證據(jù)m1,m1(A)=0.99,m1(B)= 0.01,m1(C)=0.00.

(2)對(duì)于證據(jù)m2,m2(A)=0.00,m2(B)= 0.01,m2(C)=0.99.

此例中,盡管兩證據(jù)對(duì) B的支持程度很低,但最終融合結(jié)果認(rèn)為B為真,與常理相悖.

同時(shí),mass函數(shù)的微小變化會(huì)使組合結(jié)果產(chǎn)生急劇變化.如對(duì)上述m1函數(shù)略加修改,使m1(A)= 0.98,m1(B)=0.01,m1(C)=0.01,m2不變,則會(huì)得到m(B)=m1⊕m2(B)=0.01,組合結(jié)果幾乎與之前相反.這反映了D-S合成規(guī)則在此情況下的不穩(wěn)定性和對(duì)mass函數(shù)的敏感性.歸根結(jié)底,導(dǎo)致上述缺陷的核心問(wèn)題就是錯(cuò)誤分配了沖突信息.

2 對(duì)D-S組合規(guī)則的改進(jìn)

Yager[2]提出的改進(jìn)方法是把沖突證據(jù)分配給識(shí)別框架下的完備命題集合,即把沖突證據(jù)的基本概率數(shù)歸到不確定性集合,他認(rèn)為沖突證據(jù)不能提供任何有用的信息.孫全等[3]認(rèn)為沖突證據(jù)是部分可用的,應(yīng)該將總沖突按一定比例分配給所有證據(jù)的焦元集合.文獻(xiàn)[4]引入自沖突概念來(lái)刻畫(huà)概率分配函數(shù)的自相矛盾程度,提出了一種權(quán)重分配策略.類似的改進(jìn)規(guī)則還可參見(jiàn)文獻(xiàn)[5-6].

從以上這些改進(jìn)證據(jù)組合規(guī)則的方法可知,改進(jìn)主要是集中于沖突項(xiàng)如何分配.通過(guò)引入沖突證據(jù)的加權(quán)因子ω(Q,m),m={m1,m2,…,mn}來(lái)確定證據(jù)組合后命題Q的mass函數(shù):

這就是處理沖突證據(jù)的改進(jìn)組合公式的一般形式.然而這種方法存在的主要問(wèn)題是:①當(dāng)識(shí)別框架中命題的數(shù)目很大時(shí),需要計(jì)算每個(gè)組合算子沖突證據(jù)的加權(quán)因子,且加權(quán)因子的計(jì)算量很大;②這種方法不滿足組合運(yùn)算的結(jié)合律,將使組合結(jié)果依賴于證據(jù)組合順序,這是該方法的最大缺點(diǎn).文獻(xiàn)[7]提出了一種計(jì)算證據(jù)可靠性的新方法,但它的組合公式是基于給不同的證據(jù)賦予權(quán)重,仍然屬于式(5)的范疇,存在的問(wèn)題沒(méi)有得到解決.

3 對(duì)融合模型的改進(jìn)

對(duì)融合模型進(jìn)行改進(jìn)的方法認(rèn)為:D-S組合規(guī)則本身沒(méi)有失效,當(dāng)證據(jù)高度沖突時(shí),應(yīng)該首先對(duì)沖突證據(jù)進(jìn)行預(yù)處理,然后再使用D-S組合規(guī)則.

文獻(xiàn)[8]已證明,在解決組合沖突證據(jù)過(guò)程中引起的失效問(wèn)題時(shí),修改融合模型比修改組合公式更為有效.

實(shí)際上各個(gè)證據(jù)源存在著不同程度的不可靠性,常稱為折扣系數(shù),并將之作為權(quán)值修正證據(jù)的質(zhì)量函數(shù).文獻(xiàn)[9]提出用未知擾動(dòng)來(lái)表示折扣系數(shù),通過(guò)最小化元知識(shí)來(lái)確定每條證據(jù)的未知擾動(dòng)值,然后將折扣證據(jù)進(jìn)行組合.該方法存在的問(wèn)題是需要事先確定元知識(shí)和量化的證據(jù)優(yōu)先級(jí),這在證據(jù)很多時(shí)很難實(shí)現(xiàn).文獻(xiàn)[11]和[12]在文獻(xiàn)[10]的基礎(chǔ)上引入證據(jù)間距離的概念來(lái)表示折扣系數(shù).然而這種方法計(jì)算量大,當(dāng)目標(biāo)框架復(fù)雜,證據(jù)多時(shí)尤為明顯,而且收斂速度較慢.文獻(xiàn)[13]對(duì)求證據(jù)距離的公式進(jìn)行了改進(jìn),雖然降低了一些計(jì)算復(fù)雜性,但收斂速度進(jìn)一步變慢.

4 新的沖突證據(jù)融合方法

本研究對(duì)沖突證據(jù)融合方法做了進(jìn)一步改進(jìn),即通過(guò)計(jì)算各證據(jù)到命題平均支持度的偏差來(lái)檢測(cè)和消除沖突證據(jù),并對(duì)最后結(jié)果進(jìn)行了修正.算法流程具體步驟如下:

1)證據(jù)的沖突檢測(cè).

若證據(jù)只有2條,直接跳到步驟4).

先計(jì)算出證據(jù)對(duì)各命題總的支持程度:

式中:n為證據(jù)總數(shù).找出使Sj最大的命題,構(gòu)成命題集L={Lk,k=1,2,…,u}(若只有一個(gè)命題Sj最大,則L只有一個(gè)元素,若有多個(gè)命題 Sj同為最大,則L有多個(gè)元素,記為u).L中的元素稱為關(guān)鍵命題,因?yàn)樽R(shí)別目標(biāo)存在于L中.再計(jì)算證據(jù)對(duì)L中各命題的平均支持度:

各證據(jù)與Ek的偏差為

依次檢測(cè)Dik是否符合沖突條件,若存在1≤i≤n,1≤k′≤u,使Dik′符合沖突條件,則證據(jù)mi為沖突證據(jù),不必再向后檢測(cè),若某證據(jù)通過(guò) L中所有命題的沖突檢測(cè),則其為非沖突證據(jù).檢測(cè)方法如下:

閾值α的選取與BPA函數(shù)的數(shù)據(jù)準(zhǔn)確度有關(guān),準(zhǔn)確度越高,支持同一事件的焦元就越集中,α越大.把Dik≤0的證據(jù)稱為有利證據(jù),Dik＞0的證據(jù)稱為不利證據(jù),α可以取值為有利證據(jù)的條數(shù).

對(duì)證據(jù)重新排序,得到M={mi,i=1,2,…,v, v+1,…,n},其中從第v+1條證據(jù)開(kāi)始,就是沖突證據(jù)了,即M′={mi,i=v+1,v+2,…,n}是沖突證據(jù)集.

2)對(duì)沖突證據(jù)進(jìn)行合成.

文獻(xiàn)[14]把沖突證據(jù)直接做平均加成,這是不妥當(dāng)?shù)?更合適的做法是設(shè)置權(quán)值.因?yàn)楦鳑_突證據(jù)的可利用價(jià)值不一樣,證據(jù)沖突越大,可利用價(jià)值越小.權(quán)值的計(jì)算方法如下:

對(duì)于沖突證據(jù)集M′={mi,i=v+1,v+2,…, n}中的每一個(gè)mi,其權(quán)重為

把沖突證據(jù)合成,得到

這樣證據(jù)由n條變?yōu)関+1條,即{mi,i=1,2,…,v+1}.

3)再次進(jìn)行沖突檢測(cè).

返回步驟1),再次進(jìn)行證據(jù)的沖突檢測(cè).

若存在1條以上的沖突證據(jù),返回步驟2);

若只存在 1條沖突證據(jù),把這條證據(jù)和正常證據(jù)中Dik′最大的證據(jù)進(jìn)行步驟 2)中的加權(quán)合成,若其為0,則直接平均合成.返回步驟1);

若不存在沖突證據(jù),進(jìn)入步驟4).

4)結(jié)果修正.

經(jīng)過(guò)前 3步的工作,沖突證據(jù)得到了消除,得到的證據(jù)集為M″={mi,i=1,2,…,v′}.

雖然M″中已不含沖突證據(jù),但若在 M″中?i,j, i=1,2,…,v′,j=1,2,…,r,使mi(Hj)=0且mi(Θ)= 0,利用D-S合成規(guī)則,不管其他證據(jù)對(duì) Hj的支持度如何,最后證據(jù)合成的結(jié)果都是m(Hj)=0.文獻(xiàn)[12]認(rèn)為,這是由于證據(jù) mi其實(shí)是來(lái)自少了命題Hj的另一識(shí)別框架的證據(jù),而D-S規(guī)則組合不同識(shí)別框架上的證據(jù)時(shí)只給各證據(jù)共同的命題進(jìn)行信度分配,所以無(wú)論對(duì)Hj的BPA函數(shù)為何值,只要有一條證據(jù)為0就會(huì)導(dǎo)致最終合成結(jié)果m(Hj)=0.這也是1.2的例子中m(A)和m(C)為0的原因.

以上分析說(shuō)明,若一個(gè)證據(jù)對(duì)某命題的支持度為0(概率分配數(shù)為 0),則可看成該證據(jù)的識(shí)別框架沒(méi)有這個(gè)命題,從而把原證據(jù)集的證據(jù)分在不同的框架下.而不同框架下的證據(jù),即使按照前文所述的方法檢測(cè)確認(rèn)不存在沖突,也不能直接按 D-S規(guī)則進(jìn)行合成,應(yīng)該先對(duì)證據(jù)進(jìn)行修正.方法如下:

把M″分成不同框架F={F1,F2,…,Fx}(Fi代表i框架下的證據(jù)條數(shù),共x個(gè)框架,i=1,2,…,x).先在各框架內(nèi)部用D-S規(guī)則進(jìn)行合成,得到x個(gè)結(jié)果mi,i=1,2,…,x.然后找出F中的最大值Fmax,把為新證據(jù)m′的權(quán)重,對(duì) m′進(jìn)行修正,得ii到對(duì)應(yīng)的m″i,修正公式如下:

最后應(yīng)用D-S組合規(guī)則,得到最終結(jié)果.

5 數(shù)據(jù)實(shí)驗(yàn)結(jié)果與分析

假設(shè)識(shí)別系統(tǒng)中有 7個(gè)傳感器,候選目標(biāo)為{A,B,C},在某時(shí)刻獲得的關(guān)于候選目標(biāo)的BPA如表1所示.

表1 7個(gè)傳感器獲得的關(guān)于3個(gè)候選目標(biāo)的BPATable 1 BPAs of three targets obtained by 7 sensors

從表 1中可以直觀看出,傳感器 2和 4與其他傳感器獲得的證據(jù)存在明顯沖突.表 2示出了分別使用傳統(tǒng)D-S組合規(guī)則、文獻(xiàn)[12]的方法和文獻(xiàn)[14]的方法及文中提出的方法進(jìn)行證據(jù)合成的結(jié)果.

表2 不同方法的融合結(jié)果Table 2 Fusion resu lts of differentmethods

先關(guān)注前4次合成.一方面,由于受到?jīng)_突證據(jù)的影響,傳統(tǒng)D-S組合規(guī)則多數(shù)情況下得不到正確的結(jié)果,而其他 3種方法能得到正確結(jié)果.另一方面,文中方法的收斂性最好,也即隨著支持 A的證據(jù)越來(lái)越多,能使融合結(jié)果更快地向A聚焦.從計(jì)算復(fù)雜性來(lái)說(shuō),文獻(xiàn)[12]的方法是最大的,它需要計(jì)算兩兩證據(jù)間的距離,n個(gè)證據(jù)要計(jì)算次,而文獻(xiàn)[14]的方法只需要進(jìn)行平均值運(yùn)算,計(jì)算量最小,本方法加入了基于偏差的權(quán)值運(yùn)算,由于計(jì)算方法簡(jiǎn)單,沒(méi)有帶來(lái)高的復(fù)雜性,卻能使合成結(jié)果更具收斂性和可靠性.

對(duì)于最后一次合成,因?yàn)閙7(B)=0.00,據(jù)前文所述,可以把證據(jù)m7看做來(lái)自識(shí)別框架{A,C}的證據(jù),文獻(xiàn)[14]把它和其他證據(jù)直接進(jìn)行 D-S合成,導(dǎo)致命題 B的概率分配數(shù)為 0,這是不夠準(zhǔn)確的.文中提出的方法通過(guò)修正,使命題 B分配到應(yīng)有的概率,結(jié)果不但更加精確,還比文獻(xiàn)[12]更趨近于識(shí)別目標(biāo).

6 結(jié)語(yǔ)

本研究提出的利用偏差處理沖突證據(jù)的改進(jìn)算法有效地解決了傳統(tǒng)D-S證據(jù)合成規(guī)則組合沖突證據(jù)時(shí)的缺陷,同時(shí)也保證了非沖突證據(jù)的有效合成.與其他改進(jìn)方法相比,本方法在收斂性、可靠性和計(jì)算復(fù)雜性方面具有優(yōu)勢(shì).

[1] Dempster A P.A generalization of Bayesian inference [J].Journal of the Royal Statistiacal Society,Series B, 1968,30(3):205-247.

[2] Yager R R.On the Dempster-Shafer framework and new combination ru les[J].Information Science,1989,41 (2):93-137.

[3] 孫全,葉秀清,顧偉康.一種新的基于證據(jù)理論的合成公式[J].電子學(xué)報(bào),2000,28(8):117-119.

Sun Quan,Ye Xiu-qing,Gu Wei-kang.A new combination rules of evidence theory[J].Acta Electronica Sinica, 2000,28(8):117-119.

[4] 吳根秀.沖突證據(jù)組合方法 [J].計(jì)算機(jī)工程,2005,31 (9):151-154.

Wu Gen-xiu.An approach for combining conflict evidences[J].Computer Engineering,2005,31(9):151-154.

[5] 向陽(yáng),史習(xí)智.證據(jù)理論合成規(guī)則的一點(diǎn)修正 [J].上海交通大學(xué)學(xué)報(bào),1999(3):357-360.

Xiang Yang,Shi Xi-zhi.Modification on combination rules of evidence theory[J].Journal of Shanghai Jiaotong University,1999(3):357-360.

[6] 李弼程,王波,魏俊.一種有效的證據(jù)理論合成公式[J].數(shù)據(jù)采集與處理,2002,17(1):33-36.

Li Bi-cheng,Wang Bo,Wei Jun.An efficient combination rule ofevidence theory[J].Journalof Data Acquisition＆Processing,2002,17(1):33-36.

[7] MihaiCristian Florea,Anne-Laure Jousselme,éloi Bossé, et al.Robust combination ru les for evidence theory[J]. In formation Fusion,2009,10(2):183-197.

[8] 張玉琢,余英.D-S證據(jù)理論中沖突證據(jù)組合分析[J].云南師范大學(xué)學(xué)報(bào):自然科學(xué)版,2007,27(4): 29-32.

Zhang Yu-zhuo,Yu Ying.Analysis of conflict evidence combination about D-S evidential theory[J].Journal of Yunnan Normal University:Natural Sciences Edition, 2007,27(4):29-32.

[9] 林作銓,牟克典,韓慶.基于未知擾動(dòng)的沖突證據(jù)合成方法[J].軟件學(xué)報(bào),2004(8):1150-1156.

Lin Zuo-quan,Mu Ke-dian,Han Qing.An approach to combination of conflicting evidences by disturbance of ignorance[J].Journal of Software,2004(8):1150-1156.

[10] Murphy C K.Combining belief function when evidence conflicts[J].Decision Support Systems,2000,29(1): 1-9.

[11] 鄧勇,施文康,朱振福.一種有效處理沖突證據(jù)的組合方法[J].紅外與毫米波學(xué)報(bào),2004,23(1):27-32.

Deng Yong,Shi Wen-kang,Zhu Zhen-fu.Efficient combination approach of conflict evidence[J].Journal Infrared Millimeter and Waves,2004,23(1):27-32.

[12] 劉海燕,趙宗貴,劉熹.D-S證據(jù)理論中沖突證據(jù)的合成方法[J].電子科技大學(xué)學(xué)報(bào),2008,37(5):701-704.

Liu Hai-yan,Zhao Zong-gui,Liu Xi.Combination of conflict evidences in D-S theory[J].Journal of University of Electronic Science and Technology of China,2008,37 (5):701-704.

[13] 張軍,涂國(guó)平.加權(quán)平均法解決證據(jù)理論中的失效問(wèn)題[J].微計(jì)算機(jī)信息,2007,23(33):202-203.

Zhang Jun,Tu Guo-ping.Weighted averaging approach to conflictevidence in D-Sevidence theory[J].Microcomputer In formation,2007,23(33):202-203.

[14] 關(guān)欣,衣曉,孫曉明,等.有效處理沖突證據(jù)的融合方法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2009,49(1): 138-141.

Guan Xin,Yi Xiao,Sun Xiao-ming,et al.Efficient fusion app roach for conflicting evidence[J].Journal of Tsinghua University:Science and Technology,2009,49(1): 138-141.