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

1次阅读

没有评论

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

决策树是机器学习中最直观的算法之一，它通过树形结构模拟人类决策过程。C4.5 作为 ID3 算法的升级版，主要解决了三个关键问题：

信息增益偏向多值属性：ID3 采用信息增益选择分裂属性，会倾向于选择取值多的属性（如 ID 编号）。C4.5 引入信息增益比进行修正
连续值处理：ID3 只能处理离散属性，C4.5 通过二分法支持连续特征
过拟合问题：C4.5 增加了后剪枝策略

信息增益比 = 信息增益 / 分裂信息熵

其中分裂信息熵计算公式：
$$\text{SplitInfo}(D,A) = -\sum_{j=1}^v \frac{|D_j|}{|D|} \log_2 \left(\frac{|D_j|}{|D|}\right)$$

物理意义：分裂信息熵度量了属性分裂产生的分支数量信息，有效抵消了多值属性的优势

对连续属性 a 的所有取值排序，得到候选划分点集合 T
计算每个划分点 t 的信息增益比
选择最佳划分点将连续属性转为二元分裂

采用 悲观剪枝（Pessimistic Pruning）：

计算节点误差率上限（使用二项分布置信区间）
比较剪枝前后的估计误差
当剪枝后估计误差更小时执行剪枝

import numpy as np
from collections import Counter

class C45Node:
    def __init__(self, feature=None, threshold=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 连续特征划分点
        self.children = {}  # 子节点字典
        self.value = value  # 叶节点预测值

class C45Tree:
    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 _split_info(self, X_column, thresholds):
        """计算分裂信息熵"""
        split_vals = np.digitize(X_column, thresholds)
        _, counts = np.unique(split_vals, return_counts=True)
        probs = counts / counts.sum()
        return -np.sum(probs * np.log2(probs))

    def _find_best_split(self, X, y):
        """寻找最佳分裂特征和划分点"""
        best_gain_ratio = -1
        best_feature = None
        best_threshold = None

        parent_entropy = self._entropy(y)

        for feature_idx in range(X.shape[1]):
            # 处理连续特征
            values = np.unique(X[:, feature_idx])
            thresholds = (values[:-1] + values[1:]) / 2

            for threshold in thresholds:
                left_idx = X[:, feature_idx] <= threshold
                right_idx = ~left_idx

                # 计算信息增益
                n = len(y)
                n_l, n_r = sum(left_idx), sum(right_idx)

                if n_l == 0 or n_r == 0:
                    continue

                e_l = self._entropy(y[left_idx])
                e_r = self._entropy(y[right_idx])
                info_gain = parent_entropy - (n_l/n * e_l + n_r/n * e_r)

                # 计算信息增益比
                split_info = self._split_info(X[:, feature_idx], [threshold])
                if split_info == 0:
                    continue
                gain_ratio = info_gain / split_info

                if gain_ratio > best_gain_ratio:
                    best_gain_ratio = gain_ratio
                    best_feature = feature_idx
                    best_threshold = threshold

        return best_feature, best_threshold

    def fit(self, X, y, depth=0):
        """递归构建决策树"""
        # 终止条件
        if len(y) < self.min_samples_split or \
           (self.max_depth is not None and depth >= self.max_depth):
            return C45Node(value=Counter(y).most_common(1)[0][0])

        # 寻找最佳分裂
        feature, threshold = self._find_best_split(X, y)
        if feature is None:
            return C45Node(value=Counter(y).most_common(1)[0][0])

        # 创建分裂节点
        node = C45Node(feature=feature, threshold=threshold)

        # 递归构建子树
        left_idx = X[:, feature] <= threshold
        right_idx = ~left_idx

        node.children['left'] = self.fit(X[left_idx], y[left_idx], depth+1)
        node.children['right'] = self.fit(X[right_idx], y[right_idx], depth+1)

        return node

在 UCI 的 Iris 数据集上进行测试：