- 決策樹透過遞歸分裂來模擬預測，選擇遞歸分裂以最大限度地減少雜質，使用基尼係數、熵或變異數等指標。
- 資訊增益指導每個節點特徵和閾值的選擇，使決策樹能夠同時處理回歸和分類。
- 超參數 max_depth、min_samples_split 和 min_information_gain 控制過擬合和樹的複雜度。
- 在學習隨機森林等整合學習方法（這些方法可以穩定和提高效能）之前，理解單樹演算法的機制至關重要。
從零開始建立決策樹回歸模型是讓你真正了解基於樹的模型如何思考以及它們為什麼在機器學習中如此流行的最令人大開眼界的練習之一。 您將不再把樹當作一個神秘的黑盒子，而是看到每次分裂是如何選擇的，雜質是如何測量的，以及在葉子節點上是如何產生數值預測的，無論是回歸問題還是分類問題。
在本指南中，我們將介紹決策樹背後的核心思想、它們使用的成本函數、它們如何搜尋最佳分割，以及如何僅使用循環、條件和簡單統計等基本概念來編寫支援回歸和分類的基本決策樹。 在此過程中，我們將比較回歸樹和分類樹，將理論與 Python 和 R 等工具中的實際實現聯繫起來（例如使用 rpart 和 tree），並簡要地將決策樹置於隨機森林等更大的整合模型中。
什麼是決策樹？為什麼它如此直觀易懂？
決策樹本質上是一系列是非問題（或簡單規則）的流程，它引導你從根節點決策到葉節點的最終預測。 在典型的監督式學習環境中，目標是預測目標變數。 Y 使用多個預測因子（特徵、協變量），決策樹學習一系列問題，例如“體重是否≤103？”或“國家是否屬於{美國、英國、加拿大}？”，從而逐步將數據劃分為更同質的組。
為了便於理解，假設你想只根據身高和體重來預測某人是否肥胖，並且你有一個標記的資料集，告訴你誰肥胖，誰不肥胖。 樹狀圖可能會發現一條規則，例如“體重超過100公斤，預測為肥胖”，但這條規則並不完美：有些體重超過100公斤的人並不肥胖，而有些體重低於100公斤的人卻肥胖。因此，樹狀圖會不斷添加更多問題（子分支），例如關於身高或更精確的體重閾值，以「微調」最初的粗略預測。
樹中的每個內部節點對應於一個決策規則，每個分支對應於該規則的一個結果，每個葉節點對應於特徵空間中預測結果恆定的區域。 在分類中，葉節點傳回類別標籤（或標籤的機率分佈）；在迴歸中，葉節點通常會傳回落入該區域的目標值的平均值。
決策樹的主要優勢之一是它們能夠自然地處理回歸和分類，易於解釋，並且無需大量預處理即可處理定量和定性（分類）預測因子。 你不需要對特徵或目標進行任何特定的分佈假設，這使得決策樹在現實世界中非常有吸引力，因為在現實世界中，經典的線性假設往往不成立。
分類樹與迴歸樹
雖然分類樹和迴歸樹的結構相同，但反應變數 Y 的性質和用於分裂的成本函數在這兩種類型之間有所不同。 當 Y 是定量變數（例如，銷售額、預期壽命、燃料消耗量）時，我們稱之為迴歸樹；當 Y 是定性變數或分類變數（例如，存活與否、肥胖與否）時，我們稱之為分類樹。
在迴歸樹中，通常的目標是將特徵空間劃分為若干區域，在這些區域中，反應可以用一個常數來近似，該常數通常是該區域中觀測值的平均值。 典型的決策規則形式為「是 x」。k ≤ c?”，其中 xk 其中，是協變數之一，c 是閾值；這些規則反覆將空間分割成超矩形，同一超矩形中的所有點都共享相同的預測值 ŷ。
在分類樹中，分裂仍然是“特徵≤閾值？”或“類別在集合S中？”，但分裂的品質是通過所得子節點在類別標籤方面的純度來衡量的。 葉節點預測通常是該節點內的多數類，模型會嘗試建立盡可能只包含單一類別的葉節點。
儘管目標類型存在這些差異，但從編碼的角度來看，您可以實現一個通用的樹狀結構，並根據您是進行回歸還是分類，簡單地插入不同的不純度或損失度量。 稍後，當我們計算資訊增益時，你會發現分類（基於熵）和迴歸（基於變異數）的公式在本質上是相似的。
決策樹中的雜質和成本函數
任何決策樹演算法的核心都是一個成本函數，它評估特定分割方式將資料分成有意義的群組的效果如何。 這個成本函數以不純度來表示：如果一個節點的所有樣本都屬於同一類（對於分類）或具有幾乎相同的數值（對於迴歸），則該節點被認為是純的。
每當您選擇特徵上的候選分割時，演算法都會查看它生成的子節點，並詢問：“每個子節點中的標籤（或值）混合程度如何？” 好的拆分是指產生的子節點比父節點純淨得多，這意味著每個子節點中的資料相對於目標節點而言更加同質。
在分類樹中，不純度通常用基尼指數或熵等標準來衡量，兩者都反映瞭如果我們簡單地預測多數類，那麼在該節點中隨機選擇的觀測值被錯誤分類的可能性有多大。 在迴歸樹中，不純度通常以平方誤差或變異數來衡量，反映了目標值在節點內的分散程度。
基尼指數：衡量分類樹中的雜質
基尼指數是分類樹中最常用的不純度測量之一，因為它計算簡單，而且在實踐中效果很好。 從概念上講，它衡量的是根據該節點中的標籤分佈來預測標籤時，從該節點中隨機選擇的觀測值被錯誤分類的機率。
如果一個節點包含機率為 P 的類別。1，P2，…，Pn基尼係數的計算公式為：基尼係數 = 1 − Σ (Pi)². 當一個節點完全純淨（所有觀測值都屬於同一類）時，其中一個機率為 1，其餘機率為 0，因此平方和為 1，基尼指數為 0，表示完全純淨。
另一方面，當節點內的類別均勻混合時，基尼指數達到最大值，例如在 P 為 1 的二元問題中。1 = P.2 = 0.5，由此得出基尼係數 = 1 − (0.5² + 0.5²) = 0.5。 在這種情況下，預測多數類別是你能得到的最糟糕的結果，因為節點包含了每個類別的一半。
在程式碼中實作基尼係數時，通常會取得節點的標籤向量，計算每個類別的頻率，將頻率轉換為機率，然後套用公式 1 − Σ p²。 如果對多個候選分割點進行此操作，則可以比較哪個分割點產生的子節點具有較低的加權平均基尼不純度，這正是決策樹決定最佳分割點所需要的。
熵：雜質分類的另一種視角
熵是資訊理論和早期樹演算法（如 ID3 和 C4.5）中廣泛使用的另一種雜質度量，它反映了節點類別分佈中的隨機性或不確定性。 基尼係數著重於誤分類機率，而熵則量化了在分佈混合的情況下觀察到特定類別所帶來的「意外性」。
給定類別機率 p1，…，pc 對於節點 S，其熵定義為 E(S) = − Σ pi log₂(pi). 如果節點是純節點，則其中一個機率為 1，其餘機率均為 0，因此總和為零（因為 log₂(1) = 0），所以熵為 0，表示沒有不確定性。
當節點包含均勻分佈的類別時，熵最大；對於 p 值較大的二元問題，熵最大。1 =p2 = 0.5，熵為 1 比特，這是兩個類別可能的最大值。 該值對應於最大不確定性，意味著該節點在該分佈下純度最低。
儘管基尼係數和熵使用不同的公式，數值範圍也不同（基尼係數在 0 到 0.5 之間，對應兩個類別；熵在 0 到 1 之間），但兩者本質上衡量的是相同的概念，因此在實踐中通常會產生非常相似的決策樹。 當你在同一節點上計算兩者時，你會發現高基尼係數對應於高熵，反之亦然，這就是為什麼許多函式庫允許你選擇其中一個而不會大幅改變效能的原因。
資訊增益和選擇最佳分割
為了從眾多候選方案中選擇最佳分割方案，樹演算法使用稱為資訊增益的指標，該指標衡量將節點分割成其子節點時雜質減少的程度。 直觀地說，如果子代比父代純淨得多，則拆分具有較高的資訊增益，這意味著該規則成功地將資料分成更有意義的群組。
對於使用熵的分類樹，分裂的資訊增益定義為IG分類 = E(parent) − Σ (|S孩子| / |S親|) · E(S孩子). 首先計算父節點的熵，然後減去子節點的加權平均熵，其中權重是子節點的相對大小。
對於迴歸樹，類似的概念使用方差或均方誤差作為不純度度量，從而得到IG。回歸 = Var(parent) − Σ (|S孩子| / |S親|) · Var(S孩子). 在這種情況下，好的分割方式是指能夠大幅降低每個子代目標值變異性的分割方式。
樹訓練演算法會評估每個特徵上每個可能的候選分割的資訊增益，然後選擇增益最高的分割，前提是它超過某個最小閾值，以避免產生無用的微小改進。 然後，對每個子節點遞歸地重複此過程，直到達到某些停止條件為止。
如何找到每個特徵的最佳分割點
找到單一特徵的最佳分割取決於該特徵是數值型還是類別型，但其基本想法始終相同：枚舉候選分割併計算其資訊增益。 對於數值特徵，劃分是透過閾值定義的；對於類別特徵，劃分是透過將層級分組為子集來定義的。
對於數值預測器，通常的策略是查看該特徵在目前節點中取到的所有唯一值，並對它們進行排序，然後考慮連續值之間的候選閾值。 對於每個候選閾值 c，您建立兩個組（x ≤ c 和 x > c），計算每個組的不純度，然後計算資訊增益；產生最高增益的閾值是該特徵的最佳數值分割。
當處理分類預測變數時，搜尋空間更加複雜，因為原則上，任何類別的子集都可以構成分割的一側，而其補集則構成另一側。 對於具有 K 個類別的特徵，存在許多可能的子集（2）。K−1 − 1 個非平凡的劃分），因此在實踐中，實作通常會限制這種搜尋或使用啟發式方法，尤其是在 K 很大的時候。
計算出每個特徵的最佳分割後，比較它們的資訊增益，並選擇增益最大的特徵和閾值（或類別子集）。 選定的分割結果成為目前節點的決策，然後訓練過程會遞歸地對每個子節點及其對應的觀測子集進行。
利用超參數控制樹的生長
如果允許決策樹在沒有任何約束的情況下生長，它將不斷分裂，直到每個葉子要么完全純淨，要么只包含極少的觀測值，這幾乎總是會導致嚴重的過度擬合（過度擬合與欠擬合). 為了避免這種情況，您可以設定一組超參數來控制樹的深度和複雜性。
一個常見的超參數是 max_depth，它限制了樹從根到任何葉子可以生長的最大層數。 如果 max_depth 設定為 None（或非常大的數字），只要滿足其他約束條件，樹就可以繼續增長；如果 max_depth 較小，樹將保持較淺且更易於解釋，但可能擬合不足。
另一個關鍵超參數是 min_samples_split，它指定節點在被允許分裂之前必須包含的最小觀測值數量。 如果一個節點的樣本數少於此閾值，則將其轉換為葉節點，防止模型在非常小的資料子集中追逐雜訊。
您也可以強制執行最小資訊增益 (min_information_gain)，以便演算法僅在分裂能夠顯著降低雜質含量時才執行分裂。 這樣可以避免創建不必要的分支，這些分支幾乎不會改變預測結果，只會使樹結構複雜化。
用程式碼從頭開始建立決策樹
從頭開始實作決策樹通常圍繞著一組遞歸呼叫的核心函數。 雖然像 scikit-learn 或 rpart 這樣的函式庫會在底層完成所有這些操作，但自己編寫這些步驟的程式碼會讓邏輯更加清晰（程式設計邏輯）並讓你完全控制該行為。
首先，你需要一個例程，給定節點上的當前數據，評估每個特徵和每個候選分割，以找到資訊增益最高的分割。 此函數傳回所選特徵、分割規則（閾值或類別子集）、增益值以及用於標識哪些樣本移至左側、哪些樣本移至右側的布林遮罩或索引集。
其次，你需要一個葉節點預測函數，該函數將該節點中的一組目標值轉換為單一預測值。 對於迴歸，這通常是該節點中 y 的平均值；對於分類，通常取眾數（最頻繁出現的類別），如果需要機率輸出，可能還會儲存類別機率。
第三，建立一個遞歸訓練函數，該函數檢查停止標準，如果允許則搜尋最佳分割，然後透過在左右子集上呼叫自身來建立子節點。 如果最小樣本量、最大深度或最小增益條件未滿足，則函數停止分裂並儲存葉節點預測，而不是進一步的分支。
訓練好的決策樹如何進行預測
一旦樹經過訓練並儲存了所有分裂規則和葉子預測，對新觀測值進行預測就只需從樹的根部向下走到葉子即可。 在每個內部節點，檢查所需的特徵，並測試觀察結果是否滿足節點的條件。
如果分割規則是數值型的，則檢查特徵值是否小於或等於閾值；如果分割規則是類別型的，則檢查類別是否屬於特定子集。 根據結果，你沿著相應的分支（例如，「是」走左邊，「否」走右邊）並在下一個節點重複此過程。
你繼續向下遍歷樹，直到你到達一個沒有子節點的節點，這是一個葉子節點，它儲存著一個常數輸出值或一個類別標籤。 對於迴歸樹，預測結果將是一個數字，例如估計的預期壽命或燃料效率；對於分類樹，輸出結果將是一個預測類別，例如「倖存」或「未倖存」。
如果你用與訓練相同的數據測試這種方法，你通常會看到分類準確率相當高（例如，在一些簡單的肥胖或泰坦尼克號式的例子中，準確率約為 85%），但如果你的樹太深，那麼在未見過的數據上，性能可能會下降。 正因如此，控制樹的深度和大小如此重要，而像隨機森林這樣的整合學習方法被發明出來，是為了穩定樹的預測結果。
回歸樹的實際應用
當預測變數與反應變數之間的關係是強非線性的，並且涉及難以用經典線性迴歸建模的交互作用時，迴歸樹就顯得特別有用。 此樹狀圖並非嘗試擬合單一的全域方程，而是將特徵空間劃分為多個區域，並在每個區域內擬合一個簡單的常數模型。
在 R 語言中，流行的套件如 rpart 和 tree 使得透過一次函數呼叫即可輕鬆建立回歸樹，並指定類似 y ~ x1 + x2 + … + x11 的公式。 這些軟體包受到了 Breiman 及其同事描述的原始 CART 方法的影響，並實現了現代基於樹的建模中標準的許多分裂和修剪思想。
例如，您可以使用 rpart 套件對基於 11 個協變數 x1 到 x11 的回應 y 進行建模，清理缺失值的數據，然後使用 rpart.plot 套件中的 prp 等輔助函數視覺化產生的樹。 終端節點顯示每個區域的預測 y 值，您可以直接將其用於新的觀測。
給定一個訓練好的迴歸樹，您可以將新的協變數值（例如 x9 = 70，x2 = 100 或 x9 = 60，x2 = 150）輸入到預測函數中，以獲得估計值 ŷ（例如，在燃料消耗範例中約為 20 或 28）。 將這些預測值與觀測值進行比較，例如透過 y 和 ŷ 之間的相關性，可以讓你快速了解樹捕捉潛在模式的程度，即使資料集相當小。
從單棵樹到隨機森林
單一決策樹功能強大，但同時也對訓練資料的特殊性非常敏感，這可能導致高方差（偏差和方差）和過擬合。 為了緩解這個問題，隨機森林基於數據的自舉樣本構建許多樹，並聚合它們的預測結果，從而產生更穩定且通常更準確的模型。
在隨機森林中，每棵樹都是基於自助樣本進行訓練的，這意味著從原始訓練集中有放回地抽取一個相同大小的新資料集。 這種抽樣過程使得每棵樹看到的資料集略有不同，因此它們的誤差相關性較小，並且在聚合時可以相互抵消。
此外，隨機森林透過在每次分裂時只考慮預測變量的隨機子集而不是所有預測變量，在特徵選擇過程中引入了隨機性。 這進一步降低了樹木之間的相關性，增強了森林的多樣性，並且傾向於在不增加過多偏差的情況下減少變異數。
將自助法和預測聚合相結合稱為 bagging，在隨機森林中，還可以透過評估每棵樹在其自助樣本中未包含的資料點（所謂的袋外觀測值）來獲得模型誤差的內部估計。 這種袋外誤差提供了一種便捷的方法來衡量性能，而無需單獨的驗證集。
雖然本文重點在於從頭開始構建一棵樹，但了解這一基本組件的工作原理，可以更容易地理解隨機森林、梯度提升和其他基於樹的方法等集成方法是如何基於相同的原理，在許多應用問題中取得最先進的結果的。
綜合來看，從零開始的決策樹回歸向您展示瞭如何透過一組簡單的規則、成本函數和遞歸分割來模擬複雜的關係，無論您是預測生存等二元結果、肥胖狀況等分類標籤，還是預期壽命或燃料消耗等數值目標，這種深刻的理解都為在實踐中使用更高級的基於樹的技術奠定了堅實的基礎。
