7. 集成学习
https://gitee.com/fakerlove/machine-learning7.1 个体和集成
7.1.1 概述
参考资料
https://blog.csdn.net/qq_36330643/article/details/77621232从下图，我们可以对集成学习的思想做一个概括。对于训练集数据，我们通过训练若干个个体学习器，通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。
7.1.2 基本概念
集成学习有两个主要的问题需要解决，
第一是如何得到若干个个体学习器，
第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。
7.1.3 算法分类
第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法，
第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是bagging和随机森林（Random Forest）系列算法。
7.2 Bagging族算法
参考资料
https://blog.csdn.net/qq_41870157/article/details/103395732
https://blog.csdn.net/qq_38299170/article/details/1038331137.2.1 概念
从训练集从进行子抽样组成每个基模型所需要的子训练集，对所有基模型预测的结果进行综合产生最终的预测结果：
7.2.2 Bagging
1) 概念
bagging流派，它的特点是各个弱学习器之间没有依赖关系，可以并行拟合。
Bagging算法（英语：Bootstrap aggregating，引导聚集算法），又称装袋算法，是机器学习领域的一种团体学习算法。最初由Leo Breiman于1996年提出
Bagging算法可与其他分类、回归算法结合，提高其准确率、稳定性的同时，通过降低结果的方差，避免过拟合的发生。
自组采样
Bagging算法特点在于随机采样，那么什么是随机采样（自组采样）呢？
随机采样（bootstrap sample）从n个数据点中有放回地重复随机抽取一个样本（即同一个样本可被多次抽取），共抽取n次。创建一个与原数据大小相同得数据集，但有些数据点会缺失（大约1/3），有些会重复。
举例说明： 原数据集：[‘a’, ‘b’, ‘c’, ‘d’] 随机采样1：[‘c’, ‘d’, ‘c’, ‘a’] 随机采样2：[‘d’, ‘d’, ‘a’, ‘b’] …
对于缺失得数据点我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。
在 Bagging 中，一个样本可能被多次采样，也可能一直不被采样，假设一个样本一直不出现在采样集的概率为。
其概率为
原始样本数据集中有63.2% 的样本出现在Bagging使用的数据集中，
同时在采样中，还可以使用带外样本(out of bagging) 来对模型的泛化精度进行评估。
2) 算法流程
（1） 从训练样本集中随机可放回抽样（Bootstrapping )N次，得到与训练集相同大小的训练集，重复抽样K次，得到K个训练集 。
（2） 每个训练集得到一个最优模型，K个训练集得到K个最优模型。
（3） 分类问题：对K个模型采用投票的方式得到分类结果；回归问题：对K个模型的值求平均得到分类结果。
Bagging算法图如下：
Bagging法假设训练样本集服从均匀分布，即1/N。
7.2.3 随机树RF
资料参考
https://blog.csdn.net/perfect1t/article/details/836849951) 概念
Random Forest
随机森林是bagging的扩展体。RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。
具体地，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性，
而在RF上，对基决策树的每个结点，先从该结点的属性集中随机选择其中的k个属性组成属性集，然后从该属性集中选择最优的划分属性，一般情况下，推荐
注意的问题
在建立每一棵决策树的过程中，有两点需要注意的：采样和完全分裂。
一般很多的决策树算法都有一个重要的步骤：剪枝。但是在随机森林里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现 over-fitting。按这种算法得到的随机森林的每一棵都是很弱的，但是，全部组合起来就很厉害了。
基本原理
随机森林通过自助法(bootstrap)重采样技术，从原始训练样本集 N中有放回地重复随机抽样K个样本生成新的训练样本集合，然后根据自助样本集生成 K个分类树组成随机森林，新数据的分类结果按分类树投票多少形成的分数而定。
其实质是对决策树算法的一种改进，将多个决策树合并在一起，每棵树的建立依赖于一个独立抽取的样品，森林中的每棵树具有相同的分布，分类误差取决于每一棵树的分类能力和它们的相关性。
特征选择采用随机的方法去分裂每一个节点，然后比较不同情况下产生的误差。能够检测到的内在估计误差、分类能力和相关性决定选择特征的数目。单棵树的分类能力可能很小，但在随机产生大量的决策树后，一个测试样本可以通过每一棵树的分类结果经统计后选择最可能的分类。
随机森林的三个主要超参数调整
节点规模
随机森林不像决策树，每一棵树叶子节点所包含的观察样本数量可能十分少。该超参数的目标是生成树的时候尽可能保持小偏差
树的数量
在实践中选择数百棵树一般是比较好的选择
预测器采样的数量
一般来说，如果一共有 D个预测器，那么可以在回归任务中使用个预测器作为采样数，在分类任务中使用个预测器作为抽样。
2) 算法流程
前期准备
随机森林中的每一棵分类树为二叉树，其生成遵循自顶向下的递归分裂原则，即从根节点开始依次对训练集进行划分：在二叉树中，根节点包含全部训练数据，按照节点纯度最小原则，分裂为左节点和右节点。它们分别包含训练数据的一个子集，按照同样的规则节点继续分裂，直到满足分支停止规则而停止生长。若节点n上的分类树全部来自于同一类别，则此节点的纯度。
纯度度量方法
分类树为 Gini 准则
回归树为方差计算准则
具体流程
- 原始训练集为N，应用 bootstrap 法有放回地随机抽取 K 个新的自助样本集，并由此构建 K 棵分类树，每次未被抽到的样本组成了 K 个袋外数据。
- 设有个变量，则在每一棵树的每个节点处随机抽取个变量，然后在中选择一个最具有分类能力的变量，变量分类的阈值通过检查每一个分类点确定。
- 每棵树最大限度地生长，不做任何修剪
- 将生成的多棵分类树组成随机森林，用随机森林分类器对新的数据进行判别与分类，分类结果按树分类器的投票多少而定。
3) 优缺点
随机森林的优点
- 具有较高的准确率
- 在数据集上表现良好，两个随机性的引入(样本随机选择，特征随机选择)，使得随机森林不容易陷入过拟合。
- 在当前的很多数据集上，相对其他算法有着很大的有势，两个随机性的引入，使得随机森林具有很好的抗噪声能力，训练出的模型的方差小，泛化能力强。
- 它能够处理很高维度(feature 很多)的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化(归一化)。
- 在创建随机森林的时候，对 generlization error 使用的是无偏估计。
- 训练速度快，可以得到变量重要性排序(两种：基于 OOB误分率[Out Of Bag Error, OOB; 袋外错误率，袋外误分率]的增加量和基于分裂的 Gini 下降量)。
- 在训练过程中，能够检测到 feature 间的互相影响
- 容易做成并行化方法
- 实现比较简单
- 对部分特征缺失不敏感。
随机森林的局限性
- 当需要推测超出范围的独立变量或非独立变量，随机森林做得并不好，此时最好使用如 MARS 那样的算法
- 在某些噪声较大的样本集上， RF 模型容易陷入过拟合。
- 随机森林算法在训练和预测时都比较慢
- 如果需要区分的类别十分多，随机森林的表现并不会很好。
- 取值划分比较多的特征容易对 RF 的决策产生更大的影响，从而影响拟合模型的效果。
7.2.4 小结
随机森林的优势：
- 能够处理很高维度的数据，并且不用做特征选择；
- 在训练完成后，可以给出哪些属性比较重要；
- 容易做成并行化方法，速度快；
- 可以进行可视化展示，便于分析。
随机森林和Bagging比较：
- 两者的收敛性相似，但RF的起始性能相对较差，特别只有一个基学习器时。
- 随着基学习器数量的增加，随机森林通常会收敛到更低的泛化误差。
- 随机森林的训练效率常优于Bagging，因为Bagging是“确定型”决策树，而随机森林使用“随机型”决策树。
7.3 Boosting族算法
7.3.1 概念
1) 基本概述
训练过程为阶梯状，基模型按次序一一进行训练（实现上可以做到并行），基模型的训练集按照某种策略每次都进行一定的转化。对所有基模型预测的结果进行线性综合产生最终的预测结果：
其中，学习器性能越好，对应的权值也越大。样本权值1初始化为1/N，即初始样本集服从均匀分布，后面随着前一个学习器的结果更新样本权值。
2) 核心问题
Boosting算法中，每一个样本数据是有权重的，每一个学习器是有先后顺序的。在PAC（概率近似正确）的学习框架下，一定可以将弱分类器组装成一个强分类器。
（1）每一轮如何改变训练数据的权值和概率分布？
通过提高那些在前一轮被弱学习器分错样例的权值，减小前一轮正确样例的权值，使学习器重点学习分错的样本，提高学习器的性能。
（2）通过什么方式来组合弱学习器？
通过加法模型将弱学习器进行线性组合，学习器准确率大，则相应的学习器权值大；反之，则学习器的权值小。即给学习器好的模型一个较大的确信度，提高学习器的性能。
3) 算法分类
Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。
4) Boosting 算法公式
Boosting 算法主要涉及两个部分，即加法模型和前向分步算法
加法模型
是一个弱分类器
是弱分类器学习到的最优参数
就是弱学习在强分类器中所在的比重
是所有的组合
前向分步
在训练过程中，下一轮迭代产生的分类器是在上一轮的基础上训练得来的。可以写成如下形式：
由于采用的损失函数不同， Boosting 算法也因此有了不同的类型
5) Boosting 四大损失函数
Boosting 并非是一种方法，而是一类方法。
按照损失函数的不同，将其细分为若干算法，以下为四种不同损失函数对应的 Boosting 方法：
| 名称 | Loss (损失函数) | Derivative (导数) | 目标函数 | 算法 |
|---|---|---|---|---|
| squared error 平方损失 | $f^*=E(y | x_i)$ | ||
| absolute error 绝对损失 | $ | y_i-f(x_i) | $ | |
| exponentail loss 指数损失 | AdaBoost | |||
| logLoss 对数损失 | LogitBoost |
7.3.2 AdaBoost
资料参考
https://blog.csdn.net/perfect1t/article/details/836849951) 概念
AdaBoost 是Boosting中的经典算法，其主要应用于二分类问题。
Adaboost 算法采用调整样本权重的方式来对样本分布进行调整，即提高前一轮个体学习器错误分类的样本的权重，而降低那些正确分类的样本的权重，这样就能使得错误分类的样本可以受到更多的关注，从而在下一轮中可以正确分类，使得分类问题被一系列的弱分类器“分而治之”。
对于组合方式，AdaBoost采用加权多数表决的方法，具体地，加大分类误差率小的若分类器的权值，减小分类误差率大的若分类器的权值，从而调整他们在表决中的作用。
2) 算法推导
假设给定一个二分类的训练数据集
其中，每个样本由实例与标记组成，实例，标记,是实例空间，y是标记集合。
输出：最终的分类器G(x)
所有数据的权值一样
使用具有权值分布的的训练集学习，得到基本分类器
这里的对数是自然对数
其中是规范化因子
对上面更新的方法，变成循环，不断更新
设
分类器
分类误差率
更新训练集
是一个概率分布
得到最终能分类器G(x)
3) 例子
下面给出一个数据集合，+和-表示两类，下面我们要做的就是通过寻找直线方程来将两类坐标点区分开来。
按照Adaboost算法的思想，我们需要找一系列的简单直线方程来组合划分这些坐标点。
通过Round1、2、3三次迭代，我们分别找到了3个基本分类器,h1、h2和h3。而每一轮中被误分类的样本在下一轮中权值变大（如图中图形变大），而正确分类的样本权值变小（如图中图形变小）。在每一轮学习中，可以得到基本分类器的误差率和系数。
最终，我们将这3个基本分类器通过系数组合成一个强分类器，从而得到最终的分类器G(x)。
例二
7.3.3 提升树Gradient Boost
Gradient Boosting
资料参考
https://www.zhihu.com/question/54332085/answer/296456299参考资料2
https://www.cnblogs.com/massquantity/p/9174746.html1) 概念
提升树是以分类树或回归树为基本分类器的提升方法。
提升方法采用加法模型(即基函数的线性组合)与前向分步算法。以决策树为基函数的提升方法称为提升树(boosting tree)。
对于分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。
Gradient Boosting是一种实现Boosting的方法，它的主要思想是，每一次建立模型，是在之前建立模型损失函数的梯度下降方向。损失函数描述的是模型的不靠谱程度，损失函数越大，说明模型越容易出错。如果我们的模型能够让损失函数持续的下降，说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度的方向下降。
2) 数学准备
这里首先回顾一下梯度下降 (Gradient Descend)。机器学习的一大主要步骤是通过优化方法最小化损失函数L(θ)L(θ)，进而求出对应的参数θθ。梯度下降是经典的数值优化方法，其参数更新公式：
Gradient Boosting 采用和AdaBoost同样的加法模型，在第m次迭代中，前m-1个基学习器都是固定的，即
因而在第m步我们的目标是最小化损失函数,进而求得相应的基学习器。若将f(x)当成参数，则同样可以使用梯度下降法
可以发现若将
即用基学习器hm(x)hm(x)拟合前一轮模型损失函数的负梯度，就是通过梯度下降法最小化.由于为实际为函数，所以该方法被认为是函数空间的梯度下降。
2) 算法推导
for m=1 to M:
计算负梯度
通过最小化平方误差，用基学习期拟合
使用line search 确定步长，使得L最小
7.3.4 梯度提升树GBDT
1) 概念
(Gradient Boosting Decision Tree, GBDT)
GBDT 是多棵树的输出预测值的累加，GBDT的树都是回归树而不是分类树
在Gradient Boosting框架中，最常用的基学习器是决策树 (一般是CART)，二者结合就成了著名的梯度提升树 (Gradient Boosting Decision Tree, GBDT)算法。下面先叙述回归问题，再叙述分类问题。注意GBDT不论是用于回归还是分类，其基学习器 (即单颗决策树) 都是回归树，即使是分类问题也是将最后的预测值映射为概率。
决策树可以看作是一个分段函数，将特征空间划分为多个独立区域，在每个区域预测一个常数，如下图所示：
因此单棵决策树可表示为
为划分出来的独立区域，即各个叶结点
为各区域的输出值
为了求出这两个参数，于是公式变为
即先求出树划分出的区域，而相应的为该区域的平均值。
接下来注意到求出是对于整棵树中所有区域都是一样的，这样可能并不会使损失最小，因此Friedman提出可以对每个区域别求一个最优的值
2) 算法推导
for m=1 to M:
* 计算负梯度$\hat{y}_i=-\frac{\partial L(y_i,f_{m-1}(x_i))}{\partial f_{m-1}(x_i)},i=1,2,...,N$
* $\{R_{jm}\}^J_1=argmin_{\{R_{jm}\}^J_1}\sum_{i=1}^N[\hat{y}_i-h_m(x_i;\{R_{jm}mb_{jm}\}^J_1)]^2$
* $\gamma_{jm}=argmin_{\gamma}\sum_{x_i\in R_{jm}}L(y_i,f_{m-1}(x_i)+\gamma)$
* $f_m(x)=f_{m-1}(x)+\sum_{j=1}^J\gamma_{jm}I(x\in R_{jm})$
3) 例子
资料参考
https://www.zhihu.com/question/54332085/answer/296456299举一个简单的例子。GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，我们训练的时候，第一棵树的拟合过后预测年龄是12岁，我们与真实数据比对差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去拟合学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。 如果还有疑问，请看下面这个例子： 还是年龄预测，简单起见训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：
这是一棵普通的回归树，我们可以看到，我们通过年龄平均值将少年和青年分开 ，再用上网时长将每个分支继续细分到不能分割或者达到要求为止。 接下来看BDT实现：
在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为两拨，每拨用平均年龄作为预测值。此时计算残差（残差的意思就是： A的预测值 + A的残差 = A的实际值），所以A的残差就是16-15=1（注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值）。进而得到A,B,C,D的残差分别为-1,1，-1,1。然后我们拿残差替代A,B,C,D的原值，到第二棵树去学习，如果我们的预测值和它们的残差相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了。这里的数据显然是我可以做的，第二棵树只有两个值1和-1，直接分成两个节点。此时所有人的残差都是0，即每个人都得到了真实的预测值。
换句话说，现在A,B,C,D的预测值都和真实年龄一致了:
- 14岁高一学生，购物较少，经常问学长问题；预测年龄A = 15 – 1 = 14
- 16岁高三学生；购物较少，经常被学弟问问题；预测年龄B = 15 + 1 = 16
- 24岁应届毕业生；购物较多，经常问师兄问题；预测年龄C = 25 – 1 = 24
- 26岁工作两年员工；购物较多，经常被师弟问问题；预测年龄D = 25 + 1 = 26
GBDT核心思想就是这样，但是既然普通的树和GBDT结果一样，那为什么还需要GBDT呢？ 原因就是过拟合。过拟合就是模型在训练数据集上表现的过于好，分的过于细。以致于容错能力很低，也可以称作”泛化能力“低。这就会导致在实际测试数据中表现明显差很多。我们发现图1为了达到100%精度使用了3个feature（上网时长、时段、网购金额），其中分枝“上网时长>1.1h” 很显然已经过拟合了，这个数据集上A,B也许恰好A每天上网1.09h, B上网1.05小时，但用上网时间是不是>1.1小时来判断所有人的年龄很显然是有悖常识的； 相对来说图2的boosting虽然用了两棵树 ，但其实只用了2个feature就搞定了，后一个feature是问答比例，显然图2的依据更靠谱（这是杜撰的数据，为了显示效果夸张的一下，实际有实验证明以上论点）。
7.3.5 XGBoost
资料参考
https://www.cnblogs.com/massquantity/p/9794480.html资料参考2
https://blog.csdn.net/qq_38299170/article/details/103842265小结
最后总结一下 XGBoost 与传统 GBDT 的不同之处：
- 传统 GBDT 在优化时只用到一阶导数信息，XGBoost 则对目标函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。另外 XGBoost 工具支持自定义损失函数，只要函数可一阶和二阶求导。
- XGBoost 在损失函数中加入了正则化项，用于控制模型的复杂度，防止过拟合，从而提高模型的泛化能力。
- 传统 GBDT 采用的是均方误差作为内部分裂的增益计算指标（因为用的都是回归树），而 XGBoost 使用的是经过优化推导后的式子，即式 (1.6)(1.6) 。
- XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算量，这也是 XGBoost 异于传统 GBDT 的一个特性。
- XGBoost 添加了对稀疏数据的支持，在计算分裂增益时不会考虑带有缺失值的样本，这样就减少了时间开销。在分裂点确定了之后，将带有缺失值的样本分别放在左子树和右子树，比较两者分裂增益，选择增益较大的那一边作为默认分裂方向。
- 并行化处理：由于 Boosting 本身的特性，无法像随机森林那样树与树之间的并行化。XGBoost 的并行主要体现在特征粒度上，在对结点进行分裂时，由于已预先对特征排序并保存为block 结构，每个特征的增益计算就可以开多线程进行，极大提升了训练速度。
- 传统 GBDT 在损失不再减少时会停止分裂，这是一种预剪枝的贪心策略，容易欠拟合。XGBoost采用的是后剪枝的策略，先分裂到指定的最大深度 (max_depth) 再进行剪枝。而且和一般的后剪枝不同， XGBoost 的后剪枝是不需要验证集的。 不过我并不觉得这是“纯粹”的后剪枝，因为一般还是要预先限制最大深度的呵呵。
7.4 Stacking
将训练好的所有基模型对训练基进行预测，第j个基模型对第i个训练样本的预测值将作为新的训练集中第i个样本的第j个特征值，最后基于新的训练集进行训练。同理，预测的过程也要先经过所有基模型的预测形成新的测试集，最后再对测试集进行预测：
7.5 结合策略
1. 平均法
对于数值类的回归预测，通常使用的结合策略是平均法，即对K个学习器的学习结果求平均，得到最终的预测结果。
2. 投票法
对于分类问题的预测，通常使用的结合策略是投票法，也就是我们常说的少数服从多数。即对K个学习器的分类结果作一个统计，出现次数最多的类作为预测类。
3. 学习法
上面两种结合策略方法比较简单，可能学习误差较大。因此，我们尝试用学习法去预测结果，学习法是将K个学习器的分类结果再次作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。
7.6 多样性
7.7 小结
Bagging和Boosting方法都是把若干个学习器整合为一个学习器的方法，Bagging方法可以降低模型的方差，Boosting方法可以降低模型的偏差，在实际工作中，因情况需要选择集成方法。
下面是决策树与这些算法框架进行结合所得到的新的算法：
1） Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT
区别
训练样本集
Bagging：训练集是有放回抽样，从原始集中选出的K组训练集是相互独立的。
Boosting：每一次迭代的训练集不变。
训练样本权重
Bagging：每个训练样本的权重相等，即1/N。
Boosting：根据学习器的错误率不断调整样例的权值，错误率越大，权值越大。
预测函数的权重：
Bagging：K组学习器的权重相等，即1/K。
Boosting：学习器性能好的分配较大的权重，学习器性能差的分配较小的权重。
并行计算
Bagging：K组学习器模型可以并行生成。
Boosting：K组学习器只能顺序生成，因为后一个模型的样本权值需要前一个学习器模型的结果。