深入解析CART决策树算法原理：从数学基础到工程实现

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

决策树的工业价值

决策树在金融风控中用于快速判定贷款风险等级，电商推荐系统用它生成可解释的用户分群规则，医疗领域则依赖其白盒特性辅助临床决策。这种 ”if-then” 的规则形态，让非技术背景的业务方也能理解模型逻辑。

基尼系数与分裂条件

基尼系数本质

$$Gini(p) = 1-\sum_{k=1}^K p_k^2$$
相比信息熵 $H(p)=-\sum p_k\log p_k$，基尼系数计算更快（省去对数运算），但两者在 [0,0.5] 区间变化趋势高度一致。当类别概率均等时，基尼值达到最大值 0.5。

最优分裂证明

对于特征 A 的候选划分点 s，分裂后的基尼增益为：
$$\Delta Gini(A,s) = Gini(D) – \frac{|D_1|}{|D|}Gini(D_1) – \frac{|D_2|}{|D|}Gini(D_2)$$
需遍历所有特征的所有可能分割点，选择使 $\Delta Gini$ 最大的 (A,s) 组合。连续特征需先排序后取相邻值中点作为候选切分点。

Python 实现核心代码

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              # 类别分布

class CARTClassifier:
    def _gini(self, y):
        """计算基尼系数"""
        _, counts = np.unique(y, return_counts=True)
        return 1 - np.sum((counts/len(y))**2)

    def _best_split(self, X, y):
        """寻找最优分裂特征和阈值"""
        best_gain = -1
        for feat_idx in range(X.shape[1]):
            thresholds = np.unique(X[:, feat_idx])
            for thr in thresholds:
                left_mask = X[:, feat_idx] <= thr
                gain = self._gini(y) - \
                      left_mask.mean()*self._gini(y[left_mask]) - \
                      (~left_mask).mean()*self._gini(y[~left_mask])
                if gain > best_gain:
                    best_gain = gain
                    best_feat, best_thr = feat_idx, thr
        return best_feat, best_thr

    def fit(self, X, y, max_depth=5):
        """递归构建决策树"""
        # 终止条件：纯度达标 / 达到最大深度
        if max_depth==0 or self._gini(y)<0.05:
            return Node(value=np.bincount(y)/len(y))

        feat, thr = self._best_split(X, y)
        left_mask = X[:, feat] <= thr
        # 递归构建子树
        left = self.fit(X[left_mask], y[left_mask], max_depth-1)
        right = self.fit(X[~left_mask], y[~left_mask], max_depth-1)
        return Node(feat, thr, left, right)

工程优化策略

时间复杂度对比

• 递归实现：空间复杂度 $O(d)$（d 为树深度），但 Python 递归栈限制实际深度
• 迭代实现：需手动维护节点栈，但可突破递归深度限制

并行化可能

• 特征选择可并行：不同特征的分裂计算互不干扰
• 使用 joblib 加速特征遍历：

  from joblib import Parallel, delayed
  
  def _eval_feature(X_col, y, thresholds):
      return [compute_gini_gain(X_col, y, thr) for thr in thresholds]

生产环境避坑指南

类别不平衡处理

• 样本加权：对少数类样本赋予更高权重
• 代价敏感学习：修改分裂标准为带权基尼系数

剪枝方法对比

1. 预剪枝：限制最大深度 / 最小样本数
2. 代价复杂度剪枝（CCP）：sklearn 采用的黄金标准
3. 最小误差剪枝：验证集误差不再降低时停止
4. 悲观剪枝：基于统计显著性检验
5. 基于 MDL 的剪枝：考虑编码长度

开放性问题

1. 如何改进 CART 对高维稀疏特征（如用户行为序列）的处理效率？
2. 在在线学习场景下，决策树如何实现动态增量更新？
3. 当特征间存在强相关性时，分裂标准是否需要调整？

实现完整 CART 树需要考虑更多工程细节：缺失值处理可采用代理分裂，连续特征需动态离散化。建议在掌握核心原理后，逐步扩展这些生产级功能模块。