C4.5决策树算法Python实现：从原理到生产环境避坑指南

1次阅读

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

C4.5 算法采用信息增益比（Gain Ratio）替代 ID3 的信息增益，解决属性偏向多值特征的问题。其计算分为三步：

信息增益计算 ：

def information_gain(parent_entropy, children_weights):
    return parent_entropy - sum(w*e for w,e in children_weights)

分裂信息量计算 ：

def split_info(children_sizes):
    total = sum(children_sizes)
    return -sum((size/total)*math.log2(size/total) for size in children_sizes)

最终增益比 ：信息增益与分裂信息量的比值

C4.5 通过二分法处理连续特征：
1. 将特征值排序
2. 计算相邻值中点作为候选划分点
3. 选择信息增益比最大的划分点

采用悲观剪枝（Pessimistic Pruning）：
– 计算节点误差率上界
– 比较剪枝前后误差率
– 保留统计意义显著的划分

class DecisionNode:
    def __init__(self, feature_idx=None, threshold=None,
                 value=None, true_branch=None, false_branch=None):
        self.feature_idx = feature_idx  # 特征索引
        self.threshold = threshold      # 划分阈值（连续特征）self.value = value              # 叶节点预测值
        self.true_branch = true_branch  # 左子树
        self.false_branch = false_branch # 右子树

def build_tree(X, y, current_depth=0, max_depth=10):
    # 终止条件处理
    if len(np.unique(y)) == 1 or current_depth == max_depth:
        leaf_value = _calculate_leaf_value(y)
        return DecisionNode(value=leaf_value)

    # 特征选择
    best_feature, best_threshold = _find_best_split(X, y)

    # 递归构建子树
    true_idx = X[:, best_feature] <= best_threshold
    true_X, true_y = X[true_idx], y[true_idx]
    false_X, false_y = X[~true_idx], y[~true_idx]

    return DecisionNode(
        feature_idx=best_feature,
        threshold=best_threshold,
        true_branch=build_tree(true_X, true_y, current_depth+1),
        false_branch=build_tree(false_X, false_y, current_depth+1)
    )

最优情况（平衡树）：O(n_features * n_samples * log(n_samples))
最差情况（倾斜树）：O(n_features * n_samples^2)

特征预排序：对连续特征一次性排序复用
并行化处理：各特征的信息增益计算可并行
采样优化：对大规模数据采用子采样策略

缺失值处理：建议采用该特征众数填充
类别特征：需提前做 Label Encoding
特征缩放：虽然决策树不需要，但能加快最优分割点查找

预剪枝：设置 max_depth/min_samples_split
后剪枝：训练后基于验证集进行剪枝
正则化：使用 min_impurity_decrease 参数

特性	ID3	C4.5	CART
特征选择	信息增益	信息增益比	基尼指数
处理连续值	不支持	支持	支持
树结构	多叉树	多叉树	二叉树
输出类型	分类	分类	分类 / 回归

from sklearn.tree import export_graphviz
export_graphviz(
    decision_tree,
    out_file="tree.dot",
    feature_names=feature_names,
    class_names=target_names,
    rounded=True
)