C4.5决策树算法公式解析：从数学原理到Python实现

1次阅读

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

决策树是机器学习中经典的分类与回归方法，通过树形结构对数据进行分层划分。C4.5 算法由 Ross Quinlan 在 1993 年提出，是 ID3 算法的改进版本，核心改进在于使用 信息增益比 替代信息增益进行特征选择，有效缓解了 ID3 对多值属性的偏好问题。

核心特点：
支持连续属性（通过二分法离散化）
自动处理缺失值（通过概率权重分配）
内置剪枝机制防止过拟合

信息熵 $H(D)$ 衡量数据集 $D$ 的不确定性：
$$H(D) = -\sum_{k=1}^K p_k \log_2 p_k$$
其中 $p_k$ 为类别 $k$ 在数据集中的比例。

给定特征 $A$ 的条件熵 $H(D|A)$：
$$H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i)$$
信息增益 $G(D,A) = H(D) – H(D|A)$

为解决信息增益的偏差问题，引入特征固有值 $IV(A)$：
$$IV(A) = -\sum_{i=1}^n \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$$
最终信息增益比定义为：
$$G_R(D,A) = \frac{G(D,A)}{IV(A)}$$

对比维度	ID3 算法	C4.5 算法
特征选择	使用信息增益	使用信息增益比
连续值处理	不支持	支持二分法离散化
缺失值处理	直接丢弃含缺失值样本	按概率分布分配到子节点
剪枝策略	无	后剪枝（悲观错误剪枝）
计算效率	较高（仅需计算信息增益）	较低（需计算固有值）

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)
        ps = counts / len(y)
        return -np.sum([p * np.log2(p) for p in ps 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
        for value, count in zip(values, counts):
            subset = y[X[:, feature_idx] == value]
            child_entropy += (count / len(X)) * self._entropy(subset)

        # 计算固有值
        iv = -np.sum([(count/len(X)) * np.log2(count/len(X)) 
                      for count in counts])

        # 避免除零错误
        return (parent_entropy - child_entropy) / iv if iv > 0 else 0

连续值处理：
对连续属性排序后，选择相邻值的中位数作为候选划分点
计算每个划分点的信息增益比，选择最优划分
缺失值处理：
将含缺失值的样本按已知值的比例分配到各子节点
预测时，若遇到缺失特征，同时遍历所有可能路径并按概率加权
剪枝策略：
预剪枝：通过 max_depth、min_samples_split 等参数控制
后剪枝：训练完整树后，自底向上替换子树为叶节点，验证准确率变化

以经典的天气数据集为例：

Outlook	Temperature	Humidity	Windy	Play
Sunny	Hot	High	False	No
Overcast	Hot	High	True	Yes
…	…	…	…	…

计算步骤：
1. 计算整体信息熵 $H(D) = -\frac{5}{14}\log\frac{5}{14} – \frac{9}{14}\log\frac{9}{14} \approx 0.940$
2. 计算 Outlook 特征的信息增益比：
– $G(D,Outlook) = 0.940 – 0.694 = 0.246$
– $IV(Outlook) = 1.577$
– $G_R = 0.246/1.577 \approx 0.156$
3. 同理计算其他特征，选择增益比最大的作为根节点

适用场景：
– 特征同时包含离散值和连续值
– 需要可解释性强的模型
– 数据存在缺失值

局限性：
– 对高维稀疏数据效果较差
– 容易生成复杂树结构（需配合剪枝）
– 信息增益比计算成本较高

改进方向：
– 当特征间存在强相关性时，可考虑随机森林等集成方法
– 对于类别不平衡数据，需调整划分标准（如基尼指数）
– 在大数据场景下，可使用近似计算加速增益比评估

正文完