基于證據等級的非主觀近似算法

陳 鵬， 何 凱，余肖生

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

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

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

1 證據理論基礎及相關研究概述

1.1 證據理論基礎

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

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

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

(1)

它由N個窮盡且排他的假設組成。從其結構出發，可以得到由H組成的2N個命題，表示為：

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

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

(2)

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

m(?)=0

(3)

(4)

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

(5)

(6)

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

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

(7)

其中K為歸一化常數，

(8)

為了防止不可靠證據對融合結果產生影響，往往需要對融合的證據進行折扣：

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

(9)

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

(10)

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

1.2 相關研究簡述

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

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

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

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

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

2 基于證據等級的非主觀近似算法

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

1) 復合焦元的處理規則

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

?A?H

(11)

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

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

(12)

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

3) 近似處理(approximate treament)

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

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

近似處理：根據證據的不同等級給予不同的初始標準，超過初始標準的mass值保留，低于標準mass值的舍棄。

初始標準的設定按照證據等級來確定。確定的目的主要是為了進一步減少焦元，確定主要因素。不同等級的標準由函數s確定：

(13)

標準的制定完全按照證據初始的確定性等級來確定，確定性越高的證據設定的標準也就越低，方便剔除mass值很小的焦元，確定性越低的證據設定的標準越高，以此來提高處理后證據的確定性，方便進行下一步根據權重比融合不同的證據。

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

近似處理的目的就是為了更好地進行數據融合，而很多近似處理會丟失很多關鍵的信息。若直接進行融合，最后的結果往往可信度不高，不能作為決策的標準。

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

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

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

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

經過前面近似處理的證據按照證據之間的等級差取不同的權重比進行分級融合。

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

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

(14)

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

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

圖1 折扣判斷以及證據等級的判斷過程

3 仿真結果及分析

3.1 一般情況仿真結果及分析

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

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

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

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

表2 ELNA的處理結果

表3 Bayesian近似算法的處理結果

表4 Summarization近似算法的處理結果

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

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

表5 融合結果

圖2 兩個證據的融合結果(m12)

圖3 3個證據的融合結果(m123)

圖4 4個證據的融合結果(m1234)

3.2 特殊情況仿真結果及分析

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

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

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

表7 融合結果

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

4 結束語

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