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

1次阅读

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

决策树是机器学习中最直观的算法之一，它通过一系列规则对数据进行分类或回归。CART（Classification and Regression Trees）是其中最经典的算法，由 Breiman 等人于 1984 年提出。与 ID3 和 C4.5 不同，CART 可以同时处理分类和回归问题，并且总是生成二叉树。

决策树的核心在于如何选择最优划分特征，CART 使用基尼系数（Gini Index）作为划分标准：

$$\text{Gini}(D) = 1 – \sum_{k=1}^{K} (\frac{|C_k|}{|D|})^2$$

其中 $D$ 是当前数据集，$C_k$ 是第 $k$ 类的样本子集。基尼系数反映了从数据集中随机抽取两个样本，其类别不一致的概率。与信息熵相比：

基尼系数计算更快（无对数运算）
两者在实际效果上非常接近
ID3/C4.5 只能用于分类任务，而 CART 可用于回归（使用平方误差）

function find_best_split(data):
    best_gini = ∞
    best_feature = None
    best_value = None

    for feature in features:
        if feature is continuous:
            values = get_sorted_unique_values(data[feature])
            for i in range(len(values)-1):
                threshold = (values[i] + values[i+1])/2
                left, right = split_data(data, feature, threshold)
                current_gini = weighted_gini(left, right)
                if current_gini < best_gini:
                    update_best_parameters()
        else:
            # 处理离散特征类似

    return best_feature, best_value

import numpy as np

def calc_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 = None
    best_threshold = 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
            right_mask = ~left_mask

            if len(y[left_mask]) == 0 or len(y[right_mask]) == 0:
                continue

            gini_left = calc_gini(y[left_mask])
            gini_right = calc_gini(y[right_mask])

            weighted_gini = (len(y[left_mask]) * gini_left + 
                            len(y[right_mask]) * gini_right) / len(y)

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

    return best_feature, best_threshold

对于连续特征，CART 采用二分法：

对特征值排序
取相邻值的中间点作为候选切分点
选择使基尼系数最小的切分点

这种方法比多分法效率更高，且在实践中效果良好。

过拟合是决策树的主要问题，解决方法包括：

预剪枝 ：在构建过程中提前停止
最大深度限制
最小样本分割数
基尼系数提升阈值
后剪枝 ：先构建完整树再修剪
代价复杂度剪枝（CCP）
$$\alpha = \frac{R(t) – R(T_t)}{|T_t| – 1}$$
其中 $R(t)$ 是节点 $t$ 的误差，$T_t$ 是以 $t$ 为根的子树

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 build_tree(X, y, max_depth=5, min_samples_split=2):
    # 终止条件
    if len(y) < min_samples_split or max_depth == 0 or len(np.unique(y)) == 1:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂
    feature_idx, threshold = find_best_split(X, y)
    if feature_idx is None:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 递归构建子树
    left_mask = X[:, feature_idx] <= threshold
    right_mask = ~left_mask

    left = build_tree(X[left_mask], y[left_mask], max_depth-1, min_samples_split)
    right = build_tree(X[right_mask], y[right_mask], max_depth-1, min_samples_split)

    return TreeNode(feature_idx=feature_idx, threshold=threshold, left=left, right=right)

def predict(node, x):
    if node.value is not None:
        return node.value

    if x[node.feature_idx] <= node.threshold:
        return predict(node.left, x)
    else:
        return predict(node.right, x)

通过计算每个特征在分裂时的基尼系数下降总量来评估重要性：

def feature_importance(tree, X, y):
    importance = np.zeros(X.shape[1])

    def traverse(node):
        if node.feature_idx is not None:
            left_mask = X[:, node.feature_idx] <= node.threshold
            gini_parent = calc_gini(y)
            gini_left = calc_gini(y[left_mask])
            gini_right = calc_gini(y[~left_mask])

            improvement = gini_parent - (len(y[left_mask])/len(y) * gini_left +
                len(y[~left_mask])/len(y) * gini_right
            )

            importance[node.feature_idx] += improvement

            traverse(node.left)
            traverse(node.right)

    traverse(tree)
    return importance / np.sum(importance)