---
tags: [AI, 经典机器学习, 集成学习, 决策树]
阶段: 03-经典机器学习
难度: ★★★
created: 2026-10-18
related: "[[机器学习绪论]], [[模型评估与交叉验证]], [[支持向量机SVM]], [[异常检测]]"
---

# 树模型与集成学习

## 定义

**决策树**（decision tree）是一种把输入空间递归地划分为若干互不重叠的轴对齐矩形区域、并在每个区域上输出常数预测的模型；**集成学习**（ensemble learning）是把多个基学习器的输出组合为单一预测的方法，组合方式包括对样本扰动后的模型取平均（bagging）与把模型按加法逐步累加（boosting）。

- $\mathcal{D}=\{(\mathbf{x}_i,y_i)\}_{i=1}^{n}$：训练集，$\mathbf{x}_i\in\mathbb{R}^{d}$，$y_i$ 为类别或实值。
- $T$：树的叶结点数；剪枝一节写作 $|T|$，含义相同。
- $R_m$：第 $m$ 个叶结点对应的特征空间区域，叶结点输出常数 $c_m$。
- $N_m$：落入区域 $R_m$ 的训练样本数。
- $p_k$：当前结点中第 $k$ 类样本的比例，$K$ 为类别数。
- $H(\cdot)$：信息熵；$\mathrm{Gini}(\cdot)$：基尼指数；两者都称为不纯度（impurity）度量。
- $\nu\in(0,1]$：学习率（shrinkage），控制每棵树的贡献。
- $M$：基学习器数量；$f_m$：第 $m$ 棵回归树；$F_M(\mathbf{x})=\sum_{m=1}^{M}\nu f_m(\mathbf{x})$：加法模型。
- $g_i,h_i$：损失函数对当前预测的一阶、二阶导数，$g_i=\partial_{\hat y}l(y_i,\hat y)$，$h_i=\partial^{2}_{\hat y}l(y_i,\hat y)$。
- $\gamma$：XGBoost 中每增加一个叶结点的固定代价；$\lambda$：叶结点权重的 $L_2$ 正则系数。

## 为什么重要

- 解决的问题：线性模型只能表达全局线性或经核映射后的边界，无法直接表达「若 $x_1>t_1$ 且 $x_2\le t_2$ 则预测为某类」这类条件组合；决策树用轴对齐划分直接表达特征交互，且不需要特征缩放。
- 没有它会怎样：表格数据上的非线性建模缺少一个可解释、可处理缺失值与混合类型的基线；偏差-方差权衡也缺少一个可以用「平均」与「累加」两种方式分别控制方差与偏差的工程范式。
- 集成的意义：单棵树方差大、对样本扰动敏感；bagging 通过对重采样数据取平均降低方差，boosting 通过逐步拟合残差降低偏差。两者分别对应 [[机器学习绪论]] 中偏差-方差分解的两个方向。
- 在全书中的位置：前置为 [[机器学习绪论]] 的经验风险与偏差-方差分解、[[模型评估与交叉验证]] 的验证流程；与 [[支持向量机SVM]] 构成「全局间隔最大化」与「轴对齐分段常数」两种归纳偏置的对照；后续在 [[异常检测]] 中以孤立森林的形式再次出现。
- 对应能力目标：懂原理要求能推导三种分裂准则、GBDT 的伪残差与叶子值、XGBoost 的二阶增益；能复现要求能手写单轮 GBDT 并复现库函数的输出；会评估要求能通过验证集选择树深、学习率与正则系数。

## 原理与推导

```mermaid
flowchart LR
    D["训练集"] --> S1["有放回重采样"]
    D --> S2["全量数据与当前预测"]
    S1 --> P1["并行训练多棵树"]
    S2 --> P2["串行训练多棵树"]
    P1 --> A1["平均或投票：主要降低方差"]
    P2 --> A2["按学习率累加：主要降低偏差"]
```

### 1. 决策树结构与递归划分

决策树把输入空间划分为 $M$ 个互不重叠的区域 $R_1,\dots,R_M$，模型为

$$
f(\mathbf{x})=\sum_{m=1}^{M}c_m\,\mathbb{1}\left[\mathbf{x}\in R_m\right].
$$

每个内部结点对应一次判断「$x_j\le t$ 是否成立」，左子树取成立分支，右子树取不成立分支。区域因此是轴对齐矩形的并集。CART 只产生二叉分裂；ID3 与 C4.5 允许多路分裂，一次按一个离散特征的全部取值划分。

树的构造是贪心的：在每个结点上，遍历所有特征与候选阈值，选择使不纯度下降最大的划分，然后对子结点递归执行。全局最优树需要在所有可能的树结构上搜索，其计算复杂度是指数级的，贪心只能保证当前结点最优。

贪心的直接后果是：每一步只考虑当前不纯度下降，不考虑该划分对后续划分的影响，因此当前最优的划分未必通向全局最优的树，这正是预剪枝风险与后剪枝动机的来源。此外，当多个候选的下降量并列时，实现按特征顺序取第一个，这一并列处理会使树结构随特征排列或随机种子变化。

### 2. 分裂准则

设当前结点样本集为 $D$，第 $k$ 类占比为 $p_k$。

**信息熵**：

$$
H(D)=-\sum_{k=1}^{K}p_k\log_2 p_k .
$$

$H(D)=0$ 当且仅当结点纯净；$K$ 类均匀分布时 $H(D)=\log_2 K$ 取最大。ID3 使用**信息增益**：

$$
\mathrm{Gain}(D,a)=H(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}H(D^{v}),
$$

其中 $a$ 为特征，$D^{v}$ 为 $a$ 取第 $v$ 个值的子集，$V$ 为取值数。

信息增益偏向取值多的特征：当 $V$ 接近 $|D|$ 时，每个子集只含少量样本，条件熵趋于零，增益接近 $H(D)$。C4.5 用**增益率**修正：

$$
\mathrm{IV}(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}\log_2\frac{|D^{v}|}{|D|},
\qquad
\mathrm{GainRatio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)} .
$$

$\mathrm{IV}(a)$ 是划分本身的熵，取值越多、越均匀，$\mathrm{IV}$ 越大，增益率被压得越低。C4.5 的实际做法是先选出增益高于平均水平的候选，再在其中取增益率最大者，避免增益率过度偏向取值极少的划分。

**基尼指数**：

$$
\mathrm{Gini}(D)=1-\sum_{k=1}^{K}p_k^{2}=\sum_{k}\sum_{k'\ne k}p_k p_{k'} .
$$

它等于随机抽取两个样本、其类别不同的概率。二分类时设正类比例为 $p$，则 $\mathrm{Gini}=2p(1-p)$，在 $p=0.5$ 处取最大值 $0.5$。划分后的基尼指数为

$$
\mathrm{GiniIndex}(D,a)=\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}\mathrm{Gini}(D^{v}),
$$

CART 选择使该值最小的划分。

三种准则的性质对比：

| 准则 | 取值范围（二分类） | 计算 | 偏好 | 使用者 |
|---|---|---|---|---|
| 信息增益 | $[0,1]$ bit | 含对数 | 取值多的特征 | ID3 |
| 增益率 | $[0,1]$ 量级 | 含两次对数 | 修正多值偏好，偏向极不平衡划分 | C4.5 |
| 基尼指数 | $[0,0.5]$ | 仅乘加 | 偏向孤立占比最大的类 | CART |

三种准则都是凹函数、在纯净结点取零、在均匀分布取最大，因此对「哪个划分更好」的判断高度相关，差异主要出现在多个候选接近时。基尼指数不需要对数运算，在 CART 的实现中更快；信息熵对不纯度小的结点更敏感，倾向于产生更平衡的划分。

手算对比。取 8 个样本，4 正 4 负，两个候选特征：

| 样本 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 特征 A | a1 | a1 | a1 | a2 | a2 | a2 | a2 | a2 |
| 特征 B | b1 | b1 | b2 | b2 | b3 | b3 | b4 | b4 |
| 标签 | + | + | + | + | - | - | - | - |

$H(D)=1$ bit，$\mathrm{Gini}(D)=0.5$。

特征 A：$D^{a1}$ 含 3 个正类，$H=0$；$D^{a2}$ 含 1 正 4 负，$H=0.7219$。条件熵 $=\frac{3}{8}\times0+\frac{5}{8}\times0.7219=0.4512$，故 $\mathrm{Gain}=0.5488$。$\mathrm{IV}(A)=0.9544$，增益率 $=0.5751$。基尼：$\mathrm{Gini}(D^{a1})=0$，$\mathrm{Gini}(D^{a2})=0.32$，加权得 $0.2$。

特征 B：四个取值各含 2 个同类样本，全部纯净，条件熵为 $0$，$\mathrm{Gain}=1$。$\mathrm{IV}(B)=2$，增益率 $=0.5$。基尼指数为 $0$。

按信息增益，B 更好（$1>0.5488$）；按增益率，A 更好（$0.5751>0.5$）。B 的四个取值与样本对一一对应，行为接近样本编号，属于高基数特征。这一构造说明：信息增益的偏好可以被「把样本分得足够细」利用，而增益率通过扣除划分本身的熵抑制了这种倾向。

### 3. 连续特征的切分点选择

设某特征在结点内的取值为 $v_1<v_2<\dots<v_m$。对阈值 $t$，划分只取决于哪些样本满足 $x\le t$，因此 $t$ 落在区间 $[v_i,v_{i+1})$ 内时划分完全相同。候选阈值只需取 $m-1$ 个中点

$$
t_i=\frac{v_i+v_{i+1}}{2},\qquad i=1,\dots,m-1 .
$$

对每个候选计算不纯度并按最优者切分。排序代价 $O(m\log m)$，之后用前缀和可以在 $O(m)$ 内遍历全部候选，因此单特征的最优切分代价为 $O(m\log m)$。若特征取值重复，重复值不应成为切分点，取中点前需先去重。

样本量很大时，精确遍历全部候选仍可能过慢。常用的近似做法是把特征离散化为至多 $B$ 个分位桶（如 255 个），只在桶边界上搜索。这会把每次切分的候选数压到 $O(B)$，代价是可能错过最优阈值。

### 4. 预剪枝与后剪枝

**预剪枝**在生长过程中提前停止，常用约束：最大深度 `max_depth`、叶结点最少样本数 `min_samples_leaf`、结点最少样本数 `min_samples_split`、最小不纯度下降 `min_impurity_decrease`。优点是训练快、树小；缺点是有视野效应：当前划分的不纯度下降可能很小，但其子划分的下降很大，提前停止会错过后续更优的结构。

**后剪枝**先让树完全生长，再自底向上删除子树。CART 使用**代价复杂度剪枝**（cost-complexity pruning）：对树 $T$，定义

$$
R_\alpha(T)=R(T)+\alpha|T|,
\qquad
R(T)=\sum_{m=1}^{|T|}\frac{N_m}{N}H(R_m),
$$

其中 $R(T)$ 是训练集上的误分类率或不纯度，$|T|$ 为叶结点数，$\alpha\ge0$ 是复杂度惩罚。$\alpha=0$ 时保留完整树；$\alpha$ 增大时更小的树占优。对每个 $\alpha$，存在唯一的最优子树，可通过 weakest link 规则逐个合并叶结点得到一串嵌套子树，再用交叉验证选择 $\alpha$。

两种策略的对比：

| 维度 | 预剪枝 | 后剪枝 |
|---|---|---|
| 计算 | 一次生长，开销小 | 先长满再剪，开销大 |
| 过拟合风险 | 可能欠拟合（视野效应） | 通常更低 |
| 参数 | 深度、叶样本数等阈值 | 复杂度参数 $\alpha$ |
| 调参方式 | 网格搜索 | 交叉验证选择子树序列 |

### 5. Bagging 与随机森林

**Bagging**（bootstrap aggregating）对训练集做 $B$ 次有放回重采样，每次得到 $n$ 个样本，训练一个基学习器，预测时取平均或投票。单个样本在一次重采样中不被抽中的概率为 $(1-1/n)^{n}\to e^{-1}\approx0.368$，因此每次约有 36.8% 的样本成为袋外（out-of-bag）样本，可用于无额外验证集的误差估计。

设基学习器方差为 $\sigma^{2}$，两两相关系数为 $\rho$，则 $B$ 个模型平均的方差为

$$
\operatorname{Var}\left(\frac{1}{B}\sum_{b=1}^{B}T_b\right)
=\frac{1}{B^{2}}\left[B\sigma^{2}+B(B-1)\rho\sigma^{2}\right]
=\rho\sigma^{2}+\frac{1-\rho}{B}\sigma^{2}.
$$

$B\to\infty$ 时方差趋于 $\rho\sigma^{2}$，平均只能消除独立分量，不能消除相关性带来的部分。**随机森林**（random forest）在 bagging 基础上再加一层随机性：每次结点分裂只在随机抽取的 $m_{\mathrm{try}}$ 个特征中搜索（分类常用 $\sqrt{d}$，回归常用 $d/3$）。其作用是降低树之间的相关性 $\rho$，从而压低上式中的第一项。代价是单棵树的偏差略增。

由于平均不改变期望，bagging 与随机森林主要降低方差，对偏差的改善有限；树越深、单棵树方差越大，bagging 收益越明显。增加树的数量不会导致过拟合，方差有上界 $\rho\sigma^{2}$，但计算成本线性增长。

### 6. Boosting 与加法模型

Boosting 把多个弱学习器累加为强学习器：

$$
F_M(\mathbf{x})=\sum_{m=1}^{M}\nu f_m(\mathbf{x}),
$$

其中 $f_m$ 是第 $m$ 轮训练的基学习器，$\nu$ 是学习率。训练采用**前向分步**（forward stagewise）：第 $m$ 轮固定前 $m-1$ 轮的模型，只优化新加入的 $f_m$：

$$
f_m=\arg\min_{f}\sum_{i=1}^{n}L\left(y_i,F_{m-1}(\mathbf{x}_i)+f(\mathbf{x}_i)\right),
\qquad
F_m=F_{m-1}+\nu f_m .
$$

与 bagging 的并行结构不同，boosting 的每一轮依赖上一轮的残差，训练是串行的。它主要降低偏差：每棵新树拟合当前模型尚未解释的部分。AdaBoost 是指数损失 $L=\sum_i\exp\left(-y_iF(\mathbf{x}_i)\right)$ 下的特例，其样本权重更新可从该损失的前向分步最小化推出。

### 7. GBDT：负梯度拟合与前向分步

把前向分步中的 $f$ 限制为回归树，并用一阶近似代替直接优化，就得到**梯度提升决策树**（Gradient Boosting Decision Tree, GBDT）。

初始模型取常数：

$$
F_0=\arg\min_{c}\sum_{i=1}^{n}L(y_i,c).
$$

平方损失下 $F_0=\bar y$；对数损失下 $F_0=\log\frac{\bar y}{1-\bar y}$，即基准比例的对数几率。

第 $m$ 轮，定义**伪残差**为损失对当前预测的负梯度：

$$
r_{im}=-\left[\frac{\partial L(y_i,F)}{\partial F}\right]_{F=F_{m-1}(\mathbf{x}_i)} .
$$

用平方误差准则拟合回归树 $h_m$ 到样本 $\{(\mathbf{x}_i,r_{im})\}$，得到叶结点区域 $R_{jm}$。随后在每个叶结点上重新求解常数，使真实损失最小：

$$
v_{jm}=\arg\min_{v}\sum_{\mathbf{x}_i\in R_{jm}}L\left(y_i,F_{m-1}(\mathbf{x}_i)+v\right),
$$

$$
F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+\nu\sum_{j}v_{jm}\,\mathbb{1}\left[\mathbf{x}\in R_{jm}\right].
$$

拟合伪残差时使用平方误差只是构造树结构的代理准则；叶结点的输出值由真实损失重新确定，这一步等价于在叶结点内做一次线搜索。

**平方损失**：$L=\frac{1}{2}(y-F)^{2}$，$r_{im}=y_i-F_{m-1}(\mathbf{x}_i)$ 就是残差，$v_{jm}$ 是该叶结点内残差的均值。此时 GBDT 逐轮拟合残差。

**对数损失**：设 $p_i=\sigma(F_{m-1}(\mathbf{x}_i))=1/(1+e^{-F_{m-1}(\mathbf{x}_i)})$，二分类 $y_i\in\{0,1\}$，

$$
L(y,F)=\log\left(1+e^{F}\right)-yF,
\qquad
\frac{\partial L}{\partial F}=p-y=-r,
\qquad
\frac{\partial^{2}L}{\partial F^{2}}=p(1-p).
$$

在叶结点内对 $v$ 做二阶展开并令导数为零：

$$
\sum_{i\in R_{jm}}\left[-r_i+v\,p_i(1-p_i)\right]=0
\;\Longrightarrow\;
v_{jm}=\frac{\sum_{i\in R_{jm}}r_i}{\sum_{i\in R_{jm}}p_i(1-p_i)} .
$$

分子是残差和，分母是各样本曲率之和，这正是牛顿法的一步更新。若用回归树的叶均值作为 $v$，则忽略了损失的二阶信息，收敛更慢且尺度不正确。

学习率 $\nu$ 与树的数量 $M$ 共同决定模型复杂度：$\nu$ 越小，单棵树的影响越弱，需要更多轮次才能拟合训练集；$\nu$ 与 $M$ 必须联合调参，固定一个调另一个得到的结论不可迁移。

### 8. XGBoost：二阶泰勒展开与正则化目标

XGBoost 在 GBDT 的加法框架上做两处改动：目标函数显式加入树复杂度正则项；每轮用二阶泰勒展开近似损失。

第 $t$ 轮的目标为

$$
\mathcal{L}^{(t)}=\sum_{i=1}^{n}l\left(y_i,\hat y_i^{(t-1)}+f_t(\mathbf{x}_i)\right)+\Omega(f_t),
\qquad
\Omega(f)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_j^{2},
$$

其中 $T$ 为叶结点数，$w_j$ 为第 $j$ 个叶结点的输出值。$\gamma T$ 惩罚叶结点数量，$\lambda\sum w_j^{2}$ 惩罚叶结点输出的幅度。

对损失做二阶展开，记 $g_i=\partial_{\hat y}l(y_i,\hat y^{(t-1)})$、$h_i=\partial^{2}_{\hat y}l(y_i,\hat y^{(t-1)})$：

$$
\mathcal{L}^{(t)}\approx\sum_{i=1}^{n}\left[g_i f_t(\mathbf{x}_i)+\frac{1}{2}h_i f_t^{2}(\mathbf{x}_i)\right]+\Omega(f_t)+\text{常数}.
$$

设样本 $i$ 落在叶结点 $j$，即 $f_t(\mathbf{x}_i)=w_j$，按叶结点分组，记 $G_j=\sum_{i\in I_j}g_i$、$H_j=\sum_{i\in I_j}h_i$：

$$
\mathcal{L}^{(t)}=\sum_{j=1}^{T}\left[G_j w_j+\frac{1}{2}\left(H_j+\lambda\right)w_j^{2}\right]+\gamma T .
$$

对每个 $w_j$ 独立求导并令其为零：

$$
\frac{\partial\mathcal{L}}{\partial w_j}=G_j+\left(H_j+\lambda\right)w_j=0
\;\Longrightarrow\;
w_j^{*}=-\frac{G_j}{H_j+\lambda}.
$$

代回得最优目标值

$$
\mathcal{L}^{(t)*}=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^{2}}{H_j+\lambda}+\gamma T .
$$

一次分裂把叶结点分成左右两部分，带来的目标下降为

$$
\mathrm{Gain}=\frac{1}{2}\left[\frac{G_L^{2}}{H_L+\lambda}+\frac{G_R^{2}}{H_R+\lambda}-\frac{\left(G_L+G_R\right)^{2}}{H_L+H_R+\lambda}\right]-\gamma .
$$

只有当 $\mathrm{Gain}>0$ 时分裂才被接受，这等价于要求目标下降超过 $\gamma$，因此 $\gamma$ 起到后剪枝阈值的作用。$\lambda$ 使分母变大、叶结点权重变小，是显式的收缩；$\lambda\to\infty$ 时权重趋于零，树退化为常数。

与 GBDT 的关系：平方损失下 $g_i=\hat y_i-y_i$、$h_i=1$，于是 $w_j^{*}=-\frac{\sum_{i\in I_j}(\hat y_i-y_i)}{|I_j|+\lambda}$，即叶结点内残差均值的收缩版本。取 $\lambda=0$ 时与 GBDT 的叶值完全一致；对数损失下 $g_i=p_i-y_i$、$h_i=p_i(1-p_i)$，$w_j^{*}$ 与 GBDT 的牛顿叶值相同。二阶形式统一了不同损失下的叶值计算，并让 $\lambda$ 直接进入分母。

分裂查找。精确贪心算法对每个特征先按取值排序，再从左到右扫描，用前缀和增量维护 $G_L,H_L$，代价为 $O(nd\log n)$ 一次（对全部特征排序）加上 $O(nd)$ 的扫描。样本过多时使用近似算法：按特征分布的分位数构造候选切分点（加权分位数草图），把候选数降到常数级。缺失值按「默认方向」处理：分别尝试把缺失样本分到左、右，取增益更大的一侧。

### 9. LightGBM：直方图与 leaf-wise

LightGBM 针对大规模数据做了三项工程优化。

直方图分桶：把连续特征离散为至多 255 个桶，结点分裂时只遍历桶边界。直方图的构造代价为 $O(nd)$，之后每次分裂的候选数为 $O(B)$，且可以用「父结点直方图减去兄弟结点直方图」得到另一子结点的直方图，把每个结点的直方图构造代价减半。

leaf-wise 生长：不再逐层扩展，而是每次选择当前增益最大的叶结点继续分裂，直到叶结点数达到 `num_leaves`。相同叶结点数下，leaf-wise 的训练误差通常更低，但在小样本上更容易过拟合，需要同时限制 `num_leaves`、`max_depth` 与 `min_data_in_leaf`。

特征与样本采样：互斥特征捆绑（exclusive feature bundling）把稀疏的互斥特征合并，降低有效特征数；基于梯度的单边采样（gradient-based one-side sampling）保留梯度大的样本、对梯度小的样本随机采样并加权，减少参与直方图构造的样本数。

### 10. 特征重要性

常用的三种定义：

| 定义 | 计算 | 偏差 |
|---|---|---|
| 增益型 | 该特征所有分裂带来的不纯度下降（按样本数加权）之和 | 偏向高基数与连续特征 |
| 分裂次数型 | 该特征被用作分裂特征的次数 | 强烈偏向高基数特征 |
| 置换型 | 打乱该特征取值后验证误差的上升量 | 需要验证集，相关特征会互相分摊 |

增益型重要性在 scikit-learn 中由「加权不纯度下降」给出：结点 $m$ 的重要性增量为 $\frac{N_m}{N}\left[H(m)-\frac{N_L}{N_m}H(L)-\frac{N_R}{N_m}H(R)\right]$，对所有使用该特征的结点求和后归一化。由于不纯度下降的绝对量随结点样本数缩小，深层分裂的贡献天然较小；高基数特征能提供更多候选切分点，更容易在训练集上找到不纯度下降大的划分，因此重要性偏高并不必然意味着该特征在验证集上更有用。

## 关键直觉

> [!tip] 机制性直觉
> Boosting 可以视为在函数空间中沿负梯度方向做带约束的梯度下降：每棵回归树是负梯度向量在「分段常数函数」这一假设类上的投影，学习率是步长，叶结点值是该方向上的线搜索。Bagging 可以视为对样本扰动取平均：它不改变期望，只把方差从 $\sigma^{2}$ 压到 $\rho\sigma^{2}+(1-\rho)\sigma^{2}/B$，随机森林通过特征子采样降低 $\rho$。这与定义中「加法模型」与「对样本扰动取平均」两种组合方式一一对应：前者改变偏差，后者改变方差。

## 例子与代码

### 手算：GBDT 单轮回归

取 8 个一维样本 $x=1,\dots,8$，$y=(1.0,1.6,2.1,3.2,4.1,5.3,6.0,7.1)$。平方损失下 $F_0=\bar y=3.8$，初始均方误差为 $4.25$。

第 1 轮：残差 $r=y-F_0=(-2.8,-2.2,-1.7,-0.6,0.3,1.5,2.2,3.3)$。用深度为 1 的回归树（单个切分点）拟合残差，遍历相邻样本中点 $1.5,2.5,\dots,7.5$，取平方误差最小者，得切分点 $4.5$：左叶 4 个样本的残差均值为 $-1.825$，右叶 4 个为 $+1.825$，残差平方和为 $7.355$。

取学习率 $\nu=0.3$，更新

$$
F_1(\mathbf{x})=3.8+0.3\times
\begin{cases}
-1.825, & x\le4.5,\\
+1.825, & x>4.5,
\end{cases}
$$

即前 4 个样本预测 $3.2525$，后 4 个预测 $4.3475$，均方误差降至 $2.5514$。第 2 轮在新残差上重复同样过程，切分点变为 $5.5$，均方误差降至 $1.5755$；第 3 轮切分点为 $3.5$，均方误差降至 $1.0059$。

### 代码一：决策树的结构、深度与重要性

```python
# 依赖：Python 3.12、scikit-learn 1.9.1
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

X, y = load_iris(return_X_y=True)
names = load_iris().feature_names
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)

for depth in [2, 3, None]:
    clf = DecisionTreeClassifier(criterion="gini", max_depth=depth, random_state=0).fit(X_tr, y_tr)
    print(f"max_depth={str(depth):>4} 叶结点={clf.get_n_leaves():2d} "
          f"训练准确率={clf.score(X_tr, y_tr):.4f} 测试准确率={clf.score(X_te, y_te):.4f}")

clf = DecisionTreeClassifier(criterion="gini", max_depth=2, random_state=0).fit(X_tr, y_tr)
print(export_text(clf, feature_names=names, decimals=2))
print("根结点 gini =", round(float(clf.tree_.impurity[0]), 4), " 根结点样本数 =", int(clf.tree_.n_node_samples[0]))
print("特征重要性 =", {k: round(float(v), 4) for k, v in zip(names, clf.feature_importances_)})
t = clf.tree_
print("左子结点不纯度 =", round(float(t.impurity[t.children_left[0]]), 4),
      " 右子结点不纯度 =", round(float(t.impurity[t.children_right[0]]), 4))
```

预期输出：

```text
max_depth=   2 叶结点= 3 训练准确率=0.9619 测试准确率=0.9556
max_depth=   3 叶结点= 5 训练准确率=0.9619 测试准确率=0.9556
max_depth=None 叶结点= 8 训练准确率=1.0000 测试准确率=0.9778
|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal width (cm) <= 1.75
|   |   |--- class: 1
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2

根结点 gini = 0.6667  根结点样本数 = 105
特征重要性 = {'sepal length (cm)': 0.0, 'sepal width (cm)': 0.0, 'petal length (cm)': 0.0, 'petal width (cm)': 1.0}
左子结点不纯度 = 0.0  右子结点不纯度 = 0.5
```

解读：

- 深度 2 的树只用了 `petal width`，因此该特征的归一化重要性为 1.0。根结点不纯度 $0.6667$，左子结点纯净、右子结点 $0.5$，加权下降为 $\frac{105}{105}\times0.6667-\left(\frac{35}{105}\times0+\frac{70}{105}\times0.5\right)=0.3333$，全部计入 `petal width`。
- 深度从 2 增加到 3 时，叶结点从 3 增至 5，训练与测试准确率都不变。新增的分裂把同一个叶结点继续拆成两个同类的叶结点，预测不变但不纯度下降。这说明「不纯度下降」与「预测改善」不是同一件事。
- 深度不限时训练准确率达到 1.0，测试准确率 0.9778，叶结点 8 个，过拟合程度有限但仍高于深度 2。
- `export_text` 中的阈值 $0.80$ 与 $1.75$ 是相邻取值的算术中点，与第 3 小节的候选切分点规则一致。

### 代码二：手写 GBDT 与库函数对照

```python
import numpy as np
from sklearn.ensemble import GradientBoostingRegressor

X = np.arange(1, 9, dtype=float).reshape(-1, 1)
y = np.array([1.0, 1.6, 2.1, 3.2, 4.1, 5.3, 6.0, 7.1])

def best_stump(x, r):
    # 穷举相邻样本中点，返回使平方误差最小的 (切分点, 误差, 左叶均值, 右叶均值)
    order = np.argsort(x)
    xs, rs = x[order], r[order]
    best = (None, np.inf, None, None)
    for t in (xs[:-1] + xs[1:]) / 2.0:
        left, right = rs[xs <= t], rs[xs > t]
        sse = ((left - left.mean()) ** 2).sum() + ((right - right.mean()) ** 2).sum()
        if sse < best[1]:
            best = (t, sse, left.mean(), right.mean())
    return best

F = np.full_like(y, y.mean())
lr = 0.3
print(f"F0 = {y.mean():.4f}  MSE = {np.mean((y - F) ** 2):.4f}")
for m in range(1, 4):
    t, sse, lm, rm = best_stump(X.ravel(), y - F)
    F = F + lr * np.where(X.ravel() <= t, lm, rm)
    print(f"第{m}轮 切分点={t:.1f} 左叶残差均值={lm:+.4f} 右叶残差均值={rm:+.4f} "
          f"SSE={sse:.4f} MSE={np.mean((y - F) ** 2):.4f}")

ref = GradientBoostingRegressor(n_estimators=3, max_depth=1, learning_rate=0.3,
                                random_state=0).fit(X, y)
print("sklearn 预测 =", np.round(ref.predict(X), 4))
print("手写实现预测 =", np.round(F, 4))
print("sklearn 三轮 MSE =", round(float(np.mean((y - ref.predict(X)) ** 2)), 6))
```

预期输出：

```text
F0 = 3.8000  MSE = 4.2500
第1轮 切分点=4.5 左叶残差均值=-1.8250 右叶残差均值=+1.8250 SSE=7.3550 MSE=2.5514
第2轮 切分点=5.5 左叶残差均值=-1.0715 右叶残差均值=+1.7858 SSE=5.1029 MSE=1.5755
第3轮 切分点=3.5 左叶残差均值=-1.3644 右叶残差均值=+0.8186 SSE=3.6685 MSE=1.0059
sklearn 预测 = [2.5217 2.5217 2.5217 3.1766 4.2716 5.1288 5.1288 5.1288]
手写实现预测 = [2.5217 2.5217 2.5217 3.1766 4.2716 5.1288 5.1288 5.1288]
sklearn 三轮 MSE = 1.005854
```

解读：

- 手写实现的预测与 `GradientBoostingRegressor(n_estimators=3, max_depth=1, learning_rate=0.3)` 完全一致，说明「残差 → 平方误差树 → 叶均值 → 学习率累加」这四步就是平方损失下 GBDT 的全部内容。
- 每轮的切分点依次为 $4.5$、$5.5$、$3.5$，并不单调；残差被逐轮重新分配，模型先修正整体偏移，再逐轮修正局部的残差结构。
- 把 `lr` 改为 $1.0$ 时，第 1、2、3 轮后的均方误差分别为 $0.9194$、$0.6086$、$0.5251$；改为 $0.1$ 时分别为 $3.6172$、$3.0898$、$2.6546$。学习率越大，相同轮数下训练误差越低，但单棵树的影响也越大，需要更多轮数才能逼近相同的拟合程度，因此学习率与轮数必须联合调参。
- 若删去 `best_stump` 中对所有候选中点的遍历、只按固定切分点分裂，则残差的局部结构无法被捕捉，MSE 下降会明显变慢。

### 代码三：XGBoost 的增益公式与正则系数

```python
import numpy as np

X = np.array([[1.], [2.], [3.], [4.], [5.], [6.]])
y = np.array([0, 0, 0, 1, 1, 1], dtype=float)
p = np.full(6, 0.5)                      # base_score，初始预测的对数几率
g, h = p - y, p * (1 - p)                # 对数损失下的一阶与二阶导数
G, H = g.sum(), h.sum()

def evaluate(t, lam):
    left = X.ravel() <= t
    GL, HL = g[left].sum(), h[left].sum()
    GR, HR = G - GL, H - HL
    gain = 0.5 * (GL**2 / (HL + lam) + GR**2 / (HR + lam) - G**2 / (H + lam))
    wL, wR = -GL / (HL + lam), -GR / (HR + lam)
    F1 = np.where(left, wL, wR)
    p1 = 1.0 / (1.0 + np.exp(-F1))
    loss = -np.mean(y * np.log(p1) + (1 - y) * np.log(1 - p1))
    return gain, wL, wR, loss

print("lambda = 1 时各候选切分点的增益：")
for t in [1.5, 2.5, 3.5, 4.5, 5.5]:
    gain, wL, wR, loss = evaluate(t, 1.0)
    print(f"  切分点 {t}: 增益 {gain:.4f} 左叶权重 {wL:+.4f} 右叶权重 {wR:+.4f}")

print("最优切分点 3.5 处，不同 lambda 的结果：")
for lam in [0.0, 1.0, 5.0, 100.0]:
    gain, wL, wR, loss = evaluate(3.5, lam)
    print(f"  lambda={lam:<6} 左叶 {wL:+.4f} 右叶 {wR:+.4f} 增益 {gain:.4f} 对数损失 {loss:.4f}")
```

预期输出：

```text
lambda = 1 时各候选切分点的增益：
  切分点 1.5: 增益 0.1556 左叶权重 -0.4000 右叶权重 +0.2222
  切分点 2.5: 增益 0.5833 左叶权重 -0.6667 右叶权重 +0.5000
  切分点 3.5: 增益 1.2857 左叶权重 -0.8571 右叶权重 +0.8571
  切分点 4.5: 增益 0.5833 左叶权重 -0.5000 右叶权重 +0.6667
  切分点 5.5: 增益 0.1556 左叶权重 -0.2222 右叶权重 +0.4000
最优切分点 3.5 处，不同 lambda 的结果：
  lambda=0.0    左叶 -2.0000 右叶 +2.0000 增益 3.0000 对数损失 0.1269
  lambda=1.0    左叶 -0.8571 右叶 +0.8571 增益 1.2857 对数损失 0.3537
  lambda=5.0    左叶 -0.2609 右叶 +0.2609 增益 0.3913 对数损失 0.5712
  lambda=100.0  左叶 -0.0149 右叶 +0.0149 增益 0.0223 对数损失 0.6857
```

解读：

- 初始 $p=0.5$ 时 $g=(0.5,\dots,0.5,-0.5,\dots,-0.5)$，$G=0$、$H=1.5$，因此根结点不分裂的目标值为 $-\frac{1}{2}\cdot\frac{0^{2}}{1.5}=0$；增益公式中的第三项为 0，前两项决定分裂价值。
- 切分点 $3.5$ 恰好把两类分开，$G_L=1.5$、$H_L=0.75$，$w_L=-1.5/1.75=-0.8571$；对称地 $w_R=+0.8571$。增益 $1.2857$ 与手算一致。
- $\lambda=0$ 时叶权重为 $\pm2$，与 scikit-learn 的 `GradientBoostingClassifier(n_estimators=1, learning_rate=1.0)` 给出的 $\pm2$ 相同，验证了「XGBoost 在 $\lambda=0$ 时退化为 GBDT 的牛顿叶值」。
- $\lambda$ 从 0 增到 100，叶权重从 $\pm2$ 缩到 $\pm0.0149$，对数损失从 $0.1269$ 升到 $0.6857$。正则化在单轮内表现为收缩，轮数增加后会被部分补偿。
- 若把增益公式中的 $\lambda$ 只加在分子项而漏掉分母，增益会随 $\lambda$ 错误地增大，分裂选择与实现不一致。

## 易错点

> [!warning] 常见错误
> - 把信息增益与基尼指数的数值直接比较。两者量纲不同（bit 与概率平方），同一划分的数值不可跨准则比较；跨准则只能比较各自排序下的最优划分是否一致。
> - 认为预剪枝与后剪枝等价。预剪枝在当前结点就停止，可能错过「当前增益小、子划分增益大」的结构；后剪枝先长满再按代价复杂度合并，通常泛化更好但开销更大。
> - 把随机森林的「树越多越好」理解为「树越深越好」。增加树的数量只降低方差且有下界 $\rho\sigma^{2}$；树深增加会提高单棵树方差并加剧相关，可能使平均后方差上升。
> - 在 GBDT 中把叶结点值取为残差均值而不区分损失。只有平方损失下叶值才是残差均值；对数损失下需用 $\sum r_i/\sum p_i(1-p_i)$ 的牛顿步，否则步长尺度错误。
> - XGBoost 增益公式漏项。分母必须包含 $\lambda$，且分裂收益要减去 $\gamma$；`min_child_weight` 约束的是 $\sum h_i$ 而不是样本数。
> - 用训练集上的增益型重要性判断特征价值。高基数特征与连续特征有更多候选切分点，重要性会被系统性高估；需要验证集或置换重要性交叉验证。

## 关联笔记

- 前置：[[机器学习绪论]] —— 偏差-方差分解与经验风险最小化是理解 bagging 降方差、boosting 降偏差的前提。
- 前置：[[模型评估与交叉验证]] —— 树深、叶结点样本数、学习率与 $\lambda$ 均由验证集选择，代价复杂度剪枝的 $\alpha$ 也来自交叉验证。
- 对照：[[支持向量机SVM]] —— SVM 用少数支持向量确定连续边界，对特征尺度敏感；树用轴对齐划分表达交互，不需要缩放但边界不连续。
- 应用：[[异常检测]] —— 孤立森林用随机划分的深度度量孤立程度，是树集成的无监督用法，其划分的随机性与本篇随机森林的特征子采样同属随机化集成。
- 对照：[[正则化与调参]] —— XGBoost 的 $\lambda$、$\gamma$ 与学习率是 $L_2$ 正则、结构惩罚与收缩的具体形式，可与线性模型的正则化逐项对照。

## 达标检测

- [ ] 写出信息熵、信息增益、增益率与基尼指数的定义，并对本篇 8 样本例子算出三种准则下的最优划分。
- [ ] 证明连续特征只需在相邻取值中点处搜索切分点，并说明为什么区间内部任取阈值得到相同划分。
- [ ] 推导 bagging 平均的方差公式，并解释随机森林通过特征子采样降低了公式中的哪一个量。
- [ ] 从加法模型与前向分步出发，推导 GBDT 的伪残差，并给出对数损失下叶结点值 $v_{jm}$ 的完整推导。
- [ ] 完成 XGBoost 从二阶泰勒展开到叶结点最优权重与增益公式的全部步骤，并说明 $\lambda$ 与 $\gamma$ 各自控制什么。
- [ ] 运行代码二并把学习率改为 $0.1$ 与 $1.0$，记录三轮后的 MSE，解释学习率与轮数的耦合关系。
- [ ] 对同一份数据分别用增益型与置换型重要性排序，指出排序差异并说明原因。

## 参考来源

- Hastie, Tibshirani, Friedman, *The Elements of Statistical Learning*, 2009, 第 9 章 加法模型、树与相关方法 —— 对应本篇 CART 递归划分、分裂准则与代价复杂度剪枝。
- 同上，第 10 章 Boosting 与加法树 —— 对应本篇前向分步、GBDT 的伪残差与对数损失下的叶结点值。
- 同上，第 15 章 随机森林 —— 对应本篇 bagging 的方差公式、特征子采样与相关性的作用。
- 同上，第 8 章 模型推断与平均（自助法与 bagging）—— 对应本篇袋外样本比例与重采样方差分析。
- d2l.ai《动手学深度学习》，第 3.6 节 泛化 —— 对应本篇预剪枝、后剪枝与训练误差同泛化误差差异的讨论。
