跳至内容

决策树与集成学习

决策树与集成学习的基本原理，以及 GBDT 从初始化到逐轮更新的完整推导。

发布于 约 17 分钟阅读 浏览 — 次
  • 机器学习
  • 决策树
  • 集成学习
  • 随机森林
  • GBDT
  • 复杂度

决策树把输入空间划分成若干区域，每个区域给出一个预测。集成学习再组合多个模型：Bagging 汇总分别训练的模型，Boosting 根据当前模型的误差逐轮增加新模型。

评估与偏差、方差见 机器学习基础；模型比较与调参见 机器学习常见问题。

1. 决策树：按条件逐步划分样本

内部节点检查条件，例如“某项特征是否小于阈值”；分支对应判断结果，叶节点给出预测。训练时，从根节点开始，在当前节点选择划分，再对子节点重复这一过程，直到满足停止条件。

分类树希望子节点的类别更集中。回归树希望落在同一叶子里的目标值更接近，便于用一个数代表它们。

1.1 分类树：信息增益、增益率与 Gini

熵和 Gini 不纯度都衡量节点中的类别有多混杂，值越小，类别越集中。 常见的划分准则如下：

算法常见划分依据主要区别
ID3信息增益比较划分后熵减少了多少，容易偏好取值很多的特征
C4.5信息增益率在信息增益基础上考虑分支的数量和规模，减轻对多取值特征的偏好
CART 分类树Gini 不纯度下降比较划分前后的 Gini 不纯度，采用二叉划分；CART 也能用于回归

例如，一个节点有 4 个正例、4 个负例：

  • 分成“全是正例”和“全是负例”两个子节点，类别就完全分开了。
  • 如果两个子节点仍然各有一半正例、一半负例，类别的混杂程度就没有改善。

计算划分后的不纯度时，要按各子节点的样本数加权。C4.5 还会先按信息增益筛选候选特征，再比较增益率，避免选中比值很高、实际改善却很小的特征。

预测时，样本沿分支落入一个叶子，通常取叶内占比最高的类别作为预测，也可以用各类别的占比估计类别概率。

scikit-learn 的树使用优化的 CART 算法，选择 entropy 准则不会把它变成完整的 ID3 或 C4.5。

1.2 回归树：叶子为什么输出均值

考虑平方误差。叶子区域 RR 中的样本都输出常数 cc，最优值满足：

cR=arg⁡min⁡c∑i:xi∈R(yi−c)2=1∣R∣∑i:xi∈Ryi.c_R=\arg\min_c\sum_{i:x_i\in R}(y_i-c)^2 =\frac{1}{|R|}\sum_{i:x_i\in R}y_i.

这里 ∣R∣|R| 表示落入该叶子的样本数。对目标函数求导并令其为 0，就得到叶内目标值的均值。

训练时，枚举候选特征与切分点，选择使两个子节点平方误差之和最小的划分：

∑i:xi∈RL(yi−cRL)2+∑i:xi∈RR(yi−cRR)2.\sum_{i:x_i\in R_L}(y_i-c_{R_L})^2 +\sum_{i:x_i\in R_R}(y_i-c_{R_R})^2.

例如，某节点目标值为 1,2,8,91,2,8,9，不分裂时输出均值 5，平方误差和为 50。假设某个特征阈值能把前两个与后两个分开，左右叶子分别输出 1.5 和 8.5，误差和降为 1。

叶子输出均值依赖平方误差这一条件。 使用绝对误差时，最优常数是中位数。

1.3 剪枝与适用边界

  • 预剪枝：生长时限制最大深度、叶节点最少样本数或最低不纯度下降，提前停止划分。
  • 后剪枝：先生成较大的树，再依据复杂度惩罚等准则删减分支；剪枝强度通过验证选择。

树越深、叶子中的样本越少，越容易拟合训练数据中的噪声。剪枝限制模型复杂度，过度剪枝则会欠拟合。单棵深树对训练样本扰动往往敏感，后面的 Bagging 用多棵树缓解这一问题。

基于单特征阈值的树通常无需标准化，因为保持数值顺序的缩放不改变可选划分。缺失值、类别特征如何处理，仍取决于具体实现。

2. Bagging 与随机森林

2.1 分别训练，再汇总预测

Bagging 是 Bootstrap Aggregating：通过自助采样生成多份训练集，再汇总模型预测。经典流程为：

  1. 从含 nn 个样本的训练集中，有放回抽取 nn 次，得到一份训练集。
  2. 在这份数据上训练一个基学习器；重复采样与训练，得到 BB 个模型。
  3. 回归任务通常取预测均值；分类任务可进行多数投票或汇总类别概率。

每份训练集允许同一样本出现多次。各模型不依赖前一个模型的训练结果，因此可以并行训练。

Bagging 不限定基学习器必须是树，也不要求每个模型都很弱。深树这类对样本扰动敏感的模型，通常更能从平均预测中受益。

对回归，集成预测为 fˉ(x)=1B∑b=1Bfb(x)\bar f(x)=\frac1B\sum_{b=1}^{B}f_b(x)。固定输入 xx，考察训练样本与采样变化时预测的波动。若各模型预测的方差都为 σ2\sigma^2，两两相关系数都为 ρ\rho，则：

Var⁡[fˉ(x)]=ρσ2+1−ρBσ2.\operatorname{Var}[\bar f(x)] =\rho\sigma^2+\frac{1-\rho}{B}\sigma^2.

模型越相似，增加模型数量带来的降方差收益就越有限。 例如 ρ=1\rho=1 时，平均不会降低方差。这也是随机森林还要引入特征随机性的原因。

2.2 随机森林：每个节点重新选候选特征

经典随机森林结合两种随机性：

  • 样本随机性：每棵树使用各自的 Bootstrap 训练集。
  • 特征随机性：每个节点分裂时，重新随机选取一部分候选特征，再从中寻找较好的划分。

随机选特征发生在每次节点分裂时，不是整棵树始终只使用最初选定的一组特征。 这能减少强特征反复主导所有树、导致预测高度相似的情况。

回归森林对各树预测取平均。分类森林可进行多数投票；scikit-learn 的实现先平均各树的类别概率，再选择概率最大的类别。

2.3 OOB：用每棵树没见过的样本评估

有放回抽取 nn 次时，某个样本一次都没被抽中的概率为：

P(OOB)=(1−1n)n⟶e−1≈36.8%.P(\text{OOB})=\left(1-\frac1n\right)^n\longrightarrow e^{-1}\approx36.8\%.

因此，大样本下每棵树平均见到约 63.2% 的不同训练样本，其余样本称为这棵树的包外样本。这是期望比例，每次采样的实际比例会波动；抽取次数不等于 nn 时也不能直接套用 36.8%。

计算包外误差时，对每个训练样本，只汇总没有抽到过它的树的预测，再与真实标签比较。每个样本对应的树集合不同，不能直接拿整座森林预测训练集充当 OOB 结果。

OOB 可以在不另划验证集的情况下估计泛化误差。不过，每个样本的 OOB 预测只使用约三分之一的树；树数较少时，汇总预测不如完整森林稳定，误差估计可能偏高。

3. AdaBoost：提高分错样本的权重

AdaBoost 根据上一轮的分类结果调整样本权重，再训练下一个分类器。 分错的样本在下一轮训练中占据更大权重。GBDT 则通过改变新树的拟合目标来改进模型，下一节再展开。

考虑经典二分类 AdaBoost，yi∈{−1,+1}y_i\in\{-1,+1\}，第 tt 轮分类器为 ht(x)∈{−1,+1}h_t(x)\in\{-1,+1\}。初始化 D1(i)=1n\displaystyle D_1(i)=\frac1n，其中 Dt(i)D_t(i) 是归一化后的样本权重。

先训练，再计算该分类器的权重。 用当前样本权重训练 hth_t，计算加权错误率 ϵt\epsilon_t 和投票权重 αt\alpha_t：

ϵt=∑i=1nDt(i)1[ht(xi)≠yi],αt=12ln⁡1−ϵtϵt.\begin{aligned} \epsilon_t&=\sum_{i=1}^{n}D_t(i)\mathbf1[h_t(x_i)\ne y_i],\\ \alpha_t&=\frac12\ln\frac{1-\epsilon_t}{\epsilon_t}. \end{aligned}

1\mathbf1 表示条件成立取 1，否则取 0。这里要求 0<ϵt<0.50<\epsilon_t<0.5，此时 αt>0\alpha_t>0，错误率越低，该分类器的投票权重越大。

若错误率为 0，可结束训练；若错误率达到或超过 0.5，则停止本轮或调整基学习器。

接着更新样本权重，让下一轮更关注分错的样本：

Dt+1(i)=Dt(i)exp⁡[−αtyiht(xi)]Zt.D_{t+1}(i)=\frac{D_t(i)\exp[-\alpha_t y_i h_t(x_i)]}{Z_t}.

ZtZ_t 是分子的总和，用来保证新权重之和为 1。分对时乘 e−αte^{-\alpha_t}，分错时乘 eαte^{\alpha_t}，因此分错样本相对于分对样本的权重提高。

例如，4 个等权样本中分错 1 个，ϵt=0.25\epsilon_t=0.25。更新后，错例权重变为 12\displaystyle\frac12，其余样本各为 16\displaystyle\frac16，这一个错例就占下一轮训练权重的一半。

重复 TT 轮，最终按分类器权重投票：

y^(x)=sign⁡(∑t=1Tαtht(x)).\hat y(x)=\operatorname{sign}\left(\sum_{t=1}^{T}\alpha_t h_t(x)\right).

得分为 0 时需约定类别。持续提高难例权重，也可能放大错误标签或异常样本的影响。

4. GBDT：让新树拟合损失的负梯度

GBDT（梯度提升决策树）使用 CART 回归树，逐轮学习已有模型还需要怎样修正。旧树保持不变，新树的输出累加到已有模型上。

设训练集为 (xi,yi)(x_i,y_i)，共有 NN 个样本，训练 MM 轮。用 Fm(x)F_m(x) 表示第 mm 轮后的累计模型，fm(x)f_m(x) 表示本轮新增的树。下面先推导学习率为 1 的过程，再加入学习率。

4.1 初始化：求使总损失最小的常数

初始模型对所有样本都输出同一个常数 cc，选择使总损失最小的值：

F0(x)=arg⁡min⁡c∑i=1NL(yi,c).F_0(x)=\arg\min_c\sum_{i=1}^{N}L(y_i,c).

取平方损失 L(yi,c)=12(yi−c)2L(y_i,c)=\frac12(y_i-c)^2。 总损失是关于 cc 的凸函数，可以直接对 cc 求导：

∑i=1N∂L(yi,c)∂c=∑i=1N∂[12(yi−c)2]∂c=∑i=1N(c−yi).\sum_{i=1}^{N}\frac{\partial L(y_i,c)}{\partial c} =\sum_{i=1}^{N}\frac{\partial[\frac12(y_i-c)^2]}{\partial c} =\sum_{i=1}^{N}(c-y_i).

令导数等于 0：

∑i=1N(c−yi)=0⟹Nc=∑i=1Nyi⟹c=1N∑i=1Nyi.\sum_{i=1}^{N}(c-y_i)=0 \quad\Longrightarrow\quad Nc=\sum_{i=1}^{N}y_i \quad\Longrightarrow\quad c=\frac1N\sum_{i=1}^{N}y_i.

因此，平方损失下的初始模型为 F0(x)=cF_0(x)=c，即所有训练样本标签值的均值。

4.2 第 m 轮：计算负梯度、训练新树、更新模型

对 m=1,2,…,Mm=1,2,\ldots,M，依次执行下面四步。训练本轮新树时，上一轮的累计模型 Fm−1F_{m-1} 保持不变。

A. 计算每个样本的负梯度

对可微损失，计算损失对当前预测值的负梯度，作为本轮的拟合目标：

rmi=−[∂L(yi,F(xi))∂F(xi)]F=Fm−1,i=1,2,…,N.r_{mi}=-\left[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}\right]_{F=F_{m-1}}, \qquad i=1,2,\ldots,N.

rmir_{mi} 也称伪残差。正值表示增大当前预测可以使损失局部下降，负值表示应减小预测。代入前面的平方损失，得到：

rmi=−(Fm−1(xi)−yi)=yi−Fm−1(xi).r_{mi}=-\bigl(F_{m-1}(x_i)-y_i\bigr)=y_i-F_{m-1}(x_i).

只有在上述平方损失下，负梯度才直接等于普通残差 yi−Fm−1(xi)y_i-F_{m-1}(x_i)。 其他损失需要使用相应的负梯度。

B. 用负梯度作为新的训练目标，训练一棵回归树

保持输入特征 xix_i 不变，用 rmir_{mi} 替代标签 yiy_i，即使用训练对 (xi,rmi)(x_i,r_{mi})，按平方误差训练一棵 CART 回归树。

设本轮树有 JJ 个叶子，对应区域为 RjmR_{jm}，j=1,2,…,Jj=1,2,\ldots,J。这一步确定树怎样划分样本；各叶子最终输出多少，还要按原损失函数计算。

C. 对每个叶子计算最佳修正量

同一叶子中的样本共享一个修正量 γjm\gamma_{jm}。固定叶子区域后，选择使这些样本总损失最小的值：

γjm=arg⁡min⁡γ∑i:xi∈RjmL(yi,Fm−1(xi)+γ).\gamma_{jm}=\arg\min_\gamma \sum_{i:x_i\in R_{jm}}L\bigl(y_i,F_{m-1}(x_i)+\gamma\bigr).

平方损失下，对 γ\gamma 求导并令导数为 0：

∂∂γ∑i:xi∈Rjm12(yi−Fm−1(xi)−γ)2=∑i:xi∈Rjm(Fm−1(xi)+γ−yi)=0.\frac{\partial}{\partial\gamma} \sum_{i:x_i\in R_{jm}}\frac12\bigl(y_i-F_{m-1}(x_i)-\gamma\bigr)^2 =\sum_{i:x_i\in R_{jm}}\bigl(F_{m-1}(x_i)+\gamma-y_i\bigr)=0.

整理得：

γjm=1∣Rjm∣∑i:xi∈Rjm(yi−Fm−1(xi)).\gamma_{jm}=\frac{1}{|R_{jm}|} \sum_{i:x_i\in R_{jm}}\bigl(y_i-F_{m-1}(x_i)\bigr).

这里 ∣Rjm∣|R_{jm}| 表示落入该叶子的样本数。平方损失下，叶子的最佳修正量就是叶内残差的均值。 其他损失按对应目标求解或近似更新；这一过程称为叶子上的线搜索。

D. 更新强学习器

把新树各叶子的修正量加入上一轮模型：

Fm(x)=Fm−1(x)+∑j=1JγjmI(x∈Rjm).F_m(x)=F_{m-1}(x)+\sum_{j=1}^{J}\gamma_{jm}I(x\in R_{jm}).

II 是指示函数：样本落入 RjmR_{jm} 时取 1，否则取 0。一次预测只会落入新树的一个叶子，因此求和中只有对应叶子的修正量生效。

4.3 完成 M 轮，得到最终模型

重复上述 A—D 步骤，将每轮更新展开：

FM(x)=F0(x)+∑m=1M∑j=1JγjmI(x∈Rjm).F_M(x)=F_0(x)+\sum_{m=1}^{M}\sum_{j=1}^{J}\gamma_{jm}I(x\in R_{jm}).

内层求和取出样本在本轮树中对应的叶子值，外层求和累加所有轮次的修正。最终预测就是初始值加上各棵树对应叶子的修正量。这里用 JJ 表示每棵树的叶子数；各轮叶子数不同时，将内层求和上限换成 JmJ_m 即可。

4.4 加入学习率，控制每棵树的贡献

学习率缩小每轮采用的修正量，是 GBDT 控制过拟合的一种方法。令 0<η≤10<\eta\le1，每轮更新与最终模型分别为：

Fm(x)=Fm−1(x)+η∑j=1JγjmI(x∈Rjm),FM(x)=F0(x)+η∑m=1M∑j=1JγjmI(x∈Rjm).\begin{aligned} F_m(x)&=F_{m-1}(x)+\eta\sum_{j=1}^{J}\gamma_{jm}I(x\in R_{jm}),\\ F_M(x)&=F_0(x)+\eta\sum_{m=1}^{M}\sum_{j=1}^{J}\gamma_{jm}I(x\in R_{jm}). \end{aligned}

例如叶子求得输出 2，η=0.1\eta=0.1 时只累加 0.2。学习率在每一轮更新时生效，下一轮的负梯度也根据缩小更新后的模型重新计算。

学习率越小，每棵树的贡献越小，通常需要更多的树；学习率较大时，通常较少轮数就能达到相近的训练误差，但每轮更新也更大。实际应结合树的复杂度与验证表现，选择学习率和轮数。

4.5 用三个样本看一轮更新

取平方损失、学习率为 1。3 个样本的目标值依次为 2,4,82,4,8，初始预测均为 143\displaystyle\frac{14}{3}。假设某个特征阈值把前两个样本划入左叶子，第三个划入右叶子。新树按叶内残差的均值输出修正量：

计算步骤样本 1样本 2样本 3
目标值 yiy_i224488
初始预测 F0F_0143\displaystyle\frac{14}{3}143\displaystyle\frac{14}{3}143\displaystyle\frac{14}{3}
残差 yi−F0y_i-F_0−83\displaystyle-\frac83−23\displaystyle-\frac23103\displaystyle\frac{10}{3}
新树输出 f1f_1−53\displaystyle-\frac53−53\displaystyle-\frac53103\displaystyle\frac{10}{3}
更新后预测 F0+f1F_0+f_1333388

左叶子的输出为：

−83−232=−53.\frac{-\dfrac83-\dfrac23}{2}=-\frac53.

右叶子只有一个样本，输出为 103\displaystyle\frac{10}{3}。相加后剩余残差为 −1,1,0-1,1,0：新树修正了两个区域的平均误差，后续树若能把前两个样本分开，还可继续修正。

4.6 分类任务仍然累加实数得分

分类 GBDT 的树仍然输出实数修正量，累加得到得分后再转成概率。 对二分类，取 yi∈{0,1}y_i\in\{0,1\}，用 sigmoid 将得分 F(x)F(x) 转为正类概率：p(x)=σ(F(x))=11+e−F(x)\displaystyle p(x)=\sigma(F(x))=\frac{1}{1+e^{-F(x)}}。

采用二元对数损失时，损失与对应的伪残差为：

L(yi,F)=−yiln⁡p−(1−yi)ln⁡(1−p),p=σ(F),rmi=yi−pi,pi=σ(Fm−1(xi)).\begin{aligned} L(y_i,F)&=-y_i\ln p-(1-y_i)\ln(1-p),\qquad p=\sigma(F),\\ r_{mi}&=y_i-p_i,\qquad p_i=\sigma(F_{m-1}(x_i)). \end{aligned}

例如，同样预测正类概率为 0.8，正例的伪残差是 1−0.8=0.21-0.8=0.2，负例则是 0−0.8=−0.80-0.8=-0.8。新树据此学习提高或降低正类得分，叶子输出仍按原来的对数损失确定或近似求解。最终将累加得分转成概率，再按阈值决定类别。

用回归树拟合负梯度，与用什么损失评价最终预测，是两个层次。 因而“采用 CART 回归树”不等于“整个分类模型优化平方误差”。

XGBoost 在这一加法模型上引入二阶损失信息与显式复杂度惩罚。

评论

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。