1.Boosting思路
Boosting是将若学习器提升为强学习器的算法。弱学习器仅能获得比随机猜测稍好一点的结果，而强学习器可以非常接近最优学习器。
Boosting的过程相当简单。以将示例分为正类和负类的二分类任务为例，假设弱学习器可以在任何给定分布上工作，训练样本独立同分布地根据分布 D \mathcal{D} D 从空间 X \mathcal{X} X 中抽取，并由函数 f \mathcal{f} f 打上真实标记。假设空间 X \mathcal{X} X 由 X 1 \mathcal{X_1} X1 , X 2 \mathcal{X_2} X2 和 X 3 \mathcal{X_3} X3 三部分组成，其中每部分负责 1 / 3 1/3 1/3。通过随机猜测得到的弱学习器在该问题上仅有50%的正确率。而我们希望得到分类错误率为0的分类器。
假设当前仅有一个弱分类器：能够正确预测来自 X 1 \mathcal{X_1} X1 和 X 2 \mathcal{X_2} X2 的样本，但会错误预测来自 X 3 \mathcal{X_3} X3 的样本，因此具有1/3的分类错误率。记这个若分类器为 h 1 h_1 h1 ,它显然不能符合要求。
Boosting的基本想法是纠正弱分类器 h 1 h_1 h1 所犯的错误。它从分布 D \mathcal{D} D 中生成一个新的分布 D ′ \mathcal{D'} D′ ,使得在该分布下 h 1 h_1 h1 分错的示例变得更加重要。在新的分布 D ′ \mathcal{D'} D′ 上，训练第二个分类器 h 2 h_2 h2 ，并假设再次得到一个弱分类器。 h 2 h_2 h2 能正确预测来自 X 1 \mathcal{X_1} X1 和 X 3 \mathcal{X_3} X3 的样本，但会错误预测来自 X 2 \mathcal{X_2} X2 的样本。结合 h 1 h_1 h1 和 h 2 h_2 h2，如AdaBoost算法，能得到一个可以正确预测来自 X 1 \mathcal{X_1} X1 的样本，但会在 X 2 \mathcal{X_2} X2 和 X 3 \mathcal{X_3} X3 上犯少量错误的集成分类器。再进一步重新生成分布 D ′ ′ \mathcal{D''} D′′ ，使得 X 2 \mathcal{X_2} X2 和 X 3 \mathcal{X_3} X3 的样本变得更加重要，训练第三个分类器 h 3 h_3 h3，能够正确预测 X 2 \mathcal{X_2} X2 和 X 3 \mathcal{X_3} X3 的样本。这样结合 h 1 h_1 h1， h 2 h_2 h2 和 h 3 h_3 h3 就能正确分类任何来自 X 1 \mathcal{X_1} X1 ， X 2 \mathcal{X_2} X2 和 X 3 \mathcal{X_3} X3 的样本，从而得到一个完美的分类器。
Boosting方法串行地训练一系列分类器，使得先前基分类器分错的样本在后续受到更多关注，并将这些分类器进行结合，以便获得性能完美的强分类器。
2.AdaBoost算法
输入：数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) } ; D= \left\{(x_1,y_1),(x_2,y_2),\dots,(x_m,y_m) \right\}; D={(x1,y1),(x2,y2),…,(xm,ym)}; 基学习算法 L \mathcal{L} L ; 学习轮数 T T T 。
步骤：
- D 1 ( x ) = 1 / m \mathcal{D_1} (x)=1/m\quad D1(x)=1/m %初始化权重分布
- f o r t = 1 , … , T : for\ t=1,\dots ,T: for t=1,…,T:
- h t = L ( D , D t ) \quad h_t=\mathcal{L}(D,\mathcal{D_t})\quad ht=L(D,Dt) %在分布 D t \mathcal{D_t} Dt 下从 D D D 中训练分类器 h t h_t ht
- ϵ t = P x ∼ D t ( h t ( x ) ≠ f ( x ) ) \quad \epsilon _t=P_{x\sim \mathcal{D_t} }\left ( h_t(x)\ne f(x) \right )\quad ϵt=Px∼Dt(ht(x)=f(x)) %评估 h t h_t ht 的错误率
- i f ϵ t > 0.5 t h e n b r e a k \quad if\ \epsilon _t>0.5\ then\ break if ϵt>0.5 then break
- α t = 1 2 ln 1 − ϵ t ϵ t \quad \alpha _t=\frac{1}{2} \ln_{}{\frac{1-\epsilon_t }{\epsilon_t} }\quad αt=21lnϵt1−ϵt %决定 h t h_t ht的权重
- D t + 1 = D t ( x ) Z t × { exp − ( α t ) if h t ( x ) = f ( x ) exp ( α t ) if h t ( x ) ≠ f ( x ) \quad\mathcal{D_{t+1}} =\frac{\mathcal{D_t(x)} }{Z_t} \times \begin{cases}\exp -(\alpha_t) &\text{ if } h_t(x)=f(x) \\\exp(\alpha_t) & \text{ if } h_t(x)\ne f(x)\end{cases}\quad Dt+1=ZtDt(x)×{exp−(αt)exp(αt) if ht(x)=f(x) if ht(x)=f(x) %更新分布，其中 Z t Z_t Zt 是令 D t + 1 \mathcal{D_{t+1}} Dt+1 满足分布条件的归一化因子
- e n d end end
输出： H ( x ) = s i g n ( ∑ t = 1 T α t h t ( x ) ) H(x)=sign\left ( {\textstyle \sum_{t=1}^{T}} \alpha_th_t(x) \right ) H(x)=sign(∑t=1Tαtht(x))
AdaBoost算法要求基学习器在指定的分布下学习。这通常是通过重赋权方法来完成，即每一轮训练中，根据相应的分布对训练样本赋权。对于不能利用样本权重学习的学习算法，可采用重采样方法，即每一轮根据相应的分布对训练样本采样。
3.AdaBoost实例
本次案例我们使用一份UCI的机器学习库里的开源数据集：葡萄酒数据集，该数据集可以在( https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data )上获得。该数据集包含了178个样本和13个特征，从不同的角度对不同的化学特性进行描述，我们的任务是根据这些数据预测红酒属于哪一个类别。(案例来源《python机器学习(第二版》)
数据含义：
- Class label：分类标签
- Alcohol：酒精
- Malic acid：苹果酸
- Ash：灰
- Alcalinity ofash：灰的碱度
- Magnesium：镁
- Total phenols：总酚
- Flavanoids：黄酮类化合物
- Nonflavanoid phenols：非黄烷类酚类
- Proanthocyanins：原花青素
- Color intensity：色彩强度
- Hue：色调
- OD280/OD315 of diluted wines：稀释酒OD280 OD350
- Proline：脯氨酸
结果分析：单层决策树似乎对训练数据欠拟合，而Adaboost模型正确地预测了训练数据的所有分类标签，而且与单层决策树相比，Adaboost的测试性能也略有提高。然而，为什么模型在训练集和测试集的性能相差这么大呢？我们使用图像来简单分析。
从上面的决策边界图可以看到：Adaboost模型的决策边界比单层决策树的决策边界要复杂的多。也就是说，Adaboost试图用增加模型复杂度而降低偏差的方式去减少总误差，但是过程中引入了方差，可能出现过拟合，因此在训练集和测试集之间的性能存在较大的差距。
值得注意的是：与单个分类器相比，Adaboost等Boosting模型增加了计算的复杂度，在实践中需要考虑是否愿意为预测性能的相对改善而增加计算成本，而且Boosting方式无法做到现在流行的并行计算的方式进行训练，因为每一步迭代都要基于上一部的基本分类器。
本文理论部分来自《集成学习：基础与算法》/周志华著；李楠译。
后面实验部分来源于Datawhale的开源学习内容，链接是https://github.com/datawhalechina/team-learning-data-mining/tree/master/EnsembleLearning
感谢Datawhale对开源学习的贡献！