幹貨｜從決策樹到隨機森林：樹型算法的實現原理與Python 示例

基於樹（Tree based）的學習算法在數據科學競賽中是相當常見的。這些算法給預測模型賦予了準確性、穩定性以及易解釋性。和線性模型不同，它們對非線性關係也能進行很好的映射。常見的基於樹的模型有：決策樹、隨機森林和提升樹。

在本篇文章中，我們將會介紹決策樹的數學細節（以及各種 Python 示例）及其優缺點。你們將會發現它們很簡單，並且這些內容有助於理解。然而，與最好的監督學習方法相比，它們通常是沒有競爭力的。為了克服決策樹的各種缺點，我們將會聚焦於各種概念（附有 Python 實例），比如自助聚集或袋裝（Bootstrap Aggregating or Bagging），還有隨機森林（Random Forests）。另一種廣泛使用的提升方法會在以後進行單獨討論。每種方法都包括生成多種樹，這些樹被聯合起來，生成一個單一的一致性預測結果，並且經常帶來預測精度的顯著提升。

決策樹是一種監督學習算法。它適用於類別和連續輸入（特征）和輸出（預測）變量。基於樹的方法把特征空間劃分成一係列矩形，然後給每一個矩形安置一個簡單的模型（像一個常數）。從概念上來講，它們是簡單且有效的。首先我們通過一個例子來理解決策樹。然後用一種正規分析方法來分析創建決策樹的過程。考慮一個簡單的借貸公司顧客的數據集合。我們給定了所有客戶的查詢賬戶餘額、信用記錄、任職年限和先前貸款狀況。相關任務是預測顧客的風險等級是否可信。該問題可以使用下列決策樹來解決：

分類和回歸樹（簡稱 CART）是 Leo Breiman 引入的術語，指用來解決分類或回歸預測建模問題的決策樹算法。它常使用 scikit 生成並實現決策樹： sklearn.tree.DecisionTreeClassifier 和 sklearn.tree.DecisionTreeRegressor 分別構建分類和回歸樹。

CART 模型包括選擇輸入變量和那些變量上的分割點，直到創建出適當的樹。使用貪婪算法（greedy algorithm）選擇使用哪個輸入變量和分割點，以使成本函數（cost function）最小化。樹建造的結尾使用了一個預定義的停止準則，比如分配到樹上每一個葉結點的訓練樣本達到最小數量。

其他決策樹算法：

ID3：Iterative Dichotomiser 3
C4.5：ID3 算法的改進
CHAID：Chi-squared Automatic Interaction Detector
MARS：決策樹的擴展式，以更好地解決數值型預測。
條件推斷樹

回歸樹

我們現在關注一下回歸樹的 CART 算法的細節。簡要來說，創建一個決策樹包含兩步：

把預測器空間，即一係列可能值 X_1，X_2，...，X_p 分成 J 個不同的且非重疊的區域 R_1，R_2，...，R_J。
對進入區域 R_J 的每一個樣本觀測值都進行相同的預測，該預測就是 R_J 中訓練樣本預測值的均值。

為了創建 J 個區域 R_1，R_2，...，R_J，預測器區域被分為高維度的矩形或盒形。其目的在於通過下列式子找到能夠使 RSS 最小化的盒形區域 R_1，R_2，...，R_J，

其中，yhat_Rj 即是第 j 個盒形中訓練觀測的平均預測值。鑒於這種空間分割在計算上是不可行的，因此我們常使用貪婪方法（greedy approach）來劃分區域，叫做遞歸二元分割（recursive binary splitting）。

這是貪婪的（greedy），這是因為在創建樹過程中的每一步驟，最佳分割都會在每個特定步驟選定，而不是對未來進行預測，並選取一個將會在未來步驟中出現且有助於創建更好的樹的分隔。注意所有的劃分區域 R_j 都是矩形。為了進行遞歸二元分割，首先選取預測器 X_j 和切割點 s

其中 yhat_R1 為區域 R_1(j,s) 中觀察樣本的平均預測值，yhat_R2 為區域 R_2(j,s) 的觀察樣本預測均值。這一過程不斷重複以搜尋最好的預測器和切分點，並進一步分隔數據以使每一個子區域內的 RSS 最小化。然而，我們不會分割整個預測器空間，我們隻會分割一個或兩個前麵已經認定的區域。這一過程會一直持續，直到達到停止準則，例如我們可以設定停止準則為每一個區域最多包含 m 個觀察樣本。一旦我們創建了區域 R_1、R_2、...、R_J，給定一個測試樣本，我們就可以用該區域所有訓練樣本的平均預測值來預測該測試樣本的值。

分類樹

分類樹和回歸樹十分相似，隻不過它是定性地預測響應值而非定量預測。從上文可知，回歸樹對一個觀察值所預測的連續型數值就是屬於同一葉結點訓練樣本觀察值的均值。但是對於分類樹來說，我們所預測的類別是訓練樣本觀察值在某區域下最常見的類別，即訓練觀察值的模式響應（mode response）。為了達到分類目的，很多時候係統並不會隻預測一個類別，它常常預測一組類別及其出現的概率。

分類樹的生成和回歸樹的生成十分相似。正如在回歸樹中那樣，我們一般使用遞歸性的二元分割來生成分類樹。然而在分類樹中，RSS 不能作為二元分割的標準。我們需要定義葉結點的不純度量 Q_m 來替代 RSS，即一種可以在子集區域 R_1,R_2,...,R_j 度量目標變量同質性的方法。在結點 m 中，我們可以通過 N_m 個樣本觀察值表示一個區域 R_m 所出現類別的頻率，第 k 個類別在第 m 個區域下訓練所出現的頻率可表示為：

其中，I(y_i=k) 為指示函數，即如果 y_i = k，則取 1，否則取零。不純性度量 Q_m 一個比較自然的方法是分類誤差率。分類誤差率描述的是訓練觀察值在某個區域內不屬於最常見類別的概率：

考慮到該函數不可微，因此它不能實現數值優化。此外，該函數在結點概率改變上並不敏感，因此這種分類誤差率對於生成樹十分低效。我們一般使用 Gini 指數和交叉熵函數來衡量結點的誤差度量。Gini 指數可以衡量 k 個類別的總方差，它一般定義為：

較小的 Gini 指數值表示結點包含了某個類別大多數樣本觀察值。在信息論裏麵，交叉熵函數用來衡量係統的混亂度。對於二元係統來說，如果係統包含了一個類別的所有內容，那麼它的值為零，而如果兩個類別的數量一樣多，那麼交叉熵達到最大為 1。因此，和 Gini 指數一樣，交叉熵函數同樣能用於度量結點的不純度：

和 G 一樣，較小的 S 值表示區域內結點包含了單個類別中的大多數觀察值。

決策樹常見參數和概念

如果我們希望以數學的方式理解決策樹，我們首先需要了解決策樹和樹型學習算法的一般概念。理解以下的術語同樣能幫助我們調整模型。

根結點：表示所有數據樣本並可以進一步劃分為兩個或多個子結點的父結點。
分裂（Splitting）：將一個結點劃分為兩個或多個子結點的過程。
決策結點：當一個子結點可進一步分裂為多個子結點，那麼該結點就稱之為決策結點。
葉/終止結點：不會往下進一步分裂的結點，在分類樹中代表類別。
分枝/子樹：整棵決策樹的一部分。
父結點和子結點：如果一個結點往下分裂，該結點稱之為父結點而父結點所分裂出來的結點稱之為子結點。
結點分裂的最小樣本數：在結點分裂中所要求的最小樣本數量（或觀察值數量）。這種方法通常可以用來防止過擬合，較大的最小樣本數可以防止模型對特定的樣本學習過於具體的關係，該超參數應該需要使用驗證集來調整。
葉結點最小樣本數：葉結點所要求的最小樣本數。和結點分裂的最小樣本數一樣，該超參數同樣也可以用來控製過擬合。對於不平衡類別問題來說，我們應該取較小的值，因為屬於較少類別的樣本可能數量上非常少。
樹的最大深度（垂直深度）：該超參數同樣可以用來控製過擬合問題，較小的深度可以防止模型對特定的樣本學習過於具體的關係，該超參數同樣需要在驗證集中調整。
葉結點的最大數量：葉結點的最大個數可以替代數的最大深度這一設定。因為生成一棵深度為 n 的二叉樹，它所能產生的最大葉結點個數為 2^n。
分裂所需要考慮的最大特征數：即當我們搜索更好分離方案時所需要考慮的特征數量，我們常用的方法是取可用特征總數的平方根為最大特征數。

分類樹的實現

為了展示不同的前文所述的決策樹模型，我們將使用 Kaggle 上的美國收入數據集，我們都可以在 Kaggle.com 上下載該數據集。下麵的代碼可以展示該數據集的導入過程和部分內容：

在上麵的代碼中，我們首先需要導入所有需要的庫和模塊，然後再讀取數據和結構到訓練數據和驗證數據中。我們同樣去除 fnlgwt 列，因為該數據行對於模型的訓練並不重要。輸入以下語句可以看到訓練數據的前五行：

如下所示，我們還需要做一些數據清洗。我們需要將所有列的的特殊字符移除，此外任何空格或者「.」都需要移除。

正如上圖所示，有兩行描述了個人的教育：Eduction 和 EdNum。我們假設這兩個特征十分相關，因此我們可以移除 Education 列。Country 列對預測收入並不會起到什麼作用，所以我們需要移除它。

Age 和 EdNum 列是數值型的，我們可以將連續數值型轉化為更高效的方式，例如將年齡換為 10 年的整數倍，教育年限換為 5 年的整數倍，實現的代碼如下：

現在我們已經清理了數據，下麵語句可以展示我們數據的概況：

在訓練集和測試集中，我們發現 <=50K 的類別要比>50K 的多 3 倍。從這裏我們就可以看出來樣本數據並不是均衡的數據，但是在這裏為了簡化問題，我們在這裏將該數據集看作常規問題。

現在，讓我們以圖像的形式看一下訓練數據中的不同特征的分布和相互依存（inter-dependence）關係。首先看一下關係（Relationships）和婚姻狀況（MaritalStatus）特征是如何相互關聯的。

讓我們首先看一下不同年齡組中，教育對收入的影響（用受教育的年數進行衡量）。

最近，有很多關於性別對收入差距的影響的相關說法。我們可以分別看見男性和女性的教育程度和種族間的影響。

直到現在，我們僅關注了非數值特征（non-numeric）的相互關係。現在我們看一下資本收益（CapitalGain）和資本損失（CapitalLoss）對收入的影響。

樹分類器

現在我們理解了我們數據中的一些關係，所以就可以使用 sklearn.tree.DecisionTreeClassifier 創建一個簡單的樹分類器模型。然而，為了使用這一模型，我們需要把所有我們的非數值數據轉化成數值型數據。我們可以直接在 Pandas 數據框架中使用 sklearn.preprocessing.LabeEncoder 模塊和 sklearn_pandas 模塊就可以輕鬆地完成這一步驟。

現在我們用正確的形式對數據進行了訓練和測試，已創建了我們的第一個模型！

最簡單的且沒有優化的概率分類器模型可以達到 83.5% 的精度。在分類問題中，混淆矩陣（confusion matrix）是衡量模型精度的好方法。使用下列代碼我們可以繪製任意基於樹的模型的混淆矩陣。

現在，我們可以看到第一個模型的混淆矩陣：

我們發現多數類別（<=50K）的精度為 90.5%，少數類別（>50K）的精度隻有 60.8%。

讓我們看一下調校此簡單分類器的方法。我們能使用帶有 5 折交叉驗證的 GridSearchCV() 來調校樹分類器的各種重要參數。

經過優化，我們發現精度上升到了 85.9%。在上方，我們也可以看見最優模型的參數。現在，讓我們看一下已優化模型的混淆矩陣（confusion matrix）：

經過優化，我們發現在兩種類別下，預測精度都有所提升。

決策樹的局限性

決策樹有很多優點，比如：

易於理解、易於解釋
可視化
無需大量數據準備。不過要注意，sklearn.tree 模塊不支持缺失值。
使用決策樹（預測數據）的成本是訓練決策時所用數據的對數量級。

但這些模型往往不直接使用，決策樹一些常見的缺陷是：

構建的樹過於複雜，無法很好地在數據上實現泛化。
數據的微小變動可能導致生成的樹完全不同，因此決策樹不夠穩定。
決策樹學習算法在實踐中通常基於啟發式算法，如貪婪算法，在每一個結點作出局部最優決策。此類算法無法確保返回全局最優決策樹。
如果某些類別占據主導地位，則決策樹學習器構建的決策樹會有偏差。因此推薦做法是在數據集與決策樹擬合之前先使數據集保持均衡。
某些類別的函數很難使用決策樹模型來建模，如 XOR、奇偶校驗函數（parity）和數據選擇器函數（multiplexer）。

大部分限製可以通過改善決策樹輕易解決。在下麵的內容中，我們將介紹相關的幾個概念，重點介紹袋裝和隨機森林。

剪枝

由於決策樹容易對數據產生過擬合，因此分支更少（即減少區域 R_1, … ,R_J）的小樹雖然偏差略微高一點，但其產生的方差更低，可解釋性更強。處理上述問題的一種方法是構建一棵樹，每個分支超過某個（高）閾值造成葉結點誤差率 Qm 下降，則結束構建。但是，由於分裂算法的貪婪本質，它其實很短視。決策樹早期看似無用的一次分裂有可能會導致之後一次優秀的分裂，並使得 Qm 大幅下降。

因此，更好的策略是構建一個非常大的樹 T_0，然後再剪枝，得到一棵子樹。剪枝可以使用多種策略。代價複雜度剪枝（Cost complexity pruning），又叫最弱連接剪枝（weakest link pruning），就是其中一種行之有效的策略。除了考慮每一個可能的子樹之外，還需要考慮由非負調參（nonnegative tuning parameter）α 索引的樹序列。每一個 α 值都對應一個盡可能小的子樹 T⊂T_0。

這裏∣T∣代表樹 T 中葉結點的數量，R_m 代表第 m 個葉結點對應的矩形（預測器空間的子集），yhat_Rm 是 Rm 的預測值，即 Rm 中訓練樣本預測值的均值（或分類樹中的模式響應）。調整參數 α 控製子樹複雜度之間的權衡，對訓練數據進行擬合。當 α= 0 的時候，子樹 T 等同於 T_0。當α的值增長時，構建具備多個子結點的樹需要付出代價，這樣，要想得到更小的子樹，上述公式將達到最小化。我們可以使用某種交叉驗證方法選擇剪枝參數 α 。

注意，目前 sklearn.tree 決策樹分類器（和回歸器）不支持剪枝。

在統計學中，Bootstrap 是依靠替換隨機采樣的任意試驗或度量。我們從上文可以看見，決策樹會受到高方差的困擾。這意味著如果我們把訓練數據隨機分成兩部分，並且給二者都安置一個決策樹，我們得到的結果可能就會相當不同。Bootstrap 聚集，或者叫做袋裝，是減少統計學習方法的方差的通用過程。

給定一組 n 個獨立的樣本觀測值 Z_1，Z_2，...，Z_n，每一個值的方差均為 σ^*2，樣本觀測值的均值方差為 *σ^*2/*n。換句話說，對一組觀測值取平均會減小方差。因此一種減小方差的自然方式，也就是增加統計學習方法預測精度的方式，就是從總體中取出很多訓練集，使用每一個訓練集創建一個分離的預測模型，並且對預測結果求取平均值。

這裏有一個問題，即我們不能獲取多個訓練數據集。相反，我們可以通過從（單一）訓練數據集提取重複樣本進行自助法（bootstrap）操作。在這種方法中，我們生成了 B 個不同的自助訓練數據集。我們隨後在第 b 個自助訓練數據集得到了一個預測結果，從而獲得一個聚集預測（aggregate prediction）。

這就叫做袋裝（bagging）。注意，聚集（aggregating）在回歸和分類問題中可能有不同的均值。當平均預測值在回歸問題中的效果很好時，我們將會需要使用多數票決（majority vote）：由於分類問題中的聚集機製，整體預測就是在 B 個預測值中最常出現的那個主要類別。

Out-of-Bag（OOB）誤差

Bagging 方法最大的優勢是我們可以不通過交叉驗證而求得測試誤差。回想一下，Bagging 方法的精髓是多棵樹可以重複地擬合觀察樣本的自助子集。平均而言，每一個袋裝樹可以利用 2/3 的觀察樣本。而剩下的 1/3 觀察樣本就可以稱為 out-of-bag (OOB) 觀察樣本，它們並不會擬合一一棵給定袋裝樹。我們可以使用每一棵樹的 OOB 觀察樣本而計算第 i 個觀察樣本的預測值，這將會導致大約有 B/3 的預測值可以預測第 i 個觀察樣本。現在我們可以使用和 Bagging（平均回歸和大多數投票分類）類似的聚集技術，我們能獲得第 i 個觀察樣本的單一預測值。我們可以用這種方式獲得 n 個觀察樣本的 OOB 預測，因此總體的 OOB MSE（回歸問題）和分類誤差率（分類問題）就能計算出來。OOB 誤差結果是 Bagging 模型測試誤差的有效估計，因為每一個樣本的預測值都是僅僅使用不會進行擬合訓練模型的樣本。

特征重要性度量

通過使用單一樹，Bagging 通常會提升預測的精確度。但是，解釋最終的模型可能很困難。當我們袋裝大量的樹時，就不再可能使用單一的樹表征最終的統計學習流程，因此，Bagging 是以犧牲闡釋性能力為代價來提升預測精確度的。有趣的是，一個人可使用 RSS（用於 bagging 回歸樹）或者基尼指數（用於 bagging 分類樹）得到每一個預測器的整體總結。在 bagging 回歸樹的情況中，我們可以記錄由於所有的 B 樹上平均的給定預測分子分裂而造成的 RSS 減少的所有數量。一個大的值表示一個重要的預測器。相似地，在 bagging 分類樹的情況下，我們可以添加由於所有的 B 樹上平均的給定預測分子分裂而造成的基尼係數降低的所有數量。一旦訓練完成，sklearn 模塊的不同袋裝樹（bagged tree）學習方法可直接訪問特征的重要性數據作為屬性。

雖然袋裝技術（Bagging）通過降低方差而提高了一般決策樹的預測性能，但它還遇到了其他缺點：Bagging 要求我們在自助樣本上生成整棵樹，這就增加了 B 倍計算複雜度。此外，因為基於 Bagging 的樹是相關聯的，預測精度會根據 B 而飽和。

隨機森林通過隨機擾動而令所有的樹去相關，因此隨機森林要比 Bagging 性能更好。隨機森林不像 Bagging，在構建每一棵樹時，每一個結點分割前都是采用隨機樣本預測器。因為在核心思想上，隨機森林還是和 Bagging 樹一樣，因此其在方差上有所減少。此外，隨機森林可以考慮使用大量預測器，不僅因為這種方法減少了偏差，同時局部特征預測器在樹型結構中充當重要的決策。

隨機森林可以使用巨量的預測器，甚至預測器的數量比觀察樣本的數量還多。采用隨機森林方法最顯著的優勢是它能獲得更多的信息以減少擬合數值和估計分割的偏差。

通常我們會有一些預測器能主導決策樹的擬合過程，因為它們的平均性能始終要比其他一些競爭預測器更好。因此，其它許多對局部數據特征有用的預測器並不會選定作為分割變量。隨著隨機森林計算了足夠多的決策樹模型，每一個預測器都至少有幾次機會能成為定義分割的預測器。大多數情況下，我們不僅僅隻有主導預測器，特征預測器也有機會定義數據集的分割。

隨機森林有三個主要的超參數調整：

結點規模：隨機森林不像決策樹，每一棵樹葉結點所包含的觀察樣本數量可能十分少。該超參數的目標是生成樹的時候盡可能保持小偏差。
樹的數量：在實踐中選擇數百棵樹一般是比較好的選擇。
預測器采樣的數量：一般來說，如果我們一共有 D 個預測器，那麼我們可以在回歸任務中使用 D/3 個預測器數作為采樣數，在分類任務中使用 D^(1/2) 個預測器作為抽樣。

隨機森林模型案例

使用和上文一樣的收入數據，現在我們構建一個包含 500 棵樹的簡單隨機森林分類器模型：