C4.5决策树算法演进史：从理论缺陷到工程优化

1次阅读

没有评论

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

决策树算法的发展经历了从 ID3 到 C4.5 的关键跃迁。ID3 算法（Iterative Dichotomiser 3）由 Ross Quinlan 于 1986 年提出，其核心是通过信息增益选择分裂属性。信息增益的计算公式为：

$$ IG(S,A) = H(S) – \sum_{v\in Values(A)} \frac{|S_v|}{|S|} H(S_v) $$

其中 $H(S)$ 是数据集 $S$ 的熵，$H(S_v)$ 是子集 $S_v$ 的熵。但 ID3 存在明显缺陷：

倾向于选择取值较多的属性（如 ID 字段），导致过拟合
无法处理连续值特征
缺失值处理机制不完善

这些问题催生了 1993 年 C4.5 算法的诞生。

C4.5 引入信息增益率来克服信息增益的偏向性：

$$ GainRatio(S,A) = \frac{IG(S,A)}{SplitInfo(S,A)} $$

其中分裂信息 $SplitInfo(S,A)$ 用于惩罚多值属性：

$$ SplitInfo(S,A) = -\sum_{i=1}^n \frac{|S_i|}{|S|} \log_2 \frac{|S_i|}{|S|} $$

对于连续值特征，C4.5 采用二分法寻找最佳分割点：

将特征值排序得到候选分割点集合 $T$
对每个 $t\in T$ 计算信息增益率
选择使增益率最大的 $t$ 作为分割阈值

采用悲观错误剪枝（PEP），通过统计显著性检验决定是否剪枝。定义节点错误率为：

$$ e(t) = \frac{error(t) + 0.5}{N(t)} $$

其中 $error(t)$ 是节点 $t$ 的分类错误数，$N(t)$ 是样本数。0.5 为连续性校正项。

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt

# 使用 C4.5 等价参数（实际 sklearn 实现的是 CART）clf = DecisionTreeClassifier(
    criterion='entropy',  # 使用信息熵
    max_depth=3,          # 控制树深度
    min_samples_split=5,  # 节点最小样本数
    class_weight='balanced' # 处理类别不平衡
)

# 训练模型
clf.fit(X_train, y_train)

# 特征重要性可视化
feat_importances = pd.Series(clf.feature_importances_, index=feature_names)
feat_importances.nlargest(10).plot(kind='barh')
plt.title('Top 10 Important Features')
plt.show()

设置 class_weight='balanced' 自动调整类别权重
手动指定权重字典：{class_label: weight}