回归树

回归树是一种解决回归问题的树形模型，用到是之前介绍过的 CART 树（Classification And Regression Trees）。CART 树是二叉树，在回归问题中主要用到平方误差最小化作为代价函数，来对回归树进行更新迭代。

假设有训练集 $D = {(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\dots,(x^{(m)},y^{(m)})}$，$x^{(i)} \in \mathbb R^n$，下面就根据数据集来生成一颗 CART 回归树。

首先要寻找第一个特征 $x_j$，将数据集根据 $x_j$，以及划分条件 $x_j\leq s$ 或 $x_j> s$，并且将根节点一分为二形成两个子节点，如下图

可是就算我们找到了 $x_j$ 与 $s$，那还需要确定 $c_1$ 与 $c_2$。当我们搜集出训练集中所有的 $x_j\leq s$ 的样本，我们就会发现，令 ${c_1} = \text{ave} { y^{(i)}|x^{(i)}_j \leq s }$ 是一个很合理的选择。

确定了 $c_1$ 与 $c_2$，就可以根据最小化平方误差来评价切分变量 $x_j$ 与切分点 $s$ 的选择是否为最优选择，就会有如下的代价函数最优化问题：

$$\min_{j,s} \left[ \sum_{\{i|x_j^{(i)} \leq s \}}(y^{(i)}-c_1)^2 + \sum_{\{i|x_j^{(i)} > s \}}(y^{(i)}-c_2)^2 \right]$$

遍历所有的特征和每个特征的切分点便可以找到最佳划分方案，那么这个回归树桩就成功生成啦！

对于一颗完整的树，比如下面这个之前用过的图：

通过三次决策判断将训练集划分成为了四份，用 $R_1,R_2,R_3,R_4$ 来表示这四个划分好的集合。同样的，一颗回归树可以将空间划分为 $K$ 个单元 $R_1,R_2,\cdots,R_K$，在每个单元都有一个固定的输出值 $c_k$，于是回归树模型可以表示为：

$$f(x) = \sum_{k=1}^K c_kI(x\in R_k)$$

选择第 $j$ 个变量 $x^{(j)}$ 和他的取值 $s$，定义的两个区域为：

$$R_1(j,s)=\{ x|x^{(j)} \leq s\}\qquad R_2(j,s)=\{ x|x^{(j)} > s\}$$

寻找最优切分点的代价公式为：

$$\min_{j,s} \left[ \min_{c_1} \sum_{x_j^{(i)} \in R_1(j,s)}(y^{(i)}-c_1)^2 + \min_{c_2}\sum_{x_j^{(i)} \in R_2(j,s)}(y^{(i)}-c_2)^2 \right]$$

对固定的 $j$ 与 $s$，可以求得

$$\hat{c_1} = \text{ave} \{ y^{(i)}|x^{(i)}\in R_1(j,s) \}\qquad \hat{c_2} = \text{ave} \{ y^{(i)}|x^{(i)}\in R_2(j,s) \}$$

遍历所有输入变量，找到最优的切分变量 $j$ ，够成一个对 $(j,s)$。依此将空间划分为两个区域。不断重复上述划分过程，直到满足条件为止。这样的回归树通常称为最小二乘回归树（least squares regression tree）。