1.CART（Classification And Regression Tree）
思想：遞歸地將輸入空間分割成矩形
優點：可以進行變量選擇，可以克服missing data，可以處理混合預測
缺點：不穩定

分類訓練過程：

?

?

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

?

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

流程圖如下：

?

3.隨機森林：

隨機森林，指的是利用多棵樹對樣本進行訓練并預測的一種分類器。該分類器最早由Leo Breiman和Adele Cutler提出，并被注冊成了商標。簡單來說，隨機森林就是由多棵CART（Classification And Regression Tree）構成的。對于每棵樹，它們使用的訓練集是從總的訓練集中有放回采樣出來的，這意味著，總的訓練集中的有些樣本可能多次出現在一棵樹的訓練集中，也可能從未出現在一棵樹的訓練集中。在訓練每棵樹的節點時，使用的特征是從所有特征中按照一定比例隨機地無放回的抽取的，根據Leo Breiman的建議，假設總的特征數量為M，這個比例可以是sqrt(M),1/2sqrt(M),2sqrt(M)。

因此，隨機森林的訓練過程可以總結如下：

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

對于第1-t棵樹，i=1-t：

(2)從S中有放回的抽取大小和S一樣的訓練集S(i)，作為根節點的樣本，從根節點開始訓練

(3)如果當前節點上達到終止條件，則設置當前節點為葉子節點，如果是分類問題，該葉子節點的預測輸出為當前節點樣本集合中數量最多的那一類c(j)，概率p為c(j)占當前樣本集的比例；如果是回歸問題，預測輸出為當前節點樣本集各個樣本值的平均值。然后繼續訓練其他節點。如果當前節點沒有達到終止條件，則從F維特征中無放回的隨機選取f維特征。利用這f維特征，尋找分類效果最好的一維特征k及其閾值th，當前節點上樣本第k維特征小于th的樣本被劃分到左節點，其余的被劃分到右節點。繼續訓練其他節點。有關分類效果的評判標準在后面會講。

(4)重復(2)(3)直到所有節點都訓練過了或者被標記為葉子節點。

(5)重復(2),(3),(4)直到所有CART都被訓練過。

利用隨機森林的預測過程如下：

對于第1-t棵樹，i=1-t：

(1)從當前樹的根節點開始，根據當前節點的閾值th，判斷是進入左節點(
=th)，直到到達，某個葉子節點，并輸出預測值。

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

注：有關分類效果的評判標準，因為使用的是CART，因此使用的也是CART的平板標準，和C3.0,C4.5都不相同。

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

對于回歸問題，相對更加簡單，直接使用argmax(Var-VarLeft-VarRight)作為評判標準，即當前節點訓練集的方差Var減去減去左子節點的方差VarLeft和右子節點的方差VarRight值最大。

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

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

結構如圖：

?

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

尋找多個識別率不是很高的弱分類算法比尋找一個識別率很高的強分類算法要容易得多,AdaBoost 算法的任務就是完成將容易找到的識別率不高的弱分類算法提升為識別率很高的強分類算法,這也是 AdaBoost 算法的核心指導思想所在,如果算法完成了這個任務,那么在分類時,只要找到一個比隨機猜測略好的弱分類算法,就可以將其提升為強分類算法,而不必直接去找通常情況下很難獲得的強分類算法。通過產生多分類器最后聯合的方法提升弱分類算法,讓他變為強的分類算法,也就是給定一個弱的學習算法和訓練集,在訓練集的不同子集上,多次調用弱學習算法,最終按加權方式聯合多次弱學習算法的預測結果得到最終學習結果。包含以下2點:

樣本的權重
AdaBoost 通過對樣本集的操作來訓練產生不同的分類器,他是通過更新分布權值向量來改變樣本權重的,也 就是提高分錯樣本的權重,重點對分錯樣本進行訓練。

(1) 沒有先驗知識的情況下,初始的分布應為等概分布,也就是訓練集如果有 n個樣本,每個樣本的分布概率為1/ n。(2) 每次循環后提高錯誤樣本的分布概率,分錯的樣本在訓練集中所占權重增大,使得下一次循環的基分類器能夠集中力量對這些錯誤樣本進行判斷。

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

參考文章：

[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]女神的博文：