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

1次阅读

没有评论

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

传统线性回归模型假设特征和目标变量之间存在线性关系，但在实际应用中，很多数据呈现非线性特征。比如房价预测中，面积和价格的关系可能在某个临界点突然变化（如学区房阈值）。这时候，决策树的优势就显现出来了：

天然适合处理非线性关系
通过树形结构自动学习分段规则
结果具有更好的可解释性

回归树使用方差最小化作为分裂标准（分类树用基尼系数）。对于节点 m，其方差计算公式为：

$$\text{Variance}(m) = \frac{1}{N_m} \sum_{i \in m} (y_i – \bar{y}_m)^2$$

其中：
– $N_m$ 是节点 m 的样本数
– $\bar{y}_m$ 是节点 m 的样本均值

对于每个特征 j 和切分点 s，计算分裂后的方差减少量：

$$\Delta(j,s) = \text{Variance}(m) – \left(\frac{N_l}{N_m}\text{Variance}(l) + \frac{N_r}{N_m}\text{Variance}(r) \right)$$

选择使 $\Delta(j,s)$ 最大的 (j,s) 组合进行分裂。

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 compute_variance(y):
    """计算节点的方差"""
    if len(y) == 0:
        return 0
    return np.var(y)

def find_best_split(X, y):
    """寻找最优特征和切分点"""
    best_gain = -1
    best_feature, best_thresh = None, None

    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for thresh in thresholds:
            # 按阈值划分左右节点
            left_idx = X[:, feature_idx] <= thresh
            right_idx = X[:, feature_idx] > thresh

            # 计算方差减少量
            gain = compute_variance(y) - \
                  (left_idx.mean()*compute_variance(y[left_idx]) + \
                   right_idx.mean()*compute_variance(y[right_idx]))

            if gain > best_gain:
                best_gain = gain
                best_feature = feature_idx
                best_thresh = thresh

    return best_feature, best_thresh