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

1次阅读

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

决策树的核心是选择最优划分属性。C45 算法使用 增益率 (Gain Ratio) 来选择划分属性，这是对 ID3 算法中信息增益 (Information Gain) 的改进。

信息熵(Entropy)：衡量样本集合纯度的指标
$$Ent(D) = -\sum_{k=1}^{|y|}p_klog_2p_k$$
其中 $p_k$ 是第 k 类样本所占比例
信息增益：
$$Gain(D,a) = Ent(D) – \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$
ID3 直接使用信息增益，但会偏向取值数目多的属性
增益率：
$$Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$$
$$IV(a) = -\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$$
C45 引入固有值 (IV) 来平衡信息增益的偏好

实际应用中的常见问题：

过拟合：树深度过大导致训练集表现好但测试集差
连续值处理：需要找到最佳分割点
缺失值处理：样本某些特征值缺失
高基数类别：类别型特征取值过多
类别不平衡：某些类别样本数过少

import numpy as np
from typing import List, Dict

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

def information_gain(X: np.ndarray, y: np.ndarray, feature_idx: int) -> float:
    """计算某特征的信息增益"""
    base_entropy = entropy(y)

    # 获取该特征所有唯一值
    values, counts = np.unique(X[:, feature_idx], return_counts=True)

    # 计算加权熵
    weighted_entropy = 0.0
    for v, c in zip(values, counts):
        subset_y = y[X[:, feature_idx] == v]
        weighted_entropy += (c / len(y)) * entropy(subset_y)

    return base_entropy - weighted_entropy

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target

# 创建 C45 决策树(criterion='entropy')
clf = DecisionTreeClassifier(criterion='entropy', max_depth=3)
clf.fit(X, y)

# 查看特征重要性
print("Feature importances:", clf.feature_importances_)

剪枝策略：
使用 ccp_alpha 参数控制剪枝强度
通过交叉验证选择最优 alpha 值
类别不平衡：
设置class_weight='balanced'
或手动指定类别权重class_weight={0:1, 1:5}
连续值处理：
C45 自动处理连续值特征
对于自定义实现，需要先排序后找最优分割点

特性	C45	CART
分裂标准	增益率	基尼系数
树结构	多叉树	二叉树
适用场景	分类 + 回归(离散化)	分类 + 回归
缺失值处理	通过概率权重	通过替代节点
剪枝方式	悲观剪枝	代价复杂度剪枝