C4.5算法决策树实战：解决分类问题中的信息增益比陷阱

1次阅读

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

决策树算法的核心在于如何选择最优划分特征。ID3 算法使用信息增益作为选择标准，但它存在一个明显缺陷：倾向于选择取值较多的特征。C4.5 算法通过引入信息增益比解决了这个问题。

信息熵基础：信息熵衡量的是数据集的不确定性。对于一个包含 K 个类别的数据集 D，其熵定义为：

def entropy(y):
    _, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return -np.sum(probs * np.log2(probs))

信息增益的局限：ID3 直接使用信息增益，计算公式为Gain(D,A) = Ent(D) - Σ(|Dv|/|D|)*Ent(Dv)。对于取值多的特征（如 ID 号），信息增益会人为地偏高。
C4.5 的改进：引入分裂信息量SplitInfo(D,A) = -Σ(|Dv|/|D|)*log2(|Dv|/|D|)，信息增益比定义为GainRatio(D,A) = Gain(D,A)/SplitInfo(D,A)。这相当于对信息增益做了归一化处理。

C4.5 另一个重要改进是能够直接处理连续特征，而 ID3 需要先离散化。这里的关键是找到最佳分割点：

排序与候选点 ：对连续特征的 N 个取值排序后，候选分割点为相邻值的均值。例如特征值为[1,2,3,5] 则候选点为[1.5,2.5,4]。

二分法实现：

def find_best_split(feature, y):
    unique_values = np.unique(feature)
    if len(unique_values) == 1:
        return None

    sorted_values = np.sort(unique_values)
    thresholds = (sorted_values[:-1] + sorted_values[1:]) / 2

    max_gain_ratio = -1
    best_threshold = None

    for threshold in thresholds:
        left_idx = feature <= threshold
        right_idx = feature > threshold

        current_gain_ratio = calculate_gain_ratio(y, left_idx, right_idx)

        if current_gain_ratio > max_gain_ratio:
            max_gain_ratio = current_gain_ratio
            best_threshold = threshold

    return best_threshold

虽然 sklearn 的 DecisionTreeClassifier 主要基于 CART 算法，但我们可以模拟 C4.5 的关键特性：

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV

# 模拟信息增益比选择
params = {'criterion': ['entropy'],  # 使用信息熵而非基尼系数
    'max_depth': [3,5,7,None],
    'min_samples_split': [2,5,10]
}

grid = GridSearchCV(DecisionTreeClassifier(), params, cv=5)
grid.fit(X_train, y_train)

# 最佳参数可视化
import matplotlib.pyplot as plt
plt.figure(figsize=(10,6))
plt.plot(grid.cv_results_['mean_test_score'])
plt.xlabel('Parameter Combination')
plt.ylabel('Accuracy')
plt.title('Parameter Tuning Results')
plt.show()

类别不平衡处理：
使用 class_weight=’balanced’ 自动调整类别权重
对少数类样本进行过采样（如 SMOTE）
在计算信息增益比时加入权重系数
内存优化技巧：
对于大型数据集，设置 max_leaf_nodes 限制树规模
使用 presort=False（特别是特征数 >1000 时）
考虑增量训练（warm_start=True）

特征重要性可视化：

importances = grid.best_estimator_.feature_importances_
indices = np.argsort(importances)[::-1]

plt.figure(figsize=(12,6))
plt.title("Feature Importances")
plt.bar(range(X.shape[1]), importances[indices], align="center")
plt.xticks(range(X.shape[1]), X.columns[indices], rotation=90)
plt.xlim([-1, X.shape[1]])
plt.tight_layout()
plt.show()