共计 1659 个字符，预计需要花费 5 分钟才能阅读完成。
为什么需要 C4.5？从 ID3 到改进
决策树算法中，ID3 使用信息增益（Information Gain）作为属性选择标准，但它存在一个明显缺陷：倾向于选择取值较多的属性。比如有一个『身份证号』属性，每个样本取值都不同，按 ID3 算法会选择它——但这显然没有实际意义。
C4.5 的改进在于引入信息增益率（Gain Ratio）：
$$
GainRatio(A) = \frac{InformationGain(A)}{SplitInformation(A)}
$$
其中分裂信息（Split Information）用来惩罚取值多的属性：
$$
SplitInformation(A) = -\sum_{i=1}^{v} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}
$$
完整手算流程详解
1. 数据准备
以经典的天气数据集为例：
| Outlook | Temperature | Humidity | Windy | Play Golf |
|---|---|---|---|---|
| Sunny | Hot | High | False | No |
| Sunny | Hot | High | True | No |
| Overcast | Hot | High | False | Yes |
| … | … | … | … | … |
2. 计算信息增益率
步骤分解：
-
计算目标类（Play Golf）的熵：
$$
H(D) = -\left(\frac{5}{14}\log_2\frac{5}{14} + \frac{9}{14}\log_2\frac{9}{14}\right) \approx 0.940
$$ -
以 Outlook 属性为例计算信息增益：
- Sunny 分支熵：
$$
H(D_{Sunny}) = -\left(\frac{2}{5}\log_2\frac{2}{5} + \frac{3}{5}\log_2\frac{3}{5}\right) \approx 0.971
$$ - 加权平均：
$$
H(D|A) = \frac{5}{14} \times 0.971 + … = 0.693
$$ -
信息增益：
$$
IG(Outlook) = 0.940 – 0.693 = 0.247
$$ -
计算分裂信息：
$$
SI(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
$$ -
最终增益率：
$$
GainRatio(Outlook) = \frac{0.247}{1.577} \approx 0.157
$$
3. 连续属性处理
对于 Temperature 这样的连续属性：
- 排序所有取值：65,68,69,70,71,72,…
- 计算候选划分点（相邻值的均值）：66.5,68.5,69.5,…
- 对每个划分点计算信息增益率
- 选择增益率最大的划分点
4. 递归停止条件
- 当前节点所有样本属于同一类
- 没有剩余属性可供划分
- 分支样本数小于预定阈值
避坑指南
除零问题处理
当某个属性值在所有样本中取值相同时，SplitInformation 为 0。解决方案：
if split_info == 0:
gain_ratio = 0 # 或跳过该属性
else:
gain_ratio = info_gain / split_info过拟合预防
- 预剪枝（Pre-pruning）：设置最大深度、最小样本数
- 后剪枝（Post-pruning）：生成完整树后剪枝
属性选择偏向性
即使使用增益率，仍可能偏向取值较少的属性。可考虑：
– 先选择信息增益高于平均值的属性
– 再从中选增益率最大的
局限性与改进方向
- 计算效率 ：需要排序和计算所有连续值划分点
-
改进：使用二分法快速定位最优划分点
-
缺失值处理 ：原始算法对缺失值敏感
-
改进：用概率加权分配缺失值样本
-
剪枝优化 ：后剪枝常用错误率降低剪枝（REP）
思考题
- 如果某个属性有缺失值，如何修改信息增益率计算公式？
- 当两个属性的增益率相同时，应该选择哪个属性？
- 如何用 Python 实现增益率计算的向量化运算？
实践建议
建议手动计算完整天气数据集（14 条记录），对比 ID3 和 C4.5 选择的第一个分裂属性有何不同。这个差异正是 C4.5 改进的核心价值体现。
