沖突證據的融合方法研究
2008-12-31 00:00:00王加陽周勇
計算機應用研究 2008年7期
摘 要：證據理論是處理不確定問題的重要方法，但在現實中不同來源的證據往往存在相互沖突，采用合適的方法對其進行融合是解決這一問題的有效手段。討論了DS證據合成規則存在的問題和相對于其他合成方法的優勢，提出了評價合成規則融合效果的指標，重點對幾種證據合成方法進行分析和比較，指出其特點與不足，提出進一步研究的方向。
關鍵詞：證據理論; 合成規則; 沖突證據; 信息融合
中圖分類號：TP18 文獻標志碼：A
文章編號：1001-3695(2008)07-2046-04
Research on fusion of conflict evidence
WANG Jiayang，ZHOU Yong
(College of Information Science Engineering， Central South University， Changsha 410083， China)
Abstract:The theory of evidence is important for solving uncertain problem， but in reality the evidence from different sources often exists in conflict with each other， so finding a good fusion method is an effective tool to deal with conflict evidence.This paper discussed the problem in combination rules of DS evidence and the advantages to the other combination methods，proposed some standards for evaluating the fusion result.analyzed and compared typical methods for combination of evidence，pointed out several problems for further research.
Key words:evidence theory; combination rules; conflict evidence; information fusion
證據理論在信息融合中獲得了廣泛的應用，它比傳統的概率論更好地把握了問題的未知性和不確定性。但是，DS證據理論本身也存在許多缺點，如證據推理的組合條件十分嚴格要求組合證據是條件獨立的、證據組合引起的焦元爆炸、證據基本概率指派確定的主觀性(由專家確定)等，限制了它的使用范圍。在證據理論中對所有的證據源都是平等對待的，但由于現實中不同來源的證據具有不同的可靠性和重要性，從而這一問題僅由證據理論不能得到很好的解決。證據合成法則是證據理論的核心，它對合成結果正確與否起著關鍵作用。然而所獲得的證據常常包含沖突信息，會導致合成法則失效。
1 證據理論基礎
20世紀60年代美國哈佛大學數學家A. P. Dempster利用上、下限概率來解決多值映射問題方面的研究工作。自1967年起連續發表了一系列論文，標志著證據理論的正式誕生。Dempster的學生G. Shafer[1]對證據理論作了進一步的發展，引入信任函數概念，形成了一套基于證據和組合來處理不確定性推理問題的數學方法，并于1976年出版了《證據的數學理論》，此后證據理論取得了很大的發展，應用上取得了豐富的成果，并在信息融合、不確定性推理、多規則決策、模式識別、綜合診斷等領域中得到了較好的應用。
設Θ表示X所有可能取值的一個論域集合，且所有在Θ內的元素間是互不相容的，則稱Θ為X的識別框架，那么人們所關心的任一命題都對應于Θ的一個子集。若Θ={θ1，θ2}，則有Θ的冪集：2Θ={，Θ，{θ1}，{θ2}}。
定義1 基本可信度分配(basic probability assignment，BPA)。在識別框架Θ上的BPA是一個函數m：2Θ→[0， 1]，稱為mass函數。并且滿足下列條件：
a)m() = 0；b)AΘm(A)=1。
其中:m為框架Θ上的基本可信度分配；m(A)為A的基本可信數?；究尚艛捣从沉藢Κ獳本身的信度大?。ǘ还芩娜魏握孀蛹?，使得m(A)>0的A稱為焦元(focal elements)，所有焦元的并成為信度函數Bel的核心。
定義2 信任函數也稱信度函數（belief function）。在識別框架Θ上基于基本可信度分配m的信任函數定義為
對于AΘ，Bel(A)=BAm(B)
即Bel(A)為A中所有子集的基本可信數之和，且有Bel()=0，Bel(U)=1。
定義3 似然函數也稱似然度函數 (plausibility function)。在識別框架Θ上基于基本可信度分配m的似然函數定義為
K的引入實際上是為了避免證據組合時將非零的概率賦予空集，將空集所丟棄的信度分配按比例地補給到空集上。DS合成法則是一個反映證據的聯合作用法則，給出同一識別框架上基于不同證據的信度函數，如果這幾個證據不是完全沖突的，那么就可以用DS合成法則計算出一個信度函數作為那幾個證據聯合作用下產生的信度函數。
2 證據理論存在的問題
DS證據理論具有比較強的理論基礎，它既能處理命題的不確定性問題，也能將不知道和不確定區分開來，但它也存在明顯的不足。證據推理雖然產生三十幾年，但是由于它理論上的局限，一直制約它的應用推廣。主要存在的問題如下：
a)當證據沖突度較高時，經過其組合規則得到的結論常常有悖常理。這是因為該理論規定m()=0，而在不同證據組合的過程中得到的空集的概率事實上并不為0，在組合的過程中DS方法舍棄這部分概率的值，通過乘以沖突權值K來對組合后的基本概率值進行歸一化處理，這樣就產生有背常理的結論。明顯的例子如魯棒性問題：m1(a)=0.9，m1(b)=0.1和m2(b)=0.1，m2(c)=0.9(其中a、b、c是相互獨立的焦元)，組合結果為m1m2(b)=1，事件b由置信度0.1變為必然確定事件，這顯然不合理。Yager給出的解決方法是將沖突的基本信任指派加入m(Θ)中，即分配在所有元素中，而不像原來那樣僅僅分配在焦元集合上。Smets則認為導致融合結果不合理的原因在未知環境中不可能得到一個完備的識別框架，因而必然存在著一些無法判斷其真偽的未知命題，沖突的部分正是這些未知命題造成的，將沖突量分配給空集，即假定m()>0用來表示證據沖突，但是這樣就破壞證據推理的封閉性，從而帶來其他問題。國內也有很多學者在解決證據沖突上做了大量的研究工作，并提出了一些新的合成方法。
b)證據推理的組合條件十分嚴格。Dempster組合規則要求兩證據是條件獨立的，這往往不符合客觀實際。當兩個證據有相關性時，應用DS合成法則進行證據合成，將導致結果的超估計；而且要求辨別框架能夠識別證據的相互作用，兩相關證據的融合問題早已提出，Wu等人[2]在這方面有了嘗試性討論。其次，DS合成法對各信息源提供的證據是平等對待的，在合成時各信息源提供證據的重要性與可靠性無優劣之分，這也與客觀實際不太相符，特別是當出現證據高度沖突時，其合成結果會出現逆序或有悖常理的現象。
c)證據組合會引起焦元爆炸。焦元以指數級數遞增，造成計算量變大。這一問題已經有許多解決方法，如Denceux提出了證據推理的神經網絡實現[3]；另外還有減少焦元的方法，Mamer提出的先驗條件一致度具備距離的性質，可以作為刪除焦元前后證據變化的量度，而用證據對焦元靈敏度的方法刪除不必要證據，用信息的變化也可以減少證據數目。
d)證據推理與貝葉斯推理的比較仍然是大家注視的焦點之一。貝葉斯推理是利用貝葉斯公式進行概率修正。證據推理與貝葉斯推理有很多相似之處[4]，當證據的焦元為單元集時，置信函數和似真函數與概率相等，即Bel(A)=P(A)=Pl(A)。Buede等人[5]給出了證據推理在收斂速度上不如貝葉斯推理，如在目標識別的應用中。
3 證據的合成
DS理論需要對多個不確定證據進行組合，隨著證據的不斷積累而逐步縮小假設集，最終獲得精確推理結果。證據的積累過程，需要一種方法或規則來計算多個證據對假設的影響程度。DS理論提出的DS證據組合公式就是這樣的證據組合方法，它對于某一具體問題，在封閉框架中對多個相互獨立的證據來進行組合推理。DS證據理論憑借其特點和相對于其他處理不確定性、未知等不確定推理模型理論的優勢，被成功地應用于諸如信息融合、數據挖掘、模式識別、醫療診斷、決策分析等領域來解決不確定信息的處理問題，特別是在數據融合中的應用較為廣泛。利用DS證據合成規則進行多源信息融合的優勢在于：
a)滿足比Bayes概率理論更弱的條件，即不必滿足概率可加性。DS證據理論認為，對于概率推斷的理解，不僅要強調證據的客觀性，而且要強調證據估計的主觀性，在證據的基礎上構造出對一命題為真的信任程度，簡稱為信度。證據理論中需要的先驗數據比概率推理理論中的更為直觀、更容易獲得，再加上Dempster合成公式可以綜合不同專家或數據源的知識或數據，這使得證據理論在專家系統、信息融合等領域中得到了廣泛應用。
b)證據理論有較強的理論基礎，既能處理隨機性所導致的不確定性，也能處理模糊性導致的不確定性。同時，證據理論不僅能在規則中反映未知信息，而且具有直接表達不確定和不知道的能力，這些信息表示在mass函數中，并在證據合成過程中保留了這些信息。
c)證據理論可以通過其合成法則來合成多個證據，從而逐步縮小假設集。其次，證據理論不但允許人們將信度賦予假設空間的單個元素，而且還能賦予它的子集，這很像人類在各級抽象層次上的證據收集過程。
在實際應用中，證據合成的關鍵問題是，對于給定的問題，如何選擇最合適的合成法則。因為衡量數據分析和規則獲取的質量主要取決于合成的效果，需要對各種不同合成規則的特點進行分析和比較，供實際應用時選擇。
4 證據合成規則分析
來自不同信源的證據在同一識別框架Θ上的作用，只要不是完全一致的，就會表現出若干沖突的特性。在DS證據理論中用k=Ai∩Bj=m1(Ai)m2(Bj)來表示證據間的沖突程度。k值越大，說明證據間的沖突也越大。但事實證明，DS合成法則中的k并不能真實地反映證據的沖突狀況，因為沖突并非是由所有焦元共同造成的，而k是所有證據同時考慮，它很容易受到個別異常證據的干擾。如果考慮證據兩兩之間的沖突狀況，由于它受個別異常證據的干擾相對而言要小得多，對沖突狀況的衡量就要準確得多。Dempster認為信度不應該分配在空集上，所以Dempster組合規則將沖突k舍去并且對信度進行了正則化過程。而Zadeh指出，對高度沖突的證據使用Dempster組合規則的正則化過程可能會導致某種與直覺相悖的融合結果，他用一個例子形象地說明了這一點。研究證據理論的學者們普遍認為導致錯誤結果的根本原因在于DS證據理論要求分配在空集上的信度為零(即m()=0)。目前主要存在以下幾種基于這一觀點的改進方法。
4．1 Yager的方法
證據理論在表示不確定性問題方面的優勢有目共睹，但是，證據理論在應用過程中存在著一些問題。首先，其組合規則在處理沖突證據時會得出與直覺相悖的結論，許多學者為擺脫這種困境而做了許多工作，但始終無法解決極端條件下(即完全沖突)證據的組合問題。Yager[6]針對上述問題提出了解決辦法，其提出的取消正則化過程基本思想是：既然人們并不真正知道沖突部分的情況，那么就讓它分配在所有的元素中(即將沖突部分放在Θ中)而不像原來那樣僅僅分配在焦點元素集合上。設m1與m2為識別框架Θ上的兩個獨立證據，Ω為Θ的冪集，A、B為冪集中的元素，則Yager提出的改進證據組合公式可形式化描述為
同時，Yager提出基于優先級證據的組合規則，即把給空集的指派值分給優先級較高的證據，這樣就保證了證據信息的單調非減。這一修正比較符合現實世界中的情況，能夠產生較為合理的信息融合結果。但是，Yager將沖突質量分配給全集時，由于有的原命題并不是造成沖突的原因，但也分配到一些沖突質量，這就造成沖突量分配的不公平。
4．2 Smets的方法
Smets發現許多DS模型的研究者只看到bpa是在識別框架Θ的冪集上的靜態概率分布，但他們一般都沒有研究DS模型的動態部分，即置信函數是如何更新的。因此，他提出了可傳遞置信模型TBM[7]。TBM是一個雙層模型：一個是credal層，在這層上的置信度轉換成pignistic概率，并由此作出決策；credal層先于pignistic層，在credal層上隨時可對置信度進行賦值和更新，而只有在必須作出決策時，pignistic層才出現。所以，TBM包括了兩個部分：a）靜態的，即基本置信指派；b)動態的，即置信度的傳遞過程。從數據融合的角度看，TBM模型在理論和實際應用上都很有價值，它是一種層次化的遞進模型，體現了數據融合系統的層次化描述特征，它尤其適用于需要逐層進行數據、特征或決策融合的數據融合系統。
Smets認為導致沖突證據組合結果不合理的主要原因是:由于在未知環境中不可能得到一個有窮且完備的識別框架Θ，必然存在著一些人們無法判斷其真假的未知命題，而沖突部分正是由這些未知命題造成的。為此，在可傳遞置信模型下Θ中的元素隨時可以增減且要求m()>0，因為m()對應的信任值可以理解為賦予未知命題的，并且定義Bel(Θ)=1-m()≤1，即為真的命題可能不出現在Θ中，Bel(Θ)不能恒等于1。Smets提出的改進證據組合公式可形式化描述為
m12(C)=A∩B=CC≠m1(A)m2(B)，A，B∈Ωm12()=A∩B=m1(A)m2(B)，A，B∈Ω
該合成方法討論了證據組合的諸多問題，Smets認為證據理論是其提出的可傳遞置信模型在接受封閉世界假設時的一個特例，即Dempster方法是可傳遞置信模型的一個自然的組成部分。他的這個模型很好地回答了Zadeh就ShaferDempster規則歸一化問題提出的反例，這種思想是建立在認為證據完全可靠的前提下，但在實際問題中并不一定具備這種前提條件。
4．3 向陽的方法
向陽等人認為證據組合規則應該滿足期望的基本性質，即當相互支持的證據組合在一起時，證據聚焦的權重應該由更大基數的集合指向更小基數的集合；而當相互沖突的證據組合在一起時，則結果正好相反。合成規則應具備幾個基本的數學性質，其中有一條就是對于不一致證據的合成提出了合理的解釋，假設采集到兩個證據e1和e2，在集合Θ={a，b，c，d}上，A={a}，B=，C={a，b}。如果Bel(A)=Pls(A)=1.0，Bel(B)=Pls(B)=1.0，換句話說，兩個同等的證據有著完全不同的結論。當然這種情況在實際生活中并不經常發生，這是常常發生的證據指向不同結論的極端情形。在這種情況下，合成規則應找出最合邏輯的最終結論。專家在這種情況下，會得出直觀合意的結論：e1e2=e3，Bel(C)=Pls(C)=1.0。
由于DS規則有很好的證據聚焦能力，證據經它作用后，概率分派函數向Θ中更小的子集移動。但是它無法處理不一致的極限情況，也沒有分辨證據所在子集的大小，從而按不同的權重聚焦?；谶@一思想，向陽等人[8]提出了一種解決沖突問題的新的融合方法來解決上述問題，即根據證據攜帶的信息量決定聚焦的權重并同時根據沖突系數k決定聚焦的方向。其具體規則定義如下：
其中‖#8226;‖為集合的基數。
兩個證據m1和m2的聯合式如下：
式中s1可解釋為向下聚焦的系數，它根據所聯合集合的基數大小決定向下聚焦的程度，以防止在大的子集上(攜帶確定性信息不多)的基本概率分派函數聚焦在小的子集上，后者在某種程度上攜帶有更多的確定性信息，公式通過(1-s1)和一個比例因子來決定保留在原有焦元上的m(#8226;)的大小。
該方法能很好地處理相互沖突的證據，并能根據證據攜帶的信息量決定聚焦的權重，根據需要將證據的權重聚焦到集合中更小的子集，又能根據需要向上回到集合中更大的子集，以解決不一致證據的問題，它還能根據子集的基數大小決定聚焦的權重，使組合結果更具有直觀合意性。
4．4 幾種融合方法的比較
Yager將沖突質量分配給全集時，由于有的原命題并不是造成沖突的原因，但也分配到一些沖突質量，這就造成沖突量分配的不公平；Smets所提出的將沖突質量分配給空集，這是建立在開放性識別框架基礎上的，他的方法在識別框架已知的情況下并不適用；向陽等人提出的方法較好地處理了不一致證據的問題。以Zadeh悖論為例，一宗謀殺案，有三個懷疑對象Peter、Paul、Mary，即識別框架Θ={Peter、Paul、Mary}，兩個目擊證人提供高度沖突的證據m1={0.99，0.01，0.00}，m2={0．00，0.01，0.99}。表1為Dempster、Yager、Smets、向陽等幾種不同的組合公式融合結果的比較。
合成規則的關鍵問題就是對沖突的處理。從表1可以看出各種合成規則都有一個側重點。顯然，DS合成法則完全遺棄了沖突的那部分基本信度分配而進行歸一化處理，從而導致融合結果違背常理；Yager提出取消歸一化過程，將沖突部分的信度分配在所有元素中，即表示造成沖突的所有命題都有可能是兇手；Smets所提出的將沖突質量分配給空集，將沖突量分配到未知命題中，對于命題的置信度動態更新也考慮在內，即提出的可傳遞置信模型。向陽的方法是根據證據攜帶的信息量決定聚焦的權重，并同時根據沖突系數k決定聚焦的方向，從而得到相對合理的融合結果。
5 結束語
證據理論作為處理不確定性信息的一種有效方法，是當前國內外人工智能領域的熱點研究課題，其理論和技術都得到了很大的發展。本文分析了DS證據合成規則存在的不足，同時分析了證據合成相對于其他多源信息融合方法的優勢，對當前存在的幾種證據合成方法，從不同的角度分析其特征并進行了比較。
現有的證據合成規則還未達到完善的程度，今后的研究方向關鍵是證據沖突的處理方法，證據理論與概率論、粗糙集、模糊集理論結合的進一步完善[9]，從而綜合考慮多方面因素提出合理全面的合成規則。當然，解決沖突證據的組合問題除了從證據組合規則入手以外，可以在證據組合前對證據進行一致性檢驗，避免對相互沖突的證據進行組合，這在實際數據融合過程中，對改善融合效果是十分重要的。
參考文獻：
［1］SHAFER G.Perspectives on the theory and practice of belief functions[J].International Journal of Approximate Reasoning，1990，4（5-6）:323-362.
[2]WU Yongge，YANG Jingyu，LIU Ke，et al.On the evidence inference theory[J].Information Science，1996，89(3-4):245-260.
[3] DENCEUX T.An evidencetheoretic neural network classifier[J].IEEE Int Conf on Syst ，Man，and Cybern，Vancouver，1995，25(3):712714.
[4]JAFFRAY J.Bayesian update and belief function[J].IEEE Trans on Syst， Man， and Cybern，1992，22(5):11441152.
[5]BUEDE D M，GIRARDI P.A target identification comparison of Bayesian and DempsterShafer multisensor fusion[J].IEEE Trans on Syst，Man，and Cybern，1997，27(5):569-577.
[6]YAGER R R.On the aggregation of prioritized belief structure[J].IEEE Trans on Syst， Man， and Cybern，1996，26(6):708719.
[7]SMETS P.The combination of evidence in the transferable belief model[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1990，12(5): 447-458.
[8]向陽，史習智.證據理論合成規則的一點修正[J].上海交通大學學報，1999，33(3):357-360.
[9]王加陽，羅安，蔣外文，等.模型集成誤差與優化研究[J].運籌學學報，2006，10(4):89-98.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文?！?/p>
