Machine-Learning-笔记 -Bagging&Boosting

本文介绍Bagging和Boosting的概念以及运用它们的集成学习算法Adaboost。

Bagging & Boosting

Bagging和Boosting都是将多个弱分类器集成起来形成一个强分类器，俗话说三个臭皮匠顶个诸葛亮。
首先介绍Bagging

Bagging

Bagging(bootstrap aggregating) ,采用一种有放回的抽样方式，每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本，而bootstrap是一种有放回的抽样方法。

Bagging的算法过程如下：

从原始样本中抽取训练集，每一轮从中抽取N个样本。共进行K轮抽取，得到K个训练集。
每个训练集用来训练一个模型，K个训练集共得到K个模型
对于分类问题：将上面得到的K个模型采用投票的方式得到分类结果；对于回归问题：计算上述模型的均值作为最后的结果。

注：这里的投票方式，可以采用每个模型不同的投票数的方式，可以给某个模型权重比大。也可以每个模型一样的权重。打个比方说，这就像你在买股票的时候，你有来自各方面的消息，有一个来自这家公司的高层，你跟他是朋友，他告诉你现在公司经营良好，市场份额逐年攀升，那么这时候这位高管朋友的消息一定给的权重大，因为这个是比其他更重要的信息。
运用Bagging的典型集成模型为随机森林。

Boosting

Bagging是通过有放回的抽样方式来构建强分类器，那么Boosting呢？Boosting则是通过在上一个弱分类器的基础上，通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果

运用Boosting的集成模型有Adaboost、GBDT、Xgboost。限于篇幅大小，这篇文章只介绍Adaboost，后续文章中再介绍另外两种算法。

Adaboost

Adaboost该算法先通过对N个训练样本的学习得到第一个弱分类器。然后增大犯错样本的权重，进行下一轮弱分类器的训练，最终得到一个强分类器。

Adaboost算法的大体描述为以下三步：
首先初始化训练数据，假设有N个训练样本数据，每个样本数据的权重为1/N，可以表示为
D1(i) = (W1,W2,W3,W4,…Wn)=[1/N,1/N,1/N…1/N]

第二步，训练弱分类器Ht,如果某个训练样本被错误分类，那么在构造下一个训练集中，它对应的权重要增大；相反，如果某个训练样本被正确分类，那么它的权重就减小。

a.选取一个当前误差率最低的弱分类器h,作为第t个基本分类器Ht,并计算该分类器在Dt分布上的误差et。
b.计算该弱分类器在最终分类器所占的权重(弱分类器用at表示)：
$$a_t =\ln(\sqrt{\frac{1-e_t}{e_t}})$$
c.更新训练样本的权值分布Dt+1:
$$D_{t+1} = \frac{D_t(i)exp(-a_iy_iH_t(x_i))}{Z_t} $$
其中：$$归一化常数Z_t=2\sqrt{e_t(1-e_t)}$$

说明：

从上面推导可得
错误分类样本，权重更新：
$$D_{t+1}(i) = \frac{D_t(i)}{2e_i}$$
正确分类样本，权重更新：
$$D_{t+1}(i) = \frac{D_t(i)}{2(1-e_i)}$$

第三步，将各个训练得到的弱分类器组合成一个强分类器，各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用。而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。
$$H_{final}=sign(f(x))=sign(\sum_{t=1}^T a_tH_t(x))$$

Adaboost算法实例：

将这10个样本作为训练数据，根据X和Y的对应关系，把这10个数据分为两类，其中用“+”表示类别1，用“O”表示类别-1.如图所示训练样本，弱分类器采用平行于坐标轴的直线。

初始化：令每个权值w1i = 1/N = 0.1，其中，N = 10，i = 1,2, …, 10，然后分别对于t= 1,2,3, …等值进行迭代（t表示迭代次数，表示第t轮）

第一次迭代t=1：
初始的权值分布D1为1/N（10个数据，每个数据的权值皆初始化为0.1），D1=[0.1, 0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1, 0.1]

在权值分布D1的情况下，取已知的三个弱分类器h1、h2和h3中误差率最小的分类器作为第1个基本分类器H1(x)（三个误差率都是0.3，那就取第一个吧）

在分类器H1(x)=h1情况下，样本点“5 7 8”被错分，因此基本分类器H1(x)的误差率为：e1=0.3
根据误差率e1计算Ht的权重:
$$a_1=\frac{1}{2}ln(\frac{1-0.3}{0.3})=0.4236$$
然后更新训练样本数据的权值分布，用于下一轮迭代，对于正确分类的训练样本“1 2 3 4 6 9 10”（共七个）的权值更新：
$$D_2(i) = \frac{D_1(i)}{2(1-e_1)}=\frac{1}{10}*\frac{1}{2(1-0.3)}=\frac1{14}$$
对于错误分类的训练样本“5 7 8”（共三个）的权值更新：
$$D_2(i) = \frac{D_1(i)}{2e_1}=\frac{1}{10}\frac{1}{20.3}=\frac1{6}$$

这样在第一轮结束后，最后得到的各个样本数据新的权值分布为：D2=[1/14,1/14,1/14,1/14,1/6,1/14,1/6,1/6,1/14,1/14]

可得分类函数f1(x)=a1H1(x)=0.4236H1(x)，这时，强分类器的训练错误为0.3

第二次迭代t=2：

在权值分布D2的情况下，再取三个弱分类器h1、h2和h3中误差率最小的分类器作为第2个基本分类器H2(x)：
1)　当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：
误差率e=1/6+1/6+1/6=3/6=1/2；
2)　当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：
误差率e=1/14+1/14+1/14=3/14；
3)　当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”:
误差率e=1/14+1/14+1/14=3/14；

因此选取当前最小的分类器h2作为第2个基本分类器H2(x),显然H2(x)把样本“3 4 6”分错了，根据D2可以得知他们的权值D2(3)=1/14,D2(4)=1/14,D2(6)=1/14,所以H2(x)在训练集上的误差率：e2=3 * 1/14 = 3/14

根据误差率e2计算Ht的权重:
$$a_2=\frac{1}{2}ln(\frac{1-3/14}{3/14})=0.6496$$
对于正确分类的训练样本的权值更新：
$$D_3(i) = \frac{D_2(i)}{2(1-e_2)}=\frac{7}{11}D_2(i)$$
对于错误分类的训练样本的权值更新：
$$D_3(i) = \frac{D_2(i)}{2e_2}=\frac{7}{3}D_2(i)$$

经过第2轮后，最后得到各个样本数据新的权值分布：
D3=[1/22,1/22,1/6,1/6,7/66,1/6,7/66,7/66,1/22,1/22]
分类函数f2(x) = 0.4236H1(x)+0.6496H2(x),此时组合两个基本的分类函数错分类点为”3 4 6”

第三次迭代t=3：

在权值分布D3的情况下，再取三个弱分类器h1、h2和h3中误差率最小的分类器作为第3个基本分类器H3(x)：
1)当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：
误差率e=7/66+7/66+7/66=7/22；
2)当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：
误差率e=1/6+1/6+1/6=1/2=0.5；
3)当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：
误差率e=1/22+1/22+1/22=3/22；

选取当前最小的分类器h3作为第3个基本分类器H3(x),显然H3(x)把样本“1 2 9”分错了，根据D3可以得知他们的权值D3(1)=1/22,D3(2)=1/22,D3(9)=1/22,所以H3(x)在训练集上的误差率：e3=3 * 1/22 = 3/22

根据误差率e3计算Ht的权重:
$$a_3=\frac{1}{2}ln(\frac{1-3/22}{3/22})=0.9229$$
对于正确分类的训练样本的权值更新：
$$D_4(i) = \frac{D_3(i)}{2(1-e_3)}=\frac{11}{19}D_3(i)$$
对于错误分类的训练样本的权值更新：
$$D_4(i) = \frac{D_3(i)}{2e_3}=\frac{11}{3}D_3(i)$$

经过第3轮后，最后得到各个样本数据新的权值分布：
D4=[1/6,1/6,11/114,11/114,7/114,11/114,7/114,7/114,1/6,1/38]
分类函数f3(x) = 0.4236H1(x)+0.6496H2(x)+0.9229H3(x),此时组合三个基本的强分类函数在数据集上有0个误分类点。至此，结束整个训练过程。
最终得到的强分类器为：
$$H_{final}=sign(\sum_{t=1}^T a_tH_t(x))=sign(0.4236H_1(x)+0.6496H_2(x)+0.9229H_3(x)$$

以上是Adaboost的全过程