C4.5决策树算法演进史：从ID3到现代机器学习的桥梁

1次阅读

没有评论

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

决策树算法是机器学习中最直观的算法之一，它的历史可以追溯到上世纪 60 年代。早期决策树主要用于心理学和医学领域，直到 1986 年 Ross Quinlan 提出了 ID3 算法，决策树才真正进入机器学习的主流视野。

ID3 算法虽然简单有效，但存在几个明显的局限性：

对多值属性有强烈偏好：信息增益的计算方式使得具有更多取值的特征更容易被选中
无法处理连续值特征：只能处理离散型特征
容易过拟合：没有剪枝机制
对缺失值敏感：无法有效处理含有缺失值的数据

这些局限性促使了 C4.5 算法的诞生，它成为了决策树算法发展史上的重要里程碑。

C4.5 最关键的改进是用信息增益率 (Information Gain Ratio) 替代了信息增益。其数学定义为：

$$\text{GainRatio}(S,A) = \frac{\text{Gain}(S,A)}{\text{SplitInformation}(S,A)}$$

其中 SplitInformation 的计算公式为：

$$\text{SplitInformation}(S,A) = -\sum_{i=1}^{v}\frac{|S_i|}{|S|}\log_2\frac{|S_i|}{|S|}$$

这个改进有效缓解了 ID3 对多值属性的偏好问题。

C4.5 首次在决策树中引入了连续值处理能力，主要方法是将连续属性离散化：

对连续属性值进行排序
计算每两个相邻值的中点作为候选划分点
选择信息增益率最大的划分点
将该划分点作为二元分裂的标准

C4.5 采用了一种称为 ” 悲观剪枝 ” 的后剪枝技术：

先完整构建决策树
自底向上考察每个非叶节点
计算剪枝前后的预测错误率
使用二项式分布的上界估计错误率
如果剪枝能降低错误率上界，则执行剪枝

import numpy as np
from collections import Counter

class DecisionNode:
    def __init__(self, feature_idx=None, threshold=None, value=None, true_branch=None, false_branch=None):
        # 决策节点
        self.feature_idx = feature_idx  # 特征索引
        self.threshold = threshold      # 划分阈值(连续特征)
        self.value = value              # 叶节点的预测值
        self.true_branch = true_branch  # 左子树
        self.false_branch = false_branch # 右子树

    def entropy(self, y):
        """计算熵"""
        counts = Counter(y)
        probs = [count/len(y) for count in counts.values()]
        return -sum(p * np.log2(p) for p in probs if p > 0)  # 处理 p = 0 的情况

    def information_gain(self, X_col, y, threshold):
        """计算信息增益"""
        parent_entropy = self.entropy(y)

        # 划分数据集
        left_idx = X_col <= threshold
        right_idx = X_col > threshold

        n = len(y)
        n_left, n_right = sum(left_idx), sum(right_idx)

        if n_left == 0 or n_right == 0:
            return 0

        child_entropy = (n_left/n) * self.entropy(y[left_idx]) + \
                        (n_right/n) * self.entropy(y[right_idx])

        return parent_entropy - child_entropy

    def gain_ratio(self, X_col, y, threshold):
        """计算信息增益率"""
        gain = self.information_gain(X_col, y, threshold)

        # 计算分裂信息
        left_idx = X_col <= threshold
        right_idx = X_col > threshold
        n = len(y)
        n_left, n_right = sum(left_idx), sum(right_idx)

        if n_left == 0 or n_right == 0:
            return 0

        split_info = - (n_left/n) * np.log2(n_left/n) - (n_right/n) * np.log2(n_right/n)

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

        return gain / split_info

C4.5 在类别不平衡数据上表现相对稳定，因为它基于信息理论而不是简单的错误率。但仍有几点建议：