修正的DSmT證據編碼方法

李鴻飛，金宏斌，田康生，王 晶

（1.空軍預警學院四系，湖北武漢430019；2.北京云星宇科技服務有限公司，北京100078）

修正的DSmT證據編碼方法

李鴻飛1，金宏斌1，田康生1，王 晶2

（1.空軍預警學院四系，湖北武漢430019；2.北京云星宇科技服務有限公司，北京100078）

計算量是影響Dezert-Smarandache理論（DSmT）應用的重要因素之一，也一直是DSmT的研究熱點。計算編碼由于其證據表示和信度計算的合理性，得到了廣泛的認可。計算編碼在編碼轉換時簡單有效，但在解碼轉換時需要進行全部可能元素查找，需要大量查找計算，降低了計算編碼的執行效率。文章提出了一種修正的DSmT證據編碼方法，該方法將焦元關系轉換為唯一的位置屬性并事前存儲于數據庫中，減小了在解碼過程中的查找計算量，修正方法在不改變合成結果的前提下更加有效。算例也驗證了修正方法在合成結果上的正確性和計算量上的高效性。

Dezert-Smarandache理論；計算量分析；證據編碼；計算編碼；解碼變換

0 引 言

Dezert-Smarandache理論（DSmT）的計算量主要產生于證據的組合過程，由于DSmT引入沖突焦元的概念，使得DSmT的計算量比DST更大［1－4］。DSmT的證據處理過程的計算量問題涉及到3個問題，一是證據的近似；二是合成規則的近似；三是證據的表示（包括證據編碼和證據解碼）。針對3類問題，專家學者提出3類方法。第一類方法是焦元近似方法，通過對原始證據或焦元進行簡化來減小計算量，主要針對問題1，例如，Tessem的k-l-x方法［5］、基于能量函數法［6］、貝葉斯近似方法［7］、排序融合法［8］、層次比例近似方法［9］、證據控制方法［10－13］等。第二類方法是規則近似方法，針對具體應用可以將組合規則進行簡化，減少不必要的計算，主要針對問題2，例如，層次假設近似方法［14］、基于樹的近似方法［15－18］等。第三類方法是證據編碼方法，通過使編碼蘊含邏輯關系，使用編碼可以有效處理焦元間并節省查找計算量，主要針對問題3，如Smarandache編碼［19］、計算編碼［20］。

3類方法序貫執行，可以從不同的角度減小計算量。如上節分析，目前計算量的分析主要集中于證據近似和合成規則近似，對證據編碼方法的研究較少。但證據編碼方法是DSmT方法可以進行計算機編程的基礎，其作為證據表示的方式嵌入整個證據合成流程，在完成計算機編程的同時控制了不必要的計算量。目前，最有效的方法是文獻［20］提出的計算編碼。計算編碼在編碼轉換時簡單有效，但在解碼轉換時需要進行全部可能元素查找，需要大量的查找計算，降低了計算編碼的執行效率。針對計算編碼在解碼變換時存在的問題，本文提出一種修正的計算編碼方法。該方法分為事前處理部分和實時處理部分，將元素的位置屬性與計算編碼事先對應于數據庫中，實時處理時只需定位合成結果的位置碼，即可得到合成結果的字符編碼顯示輸出。本方法在不影響計算編碼合成有效性及編碼變換簡易性的同時，使得解碼變換簡化，提高了編碼方法的效率。

1 證據編碼方法

1.1 現有的證據編碼方法

原始的證據通過字符表示，如目標1表示成θ1，目標1或目標2表示成θ1∪θ2，這種證據焦元的原始表示方法稱為字符編碼。字符編碼易于理解，但不同焦元間的蘊含關系需要用戶參與處理，這極大地阻礙了DSmT在計算機系統中的應用。同時字符編碼每次處理需查找相應焦元及其對應的基本信度值，增加了計算量。為此，專家提出了表示編碼、Smarandache編碼以及計算編碼，試圖解決字符編碼的存在問題。最直觀的方法是對字符編碼進行數字化，使其便于計算機處理。表示編碼就是把字符編碼都通過數字表示。表示編碼初始數字化字符編碼，但焦元間的邏輯關系還沒有蘊含在編碼中。同時考慮數字化和焦元邏輯，根據對焦元邏輯的不同處理方式，有文獻［19］提出的Smarandache編碼方法和文獻［20］提出了計算編碼。維恩圖以圖的形式表示了命題間的邏輯關系。圖1（a）和圖1（b）分別表示了辨識框架元素數n＝3時，命題的維恩圖及其對應的Smarandache編碼和計算編碼。計算編碼在Smarandache編碼的基礎上將維恩圖分離部分以單個數字表示，比Smarandache編碼的數字組合表示更為簡單有效。

圖1 命題的維恩圖及其對應的兩種編碼（n＝3）

不同的證據編碼有不同的特點，其特點又決定了其計算量和適用范圍。4種證據編碼在表1中進行了分析。

表1 證據編碼的特點分析

1.2 計算編碼存在問題

計算編碼由于將焦元關系內含于編碼中，可以有效降低證據焦元組合以及證據查找的計算量，并且易于編程實現，是一種有效的表示方法。其信息流程如圖2所示。

圖2 基于計算編程證據合成的信息流程

計算編碼在編碼和證據組合上簡單有效，但在解碼過程中，由于合成結果焦元不一定包含在原始證據焦元中，為了得到合成結果的字符編碼，需要將合成結果的計算編碼逐個與各元素的計算編碼進行比較，且DSmT元素包含辨識框架的所有超冪集元素，在極端情況下解碼所需的查找計算量甚至會超過證據合成所需的計算量。如假設證據有n個焦元，需要查找的焦元數量為m，則需要查找的計算量以平均查找次數表示，記為O查找（f（n，m））。若每個焦元擁有相同的查找概率，且查找成功和查找失敗的概率相同，計算編碼的查找計算量

例1 假設｜Θ｜＝4，原始證據焦元數分別為11和12，合成結果焦元數為51，則合成計算量為197.5，解碼計算量達到3／4×（167＋1）×51＝6 426。

2 修正的計算編碼方法

2.1 算法模型

計算編碼雖然能有效完成證據的表示，但其在解碼過程中的查找產生的計算量降低了其使用效率。在研究中發現，可以將計算編碼中的焦元關系轉換為某種代碼，以減少查找的計算量。在計算編碼的基礎上對計算編碼給出唯一的標識，使其增加新的標識屬性便于查找。在不改變計算編碼結構的基礎上，將計算編碼的唯一性信息作為新標識在數據庫中與計算編碼對應。將需要程序實時進行的操作，提前置于數據庫中，相當于將查找操作事前進行?；谠撍枷?，本文提出了一種修正計算編碼方法，修正方法的證據處理過程如圖3所示。非辨識框架元素中的操作符（與操作、或操作）數為ak（k＝1，…，n－｜Θ｜，ak＝w，w是正整數），則編碼計算量為

圖3 修正方法的信息流程

修正計算編碼方法的處理過程分為3個步驟進行。下面對這3個步驟進行分析，并給出了3個步驟中產生的計算量。

步驟1 證據編碼。證據編碼分為首先查找相應辨識框架的完整計算編碼，然后從輸入證據的字符代碼開始，到轉換為表示編碼，再轉換為計算編碼。其中證據的字符編碼中單焦元的個數決定了在轉換過程中所需的查找次數。例如，需要對θ1∩θ2進行證據編碼，需要查找θ1和θ2的相應辨識框架的完整計算編碼，然后再按照第2.1節的方法得到具體的證據編碼。計算量為查找次數2。證據的字符編碼在其集合的最簡形式下，其交、并集的次數永遠比單焦元次數多1。在不同的辨識框架下，單焦元的定義和表示不同，但交、并集的表示是一致的，因此本文以交、并集的次數來衡量編碼計算量。但編碼計算量的實質是查找的次數。

定義1 假設在DSm模型下，有l維辨識框架Θ＝｛θ1，θ2，…，θl｝，證據有n個焦元，其中辨識框架元素個數為｜Θ｜，

步驟2 焦元組合與信度計算。首先根據應用確定組合規則，計算焦元相交情況并進行去重，同時計算相交的基本信度值，得到合成結果。由于邏輯關系蘊含于計算編碼內，合成結果的計算編碼可直接組合得到，所以不考慮焦元組合計算量。在信度組合方面，證據合成可以看作乘運算（除運算）和加（減運算）兩種原子操作組成。兩種操作根據不同的算法產生的計算量不同，乘運算的計算量大于加運算的計算量，本文將兩種操作次數加權處理得到信度組合計算量。

定義2 在DSm模型下，有n維辨識框架Θ＝｛θ1，θ2，…，θn｝，根據相應限制條件，最大可能焦元集為GΘ（GΘ表示可為不同模型），則焦元數為｜GΘ｜，對k條證據mj（Ajl）（j＝1，2，…，k；l＝1，2，…，｜GΘ｜；Ajl?Θ），用某種組合規則組合這k條證據所需要運算的乘法和除法的次數與加法次數的加權和稱為該組合規則的信度組合計算量，表示為O組合（f（n，k））。

步驟3 證據解碼。合成結果進行解碼，得到字符編碼表示的合成結果并顯示給用戶。修正的DSmT證據編碼方法保持了計算編碼在證據組合時優良性質，并對解碼部分進行了改進，分為事先處理部分和實時處理部分（見圖4）。事先處理部分即在系統設計時就將位置碼加入編碼數據庫，這樣在實時處理部分對合成結果的計算編碼進行解碼時，可直接通過其位置碼獲取合成結果的字符編碼，不必進行大量的查找。這樣將原來在實時處理部分進行的查找可以看做在事前進行。

圖4 修正編碼方法的事前處理和實時處理過程

事先處理部分首先生成不同辨識框架下所有元素的計算編碼；判斷編碼數據庫中該計算編碼是否有對應的位置碼，若有，則判斷下一個計算編碼，若無，繼續運行；將計算編碼的每個數字轉換成為二進制碼，若計算編碼存在數字a，則將二進制碼的第a位設置為1，其余為0，m等于最大編碼數，一個計算編碼對應一個m位二進制碼；將二進制碼轉換為十進制，得到唯一的位置碼，并與該計算編碼對應；對所有未轉換計算編碼循環進行第二步到第五步，至所有元素都已完成轉換。

實時處理部分與事前處理部分原理類似，但在步驟上稍有不同。實時處理部分得到組合結果首先得到其計算編碼的位置碼，直接在數據庫中查找位置碼獲取對應的字符編碼。首先得到合成結果的焦元計算編碼；將計算編碼轉換為二進制碼；將二進制碼轉換為十進制，得到位置碼；在編碼數據庫中定位位置碼，得到字符編碼；字符編碼與其基本信度組裝，輸出顯示。

下面用一個例子，說明修正方法的解碼過程。

例2 假設辨識框架n＝3，則其最大編碼數為7，得到的合成結果計算編碼為［1 2 3 5］、［1 3］、［1］，其對應的基本信度值分別為0.675 4、0.297 5和0.027 1，解碼過程如圖5所示。

圖5 一個修正編碼方法的解碼過程舉例圖

修正方法的解碼計算量是在證據由計算編碼轉換為字符編碼過程中產生的計算量，主要為轉換為位置碼產生的計算量，即得到位置碼后即查找相應字符編碼的次數。

定義3 假設組合結果有n個焦元，則解碼計算量為O解碼（f（n））＝n。

2.2 總計算量的分析與比較

計算編碼和修正方法的計算量都由組合計算量、編碼計算量和解碼計算量組合。但如果將總計算量表示為3種計算量的簡單加和是不合理的。這是因為組合計算量是組合過程中乘法與加法運算的加權和，而編碼計算量和解碼計算量都是查找次數。組合計算量是一類計算量，編碼計算量和解碼計算量是一類計算量。為此，以二元組的形式分別表示兩類計算量。

定義4 設在證據處理過程中，其組合計算量、編碼計算量和解碼計算量組合分別為O組合、O編碼和O解碼，則證據處理過程中產生的總計算量為O總＝［O組合，O編碼＋O解碼］。

根據第1節、2.1節及本節對計算量的定義，對兩種方法的計算量進行定量分析。

假設有兩條證據E1和E2，D為所代表的模型，辨識框架元素數為｜Θ｜，其焦元數分別為n1和n2，非辨識框架元素中的操作符數為和，組合結果焦元數為r。則計算編碼方法和修正編碼方法的計算量如表2所示。使用經典DSm組合規則對兩條證據進行融合。兩條證據的經典DSm組合其信度組合計算量為乘除操作與加操作的加權和，即n1×n2＋α（n1×n2－1），α為加操作權系數。

表2 計算編碼與修正方法計算量比較

3 算例分析

不同類的減小計算量方法在證據處理中的應用位置不同且可以序貫使用，因此只有同類的方法比較有實際意義。仿真通過對證據編碼方法中的計算編碼和修正方法進行比較，驗證修正計算編碼方法的有效性。

仿真背景：在自由DSm模型下，辨識框架為Θ＝｛D，Z，Y，Q｝，假設在某時刻從傳感器獲得兩組證據E1、E2，其基本信度分配值m1、m2，如表3所示。兩條證據都認為是元素D。使用經典DSm組合規則對兩條證據進行融合。信度組合計算量度量中α取值為0.5。

主要對兩種方法的計算量和合成結果進行計算和評價。表4、表5比較了兩種方法的合成結果和計算量。

兩種編碼的組合結果見表4。從表4中可以看出，兩種方法的決策結果為D，與直覺結果一致，兩種編碼在組合時一致，均可以有效識別。

表3 某時刻的基本信度分配值

表4 兩種編碼的合成結果比較

表5 兩種編碼的計算量比較

兩種編碼的計算量見表5。從表5中可以看出，修正計算編碼方法的計算量明顯小于計算編碼，其中兩種方法的組合計算量和編碼計算量均相等，主要差別在于解碼計算量。修正計算編碼方法將計算編碼需要查找才能完成的功能以位置碼的形式內化于數據庫中，不再需要對合成結果進行反復查找。修正計算編碼方法可以看做是以“數據換程序”的思路進行的。修正計算編碼方法既保持了計算編碼在證據組合時的有效性和計算機編程的易用性，又深入挖掘計算編碼的內在特性，使其更加合理高效。

4 結束語

本文提出了一種新的DSmT證據編碼方法，該方法基于計算編碼，將位置屬性加入計算編碼中，解決了計算編碼在解碼變換時計算量大的問題。修正方法的解碼部分分為事前處理部分和實時處理部分，將元素的位置屬性與計算編碼事先對應于數據庫中，實時處理時只需定位合成結果的位置碼即可得到合成結果的字符編碼顯示輸出。算例也驗證了修正方法在合成結果上的正確性和計算量上的高效性。下一步，本課題組將繼續研究編碼的存儲結構，以方便編碼的查找、排序、修改，進一步提高處理效率。

［1］Destercke S，Burger T.Toward an axiomatic definition of con-flict between belief functions［J］.IEEE Trans.on Systems，Man and Cybernetics，Part B，2013，13（2）：585－596.

［2］Fu Y W，Yang W，Zhuang Z W.Review on evidence modeling［J］.Systems Engineering and Electronics，2013，35（6）：1160－1167.（付耀文，楊威，莊釗文.證據建模綜述［J］.系統工程與電子技術，2013，35（6）：1160－1167.）

［3］Dezert J.An introduction to DSmT for information fusion［J］.New mathematics and Natural Computation，2012，8（3）：343－359.

［4］Smarandache F，Dezert J.On the consistency of PCR6with the averaging rule and its application to probability estimation［C］∥Proc.of the 16th International Conference on Information Fusion，2013：1119－1126.

［5］Tessem B.Approximations for efficient computation in the theory of evidence［J］.Artificial Intelligence，1993，61（2）：315－329.

［6］Ye Q，Wu X P，Zhai D J.Combination algorithm for evidence theory utilizing energy function［J］.Systems Engineering and Electronics，2010，32（3）：566－569.（葉清，吳曉平，翟定軍.一種基于能量函數的證據合成算法［J］.系統工程與電子技術，2010，32（3）：566－569.）

［7］Voorbraak F.A computationally efficient approximation of Dempster-Shafer theory［J］.International Journal of Man-Machine Studies，1989，30：525－536.

［8］Yang Y，Han D Q，Han C Z，et al.A novel approximation of basic probability assignment based on rank-level fusion［J］.Chinese Journal Aeronautics，2013，26（4）：993－999.

［9］Dezert J，Han D Q，Liu Z G，et al.Hierarchical proportional redistribution principle for uncertainty reduction and BBA approximation［J］.Belief Functions：Theory and Applications，2012：275－283.

［10］Li X D，Dezert J，Smarandache F，et al.Evidence supporting measure of similarity for reducing the complexity in information fusion［J］.Information Sciences，2011，181（10）：1818－1835.

［11］Liu Z G，Pan Q，Dezert J.A new belief-based K-nearest neighbor classification method［J］.Pattern Recognition，2013，46（3）：834－844.

［12］Yang Y，Han D Q，Han C Z.Discounted combination of unreliable evidence using degree of disagreement［J］.International Journal of Approximate Reasoning，2013，54：1197－1216.

［13］Peng Y，Hu Z H，Shen H R.A modified distance of evidence［J］.Journal of Electronics ＆Information Technology，2013，35（7）：1624－1629.（彭穎，胡增輝，沈懷榮.一種修正證據距離［J］.電子與信息學報，2013，35（7）：1624－1629.）

［14］Gordon J，Edward H，Shortliffe.A method for managing evidential reasoning in a hierarchical hypothesis space［J］.Artificial Intelligence，1985，26（3）：323－357.

［15］Li X D，Dezert J，Huang X H，et.al.A fast approximate reasoning method in hierarchical DSmT（A）［J］.Acta Electronica Sinica，2010，38（11）：2566－2572.（李新德，Dezert J，黃心漢，等.一種快速分層遞階DSmT近似推理融合方法（A）［J］.電子學報，2010，38（11）：2566－2572.）

［16］Li X D，Wu X J，Sun J M，et al.An approximate reasoning method in Dezert-Smarandache Theory［J］.Journal of Electronics，2009，26（6）：738－745.

［17］Li X D，Yang W D，Wu X J，et al.A fast approximate reasoning method in hierarchical DSmT（B）［J］.Acta Electronica Sinica，2011，39（A03）：31－36.（李新德，楊偉東，吳雪建，等.一種快速分層遞階DSmT近似推理融合方法（B）［J］.電子學報，2011，39（A03）：31－36.）

［18］Li X D，Yang W D，Dezert J，et al.A fast approximate reasoning method in hierarchical DSmT（C）［J］.Journal of Huazhong University of Science and Technology（Natural Science Edition），2011，39（S2）：150－156.（李新德，楊偉東，Dezert J，等.一種快速分層遞階DSmT近似推理融合方法（C）［J］.華中科技大學學報（自然科學版），2011，39（S2）：150－156.）

［19］Dezert J，Smarandache F.Partial ordering on hyper-power sets［A］∥Dezert J，Smarandache F.Advances and applications of DSmT for information fusion（Collected Works Vol.I）.Rehoboth：American Research Press，2004.

［20］Martin A.Implementing general belief function framework with a practical codification for low complexity［A］∥Dezert J， Smarandache F.Advances and applications of DSmT for information fusion（Collected Works Vol.III）.Rehoboth：American Research Press，2009.

Modified evidence coding method based on Dezert-Smarandache theory

LI Hong-fei1，JIN Hong-bin1，TIAN Kang-sheng1，WANG Jing2
（1.The 4th Department，Air Force Early Warning Academy，Wuhan 430019，China；2.Beijing Yunxingyu Technology Service Co.，Ltd，Beijing 100078，China）

The calculation is one of the important issues which affect the application of the Dezert-Smarandache theory（DSmT）.The research of the calculation is a hotspot in the area of the DSmT.The calculation code is widely recognized for the reasonability of evidence expression and belief computation.The calculation code is simple and effective in the coding process.But all possible elements should be searched in the decoding process which causes large calculation amount to reduce the efficiency of calculation code.To solve the problem，a modified evidence coding method is presented.In the modified method，the exclusive position attribution based on the focal element relationship is added to reduce the large calculation amount in the decoding process.The exclusive position attribution is generated and stored in the database before evidence processing.The simulation example verifies the validity of the combination result and the high efficiency in the calculation.

Dezert-Smarandache theory（DSmT）；evidence code；calculation analysis；calculation code；decoding transform

TP 14

A

10.3969／j.issn.1001-506X.2015.08.31

李鴻飛（1984－），男，博士研究生，主要研究方向為不確定性推理理論及其軍事應用。

E-mail：kjld＿lhf＠163.com

金宏斌（1976－），男，副教授，博士，主要研究方向為數據融合、目標識別。

E-mail：jhbo817＠tom.com

田康生（1964－），男，教授，博士研究生導師，主要研究方向為軍事信息系統、效能評估。

E-mail：tiankangsheng＠tom.com

王 晶（1981－），女，工程師，碩士，主要研究方向為計算機應用。

E-mail：wabmwj007＠163.com

1001－506X201508－1922－06

網址：www.sys－ele.com

2014－07－29；

2014－11－08；網絡優先出版日期：2015－01－04。

網絡優先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150104.1720.010.html

國家自然科學基金（61102168）；軍事創新基金（X11QN106）資助課題