C04. 决策树

基本流程

决策树是基于树结构来进行决策的。

决策树的生成是一个递归过程，导致递归的原因：

• 当前结点包含的样本全部属于同一个类别，无需划分；
• 当前属性集为空，或者所有样本在所有属性上取值相同，无法划分；
  • 把当前结点标记为叶结点，其类别设定为这个结点所包含的样本最多的类别
• 当前结点包含的样本集合为空，不能划分。
  • 把当前结点标记为叶结点，其类别设定为其父结点所包含的样本最多的类别

划分选择

信息熵 ( Information Entropy ) 是度量样本集合纯度 ( purity ) 的指标。

划分属性的准则：

• ID3 决策树学习算法使用「信息增益」( Information Gain ) 为准则来选择划分属性
  • 「信息增益」准则偏好样本数目较多的属性
• C4.5 决策树学习算法使用「增益比」( Gain Ratio ) 为准则来选择划分属性
  • 「信息增益比」准则偏好样本数目较少的属性
• CART 决策树学习算法使用「基尼指数「( Gini Index ) 为准则来选择划分属性
  • 「基尼值」：表示从数据集 D 中随机抽取两个样本，其类别标记不一致的概率
  • 「基尼系数」准则偏好样本类别标记一致的属性

剪枝处理

决策树剪枝 ( pruning ) 是处理「过拟合」问题的主要手段。

剪枝的基本策略：

• 预剪枝 ( prepruning ) ：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能改善决策树的泛化性能则停止划分，并且将当前结点标记为叶结点。
  • 降低了「过拟合」的风险，减少了决策树的训练时间开销和测试时间开销。
  • 带来了「欠拟合」的风险。
• 后剪枝 ( postpruning ) ：先从训练集中生成一棵完整的决策树，然后自底向上地对非叶结点进行评估，若将该结点对应的子树替换为叶结点能够改善决策树的泛化性能，则将当前子树替换为叶结点。
  • 「欠拟合」风险较小，泛化性能优先预剪枝策略。
  • 决策树的训练时间开销和测试时间开销较大。

处理连续值与缺失值

• 「连续值」处理的问题：连续值离散化
  • 二分法对连续属性进行处理
• 「缺失值」处理的问题：
  • 如何在属性值缺失的情况下进行属性划分
    • 定义一个无缺失值样本所占比例ρ
  • 如何在给定划分属性的情况下，对缺失了属性值的样本进行划分
    • 将同一个样本以不同的概率划分到不同的子结点中

多变量决策树

多变量决策树 ( Multivariate Decision
Tree ) 能够实现「斜划分」甚至更复杂的划分的决策树。

多变量决策树的 OC1 算法：

• 贪心地寻找每个属性的最优权值
• 在局部优化的基础上对分类边界进行随机扰动以试图找到更好的边界