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

1次阅读

没有评论

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

决策树的核心是分裂准则，CART（Classification and Regression Trees）使用基尼不纯度（Gini Impurity）或最小二乘误差（MSE）作为分裂标准。

对于分类问题，基尼系数衡量数据集的不纯度，定义为：

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

其中 $p_k$ 是第 $k$ 类样本在数据集 $D$ 中的比例。分裂后的加权基尼系数为：

$$ Gini_{split}(D) = \sum_{j=1}^{m} \frac{|D_j|}{|D|} Gini(D_j) $$

分裂的目标是最小化 $Gini_{split}(D)$。

对于回归问题，CART 使用最小二乘准则，即最小化分裂后的加权方差：

$$ \sum_{j=1}^{m} \frac{|D_j|}{|D|} Var(D_j) $$

ID3：使用信息增益（Information Gain），倾向于选择取值多的特征。
C4.5：使用信息增益比（Gain Ratio），解决了 ID3 的偏置问题。
CART：使用基尼系数或 MSE，支持回归任务，且生成二叉树。

在高维数据场景下，特征选择和分裂点计算可能成为性能瓶颈。例如，对于 $d$ 维特征和 $n$ 个样本，计算复杂度为 $O(d \times n \log n)$。

决策树容易过拟合，表现为训练集准确率高但测试集准确率低。通过绘制学习曲线可以直观观察：

训练误差随树深度增加而持续下降。
测试误差先下降后上升，表明模型开始过拟合。

import numpy as np

def find_best_split(X, y):
    best_gini = float('inf')
    best_feature, best_threshold = None, None

    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left_mask = X[:, feature] <= threshold
            gini_left = gini_impurity(y[left_mask])
            gini_right = gini_impurity(y[~left_mask])
            weighted_gini = (len(y[left_mask]) * gini_left + len(y[~left_mask]) * gini_right) / len(y)

            if weighted_gini < best_gini:
                best_gini = weighted_gini
                best_feature = feature
                best_threshold = threshold

    return best_feature, best_threshold

def prune_tree(node, X_val, y_val, alpha):
    if node.is_leaf:
        return node

    node.left = prune_tree(node.left, X_val, y_val, alpha)
    node.right = prune_tree(node.right, X_val, y_val, alpha)

    if not node.left.is_leaf or not node.right.is_leaf:
        return node

    # 计算剪枝前后的误差
    error_before = calculate_error(node, X_val, y_val)
    merged_error = calculate_error(node.as_leaf(), X_val, y_val)

    if merged_error + alpha <= error_before:
        return node.as_leaf()
    else:
        return node

对于类别不平衡数据，可以调整基尼系数计算，引入类别权重 $w_k$：

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

在分布式环境下，可以将特征分配到不同节点并行计算分裂点：