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

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

(西北工業大學航海學院, 710072, 西安)

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

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

(西北工業大學航海學院, 710072, 西安)

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

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

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

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

1 AdaBoost算法

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

2 IFSelect-SVME算法

2.1 IFSelect-SVME算法的原理

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

圖1 IFSelect-SVME原理圖

2.2 加權免疫克隆樣本選擇算法

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

加權免疫克隆樣本選擇算法的步驟如下:

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

Step2加權親和度計算。計算分為以下2個步驟。

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

Gj(k)=1-Ej(k)

(1)

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

(2)

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

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

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

(3)

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

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

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

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

Step4判斷。若到達終止條件(終止條件通常為設定的循環次數),則輸出最優解;否則,轉至Step2。

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

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

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

(4)

式中:H(L)是類別L的熵;H(L|f)是在特征f條件下類別L的熵。互信息值越大,則表示特征與類別的相關程度越強,特征包含的分類信息越多,特征的分類性能也就越強。

2.4 生成分類系統

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

3 實 驗

3.1 實驗數據

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

表1 實驗數據

3.2 分類實驗

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

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

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

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

Vi=ui/Z

(5)

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

(a)wine (b)zoo

(c)wdbc (d)sonar

(e)parkinsons (f)ionospheres

(g)Indian-L (h)glass

(i)climate

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

(a)wine (b)zoo

(c)wdbc (d)sonar

(e)parkinsons (f)ionosphere

(g)Indian-L (h)glass

(i)climate

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

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

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

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

4 結 論

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

[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]. 系統工程與電子技術. 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]. 自動化學報, 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] 郝紅衛, 王志彬, 殷緒成. 分類器的動態選擇與循環集成方法 [J]. 自動化學報, 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]. 自動化學報, 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]馬超, 陳西宏, 徐宇亮, 等. 廣義領域粗集下的集成特征選擇及其選擇性集成算法 [J]. 西安交通大學學報, 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]楊宏暉, 戴健, 孫進才, 等. 用于水下目標識別的自適應免疫特征選擇算法 [J]. 西安交通大學學報, 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—),女,博士,副教授。

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

時間:2014-09-09

10.7652/xjtuxb201412010

TP391.4

:A

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

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140909.0840.001.html