CART之回归树构建

问题提出

在看李航的《统计学习方法》的决策树那一章节,提到了CART算法,讲解了如何分别构建分类树和回归树,文章的侧重点好像在分类树上,对回归树只是提了一下,让我很是不解,于是google了下,大家基本上都在讲怎么构建CART分类树,好像回归树不存在似得,所以根据我手头现有的资料和查找到的文献,为大家以一个例子的方式讲解如何生存CART回归树。

概念

先来回顾下关于CART回归树概念性的东西吧。

首先要强调的是CART假设决策树是二叉树,内部结点特征的取值只有“是”和“否”,左分支是取值为“是”的分支,有分支则相反。这样的决策树等价于递归地二分每个特征。

CART生成

决策树的生成就是递归地构建二叉决策树的过程,对回归树用平方误差最小化准则,对分类树用基尼指数最小化准则,进行特征选择,生成二叉树

回归树的生成

最小二叉回归树生成算法

输入:训练数据集D;
输出:回归树f(x)

算法:

在训练数据集所在的输入空间中,递归地将每个区域划分为两个子区域并决定每个子区域上输出值,构建二叉决策树:

  1. 择最优切分变量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]\]遍历变量\(j\),对固定的切分变量\(j\)扫描切分点\(s\),选择使上式最小值的对\((j, s)\)。其中\(R_m\)是被划分的输入空间,\(c_m\)是空间\(R_m\)对应的固定输出值。
  2. 用选定的对\((j, s)\)划分区域并决定相应的输出值:\[R_1(j.s)=\lbrace x\mid x^{(j)} \le s \rbrace , \quad R_2(j,s)=\lbrace x\mid x^{(j)}\gt s \\ \hat c_m = {1\over N_m}\sum_{x_i\in R_m(j,s)}y_i , \quad x\in R_m , m=1,2\]
  3. 继续对两个子区域调用步骤(1),(2),直至满足停止条件。
  4. 将输入空间划分为M个区域\(R_1,R_2,\ldots,R_M\),生成决策树:\[f(x) = \sum_{m=1}^M\hat c_m I(x\in R)\]

示例

上面的东西有点难以理解,下面举个例子来说明。

训练数据见下表,\(x\)的取值范围为区间\([0.5,10.5]\),\(y\)的取值范围为区间\([5.0,10.0]\),学习这个回归问题的最小二叉回归树。

\(x_i\) 1 2 3 4 5 6 7 8 9 10
\(y_i\) 5.56 5.70 5.91 6.40 6.80 7.05 8.90 8.70 9.00 9.05

首先来看这个优化问题

\[\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]\] 求解训练数据的切分点\(s\): \[R_1=\lbrace x\mid x\le s\rbrace , \quad R_2=\lbrace x\mid x\gt s\rbrace \] 容易求得在\(R_1\),\(R_2\)内部使得平方损失误差达到最小值的\(c_1\),\(c_2\)为: \[c_1={1\over N_1}\sum_{x_i \in R_1}y_i , \quad c_2={1\over N_2}\sum_{x_i \in R_2}y_i\] 这里\(N_1\),\(N_2\)\(R_1\),\(R_2\)的样本点数。

求训练数据的切分点,根据所给数据,考虑如下切分点: \[1.5 ,2.5 ,3.5 ,4.5 ,5.5 , 6.5 , 7.5 , 8.5 , 9.5\] 对各切分点,不难求出相应的\(R_1\) , \(R_2\) , \(c_1\) , \(c_2\)\[m(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]\] 例如,当\(s=1.5\)时,\(R_1 = \lbrace 1\rbrace\) , \(R_2 = \lbrace 2, 3 , \ldots , 10\rbrace\) , \(c_1 = 5.56\) , \(c_2 = 7.50\) , \[m(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] = 0+15.72 = 15.72\] 现将\(s\)\(m(s)\)的计算结果列表如下:

\(s\) 1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5
\(m(s)\) 15.72 12.07 8.36 5.78 3.91 1.93 8.01 11.73 15.74

由上表可知,当\(x=6.5\)的时候达到最小值,此时\(R_1 = \lbrace 1 ,2 , \ldots , 6\rbrace\) , \(R_2 ={7 ,8 ,9 , 10}\) , \(c_1 = 6.24\) , \(c_2 = 8.9\) , 所以回归树\(T_1(x)\)为: \[ T_1(x) = \begin{cases} 6.24, & x\lt 6.5 \\ 8.91, & x \ge 6.5 \\ \end{cases} \]

\[ f_1(x) = T_1(x) \]\(f_1(x)\)拟合训练数据的残差见下表,表中\(r_{2i} = y_i - f_1(x_i),i=1,2,\ldots , 10\)

\(x_i\) 1 2 3 4 5 6 7 8 9 10
\(y_i\) -0.68 -0.54 -0.33 0.16 0.56 0.81 -0.01 -0.21 0.09 0.14

\(f_1(x)\)拟合训练数据的平方误差: \[ L(y,f_1(x)) = \sum_{i=1}^{10}(y_i-f_1(x_i))^2 = 1.93 \] 第2步求\(T_2(x)\).方法与求\(T_1(x)\)一样,只是拟合的数据是上表的残差,可以得到: \[ T_2(x) = \begin{cases} -0.52, & x\lt 3.5 \\ 0.22, & x \ge 3.5 \\ \end{cases} \]

\[ f_2(x) = f_1(x) + T_2(x)= \begin{cases} 5.72, & x\lt 3.5 \\ 6.46, & 3.5\le x \lt 6.5 \\ 9.13, & x\ge 6.5 \\ \end{cases} \]\(f_2(x)\)拟合训练数据的平方误差是: \[ L(y,f_2(x)) = \sum_{i=1}^{10}(y_i-f_2(x_i))^2 = 0.79 \] 继续求得 \[ T_3(x) = \begin{cases} 0.15, & x\lt 6.5 \\ -0.22, & x \ge 6.5 \\ \end{cases} \quad L(y,f_3(x)) = 0.47 , \]

\[ T_4(x) = \begin{cases} -0.16, & x\lt 4.5 \\ 0.11, & x \ge 4.5 \\ \end{cases} \quad L(y,f_3(x)) = 0.30 , \]

\[ T_5(x) = \begin{cases} 0.07, & x\lt 6.5 \\ -0.11, & x \ge 6.5 \\ \end{cases} \quad L(y,f_3(x)) = 0.23 , \]

\[ T_6(x) = \begin{cases} -0.15, & x\lt 2.5 \\ 0.04, & x \ge 2.5 \\ \end{cases} \]

\[ f_6(x) = f_5(x)+T_6(x) =T_1(x)+ \ldots + T_5(x) + T_6(x)= \begin{cases} 5.63, & x\lt 2.5 \\ 5.82, & 2.5 \le x\lt 3.5 \\ 6.56, & 3.5 \le x\lt 4.5 \\ 6.83, & 4.5 \le x\lt 6.5 \\ 8.95, & x\ge 6.5 \\ \end{cases} \]\(f_6(x)\)拟合训练数据的平方损失误差是 \[ L(y,f_6(x)) = \sum_{i=1}^{10}(y_i-f_6(x_i))^2 = 0.71 \] 假设此时已经满足误差要求,那么\(f(x) = f_6(x)\)即为所求的回归树。

热评文章