許劍，張洪偉

（成都信息工程學院，成都610225）

Adaboost算法分類器設計及其應用

許劍，張洪偉

（成都信息工程學院，成都610225）

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

弱分類器；強分類器；BP神經網絡；Adaboost算法

BP神經網絡在分類算法中有廣泛的應用，但是由于BP神經網絡本質上是梯度下降法，當遇到比較復雜的目標函數(shù)時，其學習速度和收斂速度會變得很慢，導致訓練失敗的可能性較大。而Adaboost能夠提升任意精度的弱分類器為強分類器，它的核心思想是通過對一個訓練集訓練得到多個分類結果，最后將它們集成起來。在BP神經網絡中引入Adaboost算法作為分類器，可以彌補BP神經網絡的缺點，能提高分類準確率和泛化率。

1 Adaboost算法概述

1.1 boosting算法

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

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

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

（2）將在前面學習過程中分錯的樣本加上其他新數(shù)據(jù)一起構成一個新的含N個數(shù)據(jù)的訓練樣本集，對這個訓練樣本集進行訓練學習，得到新的分類器；

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

（4）最后通過對全部得到的弱分類器進行加權投票表決得到強分類器，即某樣本被分為哪一類要通過全部弱分類器的加權投票表決。

boosting算法需要解決兩個主要問題∶

（1）怎樣調整訓練集里的樣本分布，從而使訓練集產生適合的弱分類器；

（2）怎么把訓練所得弱分類器集成得到效果更好的強分類器。

1.2 Adaboost算法

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

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

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

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

2 adaboost_bp神經網絡分類算法

2.1 算法思路

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

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

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

步驟1數(shù)據(jù)選擇和網絡初始化。

步驟2弱分類器分類。

訓練第t個弱分類器時，用訓練樣本g（t）訓練BP神經網絡，并且分類訓練樣本輸出，得到訓練樣本的分類誤差和et。

步驟3計算分類序列權重。

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

步驟4測試數(shù)據(jù)權重調整。

根據(jù)分類序列權重at調整下一輪訓練樣本的權重，其數(shù)學表達式為∶

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

將得到的T個弱分類器的權重at歸一化，則強分類函數(shù)分類結果H（x）為∶

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

3 實驗與結果分析

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

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

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

3.2 實驗結果與分析

3.2.1 Iris Dataset

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

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

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

實驗結果見表4。

4 結束語

針對BP神經網絡訓練時間較長以及可能訓練失敗，提出把BP神經網絡引入Adaboost算法改進分類算法。該算法將BP神經網絡作為弱分類器，經過反復訓練的弱分類器組合起來稱為一個強分類器。實驗結果表明，該算法比BP神經網絡能有更低的分類誤差以及較好的擴展性。

［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］.計算機科學'2003'30(3）:30-34'145.

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

［8］曹瑩'苗啟廣'劉家辰'等.AdaBoost算法研究進展與展望［J］.自動化學報'2013'39(6）:745-758.

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

［10］李睿'張九蕊'毛莉.基于AdaBoost的弱分類器選擇和整合算法［J］.蘭州理工大學學報'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-），男，四川渠縣人，碩士生，主要從事計算智能方面的研究，（E-mail）781084168@qq.com