深入解析CART回归决策树：数学公式推导与工程实践

1次阅读

没有评论

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

当面对非线性、多模式的回归问题时，线性回归往往表现不佳。比如预测房价时，不同区域可能呈现完全不同的价格规律。CART 回归树通过递归划分特征空间，可以灵活捕捉这种局部模式。

与分类树不同，回归树的叶节点存储连续值（通常是区域样本均值），通过树结构实现分段常数拟合。这种方法特别适合处理：

存在交互作用的特征组合
非单调的变量关系
含有离群点的数据集

假设当前节点包含样本集合 $D$，我们的目标是找到特征 $j$ 的最优分割点 $s$，使得分裂后的左右子集 $D_L$ 和 $D_R$ 的平方误差最小：

$$
\min_{j,s} \left[\sum_{x_i \in D_L} (y_i – c_L)^2 + \sum_{x_i \in D_R} (y_i – c_R)^2 \right]
$$

其中 $c_L$ 和 $c_R$ 分别是左右子节点的预测值，通常取对应区域样本的均值：

$$
c_L = \frac{1}{|D_L|} \sum_{x_i \in D_L} y_i, \quad
c_R = \frac{1}{|D_R|} \sum_{x_i \in D_R} y_i
$$

对于连续特征，通常先对特征值排序，然后只考察相邻样本间的中点作为候选分割点。假设某特征有 $m$ 个不同值，则只需考察 $m-1$ 个分割点。

计算时可以维护累加和：

$$
S_L = \sum_{x_i \in D_L} y_i, \quad
S_R = S_{total} – S_L
$$

这样均值和平方误差可以快速计算：

$$
c_L = S_L / N_L, \quad
\text{MSE} = \sum y_i^2 – S_L^2/N_L – S_R^2/N_R
$$

当树停止分裂时，叶节点的最优预测值就是使该区域平方误差最小的常数。通过求导易证：

$$
\frac{\partial}{\partial c} \sum (y_i – c)^2 = 0 \implies c = \frac{1}{N} \sum y_i
$$

import numpy as np

class TreeNode:
    def __init__(self, depth=0):
        self.split_feature = None
        self.split_value = None
        self.left = None
        self.right = None
        self.prediction = None
        self.depth = depth

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

    def _find_best_split(self, X, y):
        best_mse = float('inf')
        best_feature, best_value = None, None

        for feature in range(X.shape[1]):
            # 预排序加速
            sorted_idx = np.argsort(X[:, feature])
            X_sorted, y_sorted = X[sorted_idx], y[sorted_idx]

            # 维护累加统计量
            S_total = y_sorted.sum()
            S_left, N_left = 0, 0

            for i in range(1, len(y_sorted)):
                S_left += y_sorted[i-1]
                N_left += 1

                # 跳过重复值
                if X_sorted[i-1, feature] == X_sorted[i, feature]:
                    continue

                # 计算 MSE
                S_right = S_total - S_left
                N_right = len(y_sorted) - N_left
                mse = (y_sorted**2).sum() - S_left**2/N_left - S_right**2/N_right

                if mse < best_mse:
                    best_mse = mse
                    best_feature = feature
                    best_value = (X_sorted[i-1, feature] + X_sorted[i, feature])/2

        return best_feature, best_value

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

    def _build_tree(self, X, y, depth=0):
        node = TreeNode(depth=depth)
        node.prediction = np.mean(y)

        # 终止条件
        if depth >= self.max_depth or len(y) < self.min_samples_split:
            return node

        # 寻找最优分裂
        feature, value = self._find_best_split(X, y)
        if feature is None:
            return node

        # 递归构建子树
        left_idx = X[:, feature] < value
        node.split_feature = feature
        node.split_value = value
        node.left = self._build_tree(X[left_idx], y[left_idx], depth+1)
        node.right = self._build_tree(X[~left_idx], y[~left_idx], depth+1)

        return node

对每个特征只排序一次，后续通过索引访问。对于大数据集，可以采用近似分位数方法减少候选点。