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

1次阅读

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

C4.5 算法作为 ID3 的改进版本，其核心创新在于以下三个关键技术点：

信息增益比通过引入分裂信息（Split Information）来修正 ID3 算法对多值属性的偏好问题。其计算分为两个阶段：

计算标准信息增益：

def information_gain(parent_entropy, children_entropy, weights):
    return parent_entropy - sum(w * e for w, e in zip(weights, children_entropy))

计算分裂信息：

def split_info(weights):
    return -sum(w * math.log2(w) for w in weights if w > 0)

最终增益比为两者相除，有效平衡了属性选择时的偏差。

C4.5 采用动态二分法处理连续特征：

对连续特征值进行排序
计算相邻值的中间点作为候选划分点
选择信息增益比最大的划分点
将该特征转换为二元离散特征

后剪枝（Post-Pruning）是 C4.5 防止过拟合的关键：

首先构建完整的决策树
自底向上考察非叶节点
计算替换为叶节点前后的验证集准确率
保留准确率更高的结构

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:
        return DecisionNode(value=most_common_label(y))

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

    # 节点划分
    X_true, y_true, X_false, y_false = split_dataset(X, y, best_feature, best_threshold)

    # 递归构建子树
    true_branch = build_tree(X_true, y_true, current_depth+1, max_depth)
    false_branch = build_tree(X_false, y_false, current_depth+1, max_depth)

    return DecisionNode(
        feature_idx=best_feature,
        threshold=best_threshold,
        true_branch=true_branch,
        false_branch=false_branch)

完整实现代码包含 13 个核心函数，已上传至 GitHub 仓库。

训练阶段：O(nmd)（n 样本数，m 特征数，d 树深度）
预测阶段：O(d)

并行化处理 ：
特征选择阶段可并行计算各特征增益比
使用 Python 的 multiprocessing 模块实现

增量学习 ：

def partial_fit(self, X_batch, y_batch):
    """增量更新决策树"""
    for x, y in zip(X_batch, y_batch):
        self._update_tree(self.root, x, y)

特征预筛选 ：
通过互信息或卡方检验预先过滤无关特征

连续特征标准化：

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler().fit(X_train)
X_train = scaler.transform(X_train)

类别特征编码：
高基数类别特征建议采用目标编码（Target Encoding）

早停策略：
设置最大深度（max_depth=8）
最小样本分裂限制（min_samples_split=10）

剪枝参数：

def prune(node, X_val, y_val):
    if node.value is not None:
        return

    # 先剪枝子树
    prune(node.true_branch, X_val, y_val)
    prune(node.false_branch, X_val, y_val)

    # 计算当前节点准确率
    original_acc = evaluate(node, X_val, y_val)

    # 尝试替换为叶节点
    majority_class = most_common_label(y_val)
    temp_acc = evaluate(DecisionNode(value=majority_class), X_val, y_val)

    if temp_acc >= original_acc:
        node.value = majority_class
        node.feature_idx = None

特性	ID3	C4.5	CART
分裂标准	信息增益	信息增益比	基尼系数
处理特征	仅离散	离散 + 连续	离散 + 连续
树结构	多叉树	多叉树	二叉树
输出类型	分类	分类	分类 + 回归
缺失值处理	不支持	支持	支持

使用 graphviz 生成的决策树结构：

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