随機森林算法——Random Forest（RF）

Bagging和Boosting 概念及差別

随機森林屬于內建學習（Ensemble Learning）中的bagging算法。在內建學習中，主要分為bagging算法和boosting算法。我們先看看這兩種方法的特點和差別。

Bagging

bagging的算法過程如下：

1. 從原始樣本集中使用Bootstraping方法随機抽取n個訓練樣本，共進行k輪抽取，得到k個訓練集。（k個訓練集之間互相獨立，元素可以有重複）
2. 對于k個訓練集，我們訓練k個模型（這k個模型可以根據具體問題而定，比如決策樹，knn等）
3. 對于分類問題：由投票表決産生分類結果；對于回歸問題：由k個模型預測結果的均值作為最後預測結果。（所有模型的重要性相同）

Boosting

boosting的算法過程如下：

1. 對于訓練集中的每個樣本建立權值wi，表示對每個樣本的關注度。當某個樣本被誤分類的機率很高時，需要加大對該樣本的權值。
2. 進行疊代的過程中，每一步疊代都是一個弱分類器。我們需要用某種政策将其組合，作為最終模型。（例如AdaBoost給每個弱分類器一個權值，将其線性組合最為最終分類器。誤差越小的弱分類器，權值越大）

Bagging，Boosting的主要差別

1. 樣本選擇上：Bagging采用的是Bootstrap随機有放回抽樣；而Boosting每一輪的訓練集是不變的，改變的隻是每一個樣本的權重。
2. 樣本權重：Bagging使用的是均勻取樣，每個樣本權重相等；Boosting根據錯誤率調整樣本權重，錯誤率越大的樣本權重越大。
3. 預測函數：Bagging所有的預測函數的權重相等；Boosting中誤差越小的預測函數其權重越大。
4. 并行計算：Bagging各個預測函數可以并行生成；Boosting各個預測函數必須按順序疊代生成。

下面是将決策樹與這些算法架構進行結合所得到的新的算法：

1. Bagging + 決策樹 = 随機森林
2. AdaBoost + 決策樹 = 提升樹
3. Gradient Boosting + 決策樹 = GBDT

決策樹

常用的決策樹分為ID3，C4.5,CART三種。決策樹模型的建構如下：

決策樹的生成

輸入：訓練集D，特征集A，門檻值eps

輸出：決策樹T

1. 若D中所有樣本屬于同一類Ck，則T為單節點樹，将類Ck作為該結點的類标記，傳回T
2. 若A為空集，即沒有特征作為劃分依據，則T為單節點樹，并将D中執行個體數最大的類Ck作為該結點的類标記，傳回T
3. 否則，計算A中各特征對D的資訊增益(ID3)/資訊增益比(C4.5)，選擇資訊增益最大的特征Ag
4. 若Ag的資訊增益（比）小于門檻值eps，則置T為單節點樹，并将D中執行個體數最大的類Ck作為該結點的類标記，傳回T
5. 否則，依照特征Ag将D劃分為若幹非空子集Di，将Di中執行個體數最大的類作為标記，建構子節點，由結點及其子節點構成樹T，傳回T
6. 對第i個子節點，以Di為訓練集，以A-{Ag}為特征集，遞歸地調用1~5，得到子樹Ti，傳回Ti

ID3，C4.5決策樹的差別

1. ID3以資訊增益為準則劃分屬性，遞歸建構決策樹。一般而言，資訊增益越大，意味着使用屬性進行劃分所獲得的“純度提升越大”
2. C4.5以增益率為準則劃分屬性。資訊增益準則對取值數目較多的屬性有所偏好，增益率對取值數目較少的屬性有所偏好，C4.5不是直接選擇增益率最大的候選劃分屬性，而使用一種啟發式：先從候選劃分屬性中找到資訊增益高于平均水準的屬性，再從中選擇增益率最高的

CART

分類與回歸樹（CART）同樣由特征選擇、樹的生成和剪枝組成。但CART還在給定輸入随機變量X條件下輸出随機變量Y的條件機率分布的學習方法。

CART假設決策樹是二叉樹，遞歸地二分每個特征，将輸入空間劃分為有限個單元，并在這些單元上預測機率分布。

CART由兩步組成：

1. 樹生成：基于訓練集生成決策樹，生成決策樹盡量地大。
2. 樹的剪枝：用驗證集對已生成的樹進行剪枝并選擇最優子樹。

CART決策樹的生成（分類）

輸入：訓練資料集D，特征值集A

輸出：CART決策樹

停止計算條件：結點中的樣本個數小于預定門檻值，樣本集的Gini系數小于預定門檻值（樣本基本屬于同一類），或者沒有更多特征。

根據訓練資料集，從根結點開始，遞歸地對每個結點進行以下操作，建構二叉決策樹：

1. 設結點的訓練資料集為D，計算現有屬性對該資料集的Gini系數。此時，對每一個特征A，對其可能取的每個值a，根據樣本點對A=a的測試為“是”或“否”将D分割成D1和D2兩部分，計算A=a時的Gini系數。
2. 在所有可能的特征A以及它們所有可能的切分點a中，選擇Gini系數最小的特征及其對應的切分點作為最優特征與最優切分點。依最優特征與最優切分點，從現結點生成兩個子結點，将訓練資料集依特征配置設定到兩個子結點中去。
3. 對兩個子結點遞歸地調用步驟l~2，直至滿足停止條件。
4. 生成CART決策樹。

CART決策樹的生成（回歸）

輸入：訓練資料集D

輸出：回歸數f(x)

在訓練資料所在輸入空間中，遞歸地将每個區域劃分為兩個子區域并決定每個子區域的輸出值，建構二叉決策樹。

1. 選擇最優切分變量j和切分點s，求解

   minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2] min j , s ⁡ [ min c 1 ⁡ ∑ x i ∈ R 1 ( j , s ) ⁡ ( y i − c 1 ) 2 + min c 2 ⁡ ∑ x i ∈ R 2 ( j , s ) ⁡ ( y i − c 2 ) 2 ]

   其中， R1(j,s)=(x|x(j)⩽s),R2(j,s)=(x|x(j)⩾s) R 1 ( j , s ) = ( x | x ( j ) ⩽ s ) , R 2 ( j , s ) = ( x | x ( j ) ⩾ s ) ，周遊變量j，對固定切分變量j掃描切分點s，選擇使上式達到最小值的對（j,s）。

2. 用標明的對（j,s）劃分區域并決定相應的輸出值。

   R1(j,s)=(x|x(j)⩽s),R2(j,s)=(x|x(j)⩾s) R 1 ( j , s ) = ( x | x ( j ) ⩽ s ) , R 2 ( j , s ) = ( x | x ( j ) ⩾ s )

   c^=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2 c ^ = 1 N m ∑ x i ∈ R m ( j , s ) ⁡ y i , x ∈ R m , m = 1 , 2

3. 繼續對兩個子區域調用步驟1，2，知道滿足停止條件。

4. 将輸入空間劃分為M個區域， R1,R2,...Rm R 1 , R 2 , . . . R m ，生成決策樹。

   f(x)=∑m=1Mc^I(x∈Rm) f ( x ) = ∑ m = 1 M ⁡ c ^ I ( x ∈ R m )

關于CART更詳細的說明參考李航的統計學習方法

随機森林（Random Forests）

随機森林是一種重要的基于Bagging的內建學習方法，可以用來做分類、回歸等問題。

随機森林有許多優點：

• 具有極高的準确率
• 随機性的引入，使得随機森林不容易過拟合
• 随機性的引入，使得随機森林有很好的抗噪聲能力
• 能處理很高次元的資料，并且不用做特征選擇
• 既能處理離散型資料，也能處理連續型資料，資料集無需規範化
• 訓練速度快，可以得到變量重要性排序
• 容易實作并行化

随機森林的缺點：

• 當随機森林中的決策樹個數很多時，訓練時需要的空間和時間會較大
• 随機森林模型還有許多不好解釋的地方，有點算個黑盒模型

與上面介紹的Bagging過程相似，随機森林的建構過程大緻如下：

1. 從原始訓練集中使用Bootstraping方法随機有放回采樣選出m個樣本，共進行n_tree次采樣，生成n_tree個訓練集
2. 對于n_tree個訓練集，我們分别訓練n_tree個決策樹模型
3. 對于單個決策樹模型，假設訓練樣本特征的個數為n，那麼每次分裂時根據資訊增益/資訊增益比/基尼指數選擇最好的特征進行分裂
4. 每棵樹都一直這樣分裂下去，直到該節點的所有訓練樣例都屬于同一類。在決策樹的分裂過程中不需要剪枝
5. 将生成的多棵決策樹組成随機森林。對于分類問題，按多棵樹分類器投票決定最終分類結果；對于回歸問題，由多棵樹預測值的均值決定最終預測結果

參考：

1、統計學習方法——李航

2、本文的參考部落格https://blog.csdn.net/qq547276542/article/details/78304454

3、關于決策樹的特征選擇（資訊增益，增益率，Gini系數）和決策樹的剪枝

4、CART決策樹的直覺講解

5、CARTpython代碼實作