C4.5决策树剪枝技术深度解析：从过拟合到模型泛化能力提升

1次阅读

没有评论

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

C4.5 决策树作为 ID3 算法的改进版本，其核心优势体现在两个关键技术创新：

信息增益比：通过引入分裂信息量对信息增益进行归一化处理，有效缓解了 ID3 算法倾向于选择取值较多特征的缺陷。计算公式为 GainRatio(S,A)=Gain(S,A)/SplitInfo(S,A)，其中 SplitInfo(S,A)=-Σ(|Sv|/|S|)*log2(|Sv|/|S|)
连续值处理：采用二分法对连续属性进行离散化，选择信息增益最大的划分点作为分裂阈值，这一特性使其能够直接处理数值型特征而无需预先离散化

然而，决策树的递归分割特性会导致模型倾向于完全拟合训练数据，具体表现为：

对噪声数据过度敏感
生成过于复杂的树结构（如某些分支深度超过 20 层）
在测试集上表现显著差于训练集（平均差距可达 15-30%）

基本原理：
– 自底向上遍历非叶子节点
– 用该节点下样本的多数类替换子树
– 当验证集错误率不升高时执行剪枝

数学表达：
对于节点 t，剪枝条件为：
Error(pruned_tree) ≤ Error(original_tree)

优缺点：
– 优点：简单直观，计算效率高（时间复杂度 O(n)）
– 缺点：依赖独立验证集，数据利用效率低

核心思想：
基于二项分布统计量对节点错误率进行连续性修正，使用修正后的错误率估计进行剪枝判断

计算公式：
e'(t) = [e(t) + 0.5] / N(t)
其中 e(t)为节点 t 的错误样本数，N(t)为总样本数

适用场景：
小样本数据集（单节点样本数 <100 时优势明显）

最优子树序列：
通过最小化代价复杂度函数选择最优子树：
Rα(T)=R(T)+α|T|
其中 R(T)为误分类代价，|T| 为叶节点数

关键参数：
α 调节模型复杂度惩罚力度，通常通过交叉验证选择（典型值范围 1e- 5 到 1e-2）

from sklearn.preprocessing import KBinsDiscretizer

# 连续特征离散化（模拟 C4.5 处理方式）discretizer = KBinsDiscretizer(n_bins=5, encode='ordinal', strategy='quantile')
X_train_disc = discretizer.fit_transform(X_train[cont_features])

from sklearn.tree import DecisionTreeClassifier

# 通过 max_depth 控制树深
pre_pruned_model = DecisionTreeClassifier(
    criterion='entropy',
    max_depth=5,  # 关键控制参数
    min_samples_leaf=10,
    random_state=42
).fit(X_train, y_train)

# 计算 CCP 路径
path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas

# 交叉验证选择最优 alpha
from sklearn.model_selection import GridSearchCV
param_grid = {'ccp_alpha': ccp_alphas[::10]}  # 抽样减少计算量
grid_search = GridSearchCV(DecisionTreeClassifier(criterion='entropy'),
    param_grid,
    cv=5
).fit(X_train, y_train)

import matplotlib.pyplot as plt

# 绘制 CCP 参数与准确率关系
plt.plot(ccp_alphas, train_scores, 'o-', label='Train')
plt.plot(ccp_alphas, test_scores, 'o-', label='Test')
plt.axvline(grid_search.best_params_['ccp_alpha'], 
           color='red', linestyle='--')
plt.xlabel('CCP alpha')
plt.ylabel('Accuracy')
plt.legend()

剪枝方法	训练集准确率	测试集准确率	树深度
未剪枝	0.98	0.83	18
预剪枝(max_depth=5)	0.91	0.87	5
CCP 剪枝(α=0.01)	0.89	0.88	9

from sklearn.inspection import DecisionBoundaryDisplay

DecisionBoundaryDisplay.from_estimator(
    best_model,
    X_test[:, :2],  # 取前两个特征展示
    response_method="predict",
    alpha=0.5,
    cmap=plt.cm.RdYlBu
).plot()
plt.scatter(X_test[:,0], X_test[:,1], c=y_test, edgecolor='k')