CART决策树算法实现：从原理到工程落地的最佳实践

1次阅读

没有评论

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

决策树算法因其解释性强、对数据分布要求低等特点，在风控、推荐系统等领域广泛应用。而 CART（Classification and Regression Trees）作为其中最经典的算法之一，其优势在于：

同时支持分类和回归任务
使用基尼系数作为分裂标准，计算效率高于信息增益
二叉树结构天然适合工程化实现

但在实际落地时，我们会遇到特征处理、过拟合、计算效率等一系列挑战。下面就从原理到代码，一步步拆解如何实现一个工业级的 CART 算法。

CART 使用基尼系数衡量节点纯度，其定义为：

$$Gini(p) = 1 – \sum_{k=1}^K p_k^2$$

其中 $p_k$ 是样本属于第 k 类的概率。与信息增益相比：

基尼系数计算不涉及对数运算，速度更快
两者对特征选择的倾向性差异很小
基尼系数的最大值是 0.5（二分类时），而信息增益无固定范围

实际工程中更推荐使用基尼系数，特别是在特征维度高时优势明显。

虽然 CART 本身支持连续值特征，但合理的离散化能提升模型效果：

对连续特征先排序，只考虑候选分裂点为相邻样本的中点
类别型特征采用 one-vs-rest 策略寻找最优分裂
实现时可以预计算所有可能的分裂点，避免重复计算

需要设置合理的停止条件防止过拟合：

节点样本数小于 min_samples_leaf
所有特征都已使用
节点基尼系数低于阈值（如 0.05）
树深度达到 max_depth

CCP（Cost-Complexity Pruning）是常用方法：

$$R_\alpha(T) = R(T) + \alpha|\tilde{T}|$$

其中 $R(T)$ 是误分类率，$|\tilde{T}|$ 是叶节点数。通过交叉验证选择最优的 $\alpha$。

class TreeNode:
    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 gini(y):
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities ** 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 threshold in thresholds:
            left_idx = X[:, feature_idx] <= threshold
            g = (gini(y[left_idx]) * np.sum(left_idx) + 
                 gini(y[~left_idx]) * np.sum(~left_idx)) / len(y)
            if g < best_gini:
                best_gini = g
                best_feature = feature_idx
                best_thresh = threshold
    return best_feature, best_thresh