决策树算法实战：C4.5算法在特征选择与过拟合中的优化方案

1次阅读

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

决策树是机器学习中最直观的算法之一，而 ID3 作为早期经典算法，在实际应用中发现两个明显缺陷：

特征选择偏差：ID3 使用信息增益作为分裂标准，会天然倾向于选择取值更多的特征。例如在『身份证号』这种唯一值特征上，信息增益永远最大，但这类特征毫无预测意义
过拟合严重：ID3 没有剪枝机制，只要节点不纯就会继续分裂，最终生成的树往往深度过大，在训练集上表现完美但测试集效果骤降

算法	分裂标准	支持连续值	剪枝策略	适用任务
ID3	信息增益	否	无	分类
C4.5	信息增益比	是	PEP 剪枝	分类
CART	基尼系数 / 均方差	是	CCP 剪枝	分类 / 回归

C4.5 用信息增益比克服特征选择偏差，其计算分为两步：

计算信息增益（与 ID3 相同）
$$Gain(D,a) = Ent(D) – \sum_{v=1}^V \frac{|D^v|}{|D|}Ent(D^v)$$
引入分裂信息度量 IV(a)
$$IV(a) = -\sum_{v=1}^V \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$$
最终信息增益比
$$Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$$

实际应用技巧 ：当 IV(a) 接近 0 时（特征取值几乎全部集中在一个类别），需设置阈值过滤该特征

C4.5 创新性地支持连续特征，处理流程：

对特征 A 的 m 个取值排序得到{a1,a2,…,am}
取相邻值中点作为候选划分点，共 m - 1 个：
$$T_a = {\frac{a^i+a^{i+1}}{2} | 1\leq i\leq m-1}$$
按信息增益比选择最优切分点

悲观错误剪枝 (Pessimistic Error Pruning) 步骤：

计算节点误差上界（引入统计学连续型修正）：
$$e'(t) = e(t) + 0.5$$
计算子树误差上界（假设服从二项分布）：
$$e'(T_t) = \sum_{i=1}^{|L|} (e(i) + 0.5)$$
比较剪枝前后的误差上界，决定是否剪枝

import numpy as np

def calc_entropy(y):
    """计算信息熵"""
    hist = np.bincount(y)
    ps = hist / len(y)
    return -np.sum([p * np.log2(p) for p in ps if p > 0])

def calc_info_gain_ratio(X, y, feature_idx):
    """计算信息增益比"""
    # 计算父节点熵
    ent_parent = calc_entropy(y)

    # 计算特征取值分布
    values, counts = np.unique(X[:, feature_idx], return_counts=True)

    # 计算信息增益
    ent_children = 0
    for v, cnt in zip(values, counts):
        mask = X[:, feature_idx] == v
        ent_children += (cnt / len(y)) * calc_entropy(y[mask])
    gain = ent_parent - ent_children

    # 计算分裂信息 IV
    iv = -np.sum([(cnt / len(y)) * np.log2(cnt / len(y)) for cnt in counts])

    return gain / iv if iv != 0 else 0  # 避免除以零

def find_best_split_continuous(X_col, y):
    """对连续特征寻找最佳切分点"""
    # 获取所有候选切分点
    sorted_idx = np.argsort(X_col)
    split_points = (X_col[sorted_idx][1:] + X_col[sorted_idx][:-1]) / 2

    best_gain_ratio = -1
    best_split = None

    for sp in split_points:
        # 按当前切分点划分数据
        y_left = y[X_col <= sp]
        y_right = y[X_col > sp]

        # 计算信息增益比（简化版）... # 实现类似离散特征的逻辑

        if current_gain > best_gain_ratio:
            best_gain_ratio = current_gain
            best_split = sp

    return best_split, best_gain_ratio