西瓜书—— 决策树

西瓜书—— 决策树"/>

西瓜书—— 决策树

西瓜书—— 第4 章 决策树

4.1 基本流程

• 核心思想： if… then…

4.2 划分选择

• 目的：如何选择最优划分属性，使叶节点的“纯净”度更高（分支节点所包含的样本尽可能属于同一类别）

4.2.1 信息增益

• 熵：信息量的大小（可能性的多少）
• 信息熵：某个事件所有可能值的熵和；度量样本集合纯度最常用的一个指标
• 条件熵：已知事件各取值下条件熵的期望
• 信息增益：对于已知的事件A来说，事件D的信息增益就是D的信息熵与A事件下D的条件熵之差。
  • 信息增益越大，则属性a来进行划分所获得的“纯度提升”越大
  • 取值较多（种类多）的字段信息熵偏高
  • 事件A对事件D的影响越大，条件熵就越小，信息熵也就越大，则事件D信息熵下降就越多。
  • 根节点的信息增益最大
  • 只适应于离散型因变量
  • 常使用于ID3算法，就是以信息增益为准则来选择划分属性。

4.2.2 信息增益率

• 信息增益率：在信息增益的基础上进行相应的惩罚

• 根节点的信息增益率最大
• 信息增益率对取值数目较少的属性有所偏好
• C4.5 算法不是直接选择增益率最大的属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

4.2.3 基尼指数

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

4.3 剪枝处理

• 目的：解决“过拟合“问题
• 判断泛化能力是否提升：用一部分数据用作“验证集”以进行性能评估
• 剪枝方法和程度对决策树泛化能力的影响相当显著，有实验表明，在数据带有噪声时通过剪枝甚至可将决策树的泛化能力提高25%

4.3.1 预剪枝

• 预剪枝指：在决策树生成过程中，对每个节点在划分前先进行评估，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将其当前节点标记为叶节点。
• 预剪枝使很多分支都没有“展开”，是否“展开”标准为：假如使用最优划分属性划分，若划分后在验证集中的精度反而下降了，则停止该节点的划分
• 预剪枝可显著减少决策树的训练时间开销和测试时间开销

4.3.2 后剪枝

• 后剪枝是先从训练集生成一棵完整的决策树，然后自底向上对非叶节点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化能力提升，则将该子树替换为叶结点
• 后剪枝决策树通常比预剪枝决策树保留了更多的分支。
• 通常，后剪枝决策树的欠拟合风险较小，泛化能力往往优于预剪枝决策树。但训练时间开销较大。
• 后剪枝还可以分为
  • 误差降低剪枝法：
    - 自底向上
    - 在将之过程中需要结合测试数据集对决策树进行验证，如果某个节点的子孙节点都被剪去后，新的决策树在测试集上的误差反而降低了，则表明这个剪枝过程是正确的。
    - 可能导致剪枝过度的问题
    • 悲观剪枝法：
      • 自顶向下
      • 如果剪枝后叶节点的误判率期望在剪枝前叶节点误判率期望的一个标准差内，则认为剪枝合理
    • 代价复杂度剪枝法
      • 通过系数α平衡上升的误判率与下降的复杂度

4.4 连续与缺失值

4.4.1 连续值处理

• 问题：上面讨论是基于离散属性来生成决策树，但现实中会遇到连续属性。

• 解决方法：连续属性离散化，如二分法

• 注意：与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。如：在父节点上使用了“密度<=0.381”,不会禁止在子节点上使用“密度<=0.294”

4.4.2 缺失值

• 样本的某些属性值缺失。

• 处理方法

  • C4.5 算法处理缺失值：将信息增益计算公式推广（我也没太看懂）
  • 其它方法：
    • 离散值
      • 众数填充
      • 相关列最高的列填充
    • 连续值
      • 中位数
      • 相关性最高的列做线性回归进行估计

4.5 多变量决策树

4.5.1 传统“单变量决策树”

• 若我们将每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找了不同样本间的分类边界。传统“单变量决策树”所形成的分类边界是由若干个与坐标轴平行分段组成。

4.5.2 多变量决策树

• 在多变量决策树的学习过程中，非叶节点不再是仅对某个属性，二是对属性的线性组合进行测试。即不是为每一个非叶节点寻找一个最优化属性，而是试图建立一个合适的线性分类器。

• 多变量决策树算法主要算法：
  • OC1:先贪心地寻找每一个属性的最优权值，在局部最优化的基础上在对分类边界进行随机扰动以试图找到更好的边界。
  • 引入线性分类器学习的最小二乘法
  • 在决策树叶节点嵌入神经网络

4.6 阅读材料

• C4.5Rule
  • 是一个将C4.5决策树转化为符号规则的算法，决策树的每一个分支很容易地重写为一条规则
  • C4.5Rule算法在转化过程中会进行规则前件合并、删除等操作，因此最终规则及的泛化能力会增强。

4.7 案例练习

• 分类问题

• 预测问题

• 代码 及部分笔记：[/%E8%A5%BF%E7%93%9C%E4%B9%A6-%E7%AC%AC%E5%9B%9B%E7%AB%A0%E7%AC%AC4%20%E7%AB%A0%20%E5%86%B3%E7%AD%96%E6%A0%91]