陳 鵬， 何 凱，余肖生

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

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

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

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

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

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

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

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

(1)

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

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

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

(2)

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

m(?)=0

(3)

(4)

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

(5)

(6)

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

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

(7)

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

(8)

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

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

(9)

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

(10)

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

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

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

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

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

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

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

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

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

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

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

?A?H

(11)

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

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

(12)

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

3) 近似處理(approximate treament)

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

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

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

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

(13)

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

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

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

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

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

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

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

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

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

0.5+0.1*等級差∶0.5-0.1*等級差

(14)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5 融合結(jié)果

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

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

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

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

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

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

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

表7 融合結(jié)果

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

4 結(jié)束語

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