C4.5决策树算法：从理论到Python实战指南

1次阅读

没有评论

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

决策树是一种模仿人类决策过程的树形结构，通过一系列规则对数据进行分类或回归。C4.5 作为 ID3 算法的改进版本，主要解决了以下两个关键问题：

信息增益偏向多值属性 ：ID3 使用信息增益选择分裂属性，会天然偏好取值较多的属性（如 ID 类字段）。C4.5 引入信息增益比（信息增益 / 固有值）来消除这种偏差
无法处理连续值 ：ID3 只能处理离散型特征，而 C4.5 通过二分法将连续值转化为离散区间

信息增益比的计算分为三步：

计算数据集的经验熵 H(D)
计算特征 A 对数据集的条件熵 H(D|A)
用信息增益 g(D,A)=H(D)-H(D|A) 除以特征 A 的固有值 IV(A)

数学表达式为：

Gain_ratio(D,A) = Gain(D,A) / IV(A)
其中 IV(A) = -Σ(|D_v|/|D|)*log2(|D_v|/|D|)

对于连续值特征，C4.5 采用以下步骤：

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

C4.5 采用悲观剪枝（Pessimistic Pruning）：

计算子树在训练集上的错误率
加上一个修正项（考虑二项分布的置信区间）
比较剪枝前后的预期错误率决定是否剪枝

import numpy as np
from sklearn.preprocessing import KBinsDiscretizer

# 连续值离散化示例
def discretize_continuous(X, n_bins=3, strategy='quantile'):
    est = KBinsDiscretizer(n_bins=n_bins, encode='ordinal', strategy=strategy)
    return est.fit_transform(X)

class Node:
    def __init__(self, feature_idx=None, threshold=None, value=None, left=None, right=None):
        self.feature_idx = feature_idx  # 特征索引
        self.threshold = threshold      # 分裂阈值
        self.value = value              # 叶节点值
        self.left = left                # 左子树
        self.right = right              # 右子树

class C45DecisionTree:
    def __init__(self, min_samples_split=2, max_depth=None):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth

    def _calculate_entropy(self, y):
        # 计算经验熵实现...
        pass

    def _find_best_split(self, X, y):
        # 寻找最佳分裂属性和阈值...
        pass

    def fit(self, X, y, depth=0):
        # 递归构建决策树...
        pass

from sklearn.tree import export_graphviz
import graphviz

def visualize_tree(tree_model, feature_names, class_names):
    dot_data = export_graphviz(
        tree_model,
        out_file=None,
        feature_names=feature_names,
        class_names=class_names,
        filled=True,
        rounded=True
    )
    return graphviz.Source(dot_data)

内存优化 ：
对于大型数据集，使用增量学习或采样方法
实现基于磁盘的临时数据存储
避免过拟合 ：
合理设置 max_depth 和 min_samples_split
使用交叉验证选择最优参数
考虑集成方法如随机森林

以鸢尾花数据集为例：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 数据加载与预处理
iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# 模型训练
tree = C45DecisionTree(max_depth=3)
tree.fit(X_train, y_train)

# 评估
accuracy = np.mean(tree.predict(X_test) == y_test)
print(f"Test Accuracy: {accuracy:.2f}")