第 11 章 决策树

决策树是一类基于规则划分的模型。它把样本一次次分到更小的区域中，直到叶子节点给出预测结果。随机森林是在多棵决策树基础上形成的集成模型。

本章先讲单棵决策树，再讲 Bagging 和随机森林。

11.1 决策树是什么

决策树可以看成一组 if-else 规则。

例如判断一个用户是否会购买商品：

年龄 <= 30 ?
  是 -> 收入 <= 8000 ?
  否 -> 是否有房 ?

树中有三类节点：

节点	含义
根节点	第一次划分的位置
内部节点	中间判断条件
叶子节点	最终预测结果

决策树既可以做分类，也可以做回归。

任务	叶子节点输出
分类	类别或类别比例
回归	叶子区域内样本标签的平均值

11.2 纯度

训练决策树时，每一步都要选择一个特征和一个划分条件。目标是让划分后的子节点更“纯”。

如果一个节点里几乎全是同一类样本，这个节点就很纯；如果各类样本混在一起，节点就不纯。

分类树常用的信息增益、信息增益率和基尼指数，本质上都是在衡量划分前后纯度是否变好。

11.3 熵

熵衡量类别混乱程度。设一个节点中有 $K$ 个类别，第 $k$ 类比例为 $p_k$，熵定义为：

$$H(D)=-\sum _{k=1}^K{p}_k{\log }_2{p}_k$$

如果节点中所有样本都属于同一类，则熵为 0，表示最纯。

如果各类别比例接近，熵较大，表示更混乱。

11.4 信息增益

信息增益表示一次划分让熵减少了多少。

设用特征 $A$ 把数据集 $D$ 划分成若干子集 $D_1,D_2,\dots ,D_v$，则划分后的加权熵为：

$$\sum _{j=1}^v\frac{|D_j|}{|D|}H(D_j)$$

信息增益定义为：

$$Gain(D,A)=H(D)-\sum _{j=1}^v\frac{|D_j|}{|D|}H(D_j)$$

信息增益越大，说明划分后节点越纯。

ID3 决策树使用信息增益选择划分特征。

11.5 信息增益率

信息增益有一个问题：它偏好取值很多的特征。例如“用户 ID”几乎可以把每个样本单独分开，信息增益可能很大，但这种划分没有泛化意义。

信息增益率用特征本身的划分复杂度做修正：

$$GainRatio(D,A)=\frac{Gain(D,A)}{IV(A)}$$

其中：

$$IV(A)=-\sum _{j=1}^v\frac{|D_j|}{|D|}{\log }_2\frac{|D_j|}{|D|}$$

C4.5 决策树使用信息增益率作为重要依据。

11.6 基尼指数

基尼指数也是衡量节点不纯度的指标：

$$Gini(D)=1-\sum _{k=1}^K{p}_k^2$$

如果节点全属于同一类，某个 $p_k=1$，基尼指数为 0。

如果类别混杂，基尼指数变大。

对一次划分，划分后的基尼指数为：

$$Gini(D,A)=\sum _{j=1}^v\frac{|D_j|}{|D|}Gini(D_j)$$

CART 分类树通常选择让划分后基尼指数最小的特征和阈值。

11.7 连续特征如何划分

连续特征不能直接像离散特征那样按取值分叉。常见做法是选择一个阈值。

例如对年龄特征，可以尝试：

年龄 <= 25
年龄 <= 30
年龄 <= 35

对每个候选阈值计算信息增益或基尼指数，选择最好的阈值。

CART 树通常使用二叉划分，每次把样本分成两部分：

$$A\le t$$

和：

$$A>t$$

11.8 剪枝

决策树如果一直生长，很容易把训练集细节记住。剪枝用于限制树的复杂度。

预剪枝是在建树过程中提前停止，例如：

• 限制最大深度。
• 限制叶子节点最小样本数。
• 限制节点继续划分所需的最小信息增益。

后剪枝是先生成完整树，再从下往上删除一些分支。后剪枝通常借助验证集判断删除分支后泛化效果是否更好。

11.9 Bagging

Bagging 是 Bootstrap Aggregating 的缩写。

Bootstrap 指有放回抽样。给定训练集，每次随机抽取 $m$ 个样本，抽完放回，因此同一个样本可能被抽到多次，也可能一次都没被抽到。

Bagging 的流程是：

1. 用 Bootstrap 生成多个训练子集。
2. 在每个子集上训练一个基学习器。
3. 分类任务用投票汇总。
4. 回归任务用平均值汇总。

Bagging 的主要作用是降低方差。单棵决策树对训练数据很敏感，而多棵树投票后，单棵树的偶然错误会被抵消。

11.10 随机森林

随机森林是在 Bagging 基础上进一步引入特征随机性。

它的随机性来自两处：

随机性	含义
样本随机	每棵树使用 Bootstrap 样本
特征随机	每个节点只从部分特征中选择划分

如果每棵树都很像，投票意义不大。特征随机性会让树之间差异更大，从而提高集成效果。

随机森林训练流程：

1. 生成多个 Bootstrap 数据集。
2. 每个数据集训练一棵决策树。
3. 每个节点划分时随机抽取部分特征参与选择。
4. 得到多棵树组成森林。

预测时：

任务	输出方式
分类	多数投票
回归	多棵树预测值平均

11.11 决策树和随机森林的特点

模型	优点	缺点
决策树	可解释、无需特征缩放、能处理非线性	容易过拟合
随机森林	稳定、泛化好、可估计特征重要性	可解释性下降、模型更大

决策树适合解释规则，随机森林适合追求稳定效果。随机森林属于 Bagging 思想，重点是降低方差；GBDT、XGBoost、LightGBM 属于 Boosting 思想，重点是逐步修正前一轮模型的错误。