• 决策树模型的产生可以追溯至20世纪60年代。在80年代，ID3、C4.5、CART等决策树算法相继被提出。

决策树（Decision Tree）

  • 什么是决策树？顾名思义，决策树的核心结构是一棵二叉树，包括根、内节点（分裂变量）与叶子节点（结果）。测试样本通过逐层经过分裂变量的判别，最终被划分到某个叶子节点上，得到输出结果。

决策树的学习过程

  • 决策树构建的核心问题：每一层的分裂变量如何选择？
    • 原则：最大化“纯度”或最小化“不纯度”。
  • 决策树大多数情况下都用于分类预测问题。对于分类问题，最主要的“不纯度”衡量的指标是信息熵（Information Entropy）。
    • 计算方法：设一组样本中总共有nn个类别，每一类的占比为pkp_k，则其信息熵为H(p)=−∑k=1npklog⁡pk\displaystyle H(p)=-\sum_{k=1}^n p_k\log p_k。（注：约定0log⁡0=00\log 0=0）
    • 从统计学角度，信息熵可以看作随机变量YY的分布与“均匀的”多项分布的接近程度。
    • 一棵决策树总的信息熵是每个叶子结点的信息熵按叶子结点样本量加权求和。
    • 其他“不纯度”衡量指标有：
      • Gini指数：Gini(p1,⋯ ,pn)=∑k=1npk(1−pk)=1−∑k=1npk2\displaystyle \text{Gini}(p_1,\cdots,p_n)=\sum_{k=1}^n p_k(1-p_k)=1-\sum_{k=1}^n p_k^2；【随机抽取两个观测值其类别不一样的概率】
      • 错分率（Misclassification Rate）：Err(p1,⋯ ,pn)=1−max⁡{p1,⋯ ,pn}\text{Err}(p_1,\cdots,p_n)=1-\max\{p_1,\cdots,p_n\}
  • 得到信息熵后，就可以计算决策树的信息增益（Information Gain）： Gain=Hroot−(N1N1+N2Hleft+N2N1+N2Hright)\text{Gain}=H_{\text{root}}-\left(\frac{N_1}{N_1+N_2}H_{\text{left}}+\frac{N_2}{N_1+N_2}H_{\text{right}}\right) 其中N1,N2N_1,N_2分别为左右子节点的样本数。

决策树生成方法

  1. 从根节点开始，所有训练样本都在根节点
  2. 计算所有特征的信息增益，并选择具有最高信息增益的特征
  3. 根据选定的特征拆分数据集，并创建树的左右分支
  4. 重复拆分过程（递归），直到满足停止条件。停止条件可能是以下条件之一：
    1. 叶子结点内均为同类
    2. 达到最大深度
    3. 纯度改进（信息增益）低于阈值
    4. 节点中样本数小于阈值
  • 如何处理多类别变量？
    • 构造多叉树
    • 构造哑变量（0-1变量）

回归树

  • 决策树如何处理连续型变量？可以设置某个阈值（一般取样本值的中间数），再选择信息增益最大的。
    • 一般先对某个特征的所有值进行排序，然后顺序扫描，确定最佳阈值。
  • 信息熵度量：对叶节点的所有样本计算均值和方差，通过方差度量“不纯度”。

决策树的剪枝

  • 前面我们提到，决策树可以通过设置停止条件控制其复杂度，进而防止过拟合。然而，这种控制方式往往无法实现最优分类。于是我们提出另一种优化方法：先让先让决策树尽情生长，记最大的树为Tmax⁡T_{\max}，再进行“修枝”。
  • 1984年，Breiman等人在CART中就使用了代价-复杂度剪枝算法（Cost-Complexity Pruning，CCP），其核心优化（损失）函数为： min⁡TR(T)+α⋅∣T∣\min_T R(T)+\alpha\cdot|T| 其中R(T)R(T)表示当前树的所有叶子结点训练误差总和（分类树为信息熵损失，回归树为均方误差损失），∣T∣|T|表示树的复杂度（可用叶子节点个数表示），α\alpha为学习参数，调节二者权重。
  • 对于每个内部节点tt，记以其为根节点的子树为T(t)T(t)，则
    • 剪枝前CCP为R(T(t))+α∣T(t)∣R(T(t))+\alpha|T(t)|；
    • 剪枝（将整棵子树剪去）后CCP变为R(t)+αR(t)+\alpha。
  • 由此可得剪枝的临界点g(t)=R(t)−R(T(t))∣T(t)∣−1g(t)=\dfrac{R(t)-R(T(t))}{|T(t)|-1}：
    • 当α\alpha充分小时，T(t)T(t)更可取，不剪枝；
    • 当α\alpha增大，超过临界点时，tt更可取，对T(t)T(t)进行剪枝。
  • 对固定的α\alpha，一定存在使得损失函数最小的子树，将其表示为TαT_\alpha。TαT_\alpha在损失函数最小的意义下是最优的，且可以证明这样的最优子树是唯一的。
  • Breiman等证明：可以用递归的方法对树进行剪枝。
    • 将α\alpha从小增大，产生一系列的区间；
    • 剪枝得到的子树序列对应着区间α∈[αi,αi+1)\alpha\in[\alpha_i,\alpha_{i+1})的最优子树序列{T0,T1,⋯ ,Tn}\{T_0, T_1, \cdots , T_n\}中的子树是嵌套的。【T0T_0对应最大的树，TnT_n对应只有根节点的树】

    即：若0≤α1<α20\leq \alpha_1< \alpha_2，则Tα2T_{\alpha_2}为Tα1T_{\alpha_1}的子树。

  • 由此得到CART剪枝算法：
    • 输入：CART算法生成的决策树T0T_0
    1. 初始化k=0,T=T0,α=∞k = 0, T = T_0,\alpha = \infty
    2. 自下而上地对各个内部节点tt计算g(t)=R(t)−R(T(t))∣T(t)∣−1,α=min⁡{α,g(t)}g(t) = \dfrac{R(t) - R(T(t))}{|T(t)| - 1} ,\quad \alpha = \min\{\alpha, g(t)\}
    3. 自上而下地访问内部节点tt，如果有g(t)=αg(t) = \alpha进行剪枝，得到新的树TT
    4. 更新k=k+1,αk=α,Tk=Tk = k + 1, \alpha_k = \alpha, T_k = T
    5. 递归运行2~4，得到树T0,T1,T2,⋯ ,TnT_0, T_1, T_2, \cdots, T_n，采用交叉验证法选最优子树。

总结

  • 决策树本质上是将“特征空间”进行递归分割，每次总是沿着与某个变量xx轴平行的方向进行切割，切成矩形区域。
  • 在数学上，决策树可看作“分段常值函数” f(X)=∑m=1McmI(X∈Rm)f(X) = \sum_{m=1}^M c_m I(X \in R_m) 其中cmc_m是样本落入第mm个子空间时对目标变量的预测值，MM是子空间总个数。
  • 关于ID3，C4.5和CART的比较：
    算法 支持模型 树结构 划分特征选择 连续值处理 缺失值处理 剪枝 特征属性多次使用
    ID3 分类 多叉树 信息增益 不支持 不支持 不支持 不支持
    C4.5 分类 多叉树 信息增益率 支持 支持 支持 不支持
    CART 分类、回归 二叉树 基尼系数、均方差 支持 支持 支持 支持
    • 补充：信息增益率为信息增益除以分裂信息熵（特征自身熵）。分裂信息熵的公式为：−∑i=1n∣Di∣∣D∣log⁡2∣Di∣∣D∣\displaystyle - \sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}，其中nn为特征取值的个数。
    • 采用多分枝策略时，信息增益倾向于选择取值较多的特征（如“身份证号”），这类特征可能导致过拟合。信息增益率通过分母对多值特征进行惩罚，平衡特征选择的复杂性与效果。
  • 决策树的优缺点
    • 优点：解释性很强，尤其对于非专业人士易读；有些人认为决策树相较于回归更接近于人类决策过程
    • 缺点：决策树通常预测准确性较低【需结合其他方法（如集成模型）优化】