树方法将特征空间分割为不同区域，然后用一个简单的模型（比如常数）来拟合每个区域。
考虑一个简单的回归问题。特征是二维的 和
，响应是实数
。这个问题我们可以用决策树来解决。
左上角的图是一种复杂的情形，无法进行二叉树分割。我们只研究类似于右上角的图的简单情形。
如何生成一个回归树
假设我们的特征有 维，共有
个观测样本。如果分支数太多，显然会存在过拟合的问题。但是分支数太少又可能忽略掉重要的结构。我们需要一个算法来自主决定根据哪个变量、在哪个值分支。
可调参数：
- 每个叶子节点最大样本数（用于 Step 1 终止条件）
Step1. 递归构造二叉树
Step 1.1 切分
假设我们对第 个特征选择了分割点
，则分割成的两个部分为：
我们的目标是选择 和
让两个部分的残差平方和 (RSS) 最小，即求解如下问题：
其中预测值的估计 为各部分
的均值。
假设 在样本中一共有 k 个不同的值，则显然最多有 k-1 种分法。可以依次尝试找到
。但是这对
组合并不一定是最优的，还需要对其他特征做同样的操作选取全局最优的
组合。
Step1.2 判断终止条件
完成 step 1.1 的切分之后，对每个部分判断是否停止切分。判断条件很简单，在这个部分的样本数是否低于某个给定的值，例如 5。如果低于则停止，否则重复 step 1.1 递归地进行切分。
Step2. 剪枝
通过 step 1 我们获得了一个非常大的二叉树。它的每个叶子节点都有不超过 5 个样本。显然这样的树是过拟合的，我们需要进行剪枝。
剪枝的目的是在总节点数以及每个节点的样本的 RSS 中取一个较好的平衡。因此我们定义“复杂度成本” (cost-complexity)：
其中：
：剪枝后的树 T 的节点数
：第 m 个节点的残差平方和
：节点个数权重，即复杂度成本
显然，对每个 的取值，我们都有一个唯一确定的树
使
最小。
Step 2.1 交叉检验法确定 
我们可以通过调节 来决定剪枝后的模型复杂度（节点数）。
越大，模型越简单，越不精确。
太小则会造成过拟合。
为了确定合适的 我们可以把数据的 1/5 或者 1/10 留作检验数据，剩余数据作为训练数据。然后寻找使检验数据的预测误差最小的
。
Step 2.2 最弱连接法剪枝
我们可以从 RSS 最小的节点开始依次合并分支，直到只剩一个节点。对该过程中的每个树计算 ，最小的就是最终结果
。
