基于灰關聯度系數的證據組合方法*

盧彥龍 王 拓 徐 宏

(西安交通大學電子與信息工程學院 西安 710049)

?

基于灰關聯度系數的證據組合方法*

盧彥龍 王 拓 徐 宏

(西安交通大學電子與信息工程學院 西安 710049)

分析了D-S方法及其改進方法的不足,基于灰關聯度系數提出了一種新的沖突證據處理算法。首先,以灰關聯系數作為衡量標準,把每條證據當做離散的點,求出證據體集合中其它證據與它的相似程度。然后把相似程度進行歸一化處理得到相似度,該相似度表示的是該證據的重要程度。把該相似度當做每條證據體的權重,對證據體加權合成新的證據體模型。最后用新證據體融合得到結果。通過算例表明:該方法與其他改進方法比較,具有收斂速度快,計算方法簡單,易于工程實現的優點。

D-S證據理論; 證據沖突; 灰色關聯度; 信息融合

Class Number TP301.6

1 引言

Dempster-Shafer(D-S)證據理論是1967由Dempste[1]提出,又經其弟子Shafer進一步推廣和發展。目前已廣泛應用于地理空間系統[2]、網絡安全[3]、電力自動化[4]等領域。證據理論雖然有很多優點,但Zadeh[5]在研究中發現,該理論處理高沖突證據時會產生與事實相反的結論。自此許多學者對該問題進行了深入的研究,提出了很多解決方法?？傮w來看,解決沖突方法分為兩類。

一類是對D-S理論合成規則的修改,主張修改組合規則的學者認為D-S組合規則在解決高沖突問題時會出現有悖常理的情況,是由于D-S組合規則對沖突分配不合理而造成的,進而提出了不同的沖突分配法則,Lefevre[6]、權文[7]、劉海燕[8]等人都在這方面做了相關研究。另一類是對證據模型的修改,主張修改證據模型的學者認為D-S組合規則本身并沒有問題,合成結果之所以有悖常理,造是成證據模型本身有問題,與合成規則無關,所以應該對證據模型進行修改,如Murphy[9],鄧勇[10],韓德強[11]等。

對合成規則的修改難度大、容易破壞D-S組合規則的一些良好的數學性質,而且在一些應用領域,傳感器容易受到干擾而失效,造成證據體數據出錯,這種情況下把合成結果出現悖論的原因歸結于D-S組合規則就有些許不妥。所以,本文也基于第二類改進方法提出一種新的證據體修改方法。該類方法的難點在于權重的生成確定,本文引入灰關聯度系數生成權重,直接求出證據間的相似度,使合成沖突證據時,能夠更加快速、準確的得出結論。

2 D-S 組合規則簡介

D-S理論中,對某一個問題的所有認知的可能的解所構成的集合叫做識別框架,常用Θ表示,其中Θ中的元素兩兩相斥,及Θ={A1,A2,…,AN}。稱Ai(1≤i≤N)為識別框架中的一個焦元,其中N為識別框架中總的元素個數。根據集合的定義可知,該集合有2N個子集,用2Θ表示。

定義2:D-S證據理論是對多條證據融合處理的方法,合成規則表示為[1]

(1)

例:某一刑事案件有三個犯罪嫌疑人A,B,C,現有兩個證人給出的嫌疑犯Θ={A,B,C}的基本信度賦值如下:

E1:m1(A)=0.99,m1(B)=0.01,m1(C)=0

E2:m2(A)=0,m2(B)=0.01,m2(C)=0.99

用D-S組合規則合成結果:m(A)=m(C)=0,m(B)=0.0001/(1-K)=1。

在本例中,兩個證人都對B嫌疑人的支持度很低,但合成的結果卻為B,這顯然有悖常理。

3 基于灰關聯度的改進方法

3.1 灰色關聯度

灰色關聯分析的基本思想是:根據序列中各點的貼近程度來度量該序列組成曲線幾何形狀的相似程度[12]。序列曲線的幾何形狀越接近,它們的關聯程度就越大[12]。

定義3:若Xi(i=1,2,…,N)為觀測對象序列,Xi(k)為Xi關于第k個指標的觀測數據,稱Xi=(xi(1),xi(2),…,xi(N))為序列Xi(k)的行為指數序列,則其他觀測對象Xj=(xj(1),xj(2),…,xj(N))(i≠j)(j=1,2,…,N)與行為指數序列Xi對應的每個點的灰關聯度系數定義為[12]γ(xi(k),xj(k)):

(2)

則序列Xi和序列Xj總的關聯度為兩條序列每個點的相似度之和,定義為Crd(Xi,Xj):

(3)

3.2 基于灰關聯度的改進方法

基于灰關聯度的改進方法認為若證據體與證據體集合中大多數證據之間的幾何形狀比較接近,則認為該證據對判斷出正確結果的作用高,在證據合成時,應該賦予該證據較大的權重,而證據體之間幾何形狀接近程度用相似度表示,所以可以通過灰關聯度直接求出證據體之間的相似度。求證據體相似度的方法如下:

若識別框架Θ中有N個元素,mi,mj(i≠j)為其中任意兩個不同的基本信度賦值,則把mi,mj按以下形式映射到上面敘述的灰關聯度里的Xi,Xj:

Xi(1)=mi(A1),Xi(2)=mi(A2),…,Xi(N)=mi(AN)

Xj(1)=mj(A1),Xj(2)=mj(A2),…,Xj(N)=mj(AN)

及Xi=(mi(A1),mi(A2),…,mi(AN))

Xj=(mj(A1),mj(A2),…,mj(AN))

用式(2)做一點改變,就可以求出兩條證據每個點的相似度,定義為γ(mi(Ak),mj(Ak)):

(4)

對照上述式(3),則兩條證據mi,mj(i≠j)總的相似度為兩條證據每個點的相似度之和,定義為Crd(mi,mj):

(5)

求出mi,mj(i≠j)相似度之后用相似度作為權重,對證據體模型進行修改,最后把修改后的證據體用D-S組合規則得到融合結果。

基于灰關聯度的改進方法通過灰關聯度求證據之間的相似度,通過式(4)的分母可以看出,當兩條證據的BPA對識別框架Θ中每個元素的支持程度越接近,|mi(Ak)-mj(Ak)|越小,求出的兩條證據每個點的相似度越大。若兩條證據的BPA相差不大,也就是兩條證據對識別框架中目標的支持程度沖突不大,根據式(5)可以得出兩條證據的相似度越大。

兩條證據間的相似度反映的證據信息的相似程度,若一條證據和證據集合中大部分證據對識別框架中元素的支持程度沖突不大,通過式(4)、式(5)可知,該類證據的相似度比較大則在合成時該證據應該賦予較高的權值。相反,若一條證據和證據集合中大部分證據的對別框架中元素的支持程度沖突較大,則|mi(Ak)-mj(Ak)|比較大,導致求出的每個點相似度較小,則證據之間的相似度也越小。

3.3 改進方法的計算流程

1) 計算出證據mi(1≤i≤N)與除自己之外證據體mj(1≤j≤N)每一個點的灰關聯度系數矩陣PM:

2) 對灰關聯度系數矩陣PM對行求和得到mi,mj(i≠j)的相似程度Crd(mi,mj):

3) 計算出mi與其余證據體的總相似度TotalCrd(mi):

4) 把總相似度歸一化的到歸一化相似度

5) 把歸一化相似度作為每條證據的權值

ωi=NormaCrd(mi)

6) 求出證據模型

對新證據模型進行N-1次D-S組合規則得到融合結果。

4 算例分析

下面利用鄧勇文獻[10]的算例,對比D-S組合規則,Murphy法,鄧勇法,韓德強法分析結果,說明本文提出的方法在處理沖突證據融合方面的優越性能,計算時ρ=0.05。五種方法融合結果如表1所示。

表1 五種證據組合方法的比較

本文算例中,m2為干擾證據,除它以外,其它四條證據都支持目標A。在用D-S方法融合時,由于m2(A)=0即使別的證據都支持A,依然無法識別出正確的結論,產生與事實相悖的結論,即D-S方法無法處理高沖突問題。韓德強方法雖然隨著證據數目的增加對證據A的支持程度在慢慢變大,但由于干擾證據的影響,在文中五條證據合成完之后,依然無法得出正確的結論,可以看出在文中這種算例條件下,用該方法得到正確結論需要更多的證據。

Murphy法,鄧勇法和文中提出的基于灰關聯度的改進方法在合成時都能夠比較迅速地合成結果。在合成判斷時,當我們把閾值設為0.7時,可以看出用Mruphy方法和鄧勇法融合識別時都能融合出正確的結論,但需要四次融合(m1,m2,m3,m4,m5)。而本文的方法只需三次(m1,m2,m3,m4)融合就可以得出正確的結論。當五條證據融合完以后,可以看出,本文對A的支持度為0.90216,遠大于鄧勇法的0.82493。分析其原因可以發現,Mruphy方法由于其對證據的簡單平均,使得重要程度低的證據影響了合成合理結果的速度;韓德強方法用求權重時引入了負指數函數,使得第二條證據占有的權重較大,導致收斂速度嚴重降低;鄧勇法由于Jousselme距離退化為歐氏距離,在度量兩條證據之間的相似性時,不具有直接性,放大了證據之間的差異性,突出了沖突證據的權重,導致收斂速度慢。

本文算例中,五種合成方法k值變換趨勢如圖1所示。

圖1 五種合成方法k值比較

可以看出D-S方法融合時,k值一直居高不下,韓德強法在文中例子中,由于收斂速度較慢,致使k值在例子中的數據合成完成之前,一直在增加,沒有收斂,Mruphy方法和鄧勇法的k值雖然隨著合成次數的增加都在減小,但減小速率慢于本文提出的方法。

5 結語

在軍事應用的領域,傳感器容易受到自然環境和人為因素的影響,導致少量傳感器的測量結果異常,從而得到沖突證據。通過文中分析可以看出,當證據間存在嚴重沖突時,D-S方法無法得出正確結論,Mruphy方法和鄧勇法收斂速度較慢,故而本文提出了一種基于灰關聯度系數的證據組合方法。通過算例可以看出,本文提出的方法收斂速度快,魯棒性好,計算方法簡單,易于工程實現。

[1] 韓德強,楊藝,韓崇昭.DS證據理論研究進展及相關問題探討[J].控制與決策,2014,29(1):1-8. HAN Deqiang, YANG Yi, HAN Chongzhao. Advances in DS evidence theory and related discussions[J]. Control and Decision,2014,29(1):1-8.

[2] Paul A. Elmore, Frederick E. Petry, Ronald R. Yager. Geospatial Modeling Using Dempster-Shafer Theory[J]. IEEE Transactions on Cybernetics,2016:1-11.

[3] 湯永利,李偉杰,于金霞.基于改進D-S證據理論的網絡安全態勢評估方法[J].南京理工大學學報,2015,39(4):406-411. TANG Yongli, LI Weijie, YU Jinxia. Network security situational assessment method based on improved D-S evidence theory[J]. Journal of Nanjing University of Science and Technology,2015,39(4):406-411.

[4] 司馬莉萍,舒乃秋,李自品,等.基于SVM和D-S證據理論的電力變壓器內部故障部位識別[J].電力自動化設備,2012,32(11):72-76. SIMA Liping, SHU Naiqiu, LI Zipin, et al. Identification of interior fault position based on SVM and D-S evidence theory for electric transformer[J]. Electric Power Automation Equipment,2012,32(11):72-7.

[5] Zadeh L. Asimpie view of the Dempster-Shafer theory of evidence and its impiication for the ruie of combinatio[J]. AI Magazine,1986,7(1):85-90.

[6] LEFEVRE E, COLOT O, VANNOORENBERGHE P. Belief functions combination and conflict management[J]. Information Fusion,2002,3(2):149-162.

[7] 權文,王曉丹,王堅.一種基于置信最大熵模型的證據推理方法[J].控制與決策,2012,27(6):899-903. QUAN Wen, WANG Xiadan, WANG Jian. A combination rule of evidence theory based on brief max-entropy model[J]. Control and Decision,2012,27(6):899-903.

[8] 劉海燕,趙宗貴,劉熹.D-S證據理論中沖突證據的合成方法[J].電子科技大學學報,2008,37(5):701-704. LIU Haiyan, ZHAO Zonggui, LIU Xi. Combination of Conflict Evidences in D-S Theory[J]. Journal of University of Electonic science and Technology,2008,37(5):701-704.

[9] Murphy C K. Combining beiief functions when evidence confiict[J]. Decision Support Systems,2000,29(1):1-9.

[10] 鄧勇,施文康,朱振福.一種有效處理沖突證據的組合方法[J].紅外與毫米波學報.2004,23(1):27-32. DENG Yong, SHI Wenkang, ZHU Zhenfu. Efficient combination approach of confilict evidence[J]. Journal Infrared Millimeter and Waves,2004,23(1):27-32.

[11] 韓德強,鄧勇,韓崇昭.利用不確定度的沖突證據組合[J].控制理論與應用,2011,28(6):788-792. HAN Deqiang, DENG Yong, HAN Chongzhao. Conflicting evidence combination by using uncertainty degree[J]. Control Theory & Applications,2011,28(6):788-792.

[12] 魯峰,黃金泉.基于灰色關聯聚類的特征提取算法[J].系統工程理論與實踐,2012,32(4):872-876. LU Feng, HUANG Jinquan. Feature extraction algorithm of clustering based on grey relational theory[J]. Systems Engineering — Theory & Practice,2012,32(4):872-876.

[13] 柏丹丹,和敬涵,王小君.基于灰色關聯分析的自適應低頻減載[J].電力系統保護與控制,2014,42(6):20-25. BAI Dandan, HE Jinghan, WANG Xiaojun. Adaptive UFLS scheme based on grey correlation analysis[J]. Power System Protection and Control,2014,42(6):20-25.

Evidence Combination Method Based on Degree of Gray Relationship

LU Yanlong WANG Tuo XU Hong

(College of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049)

In this paper, the shortage of D-S evidence theory as well as its modification are analyzed, then a new combination method based on degree of gray relationship is proposed. The method uses degree of gray relationship as evaluation criteria, then regards each piece of evidence as discrete points and computes the similarity between every two evidences in evidence collection. Then the obtained similarity which represents the importance of evidences is normalized. The similarity obtained above is regarded as the weight of every evidence and generate new evidence model. Finally fusion result is got by means of evidence model.The numerical examples show that the method proposed in this paper compared to other methods has following advantages, including fast convergent rate, simple calculation method, easy realization in a project.

D-S evidence theory, conflict evidence, degree of gray relationship, information fusion

2016年7月9日,

2016年8月28日

國家自然科學基金(編號:61071217);江蘇省自然科學基金(編號:Bk0141216)資助。

盧彥龍,男,碩士研究生,研究方向:數據融合、圖像處理。王拓,男,教授,博士生導師,研究方向:圖像處理,智能電網。徐宏,男,碩士研究生,研究方向:數據融合、文本處理。

TP301.6

10.3969/j.issn.1672-9722.2017.01.012