??? Adaboost with trees is the best off-the-shelf classifier in the world. ?? -Breiman 1996

??? 決策樹算法起源于1984年Breiman,Friedman等人提出的CART，后來又有人(Quinlan等)提出ID3，C4.5，C5.0，CHAID等算法，但是90年代隨著支持向量機(jī)(SVM)的提出和發(fā)展，決策樹遇到了極大的挑戰(zhàn)。1996年，F(xiàn)reund和Schapire等人提出了Adaboost算法，可以將多個(gè)弱分類器(比如Stump決策樹)組合起來形成一個(gè)更加強(qiáng)大的強(qiáng)分類器，其性能可以與支持向量機(jī)媲美，所以才會(huì)有Breiman上面那句話。

? (一) 算法：

? Adaboost算法的思想起源于80年代Valiant提出的PAC理論(Valiant因此獲得2010年圖靈獎(jiǎng))，1996年由Freund和Schapire提出該算法(二人因此獲得2003年的 Godel Price ，是計(jì)算機(jī)理論界的最高獎(jiǎng))，其大體思想是，訓(xùn)練多個(gè) 弱分類器 (Weak Classifier，所謂弱分類器是指分類效果僅比隨機(jī)分類器效果好就可以，亦即分類錯(cuò)誤率要小于0.5，典型的弱分類器如 Stump ，亦即只有一個(gè)決策節(jié)點(diǎn)的決策樹)，每個(gè)弱分類器都會(huì)更加關(guān)注上個(gè)弱分類器分錯(cuò)類的訓(xùn)練樣例，最終的分類器由所有的這些弱分類器加權(quán)組成，亦即其分類結(jié)果為多個(gè)弱分類器的分類結(jié)果的加權(quán)和。下面是詳細(xì)介紹：

? Adaboost算法會(huì)訓(xùn)練M個(gè)弱分類器，每個(gè)分類器都會(huì)給所有的訓(xùn)練樣例賦予權(quán)重，第一個(gè)分類器所有訓(xùn)練樣例的權(quán)重都是1/N(N為訓(xùn)練樣例的個(gè)數(shù))，后面每個(gè)弱分類器都會(huì)提高前面的弱分類器分錯(cuò)類的訓(xùn)練樣例的權(quán)重，以便使得這些訓(xùn)練樣例盡量不會(huì)再分錯(cuò)。在此，我們僅討論最簡(jiǎn)單的二分類，亦即分類結(jié)果為{+1，-1}：

?

? 1. 為第一個(gè)弱分類器的所有訓(xùn)練樣例初始化權(quán)重，都設(shè)為1/N。

? 2. 迭代M次，亦即訓(xùn)練M個(gè)弱分類器：

? (a) 訓(xùn)練當(dāng)前弱分類器，使得訓(xùn)練樣例的加權(quán)誤差Jm最小。

? (b) 求得當(dāng)前弱分類器的加權(quán)誤差率ε，如果ε>0.5，則當(dāng)前分類器效果太差，算法終止，否則計(jì)算α=ln((1-ε)/ε)，α是一個(gè)大于1的數(shù)，用來增加被分錯(cuò)類的訓(xùn)練樣例的權(quán)重。

? (c) 對(duì)于所有被當(dāng)前弱分類器分錯(cuò)類的訓(xùn)練樣例，增大其權(quán)重(乘以α)，以便在訓(xùn)練下一個(gè)弱分類器時(shí)重視這些被分錯(cuò)類的訓(xùn)練樣例(真正實(shí)現(xiàn)時(shí)還應(yīng)進(jìn)行標(biāo)準(zhǔn)化，亦即使得所有權(quán)重的和為1)。

? 3. 最終得到的強(qiáng)分類器利用M個(gè)弱分類器的分類結(jié)果的加權(quán)和作為測(cè)試訓(xùn)練樣例的分類結(jié)果。

? (二)Java實(shí)現(xiàn)

? 為了充分理解Adaboost算法，我寫了一個(gè)簡(jiǎn)單的Java程序，訓(xùn)練樣例是二維空間上的N個(gè)點(diǎn)，用到的弱分類器是最簡(jiǎn)單的Stump，亦即樹樁。當(dāng)訓(xùn)練數(shù)據(jù)是隨機(jī)生成的時(shí)候，迭代10次后得到的分類器的準(zhǔn)確率會(huì)達(dá)到75%-90%。當(dāng)訓(xùn)練數(shù)據(jù)是形如下所示的分布時(shí)(但是我的數(shù)據(jù)集只有20個(gè)點(diǎn))，準(zhǔn)確率可以達(dá)到100%。

? 參考文獻(xiàn)：

? [1] Christopher M.Bishop Pattern Recognization and Machine Learnin ( PRML )， Chapter 14 Combining Models, p657

? [2] Ethern Alpaydin 機(jī)器學(xué)習(xí)導(dǎo)論 15章 組合多學(xué)習(xí)器 p236

? [3] Boosting算法簡(jiǎn)介 百度搜索研發(fā)部 官方博客

? [4] 統(tǒng)計(jì)學(xué)習(xí)那些事 數(shù)據(jù)挖掘研究院

? [5] Wiki:Decision Tree Learning

? [6] Wiki:AdaBoost

機(jī)器學(xué)習(xí)-AdaBoosting及其Java實(shí)現(xiàn)