04 · 决策树与集成学习

⏱ 52 分钟 ｜ ⭐⭐ 表格数据的王者，Kaggle 板块的地基

🎯 一句话

一棵树很弱（第 1 章那个 91.8%），但把几百棵弱树按正确方式组合起来，就是表格数据上至今难以撼动的最强模型——XGBoost / LightGBM 的全部秘密就在这。

📍 这一章的链是：怎么切一刀（ID3 → C4.5 → CART）→ 怎么把树组合起来（Bagging / Boosting / Stacking）→ GBDT 每棵新树到底在学什么。 链的最后一环——「怎么把『下一棵树该怎么长』写成一个能求闭式解的目标函数」——单独放在 04b · XGBoost 的推导，读完这一章再去。

🌲 一、决策树：一堆 if-else

                  worst perimeter <= 106?
                    ╱                ╲
                  是                  否
                  ╱                    ╲
      worst concave pts <= 0.14?      恶性 (95%)
          ╱          ╲
        是            否
        ╱              ╲
    良性 (98%)      恶性 (80%)

💡 它就是在特征空间里切方块：每次沿着某个特征切一刀，把数据分成两半。

怎么决定「切哪个特征、切在哪」

贪心：试遍所有特征的所有切分点，选让子节点最"纯"的那个。

「纯度」的两种度量：

💡 人话：

切一刀之前左右混在一起（不纯），切完之后左边基本都是良性、右边基本都是恶性（纯）。 纯度提升最多的那一刀，就是最好的切法。 两个指标实践中差别很小，用默认的基尼就行。

关键特性

控制过拟合的四个旋钮：max_depth（最常用）、min_samples_leaf、min_samples_split、max_leaf_nodes

🪓 二、分裂准则的演进：ID3 → C4.5 → CART

上一节说「选让子节点最纯的那一刀」。但「纯」到底怎么量，历史上换过三代。这条演进线不只是考点——GBDT / XGBoost / LightGBM 家族的每一棵树都长在第三代（CART）上面，不搞清楚它，后面几节会变成背结论。

① ID3：信息增益

$$\text{Gain}(D,a) = H(D) - \sum_{v} \frac{|D^v|}{|D|}\, H(D^v)$$

💡 人话：熵 $H$ 是「你还有多不确定」。切一刀，不确定性掉了多少；掉得最多的那一刀就选它。

⚠️ 但它有一个致命偏好：一个特征的取值越多，信息增益天然越大。

举个能算的例子。20 个样本，10 正 10 负，所以 $H(D)=1$ bit：

ID3 会毫不犹豫地选用户 ID，而这棵树在新用户身上一个都答不出来——它把这 20 个样本背下来了。

② C4.5：信息增益率——除以「这个特征自己有多碎」

C4.5 的补丁很直接：给切得太碎的特征加罚分。

$$\text{GainRatio}(D,a)=\frac{\text{Gain}(D,a)}{IV(a)},\qquad IV(a)=-\sum_v \frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$$

💡 IV（固有值 / intrinsic value）到底是什么：把「样本落进了哪个分支」本身当成一个随机变量，算它的熵。⭐ 注意 IV 和标签 $y$ 一点关系都没有，它纯粹度量「这一刀切得多碎、多均匀」。切成越多份、越均匀，IV 越大。

接着上面的数算：

换了判据，A 就赢了。 这就是「为什么要除以固有值」的全部答案：分子奖励「分得准」，分母惩罚「分得碎」。

⚠️ 但增益率又矫枉过正了——它反过来偏爱取值少的特征。所以 C4.5 实际用的是两步启发式：先筛出信息增益高于平均水平的候选，再在这一批里挑增益率最高的。（面试能说出「C4.5 不是单纯用增益率」是加分项。）

C4.5 相比 ID3 还多做了三件事：能处理连续特征（排序后取相邻取值的中点当候选切分点）、能处理缺失值（按各分支的样本比例，把缺失样本带权重分到每一支）、有后剪枝。

③ CART：基尼系数——把 log 换成乘法

$$\text{Gini}(D)=1-\sum_k p_k^2$$

为什么更快：熵要算 $\log$，基尼只要乘法和减法。一棵树训练时要算几十万次纯度，这个常数差是实打实的。

为什么可以这么换：把 $-\ln p$ 在 $p=1$ 处做一阶泰勒展开得到 $-\ln p \approx 1-p$，代回熵的定义就成了 $\sum_k p_k(1-p_k)=1-\sum_k p_k^2$。⭐ 基尼就是熵的一阶近似——两条曲线形状几乎重合（二分类下 $p=0.5$ 时熵取最大值 1 bit、基尼取最大值 0.5，最大值在同一点），所以实践中选哪个对结果几乎没影响。

⚠️ 很多人搞错的一点：基尼并没有解决「偏好多值特征」。 还是上面那组数——A 的基尼下降是 0.32，用户 ID 的基尼下降是 0.50，基尼照样选用户 ID。这个毛病是所有「增益类判据」共有的，不是熵独有的。

CART 的解法不是换判据，是换结构：

• ⭐ CART 永远只长二叉树。 哪怕特征有 20 个取值，一次也只能切成「属于某个子集 / 不属于」两支，不允许一刀切成 20 份——「切得太碎」这条路被结构堵死了。
• 再配 min_samples_leaf 和代价复杂度剪枝，把剩下的风险压住。

⚠️ 这就是本章后面那个「特征重要性偏向高基数特征」的坑的根： CART 只是把病压住了，没治好。取值多的特征仍然有更多候选切分点可以试，仍然更容易被选中。

三代对比

🔑 最后一行是本节通向后面所有内容的接口： ⭐ Boosting 家族里的每一棵树都是 CART 回归树。 因为每棵新树要拟合的是「负梯度」——那是一串连续实数，不是类别标签。 ID3 和 C4.5 只会分类，从一开始就没有资格进这个家族；sklearn 里也只实现了 CART。

🌳 三、集成学习：三种组合方式

单棵树不稳定又易过拟合。把很多棵组合起来——但怎么组合，分成三条完全不同的路线：

🔗 Kaggle 第 3 章模型融合 讲的就是 ③ 的各种实战技巧。

🌲 四、随机森林：Bagging + 双重随机

   随机 1：每棵树用【有放回抽样】的数据（Bootstrap）
   随机 2：每次分裂只从【随机选的 k 个特征】里挑 ⭐ 关键

   为什么要第二个随机？
   → 否则每棵树都会先用那个最强特征分裂 → 树长得都一样 → 平均了也没用
   → 强制它们看不同的特征，才能真正"多样"

💡 核心直觉：集成的收益来自成员之间的「差异」。全都一样的树，平均一百次还是那棵树。

优点：几乎不用调参、不易过拟合、能给特征重要性、可并行 缺点：精度通常略输 Boosting、模型体积大

🚀 五、GBDT：Boosting 的核心思想

这是本章最重要的部分——Kaggle 的主力算法。

它在做什么

   目标：预测房价，真实值 100 万

   树1 预测 → 80万        残差(还差) = 20万
   树2 专门学「怎么预测这 20 万」→ 预测 15万   残差 = 5万
   树3 专门学这 5 万 → 预测 4万                残差 = 1万
   ...
   最终预测 = 80 + 15 + 4 + ... = 逼近 100万 ✅

💡 人话：

每棵新树不预测答案本身，而是预测「前面所有树加起来还差多少」。 像考试订正错题：第一遍做完，专门针对错的部分再学一遍，反复迭代。

数学上：每棵新树拟合的是损失函数的负梯度（所以叫「梯度」提升）。 用 MSE 损失时，负梯度恰好就是残差——上面那个直觉是严格成立的。

三个关键超参（调参时主要动这三个）

🔑 最重要的一条调参直觉： learning_rate 和 n_estimators 是一对——学习率减半，树的数量大致要翻倍。 先固定 lr=0.1 调其他参数，最后再降 lr、加树数换取最后那点精度。

为什么 GBDT 的树要浅？

   随机森林：每棵树都想【独立解决问题】→ 要深（完全生长）
   GBDT：   每棵树只需【纠正一点点错误】→ 要浅（深度 3-8）

   GBDT 用浅树是故意的：单棵弱一点，才不会一步跨太大而过拟合

🚪 这里有一句话故意没讲完

「每棵新树拟合负梯度」——⭐ 负梯度只告诉你往哪个方向走，没告诉你该走多远。 GBDT 用 learning_rate 把步子统一压小，是绕开这个问题而不是解决它。

👉 04b · XGBoost 的推导：从负梯度到闭式解 该去的时候：要面试（「XGBoost 为什么用二阶泰勒展开」是必考）、要自定义损失函数、或者想知道 LightGBM 凭什么快、CatBoost 在防什么。 可以先不去的时候：只想会调参把分刷上去 —— 直接跳 Kaggle 第 1 章，那里有现成模板。 ⚠️ 但三巨头对比表在 04b，而且在那里它是推出来的不是背的。

🔨 动手：亲眼看集成的威力

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import (RandomForestClassifier,
                              GradientBoostingClassifier, BaggingClassifier)
import numpy as np

X, y = load_breast_cancer(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3,
                                          random_state=42, stratify=y)

print(f"{'模型':<22}{'训练集':>9}{'测试集':>9}")
for name, m in [
    ("单棵决策树",        DecisionTreeClassifier(random_state=0)),
    ("Bagging(100棵)",   BaggingClassifier(n_estimators=100, random_state=0)),
    ("随机森林(100棵)",   RandomForestClassifier(n_estimators=100, random_state=0)),
    ("GBDT(100棵,深度3)", GradientBoostingClassifier(n_estimators=100,
                                                    max_depth=3, random_state=0)),
]:
    m.fit(X_tr, y_tr)
    print(f"{name:<22}{m.score(X_tr,y_tr):>8.1%}{m.score(X_te,y_te):>9.1%}")

print("\nGBDT：学习率与树数量的配合")
print(f"{'树数':<8}{'学习率':<10}{'测试集':>9}")
for n, lr in [(10,0.1),(50,0.1),(200,0.1),(500,0.1),(500,0.01)]:
    m = GradientBoostingClassifier(n_estimators=n, learning_rate=lr,
                                   max_depth=3, random_state=0).fit(X_tr, y_tr)
    print(f"{n:<8}{lr:<10}{m.score(X_te,y_te):>8.1%}")

print("\n特征重要性 Top5：")
rf = RandomForestClassifier(n_estimators=200, random_state=0).fit(X_tr, y_tr)
names = load_breast_cancer().feature_names
for i in np.argsort(-rf.feature_importances_)[:5]:
    print(f"  {names[i]:<25} {rf.feature_importances_[i]:.3f}")

实测结果：

模型                          训练集      测试集
单棵决策树                   100.0%    91.8%     ← 第1章那棵
Bagging(100棵)              100.0%    94.2%     ← +2.4%
随机森林(100棵)              100.0%    94.2%
GBDT(100棵,深度3)           100.0%    94.2%

GBDT：学习率与树数量的配合
树数      学习率        测试集
10        0.1        93.0%
200       0.1        94.7%
500       0.1        95.3%     ← 更多树还在涨
500       0.01       94.2%     ← lr 太小，500 棵不够用

特征重要性 Top5：
  worst perimeter           0.140
  worst concave points      0.132
  worst radius              0.115

💡 注意：所有集成模型训练集都是 100%，但测试集比单棵树高 2–3.5%。 训练集 100% 不等于过拟合——关键看测试集有没有跟着掉。

⚠️ 特征重要性的三个坑

树模型能给特征重要性，但别太当真：

⭐ 第一个坑的根就是第二节那件事：信息增益、增益率、基尼全都偏爱取值多的特征（用户 ID 的信息增益能到满分 1.000）。 CART 靠「只能二叉」把病压住了，但取值多 = 候选切分点多 = 被选中的机会多，这个偏向从来没被真正消除。

✅ 更可靠的做法：Permutation Importance（打乱某列看性能掉多少）或 SHAP。

🔗 和站内其他章的关系

看完这一章，接着往哪走：

✅ 检查点

1. 决策树怎么决定在哪里切分？两种纯度指标是什么？
2. ID3 的信息增益有什么致命偏好？C4.5 除以「固有值」是在惩罚什么？
3. 基尼比熵快在哪？它解决「偏向多值特征」了吗？CART 靠什么压住？
4. 为什么 Boosting 家族的树只能是 CART，不能是 ID3 / C4.5？
5. Bagging 和 Boosting 的根本区别？各降低什么？随机森林为什么要「随机选特征」？
6. GBDT 里每棵新树学的是什么？为什么树要比随机森林浅？learning_rate 和 n_estimators 什么关系？
7. 实测里所有集成模型训练集都是 100%，这算过拟合吗？该看哪个数？
8. 特征重要性有哪三个坑？其中「偏向高基数特征」的根在本章哪一节？

🛑 可以停在这里

⚡ 走神救援

决策树＝切方块，贪心试遍所有切分点，选让子节点最纯的一刀。优点：不用标准化、自带特征交互；⚠️缺点：极易过拟合（不限制就是每叶一个样本＝第 1 章那个 100% / 91.8%）；最常用的旋钮是 max_depth。⭐判据换过三代：ID3 信息增益＝切前熵 − 切后加权熵，⚠️致命偏好：取值越多增益越大——20 个样本 10 正 10 负时，「用户 ID」（20 个取值）增益满分 1.000，真正有用的二值特征只有 0.531，ID3 会选 ID，等于把样本背下来。C4.5 除以固有值 IV（IV＝「这一刀切得多碎」的熵，和标签无关）：ID 的 IV＝log₂20＝4.322，增益率掉到 0.231，二值特征 0.531 反超；⚠️但增益率又偏爱少值特征，所以 C4.5 实际是两步：先筛增益高于平均的、再挑增益率最高的。CART 用基尼 1−Σp²，快在不用算 log（基尼是 −ln p ≈ 1−p 的一阶泰勒近似，和熵曲线几乎重合）；⚠️基尼没解决多值偏好（同一组数：A 基尼下降 0.32、ID 是 0.50，照样选 ID），CART 靠只长二叉树压住——这就是「特征重要性偏向高基数」那个坑的根。⭐Boosting 家族只能用 CART，因为负梯度是连续实数，ID3/C4.5 只会分类。集成三条路：⭐Bagging 并行、降方差（随机森林＝有放回抽样＋每次分裂只从随机 k 个特征里挑，⭐否则每棵树都先用最强特征分裂、长得都一样——集成的收益全来自成员差异）；⭐Boosting 串行、降偏差（GBDT：每棵新树预测"前面所有树加起来还差多少"，即损失的负梯度）；Stacking 分层。GBDT 三参数：学习率 0.01–0.1、树深 3–8（浅是故意的：每棵树只需纠正一点点）、树数；⭐学习率和树数是一对：减半就要翻倍。实测：单棵树 100.0%/91.8% → Bagging、随机森林、GBDT 都是 100.0%/94.2%（+2.4%）；GBDT 10 棵 93.0%、200 棵 94.7%、500 棵 95.3% 还在涨，但学习率降到 0.01 时 500 棵只有 94.2%，根本不够用。💡训练集 100% 不等于过拟合，关键看测试集有没有跟着掉。⚠️特征重要性三个坑：偏向高基数、相关特征分摊、只反映训练集——改用 Permutation Importance 或 SHAP。⭐本章故意留了半句：负梯度只给方向不给步长，GBDT 用 learning_rate 压小步子是绕开不是解决——真正解决它的是 04b 的二阶泰勒展开。

下一节 👉 04b-XGBoost的推导.md ⭐⭐ 本章那半句没讲完的话

🎁 只想会调参、不想看推导的话，也可以从这里直接去 05-评估与过拟合.md（⭐⭐⭐ 全教程最重要的一章），04b 随时回来补都行。