融合樣本選擇與特征選擇的AdaBoost支持向量機集成算法

楊宏暉,王蕓,孫進才,戴健,李亞安

(西北工業(yè)大學(xué)航海學(xué)院, 710072, 西安)

融合樣本選擇與特征選擇的AdaBoost支持向量機集成算法

楊宏暉,王蕓,孫進才,戴健,李亞安

(西北工業(yè)大學(xué)航海學(xué)院, 710072, 西安)

為提高AdaBoost分類器集成算法的分類精確度并簡化分類系統(tǒng)的復(fù)雜度,提出一種融合樣本選擇與特征選擇的AdaBoost支持向量機集成算法(IFSelect-SVME)。該算法在AdaBoost算法的每個循環(huán)中利用加權(quán)免疫克隆樣本選擇算法進行樣本選擇,并用互信息順序向前特征選擇算法進行特征選擇,再利用每個循環(huán)優(yōu)化選擇得到的特征樣本子集訓(xùn)練個體SVM分類器,并對其進行加權(quán)集成,生成最終的決策系統(tǒng)。對實驗所用9組UCI數(shù)據(jù)集的仿真結(jié)果表明:與支持向量機集成(SVME)算法相比,IFSelect-SVME算法的正確分類率有所提高,且樣本數(shù)可減少30.8%～80.0%,特征數(shù)可減少32.2%～81.5%,簡化了集成結(jié)構(gòu),縮短了測試樣本的分類時間,所得到的分類系統(tǒng)具有更好的分類精度。

分類器集成;AdaBoost算法;支持向量機;樣本選擇;特征選擇

在統(tǒng)計模式識別領(lǐng)域,分類器集成作為提高分類系統(tǒng)精確度和泛化性能的重要方法[1],主要通過生成并組合個體分類器來實現(xiàn)分類[2-4]。但是,分類器集成在實際應(yīng)用中存在2個主要問題：①訓(xùn)練分類器的樣本和特征常含有噪聲樣本與冗余特征,這導(dǎo)致分類器集成的實際結(jié)果與理論值相差甚遠;②分類器集成勢必增加分類系統(tǒng)的復(fù)雜度,導(dǎo)致分類時間過長,限制了分類系統(tǒng)在對在線測試時間有要求領(lǐng)域的應(yīng)用。近年來,研究者們試圖設(shè)計出更有效的集成實現(xiàn)方式解決這2個問題。AdaBoost算法[5-6]作為一種經(jīng)典的分類器集成算法,通過加大權(quán)值來強化對難分樣本的學(xué)習(xí),提高弱分類器的分類精度,構(gòu)建更強的集成分類器,但并未去除掉噪聲樣本和冗余特征的不良影響,且系統(tǒng)仍然具有較高的復(fù)雜度;文獻[7-8]在AdaBoost算法的基礎(chǔ)上進行了改進,引入多視圖的概念來構(gòu)建集成分類器,進一步提高了分類精度,但分類系統(tǒng)仍然不夠精簡;文獻[9]通過動態(tài)地選擇個體分類器并將其循環(huán)集成,大大降低了分類系統(tǒng)的復(fù)雜度,但未考慮到訓(xùn)練集中所含的噪聲樣本和冗余特征;文獻[10]將集成思想用在特征選擇和分類器設(shè)計中,在一定程度上能夠去除冗余特征,提高分類精度并節(jié)省分類時間,但沒有考慮到噪聲樣本對分類的影響;文獻[11]在融合特征選擇和分類器集成的基礎(chǔ)上又對個體分類器進行了選擇,進一步縮小了集成規(guī)模,簡化了計算復(fù)雜度,但噪聲樣本對分類系統(tǒng)的影響依然存在;文獻[12]將樣本選擇融入AdaBoost分類器集成模型之中來提高集成系統(tǒng)的分類精度,簡化集成結(jié)構(gòu),但又忽略了冗余特征對分類的影響。

針對上述問題,本文提出一種融合樣本選擇與特征選擇的AdaBoost支持向量機[13]集成算法(AdaBoost SVM ensemble algorithm combined with instance selection and feature selection, IFSelect-SVME)。本文算法在AdaBoost分類器集成框架中融入樣本選擇[14-15]和特征選擇[16-17],剔除掉了訓(xùn)練子集中的噪聲樣本和冗余特征,提高了集成分類器的的學(xué)習(xí)效率和學(xué)習(xí)精度。采用UCI公共數(shù)據(jù)庫中的數(shù)據(jù)集本進行的分類實驗結(jié)果表明,本文算法能夠在降低特征與樣本數(shù)的同時提高或保持SVME的正確分類率,具有良好的泛化性能。

1 AdaBoost算法

AdaBoost算法[5-6]首先采用隨機遍歷抽樣法抽取訓(xùn)練樣本集,再用訓(xùn)練樣本集訓(xùn)練個體分類器;在每次循環(huán)中,根據(jù)樣本是否被分類正確而賦予不同的加權(quán)權(quán)值,被錯誤分類的樣本權(quán)值較大,被正確分類的樣本權(quán)值較小;然后根據(jù)不同樣本的加權(quán)權(quán)值對原有的訓(xùn)練樣本集進行重抽樣,重點抽取難分類的樣本,直到生成多個個體分類器;最后采用加權(quán)多數(shù)投票法對個體分類器進行集成。

2 IFSelect-SVME算法

2.1 IFSelect-SVME算法的原理

本文IFSelect-SVME算法采用了AdaBoost算法的集成框架,首先采用加權(quán)免疫克隆樣本選擇算法進行樣本選擇,再使用互信息順序向前特征選擇進行特征選擇,以保證在每個循環(huán)中只選擇最優(yōu)的樣本和特征來訓(xùn)練個體SVM分類器。這樣得到的優(yōu)化子集訓(xùn)練的個體分類器往往具有更高的分類精度,且隨著訓(xùn)練集中噪聲樣本和冗余特征的去除,個體分類器的復(fù)雜度也大大降低,由所得到的個體分類器進行加權(quán)集成,最終生成的決策系統(tǒng)的分類精度也有所提升。IFSelect-SVME算法原理如圖1所示。

圖1 IFSelect-SVME原理圖

2.2 加權(quán)免疫克隆樣本選擇算法

在IFSelect-SVME算法中,利用加權(quán)免疫克隆樣本選擇算法進行樣本選擇[15]。加權(quán)免疫克隆樣本選擇算法先隨機生成初始抗體種群,然后根據(jù)樣本權(quán)值計算抗體的加權(quán)親和度(抗體-抗原加權(quán)親和度與抗體-抗體間親和度) 以及克隆數(shù),再利用克隆操作、免疫基因操作(海明距離交叉與隨機變異)以及克隆選擇操作指導(dǎo)種群的進化,循環(huán)往復(fù),直到達到終止條件。在該算法中,一個抗體代表一種樣本選擇方式,抗體-抗原加權(quán)親和度表示某抗體的分類性能,而抗體-抗體間親和度則表示不同抗體之間的差異程度,體現(xiàn)出抗體群的多樣性。每個抗體的克隆數(shù)則通過抗體-抗原加權(quán)親和度和抗體-抗體間親和度來控制。

加權(quán)免疫克隆樣本選擇算法的步驟如下:

Step1隨機生成初始種群。對于某一樣本集X={(xi,yi)|xi∈Rd,yi∈{1,…,K},i=1,…,n},將樣本選擇問題編碼為二進制基因鏈Φ=(φ1,φ2,…,φi,…,φn),其中φi為個體基因編碼,n為樣本數(shù),φi=1表示第i個樣本被選中,φi=0表示第i個樣本未被選中,隨機生成初始抗體種群O。

Step2加權(quán)親和度計算。計算分為以下2個步驟。

(1)抗體-抗原加權(quán)親和度Gj計算如下

Gj(k)=1-Ej(k)

(1)

(2)抗體-抗體間親和度Bj計算如下

(2)

式中:αj(k)與αq(k)分別表示第k代抗體種群中的第j個和第q個抗體。

Step3克隆算子操作。操作分為以下3個步驟。

(1)克隆操作:根據(jù)每個抗體進行克隆,得到克隆種群Or;用式(3)計算抗體克隆數(shù)

(3)

式中:λj(k)為第j個抗體的克隆數(shù);δr為克隆規(guī)模設(shè)定值。

(2)免疫基因操作:對克隆種群Or以概率Ps進行海明距離交叉,產(chǎn)生交叉種群Os,再對Ot按概率Pt進行隨機變異,得到變異種群Ot[13]。

(3)克隆選擇操作:比較父代與免疫基因操作后子代抗體種群,選擇出其中抗體-抗原加權(quán)親和度高的一個抗體,組成新一代抗體種群O′。

克隆算子操作保證了在本次循環(huán)中,用優(yōu)化樣本子集訓(xùn)練的個體分類器的分類精度大于等于不做樣本選擇時訓(xùn)練的個體分類器的分類精度。

Step4判斷。若到達終止條件(終止條件通常為設(shè)定的循環(huán)次數(shù)),則輸出最優(yōu)解;否則,轉(zhuǎn)至Step2。

2.3 互信息順序向前特征選擇算法

在IFSelect-SVME算法中,用互信息順序向前特征選擇算法進行特征選擇。該算法用特征與類別之間的互信息值[16]來評價特征的分類性能,并利用順序向前特征選擇方法[15]來搜索最優(yōu)特征子集。特征f與類別L之間的互信息計算公式如下

I(L;f)=H(L)-H(L|f)

(4)

式中:H(L)是類別L的熵;H(L|f)是在特征f條件下類別L的熵?；バ畔⒅翟酱?則表示特征與類別的相關(guān)程度越強,特征包含的分類信息越多,特征的分類性能也就越強。

2.4 生成分類系統(tǒng)

IFSelect-SVME算法采用加權(quán)多數(shù)投票法對每次循環(huán)生成的個體SVM分類器進行集成,用每一個個體分類器對樣本進行決策,對自己所預(yù)測樣本的類別投一票,最終,票數(shù)最多的類別被確定為這個樣本的類別,直到所有樣本的類別被全部預(yù)測,所得到的分類結(jié)果即為分類器集成的最終分類結(jié)果。

3 實 驗

3.1 實驗數(shù)據(jù)

本文利用加州大學(xué)用于機器學(xué)習(xí)的UCI(University of California Irvine, UCI)數(shù)據(jù)庫[19]中的9種數(shù)據(jù)集對IFSelect-SVME算法的性能進行驗證實驗,9種數(shù)據(jù)集的特征均為數(shù)值類型,包含連續(xù)型(continued,C)、離散型(discreted,D)和混合型(mixed,M)特征。數(shù)據(jù)集的詳細信息如表1所示。

表1 實驗數(shù)據(jù)

3.2 分類實驗

采用表1中的9種數(shù)據(jù)集對本文的IFSelect- SVME算法進行分類實驗,通過分類性能、特征選擇性能、樣本選擇性能以及分類時間等幾個指標對本文IFSelect-SVME算法的有效性進行了分析。

表2 2種算法的分類性能對比

從表2中可以看到,對于不同的數(shù)據(jù)集,本文IFSelect-SVME算法選擇的特征數(shù)與樣本數(shù)都少于SVME算法。對于離散型數(shù)據(jù)zoo,IFSelect-SVME算法在每個循環(huán)中平均僅用31%的特征數(shù)和28%的樣本數(shù)來訓(xùn)練個體分類器,平均正確分類率比SVME算法可提高4%;對于混合型數(shù)據(jù)Indian-L,則平均需用20%的特征數(shù)與68%的樣本數(shù)訓(xùn)練個體分類器,正確分類率可提高2%;本文算法對其他幾種連續(xù)型數(shù)據(jù)的正確分類率都有提高,而樣本選擇數(shù)只有SVME算法的18%～54%;特征選擇數(shù)也只有SVME算法的33%～85%。因此不論對于何種特征類型的數(shù)據(jù),IFSelect-SVME算法均能夠提高分類系統(tǒng)的正確分類率,同時大幅度壓縮訓(xùn)練樣本數(shù)與特征數(shù)。

3.2.2 樣本選擇結(jié)果 當用加權(quán)免疫克隆算法進行樣本選擇時,每次循環(huán)中選擇出的樣本都是不同的。根據(jù)每個樣本被選擇的次數(shù),定義樣本重要性指數(shù),可按式(5)計算

Vi=ui/Z

(5)

式中:Vi是第i個樣本的重要性指數(shù);Z為訓(xùn)練個體分類器的個數(shù);ui是第i個樣本Z次分類器生成中被選擇的次數(shù)。樣本的重要性指數(shù)越高,對分類就越有效。用該算法對9種數(shù)據(jù)進行樣本選擇,得到歸一化樣本重要性指數(shù)。不同樣本集的歸一化重要性指數(shù)如圖2所示。

(a)wine (b)zoo

(c)wdbc (d)sonar

(e)parkinsons (f)ionospheres

(g)Indian-L (h)glass

(i)climate

從圖2可以看出,對于不同數(shù)據(jù)集,不同樣本的歸一化重要性指數(shù)都有著明顯的差別。本文算法只選取了重要性指數(shù)高于0.5的樣本作為樣本選擇結(jié)果。選取重要性指數(shù)高的樣本來組建最優(yōu)的樣本子集,就可以訓(xùn)練出分類性能更好的個體分類器。

(a)wine (b)zoo

(c)wdbc (d)sonar

(e)parkinsons (f)ionosphere

(g)Indian-L (h)glass

(i)climate

3.2.3 特征選擇結(jié)果 根據(jù)IFSelect-SVME算法中互信息順序向前特征選擇法的原理,可得到選取不同維數(shù)特征時對應(yīng)的平均正確分類率,如圖3所示。從圖3可以看出,隨著特征選擇數(shù)的增加,不同數(shù)據(jù)集的分類率曲線大體呈現(xiàn)先上升,到達某一值后趨于平穩(wěn)或又有所下降的趨勢;glass與ionosphere數(shù)據(jù)集的分類率曲線上下波動,但仍在中間的某一點處取得最大值。這說明,所有的數(shù)據(jù)集都只需要選取部分維數(shù)的特征就可以使得分類率達到最大,過少的特征使得正確分類率不能達到理想的效果,且冗余的特征也會導(dǎo)致分類率變差,說明IFSelect-SVME中的特征選擇不僅可以降低特征維數(shù),還可以提高分類精度。

3.2.4 IFSelect-SVME與SVME算法的分類時間對比 圖5給出了IFSelect-SVME算法與SVME算法訓(xùn)練相同數(shù)量分類器的分類時間對比。

圖4 2種算法的分類時間對比

從圖4可以看出,IFSelect-SVME比SVME算法對9種數(shù)據(jù)的分類時間都有所減少,這說明IFSelect-SVME算法精簡了個體分類器的復(fù)雜度,為分類節(jié)省了時間。

4 結(jié) 論

本文提出了一種融合樣本選擇和特征選擇的AdaBoost支持向量機集成算法,利用AdaBoost算法構(gòu)造集成模型,通過樣本選擇和特征選擇優(yōu)化訓(xùn)練子集來生成個體分類器,并將所得的個體分類器用加權(quán)多數(shù)投票的方法進行集成,從而得到最終的綜合分類器。采用本文算法對9種UCI數(shù)據(jù)集進行分類實驗,結(jié)果表明,本文算法對于多種數(shù)據(jù)均可有效地指導(dǎo)對最優(yōu)樣本和特征子集的搜索,大幅度減少樣本數(shù)和特征數(shù),且經(jīng)過樣本選擇和特征選擇后的分類器集成模型與未經(jīng)樣本選擇和特征選擇的分類器集成模型相比,具有更好的分類性能,因此本文算法具有一定的普適性和有效性,具有良好的推廣價值。

[1] MIKEL G, ALBERTO F, BDURNE B, et al. A review on ensembles for the class imbalance problem: bagging-, boosting-, and hybrid-based approaches [J]. IEEE Transactions on Systems, Man, and Cybernetics: Part C Applications and Reviews, 2012, 42(4): 463-484.

[2] 張宏達, 王曉丹, 韓鈞, 等. 分類器集成差異性研究 [J]. 系統(tǒng)工程與電子技術(shù). 2009, 31(12): 3007-3012. ZHANG Hongda, WANG Xiaodan, HAN Jun, et al. Survey of diversity researches on classifier ensembles [J]. Systems Engineering and Electronics, 2009, 31(12): 3007-3012.

[3] WINDEATT T. Accuracy/diversity and ensemble MLP classifier design [J]. IEEE Transactions on Neural Networks, 2006, 5(17): 1194-1211.

[4] SUN Shiliang. Local within-class accuracies for weighting individual outputs in multiple classifier systems [J]. Pattern Recognition Letters, 2010, 31: 119-124.

[5] FREUND Y, SCHAPIRE R E. A decision-theoretic generalization of on-line learning and an application to boosting [J]. Journal of Computer and System and Science, 1997, 63(5): 119-139.

[6] 曹瑩, 苗啟廣, 劉家辰, 等. AdaBoost算法研究進展與展望 [J]. 自動化學(xué)報, 2013, 39(6): 745-758. CAO Ying, MIAO Qiguang, LIU Jiachen, et al. Advance and Prospects of AdaBoost [J]. Acta Automatica Sinica, 2013, 39(6): 745-758.

[7] XU Zhijie, SUN Shiliang. An algorithm on multi-view AdaBoost [C]∥Proceedings of 17th International Conference on Neural Information Processing. Heidelberg, Germany: Springer, 2010: 355-362.

[8] XU Zhijie, SUN Shiliang. Multi-source transfer learning with multi-view AdaBoost [C]∥Proceedings of 19th International Conference on Neural Information Processing. Heidelberg, Germany: Springer, 2012: 332-339.

[9] 郝紅衛(wèi), 王志彬, 殷緒成. 分類器的動態(tài)選擇與循環(huán)集成方法 [J]. 自動化學(xué)報, 2011, 37(11): 1290-1295. HAO Hongwei, WANG Zhibin, YIN Xucheng. Dynamic selection and circulating combination for multiple classifier systems [J]. Acta Automatica Sinica, 2011, 37(11): 1290-1295.

[10]孫亮, 韓崇昭, 沈建京, 等. 集成特征選擇的廣義粗集方法與多分類器融合 [J]. 自動化學(xué)報, 2008, 34(3): 298-304. SUN Liang, HAN Chongzhao, SHEN Jianjing, et al. Generalized rough set method for ensemble feature selection and multiple classifier fusion [J]. Acta Automatica Sinica, 2008, 34(3): 298-304.

[11]馬超, 陳西宏, 徐宇亮, 等. 廣義領(lǐng)域粗集下的集成特征選擇及其選擇性集成算法 [J]. 西安交通大學(xué)學(xué)報, 2011, 45(6): 34-39. MA Chao, CHEN Xihong, XU Yuliang, et al. Ensemble feature selection based on generalized neighborhood rough model and its selective integration [J]. Journal of Xi’an Jiaotong University, 2011, 45(6): 34-39.

[12]GARCIA P N. Constructing ensembles of classifiers by means of weighted instance selection [J]. IEEE Transactions on Neural Networks, 2009, 20(2): 258-277.

[13]VAPNIK V. The nature of statistical learning theory [M]. New York: Springer-Verlag, 2000.

[14]OLVERA-LOPEZ J A, CARRASCO-OCHOA J A, MARTINEZ-TRINIDAD J, et al. A review of instance selection methods [J]. Artificial Intelligence Review, 2010, 34(2): 133-143.

[15]YANG Honghui, ZHOU Xin, WANG Yun, et al. A new adaptive immune clonal algorithm for underwater acoustic target sample selection [C]∥Proceedings of 2013 IEEE International Conference of IEEE Region 10. Piscataway, NJ, USA: IEEE, 2013: 1-4.

[16]楊宏暉, 戴健, 孫進才, 等. 用于水下目標識別的自適應(yīng)免疫特征選擇算法 [J]. 西安交通大學(xué)學(xué)報, 2011, 45(12): 28-32. YANG Honghui, DAI Jian, SUN Jincai, et al. A new adaption immune feature selection algorithm for underwater acoustic target classification [J]. Journal of Xi’an Jiaotong University, 2011, 45(12): 28-32.

[17]LIU Huan, YU Lei. Toward integrating feature selection algorithms for classification and clustering [J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(4): 491-502.

[18]VINH L T, THANG N D, LEE Y K. An improved maximum relevance and minimum redundancy feature selection algorithm based on normalized mutual information [C]∥Proceedings of 201010th Annual International Symposium on Applications and the Internet. Piscataway, NJ, USA: IEEE, 2010: 395-398.

[19]HETTICH S, BLAKE C, MERZ C. UCI repository of machine learning database[DB/OL]. (1998-07-11)[2014-04-03]. http:∥www.ics.uci.edu/mlearn/MLRepository.html.

(編輯 劉楊)

AnAdaBoostSupportVectorMachineEnsembleMethodwithIntegrationofInstanceSelectionandFeatureSelection

YANG Honghui,WANG Yun,SUN Jincai,DAI Jian,LI Ya’an

(School of Marine Science and Technology, Northwestern Polytechnical University, Xi’an 710072, China)

An AdaBoost support vector machine ensemble (IFSelect-SVME) method with integration of instance selection and feature selection is proposed to improve the classification accuracy of AdaBoost ensemble algorithm and to simplify the complexity of the classification system. The proposed algorithm selects instance subsets via the weighted immune clonal instance selection algorithm in each cycle of AdaBoost algorithm, and the feature subsets are obtained using the mutual information sequential forward feature selection algorithm. Then the individual SVM classifiers are trained by the resulting optimal feature instance subsets in each cycle, and combined via majority vote to generate the final decision system. Simulation results on 9 UCI datasets and comparisons with the AdaBoost SVME algorithm show that the IFSelect-SVME algorithm obtains better classification accuracy with the number of instances decreasing to 30.8%-80.0% and the number of features decreasing to 32.2%-81.5%. The proposed IFSelect-SVME algorithm simplifies the structure of ensemble model, shortens the classification time of test instances, and gives a classification system with better classification accuracy.

classifier ensemble; AdaBoost algorithm; support vector machine; instance selection; feature selection

2014-04-29。

楊宏暉(1971—),女,博士,副教授。

國家自然科學(xué)基金資助項目(51179157,60672136);水下測控技術(shù)重點實驗室基金資助項目(9140C260505120C26104)。

時間:2014-09-09

10.7652/xjtuxb201412010

TP391.4

:A

:0253-987X(2014)12-0063-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140909.0840.001.html