决策树算法实战：手把手教你用Python实现C4.5构建步骤

1次阅读

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

决策树是机器学习中最直观的算法之一，它通过一系列 if-else 规则对数据进行分类。C4.5 作为 ID3 算法的升级版，主要解决了两个痛点：

连续特征处理 ：ID3 只能处理离散特征，而 C4.5 通过二分法自动离散化连续值
抗过拟合能力 ：用信息增益比替代信息增益，减少对多值特征的偏好

举个实际例子：预测银行贷款违约风险时，C4.5 可以同时处理 ” 年龄 ”（连续值）和 ” 职业 ”（离散值），而 ID3 只能处理后者。

衡量数据不确定性的指标，公式为：

H(D) = -Σ(p_k * log₂p_k)

其中 p_k 是第 k 类样本所占比例。

已知特征 A 的条件下，数据集 D 的不确定性：

H(D|A) = Σ(|D_v|/|D| * H(D_v))

D_v 表示特征 A 取第 v 个值时对应的子集。

C4.5 的核心改进，解决了信息增益对多值特征的偏向问题：

Gain_ratio(D,A) = Gain(D,A) / SplitInfo(D,A)

其中 SplitInfo 是特征 A 的固有信息（类似熵的计算）：

SplitInfo(D,A) = -Σ(|D_v|/|D| * log₂(|D_v|/|D|))

先准备一个模拟数据集：

import pandas as pd
import numpy as np

data = {'年龄': [25, 30, 35, 40, 45, 50],
    '收入': ['高', '中', '低', '中', '低', '高'],
    '学历': ['本科', '硕士', '博士', '本科', '硕士', '博士'],
    '违约': ['否', '否', '是', '否', '是', '否']
}
df = pd.DataFrame(data)

def calc_entropy(y):
    """计算信息熵"""
    _, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return -np.sum(probs * np.log2(probs))

def find_best_split(feature, y):
    """对连续特征找到最佳分割点"""
    unique_values = np.unique(feature)
    best_gain = -1
    best_split = None

    # 尝试所有可能的分割点
    for split_val in unique_values:
        left_idx = feature <= split_val
        current_gain = calc_info_gain(y, left_idx)
        if current_gain > best_gain:
            best_gain = current_gain
            best_split = split_val
    return best_split

class TreeNode:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 分裂阈值（连续特征）self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点取值

def build_tree(X, y):
    # 终止条件：所有样本属于同一类或没有特征可用
    if len(np.unique(y)) == 1 or X.shape[1] == 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 选择最佳分裂特征
    best_feature, best_threshold = find_best_feature(X, y)

    # 递归构建子树
    left_idx = X[:, best_feature] <= best_threshold
    left = build_tree(X[left_idx], y[left_idx])
    right = build_tree(X[~left_idx], y[~left_idx])

    return TreeNode(feature=best_feature, threshold=best_threshold, left=left, right=right)

现象：训练集准确率 100%，测试集表现差
解决：
– 设置最小样本分裂数（min_samples_split）
– 后剪枝：构造完整树后，自底向上合并冗余节点

错误做法 ：等宽分箱导致信息损失
正确做法 ：
– 优先使用二分法动态寻找分割点
– 考虑特征值分布，避免产生空箱

现象：少数类被忽略
解决：
– 在信息增益计算中引入类别权重
– 采用过采样 / 欠采样平衡数据

掌握了基础实现后，可以尝试这些进阶方向：