Python实战：从零实现C4.5决策树算法及避坑指南

1次阅读

没有评论

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

决策树是机器学习中最直观的算法之一，它将数据通过一系列规则划分成不同的类别。相比于 ID3 算法，C4.5 有两大改进：

使用信息增益比（而非单纯的信息增益）选择划分属性，解决了 ID3 对取值数目多的属性偏好问题
增加了对连续属性的处理能力，使算法能直接处理现实数据中常见的数值型特征

举个实际例子：在预测贷款风险时，既有『年龄』这样的连续值，也有『职业』这种离散值。C4.5 可以同时处理这两种特征，而 ID3 只能处理离散值。

信息增益比 = 信息增益 / 分裂信息熵，其计算分为三步：

计算数据集的经验熵 H(D)
计算按某特征 A 划分后的条件熵 H(D|A)
计算特征 A 的分裂信息熵（即特征 A 的固有值）

Python 实现关键代码：

def calc_entropy(y):
    """计算信息熵"""
    counter = Counter(y)
    total = len(y)
    return -sum((count/total)*math.log2(count/total) for count in counter.values())

def calc_gain_ratio(X, y, feature_idx):
    """计算信息增益比"""
    # 计算原始熵
    base_entropy = calc_entropy(y)
    # 计算按特征划分后的条件熵
    feature_values = X[:, feature_idx]
    unique_values = set(feature_values)
    new_entropy = 0.0
    split_info = 0.0

    for value in unique_values:
        sub_y = y[feature_values == value]
        prob = len(sub_y) / len(y)
        new_entropy += prob * calc_entropy(sub_y)
        split_info -= prob * math.log2(prob)

    # 避免除零错误
    if split_info == 0:
        return 0
    return (base_entropy - new_entropy) / split_info

C4.5 采用二分法处理连续属性：

将该特征所有取值排序
计算每两个相邻值的中间点作为候选划分点
选择使信息增益比最大的划分点

实现技巧：

def handle_continuous_feature(X, y, feature_idx):
    """连续特征离散化处理"""
    feature_values = sorted(set(X[:, feature_idx]))
    best_gain_ratio = 0.0
    best_split_point = None

    for i in range(1, len(feature_values)):
        split_point = (feature_values[i-1] + feature_values[i]) / 2
        # 临时将连续值转为离散值（大于 / 小于分割点）temp_feature = (X[:, feature_idx] > split_point).astype(int)
        current_ratio = calc_gain_ratio(temp_feature.reshape(-1,1), y, 0)

        if current_ratio > best_gain_ratio:
            best_gain_ratio = current_ratio
            best_split_point = split_point

    return best_split_point

终止条件需要处理四种情况：

当前节点所有样本属于同一类别
没有剩余特征可供划分
当前节点样本集为空（通过父节点投票决定类别）
信息增益比小于阈值（预剪枝）

核心递归逻辑：

def build_tree(X, y, used_features=set(), max_depth=5):
    # 终止条件 1：所有样本同类别
    if len(set(y)) == 1:
        return {'class': y[0]}

    # 终止条件 2：无特征可用或达到最大深度
    if len(used_features) == X.shape[1] or max_depth == 0:
        return {'class': Counter(y).most_common(1)[0][0]}

    # 选择最佳划分特征
    best_gain = -1
    best_feature = None
    split_point = None

    for feature_idx in range(X.shape[1]):
        if feature_idx in used_features:
            continue

        if is_continuous(feature_idx):  # 判断是否连续特征
            point = handle_continuous_feature(X, y, feature_idx)
            temp_feature = (X[:, feature_idx] > point).astype(int)
            gain = calc_gain_ratio(temp_feature.reshape(-1,1), y, 0)

            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx
                split_point = point
        else:
            gain = calc_gain_ratio(X, y, feature_idx)
            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx

    # 终止条件 4：信息增益比过小
    if best_gain < 0.01:
        return {'class': Counter(y).most_common(1)[0][0]}

    # 构建子树
    tree = {'feature': best_feature, 'children': {}}

    if split_point is not None:  # 连续特征处理
        left_idx = X[:, best_feature] <= split_point
        right_idx = X[:, best_feature] > split_point

        tree['split_point'] = split_point
        tree['children']['left'] = build_tree(X[left_idx], y[left_idx], 
            used_features | {best_feature}, max_depth-1)
        tree['children']['right'] = build_tree(X[right_idx], y[right_idx],
            used_features | {best_feature}, max_depth-1)
    else:  # 离散特征处理
        feature_values = set(X[:, best_feature])
        for value in feature_values:
            sub_idx = X[:, best_feature] == value
            tree['children'][value] = build_tree(X[sub_idx], y[sub_idx],
                used_features | {best_feature}, max_depth-1)

    return tree

预测时需要根据节点类型（离散 / 连续）走不同分支：

def predict(tree, x):
    if 'class' in tree:
        return tree['class']

    feature_value = x[tree['feature']]

    if 'split_point' in tree:  # 连续特征
        if feature_value <= tree['split_point']:
            return predict(tree['children']['left'], x)
        else:
            return predict(tree['children']['right'], x)
    else:  # 离散特征
        if feature_value in tree['children']:
            return predict(tree['children'][feature_value], x)
        else:  # 处理未见过的特征值
            return get_leaf_class(tree)

def get_leaf_class(node):
    """获取子树中最常见的类别"""
    if 'class' in node:
        return node['class']

    classes = []
    for child in node['children'].values():
        classes.append(get_leaf_class(child))

    return Counter(classes).most_common(1)[0][0]

直接删除 ：当缺失样本占比较小时适用
填充众数 / 均值 ：对离散特征用众数，连续特征用均值
概率分布法 ：按特征取值比例分配样本到不同分支

改进后的信息增益比计算：

def calc_gain_ratio_with_missing(X, y, feature_idx):
    # 找出非缺失值索引
    non_missing = ~np.isnan(X[:, feature_idx])
    X_clean = X[non_missing]
    y_clean = y[non_missing]

    if len(X_clean) == 0:
        return 0

    # 计算非缺失部分的信息增益比
    gain_ratio = calc_gain_ratio(X_clean, y_clean, feature_idx)
    # 按有效样本比例加权
    return gain_ratio * (len(X_clean) / len(X))

预剪枝 （更常用）：
– 设置最大树深度
– 设置叶子节点最小样本数
– 设置信息增益比阈值

后剪枝 （效果更好但实现复杂）：
1. 先构建完整决策树
2. 自底向上考察非叶节点
3. 若剪枝后验证集准确率提升，则替换为叶节点

假设有 m 个特征，n 个样本，d 为树深度：

训练时：O(mnlog(n)*d)
预测时：O(d)

实际优化建议：
– 对连续特征先排序（O(nlogn)）可提升性能
– 对大规模数据可采用随机森林等集成方法

多变量决策 ：每次只按一个特征划分，可能错过特征组合带来的信息
数值敏感 ：对数值型特征的微小变化可能导致完全不同的树结构
数据倾斜 ：对类别不均衡数据需要额外处理

改进思路：

在节点划分时考虑特征的线性组合
使用 LDA（线性判别分析）找到最佳投影方向
评估划分质量时改用其他度量标准（如 Gini 系数）

实现框架示例：

class MultivariateNode:
    def __init__(self, weights, threshold):
        self.weights = weights  # 特征权重向量
        self.threshold = threshold

    def split(self, X):
        projection = X @ self.weights  # 矩阵乘法
        return projection <= self.threshold

本文完整实现了 C4.5 决策树的七个核心组件：
1. 信息熵计算
2. 信息增益比评估
3. 连续特征离散化
4. 缺失值处理
5. 递归建树逻辑
6. 预测函数
7. 剪枝策略

建议读者在 UCI 数据集（如 iris 或 adult）上测试代码效果。当遇到准确率不高的情况时，可以尝试：