树方法将特征空间分割为不同区域，然后用一个简单的模型（比如常数）来拟合每个区域。

考虑一个简单的回归问题。特征是二维的 和 ，响应是实数 。这个问题我们可以用决策树来解决。

左上角的图是一种复杂的情形，无法进行二叉树分割。我们只研究类似于右上角的图的简单情形。

利用树分割特征空间

如何生成一个回归树

假设我们的特征有 维，共有 个观测样本。如果分支数太多，显然会存在过拟合的问题。但是分支数太少又可能忽略掉重要的结构。我们需要一个算法来自主决定根据哪个变量、在哪个值分支。

可调参数：

• 每个叶子节点最大样本数（用于 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 最小的节点开始依次合并分支，直到只剩一个节点。对该过程中的每个树计算 ，最小的就是最终结果 。

参考

1. 使用 LightGBM 前剪枝过程