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

1次阅读

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

当使用 ID3 算法构建决策树时，我们会发现一个明显的缺陷：信息增益（Information Gain）会倾向于选择取值较多的特征。比如在用户画像场景中，” 用户 ID” 这种唯一标识符的特征会天然具有最大的信息增益，但实际上这个特征对分类毫无意义。

数学表达上，信息增益的计算公式为：
$$Gain(D,a) = Ent(D) – \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)$$
其中 $Ent(D)$ 是数据集 D 的经验熵。当某个特征 a 的取值数目 V 很大时，条件熵部分会趋近于 0，导致 Gain(D,a) 被夸大。

C4.5 算法通过引入增益率（Gain Ratio）来解决这个问题：
$$Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$$
$$IV(a) = -\sum_{v=1}^V \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$$
这里 IV(a) 称为特征 a 的固有值（Intrinsic Value），它就像是一个归一化因子，可以惩罚取值数目多的特征。

对于连续值特征（如年龄、收入），C4.5 采用二分法进行离散化：
1. 先将该特征的所有取值排序
2. 取相邻两个值的中间点作为候选划分点
3. 计算每个候选点的增益率
4. 选择最优划分点

例如对于一个排序后的连续特征值 [10,20,30]，候选划分点就是 15 和 25。这个处理使得决策树可以自然地处理连续特征。

import numpy as np
from collections import Counter

class C45DecisionTree:
    def __init__(self, min_samples_split=2, max_depth=None):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth

    def _entropy(self, y):
        """计算信息熵 O(n) where n is len(y)"""
        counts = Counter(y)
        probs = [c / len(y) for c in counts.values()]
        return -sum(p * np.log2(p) for p in probs)

    def _gain_ratio(self, X_col, y, split_val=None):
        """计算增益率 O(n log n) due to sorting"""
        if split_val is not None:  # 连续特征
            mask = X_col <= split_val
            y_left, y_right = y[mask], y[~mask]
            if len(y_left) == 0 or len(y_right) == 0:
                return 0
        else:  # 离散特征
            y_left, y_right = [], []
            for val, yi in zip(X_col, y):
                y_left.append(yi) if val else y_right.append(yi)

        # 计算信息增益
        entropy_parent = self._entropy(y)
        entropy_children = (len(y_left)/len(y)) * self._entropy(y_left) + \
                          (len(y_right)/len(y)) * self._entropy(y_right)
        gain = entropy_parent - entropy_children

        # 计算 IV
        iv = -((len(y_left)/len(y)) * np.log2(len(y_left)/len(y)) + \
              (len(y_right)/len(y)) * np.log2(len(y_right)/len(y)))

        return gain / iv if iv != 0 else 0

代价复杂度剪枝（Cost-Complexity Pruning）是 C4.5 常用的后剪枝方法。核心思想是通过正则化参数 α 来平衡树的复杂度和误差：

从完整树开始，计算每个节点的 α 值
剪去使整体损失函数 $C_α(T)=C(T)+α|T|$ 最小的子树
通过交叉验证选择最优 α

def prune(self, X_val, y_val):
    """基于验证集的后剪枝 O(n^2) worst case"""
    if not hasattr(self, 'tree_'):
        return

    best_acc = self.score(X_val, y_val)
    nodes_to_prune = self._find_prune_candidates(self.tree_)

    for node in nodes_to_prune:
        original = node.copy()
        # 尝试剪枝
        node['left'] = node['right'] = None
        node['is_leaf'] = True
        node['label'] = Counter(y_val).most_common(1)[0][0]

        current_acc = self.score(X_val, y_val)
        if current_acc >= best_acc:  # 剪枝后效果更好
            best_acc = current_acc
        else:  # 恢复
            node.update(original)

对于大规模数据，每次递归都重新排序特征会非常耗时。我们可以：