一種快速DSmT-DS近似推理融合方法

郭 強(qiáng) 何 友 李新德

?

一種快速DSmT-DS近似推理融合方法

郭 強(qiáng)*①何 友①李新德②

①(海軍航空工程學(xué)院信息融合技術(shù)研究所 煙臺(tái) 264001)②(東南大學(xué)復(fù)雜工程測(cè)量與控制教育部重點(diǎn)實(shí)驗(yàn)室 南京 210096)

該文對(duì)Dempster-Shafer(DS)理論以及Dezert-Smarandache理論(DSmT)進(jìn)行了深入研究，為了能夠在僅需較低計(jì)算復(fù)雜度的前提下得到更加精確的融合結(jié)果，提出一種新的快速DSmT-DS近似推理融合方法。該方法針對(duì)超冪集空間僅單子焦元具有信度賦值的情況，將超冪集空間拆分映射成元素為各單子焦元和其補(bǔ)集的二元集合的新的超冪集空間，并求出每個(gè)補(bǔ)集的信度賦值；再運(yùn)用Dezert-Smarandache框架中的第5條比例沖突分配規(guī)則(DSmT+PCR5)在新的超冪集空間的二元集合子空間下對(duì)多證據(jù)源進(jìn)行融合，得到各單子焦元的融合結(jié)果；然后通過歸一化處理求得各單子焦元的信度賦值。通過理論分析得出該文方法的融合結(jié)果是介于Dezert-Smarandache框架中的第5條比例沖突分配規(guī)則(DSmT+PCR5)及Dempster-Shafer(DS)框架下的 Dempster 組合規(guī)則之間。該文方法在需要較低計(jì)算復(fù)雜度的前提下，可以得到優(yōu)于Dempster組合規(guī)則的近似融合結(jié)果。最后通過多個(gè)角度與已有方法進(jìn)行對(duì)比，驗(yàn)證了該文方法的優(yōu)越性。

信息融合；證據(jù)理論；Dezert-Smarandache理論；近似推理；拆分映射

1 引言

信息融合技術(shù)作為一門蓬勃發(fā)展的新興關(guān)鍵技術(shù)，由于可以將多個(gè)信源采集的不完整信息加以綜合，減少多源信息間可能存在的冗余和矛盾信息，降低其不確定性，提高智能系統(tǒng)決策、規(guī)劃、反應(yīng)的快速正確性，近年來得到國內(nèi)外學(xué)者的廣泛重視，并在軍事和國民經(jīng)濟(jì)等多個(gè)領(lǐng)域得到了廣泛的應(yīng)用。隨著信息環(huán)境的日益復(fù)雜，越來越多的信息獲取、融合和智能決策系統(tǒng)對(duì)于如何高效地融合高沖突、不完善、不精確的不確定證據(jù)信息提出了更高的要求。DSmT理論(Dezert-Smarandache Theory)是由文獻(xiàn)[5]提出的一種新的處理不確定、高度沖突和不精確的證據(jù)源的融合問題的有效方法。它可以看作是DST理論(Dempster-Shafer Theory)的擴(kuò)展，卻不受DS (Dempster-Shafer)框架的限制，可以有效處理復(fù)雜的靜態(tài)或動(dòng)態(tài)融合問題，特別是當(dāng)信息源間的沖突非常大時(shí)，或者是所考慮問題的框架中命題之間的界限模糊、不確定、不精確而很難細(xì)分時(shí)，DSmT都發(fā)揮了它的優(yōu)勢(shì)[6,7]。目前該理論方法已在圖像處理、機(jī)器人環(huán)境感知、軍事上的多目標(biāo)跟蹤與識(shí)別、故障診斷、雷達(dá)目標(biāo)分類等領(lǐng)域都得到了廣泛的應(yīng)用。而現(xiàn)階段推廣和應(yīng)用DSmT最突出的瓶頸問題是，隨著鑒別框架中焦元數(shù)目的增多，其組合推理運(yùn)算成指數(shù)級(jí)增長(zhǎng)。

為了解決這一問題，文獻(xiàn)[13,14]提出一種快速分層遞階的DSmT近似推理融合方法。該方法的融合結(jié)果在保持與DSmT經(jīng)典方法融合結(jié)果較高信息相似度的前提下，計(jì)算量顯著減少，較好地解決了DSmT的計(jì)算瓶頸問題。但該方法在信息源存在較高的沖突時(shí)，正確結(jié)果焦元的信度賦值會(huì)向其它焦元轉(zhuǎn)移，導(dǎo)致各焦元的信度賦值融合結(jié)果較平均，對(duì)沖突證據(jù)源敏感性弱，而且該方法需要對(duì)每一個(gè)二叉樹分組的焦元進(jìn)行Dezert-Smarandache框架中的第5條比例沖突分配規(guī)則(Proportional Conflict Redistribution No.5 within Dezert- Smarandache framework, DSmT+PCR5)融合計(jì)算，分組的粒度隨著焦元數(shù)目的增多而增多，導(dǎo)致計(jì)算量仍然較大。

因此，本文提出一種新的快速DSmT-DS近似推理融合方法。該方法針對(duì)僅單子焦元具有信度賦值情況，將超冪集空間拆分映射成元素為各單子焦元和其補(bǔ)集的二元集合的新的超冪集空間，并求出新超冪集空間中每個(gè)子空間中單焦元的補(bǔ)集的信度賦值。然后運(yùn)用DSmT+PCR5規(guī)則分別在映射形成的新的超冪集空間的二元集合子空間下對(duì)證據(jù)源進(jìn)行融合，得到各單子焦元的融合結(jié)果，最后通過歸一化求得每一個(gè)單子焦元的信度賦值。通過理論分析得出本文方法求得的融合結(jié)果是介于DSmT+ PCR5及Dempster規(guī)則之間且優(yōu)于Dempster規(guī)則的近似融合結(jié)果。通過計(jì)算復(fù)雜度分析得出，本文方法計(jì)算復(fù)雜度極小。仿真實(shí)驗(yàn)結(jié)果表明，該方法不僅計(jì)算復(fù)雜度極小，融合結(jié)果相似度更高，而且對(duì)于高沖突信息的融合問題，相比已有的近似融合方法，可以得到一個(gè)更精確的近似融合結(jié)果。

2 基本理論

2.1 DS框架下的Dempster組合規(guī)則

2.2 DSm框架下的PCR5融合規(guī)則

其中，卷入式(3)中所有的元素都是規(guī)范形式，當(dāng)證據(jù)信息模型為DS模型時(shí)，等價(jià)于冪集空間，當(dāng)證據(jù)信息模型為存在約束的混合DSm模型時(shí)，等價(jià)于超冪集空間,代表為中的任意非空焦元，代表中與沒有交集的非空焦元，

3 一種快速DSmT-DS近似推理融合方法

本文提出一種快速DSmT-DS近似推理融合方法，該方法程序流程如圖1所示。其主要步驟為：

圖1 快速DSmT-DS近似推理融合方法程序流程圖

步驟5 對(duì)步驟4求得的各單子焦元的信度賦值進(jìn)行歸一化處理。

3.1超冪集空間拆分映射

3.2求新超冪集空間的各單子焦元信度賦值

由3.1節(jié)可知，映射生成的新超冪集空間的元素不是傳統(tǒng)意義上的單焦元或多焦元，而是由單焦元和它的補(bǔ)集構(gòu)成的二元集合子空間，如其中的第個(gè)元素，也稱子空間，由單子焦元和其補(bǔ)集=構(gòu)成，其補(bǔ)集的信度賦值為

3.3對(duì)新的超冪集空間的子空間進(jìn)行DSmT+PCR5融合

對(duì)兩證據(jù)源在新的超冪集空間中對(duì)應(yīng)的相同單子焦元和其補(bǔ)集的子空間進(jìn)行DSmT+PCR5融合推理得到各單子焦元的信度賦值為

3.4 歸一化處理

從DSmT+PCR5規(guī)則式(3)分析可知，當(dāng)使用單子焦元的補(bǔ)集的信度賦值取代補(bǔ)集中各焦元的信度賦值求得，由于補(bǔ)集為一個(gè)焦元相比各單子焦元對(duì)于的信度賦值強(qiáng)度更強(qiáng)，融合過程中沖突焦元的信度賦值會(huì)有一部分按照比例轉(zhuǎn)移給了，而使減少，，本文通過將3.3節(jié)得到的初步融合結(jié)果歸一化，平均了各焦元損失的信度賦值，得到單焦元的最終的信度賦值，即

4 分析快速DSmT-DS融合結(jié)果與DSmT+ PCR5及Dempster規(guī)則融合結(jié)果的關(guān)系

對(duì)式(7)和式(8)進(jìn)行分析，得出本文方法融合結(jié)果與DSmT+PCR5及 Dempster組合規(guī)則融合結(jié)果的關(guān)系。令,,DSmT+PCR5規(guī)則中對(duì)的每一項(xiàng)的沖突分配表示為和,，即如果使用DSmT+PCR5規(guī)則，得出的焦元的基本信度賦值為

5 計(jì)算復(fù)雜度對(duì)比分析

針對(duì)僅有兩個(gè)證據(jù)源，且超冪集空間中僅單子焦元有信度賦值(,代表焦元個(gè)數(shù))的情況，首先直接采用DSmT+PCR5方法(以下簡(jiǎn)稱經(jīng)典方法)對(duì)兩證據(jù)源融合過程進(jìn)行計(jì)算復(fù)雜度分析，然后對(duì)文獻(xiàn)[13]方法進(jìn)行計(jì)算復(fù)雜度分析，最后對(duì)本文提出的快速DSmT-DS近似推理融合方法(以下簡(jiǎn)稱本文方法)進(jìn)行分析，通過計(jì)算復(fù)雜度的理論分析對(duì)比3種方法的計(jì)算效率。

6 仿真實(shí)驗(yàn)結(jié)果對(duì)比分析

為了驗(yàn)證本文方法的優(yōu)越性，本文從融合結(jié)果的相似性、方法的高效性、沖突敏感性及魯棒性4個(gè)指標(biāo)在相同的實(shí)驗(yàn)條件下對(duì)多種方法進(jìn)行對(duì)比分析。

6.1融合結(jié)果的相似性

采用Euclid相似度函數(shù)[17]對(duì)融合結(jié)果進(jìn)行相似度分析

本文采取蒙特卡洛仿真試驗(yàn)對(duì)比3種方法的融合結(jié)果。假設(shè)給定兩證據(jù)源，，對(duì)每個(gè)證據(jù)源的超冪集空間中的焦元進(jìn)行隨機(jī)的非零信度賦值。分別進(jìn)行1000次蒙特卡洛仿真實(shí)驗(yàn)，將每次實(shí)驗(yàn)隨機(jī)產(chǎn)生的一對(duì)證據(jù)，分別利用經(jīng)典方法、文獻(xiàn)[13]方法和本文方法得到融合結(jié)果，并計(jì)算與經(jīng)典方法融合結(jié)果的相似度，每次的實(shí)驗(yàn)結(jié)果如圖2及表1所示。(本文所有仿真實(shí)驗(yàn)是通過Pentimu(R) Dual-Core CPU E5300 2.6 GHz 2.59 GHz, 1.99 GB內(nèi)存的計(jì)算機(jī)進(jìn)行Matlab仿真實(shí)現(xiàn)的。)

圖2 超冪集空間焦元數(shù)目為20情況下的蒙特卡洛仿真實(shí)驗(yàn)相似度對(duì)比

表1融合結(jié)果對(duì)比分析表

經(jīng)過1000次蒙特卡羅仿真實(shí)驗(yàn)，本文方法與經(jīng)典方法融合結(jié)果的平均相似度略高于文獻(xiàn)[13]方法與經(jīng)典方法融合結(jié)果的平均相似度，且最低相似度在95%以上，說明了本文方法融合結(jié)果的高相似性。

6.2 融合方法的高效性

第5節(jié)已經(jīng)做過了計(jì)算復(fù)雜度的理論分析，但為了更直觀體現(xiàn)本文方法的高效性，通過表2中含有不同焦元數(shù)量的超冪集空間的兩個(gè)證據(jù)源融合算例，比較3種方法的運(yùn)算性能。

表2 3種方法在不同焦元數(shù)量的超冪集空間中運(yùn)算性能比較

從表2可知，本文方法加法運(yùn)算次數(shù)小于文獻(xiàn)[13]方法的1/3，乘法運(yùn)算次數(shù)小于文獻(xiàn)[13]方法的1/2，除運(yùn)算次數(shù)小于文獻(xiàn)[13]方法的1/4，其增加的焦元個(gè)數(shù)的減法運(yùn)算，由于減法運(yùn)算量極小，對(duì)運(yùn)算復(fù)雜度影響很小，本文算法計(jì)算復(fù)雜度相比于其他方法極小。

6.3沖突敏感性

為了驗(yàn)證本文方法可以有效融合沖突證據(jù)源信息，這里假設(shè)兩個(gè)沖突證據(jù)源的超冪集空間為，其上的信度賦值如表3所示。

表3兩沖突證據(jù)源信度賦值算例

圖3 文獻(xiàn)[13]方法與經(jīng)典方法對(duì)沖突證據(jù)信息融合結(jié)果的相似度

圖4 本文方法與經(jīng)典方法對(duì)沖突證據(jù)信息融合結(jié)果的相似度

6.4 魯棒性

分析可知，同時(shí)改變焦元的賦值順序不會(huì)影響經(jīng)典方法的融合結(jié)果，因?yàn)榻?jīng)典方法是通過各單子焦元與其余各焦元的信度運(yùn)算求得融合結(jié)果的，而本文方法是通過各單子焦元與其補(bǔ)集焦元的信度運(yùn)算求得融合結(jié)果的，其融合結(jié)果也不隨著焦元賦值順序的改變而改變，隨機(jī)給出如表4所示的3個(gè)證據(jù)源情況的各單子焦元的信度賦值，其焦元次序和信度賦值次序同時(shí)變化時(shí)，本文仿真的融合結(jié)果不發(fā)生變化，且其與經(jīng)典方法的相似度為0.9610，證明了本文方法具有很強(qiáng)的魯棒性。

表4多證據(jù)源情況的融合結(jié)果比較

7 結(jié)束語

DSmT作為一種新的解決高沖突信息融合處理問題的有效方法，已經(jīng)在多個(gè)領(lǐng)域得到了廣泛的應(yīng)用，但是隨著其鑒別框架焦元數(shù)目的增多導(dǎo)致其融合結(jié)果的計(jì)算呈組合爆炸的固有瓶頸一直無法突破，對(duì)該問題的解決不僅有著重要的理論價(jià)值，更有著巨大的應(yīng)用價(jià)值?；诖耍疚难芯坎⑻岢隽艘环N快速DSmT-DS近似推理融合方法，相比已有的近似推理方法，本文方法在保證了融合結(jié)果準(zhǔn)確率的前提下，計(jì)算復(fù)雜度極小，計(jì)算效率顯著提高，有效地解決了DSmT的計(jì)算瓶頸問題。

本文進(jìn)行的DSmT近似算法的研究是建立在超冪集空間中交多子焦元為0的情況下，對(duì)超冪集空間存在交多子焦元信度賦值的復(fù)雜情況尚未進(jìn)行深入研究。在實(shí)際應(yīng)用中的融合信息高沖突背景下，即使在DS模型下，Dempster組合規(guī)則容易產(chǎn)生悖論無法得到較好的結(jié)果而使用DSmT+PCR5進(jìn)行融合可以得到更符合實(shí)際的結(jié)果[5]，在這種情況下，本文方法可以有效取代DSmT+PCR5。接下來，還要做兩方面的研究，一是如何在盡量不提高方法計(jì)算復(fù)雜度的前提下，進(jìn)一步提高近似算法的精度；二是研究在超冪集空間中存在多子焦元的情況下，如何有效進(jìn)行DSmT融合推理計(jì)算。

參考文獻(xiàn)

[1] 史亞, 姬紅兵, 朱明哲, 等. 多核融合框架下的雷達(dá)輻射源個(gè)體識(shí)別[J]. 電子與信息學(xué)報(bào), 2014, 36(10): 2484-2490.

Shi Ya, Ji Hong-bing, Zhu Ming-zhe,.. Specific radar emitter identification in multiple kernel fusion framework [J].&, 2014, 36(10): 2484-2490.

[2] 李程, 王偉, 施龍飛, 等. 基于多源信息融合的有源雷達(dá)組網(wǎng)方式序貫識(shí)別方法[J]. 電子與信息學(xué)報(bào), 2014, 36(10): 2456-2463.

Li Cheng, Wang Wei, Shi Long-fei,.. Sequential method for netting type recognition of active radars based on multi-source information fusion [J].&, 2014, 36(10): 2456-2463.

[3] 楊露, 沈懷榮, 周偉靜, 等. 基于信息融合的故障診斷集成平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)[J]. 系統(tǒng)仿真學(xué)報(bào), 2014, 26(1): 132-136.

Yang Lu, Shen Huai-rong, Zhou Wei-jing,.. Design and realization of fault diagnosis platform based on information fusion[J]., 2014, 26(1): 132-136.

[4] 李嘉菲, 周斌, 劉大有, 等. 海量信息融合方法及其在狀態(tài)評(píng)價(jià)中的應(yīng)用[J]. 軟件學(xué)報(bào), 2014, 25(9): 2026-2036.

Li Jia-fei, Zhou Bin, Liu Da-you,.. Massive information fusion algorithm and its application in status evaluation[J]., 2014, 25(9): 2026-2036.

[5] Smarandache F and Dezert J. Advances and Applications of DSmT for Information Fusion: Vol 3[M]. USA: American Research Press, 2009: 54-58.

[6] Li X, Dezert J, Smarandache F,.. Combination of qualitative information with 2-Tuple Linguistic Representation in DSmT[J]., 2009, 24(4): 786-798.

[7] Li X, Dai X, Dezert J,.. Fusion of imprecise qualitative information[J]., 2010, 33(3): 340-351.

[8] Li X, Huang X, Dezert J,.. A successful application of DSmT in sonar grid map building and comparison with DST-based approach[J]., 2007, 3(3): 539-551.

[9] 李新德, 黃心漢, 戴先中, 等. 基于DSmT融合機(jī)的移動(dòng)機(jī)器人環(huán)境感知研究[J]. 華中科技大學(xué)學(xué)報(bào), 2009, 37(12): 64-67.

Li Xin-de, Huang Xin-han, Dai Xian-zhong,.. Study on environment perception of mobile robots using DSmT-based fusion machine[J]., 2009, 37(12): 64-67.

[10] 辛玉林, 鄒江威, 徐世友, 等. DSmT理論在綜合敵我識(shí)別中的應(yīng)用[J]. 系統(tǒng)工程與電子技術(shù), 2010, 32(11): 2385-2388.

Xin Yu-lin, Zou Jiang-wei, Xu Shi-you,.. Application of DSmT in integrated identification of friend-or-foe[J]., 2010, 32(11): 2385-2388.

[11] 覃東升, 苗壯, 王勇. 改進(jìn)的DSmT算法及其在C4ISR系統(tǒng)中的應(yīng)用[J]. 電子科技大學(xué)學(xué)報(bào), 2014, 43(4): 592-595.

Qin Dong-sheng, Miao Zhuang, and Wang Yong. Improved method based on DSmT and its application in C4ISR system[J]., 2014, 43(4): 592-595.

[12] 李新德, 潘錦東, Jean D. 一種基于DSmT和HMM的序列飛機(jī)目標(biāo)識(shí)別算法[J]. 自動(dòng)化學(xué)報(bào), 2014, 40(12): 2862-2876.

Li Xin-de, Pan Jin-dong, and Jean D. A target recognition algorithm for sequential aircraft based on DSmT and HMM[J]., 2014, 40(12): 2862-2876.

[13] 李新德, Jean D, 黃心漢, 等. 一種快速分層遞階DSmT 近似推理融合方法(A)[J]. 電子學(xué)報(bào), 2010, 38(11): 2566-2572.

Li Xin-de, Jean D, Huang Xin-han,.. A fast approximate reasoning method in hierarchical DSmT(A)[J]., 2010, 38(11): 2566-2572.

[14] 李新德, 楊偉東, 吳雪建, 等. 一種快速分層遞階DSmT 近似推理融合方法(B)[J]. 電子學(xué)報(bào), 2011, 39(3A): 31-36.

Li Xin-de, Yang Wei-dong, Wu Xue-jian,.. A fast approximate reasoning method in hierarchical DSmT(B)[J]., 2011, 39(3A): 31-36.

[15] 鄧勇, 王棟, 李齊, 等. 一種新的證據(jù)沖突分析方法[J]. 控制理論與應(yīng)用, 2011, 28(6): 839-844.

Deng Yong, Wang Dong, Li Qi,.. A new method to analyze evidence conflict[J].&2011, 28(6): 839-844.

[16] 蔣雯, 彭進(jìn)業(yè), 鄧勇. 一種新的證據(jù)沖突表示方法[J]. 系統(tǒng)工程與電子技術(shù), 2010, 32(3): 562-565.

Jiang Wen, Peng Jin-ye, and Deng Yong. New representation method of evidential conflict[J]., 2010, 32(3): 562-565.

[17] Li X, Jean D, Smarandache F,.. Evidence supporting measure of similarity for reducing the complexity in information fusion[J]., 2011, 181(10): 1818-1835.

Fast DSmT-DS Approximate Reasoning Method

Guo Qiang①He You①Li Xin-de②

①(,,264001,)②(,,210096,)

In this paper, Dempster-Shafer (DS) theory and Dezert-Smarandache Theory (DSmT) are conducted thorough reasearch, and in order to obtain more accurate fusion results in the premise of needing less computation complexity, a fast DSmT-DS approximate reasoning method is proposed. This method is only fit for the case that there are only singleton focal elements with assignments in hyper-power set. The hyper-power set is splitted and mapped to a new hyper-power set which consists of the binary sets of the focal element and its complementary set to the assignments of the complementary sets are computed. Proportional Conflict Redistribution No.5 within Dezert-Smarandache framework (DSmT+PCR5) is applied to fuse the multi-source evidence in the binary sets of the new hyper-power set to get the fusion results of singleton focal elements. Then the assignments of singleton focal elements are obtained by normalization. Through the theoretical analysis, the conclusion is drawn that the fusion results of the mothod in this paper is between the results of DSmT+PCR5 and Dempster’s combination rule based on DS model, and the fusion results of the method in this paper which is better than the rusults of Dempster’s combination rule can be obtained in the premise of minimal computation complexity. Finally, by comparing the method in this paper with the existing methods from different views, the superiority of new one is testified well.

Information fusion; Evidence theory; Dezert-Smarandache Theory (DSmT); Approximate reasoning; Splitting mapping

TP391

A

1009-5896(2015)09-2040-07

10.11999/JEIT150086

郭強(qiáng) gq19860209@163.com

2015-01-15收到，2015-03-27改回，2015-06-29網(wǎng)絡(luò)優(yōu)先出版

國家自然科學(xué)基金(61102166, 61471379)和山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金(BS2013DX003)資助課題

郭 強(qiáng)： 男，1986年生，講師，研究方向?yàn)樾畔⑷诤?、輻射源識(shí)別、態(tài)勢(shì)評(píng)估、DSmT、證據(jù)網(wǎng)絡(luò)等.

何 友： 男，1956年生，教授，中國工程院院士，研究方向?yàn)樾畔⑷诤系?

李新德： 男，1975年生，副教授，研究方向?yàn)镈SmT、信息融合、自動(dòng)導(dǎo)航、多傳感器多目標(biāo)跟蹤、目標(biāo)自動(dòng)識(shí)別等.