一種高度沖突證據混合分步合成算法

陳 強，黃丹丹，李 彬，盧 愿

（江西理工大學電氣工程與自動化學院，江西 贛州341000）

ment，BPA），亦稱基本信任分配。如果m（A）＞0，則稱A為焦元。對于相互獨立的2個證據源 m1（*），m2（*），提供了如下經典合成公式：

一種高度沖突證據混合分步合成算法

陳 強，黃丹丹，李 彬，盧 愿

（江西理工大學電氣工程與自動化學院，江西 贛州341000）

為證實證據分步合成方法在理論上的合理性，給出多證據分步合成結果的一般表達式，對分步合成方法理論上的合理性、合成結果的收斂性以及最終合成結果與證據行順序之間的相關性進行研究。提出相關的定理和推論，并進行數學證明。針對高度沖突證據的分步合成問題，設計一種合成公式與加權平均法混合使用的分步合成算法。仿真結果表明，該算法的合成計算過程更為簡潔，合成結果的收斂效果更好。

D-S證據合成；分步合成算法；收斂性；高度沖突證據；加權平均法

DO I：10.3969/j.issn.1000-3428.2015.10.057

1 概述

通常使用經典D-S證據合成公式合成2個高度沖突證據時，會得到有違常理的結果［1-2］。文獻［3］提出一個著名的反例揭示這一問題。國內外學者已經提出了很多改進規則或算法。改進方案大體可分為2類：（1）規則修改方法；（2）證據修改方法。 文獻［4］的改進措施是取消歸一化因子，將沖突信息分配給不確定項。文獻［5］提出了一種加權平均法則，具有明顯的沖突消解效果。文獻［6-9］提出的改進規則大體上將平均法與經典的D-S證據合成公式相結合，通過在各證據的平均信任分配之前增加一個加權系數的方法，實現對各焦元BPA的合理補償。加權系數則是通過計算證據之間的相互支持程度或證據距離確定的［10-12］。文獻［13］提出一種證據平均組合規則。首先，將各證據的可信分配平均分配給各焦元子集，然后使用經典合成規則對修改后的證據進行K-1次合成。文獻［14］提出的改進方案是根據現實情況重新分配沖突的那部份信任分配。文獻［15］提出一種證據修改規則，借鑒2個事件的聯合概率實現證據信任分配的修改。這些改進方法具有程度不同的沖突消解效果，但它們也或多或少存

在各自的不足。如計算過程不夠簡捷，或合成結果的收斂性不夠理想等。

本文提出一種較為簡捷的沖突證據合成算法，即將經典合成公式和加權平均法混合使用的分步合成算法。盡管分步合成方法已被人們廣泛使用，但該方法理論上的合理性目前尚未見諸文獻探討。因此，本文研究證據分步合成方法理論上的合理性問題，提出相關的定理和推論，并給出證明。

2 D-S證據合成法則及其分步合成方法

2.1 D-S證據合成法則

設空間Θ=｛χ1，χ2，…，χn｝由一些互斥且窮舉的元素組成，稱為辨識框架。Θ的冪集2Θ形成一個命題集合，定義函數如果集合中的任一命題A（A∈2Θ）滿足：

則稱m為A的基本概率賦值（Basic Probability Assign-

ment，BPA），亦稱基本信任分配。如果m（A）＞0，則稱A為焦元。對于相互獨立的2個證據源 m1（*），m2（*），提供了如下經典合成公式：

其中，K值表示各項證據的相互沖突程度。當K=1時表示各方面證據極度沖突，無法進行證據合成。事實上，如果K＞1，將使合成后的m（A）＜0，同樣無意義，因此，多個證據相互合成的先決條件是0＜K＜1，K值越接近1，表示證據之間的沖突程度越高。

2.2 證據分步合成方法

經典D-S證據合成公式只有兩證據合成形式。當需要合成的證據超過2個時，普遍使用先將最前面的2個證據合成，然后逐步添加證據的分步合成方式。D-S證據合成公式滿足結合律和交換律，但是，由于D-S證據合成公式無法用于高度沖突的證據合成，在很多實際問題合成過程中，常需要修改合成規則或證據本身。這就牽涉到證據順序問題和分步合成在理論上的合理性問題，以及分步合成結果的收斂性及收斂條件等問題。

3 證據分步合成合理性及結果收斂性

本文提出關于D-S證據兩兩分步合成方法的定理和推論，并加以數學證明。

3.1 一般表達形式

首先，提出一個焦元子集互不相交條件下，分步合成最終合成結果的定理。

定理1 假設Θ為一識別框架，A為Θ中的焦元。設Θ中有 N個相互獨立的 A的子集：A：A1，A2，…，AN，這些子集彼此互不相交。現有 n行相互獨立的證據如下：

假定這些證據滿足如下歸一化條件：

且任何兩行證據之間的沖突程度K＜1，如果使用文獻［1］的合成公式對式（4）中的證據進行兩兩分步合成，那么最終的合成結果必為：

現在使用數學歸納法證明定理1，過程如下：

證明：首先獲得最前2行證據的合成結果，這里，證據組數k=2，根據式（3），計算證據相互沖突程度：

N

由式（2）得，第一步合成結果為：

則可獲得將式（8）中的結果與式（4）中下一行證據的合成結果。

沖突程度為：

前K+1行證據的合成結果為：

由于全部證據的行數為n，即K+1可取的最大值為n，因此有：

至此，定理1得證。

3.2 D-S證據分步合成結果的歸一化問題

其次，提出一個關于使用前述合成方法所獲得的合成結果滿足歸一化條件的定理。

定理2 假設Θ為一識別框架，A為Θ中的焦元。設Θ中有 N個相互獨立的 A的子集：A：A1，A2，…，AN，這些子集彼此互不相交。現有 n行相互獨立的證據如式（4）所示。假定這些證據滿足歸一化條件式（5），且任何2行證據之間的沖突程度K＜1。如果使用文獻［1］的合成公式對式（4）中的證據進行兩兩分步合成，最終合成結果可寫作：

則這一合成結果滿足如下歸一化條件：

證明：依據定理1，最終合成結果中全部BPA之和為：

因此，定理2得證。

3.3 關于D-S證據兩兩分步合成方法的推論

依據定理 1和定理 2，還可以得出如下 2個推論：

推論1 使用文獻［1］的合成公式以兩兩分步合成方式對式（4）中證據進行合成時其最終合成結果與式（4）中證據行的使用順序無關。

證明：假如將式（4）中任意2行證據的位置互換，即將第k行證據mk（Aj）與第m行證據mm（Aj），j=1，2，…，N互換。設1≤k＜m≤n。依據定理1中的結論，則式（4）中前k-1行證據合成結果為：

這一結果與定理1中未進行行交換時所得合成結果相同。因此，本推論得證。

推論2 使用文獻［1］的合成公式以兩兩分步合成方式對式（4）中的證據進行合成時，如果在全部證據中至少存在一個焦元子集，其中的各BPA元素均不為0，寫作：

則最終合成結果必收斂，即，最終合成結果中，BPA分布必大部份集中到那些BPA元素均不為零的焦元子集。

證明：假定在證據式（4）的 n行證據中，其中的m行證據中至少存在一個為零的BPA元素。記作：

式（4）中其余P行證據中均無為零的BPA元素。 記作：

那么，有：

根據定理1，有：

因此，在最終合成結果中，BPA的分配必集中到那些其中無為零 BPA元素的焦元子集。此推論得證。

4 改進的D-S證據合成算法

4.1 國內外學者提出的改進措施

針對高度沖突證據的合成問題，國內外學者提出了許多改進方法。文獻［4］提出了一種改進方法，取消了D-S證據合成中的歸一化因子，并將沖突信息全部賦予不確定項。雖然該方法可以避免極端的合成結果，但由于大多數信任分配給不確定項，在處理許多實際問題時，仍無法帶來滿意效果。文獻［5］提出了加權平均算法，其合成公式如下：

權重由證據的可靠性或重要性決定。該方法可以較好地解決高度沖突證據合成問題，但其合成結果的收斂效果差一些。至于如何確定權重是一個需要進一步研究的問題。這種方法不適合單獨使用，但可以與其他方法結合使用。文獻［13］提出的改進方法是：首先求取各證據的平均可信分配，然后使用經典合成規則，反復使用先平均后合成的方法，對證據進行K-1次合成。該方法的計算過程較為繁復，合成結果的收斂性也需進一步改善。學者們分別提出了一些改進方法，合成結果得到不同程度的改善。大體結合經典的D-S方法和平均法。高度沖突證據合成時，更新BPA的主要部分來自BPA的平均值乘以一定的加權系數。加權系數則是通過計算證據之間的相互支持程度或證據距離確定的。這些方法可以避免傳統D-S方法的一票否決現象或出現不合常理的結果。但現有大部分改進規則的計算過程比較復雜。如果加權平均方法只提供證據合成的中間結果，且最后合成結果能令人滿意，則加權平均法可視作一種簡單而有效的緩解沖突方法。因此，提出一種將經典D-S方法與加權平均法混合交替使用的新型合成算法。

4.2 分步合成算法

算法步驟如下：

Step1 根據設置的可信分配值上限（0.999 9）預處理所有的證據數據和，設置加權平均法的加權系數和沖突閾值kmax。

Step2 計算待合成的2個證據的沖突程度K。

Step3 如果k＜kmax，使用合成公式式（2），否則選擇加權平均法公式式（12）。

Step4 如果所有證據合成完畢，則保存最后結果并退出。否則，設置當前合成結果為第1個證據，提取下一個證據作為第2個證據等待合成，回到Step2。

關于沖突閾值如何確定的問題。在實際情況下，高度沖突證據與非高度沖突證據之間較難做出明確的區別。使用本文算法合成時，如果非高度沖突情況被視為高度沖突，可能降低合成結果的準確性。如果情況相反，將高度沖突視作非高度沖突，則可能無法得到融合結果。因此，寧愿非高度沖突情況被視為高度沖突，而不是相反。根據仿真結果，建議Kmax=0.96～0.98。

4.3 算法復雜度分析

將本文算法與經典合成公式相比，如果整個合成過程中沖突程度始終小于設定的閾值，則兩者合成計算過程大體相同。算法復雜度決定于子集數N和證據行數n。一般使N≤6，n≤6，可合理控制算法的硬件開銷和時間復雜度。如果合成過程中存在高度沖突證據（K≥Kmax），此時選用加權平均合成公式式（12），其算法復雜度小于合成公式。因此本文算法與經典合成公式相比，復雜度無明顯增大。

5 仿真結果和分析

本文收集了5組從某煤礦瓦斯監測系統提取的沖突樣本數據，如表1所示。這些樣本代表5種經常出現在煤礦井下的不同情況（1個正常樣本和4個異常樣本）。分別使用經典的D-S證據合成方法、國內外代表性的改進方法和本文算法進行合成有效性對比測試。測試結果如表2所示。

表1 證據樣本與危險等級對應的BPA值

表2 5種不同沖突程度證據合成結果的對比

測試結果表明：

（1）在多數情況下，本文算法的最終合成結果比表中列出的代表性改進規則具有更好的收斂效果和較小的不確定性。

（2）在證據4的合成中，出現了不夠收斂的合成結果。出現此結果的原因是，在最后一步合成中，加權平均法被選用。可見，使用本文算法時，應盡量避免在最后一步使用加權平均法。如果將證據行2和行3互換，最后合成結果將是A1=0，A2=0，A3=0，A4=0，A5=0.992 3，X=0.007 3。這使合成結果的收斂效果得到了明顯改善。因此，可通過適當調整證據順序改善合成結果的收斂性。此外，可以合理地調整加權平均法的加權系數來改善合成效果，并使合成結果更符合工程實際。

6 結束語

為解決高度沖突證據的分步合成問題，本文提出一種合成公式與加權平均法混合使用的分布合成算法。理論研究和仿真結果表明：分步合成方法具有理論上的合理性，且分步合成結果具有收斂性。本文提出的沖突證據合成算法合成高度沖突證據時，合成結果比其他改進規則具有更好的收斂效果和更小的不確定性。使用該算法合成高度沖突證據時，如果最后一步選用平均法，可能會使合成結果的收斂性變差。但如果適當調整證據順序，可明顯改善合成結果的收斂性。因此，下一步工作需要對此進行研究。

［1］ Dempste A.Upper and Lower Probabilities Induced by a Multivalued Mapping［J］.Annals of Mathematical Statistics，1967，38（2）：325-339.

［2］ Shafer G.A Mathematical Theory of Evidence［M］. Princeton，USA：Princeton University Press，1976.

［3］ Zadeh L.A Simple View of the Dempster-Shafer Theory of Evidence and Its Implication for the Rule of Combination［J］.A I Magazine，1986，7（2）：85-90.

［4］ Yager R R.On the Dempster-Shafer Framework and New Combination Rules［J］.Information Sciences，1987，41（2）：93-137.

［5］ Person S，Kreinovich V.Representation，Propagation and Aggregation of Uncertainty［Z］.2002.

［6］ 孫 全，葉秀清，顧偉康.一種新的基于證據理論的合成公式［J］.電子學報，2000，28（8）：117-119.

［7］ 李弼程，王 波，魏 俊，等.一種有效的證據理論合成公式［J］.數據采集與處理，2002，17（1）：33-36.

［8］ 鄧 勇，施文康.一種改進的證據推理組合規則［J］.上海交通大學學報，2003，37（8）：1275-1278.

［9］ 肖明珠，陳光禹.一種改進的證據合成公式［J］.數據采集與處理，2004，19（4）：467-469.

［10］ 潘 愷，李 輝，邢 鋼.基于置信距離的沖突證據合成方法［J］.計算機工程，2013，39（1）：290-293.

［11］ 權 文，王曉丹，王 堅，等.一種基于局部沖突分配的 DST組合規則［J］.電子學報，2012，40（9）：1880-1884.

［12］ 董增壽，鄧麗君，曾建潮.一種新的基于證據權重的DS改進算法［J］.計算機技術與發展，2013，23（5）：58-62.

［13］ Murphy C K.Combining Belief Functions when Evidence Conflicts［J］.Decision Support System s，2000，29（1）：1-9.

［14］ Lefevre E，Colot O，Vannoorenberghe P.Belief Function Combination and the Conflict Management［J］. Information Fusion，2002，3（2）：149-162.

［15］ Ali T，Dutta P，Boruah H.A New Combination Rule for Conflict Problem of Dempster-Shafer Evidence Theory［J］. International Journal of Energy，Information and Communications，2012，3（1）：35-40.

編輯顧逸斐

A Mixed Step by Step Combination Algorithm for Highly Conflict Evidence

CHEN Qiang，HUANG Dandan，LI Bin，LU Yuan
（School of Electrical Engineering and Automation，Jiangxi University of Science and Technology，Ganzhou 341000，China）

In spite of step by step combination method is widely used by researchers，the rationality of this method in theory is not appeared in the literature review.This paper presents a general math expressions of step by step combination results，and studies the theoretical rationality of step by step combination method.The convergence of the combination results，the relationship between final combination results and the row order is studied.Several theorems and deductions are presented and proved using mathematical methods.The step by step combination algorithm mixing evidence combination formula and the weighted average method is proposed for combination of highly conflict evidence. Simulation results show that the proposed algorithm has simpler calculation process and better convergence effectiveness than representative alternative rules.

D-S evidence combination；step by step combination algorithm；convergence；highly conflict evidence；weighted average method

陳 強，黃丹丹，李 彬，等.一種高度沖突證據混合分步合成算法［J］.計算機工程，2015，41（10）：302-308.

英文引用格式：Chen Qiang，Huang Dandan，Li Bin，et al.A Mixed Step by Step Combination Algorithm for Highly Conflict Evidence［J］.Computer Engineering，2015，41（10）：302-308.

1000-3428（2015）10-0302-07

A

TP301.6

江西省教育廳科學技術研究基金資助項目（GJJ13398）；江西省研究生創新專項基金資助項目（YC2013-S195）。

陳 強（1964-），男，教授、博士，主研方向：信息融合，智能監測，人工免疫；黃丹丹、李 彬、盧 愿，碩士研究生。

2014-09-28

2014-12-01E-m ail：ls6400@126.com