机器学习 | 西瓜书学习笔记 ch04：决策树

4.1 基本流程

• 每个非叶子结点，是对某个属性的测试
• 每个叶子结点，是判定结果

决策树算法：递归结构

递归边界：

• 当前结点包含的样本，都属于同一类别，无需划分
• 当前属性集为空（即：需要做的属性测试全做完了，没必要再分），或者所有样本在所有属性上取值相同（即：产生了样本冲突，没办法再分）
• 当前结点包含的样本集合为空（即：边界条件，没必要分 / 没办法分都有）

4.2 划分选择

关键：如何选择最优划分属性

希望决策树的分支结点所包含的样本尽可能属于同一类别，即：结点的 “纯度” (purity) 越来越高

• 经典的属性划分方法

  • 信息增益（information gain）

    • 信息熵：度量样本集合纯度最常用的一种指标

    • $Ent\left(D\right)=-\sum _{k=1}^{\mid y\mid }{p}_{k}lo{g}_2{p}_k$Ent(D)=−k=1∑∣y∣​pk​log2​pk​

    • 熵（定义）：表示信息量，概率越小，信息量越大（举例：概率越小，表示越不容易发生，但是一旦发生，信息量就很大）

    • 计算信息熵时约定：若 p = 0，则 Ent = 0

    • Ent(D) 的最小值为 0，最大值为
      $lo{g}_2\mid y\mid$log2​∣y∣

    • 按子树加权

    • 信息增益

    • $Gain(D,a)=Ent\left(D\right)-\sum _{v=1}^V\frac{\mid D^v\mid }{\mid D\mid }Ent\left(D^v\right)$Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)

    • 一般而言，信息增益越大，则意味着是以属性 a 来进行划分所获得的 "纯度提升" 越大

    • 选取信息增益最大的属性为划分属性，好处：属性集变小，数据集变小(指数级下降)

    • 存在问题：若把 “编号” 作为一个候选划分属性，则信息增益一般远大于其他属性.（信息增益对可取值数目较多的属性有所偏好）

  • 增益率（gain ratio）

    • 定义：对某一个属性的取值个数的信息

    • $Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV\left(a\right)}$Gain_ratio(D,a)=IV(a)Gain(D,a)​

      其中
      $IV\left(a\right)=-\sum _{v=1}^V\frac{\mid D^v\mid }{\mid D\mid }lo{g}_2\frac{\mid D^v\mid }{\mid D\mid }$IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​
      称为属性 a 的 "固有值" (intrinsic value). 属性 a 的可能取值数目越多(即 V 越大)，则 IV(a) 的值通常越大

    • 存在问题：增益率准则对可取值数目较少的属性有所偏好

  • 基尼指数（Gini index）

    • 数据集 D 的纯度可用基尼值来度量：

    • $Gini\left(D\right)=\sum _{k=1}^{\mid y\mid }\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-\sum _{k=1}^{\mid y\mid }{p}_k^2$Gini(D)=k=1∑∣y∣​k′̸​= k∑​pk​pk′​=1−k=1∑∣y∣​pk2​

    • 定义：Gini(D) 反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率. 因此，Gini(D) 越小，则数据集 D 的纯度越高.

    • 属性 a 的基尼指数定义为

    • $Gini\_index(D,a)=\sum _{y=1}^V\frac{\mid D^v\mid }{\mid D\mid }Gini\left(D^v\right)$Gini_index(D,a)=y=1∑V​∣D∣∣Dv∣​Gini(Dv)

    • 在候选属性集合 A 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即
      $a_{\ast }={argmin}_{x\in A}Gini\_index(D,a)$a∗​=arg minx∈A​Gini_index(D,a)

4.3 剪枝处理

• 为什么剪枝

  • 剪枝是决策树学习算法针对 “过拟合” 的主要手段
  • 避免因决策分支过多，因训练集自身特点被误认为所有数据都具有的一般性质而导致的过拟合

• 剪枝的基本策略

  • 预剪枝
    • 判断结点是否可以分，未划分前，看一下现有验证集上的精度，划分后精度大于划分前精度，则进行划分.（相等不进行划分）
    • 优点
      • 降低过拟合风险
      • 显著减少训练时间和测试时间开销
    • 缺点
      • 欠拟合风险：预剪枝基于“贪心”本质禁止以后可能导致性能显著提高的分支，因此会带来欠拟合风险
  • 后剪枝
    • 看一下现有验证集上的精度，划分后精度大于划分前精度，则进行剪枝
    • 优点
      • 保留更多分支，欠拟合风险小，泛化性能往往优于预剪枝
    • 缺点
      • 效率低
      • 训练时间开销大

• 判断决策树泛化性能是否提升的方法

  • 留出法：预留一部分数据用作 “验证集” 以进行性能评估

4.4 连续与缺失值

• 连续属性离散化（二分法）

  • 第一步：连续属性在集合 D 上出现 n 个不同取值，从小到大排列。只有 n-1 种划分（每两个连续之间，划一刀）
  • 第二步：把区间中位点作为候选划分点，选取最优划分点进行样本集合的划分

• 缺失值处理

  • 不完整样本：样本某些属性值缺失
  • 方法
    • 训练：样本属性缺失的那一类不计入计算，其他不缺失的属性，还要计入计算，不是完全扔掉这些样本
    • 测试：缺失的属性，当成每一种划分都可以进入，即看成均值

4.5 多变量决策树

• 单变量决策树分类边界：轴平行(axis-parallel)
• 多变量决策树：非弧线
  • 非叶结点：不仅对某个属性，而是对属性的线性组合进行测试
  • 试图建立一个合适的线性分类器