Bagging(Bootstrap AGGregatlNG)

思维导图

原理和算法描述

Bagging的思想如上图所示，对于给定的m个样本训练集，通过随机采样得到T个样本集，对每个样本集进行训练，得到T个学习器，通过选择结合策略得到最后的结果。

Bagging算法的伪代码如上图所示，输入一个包含m个样本的训练集、一个基学习算法以及需要训练的轮数T,训练T次，输出为最终的强分类器。

1. 对于t=1,2…,T:
   对训练集进行第t次随机采样，共采集m次，得到包含m个样本的采样集$D_{bs}$Dbs​
   用采样集$D_{bs}$Dbs​训练第t个弱学习器$h_t$ht​(x)
2. 如果是分类算法预测，则T个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

自助采样法

给定包含m 个样 本的数据集 D ， 我们对它进行采样产生数据集 D’:

每次随机从 D 中挑选一个 样本， 将其拷贝放入 D‘， 然后再将该样本放回初始数据集 D 中，使得该样本在 下次采样时仍有可能被采到;这个过程重复执行m 次后，我们就得到了包含 m 个样本的数据集 D’。

每次采样中，样本不被采样到的概率为$1-\frac{1}{m}$1−m1​,经过m次采样后，数据集中不被采样到的概率为$（1-\frac{1}{m})^m$（1−m1​)m,当$m \to \infty$m→∞时，有如下式子：

通过重要极限的性质我们可以得到结果为$\frac{1}{e}$e1​，即约等于0.368，所以数据集中不被采样到的概率为0.632

一般结合策略

任务	结合策略
分类任务	简单投票法
回归任务	简单平均法

包外估计

由于每个基学习器只使用了初始训练集中约 63.2%的样本，剩下约 36.8% 的样本可用作验证集来对泛化性能进行"包外估计"。

使用$D_t$Dt​表示$h_t$ht​实际使用的训练样本集
令$H^{oob}(x)$Hoob(x) 表示对样本x的包外预测
则可以得到$H^{oob}(x)$Hoob(x)如下式

则Bagging 泛化误差的包外估计为

包外样本还有许多其他用途.
当基学习器是决策树时，可使用包外样本来辅助剪枝或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理;
当基学习器是神经网络时，可使用包外样本来辅助早期停止 以减小过拟合的风险.

偏差(bias)-方差(variance)分析

Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。由于$E[\frac{\sum X_i}{n}]=E[X_i]$E[n∑Xi​​]=E[Xi​]，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有$Var(\frac{\sum X_i}{n})=\frac{Var(X_i)}{n}$Var(n∑Xi​​)=nVar(Xi​)​，此时可以显著降低variance。若各子模型完全相同，则$Var(\frac{\sum X_i}{n})=Var(X_i)$Var(n∑Xi​​)=Var(Xi​)，此时不会降低variance。bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。

Boosting和Bagging的区别

随机森林(Random Forest)

思维导图

与决策树联系与区别

RF是在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。
具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有 d 个属性)中选择一个最优属性;而在 RF 中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含 k个属性的子集，然后再从这个子集中选择一个最优属性用于划分. 这里的参数 k 控制了随机性的引入程度;若令 k = d， 则基决策树的构建与传统决策树相同; 若令 k = 1 ， 则是随机选择一个属性用于划分; 一般情况下，推荐值 k =$log_2 d$log2​d

算法描述

在整个随机森林算法的过程中，有两个随机过程：a. 输入数据—>随机从整体训练数据集中选取一部分作为一颗决策树的构建，而且是有放回的选取。 b. 特征选取—>每棵决策树所需的特征是从整体的特征集中随机选取的。
具体实现：

1. 从训练数据中选取n个数据作为训练数据的输入，一般情况下n是远远小于整体的训练数据N，这样就会造成有一部分数据是无法被去到的，这部分数据被称为袋外数据，可以使用袋外数据做误差分析。
2. 选取输入的训练数据后，构建决策树（方法：每一个分裂节点从整体的特征集M中选取m个特征构建，一般情况下m远小于M，通常是log2或者sqrt的数量），从这m个属性中根据某种策略（如gini减少或信息增益等）确定分裂属性。
3. 重复b步骤，直到不能分裂或达到我们设定的阈值（如叶子结点树或的树的深度），此时建立了一个决策树
4. 重复上面的1、2、3步骤，直到达到预定树的颗数为止。

收敛性

随机森林的起始性能往往相对较差， 特别是在集成中只包含一个基学习器时，因为通过引入属性扰动，随机森林中个体学习器的性能往往有所降低然而，随着个体学习器数目 的增加，随机森林通常会收敛到更低的泛化误差。

优缺点

优点:
1在当前所有算法中，具有极好的准确率

2)能够有效地运行在大数据集上

3)能够处理具有高维特征的输入样本，而且不需要降维

4)能够评估各个特征在分类问题上的重要性

5)在生成过程中，能够获取到内部生成误差的一种无偏估计

6)对于缺省值问题也能够获得很好得结果

缺点：
1）当随机森林的决策树个数较多时，训练时会消耗大量的时间和空间

2）在某些噪声较大的分类和回归问题上会过拟合

3）对于有不同级别的属性的数据，级别划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产生的属性权值是不可信的

Stacking

算法描述

为了保证样本数据的多样性，从而提高模型的泛化能力，stacking提倡每个基模型采用KFold交叉验证的方式产生预测值。如上图，Model1经过k轮训练后，每次在验证集上的预测结果汇集成了原始X_train上的预测结果y_pred_1；在k轮训练的同时，Model1也在原始测试集X_test上生成了k个预测结果，这些结果通过均值操作融合成一个测试集上的输出y_test_1。