树模型与集成学习核心30 分钟kp-010#决策树#CART#信息熵

决策树：信息增益、增益率与基尼指数

进度

一句话定义

决策树通过递归地选择「最能纯化标签」的特征与阈值把特征空间划分成矩形区域，在每个叶子上用简单规则（多数类/均值）做预测；CART 用基尼指数或平方误差、ID3/C4.5 用信息熵系指标来选择划分。

为什么重要

它是可解释性最强的模型（规则可以直接翻译给业务方），对特征尺度不敏感、天然处理混合类型与缺失，同时也是随机森林与 GBDT 两大集成主力（kp-011/013）的基学习器——理解树的生长机制才能理解整个集成家族。

前置知识

损失函数：从 0-1 损失到代理损失的损失视角（树的划分准则也是损失）；离散概率基础。

核心概念

信息熵： $H(D) = -\sum k p k log 2 p k$ ，节点标签混乱度。
信息增益（ID3）： $Gain(D, A) = H(D) - \sum v |D v | |D| H(D v)$ ，按特征 $A$ 划分后的熵下降。
增益率（C4.5）：信息增益除以固有值 $IV(A) = -\sum v |D v | |D| log 2 |D v | |D|$ ，惩罚「取值过多」特征的偏袒。
基尼指数（CART）： $Gini(D) = 1 - \sum k p k 2$ ，从节点随机抽两样本异类的概率，越小越纯。
递归划分：选特征-阈值 → 分区 → 对每区重复，直到纯/达深度限制/样本过少。
预剪枝与后剪枝：生长中设限（max_depth、min_samples_leaf）或生长完自底向上剪（ccp_alpha）。

直观类比

玩二十个问题：每个问题都要「一刀切掉尽可能多的不确定性」。熵是「还剩多少悬念」的度量，信息增益是「这个问题消掉多少悬念」。只按问题数量贪心会偏爱「每人一个答案」的废话问题，增益率就是给这种问题收「提问税」。

原理与机制

树的学习是贪心递归：对每个节点遍历候选特征与切分点，计算不纯度下降 $Δ = I(D) - n L n I(D L) - n R n I(D R)$ ，取最大者分裂。对连续特征，先把取值排序、以相邻中点为候选阈值，代价 $O(n log n)$ 。由于每层只看当前最优，整体是 NP-hard 问题的贪心近似——这正是单树高方差、需要剪枝与集成的根源。

回归树（CART 回归版）以平方误差为准则：分裂使 $\sum i (y i - ȳ leaf) 2$ 下降最大，叶预测为叶内均值；等价于用分段常数函数逼近回归面。

剪枝：预剪枝省算力但可能「早夭」（当前不佳的划分后续变好）；后剪枝（代价复杂度剪枝）按 $RSS(T) + α|T|$ 平衡拟合与叶子数，自底向上剪掉不划算的子树，配合交叉验证选 $α$ 。

公式与推导

CART 分类节点选择准则（基尼下降最大）：

Δ Gini (t) = Gini(D t) - n L n t Gini(D t,L) - n R n t Gini(D t,R)

推导基尼与熵的关系：对小概率 $p$ ， $-plog 2 p = -p ln p / ln 2 \approx p(1-p)/ln 2$ ，逐类求和得 $H(D) \approx Gini(D)/ln 2$ ——两者单调相关，实践效果相近；基尼免对数运算更快。

图示

        [收入 > 30k?]            内部节点 = 特征判断
        ╱          ╲
     是              否          边 = 判断结果
    ╱                 ╲
[负债率 < 0.4?]      [拒绝]     叶子 = 预测
   ╱        ╲
 [批准]    [人工复核]
 特征空间被切成轴对齐矩形区域

实例或案例

完整训练并读出人类可读规则：

from sklearn.datasets import load_wine
from sklearn.tree import DecisionTreeClassifier, export_text
from sklearn.model_selection import cross_val_score

X, y = load_wine(return_X_y=True)
tree = DecisionTreeClassifier(max_depth=3, min_samples_leaf=5, random_state=0)
print("CV acc:", cross_val_score(tree, X, y, cv=5).mean().round(3))
tree.fit(X, y)
print(export_text(tree, feature_names=load_wine().feature_names))  # 直接输出 if-else 规则

无 max_depth 时单树在训练集上可到 100% 准确但泛化明显更差——单树方差大的现场演示。

常见误区

不剪枝就上单树：几乎必然过拟合，单树必须配深度/叶样本/剪枝约束。
用信息增益偏爱 ID 类特征：订单号把每个样本切干净，增益爆炸但毫无泛化，用增益率或直接删 ID。
认为树「不需要特征工程」：尺度确实不敏感，但高基数类别特征、无信息特征仍会扭曲划分与重要性（见 kp-027/014）。

与其他知识点的关系

随机森林与 Bagging 用 Bagging 平抑单树方差；梯度提升树 GBDT 与 XGBoost 让树去拟合残差；树模型可解释性：特征重要性与 SHAP 讨论树重要性指标的偏差；特征工程：编码、缩放与缺失值处理说明独热高基数特征对树的伤害。

自测题

信息增益与增益率的差别，各自修复什么问题？

- 要点：增益率 = 增益/固有值，修复增益偏爱取值多特征的偏袒（ID 类问题）。

为什么单棵决策树是高方差模型？

- 要点：贪心分裂使顶层划分的微小变动层层放大，且轴对齐划分对采样噪声敏感；树深上限放开时可完全记住训练集。

回归树的叶子预测值是什么？损失是什么？

- 要点：叶内均值；分裂与预测都以平方误差为准则（等价于分段常数最小二乘）。

延伸阅读

Breiman 等《Classification and Regression Trees》(1984)；周志华《机器学习》第 4 章。