基于關(guān)聯(lián)系數(shù)的D_S融合悖論改進(jìn)算法

鄭旗，袁曉兵，李寶清

（中國(guó)科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所 ，上海 201800）

基于關(guān)聯(lián)系數(shù)的D_S融合悖論改進(jìn)算法

鄭旗，袁曉兵，李寶清

（中國(guó)科學(xué)院 上海微系統(tǒng)與信息技術(shù)研究所 ，上海 201800）

針對(duì)Dempster_Shafer證據(jù)融合理論在融合高沖突證據(jù)源時(shí)出現(xiàn)融合悖論的問(wèn)題，提出了一種通過(guò)定義關(guān)聯(lián)系數(shù)并構(gòu)造絕對(duì)支持度對(duì)原證據(jù)進(jìn)行預(yù)處理，然后采用經(jīng)典的D_S融合方法對(duì)證據(jù)進(jìn)行融合的改進(jìn)方法。通過(guò)對(duì)關(guān)聯(lián)系數(shù)中增長(zhǎng)因子取值進(jìn)行實(shí)驗(yàn)和一些經(jīng)典改進(jìn)方法進(jìn)行對(duì)比實(shí)驗(yàn)，可以看出本文方法不僅能夠有效削減證據(jù)之間的沖突，也能保持D_S融合理論的優(yōu)越性，其在融合的準(zhǔn)確性和收斂速度上都有很大的提升。

D_S證據(jù)融合；關(guān)聯(lián)系數(shù)；絕對(duì)支持度

隨著物聯(lián)網(wǎng)的快速發(fā)展，數(shù)據(jù)融合也隨之發(fā)展起來(lái)。證據(jù)理論[1]是1967年由Dempster提出，并有Shafer改進(jìn)的數(shù)學(xué)理論[2]，是對(duì)概率論的進(jìn)一步擴(kuò)充，適用于專(zhuān)家系統(tǒng)、人工智能、模式識(shí)別和系統(tǒng)決策等重要領(lǐng)域。他在物聯(lián)網(wǎng)方面的雖然D_S證據(jù)理論在不確定信息的表示和融合有其獨(dú)特的優(yōu)勢(shì)，但是其也有比較顯著的缺點(diǎn)。D_S組合規(guī)則在組合高沖突證據(jù)時(shí)，常常會(huì)出現(xiàn)有悖常理、違反直覺(jué)的結(jié)論[3-4]。有關(guān)這方面的研究，已經(jīng)成為當(dāng)前對(duì)D_S研究的一個(gè)熱點(diǎn)。

目前現(xiàn)存的對(duì)D_S證據(jù)理論的改進(jìn)方法主要?dú)w納為以下兩個(gè)方面[5-6]并提出了一些改進(jìn)方法[7-11]：

一是從修正D_S組合規(guī)則角度入手，這類(lèi)方法主要是認(rèn)為D_S組合規(guī)則的歸一化系數(shù)在遇到高度沖突證據(jù)源時(shí)表現(xiàn)不好。應(yīng)該修正融合規(guī)則，如Yager[12]提出的去掉歸一化因子1/（1-k），并將k在合成后被賦給m（X），將沖突分解給了未知領(lǐng)域，降低了證據(jù)間的沖突。孫全[13]定義了證據(jù)的可信度ε，在融合時(shí)若證據(jù)沖突較高，就會(huì)主要用證據(jù)的均值進(jìn)行融合。

另一種方法是從修正基本概率賦值的角度入手，這類(lèi)方法主要是認(rèn)為沖突的根源來(lái)自于證據(jù)源本身，如何通過(guò)修正證據(jù)源，從源頭上解決沖突，不少研究人員給出了他們的解決方法。梁旭榮[14]提出利用證據(jù)之間的支持度矩陣，得到證據(jù)的可信度，并以此對(duì)證據(jù)進(jìn)行加權(quán)平均。

以上方法從不同的角度修正D_S融合算法。修正組合規(guī)則的方法復(fù)雜度較低，但是新的合成規(guī)則可能會(huì)破壞D_S組合規(guī)則本身較好的性能[15]。修正證據(jù)源的方法，既保留了經(jīng)典D_S理論的優(yōu)勢(shì)，又能成功地降低證據(jù)間的沖突，更能為大家所理解，而且效果也優(yōu)于基于融合規(guī)則的修正方法。因此文中定義了證據(jù)間的關(guān)聯(lián)系數(shù)，并進(jìn)一步定義了絕對(duì)支持度對(duì)證據(jù)源進(jìn)行預(yù)處理，然后再采用經(jīng)典的D_S融合規(guī)則對(duì)證據(jù)進(jìn)行融合的融合方法。

1 D_S證據(jù)理論原理及改進(jìn)算法

1.1 D_S證據(jù)原理及其悖論

限于篇幅，文中只對(duì)D_S證據(jù)理論進(jìn)行簡(jiǎn)要介紹，詳細(xì)請(qǐng)參考文獻(xiàn)[1]。

定義1：設(shè)Η表示某個(gè)有限集合，稱(chēng)為假設(shè)空間；又假設(shè)Ρ（Η）表示Η的所有子集構(gòu)成的集類(lèi)（稱(chēng)為Η 的冪集），映射 m：Ρ（Η）→[0，1]稱(chēng)為一個(gè)基本概率賦值 （Basic Propability Assignment，BPA）或mass函數(shù)，如果

那么mass函數(shù)實(shí)際上就是對(duì)各種假設(shè)的評(píng)價(jià)權(quán)值（注意：基本概率賦值不是概率，不滿(mǎn)足可列可加性）。

定理1：設(shè)Η表示某個(gè)有限集合，Bel和Pl分別表示Η的信度函數(shù)和似真度函數(shù)，則有

定理2：設(shè)m、Bel和Pl分別是Η的mass函數(shù)、信度函數(shù)和似真度函數(shù)，則對(duì)任意的A∈Ρ（Η）有

定理3：（Dempster-Shafer融合公式）設(shè)m1、m2是Η上的兩個(gè)mass函數(shù)，則

是融合結(jié)果的mass函數(shù)，其中

為歸一化系數(shù)，k=1-N，為不一致因子。

在證據(jù)源沒(méi)有大沖突的情況下，D_S證據(jù)能夠很好的融合不同傳感器的證據(jù)源，但當(dāng)證據(jù)源之間存在明顯的沖突，D_S證據(jù)就會(huì)出現(xiàn)悖論。如下所示：

例：假設(shè)傳感器1，2對(duì)某一特定目標(biāo)的分類(lèi)識(shí)別結(jié)果的mass函數(shù)如下所示，識(shí)別空間Η={P，W，T}

融合結(jié)果：m（P）=0，m（W）=0，m（T）=1。從證據(jù)源可以看出，兩個(gè)傳感器將目標(biāo)判為T(mén)的概率都很低，但是融合結(jié)果卻將目標(biāo)類(lèi)別判為T(mén)。很明顯這不符合常理，產(chǎn)生了悖論。

1.2 現(xiàn)有的改進(jìn)算法

針對(duì)上述D_S證據(jù)融合規(guī)則及其悖論，有很多人分別從上文提到的兩個(gè)改進(jìn)層面提出了改進(jìn)方法。

1）Yager改進(jìn)方法

Yager[12]從修正D_S證據(jù)組合規(guī)則的角度進(jìn)行如下的改進(jìn)，融合規(guī)則如下：

可以看出，Yager將沖突因素全部劃分給了未知域X。這樣的確可以降低沖突，但是他只是將沖突簡(jiǎn)單的分解給未知域X，故融合結(jié)果不是那么理想。

2）孫全改進(jìn)方法

孫全[13]基于Yager的方法進(jìn)行了修改，根據(jù)沖突系數(shù)定義了可信度ε=e-k，其中j≤n，n是證據(jù)源的個(gè)數(shù)。Kij是證據(jù)i和證據(jù)j之間的不一致因子。定義了上述可信度后，孫全將D_S融合規(guī)則修正如下：

孫全將沖突部分分解給未知域，在沖突較高時(shí)， 利用可信度給帶融合證據(jù)的均值加權(quán)，作為融合結(jié)果。

3）梁旭榮改進(jìn)方法

梁旭榮[14]結(jié)合了更改融合規(guī)則和更改證據(jù)源的方法，該法首先計(jì)算了證據(jù)的可信度，用歸一化的可信度對(duì)證據(jù)進(jìn)行加權(quán)后，再利用一種有效的沖突分配的組合方法進(jìn)行融合。效果不錯(cuò)，但是收斂速度較慢。

2 一種新的基于修正證據(jù)源的證據(jù)融合方法

可以看出，當(dāng)mi（Ak）和mj（Ak）有一個(gè)為0時(shí)，則rij=0，表示證據(jù)mi和mj在A(yíng)k處的關(guān)聯(lián)系數(shù)為0，此時(shí)一個(gè)證據(jù)在某種程度上支持該焦元，另一個(gè)證據(jù)則完全否定該焦元。當(dāng)mi（Ak）=mj（Ak），則rij=1。此時(shí)mi（Ak）和mj（Ak）的關(guān)聯(lián)性最強(qiáng)，它們對(duì)某焦元的判決一致。a是增長(zhǎng)因子用來(lái)控制乘方系數(shù)的，a值可以用來(lái)修正底數(shù)定義的不足。a值增大，則可以降低兩個(gè)證據(jù)之間的關(guān)聯(lián)系數(shù)。通過(guò)上式可以得到焦元Ak的關(guān)聯(lián)系數(shù)矩陣Rm*m，如下：

在分析了以上改進(jìn)方法后，得出從證據(jù)源上進(jìn)行修正更有優(yōu)勢(shì)。首先，從源頭上修正證據(jù)源可以有效地減輕證據(jù)沖突的影響。而且，從源上修正可以保證D_S的良好特性得到保留。結(jié)合上述，定義了證據(jù)源之間的關(guān)聯(lián)系數(shù)，并構(gòu)造絕對(duì)支持度對(duì)原證據(jù)源進(jìn)行修正。

定義2：設(shè)識(shí)別框架Η={A1，A2，A3…An}，有m條證據(jù)源，對(duì)任意焦元Ak，兩個(gè)證據(jù)源對(duì)該焦元的關(guān)聯(lián)系數(shù)定義如下：

定義3：已知關(guān)聯(lián)系數(shù)矩陣Rm*m，則每條證據(jù)的支持度定義如下：

從定義是可以看出，證據(jù)源mi的支持度supi（Ak）是由其他所有證據(jù)對(duì)焦元 Ak的關(guān)聯(lián)系數(shù)的總和。不難理解如果一個(gè)證據(jù)與其他證據(jù)的沖突不大，則該支持度會(huì)較大。若一個(gè)證據(jù)與其他證據(jù)的沖突較大，則該證據(jù)的支持度就會(huì)比較小，其可信度較低。

定義4：已知n個(gè)證據(jù)源的支持度，則絕對(duì)支持度定義如下：

支持度最大的證據(jù)經(jīng)過(guò)該處理后會(huì)被歸一化為1，支持度較低的證據(jù)會(huì)被歸一化0到1范圍內(nèi)。構(gòu)成絕對(duì)支持度矩陣Supam*n，并用該絕對(duì)支持度作為權(quán)重wi（Ak）對(duì)證據(jù)源進(jìn)行重新分配。

上式中，X是經(jīng)過(guò)預(yù)處理后重新分配的不確定領(lǐng)域，表示證據(jù)的不確定度。本方法降低沖突的途徑就是通過(guò)將沖突一部分重新分配給不確定域?qū)崿F(xiàn)的。修正處理后，mass矩陣會(huì)增加一個(gè)維度。

當(dāng)更新得到新的mass矩陣后，再用經(jīng)典的D_S合成公式對(duì)mass矩陣進(jìn)行合成，得出結(jié)果。

3 實(shí)驗(yàn)驗(yàn)證

3.1 關(guān)聯(lián)系數(shù)增長(zhǎng)因子的實(shí)驗(yàn)

例：假設(shè)傳感器1，2，3，4對(duì)某一特定目標(biāo)的分類(lèi)識(shí)別結(jié)果的mass函數(shù)分配如下所示，識(shí)別空間Η={P，W，T}，（已知真實(shí)目標(biāo)為P）：

增長(zhǎng)因子a分別取0.5、1、3、5、7，并比較實(shí)驗(yàn)結(jié)果融合結(jié)果如表1所示。

從表1和圖1可以看出：1）隨著a的增大，融合結(jié)果的收斂速度越來(lái)越快，圖中a=7的曲線(xiàn)收斂到1的速度最快；2）當(dāng)a從0.5變?yōu)?、從1變?yōu)?時(shí)收斂速度提升地最為明顯，后面隨著a的增加，收斂速度提升不明顯；而且由于a是計(jì)算的冪次，故隨著a的增大，需要計(jì)算的冪次越大；綜上所述，關(guān)聯(lián)系數(shù)中的a選擇3最為合適。

3.2 幾種改進(jìn)D_S融合算法對(duì)比

同樣采用上述用例，根據(jù)上述實(shí)驗(yàn)a=3。則根據(jù)關(guān)聯(lián)系數(shù)定義（式（8），（9））得到各焦元的關(guān)聯(lián)系數(shù)矩陣如下：

表1 增長(zhǎng)因子對(duì)融合結(jié)果的影響

圖1 增長(zhǎng)因子a對(duì)收斂速度的影響

經(jīng)過(guò)計(jì)算權(quán)重系數(shù)矩陣為：

權(quán)重更新后得到新的mass矩陣如下所示：

表2 沖突證據(jù)改進(jìn)算法結(jié)果比較

最后運(yùn)用經(jīng)典的D_S合成規(guī)則對(duì)新的mass函數(shù)矩陣進(jìn)行融合，并與經(jīng)典的D_S證據(jù)理論、Yager、孫全和梁旭榮的融合結(jié)果進(jìn)行比較，結(jié)果如表2所示。

從表2和圖2的結(jié)果可以看出，在處理高沖突證據(jù)源時(shí)：Yager的方法不能對(duì)沖突證據(jù)進(jìn)行合理的組合，他將沖突直接分給了未知域，但這對(duì)組合結(jié)果并沒(méi)有益；孫全的方法用各證據(jù)源的平均值加權(quán)融合結(jié)果，當(dāng)待融合的證據(jù)沖突較大，則融合結(jié)果主要由均值決定?？梢钥闯鲈摲椒ǖ氖諗克俣忍耍玬ass函數(shù)分配是朝著正確的結(jié)果發(fā)展的，但是在第4個(gè)證據(jù)到來(lái)之前，融合結(jié)果中W的mass函數(shù)大于P的mass函數(shù)，可見(jiàn)與實(shí)際情況是不相符的；梁旭榮的方法更多地考慮了證據(jù)源本身的信息，一定程度上提高了融合結(jié)果的正確性，但是融合的收斂速度太慢（圖中m（P）收斂到1很慢））。而且在融合證據(jù)m1，m2時(shí)，T的概率大于P，這與實(shí)際情況是不相符的；文中的方法更大程度上利用證據(jù)源的信息，修正證據(jù)源，將沖突進(jìn)行合理的分配，從結(jié)果來(lái)看，不僅在融合的準(zhǔn)確率上，在融合的收斂速度上都明顯優(yōu)于以前的改進(jìn)方法。

圖2 不同改進(jìn)方法收斂速度

4 結(jié) 論

文中提出了一種基于權(quán)重系數(shù)的D_S證據(jù)融合改進(jìn)方法。該方法構(gòu)造了證據(jù)源之間的關(guān)聯(lián)系數(shù)，能充分利用證據(jù)源之間的關(guān)聯(lián)性，降低證據(jù)源之間的沖突。不僅能夠準(zhǔn)確地融合出結(jié)果，而且在收斂速度上優(yōu)于其他方法。成功地解決了D_S證據(jù)融合中沖突證據(jù)導(dǎo)致的融合悖論，提高了D_S證據(jù)融合的可靠性和準(zhǔn)確性。

[1]DEMPSTER A P.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:Princeton University Press，1976.

[3]YANG J B.SINGH M G.An evidential reasoning approach for multiple attributed decision making with uncertainty[J].IEEE Transaction on System， Man and Cybernetics，1994，24（1）:1-18.

[4]DRUKOPOULOS E ，HSIA Y T，SMETS P. Transferable belief model for decision making in the evaluation based systems[J].IEEE Trans on System，Man and Cybernetics，1996，26（1）:698-712.

[5]DENG Yong，SHI Wen-kang，ZHU Zhen-fu et al. Combining belief functions based on distance of evidence[J].Decision Support System，2004（38）: 489-493.

[6]Lefevre E，Colot O，Vannoorenberghe P.Belief function combination and conflict management[J]. Information Fusion，2002（3）:149-162.

[7]王棟，李齊，蔣雯，等.基于pignistic概率距離的沖突證據(jù) [J].紅外與激光工程，2009，38（1）:149-154.

[8]盧正才，覃征.證據(jù)合成的一般框架及高度沖突證據(jù)合成方法 [J].清華大學(xué)學(xué)報(bào)，2011，51（11）: 1611-1626.

[9]黃建招，謝建，李良，等.基于沖突系數(shù)和pignistic概率距離的改進(jìn)證據(jù)組合方法[J].傳感器與微系統(tǒng)，2013，32（9）:21-24.

[10]司成，張紅旗，汪永偉，等.基于相異度矩陣的沖突證據(jù)合成算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（2）:482-486.

[11]邱二輝，謝建，黃建招.一種基于證據(jù)預(yù)處理的組合方法[J].傳感器與微系統(tǒng)，2010，29（12）:38-40.

[12]RONALD R Yager.On the dempstershafer framework and new combination rules [J]. Information Sciences，1987（41）:93-137.

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

[14]梁旭榮，姚佩陽(yáng)，梁德磊.改進(jìn)的組合規(guī)則及其在融合目標(biāo)識(shí)別中的應(yīng)用[J].電光與控制，2008，15（12）:37-41.

[15]韓德強(qiáng)，鄧勇，韓崇昭，等.利用不確定度的沖突證據(jù)組合[J].控制理論與應(yīng)用，2011，28（6）:788-792.

Improved combination rule of high conflict evidence based on correlation coefficient

ZHENG Qi，YUAN Xiao-bing，LI Bao-qing
（Shanghai Institute of MicroSystem and Information Technology，Chinese Academy of Sciences，Shanghai 201800，China）

D_S combination rule may cause fusion paradox when the evidences are highly conflicted. This paper proposes a new improved combination rule of evidence based on correlation coefficient.This method can not only reduce the conflict within evidence，but also maintain the benefit of traditional D_S method.Analysis and comparison for the experiments prove that the method performed better in accuracy and convergence rates than the existing ones.

dempster_shafer combination rule；correlation coefficient；absolutely support

TN99

：A

：1674－6236（2017）01-0017-05

2015-12-10稿件編號(hào)：201512125

微系統(tǒng)技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室基金（9140C1801021XXXXX）

鄭 旗（1990—），女，安徽合肥人，碩士研究生。研究方向：數(shù)據(jù)融合。