AdaBoost算法

AdaBoost的全称是(Adaptiva Boosting)，即自适应提升方法。他的自适应在于：前一个弱分类器分错的样本权重会得到加强，权重更新后的全体样本再次被用来训练下一个弱分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

具体来讲，AdaBoost算法可以分为三步：

初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

AdaBoost二分类问题算法流程

初始化每个训练样本的权重值，每个样本的权重相等，共N个样本。

$w_i^0 = \frac{1}{N}, i = 1,2,...,N$
循环，对第t=1,2,...,T个弱分类器依次训练：
1. 训练权重分布为 $W_t$ 的样本数据，得到弱分类器 $f_t$ ，计算它对样本集的错误率 $e_t$
$e_t = P(f_t(x_i) \neq y_i) = \frac{\sum\limits_{i=1}^{N}w_i^tI(f_t(x_i) \neq y_i)}{\sum\limits_{i=1}^{N}w_i^t}$
1. 计算弱分类器的权重
$\alpha_t = \frac{1}{2}\ln\frac{1 - e_t}{e_t}$
1. 更新训练样本的权重
$w_i^t = w_i^{t-1}exp(-y_i \alpha_t f_t(x_i))/Z_t$

其中 $Z_t$ 为归一化因子，是所有训练样本的权重之和，

$Z_t = \sum\limits_{i=1}^{N}w_i^{t-1}exp(-y_i \alpha_t f_t(x_i))$
结束循环，得到一系列的权重为 $\alpha_t$ 的弱分类器 $f_t$ ，将弱分类器根据权重线性组合，得到最终的强分类器：

$G(x) = sgn(F(x)) = sgn(\sum\limits_{t=1}^{T}\alpha_tf_t(x))$

关于弱分类器权重和样本权重的分析(二分类问题)

关于弱分类器的权重，由于每个弱分类器的分类性能要好于随机分类器，故而误差率 $e_t<0.5$ ， $\alpha_t>0$ 且 $\alpha_t$ 随着 $e_t$ 的减小而增大，所以，分类误差率越小的弱分类器在最终的分类器中所占的权重越大。

对于被被弱分类器正确分类的样本，有：

$y_if_t(x_i) = 1$

对于被弱分类器错误分类的样本，有：

$y_if_t(x_i) = -1$

其中 $y_i$ 代表真实分布， $f_t(x_i)$ 代表弱学习器的预测值即非真实分布。

因此样本权重的更新公式可以写成：
$w_i^{t+1} = \begin{cases} e^{-\alpha_t}*w_i^t & f_t(x_i) = y_i \\ e^{\alpha_t}*w_i^t & f_t(x_i) \neq y_i \\ \end{cases}$
又有：

$e^{-\alpha_t} = e^{-\frac{1}{2}\ln\frac{1-e_t}{e_t}} = \sqrt{\frac{e_t}{1-e_t}}$

由于 $\alpha_t$ 大于0，故而 $e^{-\alpha_t}$ 小于1，分对的样本权重减小； $e^{\alpha_t}$ 大于1，分错的样本权重增大。

AdaBoost多分类

对于多分类问题，流程原理与二分类基本类似。

只是弱学习器的权重为 $\alpha_t = \frac{1}{2}(\ln\frac{1-e_t}{e_t} + \ln(R - 1))$

其中R是类别的数量，对于二分类问题，R=2，于是有了 $\alpha_t = \frac{1}{2}\ln\frac{1-e_t}{e_t}$

对于样本权重的更新，公式为：

$w^t = w^{t-1}*exp(\alpha_t*(y\_true \neq y\_pred))$

对于弱学习器正确分类的样本， $y\_true \neq y\_pred$ 返回False，也就是0，权重不变

对于弱学习器错误分类的样本， $y\_true \neq y\_pred$ 返回True，也就是1，权重放大

对于多分类的输出，我们可以转换成二进制编码，或者叫独热编码，举个例子：

例如三分类，类别一可以用[1,0,0]表示，类别二可以用[0,1,0]表示，类别三可以用[0,0,1]表示。

AdaBoost算例

接下来我们通过一个算例，比较sklearn中AdaBoost算法的计算结果和我们手动计算的结果，进一步了解AdaBoost算法的流程和原理。

给定以下训练样本：

X	0	1	2	3	4	5	6	7	8	9
Y	1	1	1	-1	-1	-1	1	1	1	-1

以sklearn中AdaBoost算法，训练这10个样本数据。

# 导包
from sklearn.ensemble import AdaBoostClassifier
import numpy as np
from sklearn import tree

# 样本数据
X = np.arange(10).reshape(-1,1)
y = np.array([1,1,1,-1,-1,-1,1,1,1,-1])

# 训练和预测数据
ada = AdaBoostClassifier(algorithm='SAMME',n_estimators=3)
ada.fit(X,y)
ada.predict(X)    # 结果为array([ 1,  1,  1, -1, -1, -1,  1,  1,  1, -1])

# 分别画出3棵树
_ = tree.plot_tree(ada[0],filled=True)
ada[0].predict(X)
# _ = tree.plot_tree(ada[0],filled=True)
# ada[0].predict(X)
# _ = tree.plot_tree(ada[0],filled=True)
# ada[0].predict(X)

画出三棵树，我们可以看出依次是从第3个，第9个，第6个样本划分分类。

接下来我们根据上文的公式来看看AdaBoost的算法流程。

初始化，每个样本的权重都为0.1

w1 = np.full(shape = 10,fill_value=0.1)
w1

第一棵树划分前，将10个样本划分为10个阈值，以最小误差率划分。

t = np.arange(0.5,10)
print(t)
for i,t_i in enumerate(t,start = 1):#enumerate,获取索引，默认从0开始， 
#     y_是弱分类器，预测值
    y_ = np.array([1]*i + [-1]*(10-i))
#     print(y_)
    print(t_i,((y !=y_)*w1).sum())

从结果可以看出阈值为2.5或者8.5时误差最小，所以从第三个样本划分。

然后根据公式 $\alpha_t = \frac{1}{2}log{\frac{1-e_t}{e_t}}$ 计算第一个弱学习器的权重

e1 = 0.3
alpha1 = 1/2*np.log((1-e1)/e1)
print('第一个学习器的权重：',alpha1)

得到结果为 0.42364893019360184

接下来更新所有样本的权重 $w_i^t = w_i^{t-1}exp(-y_i\alpha_tf_t(x_i))/Z_t$

y_ = np.array([1]*3 + [-1]*7)    # f(x)
w2 = w1*np.exp(-y*y_*alpha1)
w2 = w2/w2.sum()
print('更新后样本的权重：',w2)

同理，第二棵树和第三棵树也能同样计算出来

第二棵树：

# 根据结果找出从第九棵树划分
t = np.arange(0.5,10)
print(t)
for i,t_i in enumerate(t,start = 1):#enumerate,获取索引，默认从0开始， 
#     y_是弱分类器，预测值
    y_ = np.array([1]*i + [-1]*(10-i))
    print(t_i,((y !=y_)*w2).sum())
    
# 计算第二个弱学习器的权重
e2 = 0.214
alpha2 = 1/2*np.log((1-e2)/e2)
print('第二个学习器的权重：',alpha2)

# 更新样本的权重
y_ = np.array([1]*9 + [-1]*1)    # f(x)
w3 = w2*np.exp(-y*y_*alpha2)
w3 = w3/w3.sum()
print('更新后样本的权重：',w3)

第二棵树是从第九个样本划分，权重是 0.6504903887036776

第三棵树：

t = np.arange(0.5,10)
print(t)
for i,t_i in enumerate(t,start = 1): #enumerate,获取索引，默认从0开始， 
#     y_是弱分类器，预测值
    y_ = np.array([-1]*i + [1]*(10-i))
    print(t_i,((y !=y_)*w3).sum())
    
# 计算第三个弱学习器的权重
e3 = 0.18163
alpha3 = 1/2*np.log((1-e3)/e3)
print('第二个学习器的权重：',alpha3)

# 更新样本的权重
y_ = np.array([-1]*6 + [1]*4)    # f(x)
w4 = w3*np.exp(-y*y_*alpha3)
w4 = w4/w4.sum()
print('更新后样本的权重：',w4)

第三棵树是从第6个样本划分，权重是 0.7526714531563444

接下来将弱学习器组合成强学习器 $F(x) = \sum\limits_{t = 1}^N\alpha_tf_t(x)$

print(alpha1,alpha2,alpha3)
# 0.42364893019360184 0.6504903887036776 0.7526714531563444

# 第一棵树ft(x)
y1 = np.array([1]*3 + [-1]*(10-3))
# 第二棵树的预测值
y2 = np.array([1]*9 + [-1]*(10-9))#预测值
# 第三棵树，预测值
y3 = np.array([-1]*6 + [1]*(10-6))
F =  alpha1*y1 + alpha2*y2 + alpha3*y3
# 将多个弱分类器，整合，变成了强分类器F(X)
F

打印输出结果为：
array([ 0.32146787, 0.32146787, 0.32146787, -0.52582999, -0.52582999,
-0.52582999, 0.97951291, 0.97951291, 0.97951291, -0.32146787])

根据F的结果，划分为类别1和类别-1

result = [-1 if i <0 else 1  for i in F]
result

[1, 1, 1, -1, -1, -1, 1, 1, 1, -1]

结果和sklearn中算法计算的一样！

总结

AdaBoost算是是一种实现简单、易于运用的算法，具有分类精度高，不会出现过拟合的优点，是一种适用于各种分类场景下应用的算法。

AdaBoost算法

AdaBoost二分类问题算法流程

关于弱分类器权重和样本权重的分析(二分类问题)

AdaBoost多分类

AdaBoost算例

总结

推荐阅读更多精彩内容