C45决策树算法全解析：从数学原理到Python实战

1次阅读

没有评论

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

决策树的核心是选择最优划分属性，C45 沿用 ID3 的信息增益思想，但进行了改进。首先理解信息熵（Entropy）：

$$ Ent(D) = -\sum_{k=1}^{|y|}p_k\log_2p_k $$

其中 $D$ 是样本集合，$p_k$ 是第 $k$ 类样本所占比例。信息增益定义为：

$$ Gain(D,a) = Ent(D) – \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) $$

$a$ 是待划分属性
$V$ 是属性 $a$ 的取值个数
$D^v$ 是 $D$ 中在 $a$ 上取值为 $v$ 的子集

C45 改进的关键是引入增益率，解决 ID3 对取值数目多的属性偏好问题：

$$ Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)} $$

其中固有值(Intrinsic Value)：

$$ IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|} $$

实际使用时，C45 会先选出信息增益高于平均水平的属性，再从中选择增益率最高的。

决策树容易完全匹配训练数据导致过拟合，C45 通过后剪枝 (Post-Pruning) 解决：

预剪枝：在划分前评估，可能带来欠拟合
后剪枝：先生成完整树，再自底向上替换子树为叶节点

C45 的创新点之一是能直接处理连续特征：

将特征值排序得到候选划分点集合 $T_a = {\frac{a^i+a^{i+1}}{2}|1\leq i\leq n-1}$
计算每个划分点的信息增益率
选择最优划分点

实际数据常存在缺失，C45 的处理方式：

计算信息增益时忽略缺失样本
对测试样本，若属性值缺失则进入所有分支并按概率加权

import numpy as np
from typing import List

def entropy(class_counts: List[int]) -> float:
    """计算信息熵"""
    total = sum(class_counts)
    if total == 0:
        return 0.0
    proportions = np.array(class_counts) / total
    return -np.sum(proportions * np.log2(proportions + 1e-10))  # 避免 log(0)

def gain_ratio(X: np.ndarray, y: np.ndarray, feature_idx: int) -> float:
    """计算某特征的信息增益率"""
    # 计算原始熵
    base_entropy = entropy(np.bincount(y))

    # 获取该特征所有取值
    feature_values = X[:, feature_idx]
    unique_values = np.unique(feature_values)

    # 计算条件熵
    cond_entropy = 0.0
    iv = 0.0
    for value in unique_values:
        subset_mask = feature_values == value
        subset_y = y[subset_mask]
        weight = len(subset_y) / len(y)
        cond_entropy += weight * entropy(np.bincount(subset_y))
        iv += -weight * np.log2(weight + 1e-10)

    # 避免除以零
    if iv == 0:
        return 0.0

    return (base_entropy - cond_entropy) / iv

from sklearn.tree import DecisionTreeClassifier

# 使用熵作为划分标准即 C45 算法
tree = DecisionTreeClassifier(criterion='entropy', 
                             max_depth=5,
                             min_samples_split=10)
tree.fit(X_train, y_train)

成本复杂度剪枝参数，值越大剪枝越激进：

# 寻找最优 ccp_alpha
path = tree.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas

# 对每个 alpha 训练模型
trees = []
for ccp_alpha in ccp_alphas:
    tree = DecisionTreeClassifier(ccp_alpha=ccp_alpha)
    tree.fit(X_train, y_train)
    trees.append(tree)

设置 class_weight 参数自动调整权重：

# 自动按类别频率反比加权
tree = DecisionTreeClassifier(class_weight='balanced')

# 或手动指定权重
tree = DecisionTreeClassifier(class_weight={0:1, 1:5})  # 类别 1 的重要性是 0 的 5 倍

特性	C45	CART
分裂标准	增益率	基尼系数
树结构	多叉树	二叉树
输出类型	分类	分类 / 回归
连续值处理	直接支持	直接支持
缺失值处理	概率分布	替代节点