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

1次阅读

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

决策树算法是机器学习中经典的分类与回归方法，其发展经历了从 ID3 到 C4.5 再到 CART 的演进过程。C4.5 算法由 Ross Quinlan 在 1993 年提出，作为 ID3 算法的改进版本，主要解决了以下问题：

ID3 只能处理离散型特征，而 C4.5 支持连续型特征的自动离散化
ID3 使用信息增益作为特征选择标准，容易偏向取值多的特征，C4.5 引入信息增益比进行修正
C4.5 增加了剪枝策略，有效缓解过拟合问题

C4.5 算法使用信息增益比作为特征选择标准，其计算过程分为两步：

计算信息增益（与 ID3 相同）

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

计算固有值（Split Information）

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

最终信息增益比为两者相除

C4.5 采用悲观剪枝（Pessimistic Pruning）策略：

计算节点的错误率
向上合并后重新计算错误率
如果合并后的错误率不高于合并前，则执行剪枝

对于连续特征，C4.5 采用二分法进行离散化：

def discretize_continuous_feature(feature_values, labels):
    unique_values = sorted(set(feature_values))
    best_split = None
    max_gain_ratio = -1

    for i in range(1, len(unique_values)):
        threshold = (unique_values[i-1] + unique_values[i]) / 2
        # 计算信息增益比...
        if gain_ratio > max_gain_ratio:
            max_gain_ratio = gain_ratio
            best_split = threshold

    return best_split

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

def handle_missing_values(samples, feature_idx):
    # 计算每个取值的权重
    value_dist = calculate_value_distribution(samples, feature_idx)

    for sample in samples:
        if sample[feature_idx] is None:
            # 按权重分配到各个分支
            sample['weights'] = value_dist
        else:
            sample['weights'] = {sample[feature_idx]: 1.0}

C4.5 的时间复杂度主要来自：

特征选择：O(mnlog(n))，其中 m 是特征数，n 是样本数
树构建：最坏情况下 O(m*n^2)

预排序连续特征
采用特征采样（随机森林思想）
并行计算各特征的信息增益比

特征取值过多导致信息增益比失效
方案：设置最小样本分裂数
类别不平衡导致树偏向多数类
方案：采用加权信息增益比
连续特征离散化效率低
方案：使用近似算法或预分桶

算法	优点	缺点
ID3	实现简单	只能处理离散特征，无剪枝
C4.5	支持连续特征，抗过拟合	计算复杂度较高
CART	支持回归任务，二叉树结构	只能产生二元划分