C4.5决策树剪枝优化实战：从过拟合到精准预测的算法调优

1次阅读

没有评论

共计 2392 个字符，预计需要花费 6 分钟才能阅读完成。

决策树算法是机器学习中的经典方法，ID3 算法作为早期代表，使用信息增益作为特征选择标准。但在实际应用中，我们发现 ID3 存在明显缺陷：

倾向于选择取值较多的特征（如 ID 类字段）
无法直接处理连续值特征
对缺失值敏感

C4.5 算法通过引入信息增益率（Gain Ratio）完美解决了这些问题：

$$\text{GainRatio}(D,A) = \frac{\text{Gain}(D,A)}{\text{SplitInfo}(D,A)}$$

其中 SplitInfo 是分裂信息度量，用于惩罚多值特征。这种改进使得：

连续值可以通过寻找最佳分割点转化为二元分裂
消除了对多值特征的偏好
通过增益率归一化，使不同特征间的比较更公平

在乳腺癌数据集上的实验显示，未剪枝的 C4.5 决策树会出现典型的过拟合：

指标	训练集	测试集
准确率	98.7%	85.2%
树深度	15	–
叶节点数	127	–

这种高方差现象表明模型记住了训练数据中的噪声而非真实规律。我们需要通过剪枝来简化决策树结构，提高泛化能力。

在树生长过程中提前停止分裂，常用方法：

设置最小样本数阈值（min_samples_leaf）
信息增益率低于阈值（min_gain_ratio）
达到最大深度限制（max_depth）

Python 实现示例：

def should_stop_split(node, min_samples=5, min_gain=0.01):
    """
    node: 当前待分裂节点
    min_samples: 节点最小样本数，防止过小分裂
    min_gain: 信息增益率阈值，低于此值不分裂
    """
    if len(node.samples) < min_samples:
        return True
    if node.best_gain_ratio < min_gain:
        return True
    return False

悲观错误剪枝 (PEP) 是常用方法，其核心公式：

$$e'(T) = e(T) + 0.5 \times N(T)$$

其中 $e(T)$ 是节点错误数，$N(T)$ 是节点样本数。比较剪枝前后的悲观错误率：

计算子树错误率 $\text{error}_{\text{subtree}}$
计算替换为叶节点的错误率 $\text{error}_{\text{leaf}}$
当 $\text{error}{\text{leaf}} \leq \text{error}$ 时执行剪枝}

import numpy as np

def calc_gain_ratio(X, y, feature_idx):
    """计算指定特征的信息增益率"""
    # 计算原始信息熵
    base_entropy = calc_entropy(y)

    # 计算按特征分裂后的条件熵
    if is_continuous(feature_idx):
        # 连续值处理：寻找最佳分割点
        split_val = find_best_split(X[:, feature_idx], y)
        cond_entropy = calc_continuous_cond_entropy(...)
    else:
        # 离散值处理
        cond_entropy = calc_discrete_cond_entropy(...)

    # 计算信息增益
    info_gain = base_entropy - cond_entropy

    # 计算分裂信息
    split_info = calc_split_info(X[:, feature_idx])

    # 避免除零
    if split_info == 0:
        return 0

    return info_gain / split_info

使用 Graphviz 生成决策树图示（左为未剪枝，右为剪枝后）：

from sklearn.tree import export_graphviz

def visualize_tree(clf, filename):
    dot_data = export_graphviz(
        clf, 
        feature_names=features,
        class_names=['良性','恶性'],
        filled=True,
        rounded=True
    )
    graph = graphviz.Source(dot_data)
    graph.render(filename)