机器学习算法之集成算法

集成学习

1. 概述

集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务。其一般结构为：先产生一组“个体学习器”（individual learner），再用某种策略将它们结合起来。个体学习器通常由一个现有的学习算法从训练数据产生。
若集成中只包含同种类型的个体学习器，称为同质集成（homogeneous ensemble），个体学习器亦称“基学习器”（base learner）；若集成中包含不同类型的个体学习器，则称为异质集成（heterogenous ensemble），个体学习器常称为“组件学习器”（component learner）。
集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能，这对“弱学习器”（weak learner）尤为明显，因此集成学习很多理论都是针对若学习器进行的，但实践中常常选择较强的学习器。
要获得好的集成效果，个体学习器应“好而不同”，即同时具备“准确性”和“多样性”，事实上这两者本身存在冲突。于是，集成学习研究的核心，如何产生并结合“好而不同”的个体学习器。
目前集成学习的方法可分为：Boosting、Bagging、Stacking和Blending。

2. Boosting

工作机制：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至达到终止条件，最后将得到的 $T$ 个基学习器进行加权结合。
从中可知，对提升方法来说，有两个问题需要回答：

在每一轮如何改变训练数据的权值或概率分布
如何将弱分类器组合成一个强分类器

2.1 AdaBoost

针对上述问题，AdaBoost的做法是：

提高那些被前一轮弱分类器错误分类样本的权值，使其在后续分类中受到更大关注
关于弱分类器的组合，采用加权多数表决的方法。即加大分类误差率小的弱分类器的权值。

2.1.1. AdaBoost算法流程：

输入：训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N) \}$ ，其中 $x_i \in \chi \supseteq R^n$ ， $y_i \in \gamma = \{ -1, +1 \}$ ; 弱学习算法；
输出：最终分类器 $G(x)$

初始化训练数据的权值分布
$D_1 = (\omega_{11}, \cdots, \omega_{1i}, \cdots, \omega_{1N}), \omega_{1i} = \frac {1} {N}, i = 1, 2, \cdots, N$
对 $m = 1, 2, \cdots, M$
a. 使用具有权值分布 $D_m$ 的训练数据集学习，得到基本学习器
$G_m (x): \chi \rightarrow \{ -1, +1 \}$ b. 计算 $G_m (x)$ 在训练数据集上的分类误差率
$e_m = P(G_m (x_i) \neq y_i) = \sum_{i=1}^N \omega_{mi} I(G_m(x_i) \neq y_i)$ c. 计算 $G_m (x)$ 的系数
$\alpha_m = \frac {1} {2} \log \frac {1 - e_m} {e_m}$ 其中的对数是自然对数
d. 更新训练数据集的权值分布
$D_{m+1} = (\omega_{m+1,1}, \cdots, \omega_{m+1, i}, \cdots, \omega_{m+1, N})$
$\omega_{m+1, i} = \frac {\omega_{mi}} {Z_m} \exp (- \alpha_m y_i G_m (x_i)), \quad i = 1, 2, \cdots, N$ 其中， $Z_m$ 是规范化因子
$Z_m = \sum_{i=1}^N \omega_{mi} \exp (- \alpha_m y_i G_m(x_i))$ 它使 $D_{m+1}$ 成为一个概率分布
构建基本分类器的线性组合
$f(x) = \sum_{i=1}^M \alpha_m G_m(x)$ 得到最终分类器
$G(x) = sign(f(x)) = sign(\sum_{m=1}^M \alpha_m G_m(x))$

2.1.2. 加法模型

加法模型(additive model)：
$f(x) = \sum_{m=1}^M \beta_m b(x; \gamma_m)$ 其中， $b(x; \gamma_m)$ 为基函数， $\gamma_m$ 为基函数的参数， $\beta_m$ 为基函数的系数

2.1.3. 前向分步算法

输入：训练数据 $T = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N) \}$ ；损失函数 $L(y, f(x))$ ；基函数集 $\{ b(x;\gamma) \}$ ；
输出：加法模型 $f(x)$

初始化 $f_0(x) = 0$
对 $m = 1, 2, \cdots, M$
极小化损失函数
$(\beta_m, \gamma_m) = \mathop{\arg \min} \limits_{\beta, \gamma} \sum_{i=1}^N L(y_i, f_{m-1} (x_i) + \beta b(x_i; \gamma))$ 得到参数 $\beta_m, \gamma_m$
得到加法模型
$f(x) = f_M(x) = \sum_{m=1}^M \beta_m b(x; \gamma_m)$ 这样，前向分步算法将同时求解从 $m=1$ 到 $M$ 所有参数 $\beta_m, \gamma_m$ 的优化问题简化为逐次求解各个 $\beta_m, \gamma_m$ 的优化问题。

2.2 GBDT（Gradient Boosting Decision Tree）

提升树（boosting tree）是以分类树或回归树为基本分类器的提升方法，被认为是统计学习中性能最好的方法之一。
提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型：
$f_M (x) = \sum_{m=1}^M T(x; \Theta_m)$ 其中， $T(x; \Theta_m)$ 表示决策树； $\Theta_m$ 为决策树的参数； $M$ 为树的个数

2.2.1. 提升树算法

提升树算法采用前向分步算法。首先确定初始提升树 $f_0(x) = 0$ ，第 $m$ 步的模型是
$f_m(x) = f_{m-1}(x) + T(x; \Theta_m)$ 其中， $f_m(x)$ 为当前模型，通过经验风险极小化确定下一棵决策树的参数 $\Theta_m$
$\hat{\Theta}_m = \mathop {\arg \min} \limits_{\Theta_m} \sum_{i=1}^N L(y_i, f_{m-1} (x_i) + T(x_i; \Theta_m))$ 输入：训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N) \}$ ， $x_i \in \chi \subseteq R^n$ ， $y_i \in \gamma \subseteq R$ ；
输出：提升树 $f_M (x)$

初始化 $f_0(x) = 0$
对 $m = 1, 2, \cdots, M$
a. 计算残差
$r_{mi} = y_i - f_{m-1} (x_i), \quad i=1, 2, \cdots, N$ b. 拟合残差 $r_{mi}$ 学习一个回归树，得到 $T(x; \Theta_m)$
c. 更新 $f_m(x) = f_{m-1} (x) + T(x; \Theta_m)$
得到回归问题提升树
$f_M(x) = \sum_{m=1}^M T(x; \Theta_m)$

2.2.2. 梯度提升算法流程

提升树利用加法模型和前向分步算法实现学习的优化过程。当损失函数为平方损失或指数损失时，每一步很简单。但对于一般损失函数，每一步优化并不容易。梯度提升算法利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值
$- [\frac {\partial L(y_i, f(x_i))} {\partial f(x_i)}]_{f(x) = f_{m-1}(x)}$ 作为回归问题提升树算法中的残差的近似值，拟合一个回归树。
输入：训练数据集 $T = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N) \}$ ， $x_i \in \chi \subseteq R^n$ ， $y_i \in \gamma \subseteq R$ ；损失函数 $L(y, f(x))$ ；
输出：回归树 $\hat{f} (x)$

初始化
$f_0(x) = \mathop {\arg\min} \limits_{c} \sum_{i=1}^N L(y_i, c)$
对 $m = 1, 2, \cdots, M$
a. 对 $i = 1, 2, \cdots, N$ ，计算
$r_{mi} = - [\frac {\partial L(y_i, f(x_i))} {\partial f(x_i)}]_{f(x) = f_{m-1}(x)}$ b. 对 $r_{mi}$ 拟合一个回归树，得到第 $m$ 棵树的叶结点区域 $R_{my}, j = 1, 2, \cdots, J$
c. 对 $j = 1, 2, \cdots, J$ ，计算
$c_{mj} = \mathop {\arg \min} \limits_{c} \sum_{x_i \in R_{mj}} L(y_i, f_{m-1}(x_i) + c)$
更新 $f_m(x) = f_{m-1}(x) + \sum_{j=1}^J c_{mj} I(x \in R_{mj})$
得到回归树
$\hat{f} (x) = f_M (x) = \sum_{m=1}^M \sum_{j=1}^J c_{mj} I(x \in R_{mj})$

2.3 XGBoost

XGBoost（eXtreme Gradient Boosting ）是基于GBDT改进的集成学习算法，主要特征是支持损失函数的二阶导数，并加入正则项控制模型复杂度。
已知数据集 $D = \{ x_i, y_i \}$ ，其中 $\mid D \mid = n, x_i \in R^m, y_i \in R$ ，则 $K$ 棵树的预测 $\hat{y}_i$ 为
$\hat{y}_i = \sum_{k=1}^K f_k (x_i)， f_k \in F$ 其中 $F = \{ f(x) = \omega_{q(x)} \}, q: R^m \rightarrow T, \omega \in R^T$ 是决策树的集合； $q$ 是每棵树的结构； $\omega$ 为叶子权重； $T$ 为叶子节点的个数。
在损失函数中添加正则项，得到目标函数为：
$L^{(t)} = \sum_{i=1}^n l(y_i, \hat{y}_i) + \sum_{k=1}^K \Omega (f_k)$ 其中 $l$ 是可微的损失函数，表示预测值 $\hat{y}_i$ 和真实值 $y_i$ 的差值； $\Omega$ 为正则化项，可避免过拟合，其表达式为
$\Omega (f) = \gamma T + \frac {1} {2} \lambda \parallel \omega \parallel ^ 2$ 其中 $\gamma$ 为复杂度参数， $\lambda$ 为正则化系数，两者通常根据经验给出。
对 $L^{(t)}$ 进行泰勒展开
$L^{(t)} = \sum_{i=1}^n l(y_i, \hat{y}_i + f_t (x_i)) + \sum_{k=1}^K \Omega (f_k) \approx \sum_{i=1}^n l[(y_i, \hat{y}_i^{(t-1)}) + g_i f_t (x_i) + \frac {1} {2} h_i f_t^2 (x_i)] + \sum_{k=1}^K \Omega (f_k)$ 其中 $g_i = \partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)}), h_i = \partial_{\hat{y}_i^{(t-1)}}^2 l(y_i, \hat{y}_i^{(t-1)})$ 分别是损失函数对于 $y_i^{(t-1)}$ 的一阶导数和二阶导数。
针对二元分类问题，采用对数损失函数，去除常数项后化简可得最终的目标函数
$\tilde{L}^{(t)} = \sum_{i=1}^n [g_i f_t(x_i) + \frac {1} {2} h_i f_t^2 (x_i)] + \sum_{k=1}^K \Omega (f_k)$

3. Bagging

Bagging算法流程：
输入：训练集 $D = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m) \}$ ；
基学习算法 $\chi$ ；
训练轮数 $T$

for $t = 1, 2, \cdots, T$ do
$\quad h_t = \chi (D, D_{bs})$
end for

输出：
$H(x) = \mathop{\arg \max} \limits_{y \in \gamma} \sum_{t=1}^T I(h_t(x) = y)$

3.1 随机森林

随机森林（Random Forest）的核心思路：对训练集进行重采样，组成多个训练子集，每个子集生成一个决策树，所有决策树通过投票的方式进行决策，组成随机森林。

输入：训练集 $T = \{ t_1, t_2, \cdots, t_N \}$ ；特征集 $F = \{ f_1, f_2, \cdots, f_M \}$ ；类别集合 $C = \{ c_1, c_2, \cdots, c_L \}$ ；测试样本集 $D = \{ d_1, d_2, \cdots, d_\lambda \}$ 。
输出： $S(x)$

从容量为 $N$ 的训练集 $T$ 中，采用自助抽样法（bootstrap），即有放回地抽取 $N$ 个样本，作为一个训练子集 $T_k$ ；
对于训练子集 $T_k$ ，从特征集 $F$ 中无放回地随机抽取 $m$ 个特征，其中 $m = \log_2 {M}$ （向上取整），作为决策树上的每个结点分裂的依据。从根结点开始，自下而上生成一个完整的决策树 $S_k$ ，不需要剪枝；
重复 $n$ 次步骤1和2，得到 $n$ 个训练子集 $T_1, T_2, \cdots, T_n$ ，并生成决策树 $S_1, S_2, \cdots, S_n$ ，将n个决策树利用简单投票法组合起来形成随机森林；
$S(x) = \mathop{\arg \max} \limits_{c \in C} \sum_{t=1}^n I(S_t(x) = c)$
将测试集 $D$ 的样本 $d_\mu$ 输入随机森林中，让每个决策树对 $d_\mu$ 进行决策，然后采用多数投票发（Majority Voting Algorithm）对决策结果投票，最终决定 $d_\mu$ 的类别；
重复 $\lambda$ 次步骤4，直到测试集 $D$ 分类完成

4. Stacking

stacking算法流程：
输入：训练集 $D = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m) \}$ ;
初级学习算法 $\chi_1, \chi_2, \cdots, \chi_T$
次级学习算法 $\chi$

for $t = 1, 2, \cdots, T$ do
$\quad h_t = \chi_t (D)$
end for
$D^{'} = \varnothing$
for $i = 1, 2, \cdots, m$ do
for $t = 1, 2, \cdots, T$ do
$z_{it} = h_t(x_i)$ ;
end for
$D^{'} = D^{'} \cup ((z_{i1}, z_{i2}, \cdots, z_{iT}), y_i)$ ;
end for
$h^{'} = \chi(D^{'})$

输出： $H(x) = h^{'} (h_1(x), h_2(x), \cdots, h_T(x))$

5. Blending

Blending主要流程：

将原始训练数据集划分为训练集和验证集；
使用训练集训练 $T$ 个不同的基模型，同质异质皆可以；
使用生成的 $T$ 个基模型，对验证集进行预测，结果作为新的训练数据；
使用新的训练数据，训练一个元模型；
使用 $T$ 个基模型，对训练数据进行预测，结果作为新的测试数据；
使用原模型对新的测试数据进行预测，得到最终结果。

Blending优点：

比Stacking简单（不用进行 $k$ 次交叉验证来获得新特征）
由于两层训练使用的数据不同，避免了信息泄露问题
在团队建模过程中，不需要给队友分享自己的随机种子

Blending缺点：

由于Blending对数据集的划分形式，第二轮的数据量比较少，可能导致过拟合
Stacking使用多次的CV会比较稳健

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