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

1次阅读

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

决策树是机器学习中常用的分类方法，它通过树形结构对数据进行划分，每个内部节点表示一个属性判断，每个分支代表一个判断结果，最终叶子节点对应分类结果。ID3 算法作为早期决策树算法，存在以下明显局限：

仅支持离散属性，无法处理连续值
采用信息增益作为划分标准，容易偏向取值多的属性
没有剪枝机制，容易过拟合

信息增益率是 C4.5 对 ID3 最重要的改进，其计算分为两步：

首先计算信息增益：

Gain(S,A) = Entropy(S) - Σ(|Sv|/|S|)*Entropy(Sv)

然后计算分裂信息：

SplitInfo(S,A) = -Σ(|Sv|/|S|)*log2(|Sv|/|S|)

最终信息增益率：

GainRatio(S,A) = Gain(S,A)/SplitInfo(S,A)

C4.5 采用二分法处理连续属性：

对属性值排序
取相邻值中点作为候选划分点
选择信息增益率最大的划分点

C4.5 采用悲观剪枝 (Pessimistic Pruning)：

计算节点误差率上限
比较剪枝前后的预期误差
当剪枝能降低误差时执行剪枝

以下是核心类的框架实现：

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)

        # 如果是连续特征
        if self._is_continuous(feature_idx):
            # 寻找最佳划分点
            threshold = self._find_best_split(X[:, feature_idx], y)
            left_idx = X[:, feature_idx] <= threshold
            right_idx = X[:, feature_idx] > threshold

            n = len(y)
            n_left, n_right = np.sum(left_idx), np.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])
            gain = parent_entropy - child_entropy

            # 计算分裂信息
            split_info = -((n_left/n)*np.log2(n_left/n) + \
                          (n_right/n)*np.log2(n_right/n))

        else:  # 离散特征
            # 实现类似 ID3 的信息增益计算
            pass

        return gain / split_info if split_info != 0 else 0

    # 其他必要方法...