一種自適應子融合集成多分類器方法

(1.廣西師范學院 計算機與信息工程學院， 南寧 530023;2.廣西科技師范學院 數學與計算機科學學院，廣西 來賓 546199)

0 引言

模式識別領域中普遍存在的一個問題是，同一個分類方法在不同的應用中分類性能不盡相同。沒有哪種分類方法能夠普遍適用于所有的分類情況。為了解決這樣的問題，分類器融合技術成為了模式識別領域的一個重要技術。當前許多研究表明，多分類器融合技術對于模式識別的性能有較大的提高[1-3]。目前多分類器融合技術已經在很多領域上得到實踐，例如圖像分類、語音識別、手寫技術識別等[4]。模式識別領域統一將分類器技術劃分為以下兩種形式：分類器動態選擇[5]和分類器融合。動態分類器選擇方法的核心思想是：預測當前識別任務多分類器系統中識別最準確的基分類器，選擇預測的基分類器作為多分類器系統融合決策的輸出。而分類器融合方法的核心思想是：全面地考慮每一個基分類器的決策輸出，結合每一個基分類器的決策輸出作為多分類器的最終決策輸出，這種思想會得到更多的決定性決策信息。

基于這兩種思想比較，更多的學者致力于研究多分類器融合方法。常規的多分類器融合技術包括多數投票法[6],人工神經網絡法，加權平均值法，決策模板[7]和D-S證據理論[8]，行為-知識空間方法(BKS)[9]等。存在的問題是，一些基分類器存在實時性能不穩定的情況，所以在使用多分類器融合方法時容易受到這種基分類器的影響而導致性能的不穩定。因此，更多的研究者開始把目光投向基分類器的選擇，特別是集成過程中的基分類器選擇[10]。這些基于基分類器選擇的多分類器系統方法不再局限于基于單個或基于全部基分類器進行融合決策，而是靈活性地組合部分互補性強且對實時樣本有較高識別率的基分類器來完成融合決策[11]。

一些研究發現，不同分類器對于分類具有互補性，異分類器的融合能夠有效提高分類精度以及推廣能力，而提高分類器間相異性的手段之一就是采用具有互補分類信息的多個不同特征集[12-13]。這些不同特征集可以是同一特征集的不同子集，也可以是異類或不同特征空間中的特征子集[13]。

針對上述動態選擇基分類器與分類器融合方法存在實時性能不穩定的問題，本文提出一種自適應子融合集成分類器方法，首先通過有放回地隨機選擇樣本完成樣本集采樣，產生多個不同的訓練集，然后通過線性判決思想(Fisher線性判決思想是：一個好的特征應該使類內離散度盡可能小,而類間離散度盡可能大。)在不同訓練子集中進行特征提取，并利用簡單的分類器對輸入的特征變量單獨進行分類,最后基于本文提出的一種基分類器選擇模型完成實時的子融合系統構建，并在該子融合系統上按分類的結果進行投票，選擇得票最多的作為分類結果輸出。

1 問題定義

多分類器系統作為一種集成分類算法(Ensemble learning)，通過基分類器集合和組合規則或組合算法模型構成。根據基分類器決策輸出信息的不同，多分類器系統一般被劃分為三個不同的層次[14]：決策層融合(Abstract level)，排序層融合(Rank level)和度量層融合(Measurement level)。在決策層融合層次上，各個基分類器的輸出為某個確定的類別號；在排序層融合層次上，各個基分類器的輸出為測試樣本屬于各類可能性的一個排序列表；在度量層融合層次上，各個基分類器的輸出為測試樣本屬于各類的后驗概率。

在實際應用中，大部分用于集成的基分類器可以獲取類似于后驗概率的中間度量值，如k-NN分類器可以利用測試樣本到各類中心的最近鄰距離來構建函數求取測試樣本屬于各類的可能性。這種可能性在同質基分類器構成的多分類器系統中可以作為基分類器選擇的考慮因素。因此，本文主要研究度量層融合層次之上的多分類器聯合方法。

1.1 數學定義

度量層融合層次的多分類器系統問題可以定義如下：

輸入：

[e1(x)e2(x) …eK(x)]：各基分類器對樣本x的識別輸出,其中，ek(x)=[ω(C1)ω(C2) …ω(CM)](k∈{1,2,…,K})，ω(Ci)∈[0,1]，ω(Ci)(i∈{1,2,…,M})為后驗概率、隸屬度或某種模糊測度，說明樣本x歸屬于各類的程度。

輸出：

E(x)=Ci:多分類器系統識別樣本所歸屬的類別，其中i∈{1,2,…,M}。

輸出結果的獲取可以通過多種不同形式實現，常見的有提取最大值、計算平均值和加權平均等。

1.2 相關定義

上述定義中，分量ωk(Ci)與ωj(Ci)的距離越小，說明它們之間的決策支持度越大。反之，則說明決策支持度越小。

上述定義中，第k個基分類器識別樣本x歸屬于Ci類的程度ωk(Ci)越靠近[0,1]區間中值0.5，其決策置信度越小.反之，則說明決策置信度越大。

2 自適應子融合系統

自適應子融合系統可以針對不同的輸入樣本，動態挑選出不同數目的基分類器組成子融合系統進行樣本識別。根據上述實時決策支持度和實時決策置信度的定義，設計基分類器動態挑選的策略，其過程為：首先提取實時決策支持度最高的基分類器，然后在多分類器系統中將其它基分類器的實時決策置信度一一與該基分類器的實時決策置信度進行比較，動態選擇出比該基分類器實時決策置信度高的基分類器，并一起構成子融合系統,最后通過簡單多數投票決定輸入樣本所歸屬的類別號。

為了提高多分類器系統的泛化能力，自適應子融合系統通過有放回隨機選擇多個不同的訓練集，并在這些訓練集上通過線性判決思想隨機動態地提取特征構成各基分類器訓練的特征子集。自適應子融合系統的方法模型框架如圖1所示。訓練樣本和訓練特征集的差異保證了多分類器系統中基分類器的互補性。

圖1 自適應子融合集成分類器方法模型

2.1 特征子集生成

在每個隨機訓練樣本集基礎上隨機提取有較優線性可分性的特征子集，首先在特征集上隨機地限定特征提取范圍，該提取范圍為隨意的部分特征組合，以提高基分類器的差異性。然后，在隨機挑選出第一個特征的基礎上利用線性判決思想在這些隨機提取的特征組合中通過迭代重組出線性可分性較強的特征子集。具體特征子集生成算法如算法1所示。

算法1:特征選擇：

Input: 特征集F.

Output: 特征子集S.

1)獲取特征集F的特征個數m;

2)初始化: Lsd=0, max_Lsd=0, first_i=0, S=φ,i=0;

3)隨機生成長度為m的二進制字符串a;

4)在a中隨機選擇值為1的某個位置first_i;

5)S=S∪{F[first_i]};

6)max_Lsd=calculate_Lsd(S);

7)while i

8) if (a[i]==1 && i!=first_i) then

9) Lsd=calculate_Lsd(S∪{ F[i]});

10) if Lsd>max_Lsd then

11) S=S∪{F[i]}; max_Lsd=Lsd;

12) end if

13) end if

14) i++;

15)end while

16)return(S,a).

其中，步驟6)中calculate_Lsd函數為特征集輸入參數S在當前隨機樣本集中的線性可分度，線性可分度Lsd的計算公式如式(1)所示。其中，c為特征集S存在的類別數，Xi為當前隨機樣本集中屬于第i類的樣本集合。

(1)

特征子集生成算法在自適應子融合系統中是基于多個不同樣本集分別實現的，其實現過程可以并行處理。因此，有可能存在相同的特征子集被不同基分類器提取。本文通過兩種不同的策略來優化提取的特征子集，提高基分類器的差異性。這兩種策略分別是變異策略和交叉策略，具體方法如下所示：

交叉策略：隨機選擇一個不同的特征選擇向量a2,在a2中隨機選擇一個交叉區域，將a的相應交叉區域由a2交叉區域代替。

例如，存在相同特征子集的特征選擇向量為a=10011100，選擇的a2為a2=00100110，交叉區域為0011，則進行交叉操作后有：a=10000110。

通過雙重循環將所有生成的特征子集進行比較，存在相同的特征子集進行1次或多次變異和交叉操作，直至得到一個與現有所有特征子集不重復的新特征子集。

2.2 基分類器動態選擇

在隨機樣本和特征子空間生成后，分別訓練基分類器,因為自適應子融合系統基于1.2節中定義的實時決策支持度和實時決策置信度動態選擇集成，所以動態選擇基分類器操作在測試階段進行。

首先通過多分類器系統中的各個基分類器對輸入測試樣本進行分類識別，然后分別計算各基分類器的實時決策支持度DS，并從中挑選出獲得當前實時決策支持度最高的基分類器，將其作為自適應子融合系統的基分類器，并用該基分類器的實時決策置信度與其它基分類器的實時決策置信度進行比較，進一步挑選出實時決策置信度比其高的基分類器作為自適應子融合系統的成員，完成用來融合決策的子系統構建,算法流程如下：

算法2:基分類器動態選擇.

Input: 分類器集合E.

Output: 分類器子集合S.

1)初始化:S=φ;

2)從E中選擇當前樣本識別中DS最高的基分類器ec;

3)S={ec};

4)E=E-{ec};

5)θ=DC(ec);

6)while E!=NULL

7) if DC(E[0])>θthen

8)S=S∪{ei};

9) end if

10)E=E-{ei};

11)end while

12)return(S).

該方法對于輸出結果帶有類似后驗概率的分類器進行直接軟迭代集成，對于其他輸出形式的基分類器需要先將其輸出值轉化到[0,1]上的可信度，然后再利用算法。本文定義其輸出值轉化方法為：

ek(x)=[Pk(C1|x),Pk(C2|x),…,Pk(CM|x)]

基于上述方法可以得到多分類器系統的決策矩陣如下：

2.3 融合決策過程

自適應子融合集成分類方法融合了一系列基分類器的分類結果, 直接采用多數投票法來決定識別結果，讓當前被自適應子融合系統選中的基分類器都對輸入的特征向量進行投票，匯總各類得票數，找出其中擁有票數最多的類別作為融合系統對該特征向量識別的類別。

3 實驗結果與分析

本實驗使用的是UCI機器學習數據庫中的四類數據集進行相關測試。數據集樣本如表1所示。實驗數據屬于多分類樣本數據集，需限定使用方法為多分類方法，以保證分類的效果，實驗基分類器如表2所示。有效劃分訓練集與測試集比重往往可以提高分類的效率，參照先驗知識且經過多次試驗測試集與訓練集比例，最終發現30%作為訓練集、70%作為測試集的實驗效果最好，因此我們將各類數據集分別按照0.3的比例劃分。

本文將分類準確率作為衡量融合集成分類器方法識別效果的衡量標準，具體方法是測試集中分類正確數量占總測試集的百分比，公式如式(2)：

(2)

其中:Nk表示測試集中分類正確的數量，Nc表示測試集的總數。

表2實驗結果數據表明，本文提出的自適應子融合集成分類方法與其他基分類器比較，本文方法的識別效果更優，在所用數據集都得到了有效提升。同時，表2也表明了在Vehicle數據集、Glass數據集上一些基分類器識別性能較差的現象。驗證了本文前面提到的基分類器實時穩定性差從而導致一些融合方法的性能不穩定的問題。本文提出的自適應子融合集成多分類器方法從表3中明顯證明識別性能優于其他兩種多分類器融合方法，并且在Wine數據集和Vehicle數據集效果提升稍好于其他兩類數據集。通過表2、表3，我們可以得出以下結論：多分類問題，數據類別越多，分類的準確率越高，即分類效果越好。

表1 實驗的四類數據集

表2 本文方法與基本分類器識別準確度比較 %

表3 本文方法與其他多分類器聯合方法識別準確度比較 %

從圖2中，我們可以直觀看到各基分類器與多分類器融合方法的分類性能，并且在分類性能上多分類器融合方法普遍優于基分類器方法，本文方法在識別準確率上同樣高于所比較的其他分類融合方法。

圖2 各基分類器與分類器融合方法性能比較

4 結論

本文基于Fisher線性判決思想來完成隨機特征子集內的特征選擇有效提高基分類器的差異性，結合決策支持度DS與決策置信度DC完成基分類器的動態選擇，并讓每一個被選中的基分類器對輸入的特征向量進行投票，計算所有投票數，獲取子融合系統中投票數最多的類別作為當前輸入樣本的分類結果，有效提高了分類器識別性能。實驗結果表明，本文研究的度量層融合層次之上的多分類器聯合方法能獲得較好的識別性能，較單個分類器的識別準確度都有所提高。

我們的工作存在如下不足：在未來的研究中需要解決的問題，如基分類器選擇當前實時決策支持度最高者，是否可以通過先驗概率或判別函數確定基分類器會有更好的分類效果。