提升树

提升树是以分类树或回归树为基本分类器的提升方法

11.1 提升树模型

提升方法实际采用加法模型(即基函数的线性组合)与前向分步算法。对分类问题,决策树是二叉分类树;对回归问题,决策树是二叉回归树。

提升树模型可以表示为决策树的加法模型:

其中,表示决策树;为决策树的参数;M为树的个数。

11.2 提升树算法

提升树算法采用前向分步算法。首先确定初始提升树,第m步的模型是:

其中,为当前模型,通过经验风险极小化确定下一棵决策树的参数

针对不同问题的提升树学习算法,其主要区别在于使用的损失函数不同。如:用平方误差损失函数的回归问题,用指数损失函数的分类问题,以及用一般损失函数的一般决策问题。

已知一个训练数据集为输入空间,为输出空间。根据5.5节,树可以表示为:

其中,参数表示树的区域划分和各区域上的常数。J是回归树的复杂度即叶节点个数。

回归问题提升树使用以下前向分步算法:

在前向分步算法的第m步,给定当前模型,需求解

得到,即第m棵树的参数。

当采用平方误差损失函数时,

其损失变为

这里,

是当前模型拟合数据的残差。所以,对回归问题的提升树来说,只需简单的拟合当前模型的残差

算法11.1(回归问题的提升树算法)

输入:训练数据集

输出:提升树

(1)初始化

(2)对m=1,2,…,M

(a)按式(11.5)计算残差

(b)拟合残差学习一个回归树,得到

(c)更新

(3)得到回归问题提升树

11.3 梯度提升

提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失函数时,每一步优化是很简单的

但是,对一般损失函数而言,每一步优化往往比较困难

这里我们使用梯度提升算法来解决这个问题。

算法11.2(梯度提升算法)

输入:训练数据集为输入空间,为输出空间。损失函数

输出:回归树

(1)初始化

(2)对m=1,2,…,M

(a)对i=1,2,…,N,计算

(b)拟合一个回归树,得到第m棵树的叶节点区域,j=1,2,…,J

(c)对j=1,2,…,J,计算

(d)更新

(3)得到回归树

算法说明如下:

第1步初始化,估计使损失函数极小化的常数值,它是只有一个根节点的树。

第2(a)步计算损失函数的负梯度在当前模型的值,将它作为残差的估计。(对于平方损失函数,它就是所谓的残差;对于一般损失函数,它是残差的近似值)

第2(b)步估计回归树节点区域,以拟合残差的近似值。

第2(c)步利用线性搜索估计叶节点区域的值,使损失函数极小化。

第2(d)步更新回归树。

第3步得到输出的最终模型