利用證據神經網絡的多分類器系統構造

和紅順,韓德強,楊藝

(1.西安交通大學電子與信息工程學院,710049,西安;2.中國電子科技集團公司航天信息應用技術重點實驗室,050004,石家莊;3.西安交通大學機械結構強度與振動國家重點實驗室,710049,西安)

復雜環境或場景下,單一分類器的分類效果往往不夠理想[1]。多分類器系統[2]是應對復雜環境下模式分類問題的有效方法,已被廣泛應用于圖像識別[3]、語音識別[3]、醫療診斷[4]等領域。

學者們基于多分類器系統的多個層面開展了研究。在成員分類器生成層面,已有研究方法主要有選用不同訓練樣本獲得成員分類器[5]及基于不同的分類算法生成成員分類器[6]等。由多個相同的分類器構成的多分類器系統,其性能并不會優于單一成員分類器[7]。如果多個成員分類器所提供的信息是互補的、有差異的,則融合分類性能一定會優于單一最優分類器,采用具有一定互補性[8]的不同成員分類器是多分類器系統提升融合分類性能的關鍵。一些學者分析了如何生成和選擇具備互補性的成員分類器[9-10]。在多分類器融合規則方面,對成員分類器的不同輸出形式采用不同的融合方式,如投票法[11]、Bayes法[12]以及DS證據理論法[13]等。

成員分類器的生成是多分類器系統設計的基礎。神經網絡是一類常用的分類器,其中BP神經網絡是一種簡單有效的分類算法。然而,在分類訓練過程中,訓練樣本中往往存在很難準確判斷類別歸屬的數據,即這些樣本在分類時存在不確定性。證據理論是一種表示和處理不確定性的有效的工具。針對數據的不確定性問題,本文提出一種證據神經網絡分類器并將其作為成員分類器來構造多分類器系統。首先對訓練數據進行重組,將難以準確分辨類別的數據劃歸到新的類別(混合類),在建模過程中保留著訓練數據本身含混性的這一不確定性。然后使用重組后含有混合類數據的訓練集訓練成員分類器,將得到的輸出進行證據函數建模。最后用證據組合規則來融合多個成員分類器結果以提高多分類器系統的性能。實驗結果表明,本文提出的多分類器系統合理、有效。

1 多分類器系統簡介

1.1 多分類器系統概述

多分類器系統是一種應對復雜模式識別問題的有效方法,在模式識別領域得到了廣泛的關注和應用。多分類器系統使用多個不同的分類器進行分類,然后通過一定的組合機制融合多個具有一定互補性[14]的分類器結果,以獲得更加有效的分類效果。多分類器系統的流程如圖1所示。

圖1 多分類器系統流程圖

系統基于成員分類器的不同輸出形式選擇合適的融合方式,融合成員分類器結果,得到最終的決策結果。成員分類器的輸出為度量級(即輸出為一系列代表各類別可能性的度量值)時,可以采用DS證據理論[15]等方法進行融合。

多分類系統能夠一定程度上提高分類精度,但并非任意分類器組合都能獲得這樣的提升。不同成員分類器之間的互補性非常關鍵。

1.2 差異性度量

差異性度量[16]的目的是通過某種方法對分類器集合中各個分類器之間的差異進行量化。成對差異性度量較為常用。成對差異性度量需要考慮兩兩分類器之間的差異性,其代表方法有統計法、相關系數統計法、不一致度量法及雙錯法等。本文使用其中應用最多的不一致度量法。不一致度量法由于要計算兩兩基分類器之間的統計關系,因而依賴于兩基分類器的聯合分布。令分類器Si、Sj判斷正確為1,判斷錯誤為0,分類器輸出統計量Nmn(m,n∈{0,1})表示分類器Si、Sj判斷為m、n的樣本個數,分類器Si、Sj的聯合輸出碼如表1所示。

表1 分類器Si、Sj的聯合輸出碼

不一致度量值表達式如下

(1)

對一個由L個成員分類器構成的成員分類器集的差異性度量值為成員分類器集中所有兩兩分類器差異性度量值的平均,表示如下

(2)

2 基于證據神經網絡的多分類器系統

傳統的神經網絡的訓練過程是基于“硬”標簽(清晰的類別標簽)的訓練樣本,而在真實數據中往往存在一些難以準確分類的樣本。這部分數據在類別歸屬上存在著含混性,使用傳統的神經網絡直接對這些數據進行分類往往容易得到錯誤的結果。證據理論,又稱為信度函數理論,是處理這種含混的不確定性的有效工具[17-22],因此本文利用證據理論對神經網絡分類器訓練數據本身存在的不確定性進行建模表征和處理,使用證據組合規則融合多個分類器結果來減少或消解不確定性,以求得到更好的分類性能。

2.1 證據理論簡介

在證據理論中,設集合Θ={θ1,θ2,…,θn}為辨識框架,2Θ是Θ所有子集的集合。若m:2Θ→[0,1]滿足

(?)=0

(3)

則稱m為辨識框架上的基本信度賦值(BBA),也稱mass函數。若?A?Θ,m(A)>0,A被稱為焦元。

對于辨識框架Θ中的某個命題A,其信任函數和似真函數的定義分別為bel(A)和pl(A),表示如下

(4)

(5)

區間[bel(A),pl(A)]用于表示A的不確定性。

Dempster組合規則用于獨立證據間的組合。辨識框架Θ上的2個獨立證據的mass函數為m1和m2,對于?A?Θ,A≠?,依據Dempster組合規則如下

(6)

Dempster組合規則在高沖突證據組合中會得到反直觀的結果,為了解決這一問題,一些研究者提出了一些改進的方法,其中具有代表性的有Yager組合規則和Murphy組合規則。

Yage認為證據沖突部分代表了不可靠信息,應該被賦給全集,以表征“未知”[23],規則定義為

(7)

Yager規則滿足交換律,但不滿足結合律。

Murphy首先采用了等權值的方式得到平均證據[24],假設有s個證據,則平均證據為

(8)

然后應用Dempster組合規則對平均證據mave自身組合s-1次。其他一些組合規則詳見文獻[25]。

在得到融合證據后,由證據至概率的轉換是實現融合決策的重要步驟。Smets定義的Pignistic概率轉換[15]用于將mass函數轉換為概率

(9)

2.2 證據神經網絡多分類器系統

證據理論中證據函數的生成,特別是混合焦元的確定是難點所在。傳統的神經網絡訓練過程是基于“硬”的類別標簽,如圖2a所示,用傳統的神經網絡來生成證據函數只能得到單點的焦元[26],無法發揮證據理論的優勢,不能對含混性進行建模和表征。而本方法得到的輸出包含單點焦元和混合焦元,如圖2b所示用神經網絡對包含混合類數據的訓練數據進行訓練,可以得到包含混合焦元在內的多個焦元,能夠有效的表征數據的含混性。這里以BP神經網絡(三分類問題)為例,闡述本文方法的具體實現。

(a)傳統神經網絡分類器

(b)證據神經網絡分類器圖2 證據BP神經網絡分類器

假設訓練數據有3類,類別標簽為C1、C2、C3。首先對原有的訓練樣本進行重組,得到包含混合類在內的新訓練樣本,共23-1=7個類別,分別為{C1}、{C2}、{C3}、{C1,C2}、{C1,C3}、{C2,C3}、{C1,C2,C3}。給定任意一個測試樣本,采用后向傳播(BP)神經網絡得到的焦元以及所對應的mass賦值,如表2所示。

表2 證據神經網絡焦元及所對應的mass賦值

mass賦值形式如表2的神經網絡稱之為證據神經網絡。當數據含有M個類別時得到2M-1個mass賦值。信度分配方式為對于輸入的訓練樣本x={x(1),x(2),…,x(d)},將神經網絡的輸出結果歸一化為

(10)

式中:y(Ak)為測試樣本輸出。得到證據函數m(Ak),表示BP網絡在重組后的數據屬于第k個命題Ak的基本信任分配。舉例說明,設測試樣本輸出為y(A1)=0.5、y(A2)=0.3、y(A3)=0.3、y(A4)=0.2、y(A5)=0.2、y(A6)=0.3、y(A7)=0.2,利用式(10)歸一化得到一組證據函數m(A1)=0.25、m(A2)=0.15、m(A3)=0.15、m(A4)=0.1、m(A5)=0.1、m(A6)=0.15、m(A7)=0.1。圖2為傳統神經網絡分類器與BP神經網絡分類器的網絡結構對比示意圖。

需要指出的是,傳統的神經網絡是基于“硬”的清晰類別標簽的,而本文中的方法是采用混合類作為標準輸出,在證據建模的過程中不隨意丟棄數據含混的這一確定性,構造復合焦元(包括焦元組成及mass函數賦值),通過構造多個成員分類器并用證據理論方法融合來減少或消解這種不確定性,以求達到更好的分類效果。

在對訓練數據進行重組中最關鍵的一點是如何去定義混合類。

2.3 混合類的構建

本節介紹如何確定訓練數據中的含混數據部分以及數據的重組過程。本文采用K近鄰算法[27]和集合交并運算來確定混合類數據并完成訓練數據的重組。

(1)對于二分類的訓練數據,給定K值,遍歷找出距離當前訓練樣本最近的K個樣本,和當前樣本標簽一致的數據個數記為N1,與當前數據標簽不一致的數據個數記為N2。當N2≥N1時,把當前樣本劃分到混合類部分。

(2)對于多分類問題,以3類問題為例,選取C1、C2類的混合部分數據M12(M12由用上述劃分二分類混合類的方法得到,M13、M23也用同樣的方法得到),最終的C1、C2類混合數據為S12=M12-M12∩M13-M12∩M23;同樣的可以得到C1、C3類混合S13=M13-M13∩M12-M13∩M23和C2、C3類混合S23=M23-M23∩M12-M23∩M13。C1、C2、C3的混合類S123由下式得到

S123=(S12∩S13)∪(S12∩S23)∪(S23∩S13)

(11)

2.4 對不均衡數據的處理

訓練數據重組之后往往會出現數據的不均衡。兩類數據經過重組后的訓練數據C1類數據、C2類數據遠多于混合類{C1,C2}數據,如圖3所示。不均衡數據直接進行分類往往效果不佳,需要進行均衡化的處理。

圖3 訓練數據重組后的分類數據不均衡狀況

本文采用SMOTE過采樣算法[28]均衡化數據。SMOTE算法是利用特征空間中現存少數類樣本之間的相似性建立人工數據的方法。Smin表示當前的需要補充數據的原始樣本集合,對于每一個樣本xi∈Smin使用K近鄰法,其中K是指定的整數。通過以下方法得到人工樣本

(12)

3 實驗比較和分析

為了驗證本文提出的證據神經網絡多分類器系統的合理有效性,基于人工數據集和UCI數據集進對比實驗。實驗方法:依次選取原始數據的每三維特征構成一個子空間(最后一個子空間維度為原始特征維度除以3的余數),例如假設原始數據有8維特征{d1,d2,d3,d4,d5,d6,d7,d8},則可以得到{d1,d2,d3}、{d4,d5,d6}、{d7,d8} 3個特征子空間,將原始數據按列隨機排序,同樣的依次選取特征得到不同的子空間集合,將原始數據按列多次隨機依次選取生成多個不同的特征子空間集合,來構造出多個不同的多分類器系統,利用成對差異性度量(式(2))選取其中差異性最大的子空間集合構造多分類器系統。實驗將樣本數據平均分成5份,任意選取其中的3份作為訓練數據,其余2份數據作為待測數據,重復多次實驗取平均正確率。實驗中數據的每一維特征Fi都做歸一化處理

(13)

需要指出的是,在使用本文提出的證據神經網絡多分類器時,使用的訓練數據是重組后包含混合類的訓練數據(均衡化后)。

本文實驗使用了多種不同的融合規則進行對比,其中不同的融合規則對應的本文方法的簡稱如表3所示。

表3 本文設計的3種分類器系統方法的融合規則及簡稱

在同等條件下,將本文提出的方法(MNE-DS、MNE-Yager、MNE-Mur)與投票法(MaVot)和貝葉斯BBA(BBBA)方法進行對比。投票法[29-30]是一種簡單有效的融合方式,已廣泛的應用于多分類器系統中。貝葉斯BBA(只含有單焦元的BBA)是將BP神經網絡的輸出歸一化,再使用融合方法進行融合。

3.1 人工數據集

本文構造的人工數據集共3類,每個樣本包含6個獨立的特征維度。第1、2維度,3、4維度,5、6維度的數據分別由下式得到

(14)

式中:r是[01]的隨機數;αk(k=1,2,3)為給定常數;θ為一個隨機角度。人工數據集Da可以表示為Da=[x1(1),x1(2),x2(1),x2(2),x3(1),x3(2)]。

每一類數據包含100個樣本,樣本每個維度對應的αk的值如表4所示。

表4 不同維度數據3個類別所對應的αk值

本文構造的人工數據如圖4～圖6所示。本文分別使用訓練數據的1、2維度,3、4維度,5、6維度這3個子空間訓練成員分類器來構造多分類器系統。從圖4～圖6可見,第1個子空間上C1、C3類數據是容易區分的,第2個子空間上C1、C2類數據是容易區分的,第3個子空間上C2、C3類數據是容易區分的。這3個子空間有一定的差異性。

圖4 人工數據集1、2維度特征

圖5 人工數據集3、4維度特征

圖6 人工數據集5、6維度特征

人工數據集下多分類器系統的平均分類正確率如表5所示。由表5可見,本文提出的方法MNE-DS、MNE-Yager、MNE-Mur相比于投票法、Bayes BBA方法可以得到更好的分類效果。

表5 人工數據集下多分類器系統的分類效果比較

3.2 UCI數據集

實驗使用的UCI數據集信息如表6所示。本文依次選取原始訓練數據的維度特征構成子空間,將原始訓練數據按列隨機排序,用同樣的依次選取方法可以得到不同的子空間集合。重復上述操作生成30個不同的特征子空間集合,用得到的不同的子空間集合訓練得到多個不同的多分類器系統,利用成對差異性度量(式(2))選取其中差異性最大的子空間集合構造多分類器系統。

表6 實驗所用UCI數據集信息

采用本文提出的3種算法(MNE-DS、MNE-Yager、MNE-Mur)與投票法(MaVot)和Bayes BBA(BBBA)方法進行對比,結果如表7所示。從表7可以看出,本文提出的證據神經網絡多分類器有很好的分類效果,在數據集Diabetes和Seeds分類正確率明顯高于其他多分類器系統。一般而言,對于證據神經網絡多分類器,類別數據多且特征維

數低時,數據的不確定性比較突出。在二分類數據集Pima、Magic 04和Diabetes上,特征維數屬于中低水平,相比投票法,證據神經網絡多分類器分類正確率有明顯的提高,在特征維度很高的Wdbc數據集上分類正確率有一定程度的提高;在三分類數據集Seeds和Iris上,數據的特征維度較低,類別數目較高,說明證據神經網絡多分類器系統具有很好的分類性能。

總體而言,本文提出的證據神經網絡多分類器在繼承了傳統神經網絡良好的分類性能的同時,充分利用了數據間含混的不確定性,并利用證據組合規則融合來消解這一含混的不確定性,從而得到更好的分類效果。

4 結 論

本文提出了一種基于證據神經網絡的多分類器系統,該系統在建模過程中保留數據的含混性并嘗試用證據理論去消解這一含混的不確定性。本文基于證據神經網絡的多分類器系統能更加充分地利用訓練數據所包含的信息,相比于其他基于神經網絡的多分類器系統如基于投票法的多分類器系統以及基于貝葉斯BBA的多分類器系統,在建模過程中能更為有效的避免信息的丟失,得到的識別結果具有更高的可靠性,進一步提高了分類正確率,得到的分類效果更為準確。

在今后的研究中,我們將嘗試使用其他類型的有監督神經網絡分類器構造多分類器系統,以及探尋更為合理有效的劃分混合類數據的方法,更為科學地完成訓練數據的重組過程。差異性度量是多分類器系統的一個重要部分,近來取得了一些進展,在將來的工作中,我們將在本文方法的基礎上設計更為科學有效的差異性度量方法,構造出更為科學可靠的多分類器系統,以求得到更為準確的分類結果。

表7 本文3種算法與其他2種算法在UCI數據集上的分類效果比較