集成学习

About

个人同时在简书和自制个人博客两个地方同时更新文章，有兴趣的话可以来我的博客玩呀，一般而言排版会好不少。本篇在博客的位置。

集成学习一句话版本

集成学习的思想是将若干个学习器（分类器&回归器）组合之后产生新的学习器。
在学习这一章节中，老师提到了这个说法，我觉得非常言简意赅就直接引用了过来。集成学习算法的成功在于保证若分类器（错误率略小于0.5，即勉强比瞎猜好一点）的多样性，且集成不稳定的算法也能得到一种比较明显的提升。
注：深度学习其实也可以看作是一种集成学习

集成学习的作用

采用集成学习的原因有以下四点：

分类器间存在一定的差异性，这会导致分类的边界不同，也就是说分类器是一个比较专精的专家，它有它自己一定的适用范围和特长。那么通过一定的策略将多个弱分类器合并后，就可以拓展模型的适用范围，减少整体的错误率，实现更好的效果。
注：不严谨的类比的话，就像弹性网络模型就可以看作是由LASSO回归和Ridge回归组成的集成学习。
对于数据集过大或者过小，过大会导致训练一个模型太慢，过小则会导致训练不充分，在这种情况下可以分别对数据集进行划分和有放回的操作产生不同的数据子集，然后使用数据子集训练不同的分类器，最终再将不同的分类器合并成为一个大的分类器。
注：这种方案的优势就在于，提高了准确度和训练速度，使得之前很难利用的数据得到了充分的利用
如果数据的划分边界过于复杂，使用线性模型很难描述情况，那么可以训练多个模型，然后再进行模型的融合。
注：这种特性就好比当初素描老师教我们画圆一样，画一个正方形，再用一堆小直线一点一点切成圆形。
对于多个异构的特征集的时候，很难进行融合，那么可以考虑每个数据集构建一个分类模型，然后将多个模型融合。
注：简单的来说就是公司有两个人都很厉害，但是偏偏不凑巧两个人打架，就不能把他们放一个部门里，得放不同部门一样。

集成学习的三种思想

Bagging

Bagging算法思想

Bagging，这个名字就是从袋子里取的意思，本身便很形象的说明了这个算法的核心思想，即在原始数据集上通过有放回的抽样的方式，重新选择出S个新数据集来分别训练S个分类器，随后在预测的时候采用多数投票或者求均值的方式来判断预测结果。

Bagging适用弱学习器的范围

基本的弱学习器都能用，如Linear、Ridge、Lasso、 Logistic、Softmax、ID3、C4.5、CART、SVM、KNN。

Boosting

Boosting算法思想

提升学习（Boosting），这个名字也很形象，在赛车游戏中氮气加速有时候界面就描述是boost，也就是越加越快，每次都比上一次更快，也就是说同Bagging是不一样的，Boosting是会根据其他的弱分类器的结果来更改数据集再喂给下一个弱分类器。准确的描述为，Boosting算法每一步产生弱预测模型(如决策树)，并加权累加到总模型中。

它的意义在于如果一个问题存在弱预测模型，那么可以通过提升技术的办法得到一个强预测模型。
注1: 如果每一步的弱预测模型的生成都是依据损失函数的梯度方式的，那么就称为梯度提升(Gradient boosting)
注2：Boosting这个集成学习的思想就有点深度网络的意思了。

Boosting适用范围

提升学习适用于回归和分类的问题。

Stacking

之前提到了Bagging是把训练集拆成不同的子集训练多个学习器投票，而Boosting是根据学习器学习的结果来改动数据集，经过多层改动后试图获得一个更好的预测效果。Bagging和Boosting这两个集成学习其实并没有通过训练结果来改变弱分类器的参数。相对比而言，Stacking就激进许多，当然也复杂和困难许多，它首先训练出多个不同的模型，然后再以之前训练的各个模型的输出作为输入来新训练一个新的模型，换句话说，Stacking算法根据模型的输出是允许改其他分类器的参数甚至结构的，也正是因为这点sklearn中很少有stacking的内置的算法。

1、Bagging算法

随机森林(Random Forest)

随机森林的思路很简单如下：

从样本集中用Bootstrap采样选出n个样本;
从所有属性中随机选择K个属性，选择出最佳分割属性作为节点创建决策树
重复以上两步m次，即建立m棵决策树
这m个决策树形成随机森林，通过投票表决结果决定数据属于那一类
注：RF算法在实际应用中具有比较好的特性，应用也比较广泛，主要应用在分类、回归、特征转换、异常点检测等。

RF算法分析
RF的主要优点：

训练可以并行化，对于大规模样本的训练具有速度的优势。
由于进行随机选择决策树划分特征列表，这样在样本维度比较高的时候，仍然具有比较高的训练性能。
给以给出各个特征的重要性列表。
由于存在随机抽样，训练出来的模型方差小，泛化能力强;。
RF实现简单。
对于部分特征的缺失不敏感。
RF的主要缺点：
在某些噪音比较大的特征上，RF模型容易陷入过拟合。
取值比较多的划分特征对RF的决策会产生更大的影响，从而有可能影响模型的效果。

RF的变种

Extra Tree

Extra Tree是RF的一个相当激进的变种，原理基本和RF一样，区别如下:

RF会随机采样来作为子决策树的训练集，而Extra Tree每个子决策树采用原始数据集训练;
RF在选择划分特征点的时候会和传统决策树一样，会基于信息增益、信息增益率、基尼系数、均方差等原则来选择最优特征值。而Extra Tree会随机的选择一个特征值来划分决策树。
Extra Tree因为是随机选择特征值的划分点，这样会导致决策树的规模一般大于RF所生成的决策树。也就是说Extra Tree模型的方差相对于RF进一步减少。在某些情况下，Extra Tree的泛化能力比RF的强。

Totally Random Trees Embedding

TRTE算法主要进行了两部分操作，第一部分是对数据进行操作，第二部分是对生成的决策树的位置信息转换成向量信息以供之后构建特征编码使用。抛开数据集上的操作，TRTE算法对RF的变种在于如何参考最终生成的多个决策树来给出预测结果。
RF是采用投票的方式，而TRTE算法中，每个决策树会生成一个编码来对应叶子结点的位置信息，那么把所有的决策树对应相同的分类的编码合并起来，就可以用这一合并后的编码来代表它的特征了，预测时待预测样本经过这些决策树的预测也会得到这样一个合并后的编码，通过同训练好的类别的编码之间的差距的大小来预测这个样本应该属于哪一个类别。

详细的说明说下：

TRTE是一种非监督的数据转化方式。将低维的数据集映射到高维，从而让映射到高维的数据更好的应用于分类回归模型。
TRTE算法的转换过程类似RF算法的方法，建立T个决策树来拟合数据。当决策树构建完成后，数据集里的每个数据在T个决策树中叶子节点的位置就定下来了，将位置信息转换为向量就完成了特征转换操作，这个转换过程有点像霍夫曼编码的过程。

Isolation Forest

这个算法是用来异常点检测的，正如isolation这个名字，是找出非正常的点，而这些非正常的点显然是特征比较明确的，故不需要太多的数据，也不需要太大规模的决策树。
它和RF算法有以下几个差别：

在随机采样的过程中，一般只需要少量数据即可。
在进行决策树构建过程中，IForest算法会随机选择一个划分特征，并对划分特征随机选择一个划分阈值。
IForest算法构建的决策树一般深度max_depth是比较小的。

算法思路如下：
对于异常点的判断，则是将测试样本x拟合到T棵决策树上。计算在每棵树上该样本的叶子节点的深度 $h_t(x)$ 。从而计算出平均深度 $h(x)$ 。然后就可以使用下列公式计算样本点x的异常概率值， $p(x,m)$ 的取值范围为 $[0,1]$ ，越接近于1，则是异常点的概率越大。
$p(x,m) = 2^{-\frac{h(x)}{c(m)}}$
$c(m) = 2\ln(m-1)+\xi - 2\frac{m-1}{m}\ \ \ \ m为样本个数，\xi为欧拉常数$
注：这个公式可以简单的理解为越是出现在越深的层数，这个事件越不可能发生，足够深的情况基本上就可以判断为不可能发生是异常点

2、Boosting算法

Adaboost

总览

Adaboost全名为Adaptive Boosting，每轮迭代中会在训练集上产生一个新的学习器，然后使用该学习器对所有样本进行预测，以评估每个样本的重要性 (Informative)。换句话来讲就是，算法会为每个样本赋予一个权重，每次用训练好的学习器标注/预测各个样本，如果某个样本点被预测的越正确，则将其权重降低，否则提高样本的权重。权重越高的样本在下一个迭代训练中所占的比重就越大，也就是说越难区分的样本在训练过程中会变得越重要。
整个算法的迭代的结束条件就是错误率足够小或者达到一定的迭代次数为止。
注：整体的过程很像，分豆子，先把我们直接能看出来的区别的豆子分开，留下不太能区分开来的豆子，然后交给母上大人帮忙再分这种感觉。

细节描述

首先再重新强调下，从线性回归开始的两种思想，第一种是，设计出一个损失函数来代表预测结果，之后根据其应该为极小值和凸函数的特性，求原公式中的参数，一般是用导数等于0这种方式。第二种思想则是，当有多个变量共同作用结果的时候，我们给每个变量前加参数，也就是权值来控制变量的影响结果的能力。
这两种贯穿了几乎所有机器学习的思想，当然在Adaboost中也不会例外，整体的步骤分两部分：

每次迭代都为新的弱学习器加权重，并根据损失函数计算得到这个权重。
根据这个新的学习器的预测结果，对每个样本特征的权重进行调整。

算法构建之权重系数

假设我们打算用的最终分类器为 $G(x)$ ，第m次迭代用的弱分类器为 $G_m(x)$ ，并给分类器前加权重 $\alpha_m$ 已保证分类准的分类器得到足够的重视。于是得到下面公式3.1，公式3.2。
$f(x) = \sum_{m=1}^M \alpha_m G_m(x)\ \ \ 公式3.1$
$G(x) = sign(f(x)) = sign[\sum_{m=1}^M \alpha_m G_m(x)]\ \ \ 公式3.2$
有了一个对算法整体的数学表达以后，我们就可以根据它写出AdaBoost的损失函数如下公式3.3：
注：到现在为止大家应该对 $e^{(-y_i f(x))}$ 这种公式的函数图不陌生了，就不赘述了
$loss = \frac{1}{n}\sum_{i=1}^n I(G(x_i) \neq y_i) \leq \frac{1}{n}\sum_{i=1}^n e^{(-y_i f(x_i))}\ \ \ 公式3.3$
有了损失函数了，那么 $\alpha$ 在哪里呢，是要像SVM一样找个算法一起求么，显然不是了，如果那样子的话估计就不是集成算法了，它是一步一步求的，它只关心当前最好结果，类比算法中的贪心算法。于是，我们讨论第k-1轮和第k论迭代的关系：
$f_{k-1}(x) = \ sum_{j=1}^{k-1}\alpha_j G_j(x) \ \ \ 第k-1轮的函数$
$f_k(x) = \sum_{j=1}^k \alpha_j G_j(x) = f_{k-1}(x) + \alpha_k G_k(x) \ \ \ 第k轮函数$
根据loss函数的构成方法，我们很容易写出第k轮含有 $\alpha_k$ 的公式如下公式3.4，之后对其进行求导就可以得到 $\alpha_k$ 的公式3.5：
$loss(\alpha_k,G_k(x)) = \frac{1}{n} \sum_{i=1}^n e^{(-y_i(f_{m-1}(x)+\alpha_k G_k(x)))} \ \ \ 公式3.4$
$\begin{split} &\alpha_k^* = \frac{1}{x}\ln(\frac{1-\varepsilon_k}{\varepsilon_k})\ \ \ 公式3.5 \\ &\overline w_{ki} = e^{(-y_i f_{k-1}(x))} \\ &\varepsilon_k = \frac{1}{n}\sum_{i=1}^n \overline w_{ki}I(y_i \neq G_m(x_i)) \end{split}$
于是至此，我们就将弱分类器简单的连接在一起了，做好了下一步对数据样本特征值的权重调整的准备。

算法构建之样本特征权重调整

首先我们设定第k轮的数据集的权重分布为 $D_k = (w_{k,1}, w_{k,2},... ,w_{k,n},)$ 。同时每次的 $D_k$ 都是由 $D_{k-1}$ 通过某种规律计算得到的，这种计算公式如下公式3.6：
$\begin{split} &w_k = \frac{w_{k-1,i}}{Z_{k-1}}e^{-\alpha_{k-1}y_i G_{k-1}(x_i)}\ \ \ 公式3.6 \\ &Z_k = \sum_{i=1}^n w_{k,i}e^{-\alpha_k y_i G_k(x_i)} \end{split}$
可以看到这种第k次迭代开始前的数据的权重的调整是在根据第k-1次迭代中预测结果来进行调整的，换句话说，第k次迭代的数据集被第k-1次的训练修正了。

算法构建之总览

我们现在知道了每个弱分类器的权值是怎么够建的，也知道了Boosting算法中调整数据的部分是怎么调整的，算法的零件已经齐全，现在拼接起来如下：

初始化数据集权重为 $\frac{1}{n}$ ，n为特征的个数。
加入弱分类器，并根据数据集feed进模型确定这个新加入的弱分类的权重。
根据最终训练的结果，调整数据集中不同特征的权值
重复2，3步骤直到符合结束条件，一般为达到预计准确度，或者为达到规定迭代次数。

Gradient Boosting

首先值得注意的是，GBDT算法，它有很多别名如GBT，GTB，BGRT，GBDT，MART，初学者很容易把它们当作是多个算法，比如我（笑。
言归正传GBDT全名为Gradient Boosting Decision Tree。它也是Boosting算法的一种，它的算法推导相比之前算法的较为复杂，详细公式推导参考这篇文章，这里就不赘述了。
算法大体的步骤如下：

算法每次迭代生成一颗新的决策树
注：GBDT的核心其实是找出一堆决策树，然后让他们的结果累加得到最终的预测值
在每次迭代开始之前，计算损失函数在每个训练样本点的一阶导数和二阶导数
通过贪心策略生成新的决策树，通过等式计算每个叶节点对应的预测值
注：这步是通过目标函数求导得到的，需要利用第二步中的二阶导数和一阶导数，同时等式的推导中用到了泰勒公式
把新生成的决策树 $f_t(x)$ 添加到模型中： $\widehat{y}_i^{t} = \widehat{y}_i^{t-1}+f_t(x_i)$
*注：这里我们会将模型替换为 $\widehat{y}_i^{t} = \widehat{y}_i^{t-1}+\xi f_t(x_i)$ ，这里的 $\xi$ 称之为步长或者学习率。增加ϵ因子的目的是为了避免模型过拟合。*

GBDT总结

GBDT优点如下：

可以处理连续值和离散值
在相对少的调参情况下，模型的预测效果也会不错
模型的鲁棒性比较强。
缺点如下：
由于弱学习器之间存在关联关系，难以并行训练模型

Bagging和Boosting的总结

样本选择：
- Bagging算法是有放回的随机采样
- Boosting算法是每一轮训练集不变，只是训练集中的每个样例在分类器中的权重发生变化，而权重根据上一轮的分类结果进行调整
样例权重：
- Bagging使用随机抽样，样例的权重
- Boosting根据错误率不断的调整样例的权重值，错误率越大则权重越大
预测函数：
- Bagging所有预测模型的权重相等
- Boosting算法对于误差小的分类器具有更大的权重
并行计算：
- Bagging算法可以并行生成各个基模型
- Boosting理论上只能顺序生产，因为后一个模型需要前一个模型的结果
Bagging是减少模型的variance(方差)，Boosting是减少模型的Bias(偏度)。
Bagging里每个分类模型都是强分类器，因为降低的是方差，方差过高需要降低是过拟合。Boosting里每个分类模型都是弱分类器，因为降低的是偏度，偏度过高是欠拟合。
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath:[[' $','$ ']]}});</script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>