Adaboost算法及python实战

之前在写

随机森林

的时候大概介绍过boosting算法，今天重点聊一下

Adaboost

AdaBoost是最著名的Boosting族算法，同样也是数据挖掘10大算法之一。是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器，即弱分类器，然后把这些弱分类器集合起来，构造一个更强的最终分类器。算法本身是改变数据分布实现的，它根据每次训练集之中的每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改权值的新数据送给下层分类器进行训练，然后将每次训练得到的分类器融合起来，作为最后的决策分类器。

开始时，所有样本的权重相同，训练得到第一个基分类器。从第二轮开始，每轮开始前都先根据上一轮基分类器的分类效果调整每个样本的权重，上一轮分错的样本权重提高，分对的样本权重降低。之后根据新得到样本的权重指导本轮中的基分类器训练，即在考虑样本不同权重的情况下得到本轮错误率最低的基分类器。重复以上步骤直至训练到约定的轮数结束，每一轮训练得到一个基分类器。

可以想象到，远离边界（超平面）的样本点总是分类正确，而分类边界附近的样本点总是有大概率被弱分类器（基分类器）分错，所以权值会变高，即边界附近的样本点会在分类时得到更多的重视。

下面我们说一下Adaboost的算法，主要参考李航《统计学习方法》

我们用书中的一组数据来进行实际计算下，方便大家了解算法：

数据集D共有10条数据，根据x的输入得到的y可以分类两类，即y=1与y=-1。我们每一轮使用最简单的决策树桩来构建基分类器，即每轮设定一个阈值θ，只要xθ就判定为负类(y=-1)。(或者只要xθ就判定为负类(y=1))

第一轮

D1(x)

因为是第一轮，故所有样本的权重相同1/10(0.1)：

D1(x⃗ )=

最终要选择一个令ϵ1取得最小值的θ与分类方法，这9个值在两种分类方法下，此层g1的错误率分别为：

α1

第一层基分类器G1的权重α1：

α1=1/2*log(1−ϵ1)/ϵ1=0.4236

第二轮

D2(x)

第一轮训练完成后对D1(x)进行更新得到D2(x)，更新公式的推导过程也是等到后边的推到部分再说，此处还是只要知道通过下边的公式来计算更新即可：

上一轮中x=6、7、8的点分错了，可以看到这三个点在D2中的权重变大了，而其余分类正确的点权重变小了。

整个模型（现在有两个基分类器）的准确率仍然为：P(D)=0.7

第三轮

D3(x)

使用D2(x)更新得到D3(x)如下：

D3(x)=

上一轮中x=3、4、5的点被分错，所以在D3中的权重变大，其余分类正确的点权重变小。

依然使用如下公式进行计算：

α3=1/2*log(1−ϵ1)/ϵ1=0.752

继续根据如下公式计算G(x)，此时T为3：

G(x)=

sign(G(x))=

整个模型（现在有三个基分类器）的准确率为：P(D)=1

至此，我们只用了3个弱（基）分类器就在样本集D上得到了100%的准确率，总结一下：

•在第t轮被分错的样本，在下一轮更新得到的Dt+1(x)中权值将被增大

•在第t轮被分对的样本，在下一轮更新得到的Dt+1(x)中权值将被减小

•所使用的决策树桩总是选取让错误率ϵt（所有被Gt分类错误的样本在Dt(x)中对应的权值之和）最低的阈值来设计基本分类器

•最终Adboost得到的G(x)为：

sign(H(x))=sign(0.4236∗g1+0.6496∗g2+0.752∗g3)

接下来我们用SKlearn里面的例子来看下效果(python用anaconda进行展示)：

从结果看AdaBoost准确性不是最高的，当然这也与样本有关，大家也可以根据自己的需要选择合适的模型。