Adaboost算法分類器設(shè)計(jì)及其應(yīng)用

許劍，張洪偉

（成都信息工程學(xué)院，成都610225）

Adaboost算法分類器設(shè)計(jì)及其應(yīng)用

許劍，張洪偉

（成都信息工程學(xué)院，成都610225）

Adaboost算法可以將分類效果一般的弱分類器提升為分類效果理想的強(qiáng)分類器，而且不需要預(yù)先知道弱分類器的錯(cuò)誤率上限，這樣就可以應(yīng)用很多分類效果不穩(wěn)定的算法來(lái)作為Adaboost算法的弱分類器。由于BP神經(jīng)網(wǎng)絡(luò)算法自身存在的局限性和對(duì)訓(xùn)練樣本進(jìn)行選擇的主觀性，其分類精度以及擴(kuò)展性有待提高。將Adaboost算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合，使用神經(jīng)網(wǎng)絡(luò)分類模型作為Adaboost算法的弱分類器。算法在matlab中實(shí)現(xiàn)，對(duì)2個(gè)UCI的分類實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明Adaboost能有效改善BP神經(jīng)網(wǎng)絡(luò)的不足，提高分類正確率和泛化率。

弱分類器；強(qiáng)分類器；BP神經(jīng)網(wǎng)絡(luò)；Adaboost算法

BP神經(jīng)網(wǎng)絡(luò)在分類算法中有廣泛的應(yīng)用，但是由于BP神經(jīng)網(wǎng)絡(luò)本質(zhì)上是梯度下降法，當(dāng)遇到比較復(fù)雜的目標(biāo)函數(shù)時(shí)，其學(xué)習(xí)速度和收斂速度會(huì)變得很慢，導(dǎo)致訓(xùn)練失敗的可能性較大。而Adaboost能夠提升任意精度的弱分類器為強(qiáng)分類器，它的核心思想是通過(guò)對(duì)一個(gè)訓(xùn)練集訓(xùn)練得到多個(gè)分類結(jié)果，最后將它們集成起來(lái)。在BP神經(jīng)網(wǎng)絡(luò)中引入Adaboost算法作為分類器，可以彌補(bǔ)BP神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)，能提高分類準(zhǔn)確率和泛化率。

1 Adaboost算法概述

1.1 boosting算法

PAC（probably approximately correct）是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)的早期學(xué)習(xí)算法。Kearns和Valiant提出，在Valiant的PAC模型中，一個(gè)弱學(xué)習(xí)算法可以被提升為一個(gè)具有任意精度的強(qiáng)學(xué)習(xí)［1］。令S為包含N個(gè)樣本點(diǎn)（x1，y1），…，（xn，yn）的樣本集，其中xn是按照某種固定但未知的分布D（x）隨機(jī)獨(dú)立抽取的。Yn=f（xn），f屬于某個(gè)已知的布爾函數(shù)集F。如果對(duì)于任意的D，任意的0?ε?1/2、0?δ?1/2，學(xué)習(xí)算法能生成一個(gè)滿足P［h（x）≠f（x）］＜=ε的概率大于1-δ，并且學(xué)習(xí)算法的運(yùn)行時(shí)間與滿足多項(xiàng)式關(guān)系，則稱為強(qiáng)學(xué)習(xí)算法［2］。類似的，若一個(gè)滿足P［h（x）≠f（x）］≤ε的概率大于1/2+δ（0?δ?1/2），只要求這個(gè)弱學(xué)習(xí)算法的正確率大于50%，也就是比隨機(jī)猜測(cè)稍好，則稱為弱學(xué)習(xí)算法［2］。1990年，Schapire使用了構(gòu)造方法來(lái)證明弱學(xué)習(xí)算法和強(qiáng)學(xué)習(xí)算法是等價(jià)的［3］，因?yàn)閺?qiáng)學(xué)習(xí)算法在通常情況下很難獲得，只要能夠找到比隨機(jī)猜測(cè)稍好的弱學(xué)習(xí)算法，就可以把它提升為強(qiáng)學(xué)習(xí)算法。

boosting［4］算法由Schapire和Freund在1990年提出，是最早提出的集成學(xué)習(xí)算法，是一種有效提高分類學(xué)習(xí)系統(tǒng)分類能力的算法。boosting算法操縱訓(xùn)練樣本來(lái)產(chǎn)生多個(gè)分類假設(shè)，從而建立通過(guò)加權(quán)投票結(jié)合的分類器集合，其過(guò)程如下∶

（1）首先對(duì)含有N條數(shù)據(jù)的訓(xùn)練樣本進(jìn)行學(xué)習(xí)后得到第一個(gè)弱分類器；

（2）將在前面學(xué)習(xí)過(guò)程中分錯(cuò)的樣本加上其他新數(shù)據(jù)一起構(gòu)成一個(gè)新的含N個(gè)數(shù)據(jù)的訓(xùn)練樣本集，對(duì)這個(gè)訓(xùn)練樣本集進(jìn)行訓(xùn)練學(xué)習(xí)，得到新的分類器；

（3）把在步驟（1）和（2）中都分錯(cuò)了的樣本加上其他新數(shù)據(jù)構(gòu)成另一個(gè)新的包含N個(gè)數(shù)據(jù)的訓(xùn)練樣本集，對(duì)這個(gè)樣本集進(jìn)行訓(xùn)練學(xué)習(xí)得到新的分類器；

（4）最后通過(guò)對(duì)全部得到的弱分類器進(jìn)行加權(quán)投票表決得到強(qiáng)分類器，即某樣本被分為哪一類要通過(guò)全部弱分類器的加權(quán)投票表決。

boosting算法需要解決兩個(gè)主要問(wèn)題∶

（1）怎樣調(diào)整訓(xùn)練集里的樣本分布，從而使訓(xùn)練集產(chǎn)生適合的弱分類器；

（2）怎么把訓(xùn)練所得弱分類器集成得到效果更好的強(qiáng)分類器。

1.2 Adaboost算法

Adaboost算法是Schapire和Freund在1995年提出的，其關(guān)鍵思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練多個(gè)的弱分類器，最后將這些弱分類器集成起來(lái)構(gòu)成最終的強(qiáng)分類器［5］。Adaboost算法主要是根據(jù)每次訓(xùn)練過(guò)程中樣本集內(nèi)每個(gè)樣本的分類結(jié)果是否正確來(lái)改變數(shù)據(jù)樣本分布，即是修改樣本的權(quán)值。修改過(guò)權(quán)值的新數(shù)據(jù)集再次進(jìn)行訓(xùn)練得到新的弱分類器，最后通過(guò)某種策略，常用的如投票加權(quán)方式，將得到的弱分類器集成起來(lái)生成最后的決策分類器。Adaboost分類算法可以過(guò)濾掉非關(guān)鍵的數(shù)據(jù)特征，以減小數(shù)據(jù)維度。弱學(xué)習(xí)過(guò)程得到的弱假設(shè)影響最后的強(qiáng)假設(shè)的正確率，它有效地解決了早期boost算法在實(shí)際運(yùn)用中的困難，因此更能全面地挖掘?qū)W習(xí)算法的能力，因此叫adaptive boosting，簡(jiǎn)稱Adaboost。

Adaboost算法是Freund和Schapire根據(jù)已經(jīng)存在的在線分配算法提出的。跟boosting算法最大的不同的是∶Adaboost算法不需要預(yù)先知道弱學(xué)習(xí)算法的誤差精度，并且最后得到的強(qiáng)分類器的分類精度依賴于所有弱分類器的分類精度影響得到的強(qiáng)分類器的分類精度，這樣就可以去尋找要求更低的分類算法。

Adaboost算法初始狀態(tài)下每個(gè)樣本的權(quán)重是相同的，對(duì)此樣本分布訓(xùn)練得到一個(gè)弱分類器。對(duì)于被分錯(cuò)的樣本，增加權(quán)重；相反情況下，降低權(quán)重。這樣，被分錯(cuò)的樣本就更能出現(xiàn)在新的樣本分布中，這些分錯(cuò)的樣本被著重訓(xùn)練。在經(jīng)過(guò)N次訓(xùn)練后，我們得到了N個(gè)弱分類器，最后把這N個(gè)弱分類器按一定的權(quán)重集成起來(lái)得到最終想要的強(qiáng)分類器［6］。

Adaboost算法不斷加入新的弱分類器以達(dá)到足夠小的誤差率。在Adaboost算法中，每個(gè)訓(xùn)練樣本都被賦予一個(gè)權(quán)重系數(shù)，來(lái)表明它被下一次選入一個(gè)訓(xùn)練過(guò)程的概率。當(dāng)某個(gè)樣本點(diǎn)在當(dāng)前訓(xùn)練過(guò)程中被正確地分類，那么應(yīng)該降低它的權(quán)重以降低選擇該樣本進(jìn)入下次訓(xùn)練過(guò)程的幾率；相反，如果某個(gè)樣本在當(dāng)前訓(xùn)練工程中被錯(cuò)誤的分類，那么應(yīng)該增加它的權(quán)重以使得它在下個(gè)弱分類器構(gòu)造時(shí)更能被選中。這樣Adaboost就能更關(guān)注那些分類困難的樣本，提高最后算法分類結(jié)果的正確率［7］。

2 adaboost_bp神經(jīng)網(wǎng)絡(luò)分類算法

2.1 算法思路

Adaboost算法是一種迭代算法。目前，對(duì)Adaboost算法的研究以及應(yīng)用大多集中于分類問(wèn)題，同時(shí)近年也出現(xiàn)了一些在回歸問(wèn)題上的應(yīng)用［8］。Adaboost算法能夠提高任意給定弱分類器的分類精度，因此，本文針對(duì)BP神經(jīng)網(wǎng)絡(luò)自身的局限性和訓(xùn)練樣本選擇的主觀因素，為提高其分類精度，將Adaboost算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合，建立了adaboost_bp神經(jīng)網(wǎng)絡(luò)分類模型［9］。模型采用BP神經(jīng)網(wǎng)絡(luò)作為弱分類器，根據(jù)每次訓(xùn)練樣本分類的優(yōu)劣，減少或增加其對(duì)應(yīng)的權(quán)重，并使用改變權(quán)重后的樣本重新對(duì)弱分類器進(jìn)行訓(xùn)練，最后將這些弱分類器的訓(xùn)練結(jié)果進(jìn)行集成，得到最終的輸出。

2.2 算法實(shí)現(xiàn)步驟

算法基本步驟如下［10］∶

步驟1數(shù)據(jù)選擇和網(wǎng)絡(luò)初始化。

步驟2弱分類器分類。

訓(xùn)練第t個(gè)弱分類器時(shí)，用訓(xùn)練樣本g（t）訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)，并且分類訓(xùn)練樣本輸出，得到訓(xùn)練樣本的分類誤差和et。

步驟3計(jì)算分類序列權(quán)重。

根據(jù)訓(xùn)練樣本g（t）的分類誤差和et計(jì)算權(quán)重at∶

步驟4測(cè)試數(shù)據(jù)權(quán)重調(diào)整。

根據(jù)分類序列權(quán)重at調(diào)整下一輪訓(xùn)練樣本的權(quán)重，其數(shù)學(xué)表達(dá)式為∶

步驟5強(qiáng)分類函數(shù)。

將得到的T個(gè)弱分類器的權(quán)重at歸一化，則強(qiáng)分類函數(shù)分類結(jié)果H（x）為∶

式中，h（x）為T個(gè)弱分類器得到的分類樣本的分類值。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證本文提出算法的有效性和實(shí)用性，將用UCI Machine Learning Repository中的Iris Dataset和Breast Cancer Wisconsin Dataset數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn)，并對(duì)數(shù)據(jù)都采用歸一化處理，數(shù)據(jù)歸一化把數(shù)據(jù)都轉(zhuǎn)化為［0，1］之間的數(shù)，以便消除各維數(shù)據(jù)間的數(shù)量級(jí)差別，避免數(shù)據(jù)各維度之間由于數(shù)量級(jí)差別過(guò)大而造成誤差過(guò)大。常用的歸一化方法為∶

式中xmax為數(shù)據(jù)集每一維的最大值，xmin為數(shù)據(jù)集每一維的最小值。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 Iris Dataset

鳶尾花數(shù)據(jù)是模式識(shí)別文獻(xiàn)中最著名的數(shù)據(jù)集（表1），該數(shù)據(jù)集包含3個(gè)類別的鳶尾花數(shù)據(jù)，每個(gè)類別50條數(shù)據(jù)，總共有150條數(shù)據(jù)。一個(gè)類與其他兩個(gè)類是線性可分的，而后兩個(gè)不是線性可分的，所以通常用來(lái)檢測(cè)分類器的效果。該數(shù)據(jù)集包含4個(gè)數(shù)值屬性和1個(gè)類別標(biāo)簽，實(shí)驗(yàn)結(jié)果見(jiàn)表2。

3.2.2 Breast CancerWisconsin Dataset威斯康辛乳腺癌診斷數(shù)據(jù)是另外一個(gè)著名的數(shù)據(jù)集（表3）。該數(shù)據(jù)集包含2個(gè)類別（良性、惡性）的乳腺癌診斷數(shù)據(jù)，總共有699條數(shù)據(jù)，其中良性458條，惡性

241條。該數(shù)據(jù)集包含10個(gè)數(shù)值屬性（其中第一個(gè)數(shù)據(jù)為樣本編碼號(hào)在數(shù)據(jù)集使用中省略）和1個(gè)類別標(biāo)簽。

實(shí)驗(yàn)結(jié)果見(jiàn)表4。

4 結(jié)束語(yǔ)

針對(duì)BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練時(shí)間較長(zhǎng)以及可能訓(xùn)練失敗，提出把BP神經(jīng)網(wǎng)絡(luò)引入Adaboost算法改進(jìn)分類算法。該算法將BP神經(jīng)網(wǎng)絡(luò)作為弱分類器，經(jīng)過(guò)反復(fù)訓(xùn)練的弱分類器組合起來(lái)稱為一個(gè)強(qiáng)分類器。實(shí)驗(yàn)結(jié)果表明，該算法比BP神經(jīng)網(wǎng)絡(luò)能有更低的分類誤差以及較好的擴(kuò)展性。

［1］Valiant L G.A theory of learnable［J］.Communications of the ACM'1984'27(11）:1134-1142.

［2］Kearns M J'Valiant L G.Cryptographic limitations onlearning Boolean formulae and finite automata［J］.Journal of the ACM(JACM）'1994'41(1）:67-95.

［3］Freund Y.Boosting a weak learning algorithm by majority［J］.Information and Computation'1995'121(2）:256-285.

［4］Schapire R E.A brief introduction to boosting［C］//Proceedings of the 16th international joint conference on Artificial intelligence'Stockholm'Sweden'July 31-August 6'1999:1401-1406.

［5］Freund Y'Schapire R E.Experimentswith a new boosting algorithm［C］//Proceedings of the 13th International Conference on Machine Learning'Bari'Italy'July 3-6'1996: 148-156.

［6］涂承勝'刁力力'魯明羽'等.Boosting家族AdaBoost系列代表算法［J］.計(jì)算機(jī)科學(xué)'2003'30(3）:30-34'145.

［7］付忠良.關(guān)于AdaBoost有效性的分析［J］.計(jì)算機(jī)研究與發(fā)展'2008'45(10）:1747-1755.

［8］曹瑩'苗啟廣'劉家辰'等.AdaBoost算法研究進(jìn)展與展望［J］.自動(dòng)化學(xué)報(bào)'2013'39(6）:745-758.

［9］董元元'陳基漓'唐小俠.基于BP_Adaboost的文本分類研究［J］.網(wǎng)絡(luò)安全技術(shù)與應(yīng)用'2012(3）:42-43.

［10］李睿'張九蕊'毛莉.基于AdaBoost的弱分類器選擇和整合算法［J］.蘭州理工大學(xué)學(xué)報(bào)'2012'38(2）: 87-90.

Design and Application of Adaboost Algorithm Classifier

XU Jian，ZHANG Hongwei
（Chengdu University of Information Technology，Chengdu 610225，China）

Adaboost algorithm can promote a weak classifier to a strong classifier without knowing the error rate upper limit of the weak classifier in advance，so a lot of classifierswhich are not so stable can be used asweak classifiers in Adaboost algorithm.Because of the limitation and subjectivity in training samples selection of the BP neural network algorithm，its classification accuracy and scalability need to be improved.So the Adaboost algorithm is combined with BP neural network，in which the neural network classificationmodel is used as a weak classifier.Algorithm is realized inmatlab，and two UCIdata sets is used to do the experiment.The results show that Adaboost can effectively overcome the shortcomings of BP neural network，improve the classification accuracy and the rate of generalization.

weak classifier；strong classifier；BP Neural Network；Adaboost algorithm

TP301.6

A

1673-1549（2014）01-0028-04

10.11863/j.suse.2014.01.08

2013-09-24

許劍（1989-），男，四川渠縣人，碩士生，主要從事計(jì)算智能方面的研究，（E-mail）781084168@qq.com