一種基于粗糙集證據理論深度融合的局部沖突快速合成方法

倪龍強，張麗華，姚新濤，胡高歌，劉鵬輝

(1.西北機電工程研究所，陜西 咸陽 712099;2.西北工業大學 自動化學院，陜西 西安710072)

0 引言

現代檢測、認知、規劃、決策與控制系統所面對的環境、任務越來越呈現出復雜系統的多樣性、不確定性、不可預見性等特征。例如：在復雜環境態勢感知中，需用到不同維度、不同模態的檢測信息進行聯合識別和跟蹤，以提高態勢感知信息的完備性、客觀性和可理解性[1]；在聯合檢測、識別中，氣象、地理、電磁等因素可能會導致某些傳感器對目標或目標的某一特性檢測性能下降等[2]。因此對分布式檢測與融合方法提出了新的更高要求。主要表現在以下兩方面：1)如何基于大量傳感器檢測信息進行快速融合；2)如何在各檢測數據源檢測信息不完備、相互沖突條件下完成分布式探測信息的融合。

在經典貝葉斯框架下，證據理論將每個傳感器量測信息看作一個證據體，每個傳感器量測信息可能包含若干檢測屬性，該檢測屬性稱為證據焦元，一條證據體包含若干證據焦元。傳感器檢測對每個屬性的支持度稱為焦元基本信度分配(BBA)函數，證據理論通過對證據體進行兩兩組合來更新BBA函數。由于證據推理過程只能對證據體進行兩兩合成，在證據體較多時計算量呈指數性增長，同時傳統證據推理問題在兩條證據體存在沖突時可能得到有悖常理的組合結果。因此，近年來領域專家對證據理論的合成規則進行了大量研究修改，以期獲得更加客觀、統一的決策信息[3-7]。

關于沖突證據合成問題的研究最早可以追溯到1986年，Zadeh在文獻[8]中首次指出：當待合成證據體存在高度沖突時，Dempster-Shafer(D-S)組合規則會導致錯誤的融合結果。針對沖突證據合成問題，Smets[9]提出了基于閉世界和開世界假設的沖突證據合成修正方法。其中閉世界假設認為：沖突合成中產生錯誤結果的原因在于證據源受到干擾或合成規則的問題[10]；開世界假設建立在證據體完全可靠的基礎上，認為沖突的形成是由于辨識框架不完備所引起的，例如新模式、新方法的出現[11]。由于在實際應用中，很難滿足證據源完全可靠的前提假設，同時新模式很難事先確定，因此對沖突證據合成的改進大多數基于閉世界假設。在閉世界假設中，對證據合成的修正主要表現為：1)對融合證據源進行修正；2)對證據組合規則進行修正[12-14]。

對融合證據源的修改認為：D-S融合規則本身沒有問題，造成有悖常理的融合結果其主要原因在于證據體本身存在的沖突等因素，因此通過對待合成證據體進行預處理，再應用D-S組合規則進行證據合成[15-19]；對證據規則的修正認為：證據合成規則應能夠適應不同數據源，因此應當對證據合成規則進行修正[20-21]。

由于從沖突中不能直接給出正確或錯誤的結論，應將沖突按照一定的規則分配給待合成證據體，從而達到抑制沖突、增強一致的目的。假設傳感器量測的不一致來源于對某一檢測屬性的不穩定量測，因此應從傳感器量測信息中發現傳感器探測穩定性；利用傳感器量測差異來描述傳感器量測沖突。粗糙集通常被用來進行知識系統分類，其與證據理論可以相互描述，同時具有很強的互補性[22]。由于無需任何先驗知識就能夠發現信息系統內存在的關聯規則，近年來關于粗糙集與證據理論相結合的研究大都集中在刻畫知識系統中的不確定性[23]、數據預處理[24-27]等方面。

為解決證據合成在規則提取方面存在的不足，本文應用粗糙集理論對分布式傳感器獲取的大量檢測信息進行屬性約簡，從而降低待合成證據體的維度，同時計算出每條檢測記錄的支持度，并在證據合成規則中通過引入證據體支持度、焦元差異化等因素來刻畫證據體之間的沖突，以期降低證據組合中的計算量，提升沖突證據合成的客觀性和可理解性。

1 粗糙集屬性約簡及沖突證據合成

1.1 基于粗糙集的信息系統屬性約簡

在粗糙集中(U,A,F)表示一個信息系統，其中：U為對象集，

U={x1,x2,…,xn}，

(1)

xi(i≤n)稱為1個對象，n為對象總數；A為屬性集，

A={a1,a2,…,am}，

(2)

al(l≤m)稱為1個屬性，l為屬性標號；F為U與A之間的關系集合，

F={fl:U→Vl(l≤m)}，

(3)

Vl為al(l≤m)的值域。

對于任意的B?A，記

RB={(xi,xj)|fl(xi)=fl(xj)}(al∈B)，

(4)

則RB是U上的等價關系；記

[x]B={xj|(xi,xj)∈RB}，

(5)

則U/RB={[xi]B|xi∈U}是U上的劃分。劃分可以在特定關系下將信息系統分為若干類，關于粗糙集的其他性質可參考文獻[8]。

1.2 D-S證據推理及沖突證據合成

令A為信息系統(U,A,F)中所有屬性的集合，并且A中包含的所有元素互不相容，此時A為對象xi的識別框架。由于證據理論采用信任函數來度量對某一屬性的未知程度，fl(xi)→[0,1]，滿足下列條件：

(6)

此時稱fl(xi)為屬性al的一個基本概率賦值，fl(xi)表示在對象xi(可表示某一傳感器、某一探測源或某一故障模式)下對屬性al的精確信任度，表示對屬性al的直接支持程度。

設f1(·)和f2(·)分別是屬性集合A上兩個信任函數的基本概率指派，其焦元分別為ai和aj.定義

(7)

此時，D-S證據合成公式可以表示為(8)式所示的形式：

(8)

式中：K1有時也被稱為沖突系數，如果K1≠1，則f(xk)可確定一個基本概率指派值；如果K1=1，則認為待合成證據體x1和x2沖突，此時不能應用D-S證據合成規則對基本概率指派進行組合。

2 粗糙集證據理論深度融合的沖突證據合成

2.1 證據沖突形成的原因分析

在假設多數(傳感器總數的50%以上)傳感器量測均為可靠量測的前提下，至少可以得到以下結論：1)多數傳感器量測產生較一致的量測信息；2)個別證據體與其余證據體產生較大差異時，可能是由于該傳感器的誤檢測或傳感器性能下降等原因引起的；3)個別證據體某一焦元產生異常，可能是由于該檢測傳感器，在某一屬性的檢測上發生錯誤或其他原因(如遮擋、氣象條件、電磁干擾等引起的對目標某一檢測屬性的檢測性能下降)造成對該屬性檢測的異常。

基于以上假設，可以認為待合成證據體沖突主要來源于：1)待合成證據體相互之間支持度不一致引起的沖突；2)待合成證據體中同一焦元支持度在辨識空間中所占比例不同引起的沖突；3)不同證據體中同一焦元屬性不一致引起的沖突。

因此可以認為：1)數據集中其他證據體對該證據體支持度高的證據體可信度大；2)在滿足1的情況下，證據焦元在該證據體中占比較大，該焦元可信度高；3)不同證據體之間，相同焦元在待合成證據體中所占比例差異大的沖突高，因此一致性較低，可信度與一致性高的相比要低。

由以上分析可知粗糙集證據理論深度融合的數據挖掘方法如下：首先應用粗糙集對各傳感器獲得的證據體進行屬性約簡從而降低數據集維度，并計算證據體之間的相互支持度；其次計算證待合成證據體中同一焦元支持度在證據體中所占比例；再次計算不同證據體中同一焦元支持度的差異化程度；最后將以上計算結果通過沖突化因子的形式引入證據合成公式。具體過程如圖1所示，其形象化描述如圖2所示。圖2中a1、a2、a3、a4為證據焦元屬性，mi(*)為證據體i的焦元屬性值，i=1,2,3,4.

圖1 處理流程Fig.1 Procedure of fusion processing

圖2 局部沖突計算過程示意圖Fig.2 Schematic diagram of local conflict calculation

2.2 沖突因子的計算

假設對表1所示的兩條證據體應用D-S證據合成規則進行合成。

表1 沖突證據Tab.1 Conflict evidences

此時盡管證據體x1和x2對事件a2的支持度都很低，計算得到沖突系數為K1=0.99，由D-S組合規則合成的結果如表2所示，該結果顯然是不合理的。

表2 沖突證據合成結果Tab.2 Synthesis result of conflict evidences

仍然以表1的兩條證據體為例，當收到第1條證據體時，直覺上第1條證據體x1完全支持屬性a1，在接收到第2條證據體時，直覺上第1條證據體x2完全支持屬性a2.顯然造成證據合成結果的主要問題在于，兩條證據體對同一屬性的支持度產生了強烈沖突。接收到若干個證據體后的證據體如表3所示。

表3 包含多條證據體的沖突證據Tab.3 Evidence set including multiple conflict evidences

此時可以通過2.1節所述粗糙集理論對待合成證據體進行分類和屬性約簡，并計算信息系統對每條證據體的支持度，將證據體的重復因素納入計算。如果將信息系統對某一條證據體的支持度表示為Supp，則通過屬性約簡后，待合成證據體如表4所示。

表4 通過屬性約簡的待合成證據體Tab.4 Evidences to be synthesized by attribute reduction

通過表4可以看出：約簡后的證據體仍為沖突證據體。例如分布在不同區域的傳感器可能受到某一頻段干擾，有可能導致這種情況的產生。沖突的主要來源為：1)信息系統對每條證據體的支持程度不同，此時信息系統對第2條證據體的支持程度高于對第1條證據體的支持程度；2)同一證據體中，不同焦元在辨識空間上所占比例大小，直接影響證據合成中該焦元對合成證據焦元的貢獻程度，所占比例大，則合成貢獻大；3)兩條證據體對同一屬性焦元支持度的差異，如表4所示的兩條證據體對屬性a1和屬性a3的支持度完全矛盾，差異越大說明沖突越大，即便是不同證據體對同一焦元屬性支持度均相同，也要考慮焦元支持度在辨識空間上所占的比例，如表3和表4所示；不同證據體對屬性a2的支持度完全一致，同時支持度都很低，此時有理由相信合成屬性為a2的可能性較低。

造成以上結果的原因是多方面的，例如：通信傳輸誤碼率、傳感器本身或特定環境下對于某一屬性探測性能較低等。為討論方便，將表4改寫為表5所示的形式。

表5 對表4的簡化描述Tab.5 Simplified description for Tab.4

通過以上討論和分析，可以通過以下步驟對待合成證據體的沖突進行計算。

步驟1計算信息系統對證據體的支持度，

(9)

步驟2計算待合成證據空間對不同證據體相同焦元的支持度，

(10)

步驟3計算不同證據體之間同一焦元的差異化程度，

(11)

由(9)式可以看出：信息系統對證據體支持度高的證據體可信度高；由(10)式可以看出：相同焦元在待合成證據空間占比較高的屬性獲得的支持度較高；由(11)式可以看出：待合成證據體中，不同證據體之間同一焦元差異化程度大的焦元可信度低。

由于充分考慮了待合成證據體與信息系統、證據體與焦元、證據體相同焦元之間的支持度、比例以及一致性等因素，對沖突分配考慮得相對較全面，同時基于以上因素進行分配增強了沖突分配的客觀性和合理性。

2.3 證據合成

通過以上討論與分析可知，由于沖突中包含一些潛在有用信息，沖突中有些部分對待合成證據體及屬性焦元起到支持作用、有些起到削弱作用，待合成證據體、焦元屬性之間存在的沖突應該在引起沖突的證據體及焦元屬性之間進行分配。因此證據合成公式可以表示為

(12)

式中：ci(x)為各局部沖突分配給焦元ai的部分，

(13)

r1(ai)、r2(ai)分別表示待合成證據體1、2中證據焦元ai的可信度。由于(9)式～(11)式所示的證據體支持度、焦元支持度以及焦元差異化程度反映了證據體沖突程度，因此可以用(9)式～(11)所示的因子對焦元可信度進行描述。(10)式所示的焦元支持度滿足歸一化準則，可以直接用來進行沖突分配，對(11)式所示焦元差異化程度進行歸一化處理，可得

(14)

此時可將沖突通過證據體支持度進行分配，例如在表5中由于信息系統對第2條證據體支持度高，在證據合成中應加大該證據體包含證據焦元的合成比例。假設對兩條證據體進行合成，信息系統對證據體1的支持度為Supp1，對證據體2的支持度為Supp2，則證據體1中焦元在證據合成中的可信度如(15)式所示，證據體2中焦元在證據合成中的可信度如(16)式所示：

(15)

(16)

由于在證據合成之前通過粗糙集對信息系統進行了屬性約簡，消除了重復證據體參與證據合成計算帶來的時間消耗，同時在沖突證據合成中充分考慮了信息系統對證據體的支持度、待合成證據體焦元在辨識空間中所占的比例以及待合成證據體對同一證據焦元之間存在的沖突等因素，因此可有效降低待合成證據數量，同時對沖突分配相對客觀。

3 算法驗證

3.1 測試數據說明

為了驗證本文所提算法的有效性，采用表6所示的測試數據集，測試數據包括5條證據體，每條證據體包含3個屬性。同時有3條證據體完全相同，有1條證據體與其余4條證據體完全沖突，具體測試數據見表6.

表6 測試數據Tab.6 Test data set

在進行證據融合之前，先通過粗糙集對表6所示的測試數據集信息系統進行分類約簡，經過分類約簡的證據體數據集信息系統如表7所示。

表7 約簡后的測試數據集Tab.7 Test data set based on rough sets reduction

3.2 算法測試結果

應用不同融合規則對表6、表7所示的測試數據進行證據組合，結果如表8所示。應用D-S合成規則的合成結果如圖3所示，應用本文合成方法合成的結果如圖4所示。

圖3 D-S方法合成結果Fig.3 Synthetized results of D-S

圖4 本文方法合成結果Fig.4 Synthetized results of proposed combination rule

3.3 計算復雜度比較

假設有100個傳感器對目標進行檢測，融合中心接受到的證據體重復率分別為0%，10%～90%(在實際應用中，傳感器量測往往會存在微小差異，此時可以對傳感器量測設置一定的門限值，并進行數據整定。如：傳感器量測差異在某個范圍內就可認為證據體完全相同)。分別應用D-S證據理論和基于粗糙集證據理論相融合的合成規則對以上證據體進行組合，并對合成計算時間消耗進行統計。由于粗糙集證據理論相融合的合成規則先進行粗糙集約減，再進行證據合成(包含沖突分配)，因此不同證據重復率條件下的計算時間會存在差異。不同重復率條件下，經過仿真計算，得到應用D-S證據理論和應用粗糙集證據理論相融合的合成規則其計算時間消耗如圖5～圖14所示。

表8 合成結果比較Tab.8 Comparison of combined evidences of popular synthesis rules

圖5 重復率為0的證據體合成計算時間對比Fig.5 Computing time of evidence synthesis with repetition rate of 0

圖6 具有10%重復率的證據體合成計算時間對比Fig.6 Computing time of evidence synthesis with repetition rate of 10%

圖7 具有20%重復率的證據體合成計算時間對比Fig.7 Computing time of evidence synthesis with repetition rate of 20%

圖8 具有30%重復率的證據體合成計算時間對比Fig.8 Computing time of evidence synthesis with repetition rate of 30%

圖9 具有40%重復率的證據體合成計算時間對比Fig.9 Computing time comparison of evidence synthesis with repetition rate of 40%

圖10 具有50%重復率的證據體合成計算時間對比Fig.10 Computing time of evidence synthesis with repetition rate of 50%

圖11 具有60%重復率的證據體合成計算時間對比Fig.11 Computing time of evidence synthesis with repetition rate of 60%

圖12 具有70%重復率的證據體合成計算時間對比Fig.12 Computing time of evidence synthesis with repetition rate of 70%

圖13 具有80%重復率的證據體合成計算時間對比Fig.13 Computing time of evidence synthesis with repetition rate of 80%

圖14 具有90%重復率的證據體合成計算時間對比Fig.14 Computing time of evidence synthesis with repetition rate of 90%

在不同證據體重復率下，單獨應用證據理論進行合成與應用本文方法合成的平均計算時間消耗對比如表9和圖15所示。

圖15 兩種方法在不同重復率條件下的時間消耗對比Fig.15 Computing-time consumption of two methods

表9 不同重復率條件下兩種方法的仿真計算時間對比Tab.9 Computing times of two methods at different repetition rates

3.4 測試計算結果分析

算例1對D-S組合規則、Yagerr組合規則、文獻[17]、文獻[21]和文獻[28]給出的組合規則以及本文給出的融合規則進行了對比，并應用一組典型數據對各融合規則計算結果進行了測試對比，由對比結果可以看出：本文給出的融合結果在第2次融合結束后就可分辨出可信度較高的焦元屬性值，并與直觀接近。這主要是因為待合成證據體中有3條重復，經過粗糙集約簡后證據體由5條簡化為3條；同時在證據合成中考慮了證據體的支持度和焦元可信度等因素，支持度高的證據體以及可信度高的證據焦元在證據合成中所占比重相應增大，因此只需要2次合成就能夠得到合成結果。

算例2對本文給出的合成規則與D-S證據合成規則計算時間進行了比較，由仿真結果可以看出，當待合成證據體中無重復時要進行額外的粗糙集約簡過程，造成時間的額外損耗，此時應用粗糙集和證據理論性融合的規則比單獨應用證據合成規則時間消耗大。當待合成證據體中有90%不重復時，兩種方法計算時間相當，但是當待合成證據體重復率增大時，本文給出的方法計算量明顯降低。實際應用中可能會存在各級情報中心對分布式感知源獲取的信息進行融合，而傳送到融合中心的數據一般會存在大量重復，因此適合應用該方法進行融合處理。

4 結論

在應用證據理論進行多傳感器屬性融合過程中，證據體及證據屬性過多時容易引起組合爆炸，同時當分布式傳感器檢測具有沖突時，可能會存在一票否決等問題。本文通過在證據體合成過程中引入信息系統及粗糙集理論概念，采用信息系統屬性約簡的方法對待合成證據體進行約簡，從而將問題轉化為較低維度的融合問題，同時在證據體合成中綜合考慮了證據體之間的支持度、焦元屬性之間的支持度和差異度等因素，基于此給出了沖突證據合成公式，并進行了仿真驗證。

結果表明：經過屬性約減，證據合成時間得到有效降低，特別是當待合成證據體重復率較高的情況下，計算復雜度降低效果明顯；同時，通過對沖突的重新定義和分配，合成結果相對客觀。