bootstrap, boosting, bagging, stacking原理

Dear 丶 2022-05-15 05:04 235阅读 0赞

**Bootstraping:**

名字来自成语“pull up by your own bootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法，它是非参数统计中一种重要的估计统计量方差进而进行区间估计的统计方法。其核心思想和基本步骤如下：  
　　（1） 采用重抽样技术从原始样本中抽取一定数量（自己给定）的样本，此过程允许重复抽样。  
　　（2） 根据抽出的样本计算给定的统计量T。  
　　（3） 重复上述N次（一般大于1000），得到N个统计量T。  
　　（4） 计算上述N个统计量T的样本方差，得到统计量的方差。  
　　应该说Bootstrap是现代统计学较为流行的一种统计方法，在小样本时效果很好。通过方差的估计可以构造置信区间等，其运用范围得到进一步延伸。

**Jackknife**：

和上面要介绍的Bootstrap功能类似，只是有一点细节不一样，即每次从样本中抽样时候只是去除几个样本（而不是抽样），就像小刀一样割去一部分。

下列方法都是上述Bootstraping思想的一种应用。

**boosting：**

Boosting有很多种，比如AdaBoost(Adaptive Boosting)， Gradient Boosting等，这里以AdaBoost，Gradient Boosting为典型讲下。

Boosting也是集合了多个决策树，但是Boosting的每棵树是顺序生成的，每一棵树都依赖于前一颗树。**顺序运行会导致运行速度慢**。

首先介绍下AdaBoost的思想，而不去阐述Boosting决策树的构建构建方法和数学公式推导。  
AdaBoost，运用了迭代的思想。每一轮都加入一个新训练一个预测函数，直到达到一个设定的足够小的误差率，或者达到最大的树的数目。

①开始的时候每一个训练样本都被赋予一个初始权重，用***\*所有样本\****训练第一个预测函数。计算该预测函数的误差，***然后利用该误差计算训练的预测函数的权重系数***（该预测函数在最终的预测函数中的权重，此处忽略公式）。***接着利用误差更新样本权重（此处忽略公式）。如果样本被错误预测，权重会增加；如果样本被正确预测，权重会减少***。通过权重的变化，使下轮的训练器对错误样本的判断效果更好。

②以后每轮训练一个预测函数。根据最后得出的预测函数的误差计算新训练的预测函数在最终预测中的权重，然后更新样本的权重。权重更新之后，所有样本用于下轮的训练。

③如此迭代，直到误差小于某个值或者达到最大树数。

这里涉及到两个权重，***每轮新训练的预测函数在最终预测函数中所占的权重和样本下一轮训练中的权重***。这两个权重都是关于 每轮训练的预测函数产生的误差 的函数。

**Adaboost的算法流程：**  
假设训练数据集为T=\{(X1,Y1),(X2,Y2),(X3,Y3),(X4,Y4),(X5,Y5)\} 其中Yi=\{-1,1\}

1、初始化训练数据的分布  
训练数据的权重分布为D=\{W11,W12,W13,W14,W15\},其中W1i=1/N。即平均分配。

2、选择基本分类器  
这里选择最简单的线性分类器y=aX+b ，分类器选定之后，最小化分类误差可以求得参数。

3、计算分类器的系数和更新数据权重  
误差率也可以求出来为e1.同时可以求出这个分类器的系数。基本的Adaboost给出的系数计算公式为  
![这里写图片描述][SouthEast]  
上面求出的am就是这个分类器在最终的分类器中的权重。然后更新训练数据的权重分布。如果样本被错误预测，权重会增加；如果样本被正确预测，权重会减少。  
总而言之：Boosting每次迭代循环都是利用所有的训练样本，每次迭代都会训练出一个分类器，根据这个分类器的误差率计算出该分类器的在最终的分类器中的权重，并且更新训练样本的权重。这就使得每次迭代训练出的分类器都依赖上一次的分类器，串行速度慢。  
Boosting最终的组合弱分类器方式：  
通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。

![这里写图片描述][SouthEast 1]

GBDT算法流程：  
![这里写图片描述][SouthEast 2]

简单理解上面流程,其中N为样本个数，M为树的数目。**其中(a),(b),(c)步骤表示根据梯度计算出下一棵树以及下一棵树在组合中的权重。**  
注意：![这里写图片描述][SouthEast 3]，***是损失函数对f(x)求偏导***，并不是对x求偏导。

***Gradient Boost与传统的Boost的区别是，***

***Gradient Boost会定义一个loassFunction，每一次的计算是为了减少上一次的loss，而为了消除loss，我们可以在loss减少的梯度(Gradient)方向上建立一个新的模型。所以说，在Gradient Boost中，每个新的模型的建立是为了使得之前模型的loss往梯度方向减少，与传统Boost对正确、错误的样本进行加权有着很大的区别。***

![20140502093849718][]

**bagging:**

1）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping（有放回）的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（我们这里假设k个训练集之间是相互独立的，事实上不是完全独立）

2）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。但是是同种模型。（注：，k个训练集虽然有重合不完全独立，训练出来的模型因为是同种模型也是不完全独立。这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

3）对**分类**问题：将上步得到的k个模型采用**投票的方式**得到分类结果；对**回归**问题，计算上述模型的**均值**作为最后的结果。（所有模型的重要性相同）

**对于Bagging需要注意的是，每次训练集可以取全部的特征进行训练，也可以随机选取部分特征训练，例如随机森林就是每次随机选取部分特征**

**Rand forest：**随机森林，顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。 在建立每一棵决策树的过程中，有两点需要注意 - 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 - 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。 按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票得到结果。

**Rand forest与bagging的区别**：1）. Rand forest是选与输入样本的数目相同多的次数（可能一个样本会被选取多次，同时也会造成一些样本不会被选取到），而bagging一般选取比输入样本的数目少的样本；2）. bagging是用全部特征来得到分类器，而rand forest是需要从全部特征中选取其中的一部分来训练得到分类器； 一般Rand forest效果比bagging效果好！

Boosting，Bagging，这两种框架算法的异同点：

1）样本选择上：  
Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）并行计算：

Bagging：各个预测函数可以并行生成

Boosting：理论上各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。计算角度来看，两种方法都可以并行。bagging, random forest并行化方法显而意见。boosting有强力工具stochastic gradient boosting

5）bagging是减少variance，而boosting是减少bias  
在机器学习中，我们用训练数据集去训练（学习）一个model（模型），通常的做法是定义一个Loss function（误差函数），通过将这个Loss（或者叫error）的最小化过程，来提高模型的性能（performance）。然而我们学习一个模型的目的是为了解决实际的问题（或者说是训练数据集这个领域（field）中的一般化问题），单纯地将训练数据集的loss最小化，并不能保证在解决更一般的问题时模型仍然是最优，甚至不能保证模型是可用的。这个训练数据集的loss与一般化的数据集的loss之间的差异就叫做generalization error。而generalization error又可以细分为Bias和Variance两个部分。  
即**error=Bias+Variance**  
![这里写图片描述][SouthEast 4]  
可以通过降低Bias或者降低Variance来减小error

Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。由于![这里写图片描述][SouthEast 5]，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有![这里写图片描述][SouthEast 6]，此时可以显著降低variance。若各子模型完全相同，则![这里写图片描述][SouthEast 7]，此时不会降低variance。bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。boosting从优化角度来看，是用forward-stagewise这种贪心法去最小化损失函数![这里写图片描述][SouthEast 8]。例如，常见的AdaBoost即等价于用这种方法最小化exponential loss：![这里写图片描述][SouthEast 9]。所谓forward-stagewise，就是在迭代的第n步，求解新的子模型f(x)及步长a（或者叫组合系数），来最小化![这里写图片描述][SouthEast 10]，这里![这里写图片描述][SouthEast 11]是前n-1步得到的子模型的和。因此boosting是在sequential地最小化损失函数，其bias自然逐步下降。但由于是采取这种sequential、adaptive的策略，各子模型之间是强相关的，于是子模型之和并不能显著降低variance。所以说boosting主要还是靠降低bias来提升预测精度。

关于这个问题的一个引用：

作者：过拟合  
链接：https://www.zhihu.com/question/26760839/answer/40337791  
来源：知乎  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。由于![E\[\\frac\{\\sum X\_i\}\{n\}\]=E\[X\_i\]][E_frac_sum X_i_n_E_X_i]，所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。另一方面，若各子模型独立，则有![Var(\\frac\{\\sum X\_i\}\{n\})=\\frac\{Var(X\_i)\}\{n\}][Var_frac_sum X_i_n_frac_Var_X_i_n]，此时可以显著降低variance。若各子模型完全相同，则![Var(\\frac\{\\sum X\_i\}\{n\})=Var(X\_i)][Var_frac_sum X_i_n_Var_X_i]

，此时不会降低variance。bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。

（用公式可以一目了然：设有i.d.的n个随机变量，方差记为![\\sigma^2][sigma_2]，两两变量之间的相关性为![\\rho][rho]，则![\\frac\{\\sum X\_i\}\{n\}][frac_sum X_i_n]的方差为![\\rho\*\\sigma^2+(1-\\rho)\*\\sigma^2/n][rho_sigma_2_1-_rho_sigma_2_n]

，bagging降低的是第二项，random forest是同时降低两项。详见ESL p588公式15.1）

boosting从优化角度来看，是用forward-stagewise这种贪心法去最小化损失函数![L(y, \\sum\_i a\_i f\_i(x))][L_y_ _sum_i a_i f_i_x]。例如，常见的AdaBoost即等价于用这种方法最小化exponential loss：![L(y,f(x))=exp(-yf(x))][L_y_f_x_exp_-yf_x]。所谓forward-stagewise，就是在迭代的第n步，求解新的子模型f(x)及步长a（或者叫组合系数），来最小化![L(y,f\_\{n-1\}(x)+af(x))][L_y_f_n-1_x_af_x]，这里![f\_\{n-1\}(x)][f_n-1_x]

是前n-1步得到的子模型的和。因此boosting是在sequential地最小化损失函数，其bias自然逐步下降。但由于是采取这种sequential、adaptive的策略，各子模型之间是强相关的，于是子模型之和并不能显著降低variance。所以说boosting主要还是靠降低bias来提升预测精度。

（2017-3-8更新：此段存疑）另外，计算角度来看，两种方法都可以并行。bagging, random forest并行化方法显而意见。boosting有强力工具stochastic gradient boosting，其本质等价于sgd，并行化方法参考async sgd之类的业界常用方法即可。

6）Bagging里面每个分类器是强分类器，因为他降低的是方差，方差过高需要降低是过拟合。boosting里面每个分类器是弱分类器，因为他降低的是偏差，偏差过高是欠拟合。

## **stacking** ##

先讲讲stacking具体的算法流程

![这里写图片描述][SouthEast 12]

以上图为例，我们现在有训练集train\_x，train\_y,测试集test  
① 我们首先选择一种模型比如随机森林rf。（未经训练）  
②这里假设把训练集均分成5份，把其中四份作为小的训练集s\_train\_x,s\_train\_y另外一份作为小的测试集s\_test,测试集test不变。  
③我们以s\_train\_x,s\_train\_y训练rf模型，训练出的模型预测s\_test得出对应的s\_pred，再预测test得出y\_pred。  
④在训练集再选择另外一份作为小的测试集s\_test\_x,其他四份作为训练集训练模型rf。  
⑤重复②，③，④步骤五次。我们会得到五个s\_pred和五个y\_pred。  
五个s\_pred作为一个train\_X，原始的train\_y作为train\_Y训练模型得到模型G，五个y\_pred取个平均值作为新的test\_X,把test\_X带入到模型G中得出预测结果。  
以上就是stacking的第一层，在第二层中，我们以第一层的输出train再结合其他的特征集再做一层stacking。不同的层数之间有各种交互，还有将经过不同的 Preprocessing 和不同的 Feature Engineering 的数据用 Ensemble 组合起来的做法。  
上面是以一种模型随机森林进行模型训练，当然可以分别用不同种的模型。

以下代码是典型的stacking第一层

#coidng:utf-8
    import pandas as pd
    import numpy as np
    from sklearn.model_selection import KFold
    
    train=pd.read_csv("train.csv")
    test=pd.read_csv("test.csv")
    
    ntrain=train.shape[0] ## 891
    ntest=test.shape[0]   ## 418
    kf=KFold(n_splits=5,random_state=2017)
    
    def get_oof(clf,x_train,y_train,x_test):
        oof_train=np.zeros((ntrain,))  ##shape为(ntrain,)表示只有一维 891*1
        oof_test=np.zeros((ntest,))    ## 418*1
        oof_test_skf=np.empty((5,ntest))  ## 5*418
        for i,(train_index,test_index) in enumerate(kf.split(x_train)):
            kf_x_train=x_train[train_index] ## (891/5 *4)*7 故shape：(712*7)
            kf_y_train=y_train[train_index] ## 712*1
            kf_x_test=x_train[test_index]   ## 179*7
    
            clf.train(kf_x_train,kf_y_train)
    
            oof_train[test_index]=clf.predict(kf_x_test)
            oof_test_skf[i,:]=clf.predict(x_test)
    
        oof_test[:]=oof_test_skf.mean(axis=0)
        return oof_train.reshape(-1,1),oof_test.reshape(-1,1)

[SouthEast]: /images/20220515/d6d99fbcd15f4db8b9b8a052f7c28a60.png
[SouthEast 1]: /images/20220515/11c8dc421ba24fef9921e00a9a71a020.png
[SouthEast 2]: /images/20220515/bca749b118604b208c6e34c268c962b1.png
[SouthEast 3]: /images/20220515/a9e4ea8bffec416db6d756ffdcbbdcaf.png
[20140502093849718]: /images/20220515/06c88e78c8f945ba8920e77e9875d592.png
[SouthEast 4]: /images/20220515/7a92bc9f45204610b94d633eb7f318ef.png
[SouthEast 5]: https://img-blog.csdn.net/20170609170343338?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXJfdHl0aW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 6]: https://img-blog.csdn.net/20170609170432183?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXJfdHl0aW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 7]: https://img-blog.csdn.net/20170609170455525?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXJfdHl0aW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 8]: https://img-blog.csdn.net/20170609170612260?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXJfdHl0aW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 9]: https://img-blog.csdn.net/20170609170651436?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXJfdHl0aW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 10]: https://img-blog.csdn.net/20170609170718952?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvTXJfdHl0aW5n/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 11]: /images/20220515/2892f0917d69473e987e639a48b42c2b.png
[E_frac_sum X_i_n_E_X_i]: https://www.zhihu.com/equation?tex=E%5B%5Cfrac%7B%5Csum+X_i%7D%7Bn%7D%5D%3DE%5BX_i%5D
[Var_frac_sum X_i_n_frac_Var_X_i_n]: https://www.zhihu.com/equation?tex=Var%28%5Cfrac%7B%5Csum+X_i%7D%7Bn%7D%29%3D%5Cfrac%7BVar%28X_i%29%7D%7Bn%7D
[Var_frac_sum X_i_n_Var_X_i]: https://www.zhihu.com/equation?tex=Var%28%5Cfrac%7B%5Csum+X_i%7D%7Bn%7D%29%3DVar%28X_i%29
[sigma_2]: https://www.zhihu.com/equation?tex=%5Csigma%5E2
[rho]: https://www.zhihu.com/equation?tex=%5Crho
[frac_sum X_i_n]: https://www.zhihu.com/equation?tex=%5Cfrac%7B%5Csum+X_i%7D%7Bn%7D
[rho_sigma_2_1-_rho_sigma_2_n]: /images/20220515/802caed3f43a4e52ac6e1496a0b5a131.png
[L_y_ _sum_i a_i f_i_x]: https://www.zhihu.com/equation?tex=L%28y%2C+%5Csum_i+a_i+f_i%28x%29%29
[L_y_f_x_exp_-yf_x]: https://www.zhihu.com/equation?tex=L%28y%2Cf%28x%29%29%3Dexp%28-yf%28x%29%29
[L_y_f_n-1_x_af_x]: https://www.zhihu.com/equation?tex=L%28y%2Cf_%7Bn-1%7D%28x%29%2Baf%28x%29%29
[f_n-1_x]: /images/20220515/0d0a3060f2f14dfeb7f7c4d7d87d29cd.png
[SouthEast 12]: /images/20220515/658621d582e34ffeacb365b501363086.png