陳 鵬， 何 凱，余肖生

(三峽大學(xué) 計(jì)算機(jī)與信息學(xué)院， 湖北 宜昌 443002)

火災(zāi)隱患的科學(xué)判定往往需要有效的方法，融合多個(gè)組織獲取的與火災(zāi)隱患有關(guān)的不確定信息。D-S證據(jù)理論[1-2]因其在不確定性問(wèn)題上表述、組合等方面的優(yōu)勢(shì)，被廣泛應(yīng)用于信息融合[3-5]、多屬性決策分析[6]、風(fēng)險(xiǎn)評(píng)估[7]等領(lǐng)域。而Dempster組合規(guī)則[8]在處理實(shí)際問(wèn)題時(shí)，往往面臨“焦元爆炸”的問(wèn)題。針對(duì)這些問(wèn)題,國(guó)內(nèi)外研究人員都給出了自己的解決方案：Smets[9]提出TBM框架，通過(guò)解決復(fù)合源的計(jì)算問(wèn)題來(lái)達(dá)到減少焦元的目的，但是實(shí)際效果不佳,沒(méi)有真正解決“焦元爆炸”問(wèn)題；Dubois等[10]提出近似一致性算法，近似計(jì)算后焦元是嵌套的，以此減少了計(jì)算的復(fù)雜度，但是由于嵌套的焦元只能用于描述，不能進(jìn)行后續(xù)的計(jì)算，因此該近似算法無(wú)法運(yùn)用于實(shí)際計(jì)算中；Voorbraak[11]提出了Bayesian近似方法,這是一種非主觀的近似方法，解決了復(fù)合焦元的融合問(wèn)題，且在計(jì)算較少焦元時(shí)融合結(jié)果比較準(zhǔn)確，但對(duì)“焦元爆炸”的問(wèn)題依然無(wú)法很好地解決；Tessem[12]提出的(K,L,X)近似方法和Lowrance[13]提出的Summarization近似算法[13]，本質(zhì)上都屬于主觀的近似算法，基本解決了“焦元爆炸”的問(wèn)題，但由于這兩種算法都需要通過(guò)人為主觀判斷閾值，都不具備普遍適用性；Denoeux[14-15]提出的粗糙近似算法，用先“粗化”然后“細(xì)化”的方式同樣解決了“焦元爆炸”的問(wèn)題，但是其做法只能用于粗糙處理，計(jì)算結(jié)果容易出現(xiàn)結(jié)論與實(shí)際不符的情況。

本文針對(duì)“焦元爆炸”的問(wèn)題，結(jié)合具體實(shí)際情況，提出一種無(wú)需人為判斷且具有普遍適用性的近似算法(ELNA)。其主要通過(guò)判斷主要焦元的累計(jì)mass值去確定證據(jù)的等級(jí)，根據(jù)證據(jù)的不同等級(jí)采取不同的初始標(biāo)準(zhǔn)來(lái)減少焦元的數(shù)量，以達(dá)到減少計(jì)算量的目的。最后，在融合的時(shí)候也會(huì)根據(jù)證據(jù)的等級(jí)給予不同的折扣，以此來(lái)增加融合結(jié)果的準(zhǔn)確性。

1 證據(jù)理論基礎(chǔ)及相關(guān)研究概述

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

D-S證據(jù)理論被認(rèn)為是表征和處理不確定事物的有效工具。最初由Shafer從數(shù)學(xué)的角度證明了其對(duì)不確定事物的建模能力，同時(shí)提出了該理論具體的量化模型。D-S證據(jù)理論基礎(chǔ)詳見(jiàn)文獻(xiàn)[1-2]。

假設(shè)定義一個(gè)集合H叫做識(shí)別框架，定義如下：

H= {H1,…,Hn,…,HN}

(1)

它由N個(gè)窮盡且排他的假設(shè)組成。從其結(jié)構(gòu)出發(fā)，可以得到由H組成的2N個(gè)命題，表示為：

2H={?,{H1},{H2},…{HN},

{H1∪H2},{H1∪H3},…,H}

(2)

其中2H叫做識(shí)別框架的冪集，它的每一個(gè)元素都表示一種假設(shè)，這些假設(shè)在證據(jù)理論被稱為焦點(diǎn)元素，簡(jiǎn)稱焦元。對(duì)假設(shè)的支持程度叫做基本置信指派，用m表示。在2H→[0,1]滿足：

m(?)=0

(3)

(4)

其中m(A)表示對(duì)證據(jù)支持假設(shè)A的強(qiáng)度，也被叫做假設(shè)A的mass值。從該基本置信指派推廣，分別定義置信函數(shù)Bel和似然函數(shù)Pl:

(5)

(6)

其中：Bel(A)表示對(duì)假設(shè)A為真的度量；Pl(A)表示假設(shè)A可能為真的度量。m(A)、Bel(A)、Pl(A)可被看做對(duì)于同一信息的3種估計(jì)：一般估計(jì)、悲觀估計(jì)、樂(lè)觀估計(jì)。通過(guò)置信函數(shù)Bel和似然函數(shù)Pl構(gòu)成的置信區(qū)間，能較為直觀地表示證據(jù)對(duì)焦元的支持程度。

在不完全(不確定、不精確和不完全)數(shù)據(jù)的情況下，融合是獲得更多相關(guān)信息的有效解決方案。Dempster組合規(guī)則是證據(jù)理論的第1個(gè)組合規(guī)則，也是現(xiàn)今使用最廣泛的組合規(guī)則之一。定義如下：假設(shè)m1和m2是識(shí)別框架H上的2個(gè)獨(dú)立證據(jù)，2H是它的冪集，A、B是冪集中的元素，則這2個(gè)證據(jù)組合后得到的組合證據(jù)為

(7)

其中K為歸一化常數(shù)，

(8)

為了防止不可靠證據(jù)對(duì)融合結(jié)果產(chǎn)生影響，往往需要對(duì)融合的證據(jù)進(jìn)行折扣：

mw(A)=wm(A)?A?H

(9)

mw(H)=1-w+wm(H)

(10)

其中：w為折扣系數(shù)；焦點(diǎn)H存放折扣后剩余的mass值。

1.2 相關(guān)研究簡(jiǎn)述

為了解決證據(jù)理論中“焦元爆炸”的問(wèn)題，國(guó)內(nèi)外學(xué)者從不同角度進(jìn)行了研究，提出了各種各樣的近似算法。在眾多近似算法中，最具代表性的是Bayesian近似算法、(K,L,X)近似算法和Summarization近似算法。

1) Bayesian近似算法。主要是將證據(jù)理論與概率思想相結(jié)合，將基本信度值(也叫mass值)轉(zhuǎn)化為Bayesian概率。一般情況下，該算法滿足：信度函數(shù)的Bayesian近似的合成等于其合成的Bayesian近似。利用這個(gè)特性可以使融合的計(jì)算量大大減少，而且這是一種非主觀的近似算法，具備了普遍適用性。由于其將復(fù)合焦元的mass值分配給單焦元，降低了證據(jù)理論表示不確定的特點(diǎn)，丟失了大量信息。相較其他近似算法而言，其對(duì)“焦元爆炸”的處理并不具有太大的優(yōu)勢(shì)。

2) (K,L,X)近似算法。主要思想是通過(guò)閾值的選取來(lái)減少焦元的數(shù)量。依靠主觀選取保留的焦元數(shù)量，去掉mass值較小的焦元，來(lái)減少焦元數(shù)量，從而實(shí)現(xiàn)減少計(jì)算量的目的。這種近似算法從應(yīng)用的角度來(lái)講，適合幾乎所有的情況，但是因其是一種通過(guò)主觀判斷來(lái)確定閾值的方法，不同的證據(jù)都需要重新選取閾值，不同的閾值可能導(dǎo)致完全不同的結(jié)果，穩(wěn)健性不夠且要求閾值選取人員必須具備相應(yīng)的知識(shí)。這些缺點(diǎn)導(dǎo)致其無(wú)法被廣泛應(yīng)用。

3) Summarization近似算法。主要通過(guò)將較小的焦元的mass值全部放在假定焦元A0中，且不改變較大焦元的mass值的方式進(jìn)行近似處理。相當(dāng)于去掉了mass值較小的焦元，在減少了焦元數(shù)量的同時(shí)，沒(méi)有改變mass值較大的焦元，這樣的處理不會(huì)對(duì)融合結(jié)果產(chǎn)生太大影響。但是，這個(gè)近似算法和(K,L,X)算法存在類似的問(wèn)題：需要主觀判斷保留焦元的數(shù)量，不同的源可能因?yàn)楸Ａ艚乖獢?shù)量的不同導(dǎo)致完全不同的結(jié)果。另外，當(dāng)焦元的mass值相等時(shí)，這種方法在處理時(shí)也存在一定問(wèn)題。

這幾種近似算法中，Bayesian算法不需要人為判斷參與，而其他兩種都需要人為主觀判斷參與。

2 基于證據(jù)等級(jí)的非主觀近似算法

為了克服上述近似方法的不足，筆者提出基于證據(jù)等級(jí)的非主觀近似算法。該方法首先根據(jù)一定規(guī)則將復(fù)合焦元轉(zhuǎn)化為單焦元，再依據(jù)主要焦點(diǎn)的累積mass值將證據(jù)劃分成不同的等級(jí)。為了保證結(jié)果的可靠性，會(huì)將近似算法舍棄的mass值按一定的比例疊加到保留的焦元上。最后，按照證據(jù)等級(jí)的不同給予不同的權(quán)重進(jìn)行融合，以確保確定性較差的證據(jù)不會(huì)對(duì)結(jié)果產(chǎn)生過(guò)大的影響。具體處理過(guò)程如下：

1) 復(fù)合焦元的處理規(guī)則

參照Pignistic概率的處理方式，根據(jù)組成復(fù)合焦元的元素，將復(fù)合焦元的質(zhì)量等比例的分配到組成其的所有單點(diǎn)焦元中去，從而使復(fù)合焦元轉(zhuǎn)化成單焦元。

?A?H

(11)

2) 證據(jù)等級(jí)評(píng)估方法(level of envidencde estimatima method)

為了能夠利用累積的mass值去劃分不同證據(jù)的確定性等級(jí)，將經(jīng)過(guò)第1步處理后的證據(jù)按照mass值從大到小排列，將前3個(gè)焦元與前5個(gè)焦元的和分別記做A和B，且滿足A,B∈[0,1]，根據(jù)累積mass值A(chǔ)、B的大小做如下劃分：

(12)

其中1、2、3、4分別代表證據(jù)的確定性等級(jí)，等級(jí)越小說(shuō)明證據(jù)的確定性越好。按照累積mass值A(chǔ)、B的大小將證據(jù)的確定性分為4個(gè)等級(jí)，記錄下每個(gè)證據(jù)的證據(jù)等級(jí)，將作為下一步近似處理及最后融合時(shí)確定權(quán)重比的依據(jù)。

3) 近似處理(approximate treament)

為了方便后續(xù)計(jì)算，所有的源都必須先進(jìn)行初步處理。

初步處理：保留mass值前5的焦元，舍棄其他的mass值，將舍棄的mass值按照5個(gè)焦元的比例分配到5個(gè)焦元中去。

近似處理：根據(jù)證據(jù)的不同等級(jí)給予不同的初始標(biāo)準(zhǔn)，超過(guò)初始標(biāo)準(zhǔn)的mass值保留，低于標(biāo)準(zhǔn)mass值的舍棄。

初始標(biāo)準(zhǔn)的設(shè)定按照證據(jù)等級(jí)來(lái)確定。確定的目的主要是為了進(jìn)一步減少焦元，確定主要因素。不同等級(jí)的標(biāo)準(zhǔn)由函數(shù)s確定：

(13)

標(biāo)準(zhǔn)的制定完全按照證據(jù)初始的確定性等級(jí)來(lái)確定，確定性越高的證據(jù)設(shè)定的標(biāo)準(zhǔn)也就越低，方便剔除mass值很小的焦元，確定性越低的證據(jù)設(shè)定的標(biāo)準(zhǔn)越高，以此來(lái)提高處理后證據(jù)的確定性，方便進(jìn)行下一步根據(jù)權(quán)重比融合不同的證據(jù)。

4) 基于折扣處理(discounting operation)的數(shù)據(jù)融合

近似處理的目的就是為了更好地進(jìn)行數(shù)據(jù)融合，而很多近似處理會(huì)丟失很多關(guān)鍵的信息。若直接進(jìn)行融合，最后的結(jié)果往往可信度不高，不能作為決策的標(biāo)準(zhǔn)。

本文采用根據(jù)證據(jù)初始數(shù)據(jù)確定證據(jù)等級(jí)的方式，用證據(jù)等級(jí)確定融合給予的權(quán)重比大小：證據(jù)等級(jí)越小的證據(jù)在融合時(shí)給予更多的權(quán)重比，證據(jù)等級(jí)越大的證據(jù)只需要保留其主要成分，在融合時(shí)候給予較小的權(quán)重比，最后融合出來(lái)的結(jié)果就不會(huì)與實(shí)際有太大的偏差。

合理的融合順序是得到正確融合結(jié)果的有效手段,本文采取基于證據(jù)等級(jí)的證據(jù)排序方式。

證據(jù)內(nèi)的排序方式:證據(jù)內(nèi)的焦元重要性排序按照少數(shù)服從多數(shù)的原則,將所有證據(jù)的同種焦元mass值相加取平均值,平均值越大說(shuō)明該焦元在證據(jù)內(nèi)占據(jù)比例越多,說(shuō)明越重要,越重要的焦元在寫(xiě)入表格的時(shí)候就寫(xiě)得越靠前。

證據(jù)間的排序方式:首先是對(duì)不同等級(jí)的證據(jù)按照等級(jí)越小越優(yōu)先的原則進(jìn)行排序,因?yàn)樽C據(jù)等級(jí)越小的證據(jù)確定性越高,將其優(yōu)先融合能提高其作主導(dǎo)證據(jù)的機(jī)會(huì),有利于提高融合結(jié)果的可靠性。其次，是對(duì)相同證據(jù)等級(jí)的證據(jù)進(jìn)行排序,主要采取越重要焦元mass值越小越優(yōu)先的原則進(jìn)行排序。這樣做可以有效避免錯(cuò)誤證據(jù)對(duì)融合結(jié)果的影響，即使融合的證據(jù)是錯(cuò)誤證據(jù)，優(yōu)先融合能使其對(duì)融合結(jié)果的影響降至最低。

經(jīng)過(guò)前面近似處理的證據(jù)按照證據(jù)之間的等級(jí)差取不同的權(quán)重比進(jìn)行分級(jí)融合。

融合的權(quán)重比(大∶小)=

0.5+0.1*等級(jí)差∶0.5-0.1*等級(jí)差

(14)

其中等級(jí)差為2個(gè)證據(jù)等級(jí)r(A,B)差值的絕對(duì)值。融合之后的證據(jù)等級(jí)等于用于融合兩個(gè)證據(jù)等級(jí)的平均值。兩個(gè)證據(jù)折扣后的剩余部分融合產(chǎn)生的mass值按主導(dǎo)證據(jù)(證據(jù)等級(jí)小)的比例分配，若存在多個(gè)主導(dǎo)證據(jù)就隨機(jī)選取其一。由主導(dǎo)證據(jù)的選取方式?jīng)Q定,融合權(quán)重的選取要求同證據(jù)等級(jí)非錯(cuò)誤證據(jù)在4個(gè)以上，因?yàn)檫@樣能保證至少有93.75%的可能得到正確的結(jié)果。非錯(cuò)誤證據(jù)的數(shù)量越多，融合錯(cuò)誤證據(jù)造成的影響就越小,結(jié)果的準(zhǔn)確性越高,這一點(diǎn)在證據(jù)等級(jí)較低的時(shí)候能得到明顯的體現(xiàn)。在證據(jù)等級(jí)較高的時(shí)候,即使錯(cuò)誤證據(jù)較多,也并不會(huì)對(duì)融合結(jié)果產(chǎn)生太大的影響。

折扣判斷以及證據(jù)等級(jí)的判斷過(guò)程如圖1所示。

圖1 折扣判斷以及證據(jù)等級(jí)的判斷過(guò)程

3 仿真結(jié)果及分析

3.1 一般情況仿真結(jié)果及分析

這里主要針對(duì)一般情況(包括嵌套焦元證據(jù)M1和M2、多焦元證據(jù)M4、區(qū)分度不大焦元證據(jù)M3)的融合,橫向比較ELNA與其他兩種方法以驗(yàn)證ELNA方法的一般性以及結(jié)果的可靠性。至于在針對(duì)失效證據(jù)(錯(cuò)誤證據(jù))的融合上,一方面其他方法融合失效證據(jù)會(huì)產(chǎn)生與實(shí)際情況不符的結(jié)果,錯(cuò)誤的融合結(jié)果不方便做橫向比較,無(wú)法驗(yàn)證 ELNA融合結(jié)果的可靠性；另一方面在實(shí)際中錯(cuò)誤的證據(jù)畢竟只占少數(shù)，若直接融合錯(cuò)誤證據(jù)難以反映實(shí)際情況,也無(wú)法說(shuō)明方法的一般性。因此,對(duì)特殊情況(錯(cuò)誤證據(jù))的仿真結(jié)果及分析會(huì)在下文單獨(dú)列出。

在這里假設(shè)某識(shí)別框架的概率分配函數(shù)及焦元如表1所示，分別使用本文的近似算法、非主觀Bayesian近似算法和主觀Summarization近似算法進(jìn)行處理，處理后的結(jié)果如表2、3、4所示，再將這3種方法的處理結(jié)果分別進(jìn)行融合，得到融合結(jié)果如表5所示。另外，若處理之后對(duì)應(yīng)焦元的mass值為0，將無(wú)法進(jìn)行證據(jù)理論合成，一般會(huì)對(duì)表中為0的部分進(jìn)行微調(diào)，即根據(jù)實(shí)際情況加入相應(yīng)的擾動(dòng)值，方便進(jìn)行合成計(jì)算。擾動(dòng)值是作為替代0的存在，一般越小越好，通常按照數(shù)據(jù)的精確度設(shè)定相應(yīng)的擾動(dòng)值，例如本文數(shù)據(jù)的精確度只在小數(shù)點(diǎn)后2位，故使用擾動(dòng)值ε=0.01。

根據(jù)表5中列出的融合結(jié)果進(jìn)行比較，結(jié)果如圖2～4所示。

表1 基本概率分配(BBA)及焦元

表2 ELNA的處理結(jié)果

表3 Bayesian近似算法的處理結(jié)果

表4 Summarization近似算法的處理結(jié)果

從處理結(jié)果可見(jiàn)：無(wú)論是對(duì)證據(jù)中mass較小的焦元(證據(jù)M1、M2)的舍棄上，還是對(duì)多焦元證據(jù)(證據(jù)M4)的處理上，ELNA都與主觀Summarization近似算法的處理結(jié)果類似，明顯優(yōu)于同為非主觀的Bayesian近似算法的處理結(jié)果。ELNA會(huì)依靠減少需要計(jì)算的焦元數(shù)量來(lái)解決“焦元爆炸”的問(wèn)題。

從表5的融合結(jié)果可見(jiàn)：ELNA的融合結(jié)果與Bayesian近似算法的融合結(jié)果基本保持一致。Bayesian近似算法僅對(duì)復(fù)合源進(jìn)行了處理，其融合結(jié)果應(yīng)和不經(jīng)過(guò)近似處理的Dempster組合規(guī)則的融合結(jié)果一致,因此ELNA融合結(jié)果是可信的。Summarization近似算法的結(jié)果與其他方法存在一定的差異，主要問(wèn)題在于融合確定性較低的證據(jù)(證據(jù)M4)對(duì)其結(jié)果產(chǎn)生的較大的影響，因?yàn)槠淙诤锨?個(gè)證據(jù)知之后的支持度依次為0.725、0.208、0.014、0.014、0.014、0.025，而融合第4個(gè)證據(jù)使其結(jié)果產(chǎn)生了較大的偏差。ELNA近似算法通過(guò)融合前的權(quán)重分配，對(duì)于像上例中的確定性較差的證據(jù)(證據(jù)M3、M4)給予較低的權(quán)重值，這樣產(chǎn)生的融合結(jié)果基本是正確可信的。本文在處理確定性較差的焦元時(shí)會(huì)突出其主要的焦元，保留其最主要的信息。在最終的融合中這些信息能提高主要信息的支持度，使得證據(jù)的每個(gè)部分都有自己的用處，避免了信息的丟失。

表5 融合結(jié)果

圖2 兩個(gè)證據(jù)的融合結(jié)果(m12)

圖3 3個(gè)證據(jù)的融合結(jié)果(m123)

圖4 4個(gè)證據(jù)的融合結(jié)果(m1234)

3.2 特殊情況仿真結(jié)果及分析

這里主要針對(duì)特殊情況(錯(cuò)誤證據(jù))的融合,由于Summarization近似算法通常對(duì)錯(cuò)誤證據(jù)采取直接舍棄的方式進(jìn)行處理,因此這里主要比較ELNA和Bayesian近似算法在特殊情況下的融合效果。

為了方便計(jì)算,在這里采用5個(gè)同證據(jù)等級(jí)的焦元進(jìn)行融合,識(shí)別框架的概率分配函數(shù)及焦元如表6所示,因?yàn)镋LNA主導(dǎo)證據(jù)的選取是完全隨機(jī)的，在這里使用融合結(jié)果的期望值作為最終值，最終融合結(jié)果如表7所示。

表6 基本概率分配(BBA)及焦元

表7 融合結(jié)果

基于錯(cuò)誤證據(jù)的融合分析結(jié)果可知：無(wú)論是Bayesian近似算法還是ELNA都說(shuō)明只要融合足量的證據(jù)，即使其中摻雜著少量的錯(cuò)誤證據(jù)也并不會(huì)對(duì)融合結(jié)果產(chǎn)生太大的影響。從計(jì)算的角度看，ELNA的主導(dǎo)證據(jù)的選取方式?jīng)Q定融合的證據(jù)越多融合結(jié)果的可靠性越強(qiáng)。從計(jì)算復(fù)雜度上看，ELNA只有在焦元個(gè)數(shù)多的證據(jù)融合方面優(yōu)勢(shì)明顯，在應(yīng)對(duì)焦元個(gè)數(shù)少的證據(jù)融合時(shí)并沒(méi)有太好的表現(xiàn)。從融合結(jié)果各個(gè)焦元的數(shù)值上看，很顯然ELNA的融合結(jié)果更符合實(shí)際情況，mass值較小的焦點(diǎn)C即使融合了4次0.1也能保持0.049的數(shù)值，較為直觀地說(shuō)明:焦元C是作為主要焦元而存在，符合5個(gè)證據(jù)焦元的實(shí)際情況。反觀 Bayesian近似算法融合3次就基本忽略焦元C，融合4次焦元C的值就直接等于0了,甚至焦元B都明顯被忽略掉了,很顯然不符合實(shí)際情況。

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

本文提出了一種非主觀的近似算法(ELNA)，不需要人為判斷的參與，使用ELNA可使傳統(tǒng)的證據(jù)理論在實(shí)際中得到更廣泛的應(yīng)用。該算法利用焦元的累積mass值去劃分證據(jù)的等級(jí)，根據(jù)不同的證據(jù)等級(jí)設(shè)定不同的初始標(biāo)準(zhǔn)，并且會(huì)將舍棄的焦元按比例分配到保留的焦元中，增加了證據(jù)的準(zhǔn)確性，最后會(huì)根據(jù)證據(jù)的等級(jí)不同給予不同的權(quán)重值，進(jìn)一步確保了融合結(jié)果的正確性。無(wú)論是對(duì)復(fù)合焦元、多焦元引發(fā)的“焦元爆炸”，還是在對(duì)錯(cuò)誤證據(jù)融合上,ELNA都給予了相應(yīng)的解決方案。適用性強(qiáng)且兼具準(zhǔn)確性的特點(diǎn)使ELNA在參與特別是焦元數(shù)目較多且準(zhǔn)確性要求較高的實(shí)際問(wèn)題時(shí)優(yōu)勢(shì)明顯。