4 决策树

4.1 基本流程

决策树的基本流程：

1. 从根节点开始，对样本进行划分，使得每个子节点包含的样本尽可能属于同一类别。
2. 对每个子节点，递归地进行划分，直到满足停止的3个条件：

重要

决策结束的3个条件：

1. 当前节点包含的样本全部属于同一类别。
2. 当前节点的属性集为空，或所有样本在所有属性上取值相同。
3. 当前节点的样本集为空。

4.2 划分选择

相关信息

划分选择是指在决策树节点上，根据哪个属性进行样本的划分。

4.2.1 信息增益

信息熵：描述纯度，值越小，纯度越高。

信息熵.png

信息增益：增益越大，纯度提升越大，对可取值数目较多的属性有所偏好。

信息增益.png

ID3基于信息增益。

4.2.2 信息增益率

信息增益率：信息增益/属性固有值，对可取值数目少的属性有所偏好。

信息增益率.png

相关信息

C4.5 使用了一个启发式：先找出信息增益高于平均水平的属性，再选取增益率最高的。

4.2.3 基尼指数

基尼指数：反映从数据集中随机抽取两个样本，其类别标记不一致的概率，值越小，纯度越高。

基尼指数.png

相关信息

CART 采用基尼指数来选择划分属性。

4.3 剪枝处理

4.3.1 剪枝原因

• 缓解过拟合
• 减少分支、简化模型

相关信息

剪枝处理是为了控制决策树的复杂度，避免过拟合。

4.3.2 基本策略

根据剪枝前后验证集精度考虑剪枝。若划分后能提高验证集精度，则划分，对划分后的属性，执行同样判断；否则，不划分。

重要

两种剪枝方法：

1. 预剪枝：降低过拟合；带来欠拟合风险。
2. 后剪枝：欠拟合风险小，泛化能力往往优于预剪枝；逐一考察叶节点，训练时间开销大。

4.3.3 剪枝后评估

留出法：预留一部分数据作为验证集，进行性能评估。