决策树—回归[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

核心：划分点选择 + 输出值确定。

一、概述

决策树是一种基本的分类与回归方法，本文叙述的是回归部分。回归决策树主要指CART(classification and regression tree)算法，内部结点特征的取值为“是”和“否”，为二叉树结构。

所谓回归，就是根据特征向量来决定对应的输出值。回归树就是将特征空间划分成若干单元，每一个划分单元有一个特定的输出。因为每个结点都是“是”和“否”的判断，所以划分的边界是平行于坐标轴的。对于测试数据，我们只要按照特征将其归到某个单元，便得到对应的输出值。

【例】左边为对二维平面划分的决策树，右边为对应的划分示意图，其中c1,c2,c3,c4,c5是对应每个划分单元的输出。

如现在对一个新的向量(6,6)决定它对应的输出。第一维分量6介于5和8之间，第二维分量6小于8，根据此决策树很容易判断(6,6)所在的划分单元，其对应的输出值为c3.

划分的过程也就是建立树的过程，每划分一次，随即确定划分单元对应的输出，也就多了一个结点。当根据停止条件划分终止的时候，最终每个单元的输出也就确定了，也就是叶结点。

二、回归树建立

既然要划分，切分点怎么找？输出值又怎么确定？这两个问题也就是回归决策树的核心。

[切分点选择：最小二乘法]; [输出值：单元内均值].

1.原理

假设X和Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集为 $\small D=\left \{ (x_1,y_1 ),(x_2,y_2 ),...,(x_N,y_N) \right \}$ ，其中 $\small x_i=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(n)})$ 为输入实例(特征向量)，n为特征个数，i=1,2,…,N, N为样本容量。

对特征空间的划分采用启发式方法，每次划分逐一考察当前集合中所有特征的所有取值，根据平方误差最小化准则选择其中最优的一个作为切分点。如对训练集中第j个特征变量 $\small x^{(j)}$ 和它的取值s，作为切分变量和切分点，并定义两个区域 $\small R_1(j,s)=\left \{ x|x^{(j)}\leqslant s \right \}$ 和 $\small j$ 和 $\small s$ ，对下式求解

$\min_{j,s}\left [ \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} \right ]$ (1.1)

也就是找出使要划分的两个区域平方误差和最小的 $\small j$ 和 $\small s$ .

其中， $\small c_1$ , $\small c_2$ 为划分后两个区域内固定的输出值，方括号内的两个min意为使用的是最优的 $\small c_1$ 和 $\small c_2$ ，也就是使各自区域内平方误差最小的 $\small c_1$ 和 $\small c_2$ ，易知这两个最优的输出值就是各自对应区域内Y的均值，所以上式可写为

$\min_{j,s}\left [\sum_{x_i\in R_1(j,s)}(y_i-\hat{c_1})^{2}+\sum_{x_i\in R_2(j,s)}(y_i-\hat{c_2})^{2} \right ]$ (1.2)

其中 $\small \hat{c_1}=\frac{1}{N_1}\sum_{x_i\in R_1(j,s)}y_i$ ， $\small \hat{c_2}=\frac{1}{N_2}\sum_{x_i\in R_2(j,s)}y_i$ .

现证明一维空间中样本均值是最优的输出值（平方误差最小）：

给定一个随机数列 $\small \left \{ x_1,x_2,...,x_n \right \}$ ，设该空间中最优的输出值为 $\small a$ ,根据最小平方误差准则，构造 $\small a$ 的函数如下：

考察其单调性，

$F'(a)=-2(x_1-a)-2(x_2-a)+...-2(x_n-a)=2na-2\sum_{i=1}^{n}x_i$

令 $\small F'(a)=0$ 得，

$a=\frac{1}{n}\sum_{i=1}^{n}x_i$

根据其单调性，易知 $\small \hat{a}=\frac{1}{n}\sum_{i=1}^{n}x_i$ 为最小值点。证毕。

找到最优的切分点(j,s)后，依次将输入空间划分为两个区域，接着对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成了一棵回归树，这样的回归树通常称为最小二乘回归树。

2. 算法叙述

输入：训练数据集 $\small D$ ；

输出：回归树 $\small f(x)$ .

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

(1) 选择最优切分变量j与切分点s，求解

(1.3)

遍历变量 $\small j$ ，对固定的切分变量 $\small j$ 扫描切分点 $\small s$ ，选择使上式达到最小值的对 $\small (j,s)$ .

(2) 用选定的对 $\small \left ( j,s \right )$ 划分区域并决定相应的输出值：

$\hat{c_m}=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i$ ， $x\in R_m,m=1,2$ (1.4)

其中， $\small R_1(j,s)=\left \{x|x^{(j)}\leqslant s \right \}$ ， $\small R_1,R_2,...,R_M$ ，生成决策树：

$f(x)=\sum_{m=1}^{M}\hat{c_m}I(x\in R_m)$ (1.5)

其中 $\small I$ 为指示函数， $\small I=\left\{\begin{matrix} 1 &if(x\in R_m) \\ 0 &if(x\notin R_m) \end{matrix}\right.$ .

三、示例

下表为训练数据集，特征向量只有一维，根据此数据表建立回归决策树。

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) 选择最优切分变量j与最优切分点s：

在本数据集中，只有一个特征变量，最优切分变量自然是x。接下来考虑9个切分点 $\small \left \{ 1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5 \right \}$ （切分变量两个相邻取值区间 $\small [a^i,a^{i+1})$ 内任一点均可），根据式(1.2)计算每个待切分点的损失函数值：

损失函数为（同式(1.2)）

$L(j,s)=\sum_{x_i\in R_1(j,s)}(y_i-\hat{c_1})^{2}+\sum_{x_i\in R_2(j,s)}(y_i-\hat{c_2})^{2}$

其中 $\small \hat{c_1}=\frac{1}{N_1}\sum_{x_i\in R_1(j,s)}y_i$ ， $\small \hat{c_2}=\frac{1}{N_2}\sum_{x_i\in R_2(j,s)}y_i$ .

a. 计算子区域输出值

当s=1.5时，两个子区域 $\small R_1=\left \{ 1 \right \}$ ， $\small R_2=\left \{ 2,3,4,5,6,7,8,9,10 \right \}$ ，

$\small c_1=5.56$ ， $\small c_2=\frac{1}{9}(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)=7.5$

同理，得到其他各切分点的子区域输出值，列表如下

s	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5
$\small c_1$	5.56	5.63	5.72	5.89	6.07	6.24	6.62	6.88	7.11
$\small c_2$	7.5	7.73	7.99	8.25	8.54	8.91	8.92	9.03	9.05

b. 计算损失函数值，找到最优切分点

当s=1.5时，

$\small L(1.5)=(5.56-5.56)^2+[(5.7-7.5)^2+(5.91-7.5)^2+...+(9.05-7.5)^2 ]$

$\small =0+15.72$

$\small =15.72$

同理，计算得到其他各切分点的损失函数值，列表如下

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

易知，取s=6.5时，损失函数值最小。因此，第一个划分点为(j=x,s=6.5).

(2) 用选定的对划分区域并决定相应的输出值：

划分区域为： $\small R_1=\left \{ 1,2,3,4,5,6 \right \}$ ， $\small R_2=\left \{ 7,8,9,10 \right \}$

对应输出值： $\small c_1=6.24$ ， $\small c_2=8.91$

(3) 调用步骤(1),(2)，继续划分：

对 $\small R_1$ ，取切分点 $\small \left \{ 1.5,2.5,3.5,4.5,5.5 \right \}$ ，计算得到单元输出值为

s	1.5	2.5	3.5	4.5	5.5
$\small c_1$	5.56	5.63	5.72	5.89	6.07
$\small c_2$	6.37	6.54	6.75	6.93	7.05

损失函数值为

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

L(3.5)最小，取s=3.5为划分点。

后面同理。

(4) 生成回归树：

假设两次划分后即停止，则最终生成的回归树为：

四、Python实现

对第三部分例子的python实现及与线性回归对比。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
from sklearn import linear_model

# Data set
x = np.array(list(range(1, 11))).reshape(-1, 1)
y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05]).ravel()

# Fit regression model
model1 = DecisionTreeRegressor(max_depth=1)
model2 = DecisionTreeRegressor(max_depth=3)
model3 = linear_model.LinearRegression()
model1.fit(x, y)
model2.fit(x, y)
model3.fit(x, y)

# Predict
X_test = np.arange(0.0, 10.0, 0.01)[:, np.newaxis]
y_1 = model1.predict(X_test)
y_2 = model2.predict(X_test)
y_3 = model3.predict(X_test)

# Plot the results
plt.figure()
plt.scatter(x, y, s=20, edgecolor="black",
            c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue",
         label="max_depth=1", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=3", linewidth=2)
plt.plot(X_test, y_3, color='red', label='liner regression', linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()

运行结果：