C4.5决策树算法头歌：从原理到工程实践的全解析

1次阅读

没有评论

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

决策树算法是机器学习中的经典方法，最早由 Ross Quinlan 提出的 ID3 算法采用信息增益作为特征选择标准。但 ID3 存在明显缺陷：

只能处理离散型特征
对取值多的特征有偏好（如 ID 类特征）
没有剪枝机制容易过拟合

C4.5 作为 ID3 的改进版本，主要引入了三大改进：

使用信息增益比替代信息增益，解决特征取值偏向问题
支持连续特征通过二分法自动离散化
加入剪枝策略控制模型复杂度

信息增益比的本质是对信息增益进行归一化处理。具体计算分三步：

计算数据集 D 的经验熵 H(D)
计算特征 A 对数据集 D 的经验条件熵 H(D|A)
用特征 A 的固有值 IV(A)对信息增益进行标准化

数学表达式为：

GainRatio(D,A) = Gain(D,A) / IV(A)
其中 IV(A) = -Σ(|Dv|/|D|)*log2(|Dv|/|D|)

C4.5 采用悲观剪枝 (Pessimistic Pruning) 策略，其核心思想是：

计算剪枝前后在验证集上的错误率
考虑二项分布的置信区间上限
当剪枝后的上限误差小于剪枝前时执行剪枝

具体实现时会递归地对非叶子节点评估，自底向上进行剪枝判断。

对于连续特征，C4.5 采用二分法寻找最佳分割点：

def find_best_split(continuous_feature, labels):
    # 对特征值排序并获取候选分割点
    sorted_values = np.sort(np.unique(continuous_feature))
    split_points = (sorted_values[:-1] + sorted_values[1:]) / 2

    best_gain_ratio = -np.inf
    best_split = None

    for point in split_points:
        # 将特征二值化
        discrete_feature = (continuous_feature >= point).astype(int)
        current_ratio = calc_gain_ratio(discrete_feature, labels)

        if current_ratio > best_gain_ratio:
            best_gain_ratio = current_ratio
            best_split = point

    return best_split, best_gain_ratio

C4.5 采用权重分配法处理缺失值：

计算特征 A 无缺失样本的比例 ρ
计算无缺失样本的信息增益比 GainRatio
最终增益比为 ρ * GainRatio

对应代码实现：

def handle_missing_values(feature, labels):
    # 获取非缺失值索引
    non_missing = ~np.isnan(feature)
    rho = np.mean(non_missing)

    if rho == 0:
        return 0  # 全部缺失则无信息量

    # 仅用非缺失值计算增益比
    gain_ratio = calc_gain_ratio(feature[non_missing], labels[non_missing])
    return rho * gain_ratio

假设有 n 个样本，m 个特征，树深度为 d：