一種自適應(yīng)子融合集成多分類器方法

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

0 引言

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

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

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

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

1 問題定義

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

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

1.1 數(shù)學(xué)定義

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

輸入：

[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:多分類器系統(tǒng)識別樣本所歸屬的類別，其中i∈{1,2,…,M}。

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

1.2 相關(guān)定義

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

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

2 自適應(yīng)子融合系統(tǒng)

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

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

圖1 自適應(yīng)子融合集成分類器方法模型

2.1 特征子集生成

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

算法1:特征選擇：

Input: 特征集F.

Output: 特征子集S.

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

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

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

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函數(shù)為特征集輸入?yún)?shù)S在當前隨機樣本集中的線性可分度，線性可分度Lsd的計算公式如式(1)所示。其中，c為特征集S存在的類別數(shù)，Xi為當前隨機樣本集中屬于第i類的樣本集合。

(1)

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

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

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

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

2.2 基分類器動態(tài)選擇

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

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

算法2:基分類器動態(tài)選擇.

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).

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

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

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

2.3 融合決策過程

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

3 實驗結(jié)果與分析

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

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

(2)

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

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

表1 實驗的四類數(shù)據(jù)集

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

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

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

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

4 結(jié)論

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

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