CART决策树算法实战：从特征选择到工程落地避坑指南

1次阅读

没有评论

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

面对结构化数据建模时，决策树常遇到三类典型问题：

过拟合问题：当数据特征维度较高时，传统决策树容易生成过于复杂的树结构，导致在训练集上表现良好但测试集上性能骤降
特征重要性偏差：信息增益倾向于选择取值较多的特征，而这类特征不一定具有真正的预测能力
类别特征处理难题：One-Hot 编码会导致特征空间爆炸，尤其当类别基数较大时（如用户 ID、城市编码等）

与 ID3/C4.5 相比，CART 算法有三大显著差异：

二叉树结构：每个非叶节点只产生两个分支，相比多叉树更易于解释和优化
Gini 系数替代信息增益：计算复杂度从 $O(c\log c)$ 降为 $O(c)$（c 为类别数），且对类别分布不敏感
支持回归任务：通过方差最小化实现连续值预测，扩展了应用场景

Gini 系数的计算公式为：
$$Gini(D) = 1 – \sum_{k=1}^K p_k^2$$
其中 $p_k$ 表示第 k 类样本在数据集 D 中的比例。相比信息增益比，Gini 系数避免了 log 运算且对异常值更鲁棒。

输入预处理：
连续特征离散化（等频 / 等宽分箱）
类别特征采用目标编码（Target Encoding）
最优分裂点选择：
对每个特征计算所有可能分裂点的 Gini 指数
选择使 $Gini(D) – \frac{|D_1|}{|D|}Gini(D_1) – \frac{|D_2|}{|D|}Gini(D_2)$ 最大的特征和分裂点
停止条件判断：
节点样本数小于预定阈值（如 5）
Gini 下降量小于阈值（如 0.001）
达到最大树深度

import numpy as np

class Node:
    def __init__(self, feature_idx=None, threshold=None, 
                 left=None, right=None, value=None):
        # 分裂特征索引（非叶节点）self.feature_idx = feature_idx  
        # 分裂阈值
        self.threshold = threshold
        # 左右子节点
        self.left = left
        self.right = right
        # 叶节点预测值
        self.value = value

def compute_gini(y):
    """计算 Gini 系数"""
    _, counts = np.unique(y, return_counts=True)
    p = counts / len(y)
    return 1 - np.sum(p**2)

def find_best_split(X, y):
    """寻找最优分裂特征和阈值"""
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    # 遍历所有特征
    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        # 遍历所有可能的分裂点
        for thresh in thresholds:
            left_idx = X[:, feature_idx] <= thresh
            right_idx = ~left_idx

            if len(y[left_idx]) == 0 or len(y[right_idx]) == 0:
                continue

            # 计算加权 Gini
            gini_left = compute_gini(y[left_idx])
            gini_right = compute_gini(y[right_idx])
            total_gini = (len(y[left_idx]) * gini_left + 
                          len(y[right_idx]) * gini_right) / len(y)

            if total_gini < best_gini:
                best_gini = total_gini
                best_feature = feature_idx
                best_thresh = thresh

    return best_feature, best_thresh

后剪枝（Post-Pruning）流程：

从训练集划分验证集（或使用交叉验证）
自底向上遍历非叶节点
尝试将子树替换为叶节点（用该节点下样本的众数 / 均值作为预测值）
如果验证集准确率不下降，则执行剪枝

def prune_tree(node, X_val, y_val):
    if node.left is None or node.right is None:
        return

    # 递归剪枝左右子树
    prune_tree(node.left, X_val, y_val)
    prune_tree(node.right, X_val, y_val)

    # 尝试剪枝当前节点
    original_acc = evaluate(node, X_val, y_val)

    # 临时保存子树
    left_bak, right_bak = node.left, node.right

    # 尝试替换为叶节点
    node.left = node.right = None
    node.value = np.mean(y_val)  # 回归任务用均值，分类用众数

    new_acc = evaluate(node, X_val, y_val)

    if new_acc >= original_acc:  # 剪枝后精度未下降
        return  
    else:  # 恢复原状
        node.left, node.right = left_bak, right_bak
        node.value = None

对于高维稀疏数据（如用户行为特征）：

采用 CSR/CSC 稀疏矩阵存储（scipy.sparse）
特征分箱时使用近似算法（如直方图近似）
限制树的最大深度（通常不超过 10 层）

当进行特征并行计算时：

为每个特征分配独立随机数种子
使用线程锁保护共享数据结构
避免在分裂点评估时修改原始数据

from threading import Lock

class ConcurrentGiniCalculator:
    def __init__(self):
        self.lock = Lock()
        self.best_gini = float('inf')

    def update_best_split(self, gini, feature, threshold):
        with self.lock:
            if gini < self.best_gini:
                self.best_gini = gini
                self.best_feature = feature
                self.best_threshold = threshold

替代 One-Hot 编码的两种方法：

目标编码（Target Encoding）：
用该类别下目标变量的均值（回归）或类别概率（分类）作为特征值
需添加平滑项防止过拟合：
$$encoded = \frac{count \times mean + global_mean \times \alpha}{count + \alpha}$$
Embedding 映射：
通过神经网络学习类别特征的稠密表示
适合与深度学习模型联合使用

改进的加权 Gini 计算：

$$Gini_w(D) = 1 – \sum_{k=1}^K (w_k p_k)^2$$

其中 $w_k$ 是第 k 类的权重，通常取：
$$w_k = \frac{total_samples}{n_classes \times count(k)}$$

CART 天然适合作为 GBDT 的基学习器：

梯度提升框架：
每轮迭代拟合当前模型的负梯度
CART 树用于逼近残差
实现要点：
限制树的深度（通常 3 - 6 层）
采用二阶梯度（Hessian）进行节点分裂
引入行采样 / 列采样增强多样性

通过 sklearn.ensemble.GradientBoostingClassifier 可快速验证效果：

from sklearn.ensemble import GradientBoostingClassifier
from sklearn.datasets import make_classification

# 生成测试数据
X, y = make_classification(n_samples=1000, n_features=20, 
                          n_informative=5, n_classes=3)

# 使用 CART 作为基学习器的 GBDT 模型
gbdt = GradientBoostingClassifier(
    max_depth=3,      # 单棵树最大深度
    learning_rate=0.1,
    n_estimators=100
)
gbdt.fit(X, y)