决策树实战：CART算法原理与高效实现避坑指南

1次阅读

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

决策树训练的计算复杂度为 O(n_features×n_samples×log(n_samples))，传统递归实现存在两大问题：

内存消耗大 ：每次分裂需要保存整个子数据集
无法并行化 ：递归调用导致特征计算串行执行

以 10 万样本、100 维的数据为例，单线程递归构建深度 10 的树需要约 15 分钟，严重影响生产环境迭代效率。

算法	分裂标准	数学表达式	适用场景
ID3	信息增益	IG(D,A)=H(D)-H(D│A)	离散特征
C4.5	增益率	GainRatio=IG(D,A)/H_A(D)	混合特征
CART	基尼系数	Gini(D)=1-∑(p_i)^2	分类 / 回归任务

CART 的优势在于：
1. 支持连续特征自动分箱
2. 基尼系数计算量比熵小 30%（无对数运算）
3. 天然适合处理类别不平衡数据

基尼指数反映数据不纯度，对于特征 A 的分裂点 s：

def gini(left_y, right_y):
    # 计算左右子节点的基尼系数加权和
    p_left = len(left_y) / (len(left_y) + len(right_y))
    gini_left = 1 - np.sum((np.bincount(left_y) / len(left_y))**2)
    gini_right = 1 - np.sum((np.bincount(right_y) / len(right_y))**2)
    return p_left * gini_left + (1 - p_left) * gini_right

通过 numpy 广播机制实现多特征同步计算：

# 预处理：对每个特征列进行排序
sorted_indices = np.argsort(X, axis=0)
sorted_X = np.take_along_axis(X, sorted_indices, axis=0)
sorted_y = np.take_along_axis(y, sorted_indices, axis=0)

# 计算所有可能分裂点的基尼系数
split_gini = np.apply_along_axis(lambda col: [gini(y[:i], y[i:]) 
                for i in range(1, len(y))], 
    axis=0, 
    arr=sorted_X)
best_split_idx = np.argmin(split_gini, axis=0)

对连续特征只需排序一次，后续分裂直接复用：

初始化阶段对所有特征列排序
存储排序后的索引矩阵
分裂时通过掩码快速定位子集

将基尼系数计算编译为 C 代码：

# cython_gini.pyx
import numpy as np
cimport numpy as cnp

def cython_gini(cnp.ndarray[double] y):
    cdef double[:] classes = np.zeros(10)  # 假设最多 10 类
    cdef double total = 0
    for val in y:
        classes[<int>val] += 1
        total += 1
    return 1 - sum((c/total)**2 for c in classes)

错误做法：
– 在全局数据集上做 LabelEncoding（会泄露测试集分布）

正确流程：
1. 仅用训练数据拟合编码器
2. 保存编码映射关系
3. 测试时处理未知类别为特殊值

经验性配置：