C4.5决策树算法实战：从特征选择到工程落地避坑指南

1次阅读

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

在机器学习分类任务中，ID3 算法作为经典的决策树算法，依赖信息增益进行特征选择。但实践中我们会发现一个严重问题：当某个特征取值特别多时（比如用户 ID），信息增益会天然偏向选择这类特征，尽管它们可能毫无分类意义。

举个例子：用用户 ID 预测购买行为时，ID3 可能直接按每个用户单独分桶，导致生成的决策树毫无泛化能力。这就是信息增益的 多值属性偏向缺陷。

C4.5 的核心改进是引入 增益率（Gain Ratio）替代信息增益。其数学定义为：

GainRatio(D,a) = Gain(D,a) / IV(a)
其中 IV(a) = -∑(v∈a)(|Dv|/|D|)*log2(|Dv|/|D|)

关键点在于：
1. IV(a)（固有值）惩罚取值多的特征
2. 当特征取值分布越均匀（即 IV 值越大），增益率会相应减小
3. 连续特征通过二分法离散化处理（见下图示意）

graph LR
    A[连续特征排序] --> B[遍历所有相邻值中点]
    B --> C[计算每个分割点的增益率]
    C --> D[选择最优分割点]

以下是 C4.5 决策树的核心类结构设计：

import numpy as np
from collections import Counter

class C45Node:
    def __init__(self, feature_idx=None, threshold=None, children=None, label=None):
        self.feature_idx = feature_idx  # 分裂特征索引
        self.threshold = threshold      # 连续特征分割阈值
        self.children = children        # 子节点字典 {特征值: 节点}
        self.label = label              # 叶节点类别

class C45Tree:
    def __init__(self, min_samples_split=2, max_depth=10):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth

    def _gain_ratio(self, X, y, feature_idx):
        """时间复杂度 O(nlogn) 主要来自排序"""
        # 计算信息增益
        entropy_before = self._entropy(y)
        values = X[:, feature_idx]

        if np.issubdtype(values.dtype, np.number):  # 连续特征处理
            sorted_idx = np.argsort(values)
            # ... 二分法实现省略...
        else:  # 离散特征
            # ... 分组计算熵...

        # 计算 IV 值并返回增益率
        iv = self._intrinsic_value(split_groups)
        return (entropy_before - entropy_after) / iv if iv !=0 else 0

推荐使用 代价复杂度剪枝（CCP）：

def prune_tree(self, node, X_val, y_val):
    if node.is_leaf: return

    # 计算剪枝前准确率
    acc_before = self.accuracy(X_val, y_val)

    # 临时存储子树
    backup_children = node.children
    node.children = None
    node.label = self._most_common_label(y_val)

    # 比较剪枝效果
    if self.accuracy(X_val, y_val) >= acc_before:
        return  # 保留剪枝
    else:
        node.children = backup_children  # 恢复子树

对于大规模数据：