决策树算法详解：从 ID3、C4.5 到 CART 以及 sklearn 参数调优
一、什么是决策树？
决策树通过对训练样本的学习，并建立分类规则，然后依据分类规则，对新样本数据进行分类预测，属于有效监督学习。
核心：所以数据从根节点一步一步落到叶子节点。
决策树的结构非常类似生活中的判断过程：
例如：
天气怎么样？
├── 晴天 → 湿度高吗？
│ ├── 是 → 不打球
│ └── 否 → 打球
└── 阴天 → 打球
其中：
- 根节点：第一个节点
- 非叶子节点：中间节点
- 叶子节点：最终结果节点
决策树的核心问题是：
如何选择最优特征进行数据划分？
不同算法采用了不同的方法：
- ID3：使用信息增益
- C4.5：使用信息增益率
- CART：使用基尼指数（Gini Index）
二、ID3 算法：基于信息增益选择特征
1. 信息熵（Entropy）
ID3 算法的核心思想是：
选择能够最大程度降低数据不确定性的特征作为划分依据。
衡量数据混乱程度的指标就是信息熵。
公式：
\[ H(D) = -\sum p_i \log_2(p_i) \]
其中：
- \( p_i \)：某一类别出现的概率
- 熵越小，数据越纯净
- 熵越大，数据越混乱
在决策树中，希望划分之后的数据熵越来越小。
文件中的案例使用"是否外出打球"作为分类任务：
14 天数据中：
- 打球：9 天
- 不打球：5 天
因此类别熵为：
\[ H(D) = 0.940 \]
2. 信息增益（Information Gain）
信息增益表示：
一个特征能够减少多少信息的不确定性。
公式：
\[ \text{Gain}(D, A) = H(D) - H(D|A) \]
如果某个特征带来的信息增益最大，则说明该特征最具有分类能力，会优先作为决策树节点。
3. ID3 案例计算
假设数据包含：
| 特征 | 分类 |
|---|---|
| 天气 | 晴天、阴天、雨天 |
| 温度 | 热、温和、凉爽 |
| 湿度 | 高、正常 |
| 风 | 有风、无风 |
分别计算不同特征的信息增益。
（1）天气特征
天气划分后：
- 晴天：5 天
- 阴天：4 天
- 雨天：5 天
计算得到：
\[ H(D|\text{天气}) = 0.693 \]
因此：
\[ \text{Gain}(\text{天气}) = 0.940 - 0.693 = 0.247 \]
（2）温度特征
计算得到：
\[ \text{Gain}(\text{温度}) = 0.940 - 0.911 = 0.029 \]
（3）湿度特征
计算得到：
\[ \text{Gain}(\text{湿度}) = 0.151 \]
（4）风特征
计算得到：
\[ \text{Gain}(\text{风}) = 0.048 \]
最终结果：
| 特征 | 信息增益 |
|---|---|
| 天气 | 0.247 |
| 湿度 | 0.151 |
| 风 | 0.048 |
| 温度 | 0.029 |
因此：
\[ \text{天气} > \text{湿度} > \text{风} > \text{温度} \]
天气成为根节点。
三、C4.5 算法：解决 ID3 容易偏向取值多特征的问题
1. 为什么需要 C4.5？
ID3 算法存在一个问题：
如果某个特征拥有大量不同取值，例如：
- 编号
- 用户 ID
- 商品编号
虽然信息增益很高，但实际没有分类意义。
因此 C4.5 提出：
使用信息增益率代替信息增益。
2. 信息增益率
计算过程：
- 计算类别熵
- 计算每个属性的信息熵
- 计算信息增益：\[ \text{Gain} = H(D) - H(D|A) \]
- 计算信息增益率：\[ \text{GainRatio} = \frac{\text{Gain}}{H(A)} \]
选择信息增益率最大的特征。
3. C4.5 案例计算
计算结果：
| 特征 | 信息增益率 |
|---|---|
| 天气 | 0.1566 |
| 湿度 | 0.151 |
| 风 | 0.049 |
| 温度 | 0.0186 |
排序：
\[ \text{天气} > \text{湿度} > \text{风} > \text{温度} \]
因此依旧选择天气作为首个划分节点。
四、CART 算法：基于基尼指数
CART（Classification And Regression Tree）是目前应用非常广泛的一种决策树算法。
它与 ID3、C4.5 最大的区别：
- ID3：信息增益
- C4.5：信息增益率
- CART：基尼指数
CART 选择：
使划分后的数据基尼指数最小的特征。
1. 基尼指数（Gini Index）
公式：
\[ \text{Gini}(D) = 1 - \sum p_i^2 \]
含义：
- Gini 越小，数据越纯
- 最好的划分方式就是让划分后的 Gini 指数最低
例如贷款预测案例：
根据年龄特征：
- 青年
- 中年
- 老年
分别计算不同年龄节点的基尼指数。
五、决策树剪枝：解决过拟合问题
1. 为什么需要剪枝？
在决策树学习过程中，模型会不断地对数据进行划分。
如果不限制树的生长：
例如：
有 1000 条训练数据，构建出来的决策树可能生成 1000 条不同的路径。
也就是说：
- 每一个样本都有自己对应的一条判断路线
- 树会完全记住训练数据
- 对训练数据预测效果很好
- 但是面对新的未知数据时，可能无法正确判断
这种现象称为：
过拟合（Overfitting）
即：
模型过度学习训练数据中的细节和噪声，导致泛化能力下降。
因此，需要通过剪枝（Pruning）降低模型复杂度，提高模型对新数据的预测能力。
2. 决策树如何剪枝？
决策树剪枝主要分为两种：
（1）预剪枝（Pre-Pruning）
预剪枝是在：
决策树生成过程中提前限制树的生长。
也就是说，在树还没有完全建立之前，根据一定条件停止继续划分。
例如：
- 限制树的最大深度
- 限制叶子节点数量
- 限制叶子节点最少样本数量
优点：
- 训练速度快
- 可以减少模型复杂度
- 防止过拟合
缺点：
- 可能提前停止，导致模型没有充分学习数据规律
（2）后剪枝（Post-Pruning）
后剪枝是在：
决策树已经完全生成之后，再删除不必要的分支。
流程：
- 先构建完整决策树
- 分析每个节点的重要程度
- 删除贡献较小的节点
- 得到更加简单的决策树
优点：
- 保留更多数据规律
- 通常泛化能力更强
缺点：
- 计算成本较高
3. 预剪枝策略
在实际机器学习中，预剪枝通常通过以下方式实现：
（1）限制树的深度
参数：
max_depth表示：
决策树允许达到的最大层数。
例如：
如果设置：
max_depth = 3表示树最多只有 3 层。
作用：
- 防止树无限增长
- 降低模型复杂度
- 减少过拟合
在数据量较小的时候，可以不限制深度；
如果：
- 样本数量多
- 特征数量多
则可以尝试限制树深度。
（2）限制叶子节点数量
参数：
max_leaf_nodes表示：
限制决策树最大的叶子节点数量。
例如：
设置：
max_leaf_nodes = 10那么：
- 当叶子节点达到 10 个
- 模型不会继续产生新的分支
作用：
- 控制树结构规模
- 防止模型学习过多细节
（3）限制叶子节点样本数量
参数：
min_samples_leaf表示：
叶子节点中最少需要包含多少个样本。
例如：
min_samples_leaf = 5表示：
一个叶子节点至少需要 5 个样本。
如果某个节点样本过少：
- 说明该节点可能只是在记忆训练数据
- 容易造成过拟合
因此可以进行剪枝。
4. 基尼系数与剪枝
CART 算法使用：
基尼指数（Gini Index）
作为节点划分标准。
公式：
\[ \text{Gini}(D) = 1 - \sum p_i^2 \]
其中：
- \( p_i \)：类别比例
基尼指数越小：
说明数据越纯。
在剪枝过程中：
如果某个节点继续划分后：
- 基尼指数下降不明显
- 分类效果提升很小
那么这个节点可能没有必要继续展开。
因此：
基尼系数不仅用于选择划分节点，也可以辅助判断树结构是否合理。
CART 算法本身就是通过基尼指数最小化准则进行特征选择。
5. 剪枝前后的决策树变化
剪枝前：
根节点 | ---------------- | | 节点A 节点B / \ / \ C D E F /|\ /|\ ...大量分支...特点：
- 树结构复杂
- 节点数量多
- 容易过拟合
剪枝后：
根节点 | ---------------- | | 节点A 节点B | 结果特点：
- 删除无意义分支
- 模型更加简单
- 泛化能力提高
六、sklearn 中的决策树剪枝参数
在 sklearn 中：
from sklearn.tree import DecisionTreeClassifier model = DecisionTreeClassifier( criterion='gini', max_depth=5, min_samples_leaf=10, max_leaf_nodes=20 )其中：
<
| 参数 |
|---|