机器学习算法之树回归

45 sec read

在前面的文章中介绍了基本的线性回归模型属于全局的模型(除局部加权线性回归外),在线性回归模型中,其前提是假设全局的数据之间是线性的,通过拟合所有的样本点,训练得到最终的模型。然而现实中的很多问题是非线性的,当处理这类复杂的数据的回归问题时,特征之间的关系并不是简单的线性关系,此时,不可能利用全局的线性回归模型拟合这类数据。

CART树回归算法属于一种局部的回归算法,通过将全局的数据集划分成多份容易建模的数据集,这样在每一个局部的数据集上进行局部的回归建模。

复杂的回归问题

线性回归模型

在基本的线性回归算法中,样本的特征与样本的标签之间存在线性相关关系,但是,对于样本特征与样本标签存在非线性的关系时,如图所示:

对于上图所示的非线性的回归问题,利用简单的线性回归求解的结果如图所示:

局部加权线性回归

为了能够实现对非线性数据的拟合,可以使用局部加权线性回归,局部加权线性回归的求解结果如图所示:

局部加权线性回归能够对非线性的数据实现较好拟合,与简单的线性回归算法相比,局部线性加权回归算法是局部的线性模型,而简单的线性回归模型是全局的模型,利用局部的模型能够较好拟合出局部的数据。虽然基于局部加权线性回归模型能够较好拟合非线性数据,但是局部加权线性回归模型属于非参学习算法,在每次对数据进行预测时,需要利用数据重新训练模型的参数,当数据量较大时,这样的计算是非常耗费时间的。

CART算法

基于树的回归算法也是一类基于局部的回归算法,通过将数据集切分成多份,在每一份数据中单独建模。与局部加权线性回归不同的是,基于树回归的算法是一种基于参数的学习算法,利用训练数据训练完模型后,参数一旦确定,无需再改变。

分类回归树(Classification And Regression Tree,CART)算法是使用较多的一种树模型,CART算法可以处理分类问题,也可以处理回归问题。在决策树算法文章中,我们介绍了如何利用CART算法处理分类问题,在本文中,我们着重介绍如何利用CART算法处理回归问题。CART算法中的树采用一种二分递归分割的技术,即将当前的样本集分为左子树和右子树两个子样本集,使得生成的每个非叶子节点都有两个分支。因此,CART算法生成的决策树是非典型的二叉树。利用CART算法处理回归问题的主要步骤:①CART回归树的生成;②CART回归树的剪枝。

CART回归树生成

CART回归树的划分

CART分类树算法中,利用Gini指数作为划分树的指标,通过样本中的特征,对样本进行划分,直到所有的叶节点中的所有样本都为同一个类别为止。但是在 CART 回归树中,样本的标签是一系列的连续值的集合,不能再使用 Gini 指数作为划分树的指标。但是,我们注意到,Gini指数表示的是数据的混乱程度,对于连续数据,当数据分布比较分散时,各个数据与平均数的差的平方和较大,方差就较大;当数据分布比较集中时,各个数据与平均数的差的平方和较小。方差越大,数据的波动越大;方差越小,数据的波动就越小。因此,对于连续的数据,可以使用样本与平均值的差的平方和作为划分回归树的指标:

    \[m\cdot s^2 = \sum_{i=1}^{m}(y^{(i)}-\bar{y})^2\]

其中y^{(i)}为第i个样本的标签,\bar{y}为m个样本标签的均值。公式用Python表示为:

rr_cnt函数用于计算当前节点的总方差。有了划分的标准,那么,应该如何对样本进行划分呢?与CART分类树中的方法一样,我们根据每一维特征中的每一个取值,尝试将样本划分到树节点的左右子树中,如取得样本特征中的第 j维特征中值x作为划分的值,如果一个样本在第 j维处的值大于或者等于x,则将其划分到右子树中,否则划分到左子树中。划分过程程序如下:

split_tree函数根据fea位置处的特征,按照值value将样本划分到左右子树中,当样本在fea处的值大于或者等于value时,将其划分到右子树中,否则将其划分到左子树中。

CART回归树的构建

CART分类树的构建过程如下所示:

  1. 对于当前训练数据集,遍历所有属性及其所有可能的切分点,寻找最佳切分属性及其最佳切分点,使得切分之后的基尼指数最小,利用该最佳属性及其最佳切分点将训练数据集切分成两个子集,分别对应着判别结果是左子树和判别结果是右子树。
  2. 对第一步中生成的两个数据子集递归地调用第一步,直至满足停止条件。
  3. 生成CART决策树

为了能构建CART回归树算法,首先,需要为CART回归树中节点设置一个结构,其具体的实现:

在CART回归树的节点类中,属性fea表示的是待划分数据集的特征的索引,属性value表示的是划分的具体的值,属性results表示的是叶子节点的具体的值,属性right表示的是右子树,属性left表示的是左子树。现在,让我们一起实现CART回归树:

build_tree 函数用于构建 CART 回归树模型,在构建 CART回归树模型的过程中,如果节点中的样本的个数小于或者等于指定的最小的样本数min_sample,则该节点不再划分,函数leaf用于计算当前叶子节点的值;当节点需要划分时,首先计算当前节点的error值在开始构建的过程中,根据每一维特征的取值尝试将样本划分到左右子树中。划分后产生左子树和右子树,此时,计算左右子树的error值,若此时的error值小于最优的 error 值,则更新最优划分,当该节点划分完成后,继续对其左右子树进行划分:

函数leaf用于计算当前叶子节点的值,计算的方法是使用划分到该叶子节点的所有样本的标签的均值。

CART回归树剪枝

在CART树回归中,当树中的节点对样本一直划分下去时,会出现的最极端的情况是:每一个叶子节点中仅包含一个样本,此时,叶子节点的值即为该样本的标签的值。这种情况极易对训练样本“过拟合”,通过这样的方式训练出来的样本可以对训练样本拟合得很好,但是对于新样本的预测效果将会较差。为了防止构建好的CART树回归模型过拟合,通常需要对CART回归树进行剪枝,剪枝的目的是防止CART回归树生成过多的叶子节点。在剪枝中主要分为:前剪枝和后剪枝。

前剪枝

前剪枝是指在生成CART回归树的过程中对树的深度进行控制,防止生成过多的叶子节点。在build_tree函数中,我们通过参数min_sample和min_err来控制树中的节点是否需要进行更多的划分。通过不断调节这两个参数,来找到一个合适的CART树模型。

后剪枝

后剪枝是指将训练样本分成两个部分,一部分用来训练CART树模型,这部分数据被称为训练数据,另一部分用来对生成的CART树模型进行剪枝,这部分数据被称为验证数据。由上述过程可知,在后剪枝的过程中,通过验证生成好的CART树模型是否在验证数据集上发生了过拟合,如果出现过拟合的现象,则合并一些叶子节点来达到对CART树模型的剪枝。

参考链接:https://github.com/apachecn/AiLearning/blob/master/src/py2.x/ml/9.RegTrees/regTrees.py

CART回归树对数据预测

有了以上的理论准备,我们利用上述实现好的函数,构建CART树回归模型。利用CART回归树算法进行求解的过程中,主要包括:①利用训练数据训练CART回归树模型;②利用训练好的CART回归树模型对新数据进行预测。

当训练好CART回归树,需要评估训练好的CART回归树模型时,函数cal_error用于评估训练好的CART回归树模型:

函数cal_error用于评估训练好的CART回归树模型,函数的输入分别为训练数据data和训练好的CART回归树模型tree,在评估CART回归树模型的过程中,利用训练好的CART回归树模型对每一个样本进行预测,函数predict的具体实现如下所示。当预测完成后,利用预测的值和原始的样本的标签计算残差。

函数 predict 利用训练好的 CART 回归树模型 tree 对样本sample进行预测。在预测的过程中,主要分为如下的情况:

  • 若此时只有根结点,则直接返回其值作为最终的预测结果
  • 若此时该结点有左右子树,则比较样本sample中在fea索引处的值val_sample和CART回归树模型中在划分处的值value
    • 若val_sample大于或等于CART回归树模型中的值value,则选择右子树
    • 若val_sample小于CART回归树模型中的值value,则选择左子树

最终对数据的拟合效果如图:

对min_sample和min_err取值进行调整,如图所示:

Python 中用 Scikit-Learn 实现决策树

决策树分类

决策树回归

参考资料:《Python机器学习算法-赵志勇》

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

机器学习算法之Catboost

CatBoost是俄罗斯的搜索巨头Yandex在2017年开源的机器学习库,是Gradient Boostin
2 min read

机器学习算法之LightGBM

上一篇文章介绍了一个梯度提升决策树模型XGBoost,这篇文章我们继续学习一下GBDT模型的另一个进化版本:L
7 min read

机器学习算法之XGBoost

在上一篇Boosting方法的介绍中,对XGBoost有过简单的介绍。为了更还的掌握XGBoost这个工具。我
14 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注