半動(dòng)態(tài)集成選擇分類方法

李 瑞，袁小玲

(1.陜西財(cái)經(jīng)職業(yè)技術(shù)學(xué)院會計(jì)二系，陜西 咸陽 712000;2.陜西財(cái)經(jīng)職業(yè)技術(shù)學(xué)院會計(jì)一系，陜西 咸陽 712000)

0 引言

近年來，多分類器系統(tǒng)(MCS)得到了越來越廣泛的關(guān)注，并且已經(jīng)成功應(yīng)用到多個(gè)領(lǐng)域，比如風(fēng)險(xiǎn)評估［1］、文本分類［2］、以及變化檢測［3］、故障診斷［4］、遙感分類［5］等。目前，已經(jīng)提出一些經(jīng)典的集成策略，比 如Bagging［6-7］、Boosting［8-9］和隨機(jī)子空間方法［10-11］。由于以上這些方法中的每一個(gè)子分類器都要為測試樣本輸出一個(gè)結(jié)果，可能會存在冗余，而這會導(dǎo)致較高的計(jì)算復(fù)雜度。更為嚴(yán)重的是，如果子分類器集合中存在弱分類器，那么分類性能會受到極大影響。為了解決這一問題，有學(xué)者提出了選擇性集成(SE)［12-13］，該方法能夠避免傳統(tǒng)集成分類器的缺點(diǎn)［14］。目前已經(jīng)提出了一些方法，比如遺傳算法［12］、半正定規(guī)劃［15］、強(qiáng)化學(xué)習(xí)［16］、Reduce-error Pruning［15］等方法。

眾所周知，在實(shí)際應(yīng)用中，不同的測試樣本在分類時(shí)會遇到不同的困難。而在SE 中，由于所選擇的個(gè)體分類器集合相同，也會降低分類性能。但是，如果能夠?yàn)槊恳粋€(gè)測試樣本動(dòng)態(tài)地選擇分類器，會進(jìn)一步提高分類性能?；诖?，近年來，有學(xué)者提出了動(dòng)態(tài)集成選擇策略(DES)［17］。由于該策略能夠動(dòng)態(tài)地為每一個(gè)測試樣本選擇合適的個(gè)體分類器組成集成分類器，因而能夠獲得更好的性能。目前已經(jīng)提出一些策略，比如K-Nearest-ORAcles(KNORA)［17］、Local Accuracy and Diversity Method［18］、Measure of Competence based on Random Classification Method［19］等。

盡管DES 能夠獲得更好的性能，但是當(dāng)前的策略需要為每一個(gè)測試樣本選擇多個(gè)分類器。這使得當(dāng)前策略的計(jì)算復(fù)雜度較高。為了解決這一問題，本文提出一種新的半動(dòng)態(tài)集成選擇策略(Semi-DES)。該策略吸取了SE 和DES 的優(yōu)點(diǎn)。不僅能夠降低計(jì)算復(fù)雜度，而且能夠進(jìn)一步提高分類性能。在Semi-DES 中，首先為所有的樣本選擇最好的一部分子分類器，然后在剩余的子分類器集合中為每一個(gè)測試樣本動(dòng)態(tài)地選擇個(gè)體分類器，最終的結(jié)果通過融合以上2部分的輸出得到。為了驗(yàn)證所提策略的性能，本文采用UCI 數(shù)據(jù)集驗(yàn)證。與其他方法相比，所提策略是一種非常有效的方法。

1 Semi-DES 策略

在這一節(jié)，首先給出Semi-DES 策略的框架，然后給出對應(yīng)的算法。

1.1 框架

Semi-DES 包括2 個(gè)階段:第一階段靜態(tài)地選擇個(gè)體分類器;第二階段為每一個(gè)測試樣本動(dòng)態(tài)地選擇個(gè)體分類器。以一個(gè)多分類問題為例。假設(shè)訓(xùn)練樣本為:

其中yi表示標(biāo)記，D 表示樣本特征的數(shù)量，C 表示類別數(shù)量，L 表示用來訓(xùn)練樣本的數(shù)量。

假設(shè)所產(chǎn)生的個(gè)體分類器為C={C1，C2，...，CM}，其中M 表示個(gè)體分類器的數(shù)量。由于要生成2個(gè)集成分類器，并且將最終的結(jié)果融合起來，需要給出權(quán)值，這里用w1，w2表示，并且需要滿足如下限制:

在第一階段，為所有的測試樣本選擇個(gè)體分類器。這些子分類器被認(rèn)為是“優(yōu)秀的”子分類器。假設(shè)所選擇的個(gè)體分類器為}，其中I 表示分類器的數(shù)量。顯然C1?C，并且I ≤M。由于所選擇的個(gè)體分類器相對重要性不同，因而這里給出對應(yīng)的權(quán)值］，并且滿足如下限制:

最終的標(biāo)記為:

整個(gè)過程如圖1 所示。

圖1 Semi-DES 的框架

1.2 所提算法

在這一節(jié)提出了用于實(shí)現(xiàn)Semi-DES 的算法，算法包括2 階段。這里假設(shè)所有的權(quán)值均相同，并假設(shè)2 階段的權(quán)值為W1，W2。在第一個(gè)階段，為所有的測試樣本選擇一部分相同的個(gè)體分類器。由于進(jìn)化計(jì)算能夠取得全局最優(yōu)解，該算法在第一階段用于選擇個(gè)體分類器。本文采用遺傳算法實(shí)現(xiàn)。在遺傳算法中，每一個(gè)個(gè)體的編碼中，“1”表示選擇了個(gè)體分類器，“0”表示個(gè)體分類器沒有選擇，所產(chǎn)生的個(gè)體分類器的數(shù)量為M。假設(shè)所有選擇的分類器的權(quán)值相同。種群隨機(jī)初始化，目標(biāo)函數(shù)為分類準(zhǔn)確率，如式(5)所示:

其中N 表示正確分類的樣本數(shù)量，T 表示訓(xùn)練樣本的數(shù)量。接下來算法將會迭代執(zhí)行直到滿足終止條件。所選擇的個(gè)體分類器是}，其中I表示個(gè)體分類器的數(shù)量，這些個(gè)體分類器會為每個(gè)測試樣本使用。接下來將從剩余的個(gè)體分類器中為每一個(gè)樣本選擇個(gè)體分類器。在本文中采用KNORA［12］選擇個(gè)體分類器。驗(yàn)證集合與訓(xùn)練集合相同。對每個(gè)測試樣本，采用K 近鄰的方法提取驗(yàn)證集，然后判斷哪一個(gè)分類器更合適。如果當(dāng)前的個(gè)體分類器能夠正確地分類驗(yàn)證集，那么將選擇當(dāng)前的個(gè)體分類器作為該測試樣本的個(gè)體分類器，否則，該個(gè)體分類器不被選擇;如果所有的分類器都不能準(zhǔn)確地分類驗(yàn)證集，那么令K=K -1。這一過程將會持續(xù)進(jìn)行直到至少選擇出一個(gè)個(gè)體分類器。當(dāng)K=1 時(shí)，如果沒有任何一個(gè)分類器能夠被提取出來，將采用所有的分類器用于分類。所選擇的分類器為，其中P 表示分類器的數(shù)量。在選擇出分類器之后，采用公式(3)得到最終的輸出。算法如下所示。

算法1

輸入:訓(xùn)練集合T 和測試樣本X;

步驟1:產(chǎn)生個(gè)體分類器C={C1，C2，…，CM};

步驟3:從剩余的個(gè)體分類器中利用K 近鄰方法為每一個(gè)樣本選擇分類器;

輸出:最終的結(jié)果由公式(3)得到。

2 實(shí) 驗(yàn)

在這一節(jié)，所提算法采用UCI 數(shù)據(jù)集驗(yàn)證。首先給出實(shí)驗(yàn)設(shè)置，其次給出實(shí)驗(yàn)結(jié)果。

2.1 實(shí)驗(yàn)設(shè)置

本文采用14 個(gè)UCI 數(shù)據(jù)集［20］驗(yàn)證所提算法。表1 給出了數(shù)據(jù)集的屬性，比如樣本數(shù)量、屬性和類別。這里采用10 倍交叉驗(yàn)證，所有實(shí)驗(yàn)在MATLAB 2009a 平臺上執(zhí)行，采用Intel 酷睿2 處理器，主頻3.0 GHz，內(nèi)存為2 G，在Windows XP 系統(tǒng)上驗(yàn)證。

本實(shí)驗(yàn)采用Bagging 產(chǎn)生個(gè)體分類器，F(xiàn)isher 判別分析(FDA)和K 近鄰分類器(KNN)作為個(gè)體分類器，產(chǎn)生個(gè)體分類器的數(shù)量為20。4 種典型的算法用于比較:

1)最好的單分類器(SB)。集成分類器中最好的單分類器。

2)傳統(tǒng)集成分類器(ALL)［4］。該集成分類器采用投票機(jī)制得到最終的輸出。

3)基于遺傳算法的選擇性集成方法(SE-GE)。該方法利用遺傳算法靜態(tài)的選擇個(gè)體分類器。

4)KNORA 方法［12］。該方法是一種典型的動(dòng)態(tài)集成選擇方法。

表1 數(shù)據(jù)集的描述

2.2 實(shí)驗(yàn)結(jié)果

表2 和表4 給出了運(yùn)行10 次的平均分類準(zhǔn)確率，黑體部分表示每一個(gè)數(shù)據(jù)集的最好性能。顯然，在大部分情況下，Semi-DES 能夠取得更高的分類性能。表2 給出了基分類器是FDA 時(shí)的結(jié)果。除了Car 和Mammographic 數(shù)據(jù)集外，所提算法在其他數(shù)據(jù)集都取得了最好的性能。表3 給出了基分類器是KNN 時(shí)的結(jié)果(這里近鄰的數(shù)量設(shè)為10)。除了Liver、Brest Cancer、Spam 和Nursery 數(shù)據(jù)集外，Semi-DES 均能取得最好的性能。表3 和表5 給出了平均分類結(jié)果的標(biāo)準(zhǔn)差。通過統(tǒng)計(jì)分析，以P ＜0.05 為顯著性差異水平，可以看出所提算法要優(yōu)于其它比較算法。

表2 FDA 作為基分類器時(shí)的平均分類結(jié)果

表3 FDA 作為基分類器時(shí)平均分類結(jié)果的標(biāo)準(zhǔn)差

表4 KNN 作為基分類器時(shí)的平均分類結(jié)果

表5 KNN 作為基分類器時(shí)平均分類結(jié)果標(biāo)準(zhǔn)差

3 結(jié)束語

本文提出了一種新的半動(dòng)態(tài)集成選擇策略(Semi-DES)。該策略充分吸收了SE 和DES 的優(yōu)勢，并且能夠取得更好的分類性能。首先給出了該策略的框架，并且提出了相應(yīng)的算法，實(shí)驗(yàn)結(jié)果和統(tǒng)計(jì)分析表明所提算法能夠取得較好的分類性能。所提Semi-DES 是一種通用的框架，其他SE 和DES 方法也可以嵌入到該框架中，這將在以后的研究中做進(jìn)一步闡述。

［1］Marques A I，Garcia V，Sanchez J S.Two-level classifier ensembles for credit risk assessment［J］.Expert Systems with Applications，2012，39(12):10244-10250.

［2］Michelangelo Paci，Loris Nanni，Stefano Severi.An ensemble of classifier based on different texture descriptors fortexture classification［J］.Journal of King Saud University-Science，2013，25(3):235-244.

［3］Moumita Roy，Susmita Ghosh，Ashish Ghosh.A novel approach for change detection of remotely sensed images using semi-supervised multiple classifier system［J］.Information Science，2014，269(10):35-47.

［4］慕昱，夏虹，劉永闊.基于集成學(xué)習(xí)的核電站故障診斷方法［J］.原子能科學(xué)技術(shù)，2012，46(10):1254-1258.

［5］劉培，杜培軍，譚琨.一種基于集成學(xué)習(xí)和特征融合的遙感影像分類新方法［J］.紅外與毫米波學(xué)報(bào)，2014，33(3):311-317.

［6］Mordelet F，Vert J P.A bagging SVM to learn from positive and unlabeled examples［J］.Pattern Recognition Letters，2014，37(1)，201-209.

［7］李明方，張化祥.針對不平衡數(shù)據(jù)集的Bagging 改進(jìn)算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(30):40-42.

［8］Nicolas Garcia-Pedrajas，Aida de Haro-Garcia.Boosting instance selection algorithm［J］.Knowledge-based Systems，2014，67(9):342-360.

［9］于玲，吳鐵軍.集成學(xué)習(xí):Boosting 算法綜述［J］.模式識別與人工智能，2004，17(1):52-59.

［10］Le Zhang，Ponnuthrai Nagaratnam Suganthan.Random Forest with ensemble of feature spaces［J］.Pattern Recognition，2014，47(10):3429-3437.

［11］楊明，王飛.一種基于局部隨機(jī)子空間的分類集成算法［J］.模式識別與人工智能，2012，25(4):595-603.

［12］Zhou Zhihua，Wu Jianxin，Tang Wei.Ensembling neural networks:Many could be better than all［J］.Artificial Intelligence，2002，137(1-2):239-263.

［13］張春霞，張講社.選擇性集成學(xué)習(xí)算法綜述［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(8):1399-1410.

［14］Zhang Li，Zhou Weida.Sparse ensembles using weighted combination methods based on linear programming［J］.Pattern Recognition，2011，44(1):97-106.

［15］Margineantu D D，Dietterich T G.Pruning adaptive boosting［C］// Proceedings of the Fourteenth International Conference on Machine Learning.1997:211-218.

［16］Partalas I，Tsoumakas G，Vlahavas I.Pruning an ensemble of classifiers via reinforcement learning［J］.Neurocomputing，2009，72(7-9):1900-1909.

［17］Albert H R Koa，Robert Sabourina，Alceu Souza Britto Jr.From dynamic classifier selection to dynamic ensemble selection［J］.Pattern Recognition，2008，41(5):1718-1731.

［18］DeSouto M C P，Soares R G F，Santana A，et al.Empirical comparison of dynamic classifier selection methods based on diversity and accuracy for building ensembles［C］// Proceedings of the International Joint Conference on Neural Networks.2008:1480-1487.

［19］Tomasz Woloszynski，Marek Kurzynski，Pawel Podsiadlo，et al.A measure of competence based on random classification for dynamic ensemble selection［J］.Information Fusion，2012，13(3):207-213.

［20］Newman D J，Hettich S，Blake C L，et al.UCI Repository of Machine Learning Databases［EB/OL］.http://www.ics.uci.edu/～mlearn/MLRepository.html，2014-11-21.