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

1次阅读

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

决策树在回归问题中扮演着重要角色，它通过树形结构对数据进行分割，最终在每个叶节点上给出预测值。CART（Classification and Regression Trees）算法因其简单高效而广受欢迎。相比于其他回归方法，CART 具有以下优势：

可解释性强，决策过程直观
能够自动处理特征间的交互作用
不需要对数据进行复杂的预处理
适用于各种类型的数据（数值型和类别型）

CART 回归树的核心是最小化平方误差。对于给定的数据集 D，其平方误差损失函数定义为：

$$
L(D) = \sum_{i=1}^n (y_i – \bar{y})^2
$$

其中 $\bar{y}$ 是该节点上所有样本的均值，即预测值。

在选择分裂特征时，CART 使用方差减少量作为标准。对于候选分割点 s 将数据集 D 分为 $D_1$ 和 $D_2$，方差减少量为：

$$
\Delta L(s,D) = L(D) – [L(D_1) + L(D_2)]
$$

我们选择使 $\Delta L(s,D)$ 最大的特征和分割点进行分裂。

对于一个连续特征 j 和分割点 s，定义分裂后的两个区域：

$$
R_1(j,s) = {x|x_j \leq s} \
R_2(j,s) = {x|x_j > s}
$$

最优的分割点 $s^*$ 满足：

$$
(j^, s^) = \arg\min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i – c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i – c_2)^2]
$$

其中 $c_1$ 和 $c_2$ 分别是两个区域的均值。

下面是一个简化的 CART 回归树实现：

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 _calculate_mse(self, y):
        if len(y) == 0:
            return 0
        mean = np.mean(y)
        return np.sum((y - mean) ** 2)

    def _find_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_indices = X[:, feature] <= threshold
                right_indices = ~left_indices

                mse_left = self._calculate_mse(y[left_indices])
                mse_right = self._calculate_mse(y[right_indices])
                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 depth == self.max_depth or len(y) < self.min_samples_split:
            return Node(value=np.mean(y))

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

        left_indices = X[:, feature] <= threshold
        right_indices = ~left_indices

        left = self._build_tree(X[left_indices], y[left_indices], depth + 1)
        right = self._build_tree(X[right_indices], y[right_indices], 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_sample(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._predict_sample(x, node.left)
        else:
            return self._predict_sample(x, node.right)

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

算法通过递归方式构建树结构，关键步骤包括：

计算当前节点的 MSE
寻找最佳分裂特征和阈值
递归构建左子树和右子树
当达到停止条件时创建叶节点

预剪枝 ：在树构建过程中提前停止
优点：计算效率高
缺点：可能错过重要分裂
后剪枝 ：先构建完整树再剪枝
优点：保留更多信息
缺点：计算成本高

max_depth：控制树的最大深度，防止过拟合
min_samples_split：节点继续分裂的最小样本数
min_samples_leaf：叶节点的最小样本数

确保正确排序特征值
考虑所有可能的分割点
避免因数值精度问题导致的分割错误

使用交叉验证选择最优参数
引入正则化项
采用集成方法如随机森林

训练阶段：$O(n \cdot m \cdot d \cdot \log n)$
n: 样本数
m: 特征数
d: 树深度
预测阶段：$O(d)$

方法	优点	缺点
CART 回归	非线性关系建模能力强	容易过拟合
线性回归	简单高效	只能建模线性关系
支持向量回归	适用于高维数据	参数调优复杂