CART简介
本文主要讲回归树和最小二乘回归树的算法，目的是对决策树做回归有一个认识，并且熟悉经典的最小二乘回归树。我们这里只关注CART的回归树， CART(classification and regressioin tree)是在给定输入随机变量\(X\)条件下输出 随机变量\(Y\)的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”。其中的回归决策树等价于递归地二分每个特征，将输入空间即特征空间切分为有限个单元，并在这些单元上确定预测的回归值。当切分完毕，这些单元就是回归树上的叶子节点，这些单元上的预测值，就是叶子节点的取值。
怎么做
从上述简介可以看出生成一个回归树大致需要两部，第一步，切分特征空间为有限个单元；第二步，在每个切分后的单元上确定代表该单元的回归值。下面先讲如何确定单元取值，再讲如何切分特征空间。
确定单元取值
假设\(X\)与\(Y\)分别为输入和输出变量，并且\(Y\)是连续变量，给定训练数据集： \[D=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}\] 其中\(x \in R^d\)，一个回归树对应着输入空间（即特征空间）的一个切分和在切分后的单元上的输出值。我们这里假设输入空间已经被切分为\(M\)个单元\(R_1,R_2,\dots,R_M\)，并且每个单元有一个固定的输出值\(c_m\)，那么回归树的模型就可以写成： \[f(x)=\sum_{m=1}^Mc_mI(x \in R_m) \tag{1}\] 那么如何确定每个\(R_m\)上的取值呢？我们这里的最小二乘回归树用平方误差来表示回归树的单元取值与真实值的误差，即： \[\mathcal{L}=\sum_{x_i \in R_m}(y_i-f(x_i))^2 \tag{2}\] 根据最小二乘法，可以很容易知道单元\(R_m\)上的\(c_m\)的最优值\(\hat{c}_m\)是\(R_m\)的所有样本的输出\(y_i\)的均值，即： \[\hat{c}_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i \tag{3}\] 其中\(N_m\)为落在切分空间\(R_m\)的所有样本数目，\(R_m(j,s)\)意思是切分变量\(x^{(j)}\)(即输入变量的第\(j\)维特征)和对应的切分点\(s\)对应的切后单元空间。到这里就解决了问题：假设切分空间确定后，每个空间所代表的值。
切分特征空间
那么回归树的问题就剩余如何确定输入空间的切分。事实上只要找到切分变量\(x^{(j)}\)(即输入变量的第\(j\)维特征)和对应的切分点\(s\)，然后再针对切分后的子空间递归进行切分直到满足建树停止条件即可。
这里定义切分后的两个区域为\(R_1\)和\(R_2\)，有： \[R_1(j,s)=\{x|x^{(j)}\leq s\}\] \[R_2(j,s)=\{x|x^{(j)}> s\}\] 然后求解如下式寻找最优切分变量\(j\)和最优切分点\(s\)： \[min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2] \tag{4}\] 解释一下(4)式，即选取输入变量\(x\)的第\(j\)维，并扫描切分点\(s\)，当切分的两个子单元的方差之和最小，则为第\(j\)维的最优切分点。遍历所有找到符合(4)式的\(j,s\)，切分为两个子单元，再对子单元按(4)式进行递归切分直到满足停止条件即可。
这里找切分点的方法思想本质还是最小二乘法，与图像二值化当中的Otsu算法有点神似。
参考文献
《统计学习方法》李航 5.5.1
