（点击
上方蓝字
，快速关注我们）
来源：伯乐在线 - iPytLab
如有好文章投稿，请点击 → 这里了解详情
前言
最近由于开始要把精力集中在课题的应用上面了，这篇总结之后算法原理的学习先告一段落。本文主要介绍决策树用于回归问题的相关算法实现，其中包括回归树(regression tree)和模型树(model tree)的实现，并介绍了预剪枝(preprune)和后剪枝(postprune)的防止树过拟合的技术以及实现。最后对回归树和标准线性回归进行了对比。
正文
在之前的文章中我总结了通过使用构建决策树来进行类型预测。直观来看树结构最容易对分类问题进行处理，通过递归我们在数据中选取最佳分割特征对训练数据进行分割并进行树分裂最终到达触底条件获得训练出来决策树，可以通过可视化的方式直观的查看训练模型并对数据进行分类。
通常决策树树分裂选择特征的方法有ID3, C4.5算法, C5.0算法和CART树。在《机器学习算法实践-决策树(Decision Tree)》中对ID3以及C4.5算法进行了介绍并使用ID3算法处理了分类问题。本文主要使用决策树解决回归问题，使用CART(Classification And Regression Trees)算法。
CART
CART是一种二分递归分割的技术，分割方法采用基于最小距离的基尼指数估计函数，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。
分类树是针对目标变量是离散型变量，通过二叉树将数据进行分割成离散类的方法。而回归树则是针对目标变量是连续性的变量，通过选取最优分割特征的某个值，然后数据根据大于或者小于这个值进行划分进行树分裂最终生成回归树。
特征和最佳分割点的选取
在使用决策树解决回归问题中我们需要不断的选取某一特征的一个值作为分割点来生成子树。选取的标准就是使得被分割的两部分数据能有最好的纯度。
树分裂的终止条件
有了选取分割特征和最佳分割点的方法，树便可以依此进行分裂，但是分裂的终止条件是什么呢?
-
节点中所有目标变量的值相同
, 既然都已经是相同的值了自然没有必要在分裂了，直接返回这个值就好了.
-
树的深度达到了预先指定的最大值
-
不纯度的减小量小于预先定好的阈值
,也就是之进一步的分割数据并不能更好的降低数据的不纯度的时候就可以停止树分裂了。
-
节点的数据量小于预先定好的阈值
回归树的Python实现
本部分使用Python实现简单的回归树，并对给定的数据进行回归并可视化回归曲线和树结构。完整代码详见: https://github.com/PytLab/MLBox/tree/master/classification_and_regression_trees
首先是加载数据的部分，这里的所有测试数据我均使用的《Machine Learning in Action》中的数据，格式比较规整加载方式也比较一致, 这里由于做树回归，自变量和因变量都放在同一个二维数组中:
def
load_data
(
filename
)
:
''' 加载文本文件中的数据.
'''
dataset
=
[]
with
open
(
filename
,
'r'
)
as
f
:
for
line
in
f
:
line_data
=
[
float
(
data
)
for
data
in
line
.
split
()]
dataset
.
append
(
line_data
)
return
dataset
树回归中再找到分割特征和分割值之后需要将数据进行划分以便构建子树或者叶子节点:
def
split_dataset
(
dataset
,
feat_idx
,
value
)
:
''' 根据给定的特征编号和特征值对数据集进行分割
'''
ldata
,
rdata
=
[],
[]
for
data
in
dataset
:
if
data
[
feat_idx
]
<
value
:
ldata
.
append
(
data
)
else
:
rdata
.
append
(
data
)
return
ldata
,
rdata
然后就是重要的选取最佳分割特征和分割值了，这里我们通过找到使得分割后的方差最小的分割点最为最佳分割点:
def
choose_best_feature
(
dataset
,
fleaf
,
ferr
,
opt
)
:
''' 选取最佳分割特征和特征值
dataset: 待划分的数据集
fleaf: 创建叶子节点的函数
ferr: 计算数据误差的函数
opt: 回归树参数.
err_tolerance: 最小误差下降值;
n_tolerance: 数据切分最小样本数
'''
dataset
=
np
.
array
(
dataset
)
m
,
n
=
dataset
.
shape
err_tolerance
,
n_tolerance
=
opt
[
'err_tolerance'
],
opt
[
'n_tolerance'
]
err
=
ferr
(
dataset
)
best_feat_idx
,
best_feat_val
,
best_err
=
0
,
0
,
float
(
'inf'
)
# 遍历所有特征
for
feat_idx
in
range
(
n
-
1
)
:
values
=
dataset
[
:
,
feat_idx
]
# 遍历所有特征值
for
val
in
values
:
# 按照当前特征和特征值分割数据
ldata
,
rdata
=
split_dataset
(
dataset
.
tolist
(),
feat_idx
,
val
)
if
len
(
ldata
)
<
n_tolerance
or
len
(
rdata
)
<
n_tolerance
:
# 如果切分的样本量太小
continue
# 计算误差
new_err
=
ferr
(
ldata
)
+
ferr
(
rdata
)
if
new_err
<
best_err
:
best_feat_idx
=
feat_idx
best_feat_val
=
val
best_err
=
new_err
# 如果误差变化并不大归为一类
if
abs
(
err
-
best_err
)
<
err_tolerance
:
return
None
,
fleaf
(
dataset
)
# 检查分割样本量是不是太小
ldata
,
rdata
=
split_dataset
(
dataset
.
tolist
(),
best_feat_idx
,
best_feat_val
)
if
len
(
ldata
)
<
n_tolerance
or
len
(
rdata
)
<
n_tolerance
:
return
None
,
fleaf
(
dataset
)
return
best_feat_idx
,
best_feat_val
其中，停止选取的条件有两个: 一个是当分割的子数据集的大小小于一定值；一个是当选取的最佳分割点分割的数据的方差减小量小于一定的值。
fleaf是创建叶子节点的函数引用，不同的树结构此函数也是不同的，例如本部分的回归树，创建叶子节点就是根据分割后的数据集平均值，而对于模型树来说，此函数返回值是根据数据集得到的回归系数。ferr是计算数据集不纯度的函数，不同的树模型该函数也会不同，对于回归树，此函数计算数据集的方差来判定数据集的纯度，而对于模型树来说我们需要计算线性模型拟合程度也就是线性模型的残差平方和。
然后就是最主要的回归树的生成函数了，树结构肯定需要通过递归创建的，选不出新的分割点的时候就触底：
def
create_tree
(
dataset
,
fleaf
,
ferr
,
opt
=
None
)
:
''' 递归创建树结构
dataset: 待划分的数据集
fleaf: 创建叶子节点的函数
ferr: 计算数据误差的函数
opt: 回归树参数.
err_tolerance: 最小误差下降值;
n_tolerance: 数据切分最小样本数
'''
if
opt
is
None
:
opt
=
{
'err_tolerance'
:
1
,
'n_tolerance'
:
4
}
# 选择最优化分特征和特征值
feat_idx
,
value
=
choose_best_feature
(
dataset
,
fleaf
,
ferr
,
opt
)
# 触底条件
if
feat_idx
is
None
:
return
value
# 创建回归树
tree
=
{
'feat_idx'
:
feat_idx
,
'feat_val'
:
value
}
# 递归创建左子树和右子树
ldata
,
rdata
=
split_dataset
(
dataset
,
feat_idx
,
value
)
ltree
=
create_tree
(
ldata
,
fleaf
,
ferr
,
opt
)
rtree
=
create_tree
(
rdata
,
fleaf
,
ferr
,
opt
)
tree
[
'left'
]
=
ltree
tree
[
'right'
]
=
rtree
return
tree
使用回归树对数据进行回归
这里使用了现成的分段数据作为训练数据生成回归树，本文所有使用的数据详见: https://github.com/PytLab/MLBox/tree/master/classification_and_regression_trees
可视化数据点
dataset
=
load_data
(
'ex0.txt'
)
dataset
=
np
.
array
(
dataset
)
# 绘制散点
plt
.
scatter
(
dataset
[
:
,
0
],
dataset
[
:
,
1
])
创建回归树并可视化
看到这种分段的数据，回归树拟合它可是最合适不过了，我们创建回归树:
tree
=
create_tree
(
dataset
,
fleaf
,
ferr
,
opt
=
{
'n_tolerance'
:
4
,
'err_tolerance'
:
1
})
通过Python字典表示的回归树结构:
{
'feat_idx'
:
0
,
'feat_val'
:
0.40015800000000001
,
'left'
:
{
'feat_idx'
:
0
,
'feat_val'
:
0.20819699999999999
,
'left'
: -
0.023838155555555553
,
'right'
:
1.0289583666666666
},
'right'
:
{
'feat_idx'
:
0
,
'feat_val'
:
0.609483
,
'left'
:
1.980035071428571
,
'right'
:
{
'feat_idx'
:
0
,
'feat_val'
:
0.81674199999999997
,
'left'
:
2.9836209534883724
,
'right'
:
3.9871631999999999
}}}
这里我还是使用Graphviz来可视化回归树，类似之前决策树做分类的文章中的dotify函数，这里稍微修改下叶子节点的label，我们便可以递归得到决策树对应的dot文件, dotify函数的实现见:https://github.com/PytLab/MLBox/blob/master/classification_and_regression_trees/regression_tree.py#L159
然后获取树结构图:
datafile
=
'ex0.txt'
dotfile
=
'{}.dot'
.
format
(
datafile
.
split
(
'.'
)[
0
])
with
