提升算法(2)小丑jk

提升树是以分类树或回归树为基本分类器的提升方法。提升方法实际采用加法模型(即基函数的线性组合)与前向分布算法，以决策树为基函数的提升方法称为提升树，对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树，其根据特征xv将根结点直接连接两个叶结点，以作为决策树桩。提升树模型可以表示为决策树的加法模型：

提升树算法采用前向分布算法，首先确定初始提升树f0(x)=0，第m步的模型是：

由于树的线性组合可以很好的拟合训练数据，即使数据中的输入域输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

针对不同问题的提升树学习算法主要区别在于使用的损失函数不同，包括使用平方误差损失函数的回归问题、指数损失函数的分类问题、及一般损失函数的一般决策问题。下面叙述关于回归问题的提升树。

回归问题提升树使用以下向前分步算法：(该方法就是以最小化损失函数为前提得到新增决策树的参数，并将该决策树加入原多个决策树构成新的多决策树)

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

其损失变成：

回归问题的提升树算法：

输出：提升树fM(x)

(1)初始化f0(x)=0

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

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

此处给出一个书上的例子用于理解上述的回归问题的提升算法：

已知如下表所示的训练数据，x的取值范围为区间[0.5,10.5]，y的取值范围为区间[5.0,10.0]，学习这个回归问题的提升树模型，考虑只用树桩作为基函数

按照如上算法，第1步求f1(x)即回归树T1(x)

首先通过以下优化问题：

求解训练数据的切分点s：

容易求得在R1，R2内部使平方损失误差达到最小值的c1，c2为：

这里N1，N2是R1，R2的样本点数。

求训练数据的切分点，根据所给数据，考虑如下切分点：

1.5,2.5,3.5,4.5,5.5,6.57.58.59.5

对各切分点，不难求出相应的R1，R2，c1，c2及

如当s取1.5时候，R1={1},R2={2,3,...,10},c1=5.56,c2=7.50

现将s及m(s)的计算结果列表如下所示：

由上表可知。当s=6.5时，m(s)达到最小值，此时R1={1,2,...,6},R2={7,8,9,10},c1=6.24,c2=8.91,所以回归树T1(x)为：

用f1(x)拟合训练数据的残差如下表所示，表中r2i=yi-f1(xi),i=1,2,...,10

用f1(x)拟合训练数据的平方损失误差：

第2步求T2(x)，方法同上，只是拟合的数据是上面的残差表，并将其与上面得到的数值区间进行汇总得到：

用f2(x)拟合训练数据的平方损失误差是：

同上，可以依此类推：

由f6(x)拟合训练数据的平方损失误差是：

若以上求出的误差满足使用过程需要的误差阈值，那么该f6(x)为所求提升树。