基于沖突因子和向量余弦的迭代D—S加權(quán)算法

劉海峰+聶靈風(fēng)+侯再恩+曹慧

摘 要： 為了擴(kuò)大D?S方法的適用范圍，用傳統(tǒng)的沖突因子與Pignistic概率向量余弦共同度量證據(jù)間的矛盾程度，將矛盾系數(shù)轉(zhuǎn)化為證據(jù)的權(quán)系數(shù)，首輪融合時(shí)只用權(quán)系數(shù)修正證據(jù)集，其他融合用替換修正和權(quán)系數(shù)修正二次修正證據(jù)集，采用迭代思想修正融合結(jié)果。替換修正充分利用每一次的融合結(jié)果，迭代過程使得最終的融合結(jié)果更加精確。利用公共算例和隨機(jī)算例驗(yàn)證后表明所提方法的融合效率高，融合結(jié)果更準(zhǔn)確，算法收斂速度快，能有效解決問題，擴(kuò)大了D?S的使用范圍。

關(guān)鍵詞： 證據(jù)理論； 迭代； 二次修正； 向量余弦； 沖突因子； 權(quán)系數(shù)

中圖分類號(hào)： TN911.1?34； TP274 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）05?0167?06

Abstract： In order to expand the application scope of D?S evidence theory， the conflict degree is measured with traditional conflict factor and Pignistic probability vector cosine to convert the conflict coefficient into the weight coefficient of evidence. The weight coefficient is used to modify the evidence set for the first fusion. The replace correction and weight coefficient correction are used to secondly modify the evidence set for other fusions. The iteration thought is adopted to modify the fusion result. Every fusion result is fully utilized by replace correction to make the final fusion result more accurate in iteration process. The verification results of classical example and random example show this algorithm has high fusion efficiency， accurate fusion result and fast convergence speed. It solves the problem effectively and extends the application range of D?S method.

Keywords： evidence theory； iteration； second correction； vector cosine； conflict factor； weight coefficient

0 引 言

Dempster?Shafer證據(jù)理論（簡(jiǎn)稱D?S方法）是對(duì)Bayes理論的推廣。它對(duì)命題的判斷從原來的“是”和“否”變成了“是”、“無知”和“否”。D?S理論可以有效地解決傳感器信息中的“不確定”問題[1]，它能夠準(zhǔn)確表示、度量以及組合無知區(qū)間的信息，推理時(shí)也不必事先給出知識(shí)的先驗(yàn)概率[2]。故而被廣泛地應(yīng)用在信息融合、模式識(shí)別、故障診斷、入侵檢測(cè)、問題預(yù)測(cè)、專家系統(tǒng)等許多領(lǐng)域。

但D?S方法也因一些缺陷而使用受限，本文用例證解釋這些缺陷，設(shè)是證據(jù)集，是融合結(jié)果，條證據(jù)如下：

缺陷一：一般沖突，如Zadeh反例：證據(jù)集時(shí)，證據(jù)中融合結(jié)果表示支持顯然有悖于直觀判斷。

缺陷二：出現(xiàn)一票否決現(xiàn)象。例如：證據(jù)集時(shí)，有條證據(jù)的證據(jù)集中有條證據(jù)的只有一條證據(jù)的而融合結(jié)果顯然這一條證據(jù)影響了融合結(jié)果。

缺陷三：焦元BPA分配不公平。如當(dāng)證據(jù)集時(shí)，融合結(jié)果顯然，合成結(jié)果有利于對(duì)和不公平。

缺陷四：缺乏魯棒性。如證據(jù)集時(shí)，融合結(jié)果與Zadeh反例相比，只是稍微改變成為后，融合結(jié)果相差甚遠(yuǎn)。

以上的問題雖然都會(huì)使D?S方法使用受限，但是問題發(fā)生的頻率不一樣。缺陷四是因?yàn)槌诵栽瓌t[3]，這并不表示D?S方法缺乏魯棒性，只是對(duì)于BPA為0的情況處理方式果斷，屬低頻問題。造成前三種問題的主要原因是證據(jù)之間存在高沖突并且合成規(guī)則對(duì)所有證據(jù)一視同仁。沖突證據(jù)產(chǎn)生的主要原因是多傳感器數(shù)據(jù)采集時(shí)的環(huán)境干擾，而多傳感器數(shù)據(jù)采集時(shí)現(xiàn)場(chǎng)根本無法做到無干擾，因此證據(jù)集中出現(xiàn)高沖突證據(jù)幾乎無法避免，受干擾的證據(jù)也不該和無干擾證據(jù)對(duì)融合結(jié)果產(chǎn)生相同的影響力。因此該問題是限制D?S方法使用的高頻問題。

如何擴(kuò)大它D?S的適用范圍成為國(guó)內(nèi)外眾多專家學(xué)者一直探究的課題。目前已提出的改進(jìn)方法主要分為三類：

第一類：主要修正D?S合成規(guī)則。他們認(rèn)為合成規(guī)則的歸一化操作導(dǎo)致高沖突證據(jù)融合時(shí)結(jié)論不合理，需要修改合成規(guī)則。以文獻(xiàn)[4]去掉歸一化操作的方法為代表，后有文獻(xiàn)[5]的統(tǒng)一信度函數(shù)組合方法，文獻(xiàn)[6]把產(chǎn)生矛盾的因素作為變量加進(jìn)合成規(guī)則的方法等。

第二類：主要修改證據(jù)集。D?S合成時(shí)對(duì)所有證據(jù)一視同仁，但實(shí)際上每條證據(jù)的可靠程度、重要程度以及影響力大小是不同的。因此，他們主張修改BPA模型[7]，根據(jù)證據(jù)的重要程度修正原始證據(jù)，給不同證據(jù)賦予不同權(quán)系數(shù)，應(yīng)用折扣思想，削弱沖突。以 Murphy平均處理證據(jù)BPA[8]的方法為代表。度量證據(jù)矛盾的方面，沖突因子會(huì)隨著證據(jù)數(shù)量的增長(zhǎng)而增長(zhǎng)，因而不足以準(zhǔn)確度量證據(jù)間的矛盾，因此出現(xiàn)以Jousselme距離[9]（簡(jiǎn)稱J距離）、Pignistic概率距離（Pignistic Probability Distance，簡(jiǎn)稱P距離）等為主的度量辦法，目前，文獻(xiàn)[2，10?11]都認(rèn)為使用沖突因子和P距離共同度量證據(jù)矛盾更合理。此外，還有文獻(xiàn)[3]的優(yōu)化思想、文獻(xiàn)[12]的復(fù)合折扣思想等。endprint

第三類：同時(shí)修改合成規(guī)則和證據(jù)體。如文獻(xiàn)[13]利用P距離構(gòu)造可信度修正證據(jù)體的改進(jìn)合成公式的方法。

三類方案都能一定程度的解決問題，但是修改合成規(guī)則等于剔除了D?S方法的核心靈魂[7，11]。它破壞了合成規(guī)則的結(jié)合律、交換律等性質(zhì)，致使系統(tǒng)無法采取分布式局域運(yùn)算[2]，大大增加了數(shù)據(jù)融合系統(tǒng)的運(yùn)算負(fù)載[12]。就目前形勢(shì)來看，信息融合、目標(biāo)識(shí)別等領(lǐng)域的精確度要求越來越高，為使數(shù)據(jù)融合系統(tǒng)達(dá)到精確度的要求，傳感器數(shù)量、種類都會(huì)大大增加，證據(jù)量也會(huì)有數(shù)量級(jí)的變化，此時(shí)，融合系統(tǒng)降低運(yùn)算負(fù)載會(huì)尤為重要。因此，修正證據(jù)集的思想更為合理。在修正證據(jù)集的方法中，文獻(xiàn)[2?3]方法只考慮衡量矛盾的單個(gè)因素，P距離雖然比J距離清晰、時(shí)間復(fù)雜度低[13]，卻對(duì)證據(jù)間矛盾的細(xì)小變化不敏感，況且所有方法若僅一次融合就決策容易因合成結(jié)果不精確產(chǎn)生偏差[2]，文獻(xiàn)[12]方法計(jì)算過程因使用J距離，因此時(shí)間復(fù)雜度高。

本文針對(duì)上述問題，提出一種改進(jìn)的算法，該算法主要是利用沖突因子和證據(jù)間的P函數(shù)向量余弦共同度量證據(jù)的矛盾大小，轉(zhuǎn)化矛盾系數(shù)為權(quán)系數(shù)；經(jīng)過修正替換和權(quán)系數(shù)修正二次修正證據(jù)集，增加證據(jù)集的可靠性，用迭代的方式修正融合結(jié)果，提高融合結(jié)果的精確度，便于做出準(zhǔn)確決策。結(jié)果表明，該算法快速有效并且融合結(jié)果更準(zhǔn)確。

1 經(jīng)典D?S方法

完整實(shí)現(xiàn)經(jīng)典D?S方法共有三步：

1） 構(gòu)造識(shí)別框架。它是一個(gè)有限集合并且其中的元素兩兩相互獨(dú)立，表示論域中所有可能命題的集合。識(shí)別框架內(nèi)的命題都用的子集表示，的所有子集表示的命題集合就是冪集，于是對(duì)命題的研究就轉(zhuǎn)化為對(duì)集合的研究。

2） 建立概率分配函數(shù)（Basic Probability Assignment，BPA）。在上定義如下，滿足是的基本概率數(shù)，顯示對(duì)集合的信賴程度。當(dāng)時(shí)，子集稱為的焦元。

3） 應(yīng)用D?S合成規(guī)則，得到合成結(jié)果。D?S證據(jù)推理的基本運(yùn)算是BPA的正交和。其正交和公式為：

式中沖突因子便于計(jì)算可以寫成：

系數(shù)是為保證時(shí)，。時(shí)，代表和完全無共性，不符合D?S方法的使用條件。

2 改進(jìn)的加權(quán)算法

本文算法分為三部分：

1） 度量證據(jù)集的矛盾大小。

2） 修正證據(jù)集。除首輪融合外，迭代融合的證據(jù)集都經(jīng)過二次修正。

3） 利用D?S合成規(guī)則計(jì)算融合結(jié)果，比較前后兩次融合結(jié)果，當(dāng)滿足終止條件時(shí)，結(jié)束迭代，輸出最終融合結(jié)果。

2.1 度量證據(jù)的矛盾大小

函數(shù)定義為：

，這里是子集的勢(shì)，。描述了BPA對(duì)冪集上各個(gè)命題子集的信賴程度，因此表示支持是真的全部概率。

冪集的BPA以向量形式記作，則從維變?yōu)榫S的函數(shù)向量為：這大大降低了算法的復(fù)雜度。證據(jù)和向量化后，其夾角余弦值為是向量的內(nèi)積，是向量的長(zhǎng)度，。不同的證據(jù)有不同的向量表示[14]，不同的向量之間必然存在夾角，只有完全相同的兩條證據(jù)之間無矛盾，證據(jù)向量間無夾角，余弦函數(shù)在內(nèi)是單調(diào)遞減函數(shù)，因此余弦矛盾直觀地表達(dá)了證據(jù)之間的矛盾。向量距離矩陣為：

根據(jù)式（2）定義沖突系數(shù)矩陣如下：

綜合沖突因子和向量矛盾，矛盾矩陣定義如下：

用矛盾矩陣度量證據(jù)間的矛盾大小，顯然，，越大，表示之間的矛盾越大。

2.2 證據(jù)集修正過程

首次融合只一次權(quán)系數(shù)修正證據(jù)集，二次迭代開始，融合中證據(jù)集都經(jīng)過二次修正。

一次修正：替換修正。一般來說，為減少運(yùn)算量，在數(shù)據(jù)融合中，如果條證據(jù)足夠識(shí)別目標(biāo)，則無需條證據(jù)再融合。而且與第次融合的原始證據(jù)集相比，第次的融合結(jié)果更準(zhǔn)確、更有效、更真實(shí)，可信度更高。因此，用第次融合結(jié)果替換次融合的原始證據(jù)體中沖突最大的證據(jù)非常必要。替換過程如下：

Step1：計(jì)算證據(jù)矛盾系數(shù)為：

Step2：排序則表示證據(jù)為該證據(jù)體中矛盾最大、可靠度最小的證據(jù)。

Step3：用前一次融合結(jié)果替換本次融合時(shí)證據(jù)集中Step2所指向的證據(jù)。

二次修正：權(quán)系數(shù)修正。按照權(quán)系數(shù)修正BPA，公式如下：

其中，權(quán)系數(shù)生成過程如下，構(gòu)造可靠矩陣為：

證據(jù)的可靠系數(shù)是，排序，其中表示證據(jù)為證據(jù)體中可信度最高的證據(jù)，稱為關(guān)鍵證據(jù)，證據(jù)體的可靠度規(guī)范化處理以后為：

式中稱為該證據(jù)的權(quán)系數(shù)。

2.3 算法的迭代過程

迭代階段權(quán)重的生成方法如下：

輸入：辨識(shí)框架冪集證據(jù)集及其對(duì)應(yīng)的BPA是閾值

首次融合過程如下：

Step1：根據(jù)求權(quán)式（7）求出首次的權(quán)系數(shù)其中。

Step2：把代入修正式（6）中獲得修正后的BPA。

Step3：將代入D?S合成式（1）中，得到首次融合結(jié)果。

第次迭代過程：

Step1：構(gòu)造第次融合的證據(jù)集。用替換修正證據(jù)集。

Step2：計(jì)算新的權(quán)系數(shù)。

Step3：計(jì)算修正后BPA。

Step4：計(jì)算第次融合結(jié)果。

Step5：判斷終止條件。計(jì)算與的間距是否小于等于計(jì)算公式為：

如果則輸出否則繼續(xù)迭代。

輸出：最終確定的融合結(jié)果。

3 算例分析

3.1 公共算例驗(yàn)證

為驗(yàn)證本文算法的有效性，本文首先計(jì)算一個(gè)經(jīng)典的算例便于與其他文獻(xiàn)當(dāng)中的算法對(duì)比分析，結(jié)果如表1所示，本文算法的閾值。識(shí)別框架其中為三個(gè)目標(biāo)，現(xiàn)在有五條證據(jù)BPA如下：

文獻(xiàn)各個(gè)算法合成算法的融合結(jié)果如表1所示，各個(gè)目標(biāo)合成結(jié)果圖分別如圖1～圖3所示。endprint

對(duì)比表1和圖1～圖3分析得出：經(jīng)典D?S方法的合成規(guī)則在合成高沖突證據(jù)時(shí)失效，一直是0，雖然五條證據(jù)中，只有第二條證據(jù)的是0。文獻(xiàn)[8]方法融合結(jié)果有效，但也僅僅是對(duì)證據(jù)做平均處理，并未涉及到證據(jù)之間的相關(guān)性，因此圖形呈波浪折線狀。文獻(xiàn)[12]方法融合結(jié)果前期跳躍較大，圖1，圖2中表現(xiàn)尤為明顯，后期快速逼近真實(shí)結(jié)果，證明其迭代思想的正確性。文獻(xiàn)[2，11]方法都采用沖突因子和P距離相結(jié)合共同度量矛盾的方法，因此圖形走勢(shì)平緩趨近真實(shí)值，這兩種算法融合結(jié)果合理，只一次融合不精確。本文算法迭代時(shí)二次修正證據(jù)集，同時(shí)修正融合結(jié)果，因此圖形平緩且快速逼近真實(shí)值。分析發(fā)現(xiàn)，本文算法保留了經(jīng)典算法的數(shù)學(xué)特性帶來的局域運(yùn)算，保證了經(jīng)典算法系統(tǒng)運(yùn)算時(shí)原有的低負(fù)載，在度量矛盾時(shí)將向量從維變?yōu)榫S，再次降低了運(yùn)算負(fù)載。對(duì)融合結(jié)果采用迭代修正的方式修正融合結(jié)果，提高了融合結(jié)果的精確度，保證了決策的正確率。

3.2 隨機(jī)算例驗(yàn)證

為證明本文算法的通用性，計(jì)算一組隨機(jī)算例：某患者臨床癥狀表現(xiàn)為發(fā)燒、咳嗽、肌肉酸痛等，四位醫(yī)生對(duì)其初診后認(rèn)為患者可能是感冒，甲型H1N1流感病毒性肝炎。則識(shí)別框架閾值初診結(jié)果的BPA表示如下：

應(yīng)用本文算法得到的融合結(jié)果如表2所示，融合結(jié)果如圖4所示。

從隨機(jī)算例分析融合結(jié)果以及融合結(jié)果圖4可以看出，融合結(jié)果對(duì)支持的目標(biāo)隨著參與融合的證據(jù)數(shù)量的增大而增大，漲速快，如的圖線走勢(shì)，表明該患者應(yīng)確診為病毒性肝炎；對(duì)不支持的目標(biāo)隨著參與融合的證據(jù)數(shù)量的增大而減小，減速也快，如的圖線走勢(shì)，表示盡快排除了患者患甲型H1N1流感的可能。融合結(jié)果支持目標(biāo)和不支持目標(biāo)的融合結(jié)果差異較大，能盡快確診病情。本文算法收斂速度快，迭代次數(shù)也合理，時(shí)間復(fù)雜度卻沒有級(jí)別變化，融合結(jié)果更加精確。

4 結(jié) 語(yǔ)

對(duì)造成D?S方法使用受限的原因分析后，針對(duì)高頻問題提出一種基于沖突因子和Pignistic概率向量余弦的迭代D?S加權(quán)算法，利用沖突因子和Pignistic概率向量余弦共同度量證據(jù)間的矛盾大小并轉(zhuǎn)化為證據(jù)的可靠度從而計(jì)算出證據(jù)的權(quán)重系數(shù)，將權(quán)重系數(shù)代入D?S合成規(guī)則得到融合結(jié)果，第一次修正證據(jù)集是用前一次融合結(jié)果替換后一次融合的證據(jù)中矛盾最大可靠度最小的一條證據(jù)，使每一次合成結(jié)果發(fā)揮最大的價(jià)值。第二次利用權(quán)系數(shù)再次修正。對(duì)融合結(jié)果利用迭代的概念不斷修正從而獲得更精準(zhǔn)的融合結(jié)果，確保決策的正確率。分析算例融合結(jié)果發(fā)現(xiàn)，本文算法收斂速度快，運(yùn)算速度高，融合結(jié)果精確，有效地突破D?S方法的使用限制，擴(kuò)大了其適用范圍。

參考文獻(xiàn)

[1] 王欣.多傳感器數(shù)據(jù)融合問題的研究[D].長(zhǎng)春：吉林大學(xué)，2006.

WANG Xin. The research on mulisensor data fusion [D]. Changchun： Jilin University， 2006.

[2] 肖建于，童敏明，朱昌杰，等.基于Pignistic概率距離的改進(jìn)證據(jù)組合規(guī)則[J].上海交通大學(xué)學(xué)報(bào)，2012，46（4）：636?641.

XIAO Jianyu， TONG Minming， ZHU Changjie， et al. Improved combination rule of evidence based on Pignistic probability distance [J]. Journal of Shanghai Jiao Tong University， 2012， 46（4）： 636?641.

[3] 陳圣群，王應(yīng)明.基于Pignistic概率距離的最優(yōu)證據(jù)合成法[J].信息與控制，2013，42（2）：213?217.

CHEN Shengqun， WANG Yingming. Optimal combination of evidence based on Pignistic probability distance [J]. Information and control， 2013， 42（2）： 213?217.

[4] YAYER R. On the Dempster?Shafer framework and new combination rules [J]. Information sciences， 1987， 41： 93?137.

[5] LEFEVRE E， COLOT O. Belief function combination and conflict management [J]. Information fusion， 2002， 3（3）： 149?162.

[6] 王棟，李齊，蔣雯，等.基于Pignistic概率距離的沖突證據(jù)合成方法[J].紅外與激光工程，2009，38（1）：149?154.

WANG Dong， LI Qi， JIANG Wen， et al. New method to combine conflict evidence based on Pignistic probability distance [J]. Infrared and laser engineering， 2009， 38（1）： 149?154.

[7] HAENNI R. Are alternatives to Dempster′s rule of combination real alternative comments on ″about the belief function combination and the conflict management problem″ [J]. Information fusion， 2002， 3（4）： 237?239.endprint

[8] MURPHY C K. Combining belief functions when evidence conflicts [J]. Decision support systems， 2000， 29（1）： 1?9.

[9] JOUSSELME A L. A new distance between two bodies of evidence [J]. Information fusion， 2001， 2（1）： 91?101.

[10] 李昌璽，周焰，張晨，等.結(jié)合沖突系數(shù)與pignistic概率距離的沖突度量方法[J].空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，17（2）：91?97.

LI Changxi， ZHOU Yan， ZHANG Chen， et al. A new evidence conflict measurement method combined with conflict coefficient and Pignistic probability distance [J]. Journal of Air Force Engineering University （natural science edition）， 2016， 17（2）： 91?97.

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

HUANG Jianzhao， XIE Jian， LI Liang， et al. Improved combination method of evidence based on conflict coefficient and Pignistic probability distance [J]. Transducer and microsystem technologies， 2013， 32（9）： 21?24.

[12] 胡海亮，鐘求喜，劉瀏.基于迭代合成的D?S證據(jù)理論改進(jìn)方法[J].計(jì)算機(jī)應(yīng)用與研究，2016，33（10）：2985?2987.

HU Hailiang， ZHONG Qiuxi， LIU Liu. Improved method to D?S evidence theory based on iterative synthesis [J]. Computer application and research， 2016， 33（10）： 2985?2987.

[13] 馬麗麗，張芬，陳金廣.一種基于Pignistic概率距離的合成公式[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（24）：61?66.

MA Lili， ZHANG Fen， CHEN Jinguang. Synthetic rule of evidence based on Pignistic probability distance [J]. Computer engineering and applications， 2015， 51（24）： 61?66.

[14] 胡嘉驥，李新德，王豐羽.基于夾角余弦的證據(jù)組合方法[J].模式識(shí)別與人工智能，2015，28（9）：857?864.

HU Jiaji， LI Xinde， WANG Fengyu. Evidence combination method based on include angle cosine [J]. PR&AI， 2015， 28（9）： 857?864.

[15] 費(fèi)翔，周健.一種處理沖突證據(jù)的D?S證據(jù)權(quán)重計(jì)算方法[J].計(jì)算機(jī)工程，2016，42（2）：142?145.

FEI Xiang， ZHOU Jian. A D?S evidence weight computing method for conflict evidence [J]. Computer engineering， 2016， 42（2）： 142?145.endprint