我們學(xué)過決策樹、樸素貝葉斯、SVM、K近鄰等分類器算法，他們各有優(yōu)缺點(diǎn)；自然的，我們可以將這些分類器組合起來成為一個(gè)性能更好的分類器，這種組合結(jié)果被稱為 集成方法 (ensemble method)或者 元算法 (meta-method)。使用集成算法時(shí)有多種形式：
不同算法的集成
同一種算法在不同設(shè)置下的集成
數(shù)據(jù)集不同部分分配 給不同分類器之后的集成
1、bagging 和boosting綜述
bagging 和boosting中使用的分類器類型都是一樣的,即上述第二種形式。
bagging，也稱為自舉匯聚法（boostrap aggegating) 是在原始數(shù)據(jù)集中有放回的選擇S次后得到S個(gè)新數(shù)據(jù)集的一種技術(shù)。新數(shù)據(jù)集和原數(shù)據(jù)集大小相等，但是有可能某一條數(shù)據(jù)被選擇了好幾次，而原數(shù)據(jù)集中某些數(shù)據(jù)在新數(shù)據(jù)集中可能不出現(xiàn)。在S個(gè)數(shù)據(jù)集建好之后，將某個(gè)算法分別作用于每個(gè)數(shù)據(jù)集就得到S個(gè)分類器。對新數(shù)據(jù)集進(jìn)行分類時(shí)，就用這S個(gè)分類器進(jìn)行分類，與此同時(shí)，選擇分類器投票結(jié)果中最多的的類別作為最終分類結(jié)果，如圖1所示。Random Forests是一種更先進(jìn)的bagging算法，下文詳細(xì)介紹。
boosting 與bagging很類似，不同的是Boosting是通過串行訓(xùn)練而獲得的，而每個(gè)新分類器都是根據(jù)已經(jīng)訓(xùn)練好的分類器的性能來進(jìn)行訓(xùn)練的。AdaBoost是這一種常用的boosting方法。
2、一種提升算法：AdaBoost
在概率近似正確的學(xué)習(xí)框架（probably approximately corect,PAC）中，一個(gè)概念，如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法能夠?qū)W習(xí)他，并且正確率很高，在統(tǒng)計(jì)學(xué)習(xí)方法中，稱這個(gè)概念是 強(qiáng)可學(xué)習(xí)(strongly learnable)的；而如果正確率僅僅比隨機(jī)猜測（正確率大于0.5）略好，那么稱這個(gè)概念是 弱可學(xué)習(xí)(weakly learnable) 的。然而Schapire證明了再PAC學(xué)習(xí)框架下，一個(gè)概念是強(qiáng)可學(xué)習(xí)的充分必要條件是這個(gè)概念是弱可學(xué)習(xí)的。
那么也就是說，我們可以將“弱學(xué)習(xí)算法”提升為“強(qiáng)學(xué)習(xí)算法”，畢竟弱學(xué)習(xí)算法比強(qiáng)學(xué)習(xí)算法要好找的多了。問題是怎么來提升呢？有很多算法，最具代表性的就是AdaBoost算法。大多數(shù)提升方法都是改變訓(xùn)練數(shù)據(jù)的概率分布（訓(xùn)練數(shù)據(jù)的權(quán)值分布）。
因此，對提升算法有兩個(gè)問題需要回答：
在每一輪如何改變訓(xùn)練數(shù)據(jù)的權(quán)值或者概率分布
如何將若干分類器組合成一個(gè)強(qiáng)分類器
對于第一個(gè)問題AdaBoost通過集中關(guān)注那些錯分的數(shù)據(jù)，即將錯分的數(shù)據(jù)賦予較大的權(quán)重，沒錯分的數(shù)據(jù)賦予較小的權(quán)重，然后再將這有具有新權(quán)重的數(shù)據(jù)集進(jìn)行訓(xùn)練，從而來獲得新分類器；對于第二個(gè)問題，AdaBoost采取加權(quán)多數(shù)表決的方法。
2.1、AdaBoost算法
首先提一下幾個(gè)數(shù)學(xué)表達(dá)式的意思，當(dāng)做本小節(jié)的先驗(yàn)知識吧。
AdaBoost算法
在上述算法中，值得注意的是：
在2（c）中，由弱分類器的系數(shù)計(jì)算公式可知，在當(dāng)前的弱分類器分類后，其分類誤差率em如果小于0.5，系數(shù)$\alpha _{m}$將大于0，并且系數(shù)隨著誤差率em的減少而增大，所以分類誤差率小的基本分類器在最終分類器中的作用越大。
在2（d）中，更新權(quán)值分布時(shí)，被基本分類器誤分類的樣本的權(quán)值得以擴(kuò)大，而被正確分類的樣本的權(quán)值得以縮小，即誤分類樣本在下一次訓(xùn)練中起更大的作用。
在步驟（3）中，f(x)的符號決定實(shí)例x的類，它的絕對值表示分類的確信度。利用基本分類器的線性組合構(gòu)建最終分類器是AdaBoost的一個(gè)特點(diǎn)
AdaBoost算法的示意圖如圖2所示。
2.2、AdaBoost算法的誤差分析
AdaBoost最基本的性質(zhì)是它能在學(xué)習(xí)的過程中不斷的減少訓(xùn)練誤差，即在訓(xùn)練數(shù)據(jù)集上的分類誤差率。那么訓(xùn)練誤差是不是能無限制的減少呢？AdaBoost訓(xùn)練誤差界定理回答了這個(gè)問題。
AdaBoost算法最終分類器的訓(xùn)練誤差界為：
推導(dǎo)從略，見《統(tǒng)計(jì)學(xué)習(xí)方法》一書。
這一定理說明，可以在每一輪選取適當(dāng)?shù)腉m使得Zm最小，從而使訓(xùn)練誤差下降最快。
對于二類分類問題有：
AdaBoost的訓(xùn)練誤差是以指數(shù)速率下降的。AdaBoost具有適應(yīng)性，即它能適應(yīng)弱分類器各自的訓(xùn)練誤差率，這也是它名稱的由來，即adaptive。
3、Random Forests（RF）
RF在實(shí)際中使用非常頻繁，其本質(zhì)上和bagging并無不同，只是RF更具體一些。一般而言可以將RF理解為bagging和DT（CART）的結(jié)合。RF中的基學(xué)習(xí)器使用的是CART樹，由于算法本身能降低方差(variance)，所以會選擇完全生長的CART樹。抽樣方法使用bootstrap，除此之外，RF認(rèn)為隨機(jī)程度越高，算法的效果越好。所以RF中還經(jīng)常隨機(jī)選取樣本的特征屬性、甚至于將樣本的特征屬性通過映射矩陣映射到隨機(jī)的子空間來增大子模型的隨機(jī)性、多樣性。RF預(yù)測的結(jié)果為子樹結(jié)果的平均值。RF具有很好的降噪性，相比單棵的CART樹，RF模型邊界更加平滑，置信區(qū)間也比較大。一般而言，RF中，樹越多模型越穩(wěn)定。
3.1 隨機(jī)森林算法
隨機(jī)森林訓(xùn)練過程如下：
(1)給定訓(xùn)練集S，測試集T，特征維數(shù)F。確定參數(shù)：使用到的CART的數(shù)量t，每棵樹的深度d，每個(gè)節(jié)點(diǎn)使用到的特征數(shù)量f，終止條件：節(jié)點(diǎn)上最少樣本數(shù)s，節(jié)點(diǎn)上最少的信息增益m
對于第1-t棵樹，i=1-t：
(2)從S中有放回的抽取大小和S一樣的訓(xùn)練集S(i)，作為根節(jié)點(diǎn)的樣本，從根節(jié)點(diǎn)開始訓(xùn)練
(3)如果當(dāng)前節(jié)點(diǎn)上達(dá)到終止條件，則設(shè)置當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，如果是分類問題，該葉子節(jié)點(diǎn)的預(yù)測輸出為當(dāng)前節(jié)點(diǎn)樣本集合中數(shù)量最多的那一類c(j)，概率p為c(j)占當(dāng)前樣本集的比例；如果是回歸問題，預(yù)測輸出為當(dāng)前節(jié)點(diǎn)樣本集各個(gè)樣本值的平均值。然后繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)沒有達(dá)到終止條件，則從F維特征中無放回的隨機(jī)選取f維特征。利用這f維特征，尋找分類效果最好的一維特征k及其閾值th，當(dāng)前節(jié)點(diǎn)上樣本第k維特征小于th的樣本被劃分到左節(jié)點(diǎn)，其余的被劃分到右節(jié)點(diǎn)。繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。有關(guān)分類效果的評判標(biāo)準(zhǔn)在后面會講。
(4)重復(fù)(2)(3)直到所有節(jié)點(diǎn)都訓(xùn)練過了或者被標(biāo)記為葉子節(jié)點(diǎn)。
(5)重復(fù)(2),(3),(4)直到所有CART都被訓(xùn)練過。
利用隨機(jī)森林的預(yù)測過程如下：
對于第1-t棵樹，i=1-t：
(1)從當(dāng)前樹的根節(jié)點(diǎn)開始，根據(jù)當(dāng)前節(jié)點(diǎn)的閾值th，判斷是進(jìn)入左節(jié)點(diǎn)(\
我們學(xué)過決策樹、樸素貝葉斯、SVM、K近鄰等分類器算法，他們各有優(yōu)缺點(diǎn)；自然的，我們可以將這些分類器組合起來成為一個(gè)性能更好的分類器，這種組合結(jié)果被稱為 集成方法 (ensemble method)或者 元算法 (meta-method)。使用集成算法時(shí)有多種形式：
不同算法的集成
同一種算法在不同設(shè)置下的集成
數(shù)據(jù)集不同部分分配 給不同分類器之后的集成
1、bagging 和boosting綜述
bagging 和boosting中使用的分類器類型都是一樣的,即上述第二種形式。
bagging，也稱為自舉匯聚法（boostrap aggegating) 是在原始數(shù)據(jù)集中有放回的選擇S次后得到S個(gè)新數(shù)據(jù)集的一種技術(shù)。新數(shù)據(jù)集和原數(shù)據(jù)集大小相等，但是有可能某一條數(shù)據(jù)被選擇了好幾次，而原數(shù)據(jù)集中某些數(shù)據(jù)在新數(shù)據(jù)集中可能不出現(xiàn)。在S個(gè)數(shù)據(jù)集建好之后，將某個(gè)算法分別作用于每個(gè)數(shù)據(jù)集就得到S個(gè)分類器。對新數(shù)據(jù)集進(jìn)行分類時(shí)，就用這S個(gè)分類器進(jìn)行分類，與此同時(shí)，選擇分類器投票結(jié)果中最多的的類別作為最終分類結(jié)果，如圖1所示。Random Forests是一種更先進(jìn)的bagging算法，下文詳細(xì)介紹。
boosting 與bagging很類似，不同的是Boosting是通過串行訓(xùn)練而獲得的，而每個(gè)新分類器都是根據(jù)已經(jīng)訓(xùn)練好的分類器的性能來進(jìn)行訓(xùn)練的。AdaBoost是這一種常用的boosting方法。
2、一種提升算法：AdaBoost
在概率近似正確的學(xué)習(xí)框架（probably approximately corect,PAC）中，一個(gè)概念，如果存在一個(gè)多項(xiàng)式的學(xué)習(xí)算法能夠?qū)W習(xí)他，并且正確率很高，在統(tǒng)計(jì)學(xué)習(xí)方法中，稱這個(gè)概念是 強(qiáng)可學(xué)習(xí)(strongly learnable)的；而如果正確率僅僅比隨機(jī)猜測（正確率大于0.5）略好，那么稱這個(gè)概念是 弱可學(xué)習(xí)(weakly learnable) 的。然而Schapire證明了再PAC學(xué)習(xí)框架下，一個(gè)概念是強(qiáng)可學(xué)習(xí)的充分必要條件是這個(gè)概念是弱可學(xué)習(xí)的。
那么也就是說，我們可以將“弱學(xué)習(xí)算法”提升為“強(qiáng)學(xué)習(xí)算法”，畢竟弱學(xué)習(xí)算法比強(qiáng)學(xué)習(xí)算法要好找的多了。問題是怎么來提升呢？有很多算法，最具代表性的就是AdaBoost算法。大多數(shù)提升方法都是改變訓(xùn)練數(shù)據(jù)的概率分布（訓(xùn)練數(shù)據(jù)的權(quán)值分布）。
因此，對提升算法有兩個(gè)問題需要回答：
在每一輪如何改變訓(xùn)練數(shù)據(jù)的權(quán)值或者概率分布
如何將若干分類器組合成一個(gè)強(qiáng)分類器
對于第一個(gè)問題AdaBoost通過集中關(guān)注那些錯分的數(shù)據(jù)，即將錯分的數(shù)據(jù)賦予較大的權(quán)重，沒錯分的數(shù)據(jù)賦予較小的權(quán)重，然后再將這有具有新權(quán)重的數(shù)據(jù)集進(jìn)行訓(xùn)練，從而來獲得新分類器；對于第二個(gè)問題，AdaBoost采取加權(quán)多數(shù)表決的方法。
2.1、AdaBoost算法
首先提一下幾個(gè)數(shù)學(xué)表達(dá)式的意思，當(dāng)做本小節(jié)的先驗(yàn)知識吧。
AdaBoost算法
在上述算法中，值得注意的是：
在2（c）中，由弱分類器的系數(shù)計(jì)算公式可知，在當(dāng)前的弱分類器分類后，其分類誤差率em如果小于0.5，系數(shù)$\alpha _{m}$將大于0，并且系數(shù)隨著誤差率em的減少而增大，所以分類誤差率小的基本分類器在最終分類器中的作用越大。
在2（d）中，更新權(quán)值分布時(shí)，被基本分類器誤分類的樣本的權(quán)值得以擴(kuò)大，而被正確分類的樣本的權(quán)值得以縮小，即誤分類樣本在下一次訓(xùn)練中起更大的作用。
在步驟（3）中，f(x)的符號決定實(shí)例x的類，它的絕對值表示分類的確信度。利用基本分類器的線性組合構(gòu)建最終分類器是AdaBoost的一個(gè)特點(diǎn)
AdaBoost算法的示意圖如圖2所示。
2.2、AdaBoost算法的誤差分析
AdaBoost最基本的性質(zhì)是它能在學(xué)習(xí)的過程中不斷的減少訓(xùn)練誤差，即在訓(xùn)練數(shù)據(jù)集上的分類誤差率。那么訓(xùn)練誤差是不是能無限制的減少呢？AdaBoost訓(xùn)練誤差界定理回答了這個(gè)問題。
AdaBoost算法最終分類器的訓(xùn)練誤差界為：
推導(dǎo)從略，見《統(tǒng)計(jì)學(xué)習(xí)方法》一書。
這一定理說明，可以在每一輪選取適當(dāng)?shù)腉m使得Zm最小，從而使訓(xùn)練誤差下降最快。
對于二類分類問題有：
AdaBoost的訓(xùn)練誤差是以指數(shù)速率下降的。AdaBoost具有適應(yīng)性，即它能適應(yīng)弱分類器各自的訓(xùn)練誤差率，這也是它名稱的由來，即adaptive。
3、Random Forests（RF）
RF在實(shí)際中使用非常頻繁，其本質(zhì)上和bagging并無不同，只是RF更具體一些。一般而言可以將RF理解為bagging和DT（CART）的結(jié)合。RF中的基學(xué)習(xí)器使用的是CART樹，由于算法本身能降低方差(variance)，所以會選擇完全生長的CART樹。抽樣方法使用bootstrap，除此之外，RF認(rèn)為隨機(jī)程度越高，算法的效果越好。所以RF中還經(jīng)常隨機(jī)選取樣本的特征屬性、甚至于將樣本的特征屬性通過映射矩陣映射到隨機(jī)的子空間來增大子模型的隨機(jī)性、多樣性。RF預(yù)測的結(jié)果為子樹結(jié)果的平均值。RF具有很好的降噪性，相比單棵的CART樹，RF模型邊界更加平滑，置信區(qū)間也比較大。一般而言，RF中，樹越多模型越穩(wěn)定。
3.1 隨機(jī)森林算法
隨機(jī)森林訓(xùn)練過程如下：
(1)給定訓(xùn)練集S，測試集T，特征維數(shù)F。確定參數(shù)：使用到的CART的數(shù)量t，每棵樹的深度d，每個(gè)節(jié)點(diǎn)使用到的特征數(shù)量f，終止條件：節(jié)點(diǎn)上最少樣本數(shù)s，節(jié)點(diǎn)上最少的信息增益m
對于第1-t棵樹，i=1-t：
(2)從S中有放回的抽取大小和S一樣的訓(xùn)練集S(i)，作為根節(jié)點(diǎn)的樣本，從根節(jié)點(diǎn)開始訓(xùn)練
(3)如果當(dāng)前節(jié)點(diǎn)上達(dá)到終止條件，則設(shè)置當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，如果是分類問題，該葉子節(jié)點(diǎn)的預(yù)測輸出為當(dāng)前節(jié)點(diǎn)樣本集合中數(shù)量最多的那一類c(j)，概率p為c(j)占當(dāng)前樣本集的比例；如果是回歸問題，預(yù)測輸出為當(dāng)前節(jié)點(diǎn)樣本集各個(gè)樣本值的平均值。然后繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)沒有達(dá)到終止條件，則從F維特征中無放回的隨機(jī)選取f維特征。利用這f維特征，尋找分類效果最好的一維特征k及其閾值th，當(dāng)前節(jié)點(diǎn)上樣本第k維特征小于th的樣本被劃分到左節(jié)點(diǎn)，其余的被劃分到右節(jié)點(diǎn)。繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。有關(guān)分類效果的評判標(biāo)準(zhǔn)在后面會講。
(4)重復(fù)(2)(3)直到所有節(jié)點(diǎn)都訓(xùn)練過了或者被標(biāo)記為葉子節(jié)點(diǎn)。
(5)重復(fù)(2),(3),(4)直到所有CART都被訓(xùn)練過。
利用隨機(jī)森林的預(yù)測過程如下：
對于第1-t棵樹，i=1-t：
(1)從當(dāng)前樹的根節(jié)點(diǎn)開始，根據(jù)當(dāng)前節(jié)點(diǎn)的閾值th，判斷是進(jìn)入左節(jié)點(diǎn)(\
http://www.cnblogs.com/roadofstudy/p/7218745.html
