提升树，bagging与随机森林

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

对于分类树只需将adaboost算法中的基函数设置为二分类二叉树即可。

而回归树则是根据残差来训练下一个分类器的回归二叉树。下面主要介绍一下回归提升树的算法。

回归提升树

回忆一下，回归树就是将输入空间分割成 M M $M$个不相关的区域R1,...,RM$R_1,...,R_M$$R_1,...,R_M$,即回归树为 f(x)=∑Mm=1cmI(x∈Rm)=∑Mm=1T(x,θm) f ( x ) = ∑ m = 1 M c m I ( x ∈ R m ) = ∑ m = 1 M T ( x , θ m ) $f(x) = \sum_{m=1}^{M} c_mI(x \in R_m) = \sum_{m=1}^{M}T(x,\theta_m)$

下面我们用前向分步算法推导下回归提升树，有：

f(0)=0 f ( 0 ) = 0 $f(0) = 0$

fm(x)=fm−1(x)+T(x,θm) f m ( x ) = f m − 1 ( x ) + T ( x , θ m ) $f_m(x) = f_{m-1}(x) + T(x,\theta_m)$

则 θmˆ=argminθm∑Ni=1L(yi,fm−1(x)+T(x;θm)) θ m ^ = a r g m i n θ m ∑ i = 1 N L ( y i , f m − 1 ( x ) + T ( x ; θ m ) ) $\widehat{\theta_m} = arg min_{\theta_m} \sum^{N}_{i=1} L(y_i,f_{m-1}(x) +T(x;\theta_m))$

令损失函数为二次损失，则：

L(y,f(x))=(y−f(x))=(y−fm−1(x)−T(x;θm))2=(γ−T(x;θm))2 L ( y , f ( x ) ) = ( y − f ( x ) ) = ( y − f m − 1 ( x ) − T ( x ; θ m ) ) 2 = ( γ − T ( x ; θ m ) ) 2 $L(y,f(x)) = (y-f(x)) = (y - f_{m-1}(x) - T(x;\theta_m))^2 = (\gamma - T(x;\theta_m))^2$

其中 γ=y−fm−1(x) γ = y − f m − 1 ( x ) $\gamma = y - f_{m-1}(x)$， γ γ $\gamma$为残差，拟合当前模型的残差。

回归提升树即用残差来拟合后续的分类器。

输入

训练数据 D={(x1,y1),...,(xN,yN)} D = { ( x 1 , y 1 ) , . . . , ( x N , y N ) } $D = \left \{ (x_1,y_1),...,(x_N,y_N) \right \}$

过程

• 
  
• f(0)=0 f ( 0 ) = 0 $f(0) = 0$
• 对 m=1:M m = 1 : M $m=1:M$
  

• γmi=yi−fm−1(xi) γ m i = y i − f m − 1 ( x i ) $\gamma_{mi} = y_i - f_{m-1}(x_i)$
  
• 利用残差 γ γ $\gamma$拟合回归树 T(x,θm) T ( x , θ m ) $T(x,\theta_m)$
  
• 更新 fm(x)=fm−1(x)+T(x,θm) f m ( x ) = f m − 1 ( x ) + T ( x , θ m ) $f_m(x) = f_{m-1}(x) + T(x,\theta_m)$
• 得到提升树

输出

提升树 fM(x) f M ( x ) $f_M(x)$

梯度提升算法

上面的平方损失函数，利用上面的残差公式 γmi=yi−fm−1(xi) γ m i = y i − f m − 1 ( x i ) $\gamma_{mi} = y_i - f_{m-1}(x_i)$可以很方便的进行优化，如果对于更一般的损失函数而言，上面的残差公式 γmi=yi−fm−1(xi) γ m i = y i − f m − 1 ( x i ) $\gamma_{mi} = y_i - f_{m-1}(x_i)$就不适合了，因此这里引入梯度提升来计算残差

针对梯度提升，上面的算法有两个地方需要修改

一个是初始化：

f(0)=argminc∑Ni=1L(yi,c) f ( 0 ) = a r g m i n c ∑ i = 1 N L ( y i , c ) $f(0) = argmin_c \sum_{i=1}^{N} L(y_i,c)$

一个是残差的计算，利用梯度提升公式计算：

γmi=−[∂L(yi,f(xi))∂f(xi)]f(x)=fm−1(x) γ m i = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) $\gamma_{mi} = -[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x) = f_{m-1}(x)}$

bagging算法

上面的提升树算法我们利用了所有的训练数据，串行的的得到分类器，这种方法效率比较低下，无法并行操作，因此发明了bagging算法，可以并行的进行集成学习。

所谓的bagging算法，就是在训练数据中采样出m个训练样本的采样集，针对每个采样集训练一个基学习器，然后将这些基学习器组合生成最终的学习器。

对于分类任务，可以用简单投票的方式确定结果，对于回归任务，可以用平均值的方式得到最终的结果。

同时每次未被采样的数据还可以作为cross-validation的验证集。

bagging算法简单，并且可以并行，速度很快。由于采样集的样本不一致，因此天然的能够抗过拟合。但是对样本的数目要求一般比较高。

随机森林

树多的地方就是森林，因此随机森林就是以决策树作为基学习器的学习算法。

RF（Random Forest）是在以决策树为基学习器构建bagging的基础上，在决策树的训练过程中引入了随机属性的选择。

RF算法对决策树的每个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后在子集中选择一个最优属性用于划分输入空间（一般大家都选择 k=log2d k = l o g 2 d $k = log_2 d$）。

由于RF算法既随机选择了训练样本集，又随机选择了属性集，因此RF算法中的基学习器的多样性不仅来自于样本的扰动，还来自于属性的扰动，因此有很强的泛化能力。