机器学习算法之集成学习（四）

标题：

提升树简介

回归树

残差

回归树算法

回归树实例

1.提升树

这次，我们来介绍属于Boost方法中的一个经典模型——提升树模型。提升树被认为是统计学习中，性能最好的方法之一，由其延伸出的梯度提升树（GBDT）和其升级版XGBoost至今仍是各类大数据比赛中最常用的“大杀器”。

提升树本身，其实就是决策树的加法模型，而所谓加法模型，实际上就是弱分类器的线性组合，当这个弱分类器为决策树的时候，这个提升方法便称为提升树。

我们可以将提升树模型表示为：

其中T表示决策树，θ表示决策树的参数，M则表示树的个数。

提升树的生成算法同样是前向分布算法（即AdaBoost的算法）。首先确定初始提升树，第m步的模型则为：

是当前的整个模型，后面的是该模型在该步（第m步）要线性组合上的决策树。

每一步的决策树的参数通过经验风险极小化拟来合：

对于二分类问题，提升树算法实际上就是AdaBoost算法中基本分类器被替换为二分类树的算法，这个时候我们也可以将其称为AdaBoost算法的特殊情况。

2.回归树

而当我们要求解一个回归问题时，我们则需要让每一步的添加，都去拟合数据集与上一步中模型预测结果的残差，这个算法的具体步骤如下：

假设输入训练集：

输出模型：

我们如果将输入空间X划分为J个互不相交的区域，那么一棵回归树我们可以表示为：

其中表示在每个区域上确定输出的常量，参数表示树的区域划分和各区域上表示该区域的常数，J表示回归树的结点个数（又称为回归树的复杂度），I则是指示函数（当输入x在区域内时输出1，否则输出0）。

回归树采用以下前向分布算法：

该前向分布算法的关键在第m步，给定当前模型求解时，参数应该如何拟合，我们将其转化为问题：

即求解一个能够使得损失函数取最小值的参数。假设，我们这个时候用的损失函数是平方损失函数：

那么，这个问题的损失函数就为：

a.残差

我们可以将表达式称为当前模型拟合数据的残差（residual）并用符号表示。这么一来，我们可以把原来的损失函数转化为：

其中。

然后，我们便可以拟合残差学习出一个回归树，将其添加进当前模型，构成一个新模型。这样不断更新下去，便可以得到最终的提升树模型：

b.提升树算法

现我们将提升树算法简述如下：

输入：

输出：

1.初始化

2.对回归树，计算残差

3.拟合残差，学习得到回归树

4.更新模型

5.重复2-4步，直到模型达到设定的拟合程度（例如总误差小于0.001），得到最终模型：

3.回归树实例

然而，如果有pong友当算直接通过我所介绍的这个算法来找个例子自己尝试一下的话，他就会发现，他会在“拟合残差”这一步遇到困难。原因很简单，因为这一步尽管被我在上面轻飘飘的一笔带过：

但其实还是需要使用一些方法的。我们假设有这样一个例子：

训练集：

求一个基于该训练集的提升树模型。

假设我们使用决策树桩作为基函数，损失函数为平方损失函数。那么，我们考虑优化问题：

来求解训练数据的初始分割点：

容易求得，在区域R1和R2内部使平方损失函数达到最小值的c1，c2为：

（其中N1和N2表示落在区域R1和R2内的样本点数目。）

根据所给数据，我们考虑如下切分点：

对每个切分点，我们可以很简单的求出相应的R1，R2，c1，c2，以及m(s)：

假设我们以1.5为切分点，那么就有R1= ，R2=，从而求得c1=1，c2=1，。

我们将每个切分点对应的m(s)求出来：

取最小的切分点为初始回归树：

然后以这个回归树为初始模型，计算残差r=y-T(x)，得到新数据集：

然后，我们就可以以这个数据集为基础，用计算上面初始回归树的方法计算出下一个回归树（其实计算初始回归树的方法也可以看作是把0作为计算的“第m步”而已），不断重复，直至得到最终的提升树模型。

资料参考来源：

清华大学出版社 李航 《统计学习方法》

AI遇见机器学习

mltoai