Cart回归决策树

1. 回归决策树构建原理¶

CART 回归树和 CART 分类树的不同之处在于:

1. CART 分类树预测输出的是一个离散值，CART 回归树预测输出的是一个连续值。
2. CART 分类树使用基尼指数作为划分、构建树的依据，CART 回归树使用平方损失。
3. 分类树使用叶子节点里出现更多次数的类别作为预测类别，回归树则采用叶子节点里均值作为预测输出

CART 回归树构建:

Loss⁡(y,f(x))=(f(x)−y)2

例子：

假设：数据集只有 1 个特征 x, 目标值值为 y，如下图所示：

x	1	2	3	4	5	6	7	8	9	10
y	5.56	5.7	5.91	6.4	6.8	7.05	8.9	8.7	9	9.05

由于只有 1 个特征，所以只需要选择该特征的最优划分点，并不需要计算其他特征。

1. 先将特征 x 的值排序，并取相邻元素均值作为待划分点，如下图所示：

s	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5

1. 计算每一个划分点的平方损失，例如：1.5 的平方损失计算过程为：

R1 为 小于 1.5 的样本个数，样本数量为：1，其输出值为：5.56

R1=5.56

R2 为 大于 1.5 的样本个数，样本数量为：9 ，其输出值为：

R2=(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)/9=7.50

该划分点的平方损失：

L(1.5)=(5.56−5.56)2+[(5.7−7.5)2+(5.91−7.5)2+…+(9.05−7.5)2]=0+15.72=15.72

1. 以此方式计算 2.5、3.5... 等划分点的平方损失，结果如下所示：

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

1. 当划分点 s=6.5 时，m(s) 最小。因此，第一个划分变量：特征为 X, 切分点为 6.5，即：j=x, s=6.5

1. 对左子树的 6 个结点计算每个划分点的平方式损失，找出最优划分点：

x	1	2	3	4	5	6
y	5.56	5.7	5.91	6.4	6.8	7.05

s	1.5	2.5	3.5	4.5	5.5
c1	5.56	5.63	5.72	5.89	6.07
c2	6.37	6.54	6.75	6.93	7.05

s	1.5	2.5	3.5	4.5	5.5
m(s)	1.3087	0.754	0.2771	0.4368	1.0644

1. s=3.5时，m(s) 最小，所以左子树继续以 3.5 进行分裂:

1. 假设在生成3个区域 之后停止划分，以上就是回归树。每一个叶子结点的输出为：挂在该结点上的所有样本均值。

x	1	2	3	4	5	6	7	8	9	10
y	5.56	5.7	5.91	6.4	6.8	7.05	8.9	8.7	9	9.05

1号样本真实值 5.56 预测结果：5.72

2号样本真实值是 5.7 预测结果：5.72

3 号样本真实值是 5.91 预测结果 5.72

CART 回归树构建过程如下：

1. 选择第一个特征，将该特征的值进行排序，取相邻点计算均值作为待划分点
2. 根据所有划分点，将数据集分成两部分：R1、R2
3. R1 和 R2 两部分的平方损失相加作为该切分点平方损失
4. 取最小的平方损失的划分点，作为当前特征的划分点
5. 以此计算其他特征的最优划分点、以及该划分点对应的损失值
6. 在所有的特征的划分点中，选择出最小平方损失的划分点，作为当前树的分裂点