深入解析CART回归决策树：数学公式与算法推导全解

1次阅读

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

决策树是机器学习中常用的模型，既可以用于分类也可以用于回归。在回归问题中，CART（Classification and Regression Trees）算法因其简单高效而广受欢迎。CART 回归树通过递归地将特征空间划分为多个子空间，并在每个子空间内用常数（通常是均值）进行预测。相比于线性回归，CART 回归树能够更好地捕捉非线性关系，且对异常值不敏感。

CART 回归树的目标是最小化平方误差（MSE）。对于给定的数据集 $D$，假设我们将其划分为 $M$ 个区域 $R_1, R_2, …, R_M$，每个区域的预测值为 $c_m$（通常为该区域内样本的均值），则损失函数为：
$$
\sum_{m=1}^M \sum_{x_i \in R_m} (y_i – c_m)^2
$$

在选择最佳分裂特征和分裂点时，CART 回归树会计算每个可能分裂的方差减少量。对于特征 $j$ 和分裂点 $s$，定义两个区域：
$$
R_1(j, s) = {x | x_j \leq s}, \quad R_2(j, s) = {x | x_j > s}
$$
分裂后的方差减少量为：
$$
\Delta = \sum_{x_i \in R_1} (y_i – \hat{c}1)^2 + \sum_2)^2
$$
其中 $\hat{c}_1$ 和 $\hat{c}_2$ 分别是 $R_1$ 和 $R_2$ 的均值。} (y_i – \hat{c

通过遍历所有特征和可能的分裂点，选择使 $\Delta$ 最小的 $(j, s)$ 对作为最优分裂。由于平方误差函数是凸函数，这种贪心算法能够保证局部最优。

import numpy as np

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        self.threshold = threshold  # 分裂阈值
        self.left = left  # 左子树
        self.right = right  # 右子树
        self.value = value  # 叶节点值

class CARTRegressor:
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None

    def _mse(self, y):
        if len(y) == 0:
            return 0
        return np.mean((y - np.mean(y)) ** 2)

    def _best_split(self, X, y):
        best_mse = 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
                right_mask = ~left_mask

                if np.sum(left_mask) < self.min_samples_split or np.sum(right_mask) < self.min_samples_split:
                    continue

                mse_left = self._mse(y[left_mask])
                mse_right = self._mse(y[right_mask])
                total_mse = mse_left + mse_right

                if total_mse < best_mse:
                    best_mse = total_mse
                    best_feature = feature
                    best_threshold = threshold

        return best_feature, best_threshold

    def _build_tree(self, X, y, depth=0):
        if (self.max_depth is not None and depth >= self.max_depth) or len(y) < self.min_samples_split:
            return Node(value=np.mean(y))

        feature, threshold = self._best_split(X, y)
        if feature is None:
            return Node(value=np.mean(y))

        left_mask = X[:, feature] <= threshold
        right_mask = ~left_mask

        left = self._build_tree(X[left_mask], y[left_mask], depth + 1)
        right = self._build_tree(X[right_mask], y[right_mask], depth + 1)

        return Node(feature=feature, threshold=threshold, left=left, right=right)

    def fit(self, X, y):
        self.tree = self._build_tree(X, y)

    def predict(self, X):
        return np.array([self._predict_one(x, self.tree) for x in X])

    def _predict_one(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._predict_one(x, node.left)
        else:
            return self._predict_one(x, node.right)

代码中 _build_tree 方法实现了递归构建树结构的过程：
1. 检查终止条件（达到最大深度或样本数不足）
2. 寻找最佳分裂特征和阈值
3. 递归构建左右子树