Task03-决策树 Decision Tree

[x333]

来了，决策树！

1.算法流程

递归建树，递归返回情况有三：

1. 当前结点包含的样本全属于同一类别，无需划分。
2. 当前属性集为空，或是所有样本在所有属性上的取值相同，无法划分 。把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别。
3. 当前结点包含的样本集合为空，不能划分。把当前结点标记为叶结点，但将基类别设定为其父结点所含样本最多的类别。

2. 划分选择

划分：希望分支节点包含的样本类别尽可能相同，纯度 Purity 高。

2.1 ID3决策树 （信息增益）

用信息熵来衡量样本集合纯度：

划分准则：

缺陷： 偏好取值数量多的特征，极端情况下，划分后有子集 |D^v| = 1，自然子集的信息熵 = 0，从而 Gain(D, a) 最高。

2.2 C4.5决策树 （增益率）

对增益打补丁。

实际建树时，启发式：先从候选划分属性中找出信息增益高于平均水平 的，再从中选取增益率最高的。

2.3 CART决策树 （基尼指数）

除了基于信息熵来评估 Purity，还有别的选择。

构造的是二叉树！

3. 剪枝

• 预剪枝
  建树划分节点时，评估划分结果是否带来泛化性提升。（用 validation set 评估）

  • 优点：降低过拟合风险，减少训练、测试时间开销；
  • 缺点：可能欠拟合；

• 后剪枝
  自底向上检查非叶子节点是否需要剪枝。

4.连续与缺失值

• 连续值处理
  C4.5：对连续值二分
  

  
  
  便可以将样本切分为两个子集，计算增益：
  
  

• 缺失值处理
  Q1：属性值缺失时，如何选择划分属性来建树？
  A1：泛化信息增益，有
  

  
  
  
  

Q2：样本缺少划分属性的值，如何划分？