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

1次阅读

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

决策树是机器学习中最直观且易于解释的模型之一，在金融风控、医疗诊断、推荐系统等领域广泛应用。它能自动筛选重要特征，生成可读性强的规则，适合处理混合类型数据。工业界尤其青睐其无需特征缩放、支持并行计算的特点，可快速部署到生产环境。

决策树分裂质量的核心度量指标，CART 采用基尼系数（Gini Index），其定义为：
$$Gini(p) = 1 – \sum_{k=1}^K p_k^2$$
其中 $p_k$ 是样本属于第 $k$ 类的概率。相比信息熵 $H(p)=-\sum p_k\log p_k$，基尼系数计算更快（省去对数运算），且两者曲线形状相似（如下图）。实际应用中两者效果差异通常小于 2%。

对于特征 $A$ 的候选分割点 $s$，计算分裂后的基尼指数：
$$Gini(A,s) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$$
最优分裂点满足：
$$argmin_{A,s} Gini(A,s)$$
通过遍历所有特征的可能分割点（对连续值排序后取中点），选择使基尼指数下降最大的分裂方案。数学上可证明该贪婪策略在多数情况下能达到局部最优。

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  

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

def find_best_split(X, y):
    """寻找最佳分裂特征和阈值"""
    best_gini = float('inf')
    for feat_idx in range(X.shape[1]):
        # 对连续特征排序并取候选分割点
        thresholds = np.unique(X[:, feat_idx])
        for thr in thresholds:
            left_mask = X[:, feat_idx] <= thr
            curr_gini = (left_mask.sum() * gini(y[left_mask]) + 
                         (~left_mask).sum() * gini(y[~left_mask])) / len(y)
            if curr_gini < best_gini:
                best_gini = curr_gini
                best_feature, best_thr = feat_idx, thr
    return best_feature, best_thr