集成学习方法（组合分类器）

作者: 吴金君 | 来源:发表于2018-08-09 17:34 被阅读0次

1. 引言

典型的集成学习方法有bagging, boosting以及随机森林，stacking也是一种集成学习方法。本文参考《数据挖掘导论》，简单回顾一下几种集成学习方法的要点。

2. 集成学习方法

一般而言，构建组合分类器的方法有以下几种：
（1）基于训练数据集的处理，如bagging和boosting
（2）基于输入特征的处理，如随机森林，以决策树为基分类器。
（3）基于类别号的处理，适用于类别较多的情况，通过将训练集划分成正交的两个子集，分别编码为0和1，然后通过二分法分别迭代两个子集，最后构建成一个组基分类器。通过统计基分类器的投票数来完成分类。如错误-纠正输出编码(error-correcting output coding, ECOC)方法就是这种方法一个例子
（4）基于学习的处理，在同一个训练数据集上多次执行算法可能得到不同的模型，通过多次执行训练生成多个基分类器

算法: 组合方法的一般流程
输入：原始训练集 $D$ ， $k$ 表示基分类器的个数， $T$ 表示检验数据集
输出：组合基分类器 $\{C_1,C_2,...,C_k\}$ 和分类结果
1: for $i$ =1 to $k$ do
2: 由 $D$ 创建训练集 $D_i$
3: 由 $D_i$ 构建基分类器 $C_i$
4:end for
5:for 每一个检验样本 $x\in T$ do
6: $C^*(x)=Vote(C_1,C_2,...,C_k)$
7:end for

2.1 Bagging

装袋(bagging)是一种根据均匀分布从数据集中重复抽样（有放回）的技术。通过有放回的抽样构建出 $k$ 个自助样本集，每个自助样本集与原始训练集一样大。然后分别在 $k$ 个自助样本集上训练出 $k$ 个基分类器，最后对所有检验样本进行投票判决分类，选取票数最多的一类作为预测输出。
(自助样本集中大约包含63%的原始训练数据，因为每一个样本抽到 $D_i$ 中的概率为 $1-(1-1/N)^N$ ，N足够大时这个概率收敛于 $1-1/e\approx 0.632$ .)

算法: 组合方法的一般流程
输入：原始训练集 $D$ ， $k$ 表示基分类器的个数， $T$ 表示检验数据集
输出：组合基分类器 $\{C_1,C_2,...,C_k\}$ 和分类结果
1: for $i$ =1 to $k$ do
2: 由 $D$ 创建训练集 $D_i$
3: 由 $D_i$ 构建基分类器 $C_i$
4:end for
5:for 每一个检验样本 $x\in T$ do
6: $C^*(x)=\arg\max_{y} \sum_i\delta (C_i(x)=y)$ ，其中\delta()为一个布尔函数
7:end for

2.2 Boosting

提升方法中比较典型的几种算法就是Adaboost，Gradient Boost Tree，以及现在非常火热的xgboost。

2.2.1 Adaboost方法

Adaboost通过自适应地改变训练样本的分布，使得基分类器在迭代训练过程中更加关注很难分类的样本。对每一个样本都赋予了一个权值，每一轮迭代结束时都自动地调整样本的权值。为了简洁这里仅给出算法流程，具体细节可以参考李航《统计学习方法》，讲的非常详细。

算法：Adaboost算法
1: $\bold w=\{w_j=1/N\|j=1,2,...,N\}$ //对数据集中所有样本都赋予相同的权重
2:令k表示提升轮次
3: for $i=1$ to $k$ do //开始k个轮次的迭代
4: 根据 $\bold w$ ，通过对 $D$ 进行抽样产生训练集 $D_i$ //产生第i轮迭代中的数据集
5: 在训练集 $D_i$ 上训练分类器 $C_i$ //在第i轮的子集上产生第i轮的基分类器
6: 用分类器 $C_i$ 对数据集 $D$ 进行分类
7: $\epsilon_i=1/N\big[\sum_jw_j\delta(C_i(x_j)\neq y_j )\big]$ ，计算加权误差 //利用当前所有样本所具有的权值来计算误差总和
8: if $\epsilon_i > 0.5$ then //误差大于0.5，相当于比瞎猜还差，所以需要重新初始化权值，重新学习
9: $\bold w=\{w_j=1/N\|j=1,2,...,N\}$
10: 返回步骤4
11: end if
12: $\alpha_i=\frac{1}{2}ln\frac{1-\epsilon_i}{\epsilon_i}$ //如果错误率还可以接受，那么就用错误率去计算一个权重衰减因子
13: 更新每个样本的权值:
当 $C_i(x_j)=y_j$ 时， $w_i^{(k+1)}=\frac{w_i^{(k)}}{Z}e^{-\alpha_j}$ ; //预测正确时减小样本权值
当 $C_i(x_j)=y_j$ 时， $w_i^{(k+1)}=\frac{w_i^{(k)}}{Z}e^{-\alpha_j}$ ; //预测错误时加大样本权值
14:end for
15: $C^(\bold x)=\text{argmax}_y \sum_{j=1}^{T}\alpha_j\delta(C_j(x)=y_j)$ //利用集成的分类器对所有样本进行分类*

在上述算法中，通过k个轮次的学习，实际上得到了k个基分类器，我们构建这些基分类器的线性组合就得到了最终的分类器。
$C^*(x)=sign(\sum_{i=1}^{k}\alpha_iC_i(x))$

2.2.2 GBDT方法

关于Gradient Boost Decision Tree，个人感觉更像是一种策略，利用上一轮的残差来继续学习。李航《统计学习方法》中先讲了提升树，然后讲了梯度提升，两者之间的差别就在于残差的表示：
提升树中的残差： $r_{mi}=y_i-f_{m-1}(x_i)$
梯度提升的残差： $r_{mi}=-\big[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\big]_{f(x)=f_{m-1}(x)}$

提升树的基本思想

提升树实际上也可以看作多个树的线性组合，通过多个轮次的提升得到最后的提升树。
用 $f_k(x)$ 表示第k步得到的提升树；假设总共迭代了K个轮次，则有最终得到的决策树为 $f_K(x)$ ：
$\begin{aligned} f_0(x)&=0\\ f_1(x)&=f_0(x)+T(x;\theta_1)\\ ......\\ f_k(x)&=f_{k-1}(x)+T(x;\theta_k)\\ ......\\ f_K(x)&=\sum_{k=1}^{K}T(x;\theta_k) \end{aligned}$
上面式子中每次需要拟合得到的树 $T(x;\theta_k)$ 都有一个参数需要确定，通过优化这个参数，我们才可以得到更理想的树。我们假设需要通过这个参数 $\theta$ 来确定损失函数,定义损失函数可以使问题更加一般化，变成一个算法框架（陈天奇大佬说的，我也觉得挺有道理，定量分析优化好像比启发式的学习更有理论上的说服力），于是我们先抽象出一个损失函数:
$\text{Loss function: } L\Big(y_i,f_{k-1}(x_i)+T(x_i;\theta_k)\Big)$
然后通过 $\theta$ 来优化它，这貌似也是机器学习里优化模型惯用的套路。
$\hat{\theta}_k=\arg \min_{\theta_k}\sum_{i=1}^{N}L\Big(y_i,f_{k-1}(x_i)+T(x_i;\theta_k)\Big)$
这里损失函数具体是什么还没有明确下来，《统计学习方法》中以平方误差作为了损失函数举例，后面会给出推导。但我们先顺着思路来继续看看提升树基本思想的最后一步——求残差。
$r=y-f_{k-1}(x)$
利用这个残差就可以进行下一棵树的学习了。写到这里我也有点懵逼，树是怎么学习的呢？ok，这里讲的是提升方法，先把树是怎么学习的这个问题放在一边，它是另外一个问题，不要让他打搅我们的思路，暂且默认你知道树是怎么学习得来的。因此，这里总结一下提升方法的算法流程

提升树算法
输入：训练集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$
输出：提升树 $f_K(x)$
1:初始化 $f_0(x)$
2:for $k=1,2,...,K$ do
3: 计算残差 $r_{ki}=y_i-f_{k-1}(x_i)$
4: 拟合残差 $r_{ki}$ 学习回归树，得到 $T(x;\theta_k)$
5: 更新树 $f_k(x)=f_{k-1}(x)+T(x,\theta_k)$
6:end for
7:得到提升树 $f_K(x)=\sum_{k=1}^{K}T(x,\theta_k)$

平方误差损失函数
上面提到了平方误差损失函数，这里给出式子：
$L(y,f(x))=(y-f(x))^2$
再将 $L\Big(y_i,f_{k-1}(x_i)+T(x;\theta_k)\Big)$ 代入后可以得到：
$\begin{aligned} &L\Big(y_i,f_{k-1}(x_i)+T(x;\theta_k)\Big)\\ &=\Big[y_i-f_{k-1}(x_i)-T(x;\theta_k)\Big]^2\\ &=[r-T(x;\theta_k)]^2 \end{aligned}$
再次强调，这里的残差就是实际值和预测值之间的差值：
$r_{ki}=y_i-f_{k-1}(x_i)$

梯度提升方法中的残差

通过上面的描述，我们抽象出了一个损失函数，当损失函数是平方损失函数或者指数损失函数时，优化是比较容易的。但是对于更加一般化的损失函数来说优化并不容易，因此引入了梯度的概念，目的就是为了减少上一步中的残差，利用负梯度对模型进行优化。梯度提升树中的残差就定义为了负梯度。
负梯度：
$r_{mi}=-\big[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\big]_{f(x)=f_{m-1}(x)}$
给出梯度提升树的算法流程

梯度提升树算法
输入：训练集 $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$
输出：提升树 $f_K(x)$
1:初始化 $f_0(x)$
2:for $k=1,2,...,K$ do
3: 计算残差 $r_{mi}=-\big[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}\big]_{f(x)=f_{m-1}(x)}$
4: 拟合残差 $r_{ki}$ 学习回归树，得到 $T(x;\theta_k)$
5: 更新树 $f_k(x)=f_{k-1}(x)+T(x,\theta_k)$
6:end for
7:得到梯度提升树 $f_K(x)=\sum_{k=1}^{K}T(x,\theta_k)$

xgboost方法

GBDT和xgboost的区别

转载一下知乎上的一个回答
作者：黄真川
链接：https://www.zhihu.com/question/41354392/answer/91371364
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

首先xgboost是Gradient Boosting的一种高效系统实现，并不是一种单一算法。xgboost里面的基学习器除了用tree(gbtree)，也可用线性分类器(gblinear)。而GBDT则特指梯度提升决策树算法。
xgboost相对于普通gbm的实现，可能具有以下的一些优势：

显式地将树模型的复杂度作为正则项加在优化目标
公式推导里用到了二阶导数信息，而普通的GBDT只用到一阶
允许使用column(feature) sampling来防止过拟合，借鉴了Random Forest的思想，sklearn里的gbm好像也有类似实现。

4.实现了一种分裂节点寻找的近似算法，用于加速和减小内存消耗。
5.节点分裂算法能自动利用特征的稀疏性。
6.data事先排好序并以block的形式存储，利于并行计算
7.cache-aware, out-of-core computation，这个我不太懂。。
8.支持分布式计算可以运行在MPI，YARN上，得益于底层支持容错的分布式通信框架rabit。

参考资料：
chentq的slides http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
chentq的paper http://arxiv.org/abs/1603.02754
chentq在52cs上的中文博文 http://www.52cs.org/?p=429
微博上分享的xgboost导读和实战.pdf

参考这些大佬：
https://blog.csdn.net/niuniuyuh/article/details/76922210
http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/random-forest-and-gbdt.html
https://blog.csdn.net/lc013/article/details/56667157
https://www.zhihu.com/question/41354392
另外极力推荐这个大佬的主页 http://wepon.me/
https://blog.csdn.net/sb19931201/article/details/52557382讲xgboost挺不错的

集成学习方法（组合分类器）

1. 引言

2. 集成学习方法

2.1 Bagging

2.2 Boosting

2.2.1 Adaboost方法

2.2.2 GBDT方法

提升树的基本思想

梯度提升方法中的残差

xgboost方法

GBDT和xgboost的区别

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

我爱编程