C05. 决策树 (decision tree)

• 决策树模型
  • 决策树是一种基本方法，用于分类与回归。
    • 本章主要讨论的是分类决策树。
  • 分类决策树模型
    • 定义 : 是基于特征对实例进行分类的树形结构。
    • 模型的组成结构
      • 结点 (node)
        • 内部结点 (internal node)
        • 叶结点 (leaf node)
      • 有向边 (directed edge)
    • 分类决策树可以转换成一个 if-then 规则的集合；
      • 决策树的根结点到叶结点的每一条路径构建一条规则；
      • 路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
      • 重要的性质 : 互斥并且完备，即全覆盖。
        • 覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
    • 也可以看作是定义在特征空间与类空间上的条件概率分布。
      • 这个条件概率分布定义在特征空间的一个划分上，
      • 将特征空间划分为互不相交的单元或区域，
      • 并在每个单元定义一个类的概率分布就构成了一个条件概率分布。
      • 决策树分类时，将结点的实例分到条件概率大的类中。
    • 主要优点 : 可读性强，分类速度快。
• 决策树学习
  • 学习目的
    • 根据给定的训练数据集，构建一个与训练数据拟合很好，并且复杂度小的决策树，使之能够对实例进行正确的分类。
    • 决策树与训练数据的矛盾较小，同时还具有较好的泛化能力。
    • 也可以看作由训练数据集估计条件概率模型
      • 模型对训练数据拟合的效果很好；
      • 模型对未知数据有很好的预测。
    • 从所有可能的决策树中选取最优决策树是 NP 完全问题；
      • 现实中采用启发式方法学习次优的决策树。
  • 学习准则 : 损失函数最小化。
    • 损失函数是一种正则化的极大似然函数
  • 学习算法
    • 递归地选择最优特征，并根据该特征对训练数据进行分割，使之对各个数据集有一个最好的分类的过程。
• 决策树的学习算法包括 3 个部分
  • 特征选择
    • 特征选择的目的在于选取对训练数据能够分类的特征，提高决策树学习的效率；
    • 特征选择的关键是其准则
      • 样本集合 D 对特征 A 的信息增益 最大
        • 信息增益定义为集合 D 的经验熵与特征 A 在给定条件下 D 的经验条件熵之差。
          • 熵 : 表示随机变量不确定性的度量。也称为经验熵。
          • 条件熵 : 定义为 X 给定条件下 Y 的条件概率分布的熵对 X 的数学期望。也称为经验条件熵。
        • 信息增益表示得知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度。
        • 信息增益等价于训练数据集中类与特征的互信息。
        • 信息增益依赖于特征，信息增益大的特征具有更强的分类能力。
      • 样本集合 D 对特征 A 的信息增益比 最大
        • 为了避免信息增益对取值较多的特征的偏重，使用信息增益比来代替；
        • 信息增益比 : 特征 A 对训练数据集 D 的信息增益与训练数据集 D 关于特征 A 的值的熵之比。
      • 样本集合 D 的基尼指数 最小
  • 树的生成
    • 计算指标，再根据准则选取最优切分点，从根结点开发，递归地产生决策树。
    • 通过不断地选择局部最优的特征，得到可能是全局次优的结果。
  • 树的剪枝 : 将已经生成的树进行简化的过程。
    • 目的 : 由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。
    • 剪枝的准则 : 极小化决策树整体的损失函数或代价函数，等价于正则化的极大似然估计。
    • 剪枝的分类
      • 预剪枝 : 也叫分支停止准则。在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
      • 后剪枝 : 先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
  • 常用的学习算法
    • ID3: 在决策树的各个结点上应用信息增益准则选择特征，递归地构建决策树。相当于用极大似然法进行概率模型的选择。
    • C4.5: 在决策树的各个结点上应用信息增益比准则选择特征，递归地构建决策树。
    • CART: 既可用于分类，也可用于回归。
      • 等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
      • CART 算法的两个过程
        • 决策树生成 : 基于训练数据集生成决策树，要尽量大；
          • 回归树生成
            • 用平方误差最小准则求解每个单元上的最优输出值。
            • 回归树通常称为最小二乘回归树。
          • 分类树生成
            • 用基尼指数选择最优特征，并决定该特征的最优二值切分点。
            • 算法停止计算的条件
              • 结点中的样本个数小于预定阈值；
              • 样本集的基尼小于预定阈值；
        • 决策树剪枝
          • 用验证数据集对已经生成的树进行剪枝，剪枝的标准为损失函数最小，基于标准选择最优子树。
          • 可以通过交叉验证法对用于验证的独立数据集上的子树序列进行测试，从中选择最优子树。
        • [^Duda,2003] P320, CART 作为通用的框架，定义了 6 个问题
• 决策树的预测
  • 对新的数据，利用决策树模型进行分类。
• 学习总结
  • 算法 (5.1, 5.2, 5.6) + 例题 ( 5.1, 5.2, 5.3, 5.4 ) 通过算法和例题可以增强理解；
  • 损失函数的定义可以进一步参考 “不纯度” 指标 [^Duda,2003] P320, 或 “纯度” 指标 [^周志华，2018] P75
    • “不纯度” 指标是求极小值，可以跟梯度下降法等最优化理论结合。