C4.5决策树算法解析：从数学原理到工程实现

1次阅读

没有评论

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

决策树是机器学习中常用的分类与回归方法，因其模型直观、可解释性强而广受欢迎。ID3 算法作为早期决策树代表，采用信息增益作为特征选择标准，但存在两个明显缺陷：

对取值数目较多的属性有偏好（如将 ”ID” 字段误判为重要特征）
无法直接处理连续值属性

C4.5 算法正是针对这些问题提出的改进方案，通过引入信息增益率和连续值处理机制，使算法更具实用性。

信息增益率 = 信息增益 / 分裂信息量，其中：

信息增益 Gain(S,A) = Entropy(S) – Σ(|Sv|/|S|)*Entropy(Sv)
分裂信息量 SplitInfo(S,A) = -Σ(|Sv|/|S|)*log2(|Sv|/|S|)

数学推导示例：

假设某属性 A 将 10 个样本划分为：- A1:4 个正例,1 个负例
- A2:2 个正例,3 个负例

原始熵 Entropy(S)=-0.5log0.5-0.5log0.5=1
A1 熵 =-(4/5)log(4/5)-(1/5)log(1/5)≈0.7219
A2 熵 =-(2/5)log(2/5)-(3/5)log(3/5)≈0.9710
信息增益 =1-(5/10)*0.7219-(5/10)*0.9710≈0.1536
分裂信息量 =-(5/10)log(5/10)-(5/10)log(5/10)=1
最终信息增益率 =0.1536/1=0.1536

采用二分法离散化连续属性：

对属性值排序得到候选划分点集合 T
计算每个划分点 t 的信息增益率
选择最佳划分点作为决策节点

后剪枝 (PEP 方法) 步骤：

用训练集生成完整决策树
自底向上考察非叶节点
计算剪枝前后的预期错误率
保留错误率更低的子树结构

import numpy as np
from collections import Counter

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 _entropy(self, y):
        """计算信息熵"""
        counts = np.bincount(y)
        probs = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probs if p > 0])

    def _information_gain_ratio(self, X, y, feature_idx):
        """计算信息增益率"""
        # 原始熵
        parent_entropy = self._entropy(y)

        # 根据特征值划分样本
        values, counts = np.unique(X[:, feature_idx], return_counts=True)

        # 计算子节点加权熵
        child_entropy = 0
        split_info = 0
        for value, count in zip(values, counts):
            mask = X[:, feature_idx] == value
            child_entropy += (count / len(X)) * self._entropy(y[mask])
            split_info += -(count / len(X)) * np.log2(count / len(X))

        # 避免除零错误
        if split_info == 0:
            return 0

        info_gain = parent_entropy - child_entropy
        return info_gain / split_info

    # 完整实现包含 build_tree/predict 等方法...