当前位置: 首页 > >

CART之回归树构建

发布时间:

转自:https://cethik.vip/2016/09/21/machineCAST/




问题提出

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


概念

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


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


CART生成

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



回归树的生成
最小二叉回归树生成算法

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


算法:


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


    择最优切分变量j切分点s,求解



    minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]
    minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]
    遍历变量

    j
    j,对固定的切分变量

    j
    j扫描切分点

    s
    s,选择使上式最小值的对

    (j,s)
    (j,s)。其中

    Rm
    Rm是被划分的输入空间,

    cm
    cm是空间

    Rm
    Rm对应的固定输出值。用选定的对

    (j,s)
    (j,s)划分区域并决定相应的输出值:



    R1(j.s)={x?x(j)≤s},R2(j,s)={x?x(j)>sc^m=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2
    R1(j.s)={x?x(j)≤s},R2(j,s)={x?x(j)>sc^m=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2
    继续对两个子区域调用步骤(1),(2),直至满足停止条件。将输入空间划分为M个区域

    R1,R2,…,RM
    R1,R2,…,RM,生成决策树:



    f(x)=∑m=1Mc^mI(x∈R)
    f(x)=∑m=1Mc^mI(x∈R)

示例

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


训练数据见下表,

x
x的取值范围为区间

[0.5,10.5]
[0.5,10.5],

y
y的取值范围为区间

[5.0,10.0]
[5.0,10.0],学*这个回归问题的最小二叉回归树。




xi
xi
1 2 3 4 5 6 7 8 9 10


yi
yi
5.56 5.70 5.91 6.40 6.80 7.05 8.90 8.70 9.00 9.05

首先来看这个优化问题





minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]
minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]
求解训练数据的切分点


s
s:




R1={x?x≤s},R2={x?x>s}
R1={x?x≤s},R2={x?x>s}
容易求得在


R1
R1,


R2
R2内部使得*方损失误差达到最小值的


c1
c1,


c2
c2为:




c1=1N1∑xi∈R1yi,c2=1N2∑xi∈R2yi
c1=1N1∑xi∈R1yi,c2=1N2∑xi∈R2yi
这里


N1
N1,


N2
N2是


R1
R1,


R2
R2的样本点数。

求训练数据的切分点,根据所给数据,考虑如下切分点:





1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5
1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5
对各切分点,不难求出相应的


R1
R1
?,
?


R2
R2
?,
?


c1
c1
?,
?


c2
c2及




m(s)=minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]
m(s)=minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]
例如,当


s=1.5
s=1.5时,


R1={1}
R1={1}
?,
?


R2={2,3,…,10}
R2={2,3,…,10}
?,
?


c1=5.56
c1=5.56
?,
?


c2=7.50
c2=7.50
?,




m(s)=minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]=0+15.72=15.72
m(s)=minj,s[minc1∑xi∈R1(j,s)(yi?c1)2+minc2∑xi∈R2(j,s)(yi?c2)2]=0+15.72=15.72
现将


s
s及


m(s)
m(s)的计算结果列表如下:


s
s
1.5 2.5 3.5 4.5 5.5 6.5 7.5 8.5 9.5


m(s)
m(s)
15.72 12.07 8.36 5.78 3.91 1.93 8.01 11.73 15.74

由上表可知,当

x=6.5
x=6.5的时候达到最小值,此时

R1={1,2,…,6}
R1={1,2,…,6}?,?

R2=7,8,9,10
R2=7,8,9,10?,?

c1=6.24
c1=6.24?,?

c2=8.9
c2=8.9?, 所以回归树

T1(x)
T1(x)为:





T1(x)={6.24,8.91,x<6.5x≥6.5
T1(x)={6.24,x<6.58.91,x≥6.5





f1(x)=T1(x)
f1(x)=T1(x)



f1(x)
f1(x)拟合训练数据的残差见下表,表中


r2i=yi?f1(xi),i=1,2,…,10
r2i=yi?f1(xi),i=1,2,…,10


xi
xi
1 2 3 4 5 6 7 8 9 10


yi
yi
-0.68 -0.54 -0.33 0.16 0.56 0.81 -0.01 -0.21 0.09 0.14



f1(x)
f1(x)拟合训练数据的*方误差:





L(y,f1(x))=∑i=110(yi?f1(xi))2=1.93
L(y,f1(x))=∑i=110(yi?f1(xi))2=1.93
第2步求


T2(x)
T2(x).方法与求


T1(x)
T1(x)一样,只是拟合的数据是上表的残差,可以得到:




T2(x)={?0.52,0.22,x<3.5x≥3.5
T2(x)={?0.52,x<3.50.22,x≥3.5





f2(x)=f1(x)+T2(x)=???5.72,6.46,9.13,x<3.53.5≤x<6.5x≥6.5
f2(x)=f1(x)+T2(x)={5.72,x<3.56.46,3.5≤x<6.59.13,x≥6.5



f2(x)
f2(x)拟合训练数据的*方误差是:




L(y,f2(x))=∑i=110(yi?f2(xi))2=0.79
L(y,f2(x))=∑i=110(yi?f2(xi))2=0.79
继续求得




T3(x)={0.15,?0.22,x<6.5x≥6.5L(y,f3(x))=0.47,
T3(x)={0.15,x<6.5?0.22,x≥6.5L(y,f3(x))=0.47,





T4(x)={?0.16,0.11,x<4.5x≥4.5L(y,f3(x))=0.30,
T4(x)={?0.16,x<4.50.11,x≥4.5L(y,f3(x))=0.30,





T5(x)={0.07,?0.11,x<6.5x≥6.5L(y,f3(x))=0.23,
T5(x)={0.07,x<6.5?0.11,x≥6.5L(y,f3(x))=0.23,





T6(x)={?0.15,0.04,x<2.5x≥2.5
T6(x)={?0.15,x<2.50.04,x≥2.5





f6(x)=f5(x)+T6(x)=T1(x)+…+T5(x)+T6(x)=?????????????5.63,5.82,6.56,6.83,8.95,x<2.52.5≤x<3.53.5≤x<4.54.5≤x<6.5x≥6.5
f6(x)=f5(x)+T6(x)=T1(x)+…+T5(x)+T6(x)={5.63,x<2.55.82,2.5≤x<3.56.56,3.5≤x<4.56.83,4.5≤x<6.58.95,x≥6.5



f6(x)
f6(x)拟合训练数据的*方损失误差是




L(y,f6(x))=∑i=110(yi?f6(xi))2=0.71
L(y,f6(x))=∑i=110(yi?f6(xi))2=0.71
假设此时已经满足误差要求,那么


f(x)=f6(x)
f(x)=f6(x)即为所求的回归树。




友情链接: