Bagging（套袋法）
bagging的算法過程如下：
從原始樣本集中使用Bootstraping方法隨機抽取n個訓練樣本，***進行k輪抽取，得到k個訓練集。（k個訓練集之間相互獨立，元素可以有重復）
對於k個訓練集，我們訓練k個模型（這k個模型可以根據具體問題而定，比如決策樹，knn等）
對於分類問題：由投票表決產生分類結果；對於回歸問題：由k個模型預測結果的均值作為最後預測結果。（所有模型的重要性相同）
Boosting（提升法）
boosting的算法過程如下：
對於訓練集中的每個樣本建立權值wi，表示對每個樣本的關註度。當某個樣本被誤分類的概率很高時，需要加大對該樣本的權值。
進行叠代的過程中，每壹步叠代都是壹個弱分類器。我們需要用某種策略將其組合，作為最終模型。（例如AdaBoost給每個弱分類器壹個權值，將其線性組合最為最終分類器。誤差越小的弱分類器，權值越大）
Bagging，Boosting的主要區別
樣本選擇上：Bagging采用的是Bootstrap隨機有放回抽樣；而Boosting每壹輪的訓練集是不變的，改變的只是每壹個樣本的權重。
樣本權重：Bagging使用的是均勻取樣，每個樣本權重相等；Boosting根據錯誤率調整樣本權重，錯誤率越大的樣本權重越大。
預測函數：Bagging所有的預測函數的權重相等；Boosting中誤差越小的預測函數其權重越大。
並行計算：Bagging各個預測函數可以並行生成；Boosting各個預測函數必須按順序叠代生成。
下面是將決策樹與這些算法框架進行結合所得到的新的算法：
1）Bagging + 決策樹 = 隨機森林
2）AdaBoost + 決策樹 = 提升樹
3）Gradient Boosting + 決策樹 = GBDT
決策樹
常用的決策樹算法有ID3，C4.5，CART三種。3種算法的模型構建思想都十分類似，只是采用了不同的指標。決策樹模型的構建過程大致如下：
ID3，C4.5決策樹的生成
輸入：訓練集D，特征集A，閾值eps 輸出：決策樹T
若D中所有樣本屬於同壹類Ck，則T為單節點樹，將類Ck作為該結點的類標記，返回T
若A為空集，即沒有特征作為劃分依據，則T為單節點樹，並將D中實例數最大的類Ck作為該結點的類標記，返回T
否則，計算A中各特征對D的信息增益(ID3)/信息增益比(C4.5)，選擇信息增益最大的特征Ag
若Ag的信息增益（比）小於閾值eps，則置T為單節點樹，並將D中實例數最大的類Ck作為該結點的類標記，返回T
否則，依照特征Ag將D劃分為若幹非空子集Di，將Di中實例數最大的類作為標記，構建子節點，由結點及其子節點構成樹T，返回T
對第i個子節點，以Di為訓練集，以A-{Ag}為特征集，遞歸地調用1~5，得到子樹Ti，返回Ti
CART決策樹的生成
這裏只簡單介紹下CART與ID3和C4.5的區別。
CART樹是二叉樹，而ID3和C4.5可以是多叉樹
CART在生成子樹時，是選擇壹個特征壹個取值作為切分點，生成兩個子樹
選擇特征和切分點的依據是基尼指數，選擇基尼指數最小的特征及切分點生成子樹
決策樹的剪枝
決策樹的剪枝主要是為了預防過擬合，過程就不詳細介紹了。
主要思路是從葉節點向上回溯，嘗試對某個節點進行剪枝，比較剪枝前後的決策樹的損失函數值。最後我們通過動態規劃（樹形dp，acmer應該懂）就可以得到全局最優的剪枝方案。
隨機森林（Random Forests）
隨機森林是壹種重要的基於Bagging的集成學習方法，可以用來做分類、回歸等問題。
如果用全樣本去訓練m棵決策樹顯然是不可取的，全樣本訓練忽視了局部樣本的規律，對於模型的泛化能力是有害的
隨機森林有許多優點：
具有極高的準確率
隨機性的引入，使得隨機森林不容易過擬合
隨機性的引入，使得隨機森林有很好的抗噪聲能力
能處理很高維度的數據，並且不用做特征選擇
既能處理離散型數據，也能處理連續型數據，數據集無需規範化
訓練速度快，可以得到變量重要性排序
容易實現並行化
隨機森林的缺點：
當隨機森林中的決策樹個數很多時，訓練時需要的空間和時間會較大
隨機森林模型還有許多不好解釋的地方，有點算個黑盒模型
與上面介紹的Bagging過程相似，隨機森林的構建過程大致如下：
從原始訓練集中使用Bootstrapping方法隨機有放回采樣選出m個樣本，***進行n_tree次采樣，生成n_tree個訓練集
對於n_tree個訓練集，我們分別訓練n_tree個決策樹模型
對於單個決策樹模型，假設訓練樣本特征的個數為n，那麽每次分裂時根據信息增益/信息增益比/基尼指數選擇最好的特征進行分裂
每棵樹都壹直這樣分裂下去，直到該節點的所有訓練樣例都屬於同壹類。在決策樹的分裂過程中不需要剪枝
將生成的多棵決策樹組成隨機森林。對於分類問題，按多棵樹分類器投票決定最終分類結果；對於回歸問題，由多棵樹預測值的均值決定最終預測結果