集成学习

参考bootstrap, boosting, bagging 几种方法的区别与联系

决策树

好处：（1）特征数据放缩不变性；（2）面对无关特征更鲁棒；（3）得到确定的model。

但是decision tree往往不够准确，因为很容易产生over-fitting：一颗很深的树往往有low bias, high variance；而随机森林Random Forest通过对对多个决策树进行平均，可以显著降低variance来减少过拟合。RF带来的问题是稍稍增加一点bias，以及模型的可解释性，但是获得的收益是显著提高了准确率。

bootstrap

名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，

是一种有放回的抽样方法，它是非参数统计中一种重要的估计统计量方差进而进行区间估计的统计方法。

利用有限的样本资料经由多次重复抽样，重新建立起足以代表母体样本分布之新样本。

bootstrapping方法的实现很简单，假设抽取的样本大小为n:

在原样本中有放回的抽样，抽取n次。每抽一次形成一个新的样本，重复操作，形成很多新样本，通过这些样本就可以计算出样本的一个分布。新样本的数量通常是1000-10000。如果计算成本很小，或者对精度要求比较高，就增加新样本的数量。

bagging

bootstrap aggregating的缩写。具体过程如下：

从样本集中用Bootstrap采样选出n个样本
在所有属性上，对这n个样本建立分类器（CART or SVM or …）
重复以上两步m次，i.e.build m个分类器（CART or SVM or …）
将数据放在这m个分类器上跑，最后vote看到底分到哪一类

boosting

首先给个大致的概念，boosting在选择hyperspace的时候给样本加了一个权值，使得loss function尽量考虑那些分错类的样本（i.e.分错类的样本weight大）。

由于真正的boosting在实际解决问题过程中很难做到，后来就提出了AdaBoost算法，它可以非常容易运用到实际问题中，效率几乎不变。

bagging与boosting

二者的主要区别是取样方式不同。

Bagging采用均匀取样，而Boosting根据错误率来取样，因此Boosting的分类精度要优于Bagging。

Bagging的训练集的选择是随机的，各轮训练集之间相互独立，而Boostlng的各轮训练集的选择与前面各轮的学习结果有关；

Bagging的各个预测函数没有权重，而Boosting是有权重的；

Bagging的各个预测函数可以并行生成，而Boosting的各个预测函数只能顺序生成。对于象神经网络这样极为耗时的学习方法。Bagging可通过并行训练节省大量时间开销。

bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化— Overfit。

random forest

从样本集中用Bootstrap采样选出n个样本，预建立CART
在树的每个节点上，从所有属性中随机选择k个属性，选择出一个最佳分割属性作为节点
重复以上两步m次，i.e.build m棵CART
这m个CART形成Random Forest

random forest与bagging

随机森林与bagging比，它可以既可以处理属性为离散值的量，比如ID3算法，也可以处理属性为连续值的量，比如C4.5算法。

这里的random就是指

Bootstrap中的随机选择子样本
Random subspace的算法从属性集中随机选择k个属性，每个树节点分裂时，从这随机的k个属性，选择最优的

RF与bagging的区别：

Rand forest是选与输入样本的数目相同多的次数（可能一个样本会被选取多次，同时也会造成一些样本不会被选取到），而bagging一般选取比输入样本的数目少的样本；
bagging是用全部特征来得到分类器，而rand forest是需要从全部特征中选取其中的一部分来训练得到分类器；一般Rand forest效果比bagging效果好！

前向分布算法与AdaBoost算法

AdaBoost算法是前向分布加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。

Shrinkage

Shrinkage（缩减）的思想认为，每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，通过多学几棵树弥补不足。

Boosting Tree

提升树，是一种以决策树为基函数的提升方法。

它的基本思想是每次都对前面一棵树学习的残差再次进行学习，而不是与前面的学习过程是独立的，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。

分类问题的过程就是AdaBoost提升方法的过程，回归问题的过程是前向分布加法算法的特例，有以下三种：

回归问题：平方误差损失函数，决策树的类型就是回归树。
分类问题：指数损失函数，决策树的类型就是分类树。
一般决策问题：一般损失函数

以下介绍前两个问题的具体过程：

1.分类问题的提升树：

(1). 初始化权值分布，

$D_1 = {w_{11},w_{12},...,w_{1n}}$

(2).迭代过程

a.根据权值分布 $D_m$ 找到分类误差率最小的切分点，得到基本分类器（这里对应的应该就是回归问题的计算损失函数的部分，分类问题没有用到具体的损失函数，就是根据分类误差率的大小判断）

$G_m(x):X->{-1,+1}$

比如:

$\begin{equation}G_1(X)=\begin{cases}1&x<2.5\\ -1&x>2.5\end{cases}\end{equation}$

b.计算 $G_m$ 分类器的误差率：

$e_m=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\ne y_i)$

c.计算 $G_m(x)$ 的系数:

$\alpha_m=\frac12log\frac{1-e_m}{e_m}$

d.更新权值分布 $D_{m+1}$ ，用于下次迭代的a步，具体的更新公式就不展开了。

(3).最终的分类器：

$G(x) = sign(f(x)) = sign(\sum_{m=1}^{M}\alpha _mG_m(x))$

PS：在(2)的a,b部分，我们使用的是分类误差率作为选择最优特征的标准，其实还有Gini指数、熵这些也可以作为标准，在二分类问题中，基尼指数、熵之半与分类误差率很接近。

2.回归问题的提升树：

我们首先要知道我们接下来的目的是什么，我们知道如果将输入空间划分为 $J$ 个互不相交的区域 $R_1,R_2,..,R_J$ ，并且在每个区域上确定输出的常量 $c_j$ ，那么树可以表示为

$T(x;o_m)=\sum_{j=1}^Jc_jI(x\in R_j)$

我们的目的就是找到这样的划分点和 $c_j$ ，将其划分成若干个不想交的区域。

以下是具体的过程：

(1).初始化 $f_0(x) = 0$

(2).迭代过程，对于 $m=1,2,...,M$

a.计算残差(在m=1时，初始样本数据集就可以当成残差，因此不需要计算)

$r_{mi}=y_i-f_{m-1}(x_i),i=1,2,3,...,N$

b.拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x;o_m)$

对于二分类回归问题，这里的具体过程是：

遍历切分点，根据以下的公式求解最优的切分点(note:注意这里符合我们上述说的目的)
根据上面求得的切分点，将N个残差数据分裂成两个部分 $R1,R2$ ，我们可以根据定义好的损失函数计算出代表 $R_1$ 的输出常量 $c_1$ 和代表 $R_2$ 的输出常量 $c_2$ 来使损失达到最小，一般常用的损失函数为平方损失函数，容易计算得( $N_1,N_2分别是R_1，R_2的个数$ )：
$c_1 = \frac{1}{N_1}\sum_{x_i\in R_1}y_i,c_2 = \frac{1}{N_2}\sum_{x_i\in R_2}y_i$
得到拟合残差的回归树，形如：

$\begin{equation}G_1(X)=\begin{cases}-0.52&x<6.5\\ 0.22&x>6.5\end{cases}\end{equation}$

c.更新 $f_m(x) = f_{m-1}+T(x;o_m)$

(3).最终的分类器：

$f_M(x) = \sum_{m=1}^MT(x;o_m)$

GBDT

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。

GBDT中的每课决策树都是回归树。

那么为什么我们要提出GBDT呢？

与上述的回归问题的提升树比较，当损失函数是平方损失和指数损失函数时，每一步的优化是很简单的。但对一般损失函数而言，往往每一步的优化都不是那么容易。针对这个问题，我们提出了梯度提升(Gradient boosting)算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值作为回归问题提升树算法的中的残差的近似值。

说白了，那我们求导类比，如果我们求二次函数、指数函数的导，会很简单，因为有公式，那么对于一个很复杂的函数求导怎么求呢？只能根据定义， $\mathop{f'}(x)=\frac{\delta y}{\delta x}$ 来求。

具体的过程 ：

(1).根据自定义的损失函数初始化，找到损失最小的

$f_0(x) = \mathop{\arg \min}_ a\sum_{i=1}^{N}L(y_i,c)$

(2).迭代过程，对于 $m=1,2,...,M$

a.计算负梯度(对应于回归问题提升树的残差)

$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)},i=1,2,3,...,N$

b.拟合负梯度 $r_{mi}$ 学习一个回归树，得到每棵树的叶节点区域 $R_{mj},j=1,2,...,J$

c.对 $j=1,2,...,J$ ，计算

$c_{mj}=\mathop{\arg \min}_c \sum_{x_i \in R_{mj}}L(y_i,f_{m-1}(x_i)+c)$

d.更新 $f_m(x) = f_{m-1}+\sum _{j=1}^Jc_{mj}I(X \in R_{mj})$

(3).最终的分类器：

$f_M(x) = \sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(X \in R_{mj})$

PS:(2)的b、c我看不懂啊

b:拟合一个回归树，是按照自己定义的损失函数拟合吗？比如对于提升树的二分类回归问题，类比过来就是根据平方损失函数找到一个切分点和 $c_1,c_2$ 。

c:如何得到c啊，根据自己的损失函数的特性？

回归问题的提升树&GBDT

总的来说两者相同之处在于，都是迭代回归树，都是累加每颗树结果作为最终结果（Multiple Additive Regression Tree)，每棵树都在学习前N-1棵树尚存的不足，从总体流程和输入输出上两者是没有区别的；两者的不同主要在于每步迭代时，是否使用Gradient作为求解方法。前者不用Gradient而是用残差—-残差是全局最优值，Gradient是局部最优方向*步长，即前者每一步都在试图让结果变成最好，后者则每步试图让结果更好一点。

两者优缺点。看起来前者更科学一点–有绝对最优方向不学，为什么舍近求远去估计一个局部最优方向呢？原因在于灵活性。前者最大问题是，由于它依赖残差，cost function一般固定为反映残差的均方差，因此很难处理纯回归问题之外的问题。而后者求解方法为梯度下降，只要可求导的cost function都可以使用，所以用于排序的LambdaMART就是用的后者。

PS:

bagging和boosting都是集成学习的基本算法。

bagging和boosting都是bootstrap的一种应用。

提升树的分类问题应该是AdaBoost的一个特殊情况，

但提升树的回归问题和GBDT应该不是AdaBoost，但他们是Boosting，用的应该是前向分布加法算法。

关于集成学习和集成树的一些总结

决策树

bootstrap

bagging

boosting

bagging与boosting

random forest

random forest与bagging

前向分布算法与AdaBoost算法

Shrinkage

Boosting Tree

GBDT

回归问题的提升树&GBDT

PS:

FEATURED TAGS

FRIENDS