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 。

步骤：

1. D 1 ( x ) = 1 / m \mathcal{D_1} (x)=1/m\quad D1​(x)=1/m %初始化权重分布
2. f o r   t = 1 , … , T : for\ t=1,\dots ,T: for t=1,…,T:
3. 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​
4. ϵ 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​ 的错误率
5. 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
6. α t = 1 2 ln ⁡ 1 − ϵ t ϵ t \quad \alpha _t=\frac{1}{2} \ln_{}{\frac{1-\epsilon_t }{\epsilon_t} }\quad αt​=21​ln​ϵt​1−ϵt​​ %决定 h t h_t ht​的权重
7. 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​=Zt​Dt​(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​ 满足分布条件的归一化因子
8. 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​αt​ht​(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对开源学习的贡献！