adaboost

提升树

• boosting=加法模型与前向分步算法
• 提升树：以决策树为基函数提升方法
• 分类问题：二叉分类树
• 回归问题：二叉回归树

1. 提升树算法基础

• 提升树模型：决策树的加法模型

$f_M(x)=\sum\limits_{m=1}^MT(x;\Theta_M)$

其中：

$T(x;\Theta_M)$是决策树；$\Theta_M$是决策树的个数；

M是树的个数；

* 基本定义

• 设初始提升树$f_0(x)=0$,第m步的模型;

$f_m(x)=f_{m-1}(x)+T(x;\Theta_M)$

其中：

$f_{m-1}(x)是当前模型；如下公式确定参数$

$\hat{\Theta}_M=arg\min\limits_{\Theta_M}\sum\limits_{i=1}^N L(y-i,f_{m-1}(x_i)+T(x_i;\Theta_M))$

* 算法解释

• 针对不同问题的提升树算法，主要区别是损失函数的不同：平方误差的回归问题；指数损失的分类问题；一般损失的决策问题；

* 分类

• 将adaboost的基本分类器限制为二分类器（基函数限制）；例如：逻辑回归等；

2. 回归问题的提升树算法

• 数据集：二分类数据集

$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$;

• x是实例空间；y是标记集合

• 将输入空间$\chi$划分为J个互不相交的区域$R_1,...,R_J$;并且在每个区域确定输出常量 $c_j$;那么树可以表示：

$T(x;\Theta)=\sum\limits_{j=1}^Jc_jI(x\in R_j)$

其中：参数$\Theta=\{(R_1,c_1),...,(R_J,c_J)\}$,表示树的区域的划分和各区域上的常数，J是回归树的复杂度；即叶的节点数

* 回归树提升使用如下的分步算法：

其中;$r=y-f_{m-1}(x)$：是当前模型拟合数据的残差

• 对于回归问题的提升树，只要简单的拟合当前模型的残差

* 算法流程