基于樣本抽樣和權重調整的SWA-Adaboost算法

高敬陽,趙 彥

(北京化工大學信息科學與技術學院,北京100029)

基于樣本抽樣和權重調整的SWA-Adaboost算法

高敬陽,趙 彥

(北京化工大學信息科學與技術學院,北京100029)

根據分類算法是依據樣本區分度進行分類的原理,提出增加樣本屬性以提高樣本區分度的方法,在樣本預處理階段對所有樣本增加一個屬性值dmin以加強樣本之間的區分度。針對原始Adaboost算法在抽樣階段由于抽樣不均而導致對某些類訓練不足的問題,采用均衡抽樣方法,保證在抽樣階段所抽取的不同類樣本的數量比例不變。針對原始算法樣本權重增長過快的問題,給出新的權重調整策略,引入樣本錯分計數量count(n),有效地抑制樣本權重增長速度。給出一種改進的Adaboost算法,即SWA-Adaboost算法,并采用美國加州大學機器學習UCI數據庫中6種數據集的數據對改進算法與原始算法進行實驗對比,結果證明,改進算法SWA-Adaboost在泛化性能上優于Adaboost算法,泛化誤差平均降低9.54%。

樣本預處理;均衡抽樣;權重調整;泛化性能;類中心最小距離;樣本區分度

1 概述

Adaboost算法[1]作為最受歡迎的分類集成算法在機器學習領域得到了極大的關注[2-3]。該算法是boosting算法中應用最廣泛的算法[4],將若干個弱分類器通過線性集成而得到一個強分類器[5]。Adaboost算法已經通過數學證明得到:只要弱分類器的數目趨于無窮時,Adaboost算法的分類誤差將趨于0[6]。

雖然Adaboost算法已經在文本分類、人臉檢測、信息安全等很多領域得到了廣泛應用[7],但該算法仍然存在以下缺陷:

(1)樣本屬性部分的區分度不明顯而影響樣本分類效果。

(2)訓練過程中由于對樣本抽樣不均而使分類器對某些類訓練不充分。

(3)訓練過程中錯分樣本的權重增長過快[8]。

分類器是根據不同樣本屬性的區分度來對樣本進行分類的,屬性的區分度越明顯則分類效果越好。因此,可以通過增加樣本間的區分度來提高分類器的分類準確率。本文通過對所有樣本增加一個屬性值來增加樣本的區分度,提高分類的效果。原始Adaboost算法在對分類器進行訓練時,所有類均應當得到充分的訓練,但由于抽樣不均導致分類器對某些類的訓練不足,從而降低了樣本的分類效果。為此,本文提出均衡抽樣的方法。此外,針對錯分樣本權重增長過快,給出新的權重調整策略,旨在降低錯分樣本的權重增長速度。就以上缺陷對原始Adaboost算法進行改進,并提出新的算法SWA-Adaboost。

2 算法改進分析

2.1 樣本屬性的增加

每個樣本均可以表示成由n個屬性位與1個分類位組成,例如樣本 S={P1,P2,…,Pn,Ci},P1, P2,…,Pn為屬性,Ci表示樣本所屬類別。分類器是依賴于樣本屬性的不同來區分不同樣本,故屬性的區分度直接影響到分類效果。本文將訓練樣本和測試樣本均做了預處理,增加了一個屬性值以提高樣本之間的區分度,屬性值為該樣本到所有類中心的歐氏距離的最小值dmin[9]。若某樣本屬于Ci類,那么該樣本到Ci類中心的距離較它到其他類距離更小,因此,此屬性值具有實際意義。預處理方法如下:

(1)求類中心向量

假設第i類Ci中的樣本數量為T,有:

求出該類樣本中心向量:

以此類推得到 K類樣本的中心向量:SC1, SC2,…,SCK。

(2)求dmin

2.2 樣本訓練不均衡分析

2.3 錯分樣本權重分析

Adaboost算法的樣本權值調整策略是:

其中,Zt為歸一化因子[11]。此權值調整策略存在一個問題:錯分樣本的權重增長速度過快[12]。為了緩解這種情況,改進算法對樣本權值調整策略做了如下改進:

其中,Zt為歸一化因子。

該策略中新引入了樣本錯分計數量:count(i), count(i)初始化為1。其表示第i個樣本在前t個弱分類器中被錯分的總次數。這種改進方法可以使錯分樣本的權值增長速度減緩。

(3)假設第i個樣本被連續錯分若干次,則count(i)=1,2,…,N。

由此可知,當某個樣本被錯分N次時,每次的權重增長幅度Δw小于原始算法的權重增長幅度。這樣就達到了減緩錯分樣本權重增長的速度的目的。

3 SWA-Adaboost算法

SWA-Adaboost算法步驟如下:

(1)對訓練樣本集進行預處理。

(2)輸入預處理后得到的新的訓練樣本集:

其中,xi∈X,yi∈Y={1,-1}。

(3)初始化樣本權值和錯分計數量:

(4)循環t=1to T

1)按均衡抽樣法抽取樣本;

2)弱學習算法訓練得到弱分類器:

3)計算ht(x)的錯誤率:

4)計算個體網絡的權值:

5)調整樣本權值:

其中,Zt為歸一化因子。

(5)集成分類器:

4 實驗及結果分析

為了驗證SWA-Adaboost算法在泛化性能上優于原始Adaboost算法,實驗選用50個BP網絡作為弱分類器進行集成,并采用UCI數據集中的sonar, glass,diabetes,breast-cancer-wisconsin,ablone,wine數據。2種算法的泛化誤差如表1所示,性能對比如圖1所示。

如表1所示,該表呈現出隨著個體網絡數的增加泛化誤差的變化趨勢(ADO表示原始Adaboost算法,SWA表示SWA-Adaboost算法)。由表1數據可以看出:改進算法SWA-Adaboost在數據集sonar,glass,diabetes,breast-cancer-wisconsin 和ablone上的集成泛化誤差明顯小于原始 Adaboost算法的集成泛化誤差,只有wine數據集的SWAAdaboost算法的泛化誤差較大。因此可得結論: SWA-Adaboost算法的泛化性能優于原始Adaboost算法的泛化性能。

由圖1(a)～圖1(e)可以看出,原始算法與改進算法在網絡數較少時(少于5個)泛化誤差均較大,隨著個體網絡數目的增加大致在10個之后,泛化誤差雖有小幅波動但基本趨于平穩。圖中顯示,改進算法的泛化性能明顯優于原始算法。只有圖1(f)wine數據集的改進算法泛化性能不及原始算法。

表1 2種算法的集成泛化誤差 %

圖1 改進算法與原始算法泛化性能比較

5 結束語

本文對原始Adaboost算法在樣本分析階段和抽樣階段以及樣本權重調整階段存在的缺陷進行分析,從這3個方面對原始算法進行了改進,提出了樣本屬性擴充、均衡抽樣、新權重調整策略的方案,并給出了SWA-Adaboost算法。通過實驗證明,改進算法在泛化性能上優于原始Adaboost算法。但改進算法對樣本進行了預處理操作,故預處理階段所需時間較長,從而影響算法整體的時間效率。因此,今后的研究重點應放在如何在不降低樣本預處理準確率的前提下,縮短處理時間以提高算法整體的時間效率,使之成為時間效率與泛化性能俱佳的分類算法。

[1] Liu Meizhu,Vemuri B C.Rboost:Riemannian Distance Based Regularized Boosting[C]//Proc.of IEEE International Symposium on Biomedical Imaging.[S.l.]: IEEE Press,2011:1831-1834.

[2] Seyedhosseini M,PaivaA R C,Tasdizen T.Fast Adaboost Training Using Weighted Novelty Selection [C]//Proc.of International Joint Conference on Neural Network.[S.l.]:IEEE Press,2011:1245-1250.

[3] Shen Chunhua,Li Hanxi.On the Dual Formulation of Boosting Algorithms[J].IEEE Transactions on Pattern Analysis and Machine Intellgence,2010,32(12): 2216-2231.

[4] Lev R.Boosting on a Budget:Sampling for Featureefficient Prediction[C]//Proc.of the 28th International Conferenceon MachineLearning.Bellevue,USA: [s.n.],2011.

[5] An T K,Kim M H.A New Diverse Adaboost Classifier [C]//Proc.of International Conference on Artificial Intelligence and Computational Intelligence.[S.l.]: IEEE Press,2010:359-363.

[6] Schapire R.The Strength of Weak Learn Ability[J]. Machine Learning,1990,5(2):197-227.

[7] 付忠良,趙向輝,苗 青,等.Adaboost算法的推廣——一組集成學習算法[J].四川大學學報,2010, 42(6):91-98.

[8] Gao Yunlong,Ji Guoli,Yang Zijiang,et al.A Dynamic Adaboost Algorithm with Adaptive Changes of Loss Funcion[J].IEEE Transactions on Systems,Man,and Cybernetics,2012,42(6):1828-1841.

[9] 饒 雄,高振宇.多分類器聯合監督分類方法研究[J].四川測繪,2006,29(1):15-17.

[10] 林舒楊,李翠華,江 弋,等.不平衡數據的降采樣方法研究[J].計算機研究與發展,2011,48(sl):47-53.

[11] Chen Xuefang,Xing Hongjie,Wang Xizhao.A Modified Adaboost Method for One-class SVM and Its Application to Novelty Detection[C]//Proc.of IEEE International Conference on Systems,Man,and Cybernetics.[S.l.]: IEEE Press,2011:3506-3511.

[12] 富春楓,荀鵬程,趙 楊,等.logitboost及其在判別分析中的應用[J].中國衛生統計,2006,23(2):98-100.

編輯 顧逸斐

SWA-Adaboost Algorithm Based on Sampling and Weight Adjustment

GAO Jing-yang,ZHAO Yan
(College of Information Science and Technology,Beijing University of Chemical Technology,Beijing 100029,China)

Because the classification algorithm based on the differences among samples,a new method is proposed which adds a new property value dmininto each sample in order to increase the differences.Besides,according to the situation that samples belonging to different classes are sampled unevenly in the sampling phase,a new method called even sampling is proposed to keep the proportion of difference classes invariant.For the purpose of inhibition of the increment speed of misclassification samples,a new method is proposed which brings in a variable count(n)to record the times of misclassification.In the word,an improved algorithm called Sampling equilibrium&Weight adjustment&Add attribute Adaboost(SWA-Adaboost)is proposed.Using the 6 datasets belonging to machine learning database of University of California in USA,the paper runs experiments to compare the original Adaboost with SWA-Adaboost. Experimental results show that SWA-Adaboost has better generalization performance than the original Adaboost and the average decrease of generalization error is 9.54%.

sample preprocessing;even sampling;weight adjustment;generalization performance;minimum distance of class center;different degree of sample

1000-3428(2014)09-0248-04

A

TP18

10.3969/j.issn.1000-3428.2014.09.050

國家自然科學基金資助項目(51275030)。

高敬陽(1966-),女,副教授、博士,主研方向:人工智能,模式識別;趙 彥,碩士研究生。

2013-09-02

2013-10-19E-mail:gaojy@mail.buct.edu.cn