隨機(jī)森林屬于集成學(xué)習(xí)（Ensemble Learning）中的bagging算法。在集成學(xué)習(xí)中，主要分為bagging算法和boosting算法。我們先看看這兩種方法的特點和區(qū)別墨礁。
Bagging（套袋法）
bagging的算法過程如下：
從原始樣本集中使用Bootstraping方法隨機(jī)抽取n個訓(xùn)練樣本，共進(jìn)行k輪抽取耳峦，得到k個訓(xùn)練集恩静。（k個訓(xùn)練集之間相互獨立，元素可以有重復(fù)）
對于k個訓(xùn)練集，我們訓(xùn)練k個模型（這k個模型可以根據(jù)具體問題而定驶乾，比如決策樹邑飒，knn等）
對于分類問題：由投票表決產(chǎn)生分類結(jié)果；對于回歸問題：由k個模型預(yù)測結(jié)果的均值作為最后預(yù)測結(jié)果疙咸。（所有模型的重要性相同）
Boosting（提升法）
boosting的算法過程如下：
對于訓(xùn)練集中的每個樣本建立權(quán)值wi，表示對每個樣本的關(guān)注度。當(dāng)某個樣本被誤分類的概率很高時，需要加大對該樣本的權(quán)值客峭。
進(jìn)行迭代的過程中等恐，每一步迭代都是一個弱分類器。我們需要用某種策略將其組合流昏，作為最終模型谚鄙。（例如AdaBoost給每個弱分類器一個權(quán)值知市，將其線性組合最為最終分類器互例。誤差越小的弱分類器糊秆，權(quán)值越大）
Bagging，Boosting的主要區(qū)別
樣本選擇上：Bagging采用的是Bootstrap隨機(jī)有放回抽樣；而Boosting每一輪的訓(xùn)練集是不變的，改變的只是每一個樣本的權(quán)重。
樣本權(quán)重：Bagging使用的是均勻取樣矾兜，每個樣本權(quán)重相等；Boosting根據(jù)錯誤率調(diào)整樣本權(quán)重括荡，錯誤率越大的樣本權(quán)重越大邑闲。
預(yù)測函數(shù)：Bagging所有的預(yù)測函數(shù)的權(quán)重相等褪子；Boosting中誤差越小的預(yù)測函數(shù)其權(quán)重越大。
并行計算：Bagging各個預(yù)測函數(shù)可以并行生成；Boosting各個預(yù)測函數(shù)必須按順序迭代生成刻坊。
下面是將決策樹與這些算法框架進(jìn)行結(jié)合所得到的新的算法：
1）Bagging + 決策樹 = 隨機(jī)森林
2）AdaBoost + 決策樹 = 提升樹
3）Gradient Boosting + 決策樹 = GBDT
決策樹
常用的決策樹算法有ID3漏益，C4.5舞终，CART三種夸盟。3種算法的模型構(gòu)建思想都十分類似，只是采用了不同的指標(biāo)煮纵。決策樹模型的構(gòu)建過程大致如下：
ID3，C4.5決策樹的生成
輸入：訓(xùn)練集D震桶，特征集A，閾值eps 輸出：決策樹T
若D中所有樣本屬于同一類Ck蹲姐，則T為單節(jié)點樹宠能，將類Ck作為該結(jié)點的類標(biāo)記，返回T
若A為空集贡珊，即沒有特征作為劃分依據(jù)翩概，則T為單節(jié)點樹，并將D中實例數(shù)最大的類Ck作為該結(jié)點的類標(biāo)記江咳，返回T
否則逢净，計算A中各特征對D的信息增益(ID3)/信息增益比(C4.5)，選擇信息增益最大的特征Ag
若Ag的信息增益（比）小于閾值eps歼指，則置T為單節(jié)點樹爹土，并將D中實例數(shù)最大的類Ck作為該結(jié)點的類標(biāo)記，返回T
否則踩身，依照特征Ag將D劃分為若干非空子集Di胀茵，將Di中實例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點挟阻，由結(jié)點及其子節(jié)點構(gòu)成樹T琼娘，返回T
對第i個子節(jié)點呵哨，以Di為訓(xùn)練集，以A-{Ag}為特征集轨奄，遞歸地調(diào)用1~5孟害，得到子樹Ti，返回Ti
CART決策樹的生成
這里只簡單介紹下CART與ID3和C4.5的區(qū)別挪拟。
CART樹是二叉樹挨务，而ID3和C4.5可以是多叉樹
CART在生成子樹時，是選擇一個特征一個取值作為切分點玉组，生成兩個子樹
選擇特征和切分點的依據(jù)是基尼指數(shù)谎柄，選擇基尼指數(shù)最小的特征及切分點生成子樹
決策樹的剪枝
決策樹的剪枝主要是為了預(yù)防過擬合，過程就不詳細(xì)介紹了惯雳。
主要思路是從葉節(jié)點向上回溯朝巫，嘗試對某個節(jié)點進(jìn)行剪枝，比較剪枝前后的決策樹的損失函數(shù)值石景。最后我們通過動態(tài)規(guī)劃（樹形dp劈猿，acmer應(yīng)該懂）就可以得到全局最優(yōu)的剪枝方案。
隨機(jī)森林（Random Forests）
隨機(jī)森林是一種重要的基于Bagging的集成學(xué)習(xí)方法潮孽，可以用來做分類揪荣、回歸等問題。
如果用全樣本去訓(xùn)練m棵決策樹顯然是不可取的往史，全樣本訓(xùn)練忽視了局部樣本的規(guī)律仗颈，對于模型的泛化能力是有害的
隨機(jī)森林有許多優(yōu)點：
具有極高的準(zhǔn)確率
隨機(jī)性的引入，使得隨機(jī)森林不容易過擬合
隨機(jī)性的引入椎例，使得隨機(jī)森林有很好的抗噪聲能力
能處理很高維度的數(shù)據(jù)挨决，并且不用做特征選擇
既能處理離散型數(shù)據(jù)，也能處理連續(xù)型數(shù)據(jù)订歪，數(shù)據(jù)集無需規(guī)范化
訓(xùn)練速度快脖祈，可以得到變量重要性排序
容易實現(xiàn)并行化
隨機(jī)森林的缺點：
當(dāng)隨機(jī)森林中的決策樹個數(shù)很多時，訓(xùn)練時需要的空間和時間會較大
隨機(jī)森林模型還有許多不好解釋的地方陌粹，有點算個黑盒模型
與上面介紹的Bagging過程相似撒犀，隨機(jī)森林的構(gòu)建過程大致如下：
從原始訓(xùn)練集中使用Bootstrapping方法隨機(jī)有放回采樣選出m個樣本福压，共進(jìn)行n_tree次采樣掏秩，生成n_tree個訓(xùn)練集
對于n_tree個訓(xùn)練集，我們分別訓(xùn)練n_tree個決策樹模型
對于單個決策樹模型荆姆，假設(shè)訓(xùn)練樣本特征的個數(shù)為n蒙幻，那么每次分裂時根據(jù)信息增益/信息增益比/基尼指數(shù)選擇最好的特征進(jìn)行分裂
每棵樹都一直這樣分裂下去，直到該節(jié)點的所有訓(xùn)練樣例都屬于同一類胆筒。在決策樹的分裂過程中不需要剪枝
將生成的多棵決策樹組成隨機(jī)森林邮破。對于分類問題诈豌，按多棵樹分類器投票決定最終分類結(jié)果；對于回歸問題抒和，由多棵樹預(yù)測值的均值決定最終預(yù)測結(jié)果
