出差結(jié)束，繼續(xù)好好學習機器學習基礎算法，今天了解提升方法(Boosting)，主要側(cè)重于AdaBoost算法，同樣理論知識來自Peter Harrington的《機器學習實戰(zhàn)》和李航的《統(tǒng)計學習方法》，非常感謝這些優(yōu)秀人物和優(yōu)秀書籍，正文開始啦
提升算法(Boosting)
考慮前幾篇提到的分類算法，各有利弊，如果可以有效地將這些分類器結(jié)合起來，各取所長，應該也是不錯的選擇。提升算法正是基于這樣的思想，但是它不是簡單、均等的將不同分類器的結(jié)果相加，而是基于全部分類器的加權求和結(jié)果，而這個權重代表的是該分類器在上一輪迭代中的成功度。歷史上，Kearns和Valiant首先提出了'強可學習(strongly learnable)'和'弱可學習(weakly learnable)'的概念。指出：在概率近似正確(probably approximately correct, PAC)學習的框架中，一個概念(一個類)，如果存在一個多項式的學習算法能夠?qū)W習它，并且正確率很高，那么就稱這個概念是強可學習的；一個概念，如果存在一個多項式的學習算法能夠?qū)W習它，學習的正確率僅比隨機猜測略好，那么就稱這個概念是弱可學習的。非常有趣的是Schapire后來證明強可學習與弱可學習是等價的，也就是說，在PAC學習的框架下，一個概念是強可學習的充分必要條件是這個概念是弱可學習的。這樣一來，問題便成為，在學習中，如果已經(jīng)發(fā)現(xiàn)了'弱學習算法'，那么能否將它提升（boost）為'強學習算法'。大家知道，發(fā)現(xiàn)弱學習算法通常要比發(fā)現(xiàn)強學習算法容易得多。那么如何具體實施提升，便成為開發(fā)提升方法時所要解決的問題。關于提升方法的研究很多，有很多算法被提出。最具代表性的是AdaBoost算法(AdaBoost algorithm，adaptive boosting algorithm)。
AdaBoost算法工作原理：開始時，賦予訓練數(shù)據(jù)中的每個樣本一個相等的初始權重值，這些權重構成了向量D。首先在訓練數(shù)據(jù)上訓練出一個弱分類器并計算該分類的錯誤率，然后在同一數(shù)據(jù)集上再次訓練弱分類器。在分類器的第二次訓練中，將第一次分對的樣本的權重降低，將第一次分錯的樣本的權重提高。這樣一來，那些沒有得到正確分類的數(shù)據(jù)，由于其權值的加大而受到后一輪的弱分類器的更大關注。反復學習，不斷調(diào)整樣本權重，最終得到一個強分類器。
最終，AdaBoost算法的分類器是：
舉栗子-AdaBoost算法模型：
1）準備數(shù)據(jù)
2）準備一些后續(xù)用到的工具函數(shù)
在此，要先介紹下“單層決策樹”。單層決策樹(decision stump，也稱決策樹樁)是一種簡單的決策樹，它僅基于單個特征來做決策，由于這棵樹只有一次分裂過程，因此實際就是一個樹樁。而圖4中的stumpClassify函數(shù)就是基于這一思想，在分類時，根據(jù)某種比較規(guī)則，如less than (lt) 或者 great than (gt)等，判斷屬性值與閾值的關系。buildStump函數(shù)是構建單層決策樹，包括三層嵌套循環(huán)。
3）基于單層決策樹的AdaBoost算法
此算法主要流程為：在限定最大運算次數(shù)的限制下，分別計算alpha、weights、和errorRate，當errorRate=0時跳出循環(huán)，此過程中的計算主要是依據(jù)圖1中的計算式。實際分類器不是僅限于單層決策樹，任何一種分類算法都可以作為基分類器。
4）AdaBoost分類函數(shù)
好噠，關于提升方法的基礎學習先到這里，等在下一階段的深入學習中再往深挖掘，希望對大家有幫助，歡迎大神隨時指點。謝謝
