C4.5决策树实战：如何高效处理高维异构数据集

1次阅读

没有评论

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

在机器学习项目中，我们常常会遇到高维异构数据集——这种数据集通常包含数百甚至数千个特征，且特征类型混杂（如数值型、类别型、文本型等）。对于传统决策树算法来说，这类数据会带来几个典型问题：

计算复杂度爆炸：随着特征数量增加，信息增益计算的时间复杂度呈指数级增长
特征相关性干扰：大量无关或冗余特征会 ” 淹没 ” 真正重要的特征信号
过拟合风险：树模型容易在噪声特征上过度生长，导致泛化性能下降

以我们最近处理的电商用户行为数据为例，原始数据集包含 1200+ 特征（包括点击流、demographics、历史订单等），直接使用 ID3 算法训练时单次分裂就需要近 30 分钟。

在决策树家族中，C4.5 相比其他算法有几个关键优势：

信息增益率：通过引入 SplitInfo 惩罚项，避免偏向多值特征
```
GainRatio(S,A) = Gain(S,A) / SplitInfo(S,A)
```
连续值处理：自动对连续特征进行二分离散化，不需要人工分桶
缺失值鲁棒性：通过概率加权处理缺失值，比 CART 的替代分裂更灵活

与 ID3 和 CART 的对比实验显示，在 UCI 的 Adult 数据集上：

算法	训练时间(s)	测试准确率
ID3	142	84.2%
C4.5	98	85.7%
CART	105	85.1%

以下是 C4.5 的关键组件实现，重点优化了计算效率：

import numpy as np
from collections import Counter

class C45Node:
    def __init__(self, feature_idx=None, threshold=None, children=None, leaf_value=None):
        self.feature_idx = feature_idx  # 分裂特征索引
        self.threshold = threshold      # 连续特征的分裂阈值
        self.children = children        # 子节点字典
        self.leaf_value = leaf_value    # 叶节点的预测值

    def _calc_entropy(self, y):
        """计算类别的信息熵 O(c*n) c 为类别数"""
        counts = np.bincount(y)
        probs = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probs if p > 0])

    def _calc_split_info(self, X_feature):
        """计算分裂信息 O(nlogn) 主要来自排序"""
        _, counts = np.unique(X_feature, return_counts=True)
        probs = counts / counts.sum()
        return -np.sum(probs * np.log2(probs))

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

        parent_entropy = self._calc_entropy(y)

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

            if np.issubdtype(X_feature.dtype, np.number):  # 连续特征
                # 排序后计算相邻中点作为候选阈值 O(nlogn)
                sorted_values = np.sort(np.unique(X_feature))
                thresholds = (sorted_values[:-1] + sorted_values[1:]) / 2

                for threshold in thresholds:
                    left_mask = X_feature <= threshold
                    gain = parent_entropy - (len(y[left_mask])/len(y) * self._calc_entropy(y[left_mask]) +
                        len(y[~left_mask])/len(y) * self._calc_entropy(y[~left_mask])
                    )
                    split_info = self._calc_split_info(X_feature <= threshold)
                    gain_ratio = gain / (split_info + 1e-10)  # 避免除以 0

                    if gain_ratio > best_gain_ratio:
                        best_gain_ratio = gain_ratio
                        best_feature = feat_idx
                        best_threshold = threshold
            else:  # 类别特征
                # ... 类别特征处理逻辑（类似但无需阈值）pass

        return best_feature, best_threshold, best_gain_ratio

我们在实现中加入了三种停止条件：

最小样本分裂：节点样本数 < 总样本的 1% 时停止
增益率阈值：最大增益率 < 0.01 时停止
最大深度：默认限制树深为 8 层

def pessimistic_prune(node, X_val, y_val):
    if node.leaf_value is not None:
        return node

    # 递归剪枝子树
    for val, child in node.children.items():
        mask = X_val[:, node.feature_idx] == val
        node.children[val] = pessimistic_prune(child, X_val[mask], y_val[mask])

    # 计算当前节点的错误率上界
    preds = np.array([self._predict(x) for x in X_val])
    error = np.sum(preds != y_val)
    UCF = error + 0.5  # 使用连续性校正

    # 计算替换为叶节点后的错误率上界
    majority_class = Counter(y_val).most_common(1)[0][0]
    leaf_error = np.sum(y_val != majority_class)
    UCF_leaf = leaf_error + 0.5

    if UCF_leaf <= UCF:  # 剪枝条件
        return C45Node(leaf_value=majority_class)
    return node

对于正负样本比超过 1:5 的数据集，建议：

在计算信息增益时使用 加权熵
采用 SMOTE 过采样与 Tomek Links 欠采样组合
在剪枝阶段使用 Fβ-score 替代准确率

当特征维度 > 1000 时：

使用 scipy.sparse 存储稀疏矩阵
对连续特征采用分位数离散化
实现特征选择层（基于互信息预筛选）

from sklearn.feature_selection import mutual_info_classif

# 预选 Top 200 特征
mi_scores = mutual_info_classif(X, y)
selected_features = np.argsort(mi_scores)[-200:]
X_reduced = X[:, selected_features]

在 UCI 的 Credit Approval 数据集上的对比结果：