出差結(jié)束勋陪，繼續(xù)好好學(xué)習(xí)機(jī)器學(xué)習(xí)基礎(chǔ)算法髓梅，今天了解提升方法(Boosting)，主要側(cè)重于AdaBoost算法糙俗，同樣理論知識(shí)來自Peter Harrington的《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》和李航的《統(tǒng)計(jì)學(xué)習(xí)方法》绷杜，非常感謝這些優(yōu)秀人物和優(yōu)秀書籍直秆，正文開始啦
提升算法(Boosting)
考慮前幾篇提到的分類算法，各有利弊鞭盟，如果可以有效地將這些分類器結(jié)合起來圾结，各取所長(zhǎng)，應(yīng)該也是不錯(cuò)的選擇齿诉。提升算法正是基于這樣的思想筝野，但是它不是簡(jiǎn)單、均等的將不同分類器的結(jié)果相加粤剧，而是基于全部分類器的加權(quán)求和結(jié)果歇竟，而這個(gè)權(quán)重代表的是該分類器在上一輪迭代中的成功度。歷史上抵恋，Kearns和Valiant首先提出了'強(qiáng)可學(xué)習(xí)(strongly learnable)'和'弱可學(xué)習(xí)(weakly learnable)'的概念焕议。指出：在概率近似正確(probably approximately correct, PAC)學(xué)習(xí)的框架中，一個(gè)概念(一個(gè)類)弧关，如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法能夠?qū)W習(xí)它盅安，并且正確率很高，那么就稱這個(gè)概念是強(qiáng)可學(xué)習(xí)的世囊；一個(gè)概念别瞭，如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法能夠?qū)W習(xí)它，學(xué)習(xí)的正確率僅比隨機(jī)猜測(cè)略好株憾，那么就稱這個(gè)概念是弱可學(xué)習(xí)的蝙寨。非常有趣的是Schapire后來證明強(qiáng)可學(xué)習(xí)與弱可學(xué)習(xí)是等價(jià)的，也就是說，在PAC學(xué)習(xí)的框架下籽慢，一個(gè)概念是強(qiáng)可學(xué)習(xí)的充分必要條件是這個(gè)概念是弱可學(xué)習(xí)的。這樣一來猫胁，問題便成為箱亿，在學(xué)習(xí)中，如果已經(jīng)發(fā)現(xiàn)了'弱學(xué)習(xí)算法'弃秆，那么能否將它提升（boost）為'強(qiáng)學(xué)習(xí)算法'届惋。大家知道，發(fā)現(xiàn)弱學(xué)習(xí)算法通常要比發(fā)現(xiàn)強(qiáng)學(xué)習(xí)算法容易得多菠赚。那么如何具體實(shí)施提升脑豹，便成為開發(fā)提升方法時(shí)所要解決的問題。關(guān)于提升方法的研究很多衡查，有很多算法被提出瘩欺。最具代表性的是AdaBoost算法(AdaBoost algorithm，adaptive boosting algorithm)拌牲。
AdaBoost算法工作原理：開始時(shí)俱饿，賦予訓(xùn)練數(shù)據(jù)中的每個(gè)樣本一個(gè)相等的初始權(quán)重值，這些權(quán)重構(gòu)成了向量D塌忽。首先在訓(xùn)練數(shù)據(jù)上訓(xùn)練出一個(gè)弱分類器并計(jì)算該分類的錯(cuò)誤率拍埠，然后在同一數(shù)據(jù)集上再次訓(xùn)練弱分類器。在分類器的第二次訓(xùn)練中土居，將第一次分對(duì)的樣本的權(quán)重降低枣购，將第一次分錯(cuò)的樣本的權(quán)重提高。這樣一來擦耀，那些沒有得到正確分類的數(shù)據(jù)棉圈，由于其權(quán)值的加大而受到后一輪的弱分類器的更大關(guān)注。反復(fù)學(xué)習(xí)埂奈，不斷調(diào)整樣本權(quán)重迄损，最終得到一個(gè)強(qiáng)分類器。
最終账磺，AdaBoost算法的分類器是：
舉栗子-AdaBoost算法模型：
1）準(zhǔn)備數(shù)據(jù)
2）準(zhǔn)備一些后續(xù)用到的工具函數(shù)
在此芹敌，要先介紹下“單層決策樹”。單層決策樹(decision stump垮抗，也稱決策樹樁)是一種簡(jiǎn)單的決策樹氏捞，它僅基于單個(gè)特征來做決策，由于這棵樹只有一次分裂過程冒版，因此實(shí)際就是一個(gè)樹樁液茎。而圖4中的stumpClassify函數(shù)就是基于這一思想，在分類時(shí)，根據(jù)某種比較規(guī)則捆等，如less than (lt) 或者 great than (gt)等滞造，判斷屬性值與閾值的關(guān)系。buildStump函數(shù)是構(gòu)建單層決策樹栋烤，包括三層嵌套循環(huán)谒养。
3）基于單層決策樹的AdaBoost算法
此算法主要流程為：在限定最大運(yùn)算次數(shù)的限制下，分別計(jì)算alpha明郭、weights买窟、和errorRate，當(dāng)errorRate=0時(shí)跳出循環(huán)薯定，此過程中的計(jì)算主要是依據(jù)圖1中的計(jì)算式始绍。實(shí)際分類器不是僅限于單層決策樹，任何一種分類算法都可以作為基分類器话侄。
4）AdaBoost分類函數(shù)
好噠亏推，關(guān)于提升方法的基礎(chǔ)學(xué)習(xí)先到這里，等在下一階段的深入學(xué)習(xí)中再往深挖掘满葛，希望對(duì)大家有幫助径簿，歡迎大神隨時(shí)指點(diǎn)。謝謝
