李文藝， 呂現(xiàn)釗， 郝保明

(宿州學(xué)院 機(jī)械與電子工程學(xué)院,安徽 宿州 234000)

Dempster合成規(guī)則的等效計(jì)算方法及其實(shí)現(xiàn)

李文藝， 呂現(xiàn)釗， 郝保明

(宿州學(xué)院 機(jī)械與電子工程學(xué)院,安徽 宿州 234000)

摘要：給出了Dempster合成規(guī)則的一種等效計(jì)算方法，該方法能夠由非歸一化的合成結(jié)果直接計(jì)算出最終的合成結(jié)果，同時(shí)在整個(gè)合成的過(guò)程中避開了沖突系數(shù)的計(jì)算.針對(duì)該方法給出了一種簡(jiǎn)單的實(shí)現(xiàn)途徑，首先利用二進(jìn)制編碼數(shù)據(jù)表示辨識(shí)框架冪集中的元素；然后把Dempster合成規(guī)則中集合的運(yùn)算轉(zhuǎn)化為二進(jìn)制編碼數(shù)據(jù)之間的邏輯運(yùn)算；最后通過(guò)算例進(jìn)行了驗(yàn)證，結(jié)果表明該方法與Dempster合成規(guī)則得到的結(jié)果完全相同.

關(guān)鍵詞：證據(jù)理論；等效算法；二進(jìn)制編碼；沖突系數(shù)

證據(jù)理論源于上世紀(jì)60～70年代，該理論是由Dempster首先提出，后來(lái)由他的學(xué)生Shafter進(jìn)行了完善和發(fā)展，所以證據(jù)理論又稱為D-S證據(jù)理論[1,2].由于證據(jù)理論可以很好的表示客觀世界中的信息，并能夠區(qū)分命題的“不確定”與“不知道”之間的關(guān)系，該理論已經(jīng)是模式識(shí)別、信息融合等領(lǐng)域的重要方法[3-5].證據(jù)理論的核心是Dempster合成規(guī)則，該規(guī)則可以把不同的證據(jù)進(jìn)行合成，從已有的證據(jù)生成新的證據(jù).在一般情況下利用Dempster合成規(guī)則可以使正確信息逐步聚集，從而合成結(jié)果有利于進(jìn)行最終的判斷與決策.但是在使用Dempster合成規(guī)則進(jìn)行多個(gè)證據(jù)融合時(shí)，計(jì)算量會(huì)隨證據(jù)個(gè)數(shù)的增加而急劇增大；在進(jìn)行多個(gè)證據(jù)的融合過(guò)程中，計(jì)算信任函數(shù)與沖突系數(shù)時(shí)要進(jìn)行集合之間的“交”運(yùn)算，而大量集合之間的“交”、“包含”運(yùn)算會(huì)耗費(fèi)較多的計(jì)算時(shí)間.以上這些因素都影響到了證據(jù)理論的應(yīng)用[6].

針對(duì)證據(jù)理論計(jì)算量大的問題，本文給出了Dempster合成規(guī)則的一種等效計(jì)算方法，與經(jīng)典的Dempster合成方法相比本文所給出的方法計(jì)算量較小、易于計(jì)算機(jī)實(shí)現(xiàn).該方法利用二進(jìn)制編碼表示辨識(shí)框架冪集中的元素；由此可以把證據(jù)理論中集合之間的“交”運(yùn)算轉(zhuǎn)換成了二進(jìn)制編碼之間的“與”邏輯運(yùn)算.然后利用Dempster等效合成公式計(jì)算最終的融合結(jié)果.對(duì)實(shí)驗(yàn)分析表明該方法的計(jì)算量有所減小，計(jì)算結(jié)果與Dempster方法完全一樣.

1證據(jù)理論

非空集合Θ由一些互斥且可窮舉的元素組成，稱Θ為辨識(shí)框架.集合Θ表示人們對(duì)某一問題所有可能結(jié)論(或所有可能假設(shè))的集合；從而，所需要解決的問題轉(zhuǎn)化為Θ的子集.

(1)

(2)

似真函數(shù)表示不反對(duì)命題的程度，似真函數(shù)的計(jì)算方法為

(3)

2Dempster合成規(guī)則的等效計(jì)算方法

假設(shè)m1,m2為辨識(shí)框架Θ下的兩個(gè)基本概率賦值函數(shù)，A1,A2,…,AN表示基本概率賦值函數(shù)m1的焦元；B1,B2,…,BM表示基本概率賦值函數(shù)m2的焦元.利用Dempster合成規(guī)則合成之后的基本概率賦值函數(shù)記為m；C1,C2,…,CK表示合成結(jié)果的焦元.

(4)

公式(4)中Cl≠Θ；i=1,2,…,N；j=1,2,…,M；l=1,2,…,K)，最終的融合結(jié)果可以按一下方法計(jì)算：

(5)

公式(5)中(l=1,2,…,K).下面證明該計(jì)算方法與經(jīng)典的Dempster合成規(guī)則是等價(jià)的.

證明

(6)

(7)

因此，得：

(8)

由證據(jù)理論的基本要求：

m(C1)+m(C2)+…+m(CK)=1.

(9)

(10)

(11)

所以：

(12)

因此，得到：

(13)

證畢.

由以上可知本文所給出的方法方法與Dempster合成規(guī)則是完全等效的，而不是一種近似的計(jì)算[7,8].

3等效計(jì)算的實(shí)現(xiàn)

利用Dempater合成規(guī)則需要判斷集合之間的關(guān)系是否滿足運(yùn)算條件.為了避免集合之間的運(yùn)算，本文給出了一種新的實(shí)現(xiàn)方法，該方法中利用二進(jìn)制編碼之間的“與”邏輯運(yùn)算代替集合之間的“交”運(yùn)算.本文的基本思想為：若辨識(shí)框架Θ中有N個(gè)元素，則Θ的冪集2Θ中最多有2N個(gè)元素，而一個(gè)N位的二進(jìn)制數(shù)最多可以表示2N種不同的組合.可以用N位的二進(jìn)制數(shù)據(jù)表示辨冪集中的2N個(gè)不同的元素.下面通過(guò)一個(gè)實(shí)例說(shuō)明本文方法的基本思想.

例：假設(shè)Θ={a,b,c}，Θ的冪集共有8個(gè)元素分別為Φ,{a},,{c},{ab},{bc},{ac},{abc}這8個(gè)元素分別用二進(jìn)制表示為：000,100,010,001,110,011,101,111.m1,m2表示辨識(shí)框架Θ下的兩個(gè)基本概率賦值函數(shù).使用二進(jìn)制編碼之后，使用Dempster合成方法進(jìn)行計(jì)算，合成結(jié)果可用已下方法計(jì)算：

當(dāng)辨識(shí)框架中的元素較多時(shí)，只需要增加二進(jìn)制編碼的位數(shù)即可.Dempster合成規(guī)則轉(zhuǎn)換為以下表達(dá)式：

(14)

針對(duì)上述例題，利用本文所給出的方法可按照已下方法進(jìn)行計(jì)算.

分別表示未歸一化之后的融合結(jié)果.則：

則最終的融合結(jié)果可表示為

通過(guò)分析知，在Dempster合成規(guī)則中原來(lái)集合的“交”運(yùn)算變成了邏輯“與”運(yùn)算.按照此方法式(4)可以表示為

(15)

用二進(jìn)制編碼的方法實(shí)現(xiàn)證據(jù)融合的步驟為

步驟1:對(duì)冪集中的每個(gè)元素進(jìn)行二進(jìn)制編碼.

步驟2:按式(14)計(jì)算出未歸一化的融合結(jié)果.

步驟3：按式(5)計(jì)算出最終融合結(jié)果.

4算例仿真

為了比較本方法與經(jīng)典的Dempster方法，下面通過(guò)一個(gè)具體的算例進(jìn)行仿真實(shí)驗(yàn).假設(shè)有6個(gè)不同的傳感器探測(cè)到了飛行器類型，分別用ABC表示,A=“戰(zhàn)斗機(jī)”，B=“轟炸機(jī)”，C=“武裝直升機(jī)”.從6個(gè)傳感器得到的基本概率分配函數(shù)分別為m1,m2,m3,m4,m5,m6，函數(shù)值如表1所示.

表1　基本概率分配函數(shù)值

利用本文方法與Dempster合成規(guī)則得到的結(jié)果是相同的，融合結(jié)果是：

m(A)=0.573 6,m(B)=0.350 8,m(C)=0.070 7,m(AB)=0.001 2,m(BC)=0.003 7.

本文所給出的方法用二進(jìn)制編碼表示了原來(lái)的集合，利用了二進(jìn)制之間的邏輯運(yùn)算代替了原來(lái)的集合之間的運(yùn)算.另外本文所給出的方法避免了沖突系數(shù)的計(jì)算，針對(duì)本算例來(lái)說(shuō)由于不用計(jì)算沖突系數(shù)，使得本文的計(jì)算量為經(jīng)典Dempster合成規(guī)則的約70%，計(jì)算量有所減少.

5結(jié)語(yǔ)

給出了Dempster合成規(guī)則的一種等效計(jì)算方法，該方法可以避免計(jì)算證據(jù)之間的沖突系數(shù)，而可以得到與原方法相同的結(jié)果，與原方法相比本文的計(jì)算量有所減少.同時(shí)，文中對(duì)所給出的方法進(jìn)行了證明.針對(duì)文中所提出方法的實(shí)現(xiàn)問題，文中利用二進(jìn)制的方法對(duì)辨識(shí)框架的冪集中的元素進(jìn)行編碼.然后利用邏輯運(yùn)算代替Dempster方法中集合之間的運(yùn)算.用二進(jìn)制編碼對(duì)辨識(shí)框架進(jìn)行重新表示之后，可以更加方便的利用計(jì)算機(jī)編程的方法實(shí)現(xiàn)多個(gè)證據(jù)的合成問題.仿真實(shí)驗(yàn)表明該方法可以較好的解決多證據(jù)的融合問題，并能夠得到與Dempster方法相同的融合結(jié)果.

參考文獻(xiàn)：

[1]Dempster A P. Upper and lower probabilities induced by a multi-valued mapping [J].Annuals of Mathematics Statistics, 1967,38(4):325-339.

[2]Shafer G. A Mathematical Theory of Evidence [M].Princeton: Princeton University press,1976.

[3]王鳳朝,劉興堂,黃樹采.基于模糊證據(jù)理論的多特征目標(biāo)融合檢測(cè)算法[J].光學(xué)學(xué)報(bào)，2010,30(3):713-719.

[4]張燕君,龍呈.基于證據(jù)理論的目標(biāo)識(shí)別方法[J]. 系統(tǒng)工程與電子技術(shù),2013,35(12):2467-2470.

[5]王峰. D-S證據(jù)理論在指紋圖像分割中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(24):169-172.

[6]陳圣群,王應(yīng)明.證據(jù)的分組合成法[J]. 控制與決策,2013:28(4):574-578.

[7]王壯,胡衛(wèi)東,郁文賢,等.基于截?cái)嘈虳-S的快速證據(jù)組合方法[J].電子與信息學(xué)報(bào),2002 ,24(12):1-3.

[8]李岳峰,劉大有.證據(jù)理論中的近似計(jì)算方法[J].吉林大學(xué)學(xué)報(bào),1995,31(l):28-32.

An Equivalent Algorithm of the Dempster Combination

Rule and Its Realization

LI Wen-yi, LV Xian-zhao, HAO Bao-ming

(SchoolofMechanicalandElectronicEngineering,SuzhouUniversity,Suzhou234000,China)

Abstract:An equivalent algorithm of the Dempster combination rule is presented in this paper. By this algorithm, the final result can be obtained from the un-normalized combination results, and the calculation of the conflict coefficient can be avoided at the same time. A realization approach of this method is further presented. Firstly, each element of the discernment frame is coded by the binary encoding, and then the computation of sets is transformed into logic computation of the binary encoding in the Dempster combination rule. At last, calculation examples are used to test this new method, and findings show that the results obtained are the same to those obtained by the Dempster combination rule.

Key words:evidence theory; identical algorithm; binary encoding; conflict coefficient

責(zé)任編輯：趙秋宇

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1671-9824(2015)02-0065-05

作者簡(jiǎn)介：李文藝(1980—),男,河南開封人，講師，碩士，研究方向：模式識(shí)別、信息融合.

基金項(xiàng)目：安徽省高等學(xué)校省級(jí)優(yōu)秀青年人才基金重點(diǎn)項(xiàng)目(2013SQRL084ZD)；宿州學(xué)院基金項(xiàng)目(2009yss08，2009yss07，szxyjyxm201307)

收稿日期：2014-05-27