共计 1567 个字符，预计需要花费 4 分钟才能阅读完成。
为什么需要 C4.5？
决策树算法中，ID3 使用信息增益 (Information Gain) 作为属性选择标准，但它存在一个明显缺陷：倾向于选择取值较多的属性。比如有一个 ”ID” 属性，每个样本都有唯一值，按信息增益一定会选它，但这显然毫无分类意义。
C4.5 的改进在于引入 信息增益率(Gain Ratio)：
$$
\text{GainRatio}(A) = \frac{\text{Gain}(A)}{\text{SplitInfo}(A)}
$$
其中 SplitInfo 是属性的固有信息（类似熵的计算）：
$$
\text{SplitInfo}(A) = -\sum_{i=1}^v \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}
$$
这样即使某个属性取值很多，如果其 SplitInfo 也很大，最终的 GainRatio 就不会特别高。
手算六步法
1. 数据准备
以经典的天气数据集为例：
| Day | Outlook | Temperature | Humidity | Wind | Play |
|---|---|---|---|---|---|
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| … | … | … | … | … | … |
2. 计算类别的信息熵
Play 的熵：
$$
\text{Entropy}(D) = -\frac{9}{14}\log_2\frac{9}{14} – \frac{5}{14}\log_2\frac{5}{14} \approx 0.940
$$
3. 计算各属性信息增益
以 Outlook 为例：
– Sunny: [2+,3-]
– Overcast: [4+,0-]
– Rainy: [3+,2-]
$$
\text{Gain(Outlook)} = 0.940 – \left[\frac{5}{14}(0.971) + \frac{4}{14}(0) + \frac{5}{14}(0.971)\right] \approx 0.246
$$
4. 计算 SplitInfo
$$
\text{SplitInfo(Outlook)} = -\left[\frac{5}{14}\log_2\frac{5}{14} + \frac{4}{14}\log_2\frac{4}{14} + \frac{5}{14}\log_2\frac{5}{14}\right] \approx 1.577
$$
5. 得信息增益率
$$
\text{GainRatio(Outlook)} = \frac{0.246}{1.577} \approx 0.156
$$
6. 选择最大 GainRatio 属性作为节点
比较所有属性后，选择 GainRatio 最大的作为当前分裂节点。
连续属性处理
对于 Temperature 这样的连续值属性：
- 排序所有取值：(72,75,76,80,81,83,85)
- 计算相邻值的均值作为候选划分点：(73.5,75.5,78,80.5,82,84)
- 对每个划分点计算 GainRatio，选择最优的
递归停止条件
- 当前节点所有样本属于同一类
- 没有剩余属性可供划分
- 样本数小于预设阈值
避坑指南
- 除零问题：当某个属性值只有一个取值时（如 Outlook 全为 Sunny），SplitInfo 为 0。解决方法：
- 给 SplitInfo 加一个很小的 epsilon
-
直接跳过这种属性
-
过拟合预防：
- 预剪枝：限制树的最大深度
-
后剪枝：先生成完整树，再自底向上剪枝
-
属性选择修正：
- 对 GainRatio 设定阈值
- 结合其他指标综合判断
C4.5 的局限性
- 只能用于分类任务（后来的 CART 支持回归）
- 多趟数据集扫描导致效率问题
- 对缺失值处理不够鲁棒
改进方向包括引入随机森林等集成方法，或改用更现代的 XGBoost/LightGBM。
思考题
- 如果某个属性的 SplitInfo 恰好等于 0，此时的 GainRatio 该如何处理？
- 对于有 100 个取值的类别型属性，如何优化其 GainRatio 计算效率？
- 在预剪枝时，除了树深度还可以采用哪些停止条件？
