【机器学习】一文理解集成学习Boosting思想之AdaBoost，附带案例

一、Boosting（提升学习）

随机森林

在随机森林的构建过程中，由于各棵树之间是没有关系的，相对独立的；在构建的过程中，构建第m个子树的时候，不会考虑前面的m-1棵子树。

那么：

• 如果在构建第m棵子树的时候，考虑到前m-1棵子树的结果，会不会对最终结果产生有益
  的影响？
• 各个决策树组成随机森林后，在形成最终结果的时候能不能给定一种既定的决策顺序呢？
  (也就是哪颗子树先进行决策、哪颗子树后进行决策)

对于 Bagging 思想集成的随机森林，是可以并行训练的，正是因为每个弱分类器之间不相互影响；而 Boosting 是通过串行训练而获得的，每个分类器要根据以前训练出的分类器的性能来进行训练。

• Boosting 分类的结果是基于所有弱分类器的加权求和结果的，所以 Boosting 中的每个弱分类器的权重不一样，每个权重代表的是其对应的弱分类器在上一轮迭代中的成功度；
• 而 Bagging 中的弱分类器的权重是一样的。

Boosting 常用模型：

• AdaBoost
• Gradient Boosting（GBT/GBDT/GBRT）
• XGBoost

二、AdaBoost

1、AdaBoost 执行过程

AdaBoost 是一种迭代算法，整个迭代过程直到错误率足够小或者达到一定的迭代次数为止；每轮迭代中会在修改后的训练集上产生一个新的弱学习器，然后使用该弱学习器对所有样本进行预测，以评估每个样本的重要性。

1. 在每一轮如何改变训练数据的权重或概率分布

AdaBoost算法会为每个样本赋予一个权重，其做法是：

• 提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。

这样一来，在那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注，也就是说 越难区分 的样本在训练过程中会变得越重要。于是，分类问题被一系列的弱分类器“分而治之”。

2. 如何将弱分类器组合成一个强分类器

AdaBoost 采取加权多数表决的方法：

• 具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

3. 样本加权、弱学习器组合

• 如图1，训练一个弱分类器，由中间虚线决策；
• 如图2，将分类错误的样本加权，图中由大小区分，再训练一个弱分类器，由左侧虚线决策；
• 如图3，再将分类错误的样本权重加大，再训练弱分类器；
• 如图4，将之前学习的弱学习器决策线组合，形成最终的分类器

2、AdaBoost 算法推导

Adaboost算法将基分类器的线性组合作为强分类器，同时给分类误差率较小的基本分类器以大的权重值，给分类误差率较大的基分类器以小的权重值；

重点（仔细推导）：
（1）构建的线性组合为：
$f(x) = \sum_{m=1}^M\alpha_mG_m(x)$f(x)=m=1∑M​αm​Gm​(x)
（2）最强学习器是在线性组合的基础上进行Sign函数转换：
$G(x) = sign(f(x)) = sign\Big[\sum_{m=1}^M\alpha_mG_m(x)\Big]$G(x)=sign(f(x))=sign[m=1∑M​αm​Gm​(x)]
（3）损失函数：
$loss=\frac{1}{n}\sum_{i=1}^nI(G(x_i) \neq y_i) \leqslant \frac{1}{n}\sum_{i=1}^n e^{-y_if(x_i)}$loss=n1​i=1∑n​I(G(xi​)̸​=yi​)⩽n1​i=1∑n​e−yi​f(xi​)

• 其中，$I(G(x_i) \neq y_i)$I(G(xi​)̸​=yi​) 为指示函数，表示预测值与真实值不等则函数为1，否则为0；所以不等式前面一部分表示准确率。
• 不等式后半部分：假设预测正确结果为1，预测错误结果为0，$f(x)$f(x) 为预测值，$y_i$yi​ 为真实值；
• 当预测结果与真实值相等，即$y_i = f(x_i)=1，y_if(x_i) = 1，e^{-y_if(x_i)} = e^{-1}&lt; 1$yi​=f(xi​)=1，yi​f(xi​)=1，e−yi​f(xi​)=e−1<1；
• 当预测结果与真实值不等，即$y_if(x_i) = -1，e^{-y_if(x_i)} = e &gt; 1$yi​f(xi​)=−1，e−yi​f(xi​)=e>1；
• 故不等式恒成立。

（4）假设第k-1轮的强学习器为：
$f_{k-1}(x)=\sum_{j=1}^{k-1}\alpha_jG_j(x)$fk−1​(x)=j=1∑k−1​αj​Gj​(x)
（5）第k轮的强学习器为：
$f_k(x) = f_{k-1}(x) + \alpha_kG_k(x)$fk​(x)=fk−1​(x)+αk​Gk​(x)
（6）损失函数为：
$loss = \frac{1}{n}\sum_{i=1}^ne^{-y_i( f_{k-1}(x_i) + \alpha_kG_k(x_i))}$loss=n1​i=1∑n​e−yi​(fk−1​(xi​)+αk​Gk​(xi​))
$= \frac{1}{n}\sum_{i=1}^ne^{-y_i f_{k-1}(x_i)}e^{-y_i\alpha_kG_k(x_i)}$=n1​i=1∑n​e−yi​fk−1​(xi​)e−yi​αk​Gk​(xi​)
由于在训练第k轮的时候，前一轮损失是一个已知值，所以可令 $\overline{w}_{ki} = e^{-y_i f_{k-1}(x_i)}$wki​=e−yi​fk−1​(xi​)，第k轮的损失函数为：
$loss= \frac{1}{n}\sum_{i=1}^n\overline{w}_{ki}e^{-y_i\alpha_kG_k(x_i)}$loss=n1​i=1∑n​wki​e−yi​αk​Gk​(xi​)
（7）是上面损失函数达到最小值的$\alpha_k，G_k$αk​，Gk​ 就是AdaBoost算法的最终解

求解过程分为两步：

1. 求$G^*_k(x)$Gk∗​(x)

• 对于任意$\alpha &gt;0$α>0，使损失函数最小的$G^*_k(x)$Gk∗​(x)可由下式得到：
• $G^*_k(x) = arg \min_G\sum_{i=1}^n\overline{w}_{ki} I(y_i \neq G(x_i))$Gk∗​(x)=argGmin​i=1∑n​wki​I(yi​̸​=G(xi​))
• 其中：$\overline{w}_{ki} = e^{-y_i f_{k-1}(x_i)}$wki​=e−yi​fk−1​(xi​)；表示第$k$k轮第$i$i个实例的权重，且$\sum_{i=1}^n \overline{w}_{mi}=1$∑i=1n​wmi​=1
• 此分类器$G^*_k(x)$Gk∗​(x)即为AdaBoost算法的基本分类器（弱分类器），它是使第k轮加权训练数据分类误差率最小的基本分类器。

2. 求$\alpha^*_k$αk∗​

• $\sum_{i=1}^n\overline{w}_{ki}e^{-y_i\alpha_kG_k(x_i)}$i=1∑n​wki​e−yi​αk​Gk​(xi​)
• $=\sum_{y_i = G_k(x_i)}\overline{w}_{ki}e^{-\alpha_k}+\sum_{y_i \neq G_k(x_i)}\overline{w}_{ki}e^{\alpha_k}$=yi​=Gk​(xi​)∑​wki​e−αk​+yi​̸​=Gk​(xi​)∑​wki​eαk​
• $=(e^{\alpha_k }-e^{-\alpha_k})\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i)) + e^{-\alpha_k}\sum_{i=1}^n \overline{w}_{ki}$=(eαk​−e−αk​)i=1∑n​wki​I(yi​̸​=G(xi​))+e−αk​i=1∑n​wki​
• 其中：$\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))=\sum_{y_i \neq G_k(x_i)}\overline{w}_{ki}$i=1∑n​wki​I(yi​̸​=G(xi​))=yi​̸​=Gk​(xi​)∑​wki​
• $\sum_{i=1}^n \overline{w}_{ki}=\sum_{y_i = G_k(x_i)}\overline{w}_{ki}+\sum_{y_i \neq G_k(x_i)}\overline{w}_{ki}$i=1∑n​wki​=yi​=Gk​(xi​)∑​wki​+yi​̸​=Gk​(xi​)∑​wki​
• 然后对$\alpha_k$αk​求导并使导数为0：
• $(e^{\alpha_k}+e^{-\alpha_k})\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i)) - e^{-\alpha_k}\sum_{i=1}^n \overline{w}_{ki} = 0$(eαk​+e−αk​)i=1∑n​wki​I(yi​̸​=G(xi​))−e−αk​i=1∑n​wki​=0
• $(e^{\alpha_k}+e^{-\alpha_k})\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))=e^{-\alpha_k}\sum_{i=1}^n \overline{w}_{ki}$(eαk​+e−αk​)i=1∑n​wki​I(yi​̸​=G(xi​))=e−αk​i=1∑n​wki​
• $\frac{e^{\alpha_k}+e^{-\alpha_k}}{e^{-\alpha_k}}=\frac{\sum_{i=1}^n \overline{w}_{ki}}{\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))}$e−αk​eαk​+e−αk​​=∑i=1n​wki​I(yi​̸​=G(xi​))∑i=1n​wki​​
• $e^{2\alpha_k} + 1 = \frac{\sum_{i=1}^n \overline{w}_{ki}}{\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))}$e2αk​+1=∑i=1n​wki​I(yi​̸​=G(xi​))∑i=1n​wki​​
• $e^{2\alpha_k} = \frac{\sum_{i=1}^n \overline{w}_{ki} - \sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))}{\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))}$e2αk​=∑i=1n​wki​I(yi​̸​=G(xi​))∑i=1n​wki​−∑i=1n​wki​I(yi​̸​=G(xi​))​
• $\alpha_k = \frac{1}{2}ln\Big(\frac{\sum_{i=1}^n \overline{w}_{ki} - \sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))}{\sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))}\Big)$αk​=21​ln(∑i=1n​wki​I(yi​̸​=G(xi​))∑i=1n​wki​−∑i=1n​wki​I(yi​̸​=G(xi​))​)
• 令 $\mathcal{E_k} = \sum_{i=1}^n \overline{w}_{ki}I(y_i \neq G(x_i))$Ek​=∑i=1n​wki​I(yi​̸​=G(xi​))，且$\sum_{i=1}^n \overline{w}_{mi}=1$∑i=1n​wmi​=1
• 故：
• $\alpha_k^* = \frac{1}{2}ln\Big(\frac{1 - \mathcal{E}_k}{\mathcal{E}_k}\Big)$αk∗​=21​ln(Ek​1−Ek​​)

以上就是算法的推导过程，下面我们就用上面得到的解，来构建 AdaBoost 算法：

3、AdaBoost 算法的构建过程：

• 1、假设训练数据集$T = \{(X_1,Y_1),(X_2,Y_2),..,(X_n,Y_n)\}$T={(X1​,Y1​),(X2​,Y2​),..,(Xn​,Yn​)}
• 2、初始化训练数据权重分布：
  $D_1 = (w_{11},w_{12},...,w_{1n}),\quad w_{1i} = \frac{1}{n},\quad i=1,2,...,n$D1​=(w11​,w12​,...,w1n​),w1i​=n1​,i=1,2,...,n
• 3、使用具有权重分布 $D_m$Dm​ 的训练数据集学习，得到基本分类器
  $G_m(x)：x \rightarrow\{-1, +1\}$Gm​(x)：x→{−1,+1}
• 4、计算 $G_m(x)$Gm​(x) 在训练集上的分类误差
  $\mathcal{E}_m = P(G_m(x) \neq y_i) = \sum_{i=1}^n w_{(mi)}I(G_m(x) \neq y_i)$Em​=P(Gm​(x)̸​=yi​)=i=1∑n​w(mi)​I(Gm​(x)̸​=yi​)

其中，$w_{(mi)}$w(mi)​为第m次迭代第i个样本的权重，$I(G_m(x) \neq y_i)$I(Gm​(x)̸​=yi​)为指示函数，决策正确为0，决策错位为1；

• 5、计算 $G_m(x)$Gm​(x) 模型的权重系数 $\alpha_m$αm​：
  $\alpha_m = \frac{1}{2} ln(\frac{1 - \mathcal{E}_m}{\mathcal{E}_m})$αm​=21​ln(Em​1−Em​​)
• 6、权重训练数据集的权重分布
  $D_{m+1} = (w_{(m+1,1)},w_{(m+1,2)},...,w_{(m+1,n)})$Dm+1​=(w(m+1,1)​,w(m+1,2)​,...,w(m+1,n)​)
  $w_{(m+1,i)} = \frac{w_{(m,i)}}{Z_m}e^{-y_i\alpha_mG_m(x_i)}$w(m+1,i)​=Zm​w(m,i)​​e−yi​αm​Gm​(xi​)

其中：$Z_m = \sum_{i=1}^n w_{(mi)}e^{-y_i\alpha_mG_m(x_i)}$Zm​=i=1∑n​w(mi)​e−yi​αm​Gm​(xi​)

• 7、构建基本分类器的线性组合
  $f(x) = \sum_{m=1}^M \alpha_mG_m(x)$f(x)=m=1∑M​αm​Gm​(x)
• 8、得到最终分类器
  $G(x) = sign\big(f(x)\big) = sign \Big[\sum_{m=1}^M\alpha_m G_m(x)\Big]$G(x)=sign(f(x))=sign[m=1∑M​αm​Gm​(x)]

4、简单实例进一步理解 AdaBoost算法

通过具体数据了解 AdaBoost 算法

训练数据集如下表：

（1）初始化数据权值分布
$D_1 = (w_{11},w_{12},...,w_{110}) \\ w_{1i} = 0.1, i = 1,2,...,10$D1​=(w11​,w12​,...,w110​)w1i​=0.1,i=1,2,...,10
（2）对$m = 1$m=1:

• （a）在权值分布为$D_1$D1​的训练数据集上，阀值$v$v取2.5时分类误差率最低，故基本分类器为：
  $G_1(x) = \begin{cases} 1, \quad x &lt; 2.5 \\ \\ -1, \quad x&gt;2.5 \end{cases}$G1​(x)=⎩⎪⎨⎪⎧​1,x<2.5−1,x>2.5​

• （b）$G_1(x)$G1​(x)在训练数据集上的误差率
  $e_1 = P(G_1(x) \neq y_i) = 0.3$e1​=P(G1​(x)̸​=yi​)=0.3

• （c）计算$G_1(x)$G1​(x)的系数：
  $\alpha_1 = \frac{1}{2}log\frac{1- e_1}{e_1} = 0.4236$α1​=21​loge1​1−e1​​=0.4236

• （d）更新训练数据集的权值分布
  $D_2 = (w_{21},w_{22},...,w_{210}) \\ w_{wi} = \frac{w_{1i}}{Z_1}exp(-\alpha_1 y_iG_1(x)), i = 1, 2,...,10 \\ D_2 = (0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143) \\ f_1(x) = 0.4236G_1(x)$D2​=(w21​,w22​,...,w210​)wwi​=Z1​w1i​​exp(−α1​yi​G1​(x)),i=1,2,...,10D2​=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)f1​(x)=0.4236G1​(x)
  分类器$sing[f_1(x)]$sing[f1​(x)]在训练数据集上有3个误分类点。

对$m = 2$m=2:

• （a）在权值分布为$D_2$D2​的训练数据集上，阀值$v$v取8.5时分类误差率最低，故基本分类器为：
  $G_2(x) = \begin{cases} 1, \quad x &lt; 8.5 \\ \\ -1, \quad x&gt;8.5 \end{cases}$G2​(x)=⎩⎪⎨⎪⎧​1,x<8.5−1,x>8.5​
  此时，序号为4，5，6的分类错误

• （b）$G_2(x)$G2​(x)在训练数据集上的误差率（将序号为4，5，6对应的w相加）：
  $e_2 =0.07143 + 0.07143+0.07143 = 0.2143$e2​=0.07143+0.07143+0.07143=0.2143

• （c）计算$G_2(x)$G2​(x)的系数：$\alpha_2 = 0.6496$α2​=0.6496

• （d）更新训练数据集的权值分布
  $D_3 = (0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,\\ 0.1667,0.1667,0.1667,0.0455) \\ f_2(x) = 0.4236G_1(x) + 0.6496G_2(x)$D3​=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1667,0.1667,0.1667,0.0455)f2​(x)=0.4236G1​(x)+0.6496G2​(x)
  分类器$sing[f_2(x)]$sing[f2​(x)]在训练数据集上有3个误分类点。

对$m = 3$m=3:

• （a）在权值分布为$D_3$D3​的训练数据集上，阀值$v$v取8.5时分类误差率最低，故基本分类器为：
  $G_3(x) = \begin{cases} 1, \quad x &lt; 5.5 \\ \\ -1, \quad x&gt;5.5 \end{cases}$G3​(x)=⎩⎪⎨⎪⎧​1,x<5.5−1,x>5.5​

• （b）$G_3(x)$G3​(x)在训练数据集上的误差率：$e_3 = 0.1820$e3​=0.1820

• （c）计算$G_3(x)$G3​(x)的系数：$\alpha_3 = 0.7514$α3​=0.7514

• （d）更新训练数据集的权值分布
  $D_3 = (0.125,0.125,0.125,0.125,0.102,0.102,\\ 0.102,0.065,0.065,0.125) \\ f_3(x) = 0.4236G_1(x) + 0.6496G_2(x)+0.7514G_3(x)$D3​=(0.125,0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.125)f3​(x)=0.4236G1​(x)+0.6496G2​(x)+0.7514G3​(x)

分类器$sing[f_3(x)]$sing[f3​(x)]在训练数据集上有0个误分类点。

最终分类器为：
$G(x) = sign[f_3(x)] = sign[0.4236G_1(x) + 0.6496G_2(x)+0.7514G_3(x)]$G(x)=sign[f3​(x)]=sign[0.4236G1​(x)+0.6496G2​(x)+0.7514G3​(x)]

三、AdaBoost 案例

代码可见：Github

sklearn 库中 ensemble.AdaBoostClassifier 以及 ensemble.AdaBoostRegressor API：

分类：
sklearn.ensemble.AdaBoostClassifier(base_estimator=None, n_estimators=50, 
		learning_rate=1.0, algorithm=’SAMME.R’, random_state=None)
回归：		
sklearn.ensemble.AdaBoostRegressor(base_estimator=None, n_estimators=50,
		learning_rate=1.0, loss=’linear’, random_state=None)

常用参数比较：

参数	AdaBoostClassifier	AdaBoostRegressor
base_estimator	弱分类器对象，默认为CART分类树，DecisionTreeClassifier；	弱回归器对象，默认为CART回归树，DecisionTreeRegressor；
algorithm	SAMME和SAMME.R；SAMME表示构建过程中使用样本集分类效果作为弱分类器的权重；SAMME.R使用对样本集分类的预测概率大小作为弱分类器的权重。由于SAMME.R使用了连续的概率度量值，所以一般迭代比SAMME快，默认参数为SAMME.R；强调：使用SAMME.R必须要求base_estimator指定的弱分类器模型必须支持概率预测，即具有predict_proba方法。	不支持
loss	不支持	指定误差的计算方式，可选参数”linear”, “square”,“exponential”, 默认为”linear”；一般不用改动
n_estimators	最大迭代次数，值过小可能会导致欠拟合，值过大可能会导致过拟合，一般50~100比较适合，默认50
learning_rate	指定每个弱分类器的权重缩减系数v，默认为1；一般从一个比较小的值开始进行调参；该值越小表示需要更 多的弱分类器

• 数据量大的时候，可以增加内部分类器的树深度，也可以不限制树深 max_depth，一般范围在10-100之间
• 数据量小的时候，一般可以设置树深度较小，或者 n_estimators 较小迭代次数或者最大弱分类器数：200次

1、Adaboost 分类算法

本案例将 AdaBoosted 决策树桩拟合到由两个“高斯分位数” 聚类组成的非线性可分类分类数据集，并绘制决策边界和决策分数

代码可见：05_Adaboost分类算法.py

2、Adaboost参数algorithm取值比较

本案例通过更改参数algorithm的取值比较"ASMME"和"SAMME.R" 的收敛速度，错误率

可以看出，SAMME.R 的收敛速度明显比 SAMME 快，错误率也比 SAMME 低，所以一般推荐使用 SAMME.R

代码可见：06_Adaboost参数algorithm取值比较.py

总结

AdaBoost 的优点如下：

• 可以处理连续值和离散值；
• 模型的鲁棒性比较强；
• 解释强，结构简单。

AdaBoost 的缺点如下：

• 对异常样本敏感，异常样本可能会在迭代过程中获得较高的权重值，最终影响模型效果。