一種高度沖突證據(jù)混合分步合成算法

陳 強(qiáng)，黃丹丹，李 彬，盧 愿

（江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院，江西 贛州341000）

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

一種高度沖突證據(jù)混合分步合成算法

陳 強(qiáng)，黃丹丹，李 彬，盧 愿

（江西理工大學(xué)電氣工程與自動(dòng)化學(xué)院，江西 贛州341000）

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

D-S證據(jù)合成；分步合成算法；收斂性；高度沖突證據(jù)；加權(quán)平均法

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

1 概述

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

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

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

2 D-S證據(jù)合成法則及其分步合成方法

2.1 D-S證據(jù)合成法則

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

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

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

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

2.2 證據(jù)分步合成方法

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

3 證據(jù)分步合成合理性及結(jié)果收斂性

本文提出關(guān)于D-S證據(jù)兩兩分步合成方法的定理和推論，并加以數(shù)學(xué)證明。

3.1 一般表達(dá)形式

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

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

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

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

現(xiàn)在使用數(shù)學(xué)歸納法證明定理1，過程如下：

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

N

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

則可獲得將式（8）中的結(jié)果與式（4）中下一行證據(jù)的合成結(jié)果。

沖突程度為：

前K+1行證據(jù)的合成結(jié)果為：

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

至此，定理1得證。

3.2 D-S證據(jù)分步合成結(jié)果的歸一化問題

其次，提出一個(gè)關(guān)于使用前述合成方法所獲得的合成結(jié)果滿足歸一化條件的定理。

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

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

證明：依據(jù)定理1，最終合成結(jié)果中全部BPA之和為：

因此，定理2得證。

3.3 關(guān)于D-S證據(jù)兩兩分步合成方法的推論

依據(jù)定理 1和定理 2，還可以得出如下 2個(gè)推論：

推論1 使用文獻(xiàn)［1］的合成公式以兩兩分步合成方式對式（4）中證據(jù)進(jìn)行合成時(shí)其最終合成結(jié)果與式（4）中證據(jù)行的使用順序無關(guān)。

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

這一結(jié)果與定理1中未進(jìn)行行交換時(shí)所得合成結(jié)果相同。因此，本推論得證。

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

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

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

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

那么，有：

根據(jù)定理1，有：

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

4 改進(jìn)的D-S證據(jù)合成算法

4.1 國內(nèi)外學(xué)者提出的改進(jìn)措施

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

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

4.2 分步合成算法

算法步驟如下：

Step1 根據(jù)設(shè)置的可信分配值上限（0.999 9）預(yù)處理所有的證據(jù)數(shù)據(jù)和，設(shè)置加權(quán)平均法的加權(quán)系數(shù)和沖突閾值kmax。

Step2 計(jì)算待合成的2個(gè)證據(jù)的沖突程度K。

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

Step4 如果所有證據(jù)合成完畢，則保存最后結(jié)果并退出。否則，設(shè)置當(dāng)前合成結(jié)果為第1個(gè)證據(jù)，提取下一個(gè)證據(jù)作為第2個(gè)證據(jù)等待合成，回到Step2。

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

4.3 算法復(fù)雜度分析

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

5 仿真結(jié)果和分析

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

表1 證據(jù)樣本與危險(xiǎn)等級對應(yīng)的BPA值

表2 5種不同沖突程度證據(jù)合成結(jié)果的對比

測試結(jié)果表明：

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

（2）在證據(jù)4的合成中，出現(xiàn)了不夠收斂的合成結(jié)果。出現(xiàn)此結(jié)果的原因是，在最后一步合成中，加權(quán)平均法被選用?？梢姡褂帽疚乃惴〞r(shí)，應(yīng)盡量避免在最后一步使用加權(quán)平均法。如果將證據(jù)行2和行3互換，最后合成結(jié)果將是A1=0，A2=0，A3=0，A4=0，A5=0.992 3，X=0.007 3。這使合成結(jié)果的收斂效果得到了明顯改善。因此，可通過適當(dāng)調(diào)整證據(jù)順序改善合成結(jié)果的收斂性。此外，可以合理地調(diào)整加權(quán)平均法的加權(quán)系數(shù)來改善合成效果，并使合成結(jié)果更符合工程實(shí)際。

6 結(jié)束語

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

［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ù)理論的合成公式［J］.電子學(xué)報(bào)，2000，28（8）：117-119.

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

［8］ 鄧 勇，施文康.一種改進(jìn)的證據(jù)推理組合規(guī)則［J］.上海交通大學(xué)學(xué)報(bào)，2003，37（8）：1275-1278.

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

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

［11］ 權(quán) 文，王曉丹，王 堅(jiān)，等.一種基于局部沖突分配的 DST組合規(guī)則［J］.電子學(xué)報(bào)，2012，40（9）：1880-1884.

［12］ 董增壽，鄧麗君，曾建潮.一種新的基于證據(jù)權(quán)重的DS改進(jìn)算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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

陳 強(qiáng)，黃丹丹，李 彬，等.一種高度沖突證據(jù)混合分步合成算法［J］.計(jì)算機(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

江西省教育廳科學(xué)技術(shù)研究基金資助項(xiàng)目（GJJ13398）；江西省研究生創(chuàng)新專項(xiàng)基金資助項(xiàng)目（YC2013-S195）。

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

2014-09-28

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