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

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

D-S證據(jù)合成中，分步合成方法已被人們廣泛使用，但該方法理論上的合理性目前尚較少見諸文獻(xiàn)探討。本文著重研究證據(jù)分步合成方法理論上的合理性問題，使用Dempster的經(jīng)典證據(jù)合成公式合成兩個(gè)高度沖突證據(jù)時(shí)，常常得到有違常理的結(jié)果[1-2]。Zadeh曾提出一個(gè)著名的反例揭示這一問題[3]。針對這一問題，國內(nèi)外學(xué)者已經(jīng)提出了很多改進(jìn)規(guī)則或算法。改進(jìn)方案大體可分為兩類：一類屬于規(guī)則修改方法（如Yager，Person，孫全，鄧勇，李弼程，肖明珠等人提出的改進(jìn)法則）[4-12]；另一類是證據(jù)修改方法。（如 Murphy，Lefevre，Ali等人提出的改進(jìn)方法）[13-15]。Yager的改進(jìn)措施是取消歸一化因子，將沖突信息分配給不確定項(xiàng)[4]。雖然該方法可以避免極端的合成結(jié)果，但由于大多數(shù)信任分配給不確定項(xiàng)，在處理許多實(shí)際問題時(shí)，仍無法帶來滿意效果。Person等人提出了一種加權(quán)平均法則，具有明顯的沖突消解效果[5]。但其合成結(jié)果的收斂效果較差。孫全、鄧勇，肖明珠等人提出的改進(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ù)距離確定的。Murphy提出一種證據(jù)平均組合規(guī)則。首先，將各證據(jù)的可信分配平均分配給各焦元子集，然后使用經(jīng)典合成規(guī)則對修改后的證據(jù)進(jìn)行K-1次合成[13]。Lefevre提出的改進(jìn)方案是根據(jù)現(xiàn)實(shí)情況重新分配沖突的那部份信任分配[14]。阿里提出一種證據(jù)修改規(guī)則，借鑒兩個(gè)事件的聯(lián)合概率實(shí)現(xiàn)證據(jù)信任分配的修改[15]。這些改進(jìn)方法具有程度不同的沖突消解效果，但它們也或多或少存在各自的缺點(diǎn)或不足。如計(jì)算過程不夠簡捷，或合成結(jié)果的收斂性不夠令人滿意等。本研究提出一種較為簡捷的沖突證據(jù)合成算法——將Dempster的經(jīng)典合成公式和加權(quán)平均法混合使用的分步合成算法。

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

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

設(shè)空間Θ={x1，x2，…，xn}由一些互斥且窮舉的元素組成，稱為辨識框架。Θ的冪集2Θ形成一個(gè)命題集合，定義函數(shù)m:2Θ→[0，1]，如果集合中的任一命題A(A∈2Θ)滿足：

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

式（2）和（3）中的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ù)之間的沖突程度越高。

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

經(jīng)典D-S證據(jù)合成公式只有兩證據(jù)合成形式。當(dāng)需要合成的證據(jù)超過兩個(gè)時(shí)，人們普遍使用先將最前面的兩個(gè)證據(jù)合成，然后逐步添加證據(jù)的分步合成方式。D-S證據(jù)合成公式滿足結(jié)合律和交換律，這樣做法似乎順理成章。但是，由于D-S證據(jù)合成公式無法用于高度沖突證據(jù)合成，在很多實(shí)際問題合成過程中，常常需要修改合成規(guī)則或證據(jù)本身。這就牽涉到證據(jù)順序問題和分步合成在理論上的合理性問題，以及分步合成結(jié)果的收斂性及收斂條件等問題。對于這些問題，目前國內(nèi)外文獻(xiàn)尚較少論及，本文在此作了一些理論上的探討。

2 D-S證據(jù)分步合成的合理性及合成結(jié)果的收斂性

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

2.1 D-S證據(jù)兩兩分步合成方法最終合成結(jié)果的一般表達(dá)形式

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

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

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

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

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

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

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

上式可改寫為：

現(xiàn)在，假定最前面k行證據(jù)的合成結(jié)果為：

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

沖突程度為：

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

以上結(jié)果可改寫為：

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

至此，定理1得證。

2.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），且任何兩行證據(jù)之間的沖突程度K＜1。如果使用Dempster的合成公式對式（4）中的證據(jù)進(jìn)行兩兩分步合成，最終合成結(jié)果可寫作：m(A1)，m(A2)，…，m(AN)，則這一合成結(jié)果滿足如下歸一化條件：

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

因此，定理2得證。

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

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

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

證明假如將式（4）中任意兩行證據(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é)果為：

式（4）中前k行證據(jù)合成結(jié)果為：

式（4）中前m行證據(jù)合成結(jié)果為：

式（4）中全部n行證據(jù)合成結(jié)果為：

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

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

mi(Aj)≠0，i=1，2，…，n;j∈(1，2，…，N)

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

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

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

那么，

據(jù)定理1，

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

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

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

對于沖突消解方法，引言部份已對國內(nèi)外學(xué)者提出的一些代表性方法的特點(diǎn)進(jìn)行了論述。這些方法可以避免傳統(tǒng)D-S方法的一票否決現(xiàn)象或出現(xiàn)不合常理的結(jié)果。但現(xiàn)有大部份改進(jìn)規(guī)則的計(jì)算過程都比較復(fù)雜。Person等人提出的加權(quán)平均方法[5]是一種相對較為簡捷的沖突消解方法，其合成公式如下：

這里，權(quán)重由證據(jù)的可靠性或重要性決定。該方法可以較好地解決高度沖突證據(jù)合成問題，但其合成結(jié)果的收斂效果較差。至于如何確定權(quán)重是一個(gè)需要進(jìn)一步研究的問題。本文認(rèn)為這種方法不太適合單獨(dú)使用，但可以與其他方法結(jié)合使用。如果加權(quán)平均方法只提供證據(jù)合成的中間結(jié)果，且最后合成結(jié)果能令人滿意，則加權(quán)平均法不失為一種簡單而有效的緩解沖突方法。通過大量仿真實(shí)例研究發(fā)現(xiàn)，如果兩個(gè)需要合成的證據(jù)之間的沖突程度K值小于閾值Kmax，使用Dempster合成公式即可獲得令人滿意的合成結(jié)果，而當(dāng)K值達(dá)到或超過Kmax時(shí)，則合成結(jié)果具有較大的不確定性（不能保證令人滿意）。如果以Kmax為閾值，決定是選用Dempster合成公式還是選用加權(quán)平均合成公式，不但能確保各分步合成順利進(jìn)行，獲得最終合成結(jié)果，而且整個(gè)分步合成計(jì)算過程較為簡捷。因此，提出一種將經(jīng)典D-S方法與加權(quán)平均法混合交替使用的新型合成算法。

3.2 Dempster合成公式與加權(quán)平均法混合的分步合成算法

算法如下：

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

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

步驟3 如果K＜Kmax，使用Dempster合成公式（2），否則選擇加權(quán)平均法公式（12）。

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

關(guān)于沖突閾值如何確定的問題。在實(shí)際情況下，高度沖突證據(jù)與非高度沖突證據(jù)之間較難作出明確的區(qū)別。使用本文算法合成時(shí)，如果非高度沖突情況被視為高度沖突，可能降低合成結(jié)果的準(zhǔn)確性。如果情況相反，將高度沖突視作非高度沖突，則可能無法得到融合結(jié)果。因此，可容許非高度沖突情況被視為高度沖突，反之則不容許。研究結(jié)果表明：當(dāng)Kmax≥0.98時(shí)，有時(shí)會得到不合常理的合成結(jié)果；當(dāng)Kmax≤0.96時(shí)，合成結(jié)果的收斂程度有時(shí)會下降；當(dāng)0.96≤Kmax≤0.98時(shí)，既可獲得較好的收斂效果，又不會出現(xiàn)不合常理的合成結(jié)果。因此建議：Kmax=0.96～0.98。此外，本文進(jìn)行的多個(gè)仿真實(shí)例表明，使用本文算法合成時(shí)，證據(jù)使用的先后順序有時(shí)會對最終合成結(jié)果的收斂程度產(chǎn)生影響。其原因是由于證據(jù)順序的不合理，導(dǎo)致最后一步合成中，因沖突程度超過閾值，被迫選用平均法進(jìn)行合成，使最終合成結(jié)果收斂程度不夠令人滿意。此時(shí)，如果按照盡可能避免在最后一步合成中選用平均法的原則，試探性地改變證據(jù)順序，往往能獲得收斂程度更好的合成結(jié)果。

4 仿真結(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所示。測試結(jié)果表明：

（1）經(jīng)典D-S方法僅在合成低沖突程度的3號和5號證據(jù)組時(shí)獲得了令人滿意的結(jié)果，而在合成其他三組高度沖突證據(jù)時(shí)，無法得到確定的合成結(jié)果。

（2）在全部五組證據(jù)的合成中，Yager法均無法得到有實(shí)際意義的合成結(jié)果；Murphy均獲得了正確且收斂程度較高的合成結(jié)果，但其計(jì)算過程較為繁復(fù)；孫全法除了在合成4號證據(jù)組時(shí)無法得到確定的合成結(jié)果外，對其他四組證據(jù)均獲得了正確的合成結(jié)果，但合成結(jié)果的收斂程度均低于Murphy法和本文算法；Ali法均獲得了正確的合成結(jié)果，但合成結(jié)果的收斂程度也全都低于Murphy法和本文算法。

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

表2 本文算法(Kmax=0.97)與國內(nèi)外一些代表性改進(jìn)規(guī)則對五種不同沖突程度證據(jù)合成結(jié)果的對比

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

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

5 結(jié)論

理論研究和仿真結(jié)果表明：

（1）分步合成方法具有理論上的有合理性，且分步合成結(jié)果具有收斂性。

（2）分步合成方法不能用于合成高度沖突證據(jù)。

（3）本文提出的沖突證據(jù)合成算法合成高度沖突證據(jù)時(shí)，其合成結(jié)果比國內(nèi)外一些代表性改進(jìn)規(guī)則具有更好的收斂效果和更小的不確定性。

（4）使用本文算法合成高度沖突證據(jù)時(shí)，如果最后一步選用平均法，可能會使合成結(jié)果的收斂性變差。但如果適當(dāng)調(diào)整證據(jù)順序，可明顯改善合成結(jié)果的收斂性。

[1]Dempste A.Upper and lower probabilities induced by a multivalued mapping[J].Annals of Mathematical Statistics，1967：325-339.

[2]Shafer G.A mathematical theory of evidence[M].[S.l.]：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].AI 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[R].SAND Report，2002.

[6]孫全，葉秀清，顧偉康.一種新的基于證據(jù)理論的合成公式[J].電子學(xué)報(bào)，2000，28（8）：117-119.

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

[8]鄧勇，施文康.一種有效處理沖突證據(jù)的組合方法[J].紅外與毫米波學(xué)報(bào)，2004，23（1）：27-32.

[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)重的D-S改進(jìn)算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（5）：58-62.

[13]Murphy C K.Combiningbelieffunctionswhenevidence conflicts[J].Decision Support Systems，2000，29（1）：1-9.

[14]Lefevre E，Colot O，Vannoorenberghe P.Belief function combination and the conflictmanagement[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.