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

1次阅读

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

在结构化数据建模中，决策树虽然直观易懂，但实际应用常遇到三类典型问题：

过拟合问题 ：当特征维度较高时（如电商用户行为数据包含上千个特征），决策树会倾向于生成非常深的分支，导致在训练集上表现完美但测试集效果差。
特征重要性偏差 ：传统信息增益指标会偏向选择取值较多的特征（如用户 ID 这种高基数特征），而实际上这些特征可能并无预测价值。
类别特征处理困难 ：对城市、商品类别等非数值型特征，常规的 One-Hot 编码会导致特征空间爆炸（维度灾难）。

相比 ID3/C4.5 算法，CART(Classification And Regression Trees) 有以下差异点：

二叉树结构 ：每个节点只产生两个分支，相比多叉树更易于解释和优化
Gini 系数替代信息增益 ：计算效率更高且对类别分布不敏感，公式为：
$$Gini(p) = 1 – \sum_{k=1}^K p_k^2$$
支持回归任务 ：通过方差最小化处理连续目标值

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, self.right = left, right  
        # 叶子节点的预测值
        self.value = value  

def gini_impurity(y):
    """计算 Gini 不纯度"""
    m = y.size
    return 1.0 - sum((np.sum(y == c) / m) ** 2 for c in np.unique(y))

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_mask = X[:, feature_idx] <= thresh
            gini = (gini_impurity(y[left_mask]) * np.sum(left_mask) + 
                    gini_impurity(y[~left_mask]) * np.sum(~left_mask)) / y.size

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

    return best_feature, best_thresh

实际工程中需要设置以下终止条件：

节点样本数小于预设值（如 min_samples_leaf=5）
所有特征都已被使用
Gini 下降幅度小于阈值（如 min_impurity_decrease=0.01）

对于高维稀疏数据（如用户行为特征），推荐采用以下存储格式：

CSR 压缩格式 ：使用 scipy.sparse.csr_matrix 存储特征矩阵
特征哈希 ：对类别特征采用 feature hashing 替代 One-Hot

当实现特征并行搜索时，需注意：

使用线程锁保护共享变量
每个线程处理独立的特征子集
避免 False sharing（缓存行冲突）

from threading import Lock

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

    def update_best(self, new_gini, feature, thresh):
        with self.lock:
            if new_gini < self.best_gini:
                self.best_gini = new_gini
                # 更新最佳分裂点...

替代 One-Hot 的两种方案：

目标编码（Target Encoding）：用该类别对应目标值的均值编码
$$\text{encoded}i = \frac{\sum$$}^n y_j \cdot I(x_j = c_i)}{\sum_{j=1}^n I(x_j = c_i)
Count Encoding：用类别出现频次编码

修改 Gini 计算时的类权重：

def weighted_gini(y, sample_weight):
    total_weight = np.sum(sample_weight)
    return 1 - sum((np.sum(sample_weight[y == c]) / total_weight) ** 2 
                   for c in np.unique(y))

将 CART 作为 GBDT 的基学习器时：

在每轮迭代中拟合残差
通过 shrinkage 系数控制单棵树的影响力
采用特征子采样提升多样性

推荐测试数据生成方式：

from sklearn.datasets import make_classification
X, y = make_classification(n_samples=1000, n_features=20, 
                          n_informative=5, n_classes=3)

通过本文介绍的工程实践方案，可有效解决决策树在实际业务中的核心痛点。后续可进一步探索基于 CART 的集成方法如随机森林在实际系统中的部署优化。

正文完