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

1次阅读

没有评论

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

决策树是一种通过递归划分数据集的监督学习算法，其核心是通过特征选择构建树形结构。ID3 算法作为早期经典实现，采用信息增益作为划分标准，但存在两个明显缺陷：

对取值数目多的特征有偏好（如 ID 类特征）
无法直接处理连续值和缺失值

C4.5 算法在 ID3 基础上进行了三项关键改进：

引入信息增益比（Gain Ratio）替代信息增益
增加连续特征离散化处理
支持缺失值处理
加入后剪枝（Post-Pruning）策略

信息增益比通过引入分裂信息（Split Information）来修正信息增益的偏差。具体计算公式如下：

$$ GainRatio(D,A) = \frac{Gain(D,A)}{SplitInfo(D,A)} $$

其中：

$Gain(D,A)$ 是特征 A 的信息增益
$SplitInfo(D,A) = -\sum_{v=1}^V \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|} $ 称为内在信息

计算示例（天气特征）：

天气	是否打球
晴	否
晴	否
多云	是
雨	是
雨	是

原始熵：$H(D) = -[\frac{2}{5}\log_2\frac{2}{5} + \frac{3}{5}\log_2\frac{3}{5}] ≈ 0.971$
天气条件熵：$H(D| 天气) = \frac{2}{5}×0 + \frac{1}{5}×0 + \frac{2}{5}×0 = 0$
信息增益：$Gain = 0.971 – 0 = 0.971$
分裂信息：$SplitInfo = -[\frac{2}{5}\log_2\frac{2}{5} + \frac{1}{5}\log_2\frac{1}{5} + \frac{2}{5}\log_2\frac{2}{5}] ≈ 1.522$
信息增益比：$GainRatio ≈ 0.971/1.522 ≈ 0.638$

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)
        probs = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probs if p > 0])

    def _split_info(self, X_feature):
        _, counts = np.unique(X_feature, return_counts=True)
        probs = counts / len(X_feature)
        return -np.sum([p * np.log2(p) for p in probs if p > 0])

    def _information_gain_ratio(self, X_feature, y):
        parent_entropy = self._entropy(y)

        unique_values = np.unique(X_feature)
        child_entropy = 0

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

        info_gain = parent_entropy - child_entropy
        split_info = self._split_info(X_feature)

        return info_gain / split_info if split_info != 0 else 0

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

        for feature in features:
            gain_ratio = self._information_gain_ratio(X[:, feature], y)
            if gain_ratio > best_gain_ratio:
                best_gain_ratio = gain_ratio
                best_feature = feature

        return best_feature

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

        # 终止条件
        if (len(np.unique(y)) == 1 or 
            n_samples < self.min_samples_split or 
            (self.max_depth is not None and depth >= self.max_depth)):
            return Counter(y).most_common(1)[0][0]

        # 选择最佳特征
        best_feat = self._best_feature(X, y, features)
        best_feat_name = features[best_feat]

        # 构建子树
        tree = {best_feat_name: {}}
        remaining_features = [f for f in features if f != best_feat]

        for value in np.unique(X[:, best_feat]):
            mask = X[:, best_feat] == value
            X_subset, y_subset = X[mask], y[mask]

            if len(y_subset) == 0:
                tree[best_feat_name][value] = Counter(y).most_common(1)[0][0]
            else:
                tree[best_feat_name][value] = self._build_tree(X_subset, y_subset, remaining_features, depth+1)

        return tree

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

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

    def _predict_sample(self, x, tree):
        if not isinstance(tree, dict):
            return tree

        feature_idx = self.feature_names.index(next(iter(tree)))
        feature_value = x[feature_idx]

        if feature_value not in tree[next(iter(tree))]:
            return Counter(y_train).most_common(1)[0][0]

        subtree = tree[next(iter(tree))][feature_value]
        return self._predict_sample(x, subtree)

# 使用示例
from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data, iris.target
feature_names = iris.feature_names

model = C45DecisionTree(max_depth=3)
model.fit(X, y, feature_names)
print(model.predict([[5.1, 3.5, 1.4, 0.2]]))  # 输出预测类别

将连续特征排序后取相邻值中点作为候选划分点
计算每个划分点的信息增益比
选择最优划分点将连续特征转化为二值特征

改进后的划分标准计算：

def _handle_continuous_feature(self, X_feature, y):
    unique_values = np.unique(X_feature)
    if len(unique_values) < 2:
        return None, 0

    split_points = [(unique_values[i] + unique_values[i+1])/2 
                    for i in range(len(unique_values)-1)]

    best_gain_ratio = -1
    best_split = None

    for point in split_points:
        binary_feature = (X_feature >= point).astype(int)
        gain_ratio = self._information_gain_ratio(binary_feature, y)

        if gain_ratio > best_gain_ratio:
            best_gain_ratio = gain_ratio
            best_split = point

    return best_split, best_gain_ratio

训练阶段：
计算特征 A 的信息增益比时，仅使用 A 未缺失的样本
调整信息增益比计算公式中的权重系数
预测阶段：
当遇到缺失特征时，同时探索所有分支
按各分支样本占比加权汇总预测结果

悲观错误剪枝 (PEP) 实现步骤：

计算节点误差上界：
$$ e(t) = \frac{error(t) + 0.5}{N(t)} $$
$$ U_{CF}(e(t), N(t)) = e(t) + z_{α/2} \sqrt{\frac{e(t)(1-e(t))}{N(t)}} $$
计算子树误差：
$$ error(T_t) = \sum_{leaf} (error(leaf) + 0.5) $$
比较剪枝前后误差，决定是否剪枝

代码实现片段：

def _prune(self, node, X_val, y_val):
    if not isinstance(node, dict):
        return node

    # 先剪枝子树
    for feature_value in node[next(iter(node))]:
        if isinstance(node[next(iter(node))][feature_value], dict):
            node[next(iter(node))][feature_value] = self._prune(node[next(iter(node))][feature_value], X_val, y_val)

    # 计算当前节点作为叶节点的误差
    leaf_error = self._calculate_error(node, X_val, y_val)

    # 计算不剪枝的子树误差
    subtree_error = 0
    for sample, label in zip(X_val, y_val):
        subtree_error += (self._predict_sample(sample, node) != label)

    # 比较并决定是否剪枝
    if leaf_error <= subtree_error + self._std_err(subtree_error, len(y_val)):
        majority_class = Counter(y_val).most_common(1)[0][0]
        return majority_class

    return node