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

1次阅读

没有评论

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

决策树在工业界广泛应用于风控评分卡构建、用户行为分群以及医疗诊断辅助等场景。其优势在于模型可解释性强，能自动处理非线性关系，且对缺失值不敏感。特别是在需要快速业务决策的领域，决策树往往作为基线模型的首选。

基尼系数 (Gini Index) 与信息熵 (Entropy) 的数学表达分别为：

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

$$
H(D) = -\sum_{k=1}^K p_k \log_2 p_k
$$

两者的主要差异在于：
– 基尼系数的计算效率更高（省去对数运算）
– 信息熵对不纯度更敏感，容易产生更平衡的划分
– 实际应用中基尼系数通常作为默认选择

分裂停止的充分必要条件：
1. 当前节点样本数小于 min_samples_split
2. 所有特征分裂增益小于 min_impurity_decrease
3. 达到 max_depth 限制

数学证明：当特征 $X_j$ 对目标变量 $Y$ 的条件熵 $H(Y|X_j)$ 等于原始熵 $H(Y)$ 时，信息增益 $IG(X_j)=0$，此时继续分裂无意义。

设样本数 $n$，特征数 $m$，树深度 $d$：
– 最优情况（平衡树）：$O(m n \log n)$
– 最坏情况（链式树）：$O(m n^2)$
– 空间复杂度恒为 $O(d)$

def find_best_split(X: np.ndarray, y: np.ndarray) -> Tuple[int, float]:
    """时间复杂度: O(m*n^2) where m=features, n=samples"""
    best_gini = float('inf')
    best_feature, best_threshold = -1, None

    for feature_idx in range(X.shape[1]):
        # 处理连续特征
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            left_mask = X[:, feature_idx] <= threshold
            gini = weighted_gini(y[left_mask], y[~left_mask])
            if gini < best_gini:
                best_gini = gini
                best_feature = feature_idx
                best_threshold = threshold
    return best_feature, best_threshold

基于节点样本加权的不纯度下降：

def feature_importance(tree: TreeNode) -> Dict[int, float]:
    """后序遍历计算特征重要性"""
    importance = defaultdict(float)

    def _dfs(node):
        if node.is_leaf:
            return
        importance[node.split_feature] += \
            node.n_samples * node.gini_gain
        _dfs(node.left)
        _dfs(node.right)

    _dfs(tree.root)
    return {k: v/tree.total_samples for k,v in importance.items()}

预剪枝（Pre-pruning）：

class DecisionTree:
    def __init__(self, max_depth=3):
        self.max_depth = max_depth  # 直接限制生长深度

后剪枝（CCP）：

def cost_complexity_pruning(tree, alpha):
    """Bottom-up 剪枝"""
    weakest_link = find_weakest_link(tree)
    if weakest_link.ccp_alpha < alpha:
        weakest_link.make_leaf()