C4.5决策树算法公式解析与工程实践：从信息增益到剪枝优化

1次阅读

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

决策树算法在金融风控、医疗诊断、推荐系统等领域广泛应用，其白盒特性（解释性强）和无需特征缩放的优点深受工程师青睐。传统 ID3 算法存在两个致命缺陷：使用 Information Gain（信息增益）倾向于选择取值多的属性，且无法处理连续特征。C4.5 算法通过引入 Gain Ratio（信息增益率）和动态离散化技术，使模型鲁棒性显著提升。

ID3 的信息增益公式：
$$
IG(S,A) = H(S) – \sum_{v\in Values(A)} \frac{|S_v|}{|S|}H(S_v)
$$
其中 $H(S)=-\sum p_i\log_2 p_i$ 是熵（Entropy）。

C4.5 改进为信息增益率：
$$
GR(S,A) = \frac{IG(S,A)}{SplitInfo(A)}
$$
分裂信息量（Split Information）的计算：
$$
SplitInfo(A) = -\sum_{v\in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}
$$

关键区别 ：SplitInfo 相当于属性本身的熵，可以惩罚取值分散的属性。当属性有大量取值时，SplitInfo 会增大，从而降低增益率。

C4.5 采用二分法（Binary Discretization）离散化连续特征：

对当前节点所有样本按该特征值排序
遍历所有相邻值的中间点作为候选划分点
选择使信息增益率最大的划分点

例如年龄特征可能被划分为 ”≤32.5 岁 ” 和 ”>32.5 岁 ” 两个区间。

采用概率加权法（Probability Weighting）：

计算有缺失值的属性在已知值上的信息增益率
将该增益率乘以已知值的比例作为最终评估值
预测时让缺失值样本同时进入所有子节点，按各分支概率加权结果

import numpy as np
from math import log2

def calc_split_info(subset_ratios):
    """ 计算分裂信息量（Split Information）Args:
        subset_ratios: 各子集样本占比的列表，如 [0.3, 0.7]
    """
    return -sum(p * log2(p) for p in subset_ratios if p > 0)

def calc_gain_ratio(feature_values, labels):
    # 计算原始熵
    base_entropy = calc_entropy(labels)

    # 计算该特征的信息增益
    unique_values = np.unique(feature_values)
    weighted_entropy = 0.0
    split_info = 0.0

    for value in unique_values:
        subset_mask = (feature_values == value)
        subset_labels = labels[subset_mask]
        ratio = len(subset_labels) / len(labels)
        weighted_entropy += ratio * calc_entropy(subset_labels)
        split_info -= ratio * log2(ratio)

    information_gain = base_entropy - weighted_entropy
    return information_gain / split_info if split_info > 0 else 0