一、核心決策樹算法（3 類主流算法）

1. 1. ID3 算法：用 “信息增益” 選屬性

   ID3 是決策樹的 “開山鼻祖” 之一，它的核心邏輯是 “選能讓數據最‘純’的屬性”—— 這里的 “純” 用 “信息增益” 衡量。
   簡單說，“信息增益” 就是 “劃分前的混亂度（熵）減去劃分后的混亂度”，增益越大，說明用這個屬性劃分后，數據從 “雜亂無章” 到 “類別分明” 的提升越明顯。
   比如 PPT 里的例子：用 “天氣、溫度、濕度、是否多云” 這 4 個屬性，預測 “是否出去玩”。ID3 會計算每個屬性的信息增益，選增益最大的那個先劃分（比如先按 “天氣” 分，再按 “溫度” 分）。

   但 ID3 有個明顯的缺點：偏愛 “取值多的屬性”。比如如果數據里有 “編號” 這種每個樣本都不同的屬性，ID3 會覺得它的信息增益最大（畢竟每個編號對應一個樣本，劃分后完全 “純”），但這顯然沒意義 —— 相當于用 “身份證號” 做決策，對新數據毫無泛化能力。

   2. C4.5 算法：用 “信息增益率” 補坑

   為了修復 ID3 的 bug，C4.5 算法橫空出世。它在 “信息增益” 的基礎上，加了一個 “屬性自身的熵” 作為分母，得到 “信息增益率”。
   為什么這么做？因為取值多的屬性，自身的熵通常更大，除以它之后，就能平衡對 “多取值屬性” 的偏好。比如 “編號” 的信息增益高，但自身熵也極高，算出來的增益率反而可能很低，這樣就不會被誤選為劃分屬性了。

   PPT 里還是用 “是否出去玩” 的數據集，C4.5 會通過信息增益率，避開不合理的屬性，選出更有實際意義的劃分依據（比如優先選 “天氣”，而不是 “編號”）。

   3. CART 算法：用 “基尼指數” 兼顧分類與連續值

   CART 算法更靈活，它既能做分類，也能做回歸，這里我們先看分類場景。它用 “基尼指數” 衡量數據純度：基尼指數越小，說明數據越純（比如隨機從數據里抽兩個樣本，類別不一樣的概率越低）。

   最實用的是，CART 能處理 “連續值” 屬性 —— 比如 PPT 里的 “應稅收入”（125K、100K、70K…），它會用 “貪婪算法” 先給連續值排序，再找最優分界點（比如把 “應稅收入” 分成 “≤97.5K” 和 “>97.5K”），本質就是把連續值 “離散化”，再按分類邏輯劃分。這一點比 ID3 和 C4.5 更貼近真實數據（畢竟現實中很多特征是連續的，比如年齡、身高）。

二、決策樹剪枝策略（解決過擬合）

剪枝原因
決策樹理論上能完全分割數據，但易因 “過度貼合訓練數據” 導致過擬合，需通過剪枝降低復雜度、提升泛化能力。

1. 預剪枝：邊建邊剪，高效實用

預剪枝的思路很直接：在構建決策樹的過程中，就提前設定 “停止條件”，不讓樹長太 “胖”。
比如設定 “樹的最大深度不超過 10”“葉子節點至少有 5 個樣本才繼續劃分”“信息增益小于 0.1 就不劃分”—— 這些條件能從源頭限制樹的復雜度，避免過擬合。
預剪枝的優點是 “高效”，不用等樹建完再改；缺點是可能 “剪太狠”，導致欠擬合（樹太簡單，沒學到足夠的規律），所以參數需要反復調試。

2. 后剪枝：先建全樹，再 “砍枝”

后剪枝則是 “先把樹建完整，再回頭看哪些分支沒必要”。它的核心是 “計算損失”：
最終損失 = 分支自身的基尼系數（擬合效果） + α× 葉子節點數量（復雜度）
這里的 α 是 “平衡系數”：α 越大，越看重簡化樹（減少葉子節點），越能避免過擬合；α 越小，越看重擬合效果，可能保留更多分支。判斷是否剪枝的關鍵是 “驗證集精度”。
后剪枝的優點是 “效果更穩”，不容易欠擬合；缺點是 耗時

三、實踐