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

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挺不错的

最后编辑于：2018.08.26 21:06:21

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 205,236评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,867评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,715评论 0赞 340
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,899评论 1赞 278
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,895评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,733评论 1赞 283
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,085评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,722评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,025评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,696评论 2赞 323
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,816评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,447评论 4赞 322
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,057评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,009评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,254评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,204评论 2赞 352
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,561评论 2赞 343