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

1次阅读

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

CART 决策树在推荐系统中能快速处理混合特征类型，成为用户画像构建的核心组件；在金融风控领域，其白盒特性满足监管要求的同时，通过 Gini 系数有效识别高风险交易；工业级应用中，二叉结构和剪枝策略使其成为高维稀疏数据处理的瑞士军刀。

Gini 系数：衡量节点纯度，计算式为 $Gini(p) = 1-\sum_{k=1}^K p_k^2$，其中 $p_k$ 是第 k 类样本占比。与信息熵 $H(p)=-\sum p_k\log p_k$ 相比，Gini 计算量更小且对分布差异更敏感
分裂收益计算：对于特征 $A$ 的分裂点 $s$，分裂增益 $\Delta = Gini(D) – \frac{|D_1|}{|D|}Gini(D_1) – \frac{|D_2|}{|D|}Gini(D_2)$，其中 $D_1/D_2$ 为分裂后子集

理论基础：当满足以下任一条件时停止分裂
节点样本数小于预设阈值（防止过拟合）
Gini 系数下降幅度小于 $\epsilon$（通常设 0.001）
达到最大树深度（控制模型复杂度）
数学验证：通过归纳法可证明，当特征空间划分为有限区域时，有限深度树必能收敛

import numpy as np
from collections import Counter

class CARTNode:
    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 __init__(self, max_depth=5, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split

    def _gini(self, y):
        # 时间复杂度 O(K), K 为类别数
        counts = np.bincount(y)
        return 1 - np.sum((counts / len(y)) ** 2)

    def _best_split(self, X, y):
        best_gini = float('inf')
        best_idx, best_thresh = None, None

        # 时间复杂度 O(m*n), m 为特征数,n 为样本数
        for feature_idx in range(X.shape[1]):
            thresholds = np.unique(X[:, feature_idx])
            for thresh in thresholds:
                left_idx = X[:, feature_idx] <= thresh
                gini = self._gini(y[left_idx]) * left_idx.sum() / len(y) + \
                       self._gini(y[~left_idx]) * (~left_idx).sum() / len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_idx = feature_idx
                    best_thresh = thresh
        return best_idx, best_thresh

    def fit(self, X, y, depth=0):
        # 预剪枝条件判断
        if depth >= self.max_depth or len(y) < self.min_samples_split \
           or len(np.unique(y)) == 1:
            return CARTNode(value=Counter(y).most_common(1)[0][0])

        idx, thresh = self._best_split(X, y)
        left_idx = X[:, idx] <= thresh
        node = CARTNode(feature_idx=idx, threshold=thresh,
                       left=self.fit(X[left_idx], y[left_idx], depth+1),
                       right=self.fit(X[~left_idx], y[~left_idx], depth+1))
        return node

特征重要性计算：sklearn 采用加权平均的 Gini 下降量，而上述实现可通过节点样本占比加权
类别型特征处理：sklearn 内部使用 OneHot 编码，我们示例直接比较阈值
并行优化：sklearn 利用 Cython 加速，我们的 Python 原生实现更适合教学演示

有序类别编码 ：对学历等有序类别，使用[0,1,2,…] 代替 OneHot
直方图加速：对连续特征先分箱为 10-20 个桶，减少分裂点计算量
Gini 增益缓存：对高频类别值预计算分裂收益

# Mapper 阶段
for feature in features:
    local_counts = calculate_local_gini(X_partition, y_partition, feature)
    emit(feature, local_counts)

# Reducer 阶段
global_gini = aggregate_all_mappers()
best_feature = find_min_gini(global_gini)