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

1次阅读

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

决策树算法因其可解释性强、训练效率高的特点，在金融风控、医疗诊断等场景广泛应用。传统 ID3 算法存在两大痛点：一是采用 Information Gain（信息增益）偏向选择取值多的特征，二是无法直接处理连续值。C4.5 算法通过引入 Gain Ratio（信息增益率）和动态离散化技术，显著提升了模型的鲁棒性。

C4.5 最关键的改进是将分裂标准从信息增益调整为信息增益率，其计算分为两步：

信息增益公式（对比 ID3）：
$$\text{Gain}(S,A) = \text{Entropy}(S) – \sum_{v\in Values(A)} \frac{|S_v|}{|S|} \text{Entropy}(S_v)$$
分裂信息量（Split Information）：
$$\text{SplitInfo}(S,A) = -\sum_{v\in Values(A)} \frac{|S_v|}{|S|} \log_2 \frac{|S_v|}{|S|}$$
最终增益率公式：
$$\text{GainRatio}(S,A) = \frac{\text{Gain}(S,A)}{\text{SplitInfo}(S,A)}$$

这种改进有效抑制了 ID3 对多值属性的偏好，当特征取值过多时，SplitInfo 会增大从而降低增益率。

对于连续值特征，C4.5 采用以下步骤：

将特征值排序后得到候选划分点集合 $T = {(a_i+a_{i+1})/2 | 1\leq i\leq n-1}$
计算每个划分点 $t\in T$ 的信息增益率
选择最优划分点将连续值转为二元分裂

当样本 $x$ 在特征 $A$ 上缺失时：

将 $x$ 按权重分配到所有子节点
权重等于各分支的样本占比 $\frac{|S_v|}{|S|}$
计算信息增益时用有效样本比例调整熵值

import numpy as np

def calculate_gain_ratio(X, y, feature_idx):
    """
    计算信息增益率
    :param X: 特征矩阵 (n_samples, n_features)
    :param y: 标签向量 (n_samples,)
    :param feature_idx: 当前特征索引
    :return: (gain_ratio, best_split) 连续值返回最佳分割点
    """
    # 计算原始熵
    base_entropy = _entropy(y)

    # 处理连续值特征
    if isinstance(X[0, feature_idx], (float, np.floating)):
        sorted_values = np.sort(np.unique(X[:, feature_idx]))
        split_points = [(sorted_values[i] + sorted_values[i+1])/2 
                        for i in range(len(sorted_values)-1)]

        best_gain_ratio = -np.inf
        best_split = None

        for t in split_points:
            mask = X[:, feature_idx] <= t
            gain = base_entropy - (len(y[mask])/len(y) * _entropy(y[mask]) +
                len(y[~mask])/len(y) * _entropy(y[~mask])
            )
            split_info = -(np.mean(mask) * np.log2(np.mean(mask)) +
                np.mean(~mask) * np.log2(np.mean(~mask))
            )
            current_ratio = gain / (split_info + 1e-10)  # 避免除以零

            if current_ratio > best_gain_ratio:
                best_gain_ratio = current_ratio
                best_split = t

        return best_gain_ratio, best_split

    # 处理离散值特征
    else:
        values, counts = np.unique(X[:, feature_idx], return_counts=True)
        gain = base_entropy
        split_info = 0.0

        for v, cnt in zip(values, counts):
            subset = y[X[:, feature_idx] == v]
            gain -= (cnt/len(y)) * _entropy(subset)
            split_info -= (cnt/len(y)) * np.log2(cnt/len(y))

        return gain / (split_info + 1e-10), None

def _entropy(y):
    """计算标签熵值"""
    _, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return -np.sum(probs * np.log2(probs))