Python实战：C4.5决策树算法实现与调优指南

1次阅读

没有评论

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

C4.5 是经典的决策树算法，属于监督学习的分类方法。相比前辈 ID3 算法，它最大的改进是：

用 信息增益比 替代信息增益，解决 ID3 偏向多值特征的问题
支持 连续特征 的自动离散化（通过阈值划分）
引入 后剪枝 机制降低过拟合风险

举个例子：当某个特征有 100 个不同取值时，ID3 会优先选择它（因为信息增益最大），而 C4.5 会通过增益比惩罚这种高基数特征。

实际编码时会遇到这些坎儿：

连续特征处理：需要动态寻找最佳分割点，计算复杂度陡增
过拟合控制：纯 Python 实现剪枝比 sklearn 麻烦得多
计算效率：大数据集下递归计算容易爆栈

分四步走：

计算数据集的经验熵 H(D)
计算特征 A 对 D 的经验条件熵 H(D|A)
求信息增益 = H(D) – H(D|A)
增益比 = 信息增益 / 特征 A 的固有值（IV）

def calc_gain_ratio(X, y, feature_idx):
    # 计算原始熵
    base_entropy = calc_entropy(y)

    # 按特征值划分数据集
    split_values = np.unique(X[:, feature_idx])
    weighted_entropy = 0.0
    iv = 0.0

    for value in split_values:
        subset_mask = X[:, feature_idx] == value
        subset_y = y[subset_mask]
        prob = len(subset_y) / len(y)
        weighted_entropy += prob * calc_entropy(subset_y)
        iv -= prob * np.log2(prob) if prob > 0 else 0

    gain = base_entropy - weighted_entropy
    return gain / iv if iv != 0 else 0  # 避免除零

关键点：对排序后的特征值取中位数作为候选分割点

def find_best_split_continuous(X_col, y):
    sorted_idx = np.argsort(X_col)
    split_points = []

    for i in range(1, len(X_col)):
        if y[sorted_idx[i]] != y[sorted_idx[i-1]]:
            split_points.append((X_col[sorted_idx[i]] + X_col[sorted_idx[i-1]]) / 2)

    # 评估每个分割点的增益比...
    return best_split

维度	手写实现	sklearn.tree.DecisionTreeClassifier
分裂标准	仅支持增益比	支持 gini/ 信息增益
连续值处理	需手动实现	自动优化
并行计算	不支持	支持 n_jobs 参数

采样策略：对特征计算时采用随机采样（sklearn 的 max_features 参数）
提前终止：当信息增益比小于 epsilon 时停止分裂
内存优化：用 pandas.category 处理类别特征

class C45Optimized:
    def __init__(self, max_samples=100000):
        self.max_samples = max_samples

    def fit(self, X, y):
        if len(X) > self.max_samples:
            idx = np.random.choice(len(X), self.max_samples, replace=False)
            X, y = X[idx], y[idx]
        # ... 后续处理

min_samples_split：建议从 5 开始网格搜索
max_depth：先用 None 训练，观察深度分布再约束
ccp_alpha：后剪枝强度（sklearn 特有）

方案一：用该特征出现最频繁的值填充（mode）
方案二：单独作为特殊分支处理
千万避免：直接删除含缺失值的样本

在计算熵时加入类别权重
采用代价敏感学习（class_weight 参数）

# 加权熵计算示例
def weighted_entropy(y, class_weights):
    counts = np.bincount(y)
    probs = counts / len(y)
    return -np.sum(class_weights * probs * np.log2(probs + 1e-10))