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

1次阅读

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

决策树是一种经典的机器学习算法，通过树状结构对数据进行分类或回归。C4.5 算法由 Ross Quinlan 在 1993 年提出，是 ID3 算法的改进版本，主要解决了 ID3 无法处理连续特征和缺失值的问题，并引入信息增益比来减少对多值特征的偏好。

C4.5 算法的核心是信息增益比（Gain Ratio），它是对信息增益的改进，能够避免选择取值较多的特征。其计算分为以下三步：

计算信息熵（Entropy）：
$$Entropy(S) = -\sum_{i=1}^{c}p_i\log_2p_i$$
其中 $S$ 是样本集合，$c$ 是类别数，$p_i$ 是第 $i$ 类样本的比例。
计算信息增益（Information Gain）：
$$Gain(S,A) = Entropy(S) – \sum_{v\in Values(A)}\frac{|S_v|}{|S|}Entropy(S_v)$$
$A$ 是某个特征，$Values(A)$ 是特征 $A$ 的取值集合，$S_v$ 是 $A$ 取值为 $v$ 的样本子集。
计算信息增益比：
$$GainRatio(S,A) = \frac{Gain(S,A)}{SplitInfo(S,A)}$$
其中分裂信息 $SplitInfo(S,A)$ 的计算公式为：
$$SplitInfo(S,A) = -\sum_{v\in Values(A)}\frac{|S_v|}{|S|}\log_2\frac{|S_v|}{|S|}$$

ID3 算法
仅能处理离散特征
使用信息增益作为特征选择标准
容易偏向取值较多的特征
无法处理缺失值
C4.5 算法
可以处理连续特征（通过二分法离散化）
使用信息增益比减少多值特征偏好
能够处理缺失值
引入了剪枝策略防止过拟合

import numpy as np
import math

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 连续特征的分裂阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点的类别

class C45DecisionTree:
    def __init__(self, min_samples_split=2, max_depth=None):
        self.min_samples_split = min_samples_split
        self.max_depth = max_depth
        self.root = None

    def _entropy(self, y):
        _, counts = np.unique(y, return_counts=True)
        probs = counts / len(y)
        return -np.sum(probs * np.log2(probs))

    def _split_info(self, X_feature):
        _, counts = np.unique(X_feature, return_counts=True)
        probs = counts / len(X_feature)
        return -np.sum(probs * np.log2(probs))

    def _information_gain_ratio(self, X, y, feature_idx):
        # 计算信息增益
        parent_entropy = self._entropy(y)
        X_feature = X[:, feature_idx]
        unique_values = np.unique(X_feature)

        child_entropy = 0
        for value in unique_values:
            mask = X_feature == value
            child_y = y[mask]
            if len(child_y) > 0:
                child_entropy += (len(child_y)/len(y)) * self._entropy(child_y)

        information_gain = parent_entropy - child_entropy

        # 计算分裂信息
        split_info = self._split_info(X_feature)

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

        return information_gain / split_info

    def _best_split(self, X, y, features):
        best_gain_ratio = -1
        best_feature = None
        best_threshold = None

        for feature_idx in features:
            X_feature = X[:, feature_idx]

            # 处理连续特征
            if len(np.unique(X_feature)) > 10:  # 假设超过 10 个不同值视为连续特征
                thresholds = np.unique(X_feature)
                for threshold in thresholds:
                    gain_ratio = self._information_gain_ratio(X, y, feature_idx)
                    if gain_ratio > best_gain_ratio:
                        best_gain_ratio = gain_ratio
                        best_feature = feature_idx
                        best_threshold = threshold
            else:  # 离散特征
                gain_ratio = self._information_gain_ratio(X, y, feature_idx)
                if gain_ratio > best_gain_ratio:
                    best_gain_ratio = gain_ratio
                    best_feature = feature_idx
                    best_threshold = None

        return best_feature, best_threshold

    def _build_tree(self, X, y, features, depth=0):
        n_samples, n_features = X.shape
        n_labels = len(np.unique(y))

        # 终止条件
        if (depth >= self.max_depth if self.max_depth is not None else False) or \
           (n_labels == 1) or \
           (n_samples < self.min_samples_split):
            leaf_value = np.bincount(y).argmax()
            return Node(value=leaf_value)

        # 寻找最佳分裂
        best_feature, best_threshold = self._best_split(X, y, features)

        if best_feature is None:
            leaf_value = np.bincount(y).argmax()
            return Node(value=leaf_value)

        # 递归构建子树
        node = Node(feature=best_feature, threshold=best_threshold)

        if best_threshold is not None:  # 连续特征
            left_mask = X[:, best_feature] <= best_threshold
            right_mask = ~left_mask

            left_subtree = self._build_tree(X[left_mask], y[left_mask], features, depth+1)
            right_subtree = self._build_tree(X[right_mask], y[right_mask], features, depth+1)

            node.left = left_subtree
            node.right = right_subtree
        else:  # 离散特征
            unique_values = np.unique(X[:, best_feature])
            new_features = [f for f in features if f != best_feature]

            for value in unique_values:
                mask = X[:, best_feature] == value
                if np.any(mask):
                    subtree = self._build_tree(X[mask], y[mask], new_features, depth+1)
                    setattr(node, f"child_{value}", subtree)

        return node

    def fit(self, X, y):
        self.root = self._build_tree(X, y, list(range(X.shape[1])))

    def predict(self, X):
        return np.array([self._traverse_tree(x, self.root) for x in X])

    def _traverse_tree(self, x, node):
        if node.value is not None:
            return node.value

        if node.threshold is not None:  # 连续特征
            if x[node.feature] <= node.threshold:
                return self._traverse_tree(x, node.left)
            else:
                return self._traverse_tree(x, node.right)
        else:  # 离散特征
            value = x[node.feature]
            child_node = getattr(node, f"child_{value}", None)
            if child_node is not None:
                return self._traverse_tree(x, child_node)
            else:
                # 处理未知特征值，返回当前节点的多数类
                return self._majority_class(node)

    def _majority_class(self, node):
        # 后序遍历计算每个节点的多数类
        if node.value is not None:
            return node.value

        class_counts = {}
        if node.threshold is not None:  # 连续特征
            left_class = self._majority_class(node.left)
            right_class = self._majority_class(node.right)

            class_counts[left_class] = class_counts.get(left_class, 0) + 1
            class_counts[right_class] = class_counts.get(right_class, 0) + 1
        else:  # 离散特征
            for attr in dir(node):
                if attr.startswith('child_'):
                    child_node = getattr(node, attr)
                    child_class = self._majority_class(child_node)
                    class_counts[child_class] = class_counts.get(child_class, 0) + 1

        return max(class_counts.items(), key=lambda x: x[1])[0]

连续值处理
C4.5 通过二分法将连续特征离散化
需要对连续特征进行排序，并测试每个可能的分割点
选择信息增益比最大的分割点作为阈值
缺失值处理
训练时可以忽略含缺失值的样本
预测时将缺失值样本分配到所有子节点，根据概率加权
实际应用中也可以使用均值 / 众数填充
剪枝策略
预剪枝：在构建树时限制深度、最小样本数等
后剪枝：先构建完整树，再自底向上剪枝
可基于验证集错误率进行剪枝决策
其他注意事项
类别不平衡问题：可以使用加权信息增益
特征重要性评估：基于信息增益比的值
大数据处理：可能需要分布式实现

使用经典的鸢尾花数据集演示 C4.5 算法的运行过程：

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target

# 划分训练测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 训练模型
model = C45DecisionTree(max_depth=3)
model.fit(X_train, y_train)

# 评估
predictions = model.predict(X_test)
accuracy = np.sum(predictions == y_test) / len(y_test)
print(f"Test Accuracy: {accuracy:.2f}")

C4.5 算法的优势在于能够处理连续特征和缺失值，通过信息增益比减少了多值特征的偏好，具有较强的可解释性。但也存在一些局限性：