从数学原理到代码实现：深入解析CART回归决策树算法推导

1次阅读

没有评论

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

当数据存在非线性关系时，线性回归的表现往往不尽如人意。比如预测房屋价格时，房间数量和面积的关系可能是阶梯状的——只有达到某个面积阈值时，增加房间数量才会显著提升价格。这时候决策树的优势就显现出来了：

自动捕捉变量间的交互作用
无需手动构造多项式特征
输出结果直观可解释

回归树使用方差取代分类树中的基尼系数。对于节点 $t$，其方差计算公式为：

$$
\text{Var}(t) = \frac{1}{N_t}\sum_{i\in t}(y_i – \bar{y}_t)^2
$$

其中 $\bar{y}_t$ 是节点 $t$ 内所有样本的均值。分裂目标是找到使加权方差和最小的特征和切分点：

$$
\arg\min_{f,s}\left[\frac{N_L}{N}\text{Var}(t_L) + \frac{N_R}{N}\text{Var}(t_R)\right]
$$

假设我们有以下房价数据：

面积(m²)	房间数	价格(万)
80	2	320
95	3	420
120	3	480
150	4	620

对于 ” 面积 ” 特征：

排序后候选切分点为 87.5, 107.5, 135
计算每个切分点的加权方差
选择使方差下降最大的切分点

import numpy as np

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 calculate_variance(y):
    """计算节点方差"""
    return np.var(y) * len(y)

def find_best_split(X, y):
    """寻找最优分裂特征和阈值"""
    best_var_reduction = -np.inf
    best_feature, best_threshold = None, 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

            # 计算方差减少量
            var_reduction = calculate_variance(y) - \
                           (calculate_variance(y[left_mask]) + \
                            calculate_variance(y[right_mask]))

            if var_reduction > best_var_reduction:
                best_var_reduction = var_reduction
                best_feature = feature_idx
                best_threshold = threshold

    return best_feature, best_threshold

连续值处理：
建议先做标准化处理（如 Z -score）
分裂点选择相邻值的平均值
过拟合预防：
预剪枝：设置最大深度、最小样本数
后剪枝：CCP 代价复杂度剪枝
缺失值应对：
将缺失值单独作为一类
或按照非缺失样本的比例分配
特征重要性：
通过方差减少量评估
注意高基数特征的偏差
多输出支持：
修改方差计算为多变量情况
每个叶节点存储向量值
可视化工具有效性：
当特征 >5 个时建议用特征重要性
局部可视化可用 dtreeviz 库

训练：$O(n_{\text{features}} \times n_{\text{samples}} \times \log n_{\text{samples}})$
预测：$O(\text{树深度})$

实现维度	本文实现	sklearn 优化
分裂点搜索	穷举法	分箱 + 采样
并行化	单线程	特征并行
类别特征	需独热编码	原生支持

只需两步即可升级为随机森林：

数据层面：对训练集做 Bootstrap 抽样
特征层面：每个节点随机选择特征子集

from sklearn.ensemble import RandomForestRegressor
rf = RandomForestRegressor(
    n_estimators=100,
    max_features='sqrt',  # 推荐设置
    min_samples_leaf=5    # 防止过拟合
)