基于改進余弦相似度的證據間定向沖突度量方法

毛藝帆,張多林,王　路

(空軍工程大學防空反導學院,陜西 西安 710038)

?

基于改進余弦相似度的證據間定向沖突度量方法

毛藝帆,張多林,王路

(空軍工程大學防空反導學院,陜西 西安 710038)

針對傳統證據沖突度量方法無法區分證據間沖突程度的差異,并且會在特定情況下失效的問題,提出一種基于改進余弦相似度的證據間定向沖突度量方法。通過將支持系數引入余弦相似度模型,使所提方法具有非對稱性,從而能夠區分證據間沖突程度的差異,同時還可解決基本余弦相似度模型不適合處理證據中包含非單子集焦元的問題。實驗結果驗證了所提方法的準確性和有效性。

Dempster-Shafer證據理論; 證據沖突; 沖突度量; 定向; 余弦相似度

0　引　言

證據理論于1967年由文獻[1]首次提出,經過文獻[2]完善和發展,成為系統化的不確定性推理理論,故又名Dempster-Shafer(D-S)理論。D-S理論可在無先驗信息的條件下有效表達和處理不確定信息,在不確定推理[3]和數據融合[4]等領域已得到廣泛應用。

自1986年文獻[5]指出D-S理論無法合成沖突證據開始,國內外大量學者展開對D-S理論改進方法的研究,大體分為兩類[6]:第一類為對D-S組合規則的修改[7-8],通過將沖突重新分配實現;第二類為對證據源的修改[9-10],如文獻[10]所提出的方法:首先計算證據間的沖突程度,如果一個證據與其他證據的沖突程度較小,其將獲得較大的可信度,然后根據證據可信度對證據進行加權平均,最后采用基本D-S組合規則進行證據合成。可見,無論哪種改進方式,首先都必須確定證據間是否存在沖突以及沖突程度的大小,可見,證據沖突度量方法是否準確將直接左右最終結果。

典型證據沖突度量方法主要包括沖突系數[2]、Jousselme證據距離[11]和余弦相似度[12]。通過分析,3類方法主要存在兩方面的問題:

(1)模型都具有對稱性,因而無法區分證據間沖突程度的差異。

(2)模型都會在特定的情況下失效。如后文分析中所指出:對于完全相同的證據,沖突系數的計算結果卻非零,表明證據之間存在沖突;對于完全不同的證據,Jousselme距離的計算結果卻可能不為期望值1,其數值大小與BPA的分散程度有關;余弦相似度則只能處理證據中僅包含單子集焦元的情況。

針對問題1,文獻[13]通過論證指出不確定度低的證據應該更加支持不確定度高的證據,并基于Jousselme證據距離設計了非對稱證據沖突度量方法,但是并沒有解決證據距離失效的問題。針對問題2,文獻[14]對余弦相似度模型進行了修正,解決了余弦相似度模型不適合處理證據中包含非單子集焦元的問題,但本文通過實例分析發現,當證據中僅包含單子集焦元時,修正模型無法退化為基本模型,計算結果會與事實相悖。還有部分學者通過對3類典型方法的結合來克服單一度量方法失效的問題[15-21],如文獻[15]通過對沖突系數和證據距離求平均值來度量證據沖突的大小,但通過分析,這些改進方法無法從根本上解決各自模型會在特定情況下失效的問題,并且在模型的組合方式上受主觀因素影響較大。

為定向度量證據間的沖突程度,并解決傳統方法失效的問題,本文在分析典型沖突度量方法不足的基礎上,提出了一種基于改進余弦相似度的證據沖突度量方法,該方法通過將支持系數引入余弦相似度模型,不但使所提方法具有非對稱性,而且解決了余弦相似度模型無法有效處理證據中包含非單子集焦元的問題。實驗結果驗證了所提方法的有效性。

1　典型沖突度量方法分析

證據理論的基本概念以及合成規則可參閱相關文獻,這里不再贅述。

1.1沖突系數

在經典證據理論中,沖突系數k被用來描述證據之間的沖突程度,k值越大,沖突程度越大,其定義如下:

定義1(沖突系數)假設識別框架Θ下兩組獨立證據體的BPA為m1(·)、m2(·),沖突系數的計算公式為

(1)

首先可以看出,沖突系數具有對稱性,即k(m1,m2)=k(m2,m1),因此k無法區別證據間相互沖突程度的差異;其次,沖突系數反應的是識別框架焦元之間的非相互包含程度,只要兩證據中存在非相互包含焦元,則沖突必然存在,因此會帶來例1所示問題。

例1假設識別框架Θ={θ1,θ2}下兩獨立證據體的BPA為

由兩證據體BPA可見,這是兩個完全相同的證據,沖突程度理應為零,然而由于證據體1中的焦元θ1與證據體2中的焦元θ2非相互包含,證據體1中的焦元θ2與證據體2中的焦元θ1同樣非相互包含,沖突系數k=0.5,表明兩證據間存在較大的沖突,與事實不符。

1.2Jousselme證據距離

定義2 (Jousselme證據距離)假設識別框架Θ下兩獨立證據體的BPA為m1(·)、m2(·),其矢量形式為m1、m2,則其Jousselme證據距離[11]可表示為

(2)

通過分析,證據距離存在下述3類問題。

(1)證據距離具有對稱性,因而無法區分證據間相互沖突程度的差異;

(2)對于完全不同的兩組證據,其證據距離會隨著證據BPA分散程度的不同而改變,如例2所示。

例2假設識別框架Θ={θ1,θ2,…,θ6}下兩獨立證據體的BPA為

情形 1

情形 2

由兩證據體的BPA可以看出,情形1與情形2中兩證據體都完全沖突,證據距離的計算結果理應為最大值1,然而通過計算,情形1時,dBPA=0.707,情形2時dBPA=0.577。可見,于完全沖突的兩組證據,BPA越分散,證據距離越小,這與邏輯分析結果相悖。

(3)對于證據中存在非單子集焦元的情況,證據距離的度量結果會出現與邏輯分析不一致的情況,如例3所示。

例3假設識別框架Θ={θ1,θ2,θ3}下兩獨立證據體的BPA為

情形 1

情形 2

對于上述兩種情形進行分析,情形1時證據體1明確支持θ1,證據體2明確支持θ3,兩者沖突程度較大,情形2時證據體1明確支持θ1,證據體2則完全不確定,兩證據體沒有明顯沖突。因此,情形1時的證據距離計算結果應該大于情形2,然而通過計算,情形1時dBPA=0.7,情形2時dBPA=0.7047,與邏輯分析結果相悖。

1.3余弦相似度

余弦相似度由文獻[12]首先提出,用以間接度量證據間的沖突程度,余弦相似度越小,沖突程度越大,反之亦然,其定義如下。

定義3(余弦相似度)設識別框架Θ={θ1,…,θN}下兩獨立證據體的BPA為m1(·)、m2(·),其矢量形式為m1、m2,則兩證據的余弦相似度[12]為

(3)

文獻[14]指出,基本余弦相似度模型能夠有效處理證據中僅包含單子集焦元的情況。在此對例1與例2 進行驗證,對于例1,可得 c(m1,m2)=1,表明兩證據無沖突,與事實相符;對于例2,c(m1,m2)=0,表明兩證據完全沖突,與事實相符,可見,余弦相似度在處理證據中只包含單子集焦元的證據時,結果可靠有效。

文獻[14]同樣指出了式(3)在處理證據中包含非單子集焦元時的不足,并給出了具體的改進方法如下:

(4)

(5)

(6)

通過分析基本余弦相似度計算式(3)與修正式(4)～式(6),可得下述結論。

(1)兩種方法都具有對稱性,因而無法區分證據間相互沖突程度的差異;

(2)基本余弦相似度模型適用于證據中只包含單子集焦元的情況,在處理證據中包含非單子集焦元時的存在不足;

(3)當證據中僅包含單子集焦元時,修正模型無法退化為基本模型,即在處理單子集焦元證據時不如基本模型準確,如例4所示。

例4假設識別框架Θ={θ1,θ2}下兩獨立證據體的BPA為

通過對上述3種典型沖突度量方法的分析可知:①典型沖突度量方法都具有對稱性,都無法區分證據間相互沖突程度的差異;②當證據中只包含單子集焦元時,基本余弦相似度能夠有效解決沖突系數、證據距離以及修正余弦相似度存在的問題;③當證據中包含非單子集焦元時,基本余弦相似度會失效。

2　定向沖突度量方法

鑒于基本余弦相似度模型在度量證據沖突時(證據中僅包含單子集焦元)的有效性,本文提出一種改進的余弦相似度模型。當證據中僅包含單子集焦元時,該公式可退化為基本余弦相似度模型;當證據中包含非單子集焦元時,該模型依然有效;此外,改進模型還可有效區分證據間沖突程度的差異。

定義3(改進余弦相似度)設識別框架Θ={θ1,…,θN}下兩獨立證據體的BPA為m1(·)、m2(·),其矢量形式為m1、m2,則證據體1對2的余弦相似度為

(7)

(8)

所以當Ai?Aj時,Ai對Aj的支持程度大于Aj對Ai的支持程度。

此外,改進余弦相似度模型滿足以下3條性質。

性質 1c′(m1,m2)∈[0,1];

性質 2c′(m1,m2)=1?m1=m2;

性質 3c′(m1,m2)=0?(∪Ai)∩(∪Bj)=?,Ai、Bj分別為m1、m2的焦元。

下面通過證明來驗證定義3中的c′(m1,m2)滿足上述3條性質。

證明假設兩證據體BPA的矢量形式為m1=[x1,x2,…,xn],m2=[y1,y2,…,yn]。

(1)式(7)可以看成向量m1與m2夾角的余弦值,因此c′(m1,m2)∈[-1,1],又因為分子、分母都為正,可得c′(m1,m2)∈[0,1]。

在改進余弦相似度模型的基礎上,證據1對證據2的不支持度,即證據1對證據2產生的定向沖突大小可通過式(9)計算

(9)

3　實驗分析

實驗 1該實驗主要用于驗證所提方法能否有效解決傳統方法失效的問題。

(1)對于例1,計算結果為d(m1,m2)=d(m2,m1)=0,表明兩證據無沖突,相互間完全支持,與事實相符。

(2)對于例2,兩種情形的計算結果同為d(m1,m2)=d(m2,m1)=1,表明兩證據完全沖突,與事實相符。

(3)對于例3,情形1的計算結果為d(m1,m2)=d(m2,m1)=0.742 4,表明兩證據間沖突程度相同;情形2的計算結果為d(m1,m2)=0.384 5,d(m2,m1)=0.589 7,表明兩證據沖突程度不同。綜合可得,情形1的證據沖突程度大于情形2的證據沖突程度,與分析結果一致,此外,情形2的計算結果顯示d(m1,m2)

(4)對于例4,計算結果為d(m1,m2)=d(m2,m1)=0,兩證據無沖突,與事實相符。

由以上分析可知,所提方法能夠有效克服傳統沖突度量方法的不足。

實驗 2由于本文方法在證據中僅包含單子集焦元時可退化為基本余弦相似度模型,文獻[14]對余弦相似度模型在這種情況下的有效性已進行了驗證。為此,本實驗主要用于驗證當證據中存在非單子集焦元時,所提方法能否準確有效的區分證據間沖突程度的差異。

假設識別框架Θ={θ1,θ2,…,θ20},兩證據體的BPA為m1(θ2∪θ3∪θ4)=0.05,m1(θ7)=0.05,m1(Θ)=0.1,m1(Α)=0.8;m2(θ1∪θ2∪θ3∪θ4∪θ5)=1,命題Α按{θ1},{θ1∪θ2},{θ1∪θ2∪θ3},…,{θ1∪θ2∪…∪θ20}的規律變化。

圖1給出了各沖突度量方法的度量結果隨|Α|的變化情況。圖1結果顯示,沖突系數恒為0.1,這是因為證據體1的焦元Α與證據體2的焦元的交集始終不為空集,因此無論Α如何變化,沖突系數始終不變,可見沖突系數無法反映|Α|的變化對結果的影響;文獻[18]所提方法對|Α|=4與|Α|=5的度量結果一致,即無法區分{θ1∪θ2∪θ3∪θ4}與{θ1∪θ2∪θ3∪θ4∪θ5}的區別,不夠準確;1-c、dBPA、d(m1,m2)、d(m2,m1)的相同之處是曲線的變化趨勢一致,說明了這4種方式都能較好的處理證據中包含非單子集焦元的情況,不同之處在于本文方法能夠有效區分證據間沖突程度的差別,在[1,5]的范圍內,證據1中的焦元Α為證據2的焦元的子集,Α的不確定性更小,所以證據1對證據2的支持度大于證據2對證據1的支持度,換句話說,證據1對證據2產生的沖突更小,此分析結果與圖1中d(m1,m2)與d(m2,m1)的相對大小一致,在[5,20]的范圍內,證據2對證據1產生的沖突更小,與圖1中d(m1,m2)與d(m2,m1)的相對大小一致。

圖1　不同方法下證據沖突大小隨|A|變化情況Fig.1　Evidence conflict of different approaches varies by |A|

上述兩實驗結果表明,本文所提算法不但能夠解決傳統度量方法存在的問題,而且能夠準確、有效地表征證據之間的單向沖突程度。

實驗 3本實驗主要用于驗證所提方法在進行實際應用中的有效性,通過將本文所提證據沖突度量方法替換文獻[10]中沖突度量方法實現,沖突合成規則同文獻[10]一致。假設識別框架Θ={θ1,θ2,θ3},5個相互獨立證據體的BPA為

使用文獻[10]方法與本文方法進行對比,結果如表1所示。由表1所示結果可以看出,當只有證據體m1和m2時,由于其同為僅含單子集焦元的證據,兩種方法計算得到的證據權重同為0.5,因此合成結果一致;當證據體m3和m4出現后,相比文獻[10]的方法,本文所提方法對m1賦予了更高的權重,對應m2的權重減少,合成結果更加支持θ1,可見,通過將本文所提沖突度量方法應用到文獻[10]中,不但保證了結果的合理性,而且使得證據合成算法的收斂性更強。

表1　不同方法融合結果比較

4　結　論

本文首先對典型證據沖突度量方法(沖突系數、證據距離以及證據向量余弦相似度)進行了分析,發現其存在兩方面的問題。首先,模型都不具有方向性,即無法區分證據間沖突程度的差異;其次,這些方法都存在失效的情況,但是相比較而言,當證據中僅包含單子集焦元時,余弦相似度能夠避免沖突系數與證據距離失效情況的發生,而當證據中存在非單子集焦元時,其準確度大大降低。為了能夠準確度量證據間的定向沖突程度,本文對基本余弦相似度計算模型進行了改進,通過引入支持系數,一方面使得模型具有非對稱性,從而能夠區分證據間沖突程度的差異;另一方面使得模型能夠處理證據中包含非單子集焦元的情況,由于該方法在證據中僅包含單子集焦元時退化為基本余弦相似度模型,因而保留了其基本模型在處理單子集焦元時的優勢。仿真結果表明,較傳統方法相比,所提沖突度量方法更加準確有效,基于其實現的證據合成方法收斂性更強。

本文雖然設計了具有非對稱性的證據沖突度量方法,但是并未給出更合理的基于其實現的沖突證據的合成方法,僅僅在實驗3中驗證了其在實際應用中的有效性,現有證據合成方法可分為多類,如何進行更為合理的證據組合將是下一步的重點研究方向。

[1] Dempster A P.Upper and lower probabilities induced by a multivalued mapping[J].Annual Mathematics and Statistics,1967,38(2):325-339.

[2] Shafer G A.Mathematical theory of evidence[M].Princeton:Princeton University Press,1976.

[3] Thierry D,Zoulficar Y,Fahed A.Representing uncertainty on set-valued variables using belief functions[J].Artificial Intelligence,2010,174(7):479-499.

[4] Zhang W X,Liu W H,Wu X.Quantitative evaluation across software development life cycle based on evidence theory[J].Lecture Notes in Computer Science,2013,7996(1):353-362.

[5] Zadeh L A.A simple view of the Dempster-Shafer theory of evidence and its implication for the rule of combination[J].Artificial Intelligence Magazine,1986,7(1):85-90.

[6] Guo H W,Shi W K,Deng Y,et al.Evidential conflict and its 3D strategy:discard,discover and disassemble[J].Systems Engineering and Electornics,2007,29(6):890-898.(郭華偉,施文康,鄧勇,等.證據沖突:丟棄,發現或化解?[J].系統工程與電子技術,2007,29(6):890-898.)

[7] Han D Q,Han C Z,Yang Y.A modified evidence combination approach based on ambiguity measure[C]//Proc.of the 11th International Conference on Information Fusion,2008:1-6.

[8] Quan W,Wang X D,Wang J,et al.New combination rule of DST based on local conflict distribution strategy[J].Acta Electronica Sinica,2012,40(9):1880-1884.(權文,王曉丹,王堅,等.一種基于局部沖突分配的DST組合規則[J].電子學報,2012,40(9):1880-1884.)

[9] Song Y F,Wang X D,Lei L,et al.Evidence combination based on the degree of credibility and falsity[J].Journal on Communications,2015,36(5):2456-2463.(宋亞飛,王曉丹,雷蕾,等.基于信任度和虛假度的證據組合方法[J].通信學報,2015,36(5):2456-2463.)

[10] Deng Y,Shi W K,Zhu Z F,et al.Combining belief functions based on distance of evidence[J].Decision Support Systems,2004,38(3):489-493.

[11] Jousselme A L,Grenier D,Bosse E.A new distance between two bodies of evidence[J].Information Fusion,2001,2(1):90-101.

[12] Wen C L,Wang Y C,Xu X B.Fuzzy information fusion algorithm of fault diagnosis based on similarity measure of evidence[J].Lecture Notes in Computer Science,2008,5264:506-515.

[13] Wang W Q,Zhao Y J,Huang J,et al.An asymmetrical measure for evidence conflict[J].Control and Decision,2014,29(3):533-536.(王萬請,趙擁軍,黃潔,等.一種非對稱的證據沖突度量方法[J].控制與決策,2014,29(3):533-536.)

[14] Song Y F,Wang X D,Lei L,et al.Measurement of evidence conflict based on correlation coefficient[J].Journal on Communications,2014,35(5):95-99.(宋亞飛,王曉丹,雷蕾,等.基于相關系數的證據沖突度量方法[J].通信學報,2014,35(5):95-99.)

[15] Jiang W,Peng J Y,Deng Y.New representation method of evidential conflict[J].Systems Engineering and Electronics,2010,32(3):562-564.(蔣雯,彭進業,鄧勇.一種新的證據沖突表示方法[J].系統工程與電子技術,2010,32(3):562-564.)

[16] Zhang Y J,Long C.Improved conflict representation method[J].Application Research of Computers,2013,30(6):1716-1718.(張燕君,龍呈.一種改進的沖突表示方法[J].計算機應用研究,2013,30(6):1716-1718.)

[17] Cuzzolin F.A geometric approach to the theory of evidence[J].IEEE Trans.on Systems,Man,and Cybernetics-PartC:Applications and Reviews,2008,38(2):522-534.

[18] Liu W R.Analyzing the degree of conflict among belief functions[J].Artificial Intelligence,2006,170(170):909-924.

[19] Liu X L,Chen G M.A self-adaptive conflicting evidence test and combination approach[J].Control and Decision,2014,29(5):929-932.(劉希亮,陳桂明.一種自適應沖突證據檢驗與合成方法[J].控制與決策,2014,29(5):929-932.)

[20] Alexander L A.Estimation of conflict and decreasing of ignorance in Dempster-Shafer theory[J].Procedia Computer Science,2013,17:1113-1120.

[21] Martin A,Jousselme A L,Osswald C.Conflict measure for the discounting operationon belief functions[C]//Proc.of the 11th International Conference on Information Fusion,2008:1-8.

Directional evidence conflict measurement based on improved cosine similarity

MAO Yi-fan,ZHANG Duo-lin,WANG Lu

(College of Air and Missile Defense,Air Force Engineering University,Xi’an 710038,China)

In order to solve the problems that traditional evidence conflict measurement methods can not express the difference of mutual conflict degrees between evidences and work poorly under special situation,a directional evidence conflict measurement based on the improved cosine similarity is proposed.By importing the support coefficient matrix into the cosine similarity model,the proposed model can be asymmetrical,so that the difference of mutual conflict degrees between evidences can be expressed,and the problem that the basic cosine similarity model is not suitable to measure the evidence conflict when the evidences include multi-subset focal elements can be overcame.Simulation results show that the proposed method is effective and accurate.

Dempster-Shafer evidence theory; evidence conflict; conflict measure; direction; cosine similarity

2015-11-27；

2016-06-03；網絡優先出版日期：2016-07-06。

國家自然科學基金(61272011)資助課題

TP 391

ADOI:10.3969/j.issn.1001-506X.2016.11.18

毛藝帆(1988-),女,博士研究生,主要研究方向為防空反導作戰建模與仿真。

E-mail:myf1210@126.com

張多林(1959-),男,教授,博士研究生導師,博士,主要研究方向為防空反導作戰建模與仿真。

E-mail:zdh1959@126.com

王路(1987-),男,博士研究生,主要研究方向為鄰近空間高超聲速飛行器防御作戰建模與仿真。

E-mail:408191081@qq.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160706.1958.008.html