1.CART（Classification And Regression Tree）
思想：遞歸地將輸入空間分割成矩形
優(yōu)點(diǎn)：可以進(jìn)行變量選擇，可以克服missing data，可以處理混合預(yù)測(cè)
缺點(diǎn)：不穩(wěn)定

分類(lèi)訓(xùn)練過(guò)程：

?

?

就這樣不斷分割之后可以建立如下這樣的決策樹(shù)：

?

2.Bagging (Breiman1996): 也稱(chēng)bootstrap aggregation
Bagging的策略：
- 從樣本集中用Bootstrap采樣選出n個(gè)樣本
- 在所有屬性上，對(duì)這n個(gè)樣本建立分類(lèi)器（CART or SVM or ...）
- 重復(fù)以上兩步m次，i.e.build m個(gè)分類(lèi)器（CART or SVM or ...）
- 將數(shù)據(jù)放在這m個(gè)分類(lèi)器上跑，最后vote看到底分到哪一類(lèi)
Fit many large trees to bootstrap resampled versions of the training data, and classify by majority vote.
下圖是Bagging的選擇策略，每次從N個(gè)數(shù)據(jù)中采樣n次得到n個(gè)數(shù)據(jù)的一個(gè)bag，總共選擇B次得到B個(gè)bags，也就是B個(gè)bootstrap samples.

流程圖如下：

?

3.隨機(jī)森林：

隨機(jī)森林，指的是利用多棵樹(shù)對(duì)樣本進(jìn)行訓(xùn)練并預(yù)測(cè)的一種分類(lèi)器。該分類(lèi)器最早由Leo Breiman和Adele Cutler提出，并被注冊(cè)成了商標(biāo)。簡(jiǎn)單來(lái)說(shuō)，隨機(jī)森林就是由多棵CART（Classification And Regression Tree）構(gòu)成的。對(duì)于每棵樹(shù)，它們使用的訓(xùn)練集是從總的訓(xùn)練集中有放回采樣出來(lái)的，這意味著，總的訓(xùn)練集中的有些樣本可能多次出現(xiàn)在一棵樹(shù)的訓(xùn)練集中，也可能從未出現(xiàn)在一棵樹(shù)的訓(xùn)練集中。在訓(xùn)練每棵樹(shù)的節(jié)點(diǎn)時(shí)，使用的特征是從所有特征中按照一定比例隨機(jī)地?zé)o放回的抽取的，根據(jù)Leo Breiman的建議，假設(shè)總的特征數(shù)量為M，這個(gè)比例可以是sqrt(M),1/2sqrt(M),2sqrt(M)。

因此，隨機(jī)森林的訓(xùn)練過(guò)程可以總結(jié)如下：

(1)給定訓(xùn)練集S，測(cè)試集T，特征維數(shù)F。確定參數(shù)：使用到的CART的數(shù)量t，每棵樹(shù)的深度d，每個(gè)節(jié)點(diǎn)使用到的特征數(shù)量f，終止條件：節(jié)點(diǎn)上最少樣本數(shù)s，節(jié)點(diǎn)上最少的信息增益m

對(duì)于第1-t棵樹(shù)，i=1-t：

(2)從S中有放回的抽取大小和S一樣的訓(xùn)練集S(i)，作為根節(jié)點(diǎn)的樣本，從根節(jié)點(diǎn)開(kāi)始訓(xùn)練

(3)如果當(dāng)前節(jié)點(diǎn)上達(dá)到終止條件，則設(shè)置當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，如果是分類(lèi)問(wèn)題，該葉子節(jié)點(diǎn)的預(yù)測(cè)輸出為當(dāng)前節(jié)點(diǎn)樣本集合中數(shù)量最多的那一類(lèi)c(j)，概率p為c(j)占當(dāng)前樣本集的比例；如果是回歸問(wèn)題，預(yù)測(cè)輸出為當(dāng)前節(jié)點(diǎn)樣本集各個(gè)樣本值的平均值。然后繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)沒(méi)有達(dá)到終止條件，則從F維特征中無(wú)放回的隨機(jī)選取f維特征。利用這f維特征，尋找分類(lèi)效果最好的一維特征k及其閾值th，當(dāng)前節(jié)點(diǎn)上樣本第k維特征小于th的樣本被劃分到左節(jié)點(diǎn)，其余的被劃分到右節(jié)點(diǎn)。繼續(xù)訓(xùn)練其他節(jié)點(diǎn)。有關(guān)分類(lèi)效果的評(píng)判標(biāo)準(zhǔn)在后面會(huì)講。

(4)重復(fù)(2)(3)直到所有節(jié)點(diǎn)都訓(xùn)練過(guò)了或者被標(biāo)記為葉子節(jié)點(diǎn)。

(5)重復(fù)(2),(3),(4)直到所有CART都被訓(xùn)練過(guò)。

利用隨機(jī)森林的預(yù)測(cè)過(guò)程如下：

對(duì)于第1-t棵樹(shù)，i=1-t：

(1)從當(dāng)前樹(shù)的根節(jié)點(diǎn)開(kāi)始，根據(jù)當(dāng)前節(jié)點(diǎn)的閾值th，判斷是進(jìn)入左節(jié)點(diǎn)(
=th)，直到到達(dá)，某個(gè)葉子節(jié)點(diǎn)，并輸出預(yù)測(cè)值。

(2)重復(fù)執(zhí)行(1)直到所有t棵樹(shù)都輸出了預(yù)測(cè)值。如果是分類(lèi)問(wèn)題，則輸出為所有樹(shù)中預(yù)測(cè)概率總和最大的那一個(gè)類(lèi)，即對(duì)每個(gè)c(j)的p進(jìn)行累計(jì)；如果是回歸問(wèn)題，則輸出為所有樹(shù)的輸出的平均值。

注：有關(guān)分類(lèi)效果的評(píng)判標(biāo)準(zhǔn)，因?yàn)槭褂玫氖荂ART，因此使用的也是CART的平板標(biāo)準(zhǔn)，和C3.0,C4.5都不相同。

對(duì)于分類(lèi)問(wèn)題（將某個(gè)樣本劃分到某一類(lèi)），也就是離散變量問(wèn)題，CART使用Gini值作為評(píng)判標(biāo)準(zhǔn)。定義為Gini=1-∑(P(i)*P(i)),P(i)為當(dāng)前節(jié)點(diǎn)上數(shù)據(jù)集中第i類(lèi)樣本的比例。例如：分為2類(lèi)，當(dāng)前節(jié)點(diǎn)上有100個(gè)樣本，屬于第一類(lèi)的樣本有70個(gè)，屬于第二類(lèi)的樣本有30個(gè)，則Gini=1-0.7×07-0.3×03=0.42，可以看出，類(lèi)別分布越平均，Gini值越大，類(lèi)分布越不均勻，Gini值越小。在尋找最佳的分類(lèi)特征和閾值時(shí)，評(píng)判標(biāo)準(zhǔn)為：argmax（Gini-GiniLeft-GiniRight），即尋找最佳的特征f和閾值th，使得當(dāng)前節(jié)點(diǎn)的Gini值減去左子節(jié)點(diǎn)的Gini和右子節(jié)點(diǎn)的Gini值最大。

對(duì)于回歸問(wèn)題，相對(duì)更加簡(jiǎn)單，直接使用argmax(Var-VarLeft-VarRight)作為評(píng)判標(biāo)準(zhǔn)，即當(dāng)前節(jié)點(diǎn)訓(xùn)練集的方差Var減去減去左子節(jié)點(diǎn)的方差VarLeft和右子節(jié)點(diǎn)的方差VarRight值最大。

Random Forest與Bagging的區(qū)別在于：Bagging每次生成決策樹(shù)的時(shí)候從全部的屬性Attributes里面選擇，而Random Forest是隨機(jī)從全部Attributes的集合里面生成一個(gè)大小固定的子集，相對(duì)而言需要的計(jì)算量更小一些。

4.Boosting(Freund & Schapire 1996):
boosting在選擇hyperspace的時(shí)候給樣本加了一個(gè)權(quán)值，使得loss function盡量考慮那些分錯(cuò)類(lèi)的樣本（i.e.分錯(cuò)類(lèi)的樣本weight大）。
怎么做的呢？
- boosting重采樣的不是樣本，而是樣本的分布，對(duì)于分類(lèi)正確的樣本權(quán)值低，分類(lèi)錯(cuò)誤的樣本權(quán)值高（通常是邊界附近的樣本），最后的分類(lèi)器是很多弱分類(lèi)器的線性疊加（加權(quán)組合），分類(lèi)器相當(dāng)簡(jiǎn)單。

結(jié)構(gòu)如圖：

?

AdaBoost和RealBoost是Boosting的兩種實(shí)現(xiàn)方法。general的說(shuō)，Adaboost較好用，RealBoost較準(zhǔn)確。由于Boosting算法在解決實(shí)際問(wèn)題時(shí)有一個(gè)重大的缺陷,即他們都要求事先知道弱分類(lèi)算法分類(lèi)正確率的下限,這在實(shí)際問(wèn)題中很難做到。后來(lái) Freund 和 Schapire提出了 AdaBoost 算法,該算法的效率與 Freund 方法的效率幾乎一樣,卻可以非常容易地應(yīng)用到實(shí)際問(wèn)題中。AdaBoost 是Boosting 算法家族中代表算法,AdaBoost 主要是在整個(gè)訓(xùn)練集上維護(hù)一個(gè)分布權(quán)值向量 D( x) t ,用賦予權(quán)重的訓(xùn)練集通過(guò)弱分類(lèi)算法產(chǎn)生分類(lèi)假設(shè) Ht ( x) ,即基分類(lèi)器,然后計(jì)算他的錯(cuò)誤率,用得到的錯(cuò)誤率去更新分布權(quán)值向量 D( x) t ,對(duì)錯(cuò)誤分類(lèi)的樣本分配更大的權(quán)值,正確分類(lèi)的樣本賦予更小的權(quán)值。每次更新后用相同的弱分類(lèi)算法產(chǎn)生新的分類(lèi)假設(shè),這些分類(lèi)假設(shè)的序列構(gòu)成多分類(lèi)器。對(duì)這些多分類(lèi)器用加權(quán)的方法進(jìn)行聯(lián)合,最后得到?jīng)Q策結(jié)果。這種方法不要求產(chǎn)生的單個(gè)分類(lèi)器有高的識(shí)別率,即不要求尋找識(shí)別率很高的基分類(lèi)算法,只要產(chǎn)生的基分類(lèi)器的識(shí)別率大于 015 ,就可作為該多分類(lèi)器序列中的一員。

尋找多個(gè)識(shí)別率不是很高的弱分類(lèi)算法比尋找一個(gè)識(shí)別率很高的強(qiáng)分類(lèi)算法要容易得多,AdaBoost 算法的任務(wù)就是完成將容易找到的識(shí)別率不高的弱分類(lèi)算法提升為識(shí)別率很高的強(qiáng)分類(lèi)算法,這也是 AdaBoost 算法的核心指導(dǎo)思想所在,如果算法完成了這個(gè)任務(wù),那么在分類(lèi)時(shí),只要找到一個(gè)比隨機(jī)猜測(cè)略好的弱分類(lèi)算法,就可以將其提升為強(qiáng)分類(lèi)算法,而不必直接去找通常情況下很難獲得的強(qiáng)分類(lèi)算法。通過(guò)產(chǎn)生多分類(lèi)器最后聯(lián)合的方法提升弱分類(lèi)算法,讓他變?yōu)閺?qiáng)的分類(lèi)算法,也就是給定一個(gè)弱的學(xué)習(xí)算法和訓(xùn)練集,在訓(xùn)練集的不同子集上,多次調(diào)用弱學(xué)習(xí)算法,最終按加權(quán)方式聯(lián)合多次弱學(xué)習(xí)算法的預(yù)測(cè)結(jié)果得到最終學(xué)習(xí)結(jié)果。包含以下2點(diǎn):

樣本的權(quán)重
AdaBoost 通過(guò)對(duì)樣本集的操作來(lái)訓(xùn)練產(chǎn)生不同的分類(lèi)器,他是通過(guò)更新分布權(quán)值向量來(lái)改變樣本權(quán)重的,也 就是提高分錯(cuò)樣本的權(quán)重,重點(diǎn)對(duì)分錯(cuò)樣本進(jìn)行訓(xùn)練。

(1) 沒(méi)有先驗(yàn)知識(shí)的情況下,初始的分布應(yīng)為等概分布,也就是訓(xùn)練集如果有 n個(gè)樣本,每個(gè)樣本的分布概率為1/ n。(2) 每次循環(huán)后提高錯(cuò)誤樣本的分布概率,分錯(cuò)的樣本在訓(xùn)練集中所占權(quán)重增大,使得下一次循環(huán)的基分類(lèi)器能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷。

弱分類(lèi)器的權(quán)重
最后的強(qiáng)分類(lèi)器是通過(guò)多個(gè)基分類(lèi)器聯(lián)合得到的,因此在最后聯(lián)合時(shí)各個(gè)基分類(lèi)器所起的作用對(duì)聯(lián)合結(jié)果有很大的影響,因?yàn)椴煌诸?lèi)器的識(shí)別率不同,他的作用就應(yīng)該不同,這里通過(guò)權(quán)值體現(xiàn)他的作用,因此識(shí)別率越高的基分類(lèi)器權(quán)重越高,識(shí)別率越低的基分類(lèi)器權(quán)重越低。權(quán)值計(jì)算如下: 基分類(lèi)器的錯(cuò)誤率: e = ∑( ht ( x i) ≠yi) Di (1) 基分類(lèi)器的權(quán)重:W t = F( e) ,由基分類(lèi)器的錯(cuò)誤率計(jì)算他的權(quán)重。2.3 算法流程及偽碼描述 算法流程描述 算法流程可用結(jié)構(gòu)圖 1 描述,如圖 1 所示 AdaBoost重復(fù)調(diào)用弱學(xué)習(xí)算法(多輪調(diào)用產(chǎn)生多個(gè)分類(lèi)器) ,首輪調(diào)用弱學(xué)習(xí)算法時(shí),按均勻分布從樣本集中選取子集作為該次訓(xùn)練集,以后每輪對(duì)前一輪訓(xùn)練失敗的樣本,賦予較大的分布權(quán)值( Di 為第i 輪各個(gè)樣本在樣本集中參與訓(xùn)練的概率) ,使其在這一輪訓(xùn)練出現(xiàn)的概率增加,即在后面的訓(xùn)練學(xué)習(xí)中集中對(duì)比較難訓(xùn)練的樣本進(jìn)行學(xué)習(xí),從而得到 T個(gè)弱的基分類(lèi)器, h1 , h2 , …, ht ,其中 ht 有相應(yīng)的權(quán)值 w t ,并且其權(quán)值大小根據(jù)該分類(lèi)器的效果而定。最后的分類(lèi)器由生成的多個(gè)分類(lèi)器加權(quán)聯(lián)合產(chǎn)生。

參考文章：

[1]Joint Cascade Face Detection and Alignment（ECCV14)

[2]Face Alignment at 3000 FPS via Regressing Local Binary Features (CVPR14)

[3]Cascaded Pose Regression (CVPR10)

[4]Fast Keypoint Recognition in Ten Lines of Code

[5]女神的博文：