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

郭 強 何 友 李新德

?

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

郭 強*①何 友①李新德②

①(海軍航空工程學院信息融合技術研究所 煙臺 264001)②(東南大學復雜工程測量與控制教育部重點實驗室 南京 210096)

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

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

1 引言

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

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

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

2 基本理論

2.1 DS框架下的Dempster組合規則

2.2 DSm框架下的PCR5融合規則

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

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

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

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

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

3.1超冪集空間拆分映射

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

由3.1節可知，映射生成的新超冪集空間的元素不是傳統意義上的單焦元或多焦元，而是由單焦元和它的補集構成的二元集合子空間，如其中的第個元素，也稱子空間，由單子焦元和其補集=構成，其補集的信度賦值為

3.3對新的超冪集空間的子空間進行DSmT+PCR5融合

對兩證據源在新的超冪集空間中對應的相同單子焦元和其補集的子空間進行DSmT+PCR5融合推理得到各單子焦元的信度賦值為

3.4 歸一化處理

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

4 分析快速DSmT-DS融合結果與DSmT+ PCR5及Dempster規則融合結果的關系

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

5 計算復雜度對比分析

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

6 仿真實驗結果對比分析

為了驗證本文方法的優越性，本文從融合結果的相似性、方法的高效性、沖突敏感性及魯棒性4個指標在相同的實驗條件下對多種方法進行對比分析。

6.1融合結果的相似性

采用Euclid相似度函數[17]對融合結果進行相似度分析

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

圖2 超冪集空間焦元數目為20情況下的蒙特卡洛仿真實驗相似度對比

表1融合結果對比分析表

經過1000次蒙特卡羅仿真實驗，本文方法與經典方法融合結果的平均相似度略高于文獻[13]方法與經典方法融合結果的平均相似度，且最低相似度在95%以上，說明了本文方法融合結果的高相似性。

6.2 融合方法的高效性

第5節已經做過了計算復雜度的理論分析，但為了更直觀體現本文方法的高效性，通過表2中含有不同焦元數量的超冪集空間的兩個證據源融合算例，比較3種方法的運算性能。

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

從表2可知，本文方法加法運算次數小于文獻[13]方法的1/3，乘法運算次數小于文獻[13]方法的1/2，除運算次數小于文獻[13]方法的1/4，其增加的焦元個數的減法運算，由于減法運算量極小，對運算復雜度影響很小，本文算法計算復雜度相比于其他方法極小。

6.3沖突敏感性

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

表3兩沖突證據源信度賦值算例

圖3 文獻[13]方法與經典方法對沖突證據信息融合結果的相似度

圖4 本文方法與經典方法對沖突證據信息融合結果的相似度

6.4 魯棒性

分析可知，同時改變焦元的賦值順序不會影響經典方法的融合結果，因為經典方法是通過各單子焦元與其余各焦元的信度運算求得融合結果的，而本文方法是通過各單子焦元與其補集焦元的信度運算求得融合結果的，其融合結果也不隨著焦元賦值順序的改變而改變，隨機給出如表4所示的3個證據源情況的各單子焦元的信度賦值，其焦元次序和信度賦值次序同時變化時，本文仿真的融合結果不發生變化，且其與經典方法的相似度為0.9610，證明了本文方法具有很強的魯棒性。

表4多證據源情況的融合結果比較

7 結束語

DSmT作為一種新的解決高沖突信息融合處理問題的有效方法，已經在多個領域得到了廣泛的應用，但是隨著其鑒別框架焦元數目的增多導致其融合結果的計算呈組合爆炸的固有瓶頸一直無法突破，對該問題的解決不僅有著重要的理論價值，更有著巨大的應用價值。基于此，本文研究并提出了一種快速DSmT-DS近似推理融合方法，相比已有的近似推理方法，本文方法在保證了融合結果準確率的前提下，計算復雜度極小，計算效率顯著提高，有效地解決了DSmT的計算瓶頸問題。

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

參考文獻

[1] 史亞, 姬紅兵, 朱明哲, 等. 多核融合框架下的雷達輻射源個體識別[J]. 電子與信息學報, 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] 李程, 王偉, 施龍飛, 等. 基于多源信息融合的有源雷達組網方式序貫識別方法[J]. 電子與信息學報, 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] 楊露, 沈懷榮, 周偉靜, 等. 基于信息融合的故障診斷集成平臺設計與實現[J]. 系統仿真學報, 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] 李嘉菲, 周斌, 劉大有, 等. 海量信息融合方法及其在狀態評價中的應用[J]. 軟件學報, 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]. 華中科技大學學報, 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理論在綜合敵我識別中的應用[J]. 系統工程與電子技術, 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] 覃東升, 苗壯, 王勇. 改進的DSmT算法及其在C4ISR系統中的應用[J]. 電子科技大學學報, 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]. 自動化學報, 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]. 電子學報, 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]. 電子學報, 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]. 控制理論與應用, 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]. 系統工程與電子技術, 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

郭強 gq19860209@163.com

2015-01-15收到，2015-03-27改回，2015-06-29網絡優先出版

國家自然科學基金(61102166, 61471379)和山東省優秀中青年科學家科研獎勵基金(BS2013DX003)資助課題

郭 強： 男，1986年生，講師，研究方向為信息融合、輻射源識別、態勢評估、DSmT、證據網絡等.

何 友： 男，1956年生，教授，中國工程院院士，研究方向為信息融合等.

李新德： 男，1975年生，副教授，研究方向為DSmT、信息融合、自動導航、多傳感器多目標跟蹤、目標自動識別等.