基于三支決策的證據(jù)融合策略

陳 緣,王加陽

(中南大學(xué) 計(jì)算機(jī)學(xué)院,長沙 410083)

1 引 言

隨著海量不確定性數(shù)據(jù)出現(xiàn),如何處理并探尋這些數(shù)據(jù)中蘊(yùn)含的知識已成為一個熱點(diǎn)課題.證據(jù)理論的提出和發(fā)展[1,2]豐富了處理不確定性問題的方法,在智能決策、目標(biāo)優(yōu)化、故障檢測和統(tǒng)計(jì)分析等領(lǐng)域發(fā)揮了不可替代的作用[3-7].證據(jù)合成是證據(jù)理論的重要部分,對于來源不同的證據(jù),往往因其主要支持的焦元不同而產(chǎn)生沖突.當(dāng)證據(jù)之間存在沖突時,直接使用D-S規(guī)則進(jìn)行合成常會產(chǎn)生證據(jù)悖論[8-10].針對這一問題,許多學(xué)者對沖突證據(jù)合成方法進(jìn)行了大量研究和改進(jìn),這些方法大致可分為以下兩類:

一類是對組合規(guī)則進(jìn)行修正,由此產(chǎn)生了許多新的組合規(guī)則.其中有的學(xué)者在改進(jìn)的組合規(guī)則中考慮如何分配沖突量[11-13].Wang等[14]對相似性碰撞進(jìn)行分析和說明,并提出一種新的組合規(guī)則.Du等[15,16]提出依賴于主客觀的的廣義組合規(guī)則.但這些組合規(guī)則可能會破壞交換律和結(jié)合律等數(shù)學(xué)特性,當(dāng)待融合的證據(jù)較多時,結(jié)果可能會有較大偏差.

另一類是對證據(jù)源進(jìn)行修正,關(guān)鍵在于如何確定證據(jù)的折扣系數(shù).通常是通過度量證據(jù)不確定性,以及計(jì)算證據(jù)相似系數(shù)、證據(jù)距離等來確定折扣系數(shù).Jousselme等[17]通過冪集空間上的序列向量計(jì)算證據(jù)距離;Yu等[18]定義了一種支持概率距離,以證據(jù)的被支持度確定其折扣系數(shù);陳哲等[19]通過構(gòu)建沖突關(guān)系網(wǎng)絡(luò),利用PageRank算法來修正證據(jù)權(quán)值;Xiao[20]通過衡量證據(jù)的各種可信度來修正權(quán)重;Xiong[21]等通過研究證據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的直接和間接互動來實(shí)現(xiàn)權(quán)值修正.但上述方法或多或少存在局限性:有的方法簡單地將證據(jù)之間的關(guān)系分為沖突和不沖突兩種,可能會出現(xiàn)劃分錯誤的情況;有的方法在處理高沖突證據(jù)時能夠取得很好的合成效果,但當(dāng)合成證據(jù)彼此沖突較小時,可能會引入不必要的計(jì)算量.究其原因,在于前者對于介于沖突和不沖突之間的證據(jù)關(guān)系沒有進(jìn)行深入的探討,僅通過人為確定的單一閾值無法對證據(jù)間的復(fù)雜關(guān)系進(jìn)行確切區(qū)分.后者則無法有效判斷證據(jù)是單類還是多類[22],在融合單類證據(jù)時有殺雞牛刀之嫌,無法避免其過程復(fù)雜和計(jì)算量大的缺陷.

三支決策模型[23,24]作為對傳統(tǒng)二支決策的推廣和拓展,通過引入延遲決策的概念來規(guī)避當(dāng)前因?yàn)榭捎眯畔⒉蛔銕淼娘L(fēng)險(xiǎn)[25],在數(shù)據(jù)采樣、自動聚類等方面[26,27]得到了實(shí)際應(yīng)用.利用三支決策模型,能夠更好地對證據(jù)之間的沖突和一致性進(jìn)行說明,并可以為證據(jù)的劃分提供理論支持.為此,本文提出一種基于三支決策的證據(jù)融合策略,來實(shí)現(xiàn)證據(jù)沖突的分而治之.該策略能夠根據(jù)證據(jù)的焦元特征快速辨別證據(jù)關(guān)系,進(jìn)而根據(jù)沖突大小采用不同的合成態(tài)度和策略.并通過證據(jù)集來合并具有一致性的證據(jù),避免了傳統(tǒng)方法中對證據(jù)距離或關(guān)系的逐次比較.與現(xiàn)有方法相比,本文方法采用更為靈活變通的方式來融合證據(jù),在充分利用證據(jù)信息的情況下能夠減少計(jì)算量,為證據(jù)融合方法提供一種新的思考角度和方式.

接下來,本文將概述證據(jù)理論和三支決策的相關(guān)知識,并分析如何應(yīng)用三支決策思想去看待證據(jù)之間的沖突關(guān)系,在此基礎(chǔ)上提出基于三支決策的證據(jù)融合策略:首先確定每個證據(jù)支持的主要焦元,從支持的焦元是否相同的角度看待證據(jù)與證據(jù)集關(guān)系,構(gòu)建三支決策證據(jù)關(guān)系模型將證據(jù)劃分到對應(yīng)的證據(jù)集中或邊界上.接著,對證據(jù)集內(nèi)部的證據(jù)使用D-S規(guī)則合成,對證據(jù)集的合成結(jié)果和邊界證據(jù)使用不同的規(guī)則進(jìn)行權(quán)值修正,然后統(tǒng)一進(jìn)行合成.最后,結(jié)合多源證據(jù)融合實(shí)例,與其他融合規(guī)則進(jìn)行對比分析,來說明本文方法的有效性.

2 相關(guān)概念

2.1 三支決策模型

Yao[23,24]基于貝葉斯最小風(fēng)險(xiǎn)理論和決策粗糙集理論,提出了三支決策模型:給定一個S=的決策表,U表示論域?yàn)榉强沼邢藜?C為條件屬性集,j5i0abt0b表示為決策屬性.對于X?U,構(gòu)造狀態(tài)空間Ω={X,～X}來表示對象是否屬于集合X,并構(gòu)造集合AC={aP,aN,aB}來分別表示3種決策動作:接受、拒絕和延遲決策.不同條件下采取不同行動對應(yīng)的代價函數(shù)如表1所示.

表1 不同行動的代價函數(shù)

如表1所示,當(dāng)一個對象屬于集合X時,采取動作aP,aB,aN對應(yīng)的代價分別為λPP,λBP,λNP;當(dāng)一個對象不屬于集合X時,采取動作aP,aB,aN對應(yīng)的代價分別為λPN,λBN,λNN.當(dāng)一個對象屬于集合X時,代價函數(shù)通常滿足:λPP≤λBP<λNP,它說明將一個屬于X的對象x劃分到正域POS(X)的代價要小于或等于將其劃分到邊界域BND(X)的代價,而這二者的代價都小于將其劃分到負(fù)域NEG(X)的代價.同理,當(dāng)一個對象不屬于集合X時,代價函數(shù)通常滿足:λNN≤λBN<λPN.

使用P(X|[x]R)表示對象所在的等價類[x]R屬于集合X的條件概率,它的計(jì)算公式為:

(1)

對于一個對象x,采取行動aP,aB,aN的期望代價為:

R(aP|[x]R)=λPPP(X|[x]R)+λPNP(～X|[x]R)

(2)

R(aB|[x]R)=λBPP(X|[x]R)+λBNP(～X|[x]R)

(3)

R(aN|[x]R)=λNPP(X|[x]R)+λNNP(～X|[x]R)

(4)

根據(jù)貝葉斯最小風(fēng)險(xiǎn)決策理論,可得最小代價決策規(guī)則如下:

(P)如果R(aP|[x]R)≤R(aB|[x]R),且R(aP|[x]R)≤R(aN|[x]R),則x∈POS(X)接受決策.

(N)如果R(aN|[x]R)≤R(aB|[x]R),且R(aN|[x]R)≤R(aP|[x]R),則x∈NEG(X)接受決策.

(B)如果R(aB|[x]R)≤R(aP|[x]R),且R(aB|[x]R)≤R(aN|[x]R),則x∈BND(X)接受決策.

2.2 證據(jù)理論

定義1[1,2].設(shè)Θ為識別框架,基本信任分配函數(shù)m是一個從集合2Θ到 [0,1] 的映射,A表示識別框架Θ的任一子集,記作A?Θ,且滿足:

(5)

定義2[1,2].假定識別框架Θ下的兩個證據(jù)E1和E2,其相應(yīng)的質(zhì)量函數(shù)為m1和m2,焦元分別為Ai和Bj,使用D-S合成規(guī)則后合成的質(zhì)量函數(shù)為:

(6)

式中:

K=∑Ai∩Bj=?m1(Ai)m2(Bj)

(7)

它反映了各個證據(jù)之間的沖突程度,系數(shù)1/(1-K)稱為正則化因子.由m給定的質(zhì)量函數(shù)稱為m1和m2的正交和,記作m1⊕m2.

定義3[19].假設(shè)證據(jù)的權(quán)重為w,則對證據(jù)進(jìn)行加權(quán)修正后的質(zhì)量函數(shù)為:

(8)

其中,m(Θ)表示對整個識別框架分配的質(zhì)量函數(shù),m(A)表示對任一焦元分配的質(zhì)量函數(shù).

定義4[28].假設(shè)識別框架上Θ的證據(jù)質(zhì)量函數(shù)為m,則Pignistic概率轉(zhuǎn)化函數(shù)BetPm滿足:

(9)

其中|B|為集合的基數(shù)大小,A為單點(diǎn)集,BetPm將復(fù)合集焦元的信度平均分配給了其包含的單點(diǎn)集焦元.

3 基于三支決策的證據(jù)關(guān)系模型

當(dāng)多個證據(jù)進(jìn)行合成時,證據(jù)沖突產(chǎn)生的主要原因是不同的證據(jù)支持不同的焦元,而傳統(tǒng)D-S規(guī)則無法有效處理證據(jù)之間的高沖突,只適用于沖突相對較小的證據(jù)融合.但是在如何界定證據(jù)之間的高低沖突這一問題上,已有文獻(xiàn)提出的方法常常通過對沖突量設(shè)置閾值來區(qū)分,可能出現(xiàn)劃分錯誤的情況,缺乏對證據(jù)沖突的邊界的深入分析和討論.證據(jù)之間的沖突關(guān)系不應(yīng)簡單地概括為“沖突”和“一致”兩種,介于“沖突”和“一致”之間的關(guān)系同樣值得討論:這說明證據(jù)之間既存在無法避免的沖突,也存在不可忽視的一致性.換而言之,證據(jù)之間可以保持“中立”關(guān)系.

3.1 模型的建立

證據(jù)的合成結(jié)果本質(zhì)上是證據(jù)在不同焦元上的拉鋸,當(dāng)證據(jù)支持的焦元趨向于一致時,對應(yīng)的沖突也就越小,因而可從證據(jù)支持的焦元集合是否相同來判定證據(jù)之間的關(guān)系.

假設(shè)識別框架Θ={x1,…,xn},構(gòu)造狀態(tài)集合AC={aU,aN,aC}來分別表示3種證據(jù)關(guān)系:一致的(Uniform),中立的(Neutral)和沖突的(Conflicting),E表示當(dāng)前證據(jù)支持的焦元集合,～E表示當(dāng)前證據(jù)不支持的焦元集合,～E是E在識別框架Θ上的補(bǔ)集.證據(jù)與當(dāng)前證據(jù)支持的焦元集合E一致時,判定證據(jù)關(guān)系aU,aN,aC對應(yīng)的代價分別為λUU,λNU,λCU;證據(jù)與當(dāng)前證據(jù)支持的焦元集合E不一致時,判定證據(jù)關(guān)系aU,aN,aC對應(yīng)的代價分別為λUU,λNU,λCU.綜上,在不同條件下對證據(jù)的不同關(guān)系進(jìn)行判定的代價如表2所示.

表2 判定證據(jù)不同關(guān)系的代價函數(shù)

值得注意的是,代價函數(shù)需滿足:λUU≤λNU<λCU,它說明將一個與E一致的證據(jù)劃分到一致域UNI(E)的代價要小于或等于將其劃分到中立域NEU(E)的代價,而這二者的代價都小于將其劃分到?jīng)_突域CON(E)的代價.同理,后者的代價函數(shù)需滿足:λCC≤λNC<λUC,它說明將一個與E沖突的證據(jù)劃分到?jīng)_突域CON(E)的代價要小于或等于將其劃分到中立域NEU(E)的代價,而這二者的代價都小于將其劃分到一致域UNI(E)的代價.

同時,記P(e,E)為證據(jù)e與當(dāng)前證據(jù)支持的焦元集合E一致的概率,記P(e,～E)表示證據(jù)e與當(dāng)前證據(jù)支持的焦元集合E不一致的概率,也即e與焦元集合～E一致的概率.結(jié)合表2,判定證據(jù)e與當(dāng)前證據(jù)支持的焦元集合E的證據(jù)關(guān)系時,采取行動aU,aN,aC的期望代價分別為:

R(aU)=λUUP(e,E)+λUCP(e,～E)

(10)

R(aN)=λNUP(e,E)+λNCP(e,～E)

(11)

R(aC)=λCUP(e,E)+λCCP(e,～E)

(12)

根據(jù)貝葉斯最小風(fēng)險(xiǎn)決策理論,可得最小代價的行動規(guī)則如下:

(U)如果R(aU)≤R(aN)且R(aU)≤R(aC),則采取行動aU,認(rèn)為證據(jù)之間是一致的.

(C)如果R(aC)≤R(aN)且R(aC)≤R(aU),則采取行動aC,認(rèn)為證據(jù)之間是沖突的.

(N)如果R(aN)≤R(aU)且R(aN)≤R(aN),則采取行動aN,認(rèn)為證據(jù)之間是中立的.

3.2 一致概率的計(jì)算

當(dāng)多個證據(jù)進(jìn)行合成時,其合成結(jié)果可以看作是它們在焦元上的拉鋸和博弈,所以問題的關(guān)鍵在于如何確定各個證據(jù)支持的主要焦元.而證據(jù)間的一致性也表現(xiàn)在它們對各個主要焦元的支持度,同時應(yīng)忽略非主要焦元的影響.

首先為得到證據(jù)e支持的主要焦元集為FSe,需要區(qū)分證據(jù)的主要焦元,而非焦元.此時需要考慮兩個方面的問題:其一是避免質(zhì)量函數(shù)過小的焦元被誤判為主要焦元,其二是為使集合形式更為精簡,需要將復(fù)合集焦元的信度平均分配給單點(diǎn)集焦元.下面通過兩個例子說明這兩個問題的必要性.

例1.假設(shè)識別框架Θ={A,B,C,D},某個證據(jù)的質(zhì)量函數(shù)為:m({A})=0.3,m({B})=0.3m({A,B})=0.3,m({C})=0.05,m({D})=0.05.可以看出證據(jù)對{C}和{D}的相對信任度比較小,故{C}和{D}不應(yīng)納入主要焦元的范疇,即避免質(zhì)量函數(shù)過小的焦元被當(dāng)成主要焦元.

例2.假設(shè)識別框架Θ={A,B,C,D},某個證據(jù)的主要焦元集合FS={{A},{B},{A,B}},而當(dāng)前證據(jù)集支持的主要焦元集為{{A},{B}},正因?yàn)閺?fù)合集焦元的存在,難以考量二者的主要焦元的重疊部分該如何計(jì)算,若將復(fù)合集焦元的信度平均分配給單點(diǎn)集焦元,則有利于問題的簡化,同時,主要焦元集合可能包含的元素個數(shù)將會從24個縮小到4個,且元素之間不重疊,更具有合理性.

因此,為避免復(fù)合集焦元對區(qū)分主要焦元的干擾,應(yīng)先將對復(fù)合集焦元的信度平均分配給單點(diǎn)集焦元,即使用Pignistic概率轉(zhuǎn)化函數(shù)實(shí)現(xiàn)復(fù)合集焦元到單點(diǎn)集焦元的轉(zhuǎn)化,再盡量避免質(zhì)量函數(shù)過小的焦元被誤判為主要焦元.而大津法能夠?qū)?shù)據(jù)分成兩類,使它們的類間方差最大,這與區(qū)分主要焦元和非主要焦元的思想不謀而合,但是當(dāng)數(shù)據(jù)差別不大時,大津法可能不會取得很好的效果.從另一方面來說,信度越大的焦元為主要焦元的可能性越大,而信度最大的焦元一定為主要焦元,可以通過信度之間的比值來確定其他的主要焦元.據(jù)此本文設(shè)計(jì)了以下算法來區(qū)分主要焦元.

算法1.區(qū)分證據(jù)主要焦元集合算法.

輸入：識別框架Θ={x1,x2,…,xn},證據(jù)質(zhì)量函數(shù)m.

輸出：證據(jù)的主要焦元集合FS.

1.輸入質(zhì)量函數(shù),并根據(jù)Pignistic概率轉(zhuǎn)化公式計(jì)算BetPm(xi)的值,i=1,2,…,n.

2.在BetPm找到最大值max和非零最小值min.

3.如果max/min≥k,(k是常數(shù),通常k≥3)則轉(zhuǎn)到步驟 4 ;否則轉(zhuǎn)至步驟 5.

4.設(shè)置區(qū)分主要焦元的閾值Th為min,并轉(zhuǎn)至步驟 9.

5.對BetPm(xi),i=1…n從小到大排序,得到序列L={l1,…,ln},并計(jì)算它們的平均值avgΘ,并初始化j=1.

6.將序列L分為兩類:L1={l1,…,lj},L2={lj+1,…,ln}.分別計(jì)算L1和L2的平均值avg1和avg2.根據(jù)公式[29]σ2=j(avg1-avgΘ)2+(n-j)(avg2-avgΘ)2計(jì)算此時的類間方差,并保留在數(shù)組var中第j個位置.

7.判斷j和n的大小關(guān)系,若j

8.在數(shù)組var中尋找最大類間方差,以及它所對應(yīng)的位置k,將Th設(shè)為lk.

9.對x1,x2,…,xn逐一比較BetPm(xi)和Th的大小,若BetPm(xi)>Th,則將xi加入到FS中.

10.算法結(jié)束,輸出證據(jù)的主要焦元集合FS.

經(jīng)典三支決策模型使用P(X|[x]R)來描述對象所在的等價類[x]R屬于集合X的條件概率,但在基于三支決策的證據(jù)關(guān)系模型中,不宜繼續(xù)使用條件概率,其主要原因有兩個:1)條件概率本質(zhì)上是描述在某一事件已發(fā)生的條件下另一事件發(fā)生的概率,而除時序證據(jù)之外,證據(jù)之間并無先來后到之說;2)證據(jù)關(guān)系是對稱的,但條件概率的計(jì)算方式使其無法實(shí)現(xiàn)對稱性.本文認(rèn)為證據(jù)e與當(dāng)前證據(jù)支持的焦元集合E的一致性表現(xiàn)在它們是否支持同樣的焦元,同時應(yīng)忽略非主要焦元的影響,故通過焦元集合之間的相似度[10]來計(jì)算二者一致的概率,即:

(13)

式中FSe表示證據(jù)e支持的主要焦元集合.

3.3 代價函數(shù)的設(shè)置

對證據(jù)關(guān)系進(jìn)行不同的判定會有對應(yīng)的代價,判定結(jié)果更符合證據(jù)之間關(guān)系的本質(zhì),代價則越小,反之,代價則越高.

當(dāng)證據(jù)e支持的主要焦元集FSe與當(dāng)前證據(jù)支持的主要焦元集合E越接近時,可以認(rèn)為二者的一致性越高,而認(rèn)為二者一致的代價也就越小.問題的關(guān)鍵轉(zhuǎn)化為如何確定集合之間的距離.

定義5.在識別框架Θ={x1,x2,…,xn}上,使用向量V={v1,v2,…,vn}來表示證據(jù)支持的焦元集合,當(dāng)vi=1表示證據(jù)支持第i個焦元,反之當(dāng)vi=0表示不支持.

由此,集合之間的距離可以轉(zhuǎn)化為向量之間的距離,本文使用歐式距離來計(jì)算集合距離d(FSe,E):

(14)

(15)

(16)

(17)

(18)

(19)

(20)

3.4 證據(jù)關(guān)系對融合策略的影響

事實(shí)上,不同的證據(jù)關(guān)系正對應(yīng)了不同的融合態(tài)度,應(yīng)而可采取不同的融合策略.例如當(dāng)判定證據(jù)關(guān)系為aU,可以采用相對簡單的融合策略來提高融合效率;當(dāng)證據(jù)關(guān)系為aC時,說明證據(jù)之間不宜直接進(jìn)行融合.

當(dāng)證據(jù)關(guān)系為aU時,證據(jù)的融合規(guī)則應(yīng)滿足交換律和結(jié)合律,這樣當(dāng)多個具有一致性的證據(jù)進(jìn)行融合時,證據(jù)融合的先后順序不會影響最后融合的結(jié)果.同時,因?yàn)榇藭r待融合的證據(jù)傾向于支持相同的焦元,證據(jù)的融合規(guī)則應(yīng)盡可能簡單,使得計(jì)算速度盡可能快.D-S組合規(guī)則滿足交換律和結(jié)合律,同時運(yùn)算規(guī)則較簡單,可作為此時的融合備選方案.

當(dāng)證據(jù)關(guān)系為aC時,比較激進(jìn)的策略是不予以融合,例如在時序證據(jù)融合過程中常會舍棄與當(dāng)前證據(jù)存在高沖突的證據(jù).其他的策略可選擇對沖突證據(jù)進(jìn)行加權(quán)修正后再進(jìn)行融合,若無法確定孰輕孰重,可各分配1/2的權(quán)重.

當(dāng)證據(jù)關(guān)系為aN時,表明證據(jù)之間存在一致性同時也存在不可忽略的證據(jù)沖突,當(dāng)前可用信息不足,可暫緩融合過程,待更多證據(jù)加入后再進(jìn)行融合.若必須進(jìn)行融合,可根據(jù)證據(jù)本身的不確定性或其他特性來修正權(quán)重再進(jìn)行融合.

4 基于三支決策的證據(jù)融合策略

上一節(jié)中本文對基于三支決策的證據(jù)沖突情況進(jìn)行了分析,把證據(jù)之間的關(guān)系分為一致、中立和沖突三種.當(dāng)有多個證據(jù)進(jìn)行融合時,如何根據(jù)證據(jù)的關(guān)系,采取不同且合適的合成策略是本文研究的重點(diǎn).為此,本文提出了基于三支決策的證據(jù)融合策略:首先根據(jù)各個證據(jù)支持的主要焦元確定初始證據(jù)集上的焦元分布.接著應(yīng)用基于三支決策的證據(jù)關(guān)系模型來判斷證據(jù)與各初始證據(jù)集的關(guān)系.當(dāng)證據(jù)與某初始證據(jù)集為一致關(guān)系時,將其劃分到證據(jù)集內(nèi)部;為中立關(guān)系時,劃分到證據(jù)集邊界上;為沖突關(guān)系時,劃分到證據(jù)集外部.通過將證據(jù)劃分到不同證據(jù)集內(nèi)部或邊界來確定其權(quán)重,最后對加權(quán)證據(jù)進(jìn)行融合.

4.1 初始證據(jù)集上的焦元分布

多個證據(jù)中可能存在支持相同主要焦元的證據(jù),這些傾向于支持同樣焦元的證據(jù)便組成了證據(jù)集.當(dāng)需要融合多個證據(jù)時,大部分證據(jù)源修正改進(jìn)法需要逐一計(jì)算證據(jù)兩兩之間的某種距離或關(guān)系,而本文方法使用證據(jù)集來合并具有一致性的證據(jù),將證據(jù)與證據(jù)的關(guān)系轉(zhuǎn)化為證據(jù)與證據(jù)集的關(guān)系:證據(jù)可能屬于某一證據(jù)集,也可能與證據(jù)集保持中立,而證據(jù)集之間彼此沖突.這種轉(zhuǎn)化的關(guān)鍵在于如何確定初始證據(jù)集及其焦元分布.

沿用前節(jié)3.2中的算法1,可得單個證據(jù)的主要焦元.當(dāng)多證據(jù)融合時,便可根據(jù)這些證據(jù)的主要焦元確定初始證據(jù)集,進(jìn)而利用證據(jù)集歸并具有一致性的證據(jù).為此,本文設(shè)計(jì)了如下算法來確定初始證據(jù)集上的焦元分布.

算法2.確定初始證據(jù)集上的焦元分布.

輸入：m個證據(jù)的主要焦元集合FS1,…,FSm.

輸出：n個證據(jù)集的集合ES={ES1,…,ESn},ESi為第i個證據(jù)集.

1.初始化i=1,n=1,ES={FS1}.

2.i=i+1,并判斷FSi∩ES的交集是否為空,若為空則n=n+1,并令ESn=FSi,將ESn加入至ES中;否則轉(zhuǎn)至步驟4.

3.判斷FSi∈ES是否成立,若成立,則轉(zhuǎn)至步驟2;否則設(shè)j=1并轉(zhuǎn)至步驟4.

4.判斷j≤n是否成立,若成立轉(zhuǎn)至步驟5;否則令ESn+1=FSi,n=n+1并轉(zhuǎn)至步驟2.

5.判斷FSi=?是否成立,若成立則轉(zhuǎn)至步驟2;否則轉(zhuǎn)至步驟6.

6.判斷ESj∩FSi≠?是否成立,若不成立則直接轉(zhuǎn)至步驟7;否則令ESn+1=ESj-ESj∩FSi,n=n+1,并令ESj=ESj∩FSi,FSi=FSi-ESj,再轉(zhuǎn)至步驟7.

7.j=j+1,并轉(zhuǎn)至步驟4.

8.判斷i和m的大小,若i≤m,則轉(zhuǎn)至步驟2;否則轉(zhuǎn)至步驟9.

9.算法結(jié)束,輸出ES1,…,ESn.

由上述算法2可得初始證據(jù)集上的焦元分布.由于各個初始證據(jù)集包含的焦元并不重疊,可認(rèn)為證據(jù)集之間彼此沖突.值得注意的是,此時得來的初始證據(jù)集內(nèi)部證據(jù)數(shù)量為空,并不包含任一證據(jù).因而需要進(jìn)一步判斷各個證據(jù)與初始證據(jù)集的關(guān)系,以此作為劃分的依據(jù).

4.2 證據(jù)的三支劃分

得到初始證據(jù)集上的焦元分布之后,便可根據(jù)第3節(jié)的基于三支決策的證據(jù)關(guān)系模型來判定每條證據(jù)與證據(jù)集的關(guān)系,以此作為證據(jù)劃分到證據(jù)集時的依據(jù),即:當(dāng)判定證據(jù)與證據(jù)集為一致關(guān)系時,將該證據(jù)分配到證據(jù)集內(nèi)部;判定為中立關(guān)系時,將該證據(jù)劃分到證據(jù)集邊界上;判定為沖突關(guān)系時,則不予劃分.

假定識別框架Θ={x1,…,xn},第i條證據(jù)的主要焦元集合為FSi,第j個證據(jù)集支持的焦元集合為ESj,同樣構(gòu)造集合AC={aU,aN,aC}來分別表示證據(jù)與證據(jù)集的3種關(guān)系:一致、中立和沖突.當(dāng)證據(jù)與證據(jù)集存在一致關(guān)系時,判定證據(jù)關(guān)系aU,aN,aC對應(yīng)的代價分別為λUU,λNU,λCU;存在沖突關(guān)系時,判定證據(jù)關(guān)系aU,aN,aC對應(yīng)的代價分別為λUC,λNC,λCC.

沿用前節(jié)3.1中的建模過程,判定第i條證據(jù)ei和第j個證據(jù)集的關(guān)系時,采取行動aU,aN,aC的期望代價分別為:

R(aU)=λUUP(ei,ESj)+λUCP(ei,～ESj)

(21)

R(aN)=λNUP(ei,ESj)+λNCP(ei,～ESj)

(22)

R(aC)=λCUP(ei,ESj)+λCCP(ei,～ESj)

(23)

式中P(FSi,ESj)表示證據(jù)ej和第j個證據(jù)集的一致概率,通過式(13)計(jì)算而來.～ESj為ESj在識別框架Θ上的補(bǔ)集.λUU,λNU,λCU,λUC,λNC,λCC的計(jì)算則參照式(15)～式(20).

根據(jù)貝葉斯最小風(fēng)險(xiǎn)決策理論,可得最小代價的行動規(guī)則如下:

(U)如果R(aU)≤R(aN)且R(aU)≤R(aC),則認(rèn)為證據(jù)與證據(jù)集之間存在一致,將第i條證據(jù)分配到第j個證據(jù)集內(nèi)部.

(C)如果R(aC)≤R(aN)且R(aC)≤R(aU),則認(rèn)為證據(jù)與證據(jù)集保持中立,將第i條證據(jù)劃分到第j個證據(jù)集邊界上.

(N)如果R(aN)≤R(aU)且R(aN)≤R(aC),則認(rèn)為證據(jù)與證據(jù)集存在沖突,將第i條證據(jù)分配到第j個證據(jù)集外部,也即不予劃分.

當(dāng)證據(jù)被分配到某一證據(jù)集內(nèi)部時,由于證據(jù)集之間彼此沖突,可認(rèn)為該證據(jù)與其他證據(jù)集也存在沖突;當(dāng)證據(jù)被劃分到某一證據(jù)集邊界上時,它可能同樣處于其他證據(jù)集的邊界上.

4.3 證據(jù)的修正與融合

假設(shè)總證據(jù)數(shù)量為k,若根據(jù)本文策略可劃分為a個證據(jù)集ES1,…,ESa和b個邊界證據(jù)E1,…,Eb.對于同一證據(jù)集內(nèi)部的證據(jù),因?yàn)樗鼈冎g存在較高的一致性,即證據(jù)沖突較小,故可以根據(jù)D-S規(guī)則直接進(jìn)行合成,最后得到該證據(jù)集的合成結(jié)果.初始情況下可認(rèn)為每個證據(jù)的權(quán)重均等,均為1/k,證據(jù)集內(nèi)部的證據(jù)數(shù)量越多,說明它的相對可信度越大,也應(yīng)具有更高的權(quán)重,故ESi的權(quán)重wi由該證據(jù)集的大小占總證據(jù)大小的比值來確定,即:

(24)

對于劃分到證據(jù)集邊界上的證據(jù),與之中立的證據(jù)集的權(quán)重有關(guān),并由于被Ej劃分到了證據(jù)集的邊界上,因而分配原證據(jù)集的一半權(quán)重,同時應(yīng)考慮它本身具有的權(quán)重,即:

(25)

最后根據(jù)式(8)對證據(jù)集ESi和邊界證據(jù)Ej進(jìn)行修正,并使用D-S規(guī)則進(jìn)行合成.

4.4 計(jì)算量分析

大部分證據(jù)源修正改進(jìn)法對證據(jù)兩兩之間的距離或某種關(guān)聯(lián)度進(jìn)行衡量,進(jìn)而獲得距離矩陣,而本文方法與這些方法的主要區(qū)別在于以證據(jù)集為單位來判定證據(jù)關(guān)系.而其他方法與本文方法在最后權(quán)值修正和融合時所需要的計(jì)算量變化不大.因此,下面就生成距離矩陣和劃分證據(jù)到證據(jù)集的計(jì)算量進(jìn)行對比分析.

首先對傳統(tǒng)的證據(jù)源修正法進(jìn)行分析,以基于證據(jù)間相關(guān)系數(shù)的沖突證據(jù)合成方法[10](簡稱證據(jù)相關(guān)系數(shù)法)為例.假定待合成的證據(jù)數(shù)量為k,運(yùn)算過程中的加減乘除、交并集、求基數(shù)和比較大小都視為一次運(yùn)算.根據(jù)證據(jù)相關(guān)系數(shù)法中計(jì)算兩個證據(jù)之間相關(guān)系數(shù)的公式,可知求解相關(guān)系數(shù)的計(jì)算量為:

C1=CD+2n+2n·2n+2·(2n-1)+2n·2n+3=11×22n-1-3×n-1+1

(26)

式中:n表示識別框架Θ的基數(shù)大小,CD表示求解矩陣需要的計(jì)算量,文獻(xiàn)[31]中給出了它的值為5×2n-1(2n-1).之后為了得到相似度矩陣,k條證據(jù)之間需要兩兩比較,則證據(jù)相關(guān)系數(shù)法的總計(jì)算量大小為:

CS=k(k-1)C1=k(k-1)(11×22n-1-3×2n-1+1)

(27)

接著對本文方法的計(jì)算量進(jìn)行分析.據(jù)4.1節(jié)可知,確定初始證據(jù)集上焦元分布的計(jì)算量為:

C2=7×2n×n+8n

(28)

式中:n表示識別框架Θ的基數(shù)大小.根據(jù)證據(jù)集的焦元彼此不重疊的特性可知,最多可劃分為n個初始證據(jù)集,此時每個證據(jù)集只支持單焦元.而劃分證據(jù)到證據(jù)集時,需要對二者關(guān)系進(jìn)行判定,每次判定需要的計(jì)算量為:

C3=8n+26

(29)

k條證據(jù)與n個證據(jù)集之間最多需要kn次比較.綜合式(28)～式(29),可知本文算法的總計(jì)算量為:

Cr=C2+knC3=7n·2n+8n(kn+1)+26kn

(30)

綜合式(26)～式(30),對證據(jù)相關(guān)系數(shù)法和本文方法的計(jì)算量進(jìn)行對比,結(jié)果如圖1所示.圖中橫坐標(biāo)表示識別框架的基數(shù)大小,縱坐標(biāo)為計(jì)算量大小(×108).曲線1～4從上至下分別為k=10,8,6,4時使用證據(jù)相關(guān)系數(shù)法的計(jì)算量,曲線5～8分別為k=10,8,6,4時本文方法需要的計(jì)算量.由圖1可知,曲線5～8的增長速率明顯低于曲線1～4,說明本文方法所需要的計(jì)算量遠(yuǎn)小于證據(jù)相關(guān)系數(shù)法.為了便于觀察,對圖1中縱坐標(biāo)表示的計(jì)算量取自然對數(shù)lnC,如圖2所示,可以看出證據(jù)相關(guān)系數(shù)法和本文方法的計(jì)算量的對數(shù),都近似于線性增長.

圖1 證據(jù)相關(guān)系數(shù)法與本文方法計(jì)算量圖

圖2 證據(jù)相關(guān)系數(shù)法與本文方法計(jì)算量的對數(shù)圖

根據(jù)圖1和圖2可知,當(dāng)證據(jù)的數(shù)量一定時,證據(jù)相關(guān)系數(shù)法和本文方法的計(jì)算量都隨著識別框架基數(shù)增大而呈指數(shù)增長,但本文方法的增長速率更慢.當(dāng)識別框架的基數(shù)一定時,二者的計(jì)算量雖然都隨著證據(jù)數(shù)量的增多而增加,但本文方法的增長態(tài)勢隨證據(jù)數(shù)增多而變緩.主要原因在于本文方法的計(jì)算量CT主要集中在C2的指數(shù)部分,此時因證據(jù)數(shù)量變多而新增的計(jì)算量與這一部分相比可以相對忽略.

綜上可知,較于經(jīng)典的對證據(jù)源進(jìn)行修正的改進(jìn)方法,如證據(jù)相關(guān)系數(shù)法,本文方法能有效減少計(jì)算量.并且在識別框架的基數(shù)一定的情況下,當(dāng)證據(jù)數(shù)量增多時,本文算法隨之增加的計(jì)算量相對有限.

5 算例分析

5.1 證據(jù)悖論分析

在疑難雜癥的診斷中往往需要多個專家進(jìn)行綜合會診.專家由于個人經(jīng)驗(yàn)的不同可能會得出不同的診斷結(jié)果.此時可用證據(jù)的質(zhì)量函數(shù)來表示診斷意見,但直接使用D-S規(guī)則對診斷意見進(jìn)行融合,可能會得到有悖常理的結(jié)果進(jìn)而造成醫(yī)療事故.

例3.假設(shè)在某次專家會診中,病人被判斷患上的疾病類型可分為A,B兩種.其中,專家1判定患病類型為A的置信度為1,為B的置信度為0;專家2判定患病類型為B的置信度為1,為A的置信度為0.

該例中,因?yàn)閮蓚€專家的診斷意見完全沖突,無法根據(jù)D-S規(guī)則進(jìn)行合成,又因此時證據(jù)沖突K=1而被稱為全沖突悖論.根據(jù)常理,判斷類型為A和判斷類型為B的信度相同,即:0

例4.假設(shè)病人被判斷患上的疾病類型可分為A,B,C這3種.其中,專家1判定患病類型為A和B的置信度分別為0.9和0.1; 專家2判定患病類型為B和C的置信度分別為0.1和0.9.

該例中,盡管兩個專家對疾病類型B的信任度都很低,但使用DS規(guī)則合成后的結(jié)果對B的信度為1,明顯不合理,被稱為1信任悖論.根據(jù)常理,判斷類型為A和判為C的信度相同,且均大于判為B的信度,即:0

例5.假設(shè)病人被判斷患上的疾病類型可分為A,B,C這3種.其中,專家1判定患病類型為A和B的置信度分別為0.9和0.1;專家2判定患病類型為A、B和C的置信度分別為0.7、0.2和0.1;專家3判定患病類型為A、B和C的置信度分別為0.8、0.1和0.1;專家4判定患病類型為B和C的置信度分別為0.1和0.9.

該例中,若采取D-S規(guī)則進(jìn)行合成,則合成結(jié)果為m(A)=0,m(C)=0,m(B)=1.無論其他專家對A和C的基本信任分配有多大,合成結(jié)果對A和C的基本信任分配均為0 ,被稱為0信任悖論.而4個專家中對疾病類型為A的可信度普遍較高,其次是疾病C,最后是疾病B,因此合成結(jié)果基本合理的標(biāo)準(zhǔn)為:0

對上述算例采用相關(guān)算法進(jìn)行合成.在此選擇了Yager法[32]等其他合成方法,與本文方法進(jìn)行對比,如表3所示.以此來說明本文方法能合理有效處理證據(jù)悖論.

表3 多種方法的沖突證據(jù)合成結(jié)果

由表3可知,經(jīng)典DS規(guī)則無法有效處理證據(jù)悖論.Yager法處理以上3種悖論時分配了大量的信度給全集,合成結(jié)果對于決策缺乏實(shí)際意義.Murphy法能處理全沖突和1信任悖論,但在處理0信任悖論時分配了過多的信度給疾病類型A,存在不合理現(xiàn)象.基于證據(jù)相關(guān)系數(shù)的沖突證據(jù)合成方法和本文方法的結(jié)果都能符合3種悖論的基本合理標(biāo)準(zhǔn).二者在前兩種悖論中的合成結(jié)果幾乎一致,但在處理0信任悖論的結(jié)果略有不同:1)本文方法分配了更多的信度給最有可能的疾病類型A,使結(jié)果更清晰,更有利于疾病診斷; 2)二者都分配了一定的信度給識別框架的全集,但本文方法對全集的信度m(Θ)更小,表明本文方法的不確定性更低.綜上,本文方法更具有合理性.

5.2 多證據(jù)合成分析

例6.復(fù)雜戰(zhàn)場環(huán)境中經(jīng)常需要對多個傳感器獲得的決策判別信息進(jìn)行融合.假設(shè)在某多源信息融合系統(tǒng)中,現(xiàn)有五類傳感器對空中目標(biāo)進(jìn)行偵查識別,得到的識別結(jié)果可分為A,B,C這3種類型.其中,傳感器1分別判定目標(biāo)為類型A,B,C的置信度為0.3、0.2、0.05,判定類型為A或B的置信度為0.4,判定類型為A或C的置信度為0.05.傳感器2分別判定目標(biāo)為類型A,B,C的置信度為0.3、0.3、0.05,判定類型為A或B的置信度為0.3,判定類型為A或C的置信度為0.05.傳感器3分別判定目標(biāo)為類型A,B,C的置信度為0.05、0.1、0.6,判定類型為A或B的置信度為0.05,判定類型為A或C的置信度為0.2.傳感器4分別判定目標(biāo)為類型A,B,C的置信度為0.1、0.05、0.7,判定類型為A或B的置信度為0.05,判定類型為A或C的置信度為0.1.傳感器5分別判定目標(biāo)為類型A,B,C的置信度為0.2、0.2、0.2,判定類型為A或B的置信度為0.2,判定類型為A或C的置信度為0.2.

用證據(jù)的質(zhì)量函數(shù)m1,…,m5分別表示以上5類傳感器的識別結(jié)果.根據(jù)式(9),計(jì)算多個證據(jù)的BetPm值.根據(jù)算法1可以得到m1,…,m5中的主要焦元集合.根據(jù)算法2可將證據(jù)分為兩個初始證據(jù)集ES1,ES2,其支持的主要焦元分別為ES1={A,B}和ES2={C}.分別計(jì)算m1,…,m5與這兩個證據(jù)集的一致概率,以及證據(jù)與對應(yīng)證據(jù)集之間的代價函數(shù).并根據(jù)貝葉斯最小決策風(fēng)險(xiǎn)理論,可知:m1和m2與證據(jù)集ES1存在一致性,m3和m4與另一證據(jù)集ES2存在一致性,而m5與這兩個證據(jù)集中立,劃為邊界證據(jù).

對ES1,ES2證據(jù)集內(nèi)部使用D-S規(guī)則進(jìn)行合成.根據(jù)式(24)計(jì)算可得它們的權(quán)重分別為0.4,0.4.而邊界證據(jù)的權(quán)重根據(jù)式(25)計(jì)算可得,最后使用修改后的D-S合成規(guī)則對它們進(jìn)行合成.同樣使用經(jīng)典D-S規(guī)則和Yager法[32]等其他合成方法對例6中的證據(jù)進(jìn)行合成,得到的結(jié)果如表4所示.

表4 不同方法的證據(jù)合成結(jié)果

在例6中,m1和m2主要支持識別類型為A和B,m3和m4主要支持識別類型為C,而m5對以上3種識別類型都予以支持.從每個焦元的平均可信度來說,C最高,A次之,B最低,因而其合成結(jié)果的合理標(biāo)準(zhǔn)應(yīng)為:m(C)>m(A)>m(B).同時,復(fù)合焦元的信度之和越高,證據(jù)的不確定性越高.根據(jù)以上標(biāo)準(zhǔn)和表4可知,D-S合成規(guī)則和Murphy法不合理,Yager法和證據(jù)相關(guān)系數(shù)法雖滿足該標(biāo)準(zhǔn),但Yager法給焦元B分配了過少的可信度,且給復(fù)合焦元分配了相對較多的可信度,存在不合理.證據(jù)相關(guān)系數(shù)法和本文方法雖都符合以上合理標(biāo)準(zhǔn),但結(jié)果存在以下差異:1)本文方法給單點(diǎn)集焦元分配的信度相對較高,更利于多源信息系統(tǒng)進(jìn)行決策; 2)本文方法對復(fù)合焦元的可信度相對較低,說明本文方法不確定性更低,更具有參考意義.綜上,本文方法更具優(yōu)勢.

6 總 結(jié)

證據(jù)融合方法是證據(jù)理論的重要研究內(nèi)容.現(xiàn)有融合方法能有效處理沖突數(shù)據(jù),但缺乏良好的可伸縮性,以至于在證據(jù)沖突較小時會引入不必要的計(jì)算量.因此,本文首先對證據(jù)之間的沖突關(guān)系進(jìn)行了研究,建立了基于三支決策的證據(jù)關(guān)系模型.該模型利用證據(jù)的主要焦元和貝葉斯最小風(fēng)險(xiǎn)理論來判別證據(jù)之間的關(guān)系,并討論了不同關(guān)系下對應(yīng)的融合策略.其次,當(dāng)多證據(jù)進(jìn)行融合時,提出了基于三支決策的證據(jù)融合策略.該策略以證據(jù)集為單位來歸并具有一致性的證據(jù),避免了證據(jù)之間的逐次比較.通過應(yīng)用三支決策證據(jù)關(guān)系模型來實(shí)現(xiàn)證據(jù)的三支劃分.最后對這些被分配到不同證據(jù)集內(nèi)部和邊界上的證據(jù)進(jìn)行修正與融合.結(jié)果表明,本文方法不僅能有效處理證據(jù)悖論,同時在充分利用證據(jù)信息的情況下能夠減少計(jì)算量,得到合理的結(jié)果.

但本文方法仍存在一些不足:1)初始證據(jù)集的分布對融合結(jié)果可能會產(chǎn)生影響,下一步將改進(jìn)計(jì)算初始證據(jù)集分布的算法; 2)計(jì)算證據(jù)權(quán)重時沒有考慮到證據(jù)自身特性,在后續(xù)工作中可以結(jié)合證據(jù)的不確定性來修正權(quán)重.