淺析決策樹及其剪枝、集成方法

目錄

• 導讀
• brief introduction
  • information
  • details
• entropy
  • information gain
  • information gain-ratio
  • gini impurity
  • MSE/LSD
• pruning
  • pre-pruning
  • post-pruning
• value processing
  • continuous value$[4][9]$
  • missing value$[3][9]$
• ensemble model
  • bagging
  • boosting
• #reference links

導讀

決策樹作為機器學習十大演算法之一，具有易理解，可解釋性強，使用場景多（包括特征重要性）等，利用提升（Boosting）方法可以構建較好的基準線（baseline），但優化決策樹存在許多注意點，比如剪枝（pruning）方法的選擇，集成（ensemble）方法的取舍等；本文借鑒了多篇（目前是12篇）博客，包括towarscience、博客園、知乎、簡書、machinelearningmastery（強推）、高校ppt等資源，進行初步分析；
決策樹實際落地還有許多注意點（選擇、取舍等）、優化方法、數學原理等內容，本篇不做深入探討，另找時間出一篇更深入的博客，希望大家多提意見，一起進步呀，

brief introduction

information

? 決策樹（Decision Tree，以下簡稱DT），是簡單樹形結構（tree structure）的基于概率期望值（expected probability）的非線性分類器（nonlinear classifier）（分類超平面類似于折躍函式(folding function)\([1][2]\) ）;通過（在當前節點（node））不斷尋找資訊增益（information gain）最大的位置分割特征，生成并（使用分支（branch））連接子節點（leaf nodes）\([1]\) ，

? 其中需要學習三個資料值：樹形狀（structure learning）（深度和廣度）、決策閾值（decision threshold）、葉節點對應值（classifier results），（圖來源\([1 ]\)

? 多變數決策樹（Multivariate Decision Tree）\([3]\)，即使用特征線性組合進行特征分割，以達到“斜劃分”；，（圖來源\([3]\) ）

details

? 屬性：簡單但可解釋性（Interpretability）強，監督學習（supervised learning），非線性分類器（nonlinear classifier），樹結構（tree instructure），基于期望概率（expected probability）\([1]\)，基于分類資訊熵（information entropy）或回歸均方誤差（Mean Squares Error），不支持在線學習，

? 求解：分類樹：因為要使分類結果的各個葉節點中樣本盡可能屬于同一類，所以采用資訊混亂度衡量（即資訊熵），（類似于貪心演算法）每一次分割都使資訊熵增加最多；回歸樹：切分連續資料，損失函式為均方誤差，基于殘差資料擬合多個子樹，疊加得到回歸決策樹\([4]\)，

? 擴展：決策樹極易受到例外資料干擾進而過擬合：
? 1.采用剪枝（pruning）方法，包括預剪枝（prepruning）和后剪枝（post-pruning）\([3]\) ，方法有設定引數閾值、錯誤率降低剪枝（ Reduced-Error Pruning ， REP） 、悲觀錯誤剪枝（ Pessimistic Error Pruning， PEP） 、代價復雜度剪枝（ Cost-Complexity Pruning， CCP) \([4]\) ；
? 2.采用集成方法（ensemble methods），包括裝袋（bagging）和提升（boosting），方法有隨機森林(Random Forest)、梯度提升決策樹（ Gradient Boosting Decision Tree）等，

entropy

• 資訊熵：集合總體不確定性程度\([6 ]\)

  \[\begin{aligned} \H(X)=-\sum_{i=1}^nP_i\log_2{P_i} \end{aligned} \]

• 條件熵：已知某個資訊下，集合不確定性程度$[6 ] $

  \[\begin{aligned} \H(X|Y) &=\sum_{v\in values(Y)}P_{Y=v}\H({X|Y=v})\\ &=\sum_{v\in values(Y)}P_{Y=v}[-\sum_{i=1}^nP_{X=i,Y=v}\log_2{P_{X=i,Y=v}}]\\ \end{aligned} \]

• 延伸閱讀：卡方自動互動檢測（CHi-square Automatic Interaction Detection，CHAID），用于在分類樹計算時，執行多級分割；多元自適應回歸樣條（Multivariate Adaptive Regression Splines，MARS）\([12]\) ，

information gain

• 資訊增益：特征\(F\)對資料集\(D\)不確定性減少的程度（包括資訊熵和條件熵）

  \[\begin{aligned} {\cal{g}}(D,F)&= \H(D)-\H(D|F)\\ \end{aligned} \]

• 特點：偏好類別取值數量較多的特征（即類別取值數量更多的特征對集合的資訊增益更大）

  • 原因：（類別多，可能分類后集合熵更低，此時資訊增益更大，但可能出現分類過細而過擬合\([6 ]\)），可能出現的情況，難以通過公式推導證明；
  • 解決辦法：使用資訊增益率；

• 迭代二分法三（The Iterative Dichotomiser 3，ID3）使用

  • 優缺點：每次僅搜索空間一部分，速度快，測驗資料少，形式簡單（不分割特征值），深度小；但無法處理連續數值和缺失資料\([8]\) ；

information gain-ratio

• 資訊增益率：特征\(F\)對資料集\(D\)的資訊增益除以特征\(F\)的資訊熵（即注重有效資訊增益）

  \[\begin{aligned} {\cal{g_r}}(D,F)&= \]

  \end{aligned}

  \[ \]

  • 原因：（類別少，必然使分類后懲罰系數（即特征資訊熵）更小，此時資訊增益率更大，但可能出現分類粗糙而欠擬合\([6]\) ）
  • 解決辦法：先選擇資訊增益高于平均的部分，從中，再選擇資訊增益率最高的\([6][9]\) ；

• C4.5使用

  • 優缺點：支持對連續資料進行離散化（下面詳細討論），可以對缺失資料進行填充（下面詳細討論），K次迭代交叉驗證，可以使用剪枝方法；但速度較慢，計算復雜（多叉樹、對數運算、排序）\([8]\) ；

gini impurity

• 基尼不純度：從資料集 D 中隨機抽取一個樣本，其類別被錯分的概率 （數值等于隨機抽取兩個樣本，類別不一致的概率）\([4][9]\) ；

  \[\begin{aligned} {\cal{Gini}}(p) &=\sum_{k=1}^Kp_k(1-p_k)\\ &=1-\sum_{k=1}^Kp_k^2 \end{aligned} \]

• 特點：物理含義接近C4.5，更便于計算\([4]\)
  

• 分類與回歸樹（Classification And Regression Tree）分類時使用：

  • 優缺點：計算簡單，幾乎不需要預處理\([7]\)；需要生成多個決策樹（sequence of decision trees），使用代理特征分割（surrogate splits）時計算量爆表\([9]\)

MSE/LSD

• 均方誤差（Mean Squares Error，MSE）\([4]\) ： 計算每個序列間隔（序號：x.5，即兩個連續資料點的中間）拆分的子序列之最優輸出（均值），在計算最優輸出與真實資料間的平方誤差，迭代選擇最小MSE；最后融合多個子樹；

• 最小二乘偏差（Least Squares Diviation，LSD）\([7]\) ：在均方誤差首次計算后，迭代選擇最小LSD，減少計算量；

• 分類與回歸樹（Classification And Regression Tree）回歸時使用：

  • 優缺點：回歸中解釋性強，能回歸高度非線性；但因變數和自變數之間的關系無法很好逼近\([12]\) ，

pruning

機器學習筆記（6）——C4.5決策樹中的剪枝處理和Python實作，決策樹系列（二）——剪枝，決策樹的剪枝問題，

pre-pruning

• 可以有效提高泛化能力才進行下一步分割，減少計算；但容易產生“視界局限”，即會忽略下下一步（已被舍棄）\([2]\) ，且需要準備測驗集：
  • 資訊熵增最小閾值
  • 廣度/深度最大閾值
  • 葉節點最少樣本閾值
  • 性能提高最小閾值（常用）
• 留出法：留出部分資料作為測驗集，每一步分割，都比較測驗集在分割前后的精度，有性能提升則進行分割（即性能提高最小閾值為0%）\([3]\) ，

post-pruning

• 使樹充分生長，然后自底而上消除能提高泛化能力的子樹，克服“視界局限”；計算量大不適用于大資料量\([2]\) ，可以不需要測驗集：

  • 錯誤率降低剪枝（REP）
  • 悲觀錯誤剪枝（PEP）
  • 代價復雜度剪枝（CCP)

• 錯誤率降低剪枝（REP）：留出測驗集，自下而上比較測驗集在葉節點上下精度，有必要即洗掉（類似于預剪枝-留出法的反向）（用于ID3）\([11]\)

• 悲觀錯誤剪枝（PEP）：自上而下比較在節點上（帶懲罰項\(\epsilon\)，也是“悲觀”的原因）的錯誤率和標準誤差，如果樹錯誤率大于節點錯誤率-標準誤差，執行剪枝（用于C4.5）\([11][13]\) ；充分使用資料準確率高，但容易剪枝過度（自上而上的“視界局限”）甚至剪枝失敗，

  \[\begin{aligned} &E(n^+)\geq E(n)-S{\large(}E(n^+){\large)} \\ define: &E(n^+)=\sum_{i=1}^m(e_i+\epsilon)\\ &E(n)=e+\epsilon\\ &S{\large(}E(n^+){\large)} =\sqrt{np(1-p)}\\ &\epsilon=0.5, p:E(n^+)/n\\ &m：葉節點數量, n:總樣本數\\ &n^+:帶節點n的樹,n:節點n \\ \end{aligned} \]

• 代價復雜度剪枝（CCP)：計算全部節點的剪枝系數，回圈查找最小剪枝系數，從而獲得多個剪枝后的樹（決策樹序列\(T_k\)），交叉驗證選擇最優樹（用于CART）\([13]\) ；避免剪枝過度，但計算量較大，

  \[\begin{aligned} \alpha &=\frac{\R(t)-\R(T)}{m-1}\\ &=\frac{r_e(t)\cdot p_{all}(t)-\sum^m\R(T_i)}{m-1}\\ &=\frac{r_e(t)\cdot p_{all}(t)- \sum^mr_e(T_i)\cdot p_{all}(T_i)}{m-1}\\ define:\qquad &r_e(t):節點t錯分樣本在節點樣本占比\\ &p_{all}(t): 節點t樣本在全部樣本占比\\ &m：葉節點數量\\ &T_i:節點t為根的樹T的葉節點\\ \end{aligned} \]

value processing

continuous value\([4][9]\)

• 區間劃分（bi-partition）：特征\(F\in[a,d]\)，（啟發式方法）分割為多個空間\(F_1\in[a,b),F_2\in[b,c),F_3\in[c,d)\) （C4.5）；
• 取值劃分：特征\(F\)，取值\([1,2,3,4,5]\)，在取值間隙（如\([1,2,3]/[4,5]\)）劃分，且可連續劃分（即視為類別較多的離散值）（CART）；

missing value\([3][9]\)

• 缺失特征資訊增益率：在非缺失值上進行分裂，計算資訊增益率，然后根據非缺失值的占比在計算出來的資訊增益率前加入比值系數\([9 ]\)

  \[\begin{aligned} &g(D,F^+)=\frac{len(F^+)}{len(F)}g(D_F^+,F^+) \\ define:\qquad &F^+:特征中非缺失值\\ &D_F^+:集合中非缺失值集合\\ \end{aligned} \]

• 最優特征缺失：使用樣本權重將缺失值按照權重切分劃分到不同的節點中 \([9]\)

ensemble model

集成方法是重要演算法，與決策樹同一地位，后續會另開一篇續寫Bagging、Boosting（AdaBoost、XGBoost）等；

推薦閱讀：深度隨機森林（Deep Random Forest），作者周志華，3 Reasons to Use Random Forest Over a Neural Network–Comparing Machine Learning versus Deep Learning，DPP（determinant point process），Determinantal point processes for machine learning；

這些模型也是集成模型（想不到吧）

• dropout/dropconnect
• bayesian model
• denoising autoencoder

bagging

使用同一份樣本，有放回隨機采樣（bootstrap aggregating），并行構建K個模型，最后投票決定\([4]\) ；（單個模型擬合過強，容易過擬合）

\[\hat{P}(c|F)=\sum_1^nP_n(c|F) \]

• 隨機森林（Random Forest，RF）：（通過提高子集多樣性(diversity)）有效減少方差（variance reduction）（\(\frac{\sigma^2}{K}\)），降低錯誤風險，有效處理高維資料，處理缺失資料并保持準確性；但（回歸）取值無法精確；\([14]\)
  

boosting

使用均等分割的樣本，基于概率近似正確（Probability Approximatly Correct），逐步訓練K個模型，最終得到最終模型（\(f_K(x)=\sum_{m=1}^Kh_m(x)\)）\([4]\) ；（單個模型擬合過弱，容易欠擬合）Decision Tree vs Random Forest vs Gradient Boosting Machines: Explained Simply，Boosting and AdaBoost for Machine Learning；

• 梯度提升決策樹（Gradient Boosting Decision Tree，GBDT）（又叫Multiple Additive Regression Tree，MART）：以梯度下降的最速下降近似方法，即以損失函式負梯度擬合決策樹，此處是殘差（\(y-f_{i-1}(x)\)） \([4]\) ；

#reference links

[1].Stanford，課程：Data mining and analysis，Lecture 19: Decision trees；
[2].百度百科，決策樹；
[3].機器學習（西瓜書），作者：周志華，第四章第五節；
[4].貪心科技，課程：自然語言訓練營，回顧-決策樹；
[5].towardscience，作者：Anuja Nagpal，Decision Tree Ensembles- Bagging and Boosting;
[6].博客園，作者：張小呱，決策樹--資訊增益，資訊增益比，Geni指數的理解；
[7].towardscience，作者：Diego Lopez Yse，The Complete Guide to Decision Trees；
[8].新浪博客，作者：楊童，【周記2】C4.5演算法來源；
[9].知乎，作者：馬東什么，決策樹 ID3 C4.5 cart 總結；
[10].towardscience，作者：Lorraine Li， Classification and Regression Analysis with Decision Trees；
[11].博客園，作者：學會分享~，決策樹系列（二）——剪枝；
[12.].towardscience，作者：Nagesh Singh Chauhan：，Decision Tree Algorithm — Explained；
[13].博客園，作者：DreamFaquir，決策樹-剪枝演算法（二）；
[14].towardscience，作者：Neil Liberman，Decision Trees and Random Forests；

墻裂推薦： https://machinelearningmastery.com

標籤：其他

上一篇：深度學習權重初始化

下一篇：【學習篇】機器學習之模型評價