决策树一回归

文章目录

• 决策树一回归
• • 一、概述
  • 二、回归树建立
  • • 1. 原理
    • 2. 算法叙述
  • 三、示例
  • 四. Python 实现
  • • 程序源代码
    • 运行结果:
  • 参考:

核心: 划分点选择 + 输出值确定.

一、概述

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

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

【例】左边为对二维平面划分的决策树, 右边为对应的划分示意图, 其中 c 1 , c 2 , c 3 , c 4 , c 5 c_{1}, c_{2}, c_{3}, c_{4}, c_{5} c1​,c2​,c3​,c4​,c5​ 是对应每个划分单元的输出.

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

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

二、回归树建立

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

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

1. 原理

假设 X \mathrm{X} X 和 Y \mathrm{Y} Y 分别为输入和输出变量, 并且 Y \mathrm{Y} Y 是连续变量, 给定训练数据集为 D = \mathrm{D}= D= { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x N , y N ) } \left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\} {(x1​,y1​),(x2​,y2​),…,(xN​,yN​)}, 其中 x i = ( x i ( 1 ) , x i ( 2 ) , … , x i ( n ) ) x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right) xi​=(xi(1)​,xi(2)​,…,xi(n)​) 为输入实例(特征向量), n \mathrm{n} n 为特 征个数, i = 1 , 2 , … , N , N \mathrm{i}=1,2, \ldots, \mathrm{N}, \mathrm{N} i=1,2,…,N,N 为样本容量.

对特征空间的划分采用启发式方法, 每次划分逐一考察当前集合中所有特征的所有取值, 根据平方误差最小化准则选择其中最优的一个作为切分点.如对训练集中第 j j j 个特征变量 x ( j ) x^{(j)} x(j) 和它的取值 s s s, 作为切分变量和切分点, 并定义两个区域 R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\} R1​(j,s)={x∣x(j)≤s} 和 R 2 ( j , s ) = R_{2}(j, s)= R2​(j,s)= { x ∣ x ( j ) > s } \left\{x \mid x^{(j)}>s\right\} {x∣x(j)>s}, 为找出最优的 j \mathrm{j} j 和 s \mathrm{s} s, 对下式求解

min ⁡ j , s [ min ⁡ c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right] j,smin​⎣⎡​c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2⎦⎤​

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

其中, c 1 , c 2 c_{1}, c_{2} c1​,c2​ 为划分后两个区域内固定的输出值, 方括号内的两个 min ⁡ \min min 意为使用的是最 优的 c 1 c_{1} c1​ 和 c 2 c_{2} c2​, 也就是使各自区域内平方误差最小的 c 1 c_{1} c1​ 和 c 2 c_{2} c2​, 易知这两个最优的输出值就是各 自对应区域内 Y Y Y 的均值, 所以上式可写为

min ⁡ j , s [ ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ^ ) 2 + ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ^ ) 2 ] \min _{j, s}\left[\sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-\widehat{c_{1}}\right)^{2}+\sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-\widehat{c_{2}}\right)^{2}\right] j,smin​⎣⎡​xi​∈R1​(j,s)∑​(yi​−c1​ ​)2+xi​∈R2​(j,s)∑​(yi​−c2​ ​)2⎦⎤​

其中 C 1 ^ = 1 N 1 ∑ x i ∈ R 1 ( j , s ) y i , c 2 ^ = 1 N 2 ∑ x i ∈ R 2 ( j , s ) y i \widehat{C_{1}}=\frac{1}{N_{1}} \sum_{x_{i} \in R_{1}(j, s)} y_{i}, \widehat{c_{2}}=\frac{1}{N_{2}} \sum_{x_{i} \in R_{2}(j, s)} y_{i} C1​ ​=N1​1​∑xi​∈R1​(j,s)​yi​,c2​ ​=N2​1​∑xi​∈R2​(j,s)​yi​.

---

现证明一维空间中样本均值是最优的输出值 (平方误差最小):

给定一个随机数列 { x 1 , x 2 , … , x n } \left\{x_{1}, x_{2}, \ldots, x_{n}\right\} {x1​,x2​,…,xn​}, 设该空间中最优的输出值为 a a a, 根据最小平方误差准则, 构造 a a a 的函数如下:

F ( a ) = ( x 1 − a ) 2 + ( x 2 − a ) 2 + ⋯ + ( x n − a ) 2 \mathrm{F}(\mathrm{a})=\left(x_{1}-a\right)^{2}+\left(x_{2}-a\right)^{2}+\cdots+\left(x_{n}-a\right)^{2} F(a)=(x1​−a)2+(x2​−a)2+⋯+(xn​−a)2

考察其单调性,

F ′ ( a ) = − 2 ( x 1 − a ) − 2 ( x 2 − a ) + ⋯ − 2 ( x n − a ) = 2 n a − 2 ∑ i = 1 n x i F^{\prime}(a)=-2\left(x_{1}-a\right)-2\left(x_{2}-a\right)+\cdots-2\left(x_{n}-a\right)=2 n a-2 \sum_{i=1}^{n} x_{i} F′(a)=−2(x1​−a)−2(x2​−a)+⋯−2(xn​−a)=2na−2i=1∑n​xi​

令 F ′ ( a ) = 0 F^{\prime}(a)=0 F′(a)=0 得, a = 1 n ∑ i = 1 n x i a=\frac{1}{n} \sum_{i=1}^{n} x_{i} a=n1​∑i=1n​xi​

根据其单调性, 易知 a ^ = 1 n ∑ i = 1 n x i \hat{a}=\frac{1}{n} \sum_{i=1}^{n} x_{i} a^=n1​∑i=1n​xi​ 为最小值点.证毕.

---

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

2. 算法叙述

输入: 训练数据集 D;

输出: 回归树 f ( x ) f(x) f(x).

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

(1) 选择最优切分变量 j \mathrm{j} j 与切分点 s \mathrm{s} s, 求解

min ⁡ j , s [ min ⁡ c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + min ⁡ c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] \min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right] j,smin​⎣⎡​c1​min​xi​∈R1​(j,s)∑​(yi​−c1​)2+c2​min​xi​∈R2​(j,s)∑​(yi​−c2​)2⎦⎤​

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

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

c m ^ = 1 N m ∑ x i ∈ R m ( j , s ) y i , x ∈ R m ,   m = 1 , 2 \widehat{c_{m}}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}, \quad \mathrm{x} \in R_{m}, \mathrm{~m}=1,2 cm​ ​=Nm​1​xi​∈Rm​(j,s)∑​yi​,x∈Rm​, m=1,2

其中, R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } , R 2 ( j , s ) = { x ∣ x ( j ) > s } R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\}, R_{2}(j, s)=\left\{x \mid x^{(j)}>s\right\} R1​(j,s)={x∣x(j)≤s},R2​(j,s)={x∣x(j)>s}.

(3) 继续对两个子区域调用步骤(1),(2), 直至满足停止条件.

(4) 将输入空间划分为 M M M 个区域 R 1 , R 1 , … , R M R_{1}, R_{1}, \ldots, R_{M} R1​,R1​,…,RM​, 生成决策树:

f ( x ) = ∑ m = 1 M c m ^ I ( x ∈ R m ) \mathrm{f}(\mathrm{x})=\sum_{m=1}^{M} \widehat{c_{m}} I\left(x \in R_{m}\right) f(x)=m=1∑M​cm​ ​I(x∈Rm​)

其中 | 为指示函数, I = { 1  if  ( x ∈ R m ) 0  if  ( x ∉ R m ) \mathrm{I}=\left\{\begin{array}{l}1 \text { if }\left(x \in R_{m}\right) \\ 0 \text { if }\left(x \notin R_{m}\right)\end{array}\right. I={1 if (x∈Rm​)0 if (x∈/​Rm​)​

三、示例

(参考: @一个拉风的名字
)

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

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 \mathrm{j} j 与最优切分点 s \mathrm{s} s : 在本数据集中, 只有一个特征变量, 最优切分变量自然是 x \mathrm{x} x .接下来考虑 9 个切分点 { 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\} {1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5} (切分变量两个相邻取值区间 [ a i , a i + 1 \left[a^{i}, a^{i+1}\right. [ai,ai+1 ) 内任一点均可), 根据式(1.2)计算每个待切分点的损失函数值:

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

L ( j , s ) = ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ^ ) 2 + ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ^ ) 2 L(j, s)=\sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-\widehat{c_{1}}\right)^{2}+\sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-\widehat{c_{2}}\right)^{2} L(j,s)=xi​∈R1​(j,s)∑​(yi​−c1​ ​)2+xi​∈R2​(j,s)∑​(yi​−c2​ ​)2

其中 c 1 ^ = 1 N 1 ∑ x i ∈ R 1 ( j , s ) y i , c 2 ^ = 1 N 2 ∑ x i ∈ R 2 ( j , s ) y i \widehat{c_{1}}=\frac{1}{N_{1}} \sum_{x_{i} \in R_{1}(j, s)} y_{i}, \widehat{c_{2}}=\frac{1}{N_{2}} \sum_{x_{i} \in R_{2}(j, s)} y_{i} c1​ ​=N1​1​∑xi​∈R1​(j,s)​yi​,c2​ ​=N2​1​∑xi​∈R2​(j,s)​yi​.

a. 计算子区域输出值

当 s = 1.5 \mathrm{s}=1.5 s=1.5 时, 两个子区域 R 1 = { 1 } , R 2 = { 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } , c 1 = 5.56 \mathrm{R} 1=\{1\}, \mathrm{R} 2=\{2,3,4,5,6,7,8,9,10\}, c_{1}=5.56 R1={1},R2={2,3,4,5,6,7,8,9,10},c1​=5.56,

c 2 = 1 9 ( 5.7 + 5.91 + 6.4 + 6.8 + 7.05 + 8.9 + 8.7 + 9 + 9.05 ) = 7.5 c_{2}=\frac{1}{9}(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)=7.5 c2​=91​(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
c_(1)	5.56	5.63	5.72	5.89	6.07	6.24	6.62	6.88	7.11
c_(2)	7.5	7.73	7.99	8.25	8.54	8.91	8.92	9.03	9.05

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

当 s = 1.5 \mathrm{s}=1.5 s=1.5 时,

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 \begin{aligned} \mathrm{L}(1.5) &=(5.56-5.56)^{2}+\left[(5.7-7.5)^{2}+(5.91-7.5)^{2}+\cdots+(9.05-7.5)^{2}\right] \\ &=0+15.72 \\ &=15.72 \end{aligned} 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​

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

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 s=6.5 s=6.5 时, 损失函数值最小.因此, 第一个划分点为 ( j = x , s = 6.5 ) (j=x, s=6.5) (j=x,s=6.5).

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

划分区域为: R 1 = { 1 , 2 , 3 , 4 , 5 , 6 } , R 2 = { 7 , 8 , 9 , 10 } R_{1}=\{1,2,3,4,5,6\}, R_{2}=\{7,8,9,10\} R1​={1,2,3,4,5,6},R2​={7,8,9,10}

对应输出值: c 1 = 6.24 , c 2 = 8.91 c_{1}=6.24, c_{2}=8.91 c1​=6.24,c2​=8.91

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

 对  R 1 , 取切分点  { 1.5 , 2.5 , 3.5 , 4.5 , 5.5 } , 计算得到单元输出值为  \text { 对 } R_{1} \text {, 取切分点 }\{1.5,2.5,3.5,4.5,5.5\} \text {, 计算得到单元输出值为 }  对 R1​, 取切分点 {1.5,2.5,3.5,4.5,5.5}, 计算得到单元输出值为 

s	1.5	2.5	3.5	4.5	5.5
c_(1)	5.56	5.63	5.72	5.89	6.07
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 ) L(3.5) L(3.5) 最小, 取 s = 3.5 s=3.5 s=3.5 为划分点.

后面同理.

(4) 生成回归树:

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

T = { 5.72 , x ≤ 3.5 6.75 , 3.5 < x ≤ 6.5 8.91 , x > 6.5 \mathrm{T}=\left\{\begin{array}{cc} 5.72, & x \leq 3.5 \\ 6.75, & 3.5<x \leq 6.5 \\ 8.91, & x>6.5 \end{array}\right. T=⎩⎨⎧​5.72,6.75,8.91,​x≤3.53.5<x≤6.5x>6.5​

四. Python 实现

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

程序源代码

# 开发者:    Leo 刘
# 开发环境: macOs Big Sur
# 开发时间: 2021/11/23 12:48 下午
# 邮箱  : 517093978@qq.com
# @Software: PyCharm
# ----------------------------------------------------------------------------------------------------------
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()

运行结果:

Decision Tree Regression

参考:

1. 李航.《统计学习方法》.清华大学出版社.
2. 周志华.《机器学习》.清华大学出版社.
3. CSDN.一个拉风的名字