用于回歸任務的決策樹稱作回歸樹，屬性選擇與生長方式與分類決策樹不同。本文講解決策樹回歸算法的核心思想、啟發式切分、最優屬性選擇、過拟合、正則化、以及缺失值處理等關鍵知識點。
作者：韓信子@ShowMeAI
教程位址：https://www.showmeai.tech/tutorials/34
本文位址：https://www.showmeai.tech/article-detail/192
聲明：版權所有，轉載請聯系平台與作者并注明出處
引言
大家在前面的部分學習到了使用決策樹進行分類，實際決策樹也可以用作回歸任務，我們叫作回歸樹。而回歸樹的結構還是樹形結構，但是屬性選擇與生長方式和分類的決策樹有不同，我們一起來看看它的原理知識吧。
（本篇回歸樹模型部分内容涉及到機器學習基礎知識、決策樹算法，沒有先序知識儲備的寶寶可以檢視ShowMeAI的文章 [圖解機器學習 | 機器學習基礎知識]((https://www.showmeai.tech/article-detail/185) 及 決策樹模型詳解）。
1.決策樹回歸算法核心思想
1）決策樹結構回顧
我們一起來回顧一下決策樹的結構，決策樹的典型結構如下圖所示。
決策樹的學習過程和預測過程如下圖所示。詳細内容可以參考ShowMeAI的文章 決策樹模型詳解。
主流的決策樹算法有：
- ID3：基于資訊增益來選擇分裂屬性（每步選擇資訊增益最大的屬性作為分裂節點，樹可能是多叉的）。
- C4.5：基于資訊增益率來選擇分裂屬性（每步選擇資訊增益率最大的屬性作為分裂節點，樹可能是多叉的）。
- CART：基于基尼系數來建構決策樹（每步要求基尼系數最小，樹是二叉的）。
其中：CART樹全稱Classification And Regression Tree，即可以用于分類，也可以用于回歸，這裡指的回歸樹就是CART樹，ID3和C4.5不能用于回歸問題。
2）回歸樹的核心思想
要講回歸樹，我們一定會提到CART樹，CART樹全稱Classification And Regression Trees，包括分類樹與回歸樹。
CART的特點是：假設決策樹是二叉樹，内部結點特征的取值為「是」和「否」，右分支是取值為「是」的分支，左分支是取值為「否」的分支。這樣的決策樹等價于「遞歸地二分每個特征」，将輸入空間（特征空間）劃分為有限個單元，并在這些單元上确定預測的機率分布，也就是在輸入給定的條件下輸出的條件機率分布。
設有資料集 \(D\) ，建構回歸樹的大體思路如下：
- ①考慮資料集 \(D\) 上的所有特征 \(j\) ，周遊每一個特征下所有可能的取值或者切分點 \(s\) ，将資料集 \(D\) 劃分成兩部分 \(D_1\) 和 \(D_2\) 。
- ②分别計算 \(D_1\) 和 \(D_2\) 的平方誤差和，選擇最小的平方誤差對應的特征與分割點，生成兩個子節點（将資料劃分為兩部分）。
- ③對上述兩個子節點遞歸調用步驟①②，直到滿足停止條件。
回歸樹建構完成後，就完成了對整個輸入空間的劃分（即完成了回歸樹的建立）。将整個輸入空間劃分為多個子區域，每個子區域輸出為該區域内所有訓練樣本的平均值。
我們知道了回歸樹其實是将輸入空間劃分為M個單元，每個區域的輸出值是該區域内所有點y值的平均數。但我們希望建構最有效的回歸樹：預測值與真實值差異度最小。下面部分我們展開講講，回歸樹是如何生長的。
2.啟發式切分與最優屬性選擇
1）回歸樹模型示例
我們用一個經典的棒球案例來解釋回歸樹：根據從業年限和表現，去預估棒球運動員的工資。如下所示，有1987個資料樣本，包含322個棒球運動員。紅黃表示高收入，藍綠表示低收入。橫坐标是年限，縱坐标是表現。
這個簡單案例中，每個樣本資料有兩個特征：從業年限years和成績表現hits，回歸樹的決策過程由最終生成的回歸樹決定，如右圖所示：
- 根決策節點為特征Years，其劃分門檻值為4.5，Years小于4.5的樣本劃分到左邊，大于或等于4.5的樣本劃分到右邊；
- 第二個決策節點的特征為Hits，其劃分門檻值為117.5，Hits小于117.5的樣本劃分到左邊，大于或等于117.5的樣本劃分到右邊。
- 一個樣本順着決策樹的決策條件，走到葉子節點，即可獲得預測工資，這裡的預測工資總共就3種取值，分别為5.11、6.00、6.74。
我們來深入拆解和對應一下，其實回歸樹建構完成後，實作了對整個空間的劃分（如下圖所示）。實際預測時，新樣本會按照回歸樹的決策過程，被劃分到下圖 \(R_1\) 、 \(R_2\) 、 \(R_3\) 之中的一個區域 \(R_i\) ，而這個新樣本的預測值（本案例中為棒球運動員的工資）就是它所在的區域。
- \(R_i\) 中所有訓練樣本的工資平均值。
回歸樹背後的含義：對空間的劃分。整個平面被劃分成3部分：
- \(R1 = {X |Years < 4.5}\)
- \(R2 = {X |Years ≥ 4.5, Hits < 117.5}\)
- \(R3 = {X |Years ≥ 4.5, Hits ≥ 117.5}\)
2）回歸樹建構方法
下面切到回歸樹建構的核心：切分方式與屬性選擇。
假設一回歸問題，預估結果 \(y \in R\) ，特征向量為 \(X = [x_1,x_2,x_3, \dots , x_p ]\) ，回歸樹2個步驟是：
- ①把整個特征空間 \(X\) 切分成 \(J\) 個沒有重疊的區域 \(R_1,R_2,R_3, \dots ,R_J\)
- ②其中區域 \(R_J\) 中的每個樣本我們都給一樣的預測結果 \(\tilde{y}_{R_{j}}=\frac{1}{n} \sum j \in R j y_{j}\) ，其中 \(n\) 是 \(R_J\) 中的總樣本數。
仔細觀察一下上面的過程，實際上我們希望能找到如下的RSS最小的化劃分方式 \(R_1,R_2,R_3, \dots ,R_J\)
\[R S S=\sum_{j=1}^{J} \sum_{i \in R j}\left(y_{i}-\tilde{y}_{R_{j}}\right)^{2}
\]
- \(y\) ：為每個訓練樣本的标簽構成的标簽向量，向量中的每個元素 $y_j $ 對應的是每個樣本的标簽。
- \(X\) ：為特征的集合， \(x_1,x_2, \dots , x_p\) 為第1個特征到第 \(p\) 個特征。
- \(R_1,R_2,R_3, \dots ,R_J\) 為整個特征空間劃分得來的J個不重疊的區域（可以參考上頁的右圖）。
- \(\tilde{y}_{R_{j}}\) ：為劃分到第 \(j\) 個區域 $R_j $ 的樣本的平均标簽值，用這個值作為該區域的預測值，即如果有一個測試樣本在測試時落入到該區域，就将該樣本的标簽值預測為 \(\tilde{y}_{R_{j}}\) 。
但是這個最小化和探索的過程，計算量是非常非常大的。我們采用「探索式的遞歸二分」來嘗試解決這個問題。
遞歸二分
回歸樹采用的是「自頂向下的貪婪式遞歸方案」。這裡的貪婪，指的是每一次的劃分，隻考慮目前最優，而不回頭考慮之前的劃分。從數學上定義，即選擇切分的次元（特征） \(x_j\) 以及切分點 \(s\) 使得劃分後的樹RSS結果最小，公式如下所示：
\[\begin{aligned}
& R_{1}(j, s)=\left\{x \mid x_{j}<s\right\} \\
& R_{2}(j, s)=\left\{x \mid x_{j} \geq s\right\} \\
& RSS=\sum x_{i} \in R_{1}(j, s)\left(y_{i}-\tilde{y}_{R 1}\right)^{2}+\sum x_{i} \in R_{2}(j, s)\left(y_{i}-\tilde{y}_{R_{2}}\right)^{2}
\end{aligned}
\]
我們再來看看「遞歸切分」。下方有兩個對比圖，其中左圖是非遞歸方式切分得到的，而右圖是二分遞歸的方式切分得到的空間劃分結果（下一次劃分一定是在之前的劃分基礎上将某個區域一份為二）。
兩種方式的差别是：遞歸切分一定可以找到一個較優的解，非遞歸切分窮舉不了所有情況，算法上無法實作，可能無法得到一個較好的解。
回歸樹總體流程類似于分類樹：分枝時窮舉每一個特征可能的劃分門檻值，來尋找最優切分特征和最優切分點門檻值，衡量的方法是平方誤差最小化。分枝直到達到預設的終止條件（如葉子個數上限）就停止。
但通常在處理具體問題時，單一的回歸樹模型能力有限且有可能陷入過拟合，我們經常會利用內建學習中的Boosting思想，對回歸樹進行增強，得到的新模型就是提升樹（Boosting Decision Tree），進一步，可以得到梯度提升樹（Gradient Boosting Decision Tree，GBDT），再進一步可以更新到XGBoost。通過多棵回歸樹拟合殘差，不斷減小預測值與标簽值的偏差，進而達到精準預測的目的，ShowMeAI會在後面介紹這些進階算法。
3.過拟合與正則化
1）過拟合問題
決策樹模型存在過拟合風險，通常情況下，樹的規模太小會導緻模型效果不佳，而樹的規模太大就會造成過拟合，非常難以控制。
2）過拟合問題處理
對于決策樹，我們通常有如下一些政策可以用于環節過拟合：
（1）限制控制樹的過度生長
- 限制樹的深度：當達到設定好的最大深度時結束樹的生長。
- 分類誤差法：當樹繼續生長無法得到客觀的分類誤差減小，就停止生長。
- 葉子節點最小資料量限制：一個葉子節點的資料量過小，樹停止生長。
（2）剪枝
限制樹生長的缺點就是提前扼殺了其他可能性，過早地終止了樹的生長，我們也可以等待樹生長完成以後再進行剪枝，即所謂的後剪枝，而後剪枝算法主要有以下幾種：
- Reduced-Error Pruning（REP，錯誤率降低剪枝）。
- Pesimistic-Error Pruning（PEP，悲觀錯誤剪枝）。
- Cost-Complexity Pruning（CCP，代價複雜度剪枝）。
- Error-Based Pruning（EBP，基于錯誤的剪枝）。
3）正則化
對于回歸樹而言，在剪枝過程中我們會添加正則化項衡量。如下所示，考慮剪枝後得到的子樹 \(\left \{T_a \right \}\) ，其中 \(\alpha\) 是正則化項的系數。當固定住 \(\alpha\) 之後，最佳的 \(T_a\) 就是使得下列式子值最小的子樹。
\[\sum_{m=1}^{|T|} \sum_{x_{i} \in R_{m}}\left(y_{i}-\tilde{y}_{R_{2}}\right)^{2}+\alpha|T|
\]
- \(|T|\) 是回歸樹葉子節點的個數。
- \(\alpha\) 可以通過交叉驗證去選擇。
更多監督學習的算法模型總結可以檢視ShowMeAI的文章 AI知識技能速查 | 機器學習-監督學習。
視訊教程
可以點選 B站 檢視視訊的【雙語字幕】版本
[video(video-ZbsrqzXo-1646894886536)(type-bilibili)(url-https://player.bilibili.com/player.html?aid=975327190&page=12)(image-https://img-blog.csdnimg.cn/img_convert/37b2b4180b9b5bc976b1b07042a42a3c.png)(title-【雙語字幕+資料下載下傳】MIT 6.036 | 機器學習導論(2020·完整版))]
【雙語字幕+資料下載下傳】MIT 6.036 | 機器學習導論(2020·完整版)
https://www.bilibili.com/video/BV1y44y187wN?p=12
機器學習【算法】系列教程
- 圖解機器學習 | 機器學習基礎知識
- 圖解機器學習 | 模型評估方法與準則
- 圖解機器學習 | KNN算法及其應用
- 圖解機器學習 | 邏輯回歸算法詳解
- 圖解機器學習 | 樸素貝葉斯算法詳解
- 圖解機器學習 | 決策樹模型詳解
- 圖解機器學習 | 随機森林分類模型詳解
- 圖解機器學習 | 回歸樹模型詳解
- 圖解機器學習 | GBDT模型詳解
- 圖解機器學習 | XGBoost模型最全解析
- 圖解機器學習 | LightGBM模型詳解
- 圖解機器學習 | 支援向量機模型詳解
- 圖解機器學習 | 聚類算法詳解
- 圖解機器學習 | PCA降維算法詳解
機器學習【實戰】系列教程
- 機器學習實戰 | Python機器學習算法應用實踐
- 機器學習實戰 | SKLearn入門與簡單應用案例
- 機器學習實戰 | SKLearn最全應用指南
- 機器學習實戰 | XGBoost模組化應用詳解
- 機器學習實戰 | LightGBM模組化應用詳解
- 機器學習實戰 | Python機器學習綜合項目-電商銷量預估
- 機器學習實戰 | Python機器學習綜合項目-電商銷量預估<進階方案>
- 機器學習實戰 | 機器學習特征工程最全解讀
- 機器學習實戰 | 自動化特征工程工具Featuretools應用
- 機器學習實戰 | AutoML自動化機器學習模組化
ShowMeAI系列教程推薦
- 大廠技術實作方案系列
- 圖解Python程式設計：從入門到精通系列教程
- 圖解資料分析：從入門到精通系列教程
- 圖解AI數學基礎：從入門到精通系列教程
- 圖解大資料技術：從入門到精通系列教程
- 圖解機器學習算法：從入門到精通系列教程
- 機器學習實戰：手把手教你玩轉機器學習系列
- 深度學習教程：吳恩達專項課程 · 全套筆記解讀
- 自然語言處理教程：斯坦福CS224n課程 · 課程帶學與全套筆記解讀
- 深度學習與計算機視覺教程：斯坦福CS231n · 全套筆記解讀