一、基本原理

集成学习(ensemble learning) 通过构建并结合多个学习器来完成学习任务，以提高比单个学习器更好的泛化和稳定性能。要获得好的集成效果，个体学习器应该“好而不同”。按照个体学习器的生成方式，集成学习可分为两类：序列集成方法，即个体学习器存在强依赖关系，必须串行生成，如Boosting；并行集成方法，即个体学习器不存在强依赖关系，可以并行生成，如Bagging，随机森林。

集成学习应“好而不同”

二、Boosting

Boosting指的是通过算法集合将弱学习器转换为强学习器。Boosting的主要原则是训练一系列的弱学习器，所谓弱学习器是指仅比随机猜测好一点点的模型，例如较小的决策树，训练的方式是利用加权的数据。在训练的早期对于错分数据给予较大的权重。
其工作机制如下：

先从初始训练集训练出一个基学习器；
再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注；
基于调整后的样本分布来训练下一个基学习器；
重复进行上述步骤，直至基学习器数目达到事先指定的值T，最终将这T个基学习器进行加权结合。
以下介绍几种典型的Boosting方法。

2.1、AdaBoost

给定二分类训练数据集 $T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$ ，AdaBoost需要将弱分类器线性组合为强分类器，步骤如下：

初始化训练数据权值分布 $D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}$
对 $m=1,2, \cdots, M$

使用具有权值分布 $D_{m}$ 的训练数据集学习，得到基分类器 $G_{m}(x)$ $\mathcal{X} \rightarrow \{-1,+1\}$
计算 $G_{m}(x)$ 在训练数据集上的分类误差率 $e_{m}=P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{t}\right)$
计算 $G_{m}(x)$ 的系数 $\alpha_{m}=\frac{1}{2} \ln \frac{1-e_{m}}{e_{m}}$
更新训练集的权值分布 $D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1,1}, \cdots, w_{m+1, N}\right)$ 其中 $w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N$ 这里 $Z_{m}$ 是规范化因子， $Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)$

构建基本分类器的线性组合 $f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)$ ，得到最终分类器 $G(x)=\operatorname{sign}(f(x))=\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right)$

以下为AdaBoost的sklearn实现：

from sklearn.ensemble import AdaBoostClassifier
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
import mglearn
import matplotlib.pyplot as plt

X,y = make_moons(n_samples=200,noise=0.25,random_state=3)
X_train,X_test,y_train,y_test = train_test_split(X,y,stratify=y,random_state=4)

adaboost = AdaBoostClassifier(n_estimators=10,random_state=2)
adaboost.fit(X_train,y_train)

print('accuracy on training set:{:.3f}'.format(adaboost.score(X_train,y_train)))
print('accuracy on test set:{:.3f}'.format(adaboost.score(X_test,y_test)))

fig,axes= plt.subplots(1)
mglearn.plots.plot_2d_separator(adaboost,X_train,fill=True,alpha=0.4)
mglearn.discrete_scatter(X_train[:,0],X_train[:,1],y_train)
axes.set_title('AdaBoost')

以下为输出结果及二分类划分边界
accuracy on training set:0.973
accuracy on test set:0.920

AdaBoost 解决二分类问题

2.2、Gradient Boosting Decision Tree

Gradient Boosting Decision Tree (GBDT) 是以分类树或者回归树为基本分类器的提升方法。提升树模型可以表示为决策树的加法模型： $f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)$ 其中 $T\left(x ; \Theta_{m}\right)$ 表示决策树， $\Theta_{m}$ 表示决策树参数， $M$ 表示树的个数。
提升树算法采用前向分步算法。首先确定初始提升树 $f_{0}(x)=0$ ，第m步模型是 $f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)$ 。
通过经验风险极小化确定下一棵树的参数 $\Theta_{m}$ ， $\hat{\Theta}_{m}=\arg \min _{\Theta_{n}} \sum_{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+T\left(x_{i} ; \Theta_{m}\right)\right)$ 。

对于上述相同问题，实现过程与结果如下所示。

gbdt = GradientBoostingClassifier(n_estimators=20,random_state=2)
gbdt.fit(X_train,y_train)

print('accuracy on training set:{:.3f}'.format(gbdt.score(X_train,y_train)))
print('accuracy on test set:{:.3f}'.format(gbdt.score(X_test,y_test)))

fig,axes= plt.subplots(1)
mglearn.plots.plot_2d_separator(gbdt,X_train,fill=True,alpha=0.4)
mglearn.discrete_scatter(X_train[:,0],X_train[:,1],y_train)
axes.set_title('GBDT')

accuracy on training set:0.967
accuracy on test set:0.880

GBDT 解决二分类问题

2.3、XGBoost

XGBoost（eXtreme Gradient Boosting）是一个非常优秀的集成学习方法。其算法思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。
XGBoost和GBDT的区别:

将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会优于GBDT。
损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，可以加快优化速度。
和GBDT只支持CART作为基分类器之外，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。
引进了特征子采样，像Random Forest那样，这种方法既能降低过拟合，还能减少计算。
在寻找最佳分割点时，考虑到传统的贪心算法效率较低，实现了一种近似贪心算法，用来加速和减小内存消耗，除此之外还考虑了稀疏数据集和缺失值的处理，对于特征的值有缺失的样本，XGBoost依然能自动找到其要分裂的方向。
XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。

对于上述相同问题，实现过程与结果如下所示。

from xgboost import XGBClassifier

xgboost = XGBClassifier(n_estimators=20,random_state=2)
xgboost.fit(X_train,y_train)

print('accuracy on training set:{:.3f}'.format(xgboost.score(X_train,y_train)))
print('accuracy on test set:{:.3f}'.format(xgboost.score(X_test,y_test)))

fig,axes= plt.subplots(1)
mglearn.plots.plot_2d_separator(xgboost,X_train,fill=True,alpha=0.4)
mglearn.discrete_scatter(X_train[:,0],X_train[:,1],y_train)
axes.set_title('xgboost')

accuracy on training set:0.960
accuracy on test set:0.860

XGBoost 解决二分类问题

三、问题探讨

参考资料

[1] https://scikit-learn.org/dev/modules/ensemble.html
[2] 周志华著. 机器学习. 北京:清华大学出版社,2016
[3] 李航著. 统计学习方法. 北京:清华大学出版社,2012
[4] 史春奇等著. 机器学习算法背后的理论与优化. 北京:清华大学出版社,2019
[5] Peter Harrington 著. 李锐等译. 机器学习实战. 北京:人民邮电出版社,2013

机器学习（八）：集成学习