高敬陽,趙 彥

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

基于樣本抽樣和權(quán)重調(diào)整的SWA-Adaboost算法

高敬陽,趙 彥

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

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

樣本預(yù)處理;均衡抽樣;權(quán)重調(diào)整;泛化性能;類中心最小距離;樣本區(qū)分度

1 概述

Adaboost算法[1]作為最受歡迎的分類集成算法在機(jī)器學(xué)習(xí)領(lǐng)域得到了極大的關(guān)注[2-3]。該算法是boosting算法中應(yīng)用最廣泛的算法[4],將若干個(gè)弱分類器通過線性集成而得到一個(gè)強(qiáng)分類器[5]。Adaboost算法已經(jīng)通過數(shù)學(xué)證明得到:只要弱分類器的數(shù)目趨于無窮時(shí),Adaboost算法的分類誤差將趨于0[6]。

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

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

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

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

分類器是根據(jù)不同樣本屬性的區(qū)分度來對樣本進(jìn)行分類的,屬性的區(qū)分度越明顯則分類效果越好。因此,可以通過增加樣本間的區(qū)分度來提高分類器的分類準(zhǔn)確率。本文通過對所有樣本增加一個(gè)屬性值來增加樣本的區(qū)分度,提高分類的效果。原始Adaboost算法在對分類器進(jìn)行訓(xùn)練時(shí),所有類均應(yīng)當(dāng)?shù)玫匠浞值挠?xùn)練,但由于抽樣不均導(dǎo)致分類器對某些類的訓(xùn)練不足,從而降低了樣本的分類效果。為此,本文提出均衡抽樣的方法。此外,針對錯分樣本權(quán)重增長過快,給出新的權(quán)重調(diào)整策略,旨在降低錯分樣本的權(quán)重增長速度。就以上缺陷對原始Adaboost算法進(jìn)行改進(jìn),并提出新的算法SWA-Adaboost。

2 算法改進(jìn)分析

2.1 樣本屬性的增加

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

(1)求類中心向量

假設(shè)第i類Ci中的樣本數(shù)量為T,有:

求出該類樣本中心向量:

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

(2)求dmin

2.2 樣本訓(xùn)練不均衡分析

2.3 錯分樣本權(quán)重分析

Adaboost算法的樣本權(quán)值調(diào)整策略是:

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

其中,Zt為歸一化因子。

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

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

由此可知,當(dāng)某個(gè)樣本被錯分N次時(shí),每次的權(quán)重增長幅度Δw小于原始算法的權(quán)重增長幅度。這樣就達(dá)到了減緩錯分樣本權(quán)重增長的速度的目的。

3 SWA-Adaboost算法

SWA-Adaboost算法步驟如下:

(1)對訓(xùn)練樣本集進(jìn)行預(yù)處理。

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

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

(3)初始化樣本權(quán)值和錯分計(jì)數(shù)量:

(4)循環(huán)t=1to T

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

2)弱學(xué)習(xí)算法訓(xùn)練得到弱分類器:

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

4)計(jì)算個(gè)體網(wǎng)絡(luò)的權(quán)值:

5)調(diào)整樣本權(quán)值:

其中,Zt為歸一化因子。

(5)集成分類器:

4 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證SWA-Adaboost算法在泛化性能上優(yōu)于原始Adaboost算法,實(shí)驗(yàn)選用50個(gè)BP網(wǎng)絡(luò)作為弱分類器進(jìn)行集成,并采用UCI數(shù)據(jù)集中的sonar, glass,diabetes,breast-cancer-wisconsin,ablone,wine數(shù)據(jù)。2種算法的泛化誤差如表1所示,性能對比如圖1所示。

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

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

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

圖1 改進(jìn)算法與原始算法泛化性能比較

5 結(jié)束語

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

[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算法的推廣——一組集成學(xué)習(xí)算法[J].四川大學(xué)學(xué)報(bào),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] 饒 雄,高振宇.多分類器聯(lián)合監(jiān)督分類方法研究[J].四川測繪,2006,29(1):15-17.

[10] 林舒楊,李翠華,江 弋,等.不平衡數(shù)據(jù)的降采樣方法研究[J].計(jì)算機(jī)研究與發(fā)展,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及其在判別分析中的應(yīng)用[J].中國衛(wèi)生統(tǒng)計(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

國家自然科學(xué)基金資助項(xiàng)目(51275030)。

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

2013-09-02

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