集成算法

2019-10-23 本文已影响0人 dingtom

集成学习包括Bagging方法和Boosting方法，下面详细分析这两种方法。

下面是决策树与这些算法框架进行结合所得到的新的算法：
1） Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT

Bagging即套袋法

Bagging法假设训练样本集服从均匀分布，即1/N。

算法过程如下：

（1）从训练样本集中随机可放回抽样（Bootstrapping )N次，得到与训练集相同大小的训练集，重复抽样K次，得到K个训练集。
（2）每个训练集得到一个最优模型，K个训练集得到K个最优模型。
（3）分类问题：对K个模型采用投票的方式得到分类结果；回归问题：对K个模型的值求平均得到分类结果。

Boosting算法

每一个样本数据是有权重的，每一个学习器是有先后顺序的。在PAC（概率近似正确）的学习框架下，一定可以将弱分类器组装成一个强分类器。

关于Boosting的两个核心问题

（1）每一轮如何改变训练数据的权值和概率分布？

通过提高那些在前一轮被弱学习器分错样例的权值，减小前一轮正确样例的权值，使学习器重点学习分错的样本，提高学习器的性能。

（2）通过什么方式来组合弱学习器？

通过加法模型将弱学习器进行线性组合，学习器准确率大，则相应的学习器权值大；反之，则学习器的权值小。即给学习器好的模型一个较大的确信度，提高学习器的性能。

其中，学习器性能越好，对应的权值也越大。样本权值1初始化为1/N，即初始样本集服从均匀分布，后面随着前一个学习器的结果更新样本权值。

集成学习之结合策略

集成学习得到多个学习器后，结合策略得到最终的结果。通常用到最多的是平均法，投票法和学习法。

平均法：简单平均、加权平均

适用范围：

规模大的集成，学习的权重较多，加权平均法易导致过拟合
$H(x)=\sum_{i=1}^{T} w_{i} h_{i}(x)$
个体学习器性能相差较大时宜使用加权平均法，相近用简单平均法。
$H(x)=\frac{1}{T} \sum_{i=1}^{T} h_{i}(x)$

投票法：

绝对多数投票法：某标记超过半数，也就是我们常说的要票过半数，否则就当会拒绝预测；
$H(x)=\left\{\begin{array}{l}{c_{j}, \quad \text { if } \sum_{i=1}^{T} h_{i}^{j}(x)>0.5 \sum_{k=1}^{T} \sum_{i=1}^{T} h_{i}^{k}(x)} \\ {\text {reject,} \quad \text { otherwise. }}\end{array}\right.$
相对多数投票法：预测为得票最多的标记，若同时有多个标记的票最高，则从中随机选取一个，也就是所谓的“少数服从多数”。
$H(x)=c_{a r g} \max _{j} \sum_{i=1}^{T} h_{i}^{j}(x)$
加权投票法：提供了预测结果，与加权平均法类似。
$H(x)=c_{\arg \max _{j}} \sum_{i=1}^{T} w_{i} h_{i}^{j}(x)$

学习法：

对于学习法，代表方法是stacking，当使用stacking的结合策略时，我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。
在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。

image.png

Bagging和Boosting两者之间的区别

1）训练样本集
Bagging：训练集是有放回抽样，从原始集中选出的K组训练集是相互独立的。
Boosting：每一次迭代的训练集不变。
2）训练样本权重
Bagging：每个训练样本的权重相等，即1/N。
Boosting：根据学习器的错误率不断调整样例的权值，错误率越大，权值越大。
3）预测函数的权重：
Bagging：K组学习器的权重相等，即1/K。
Boosting：学习器性能好的分配较大的权重，学习器性能差的分配较小的权重。
4）并行计算
Bagging：K组学习器模型可以并行生成。
Boosting：K组学习器只能顺序生成，因为后一个模型的样本权值需要前一个学习器模型的结果。

Bagging和Boosting的方差和偏差问题讨论

Bagging减小模型的方差
bagging对样本进行有放回的重采样，学习结果是各个学习模型的平均值。由于重采样的样本集具有相似性以及使用相同的学习器模型，因此，各学习模型的结果相近，即模型有近似相等的偏差和方差。
假设 $X_i$ 为 $i$ 组训练样本集，各组训练样本集是相互独立的，不同的训练样本集代表不同的模型，由概率论可知：

大家发现了没有，均值没变，但是方差却减小到只有原来方差的 $\frac{1}{n^2}$ 。因此，Bagging法是显著的减小了学习器的方差。
Boosting是减小模型的偏差
Boosting是从学习模型的优化角度去更新样本权值和分配学习器权值，因此，学习模型随着迭代次数的增加，模型偏差越来越小。Boosting是通过迭代的方式去更新模型，因此各个子模型的之间是强相关的，强相关的意思是各模型的相似度很多，且训练集一直是不变的。因此模型之和并不能降低方差。