??? 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年代隨著支持向量機(SVM)的提出和發展，決策樹遇到了極大的挑戰。1996年，Freund和Schapire等人提出了Adaboost算法，可以將多個弱分類器(比如Stump決策樹)組合起來形成一個更加強大的強分類器，其性能可以與支持向量機媲美，所以才會有Breiman上面那句話。

? (一) 算法：

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

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

?

? 1. 為第一個弱分類器的所有訓練樣例初始化權重，都設為1/N。

? 2. 迭代M次，亦即訓練M個弱分類器：

? (a) 訓練當前弱分類器，使得訓練樣例的加權誤差Jm最小。

? (b) 求得當前弱分類器的加權誤差率ε，如果ε>0.5，則當前分類器效果太差，算法終止，否則計算α=ln((1-ε)/ε)，α是一個大于1的數，用來增加被分錯類的訓練樣例的權重。

? (c) 對于所有被當前弱分類器分錯類的訓練樣例，增大其權重(乘以α)，以便在訓練下一個弱分類器時重視這些被分錯類的訓練樣例(真正實現時還應進行標準化，亦即使得所有權重的和為1)。

? 3. 最終得到的強分類器利用M個弱分類器的分類結果的加權和作為測試訓練樣例的分類結果。

? (二)Java實現

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

? 參考文獻：

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

? [2] Ethern Alpaydin 機器學習導論 15章 組合多學習器 p236

? [3] Boosting算法簡介 百度搜索研發部 官方博客

? [4] 統計學習那些事 數據挖掘研究院

? [5] Wiki:Decision Tree Learning

? [6] Wiki:AdaBoost

機器學習-AdaBoosting及其Java實現