数学原理

本章目标

1. 理解决策树回归的数学本质——递归二分特征空间，每次选择使平方误差最小的特征和阈值。
2. 理解叶子节点为什么输出局部常数（区域均值）——这是平方误差最小化的自然结果。
3. 把这些数学表达和当前源码中的 max_depth、min_samples_split、min_samples_leaf 对应起来。

重点方法与概念速览

名称	类型	作用
区域划分	数学过程	将特征空间递归二分为若干矩形子区域 $R_1,R_2,\dots ,R_M$
平方误差最小化	分割准则	$\underset{j,s}{min}[\sum _{{\mathbf{x}}_i\in R_1}(y_i-{\hat{c}}_1{)}^2+\sum _{{\mathbf{x}}_i\in R_2}(y_i-{\hat{c}}_2{)}^2]$——选择最优特征 $j$ 和阈值 $s$
局部常数预测	叶子输出	$\hat{c}_m = \frac{1}{
复杂度控制	正则化	max_depth、min_samples_split、min_samples_leaf——防止树过深、区域过细

1. 区域划分的数学形式

决策树回归将特征空间划分为 $M$ 个互不相交的矩形区域 $R_1,R_2,\dots ,R_M$。预测函数为：

$$f(\mathbf{x})=\sum _{m=1}^M{\hat{c}}_m\cdot \mathbb{1}(\mathbf{x}\in R_m)$$

其中 ${\hat{c}}_m$ 是区域 $R_m$ 的预测值（常数），$\mathbb{1}(\cdot )$ 是指示函数。

对于特征 $j$ 和分割点 $s$，定义左右子区域：

$$R_1(j,s)=\{\mathbf{x}\mid x_j\le s\},R_2(j,s)=\{\mathbf{x}\mid x_j>s\}$$

划分过程是递归的——对 $R_1$ 和 $R_2$ 各自继续寻找最优 $(j,s)$ 分裂，直到满足停止条件。

理解重点

• 决策树的每一步分裂都是轴对齐（axis-aligned）的——每次只用一个特征的一个阈值切一刀。
• 这意味着决策边界总是由垂直于坐标轴的超平面组成——不能直接产生斜线分割。
• 数学上的区域划分，在工程上对应树的节点不断生成左右子节点——直到触及 max_depth 或 min_samples_split 等约束。

2. 分割准则：平方误差最小化

回归树的核心目标是最小化每个区域内的平方误差和。在第 $m$ 个节点，选择最优 $(j,s)$ 使得分裂后的总平方误差最小：

$$\underset{j,s}{min}[\sum _{{\mathbf{x}}_i\in R_1(j,s)}(y_i-{\hat{c}}_1{)}^2+\sum _{{\mathbf{x}}_i\in R_2(j,s)}(y_i-{\hat{c}}_2{)}^2]$$

其中：

$${\hat{c}}_1=\frac{1}{|R_1|}\sum _{{\mathbf{x}}_i\in R_1}{y}_i,{\hat{c}}_2=\frac{1}{|R_2|}\sum _{{\mathbf{x}}_i\in R_2}{y}_i$$

理解重点

• 回归树的分裂准则与分类树有本质区别——分类树用基尼系数或信息增益（衡量类别纯度），回归树用平方误差（衡量数值离散度）。
• 每次分裂的目标是让左右两边的目标值各自更"集中"——也就是让区域内方差尽可能小。
• 这也解释了为什么叶子节点预测值自然取区域均值——对于平方损失，均值是最优的常数预测。

3. 叶子节点预测值：局部常数

一旦样本落入某个叶子节点（区域 $R_m$），预测值固定为该区域内所有训练样本目标值的均值：

$${\hat{c}}_m=\frac{1}{|R_m|}\sum _{{\mathbf{x}}_i\in R_m}{y}_i$$

整个模型的预测函数因此呈现分段常数形态：

$$f(\mathbf{x})={\hat{c}}_{m(\mathbf{x})},m(\mathbf{x})=\text{包含 }\mathbf{x}\text{ 的叶子区域}$$

理解重点

• 决策树回归不是在拟合一条连续曲线——它在每个叶子区域输出一个常数，整体预测函数是阶梯状的。
• 与线性回归的对比：线性回归对任意 $\mathbf{x}$ 输出 ${\mathit{\beta }}^T\mathbf{x}$（全局连续函数），决策树回归输出不同区域的局部均值（分段常数）。
• 树越深、叶子越多，分段越细——模型越灵活但也越容易过拟合。

4. 训练复杂度与搜索策略

对每个特征 $j$，将其取值排序后遍历可能的分割点，整体搜索成本为：

$$O(d\cdot N\log N)$$

其中 $d$ 是特征数（当前 8），$N$ 是样本数（训练集约 16512）。

每层分裂后样本被二分，递归深度受 max_depth 限制，总复杂度约为 $O(d\cdot N\log N\cdot \text{depth})$。

理解重点

• 回归树的训练不是遍历所有可能的分裂组合——而是对每个特征单独排序、单独搜索最优阈值，再选全局最优。
• California Housing 有 20640 样本 × 8 特征——在此规模上决策树训练极快（秒级），这也是树模型的一大工程优势。
• 当前源码中同时使用 @timeit 和 timer 打印耗时——对于这个数据规模，训练耗时通常在毫秒到秒级。

5. 复杂度控制与正则化

不加约束的决策树会一直分裂到每个叶子只有 1 个样本——完美拟合训练数据但毫无泛化能力。当前源码通过三个超参数约束树的生长：

约束项	数学含义	当前取值
max_depth	树的最大深度——限制从根到叶子的最长路径长度	6
min_samples_split	节点继续分裂所需的最小样本数——若当前节点样本数小于此值，停止分裂	6
min_samples_leaf	叶子节点允许的最少样本数——分裂后任一子节点样本数少于此值则拒绝该分裂	3

此外，理论上还有代价复杂度剪枝（cost-complexity pruning）：

$$C_{\alpha }(T)=\sum _{m=1}^{|T|}{N}_m\cdot {\text{MSE}}_m+\alpha |T|$$

其中 $|T|$ 是叶子节点数，$\alpha$ 是复杂度惩罚系数。但当前源码未使用 ccp_alpha——复杂度控制完全通过上述三个超参数。

理解重点

• 三个超参数从不同角度阻止树的过度生长：max_depth 限制深度上限，min_samples_split 限制何时还能切，min_samples_leaf 限制叶子不能太小。
• 当前默认值 (6, 6, 3) 是中等保守的配置——在 California Housing 上既有足够的非线性拟合能力，又不过度分裂。
• 理论上常见的 ccp_alpha 剪枝在 scikit-learn 中可用但当前未启用——文档必须区分"理论上常见的控制方式"和"当前实现实际使用了什么"。

6. 数学原理如何映射到当前源码

数学概念	数学符号	代码实现
区域划分	$R_1(j,s),R_2(j,s)$	DecisionTreeRegressor 内部节点分裂——max_depth=6 限制层数
分割准则	$\underset{j,s}{min}\sum (y_i-\hat{c}{)}^2$	criterion="squared_error"（默认，源码未显式写出）
叶子预测值	${\hat{c}}_m=\text{mean}(y_i:{\mathbf{x}}_i\in R_m)$	model.predict(X) 返回各叶子区域均值
特征搜索	对每个 $j$ 排序后遍历 $s$	scikit-learn 内部 Cython 实现——random_state=42 保证可复现
最大深度	${\text{depth}}_{max}$	max_depth=6
最小分裂样本数	$N_{min}^{\text{split}}$	min_samples_split=6
最小叶子样本数	$N_{min}^{\text{leaf}}$	min_samples_leaf=3
叶节点数	$	T
树深度	$\text{depth}(T)$	model.get_depth()
特征重要性	${\text{imp}}_j$	model.feature_importances_

7. 决策树回归 vs 线性回归 数学对比

维度	线性回归	决策树回归
模型形式	$f(\mathbf{x})={\mathit{\beta }}^T\mathbf{x}+{\beta }_0$——全局线性函数	$f(\mathbf{x})=\sum _m{\hat{c}}_m\mathbb{1}(\mathbf{x}\in R_m)$——分段常数
目标函数	$\underset{\mathit{\beta }}{min}|\mathbf{y}-\mathbf{X}\mathit{\beta }{|}^2$——闭式解或梯度下降	$\underset{j,s}{min}\sum _{R_1,R_2}(y_i-\hat{c}{)}^2$——贪心搜索
假设	全局线性关系	无条件分布假设
特征交互	需手工构造交互项	自然通过条件分支捕获
非线性处理	需基函数展开或特征工程	天然支持——分裂即是非线性
参数数	$d+1$（系数 + 截距）	随树深度指数增长——叶子数
过拟合风险	低（参数少）	高（需显式约束深度和叶子大小）
对特征尺度敏感	是——需标准化	否——仅依赖相对排序

常见坑

1. 把回归树的分裂准则与分类树混淆——回归用平方误差（MSE），分类用基尼系数或熵。
2. 以为树越深越好——未约束的树会在训练集上完美拟合但泛化极差。
3. 把叶子预测值理解为"该区域的线性拟合"——决策树回归输出的是常数（均值），不是局部线性函数。
4. 忽略 min_samples_split 和 min_samples_leaf 的联合作用——只看 max_depth 不足以控制复杂度。

小结

• 决策树回归的数学核心链：递归二分特征空间 → 平方误差最小化选择 $(j,s)$ → 叶子输出区域均值 ${\hat{c}}_m$ → max_depth/min_samples_split/min_samples_leaf 控制复杂度。
• 与线性回归的根本区别：分段常数 vs 全局线性，无条件假设 vs 线性假设，天然处理非线性 vs 需特征工程。
• 当前源码 DecisionTreeRegressor(max_depth=6, min_samples_split=6, min_samples_leaf=3) 是展示回归树核心数学最经典的中等复杂度配置。