第四章 决策树
第四章 决策树
  4.1 基本流程
    基本概念
    决策树是基于树结构来进行决策的
    决策树的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略
    西瓜例子
      流程解释
        决策过程的最终结论对应了我们所希望的判定结果
        决策过程中提出的每个判定问题都是对某个属性的“测试”
        每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是上次决策结果的下定范围之内
    决策树的组成
      一个根结点
      若干个内部结点
      若干个叶结点
      叶结点对应于决策结果，其他每个结点则对应于一个属性测试
        每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集
        从根结点到每个叶结点的路径对应了一个判定测试序列
    算法示例
        决策树的生成是一个递归过程
        三种会导致递归返回的情形
          当前结点包含的样本全属于同一类别，无需划分
          当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
            把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别
            利用当前结点的后验分布
          当前结点包含的样本集合为空，不能划分
            把当前结点标记为叶结点，但将其类别设定为父结点所含样本做多的类别
            把父结点的样本分布作为当前结点的先验分布
        如何解决“从A中选择最优划分属性”？
  4.2 划分选择
    核心问题
    划分目的
    如何解决“从A中选择最优划分属性”？
    决策树分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高
    信息熵（information entropy）
      是度量样本集合纯度最常用的一种指标
    西瓜例子
      数据集2.0
    常见方法
      参数设置
      信息增益（information gain）
        公式
            信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大
            经典的ID3决策树算法就是以信息增益来为准则进行属性选择的
        西瓜例子
          计算过程
            例如以“色泽”作为划分依据，则可以建立三个分支其对应的信息熵为
            则“色泽”对应的信息增益为
            其他属性对应的信息增益
        特点
          信息增益准则对可取值数目较多的属性有所偏好
      增益率（gain ratio）
        公式
            属性a的可能取值数目越多（即V越大），则IV（a）得值通常会越大
            著名的C4.5决策算法则是使用“增益率”来选择最优划分属性
        西瓜例子
          计算过程略
        特点
          增益率准则对可取数值数目较少的属性有所偏好
      基尼指数（Gini index）
        公式
            CART决策树使用基尼指数来选择划分属性
            直观来说基尼指数反省了从数据集D中随机抽取两个样本，期类别标记不一致的概率
            基尼指数越小，数据集D的纯度越高
        在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即
  4.3 剪枝处理
    剪枝（pruning）
      在决策树算法中对付“过拟合”的主要手段
      如何理解决策树过拟合？
        决策树分支结点过多，把训练集本生学得太好了，以致于把训练集自身的一些特点当作是所有数据集都具有的一般性质而导致过拟合
      基本策略
        预剪枝（prepruning）
          基本思路：生成决策树的过程中
          预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点
        后减枝（postpruning）
          基本思路：生成决策树之后
          后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶子结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点
      西瓜例子
        数据集
          使用“留出法”对数据集进行划分
        预剪枝
          由于“贪心”造成了欠拟合的风险
          假设以 “脐部” 属性来对训练集进行划分
            假设不进行划分，与使用脐部进行划分验证集精度前后变化
          特点
            预剪枝使得决策树的分支都没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销
            有些分支的当前划分虽然不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能的显著提高
        后减枝
          假设以 “脐部” 属性来对训练集进行划分
            自下而上观察子树替换为叶结点后的验证集精度
          特点
            一般情况下，后剪枝决策树的欠拟合风险很小，繁华性能往往优于预剪枝决策树
            后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多
  4.4 连续与缺失值
    连续值处理
      二分法（bi-partition）
        概念
        步骤
          属性在实际情况中取值是连续的，但是样本集中也是呈现离散的装态，这里的取值不影响划分是指样本集中的离散状态
            即将每个区间的中位点作为候选划分点
      与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性
    缺失值处理
      问题描述
        两个核心问题
        现实任务中常会遇到不完整的样本，即样本的某些属性值缺失
        （1）如何在属性值缺失的情况下进行划分属性选择？
（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
      权重法
        符号定义
          无缺失值的比例
          无缺失样本中第k类所占的比例
          无缺失样本中属性a上取值的样本所占的比例
        公式
          解决的问题（1）
          让同一个样本以不同的概率划分到不同的子结点中去：解决的问题（2）
  4.5 多变量决策树
    单变量决策树（univariate decision tree）
      特点
      轴平行（axis-parallel）：即它的分类边界由若干个与坐标轴平行的分段组成
    多变量决策树（multivariate decision tree）
      非叶结点不再是仅对某个属性进行测试，而是对属性的线性组合进行测试