机器学习 Adaboost算法

01

—

Boosting

Boosting的基本思想是将若干个弱分类器(base learner)组合起来，变成一个强分类器，它需要回答2个问题:

如何改变训练数据的权值分布

如何将弱分类器组合起来

常见的Boosting算法有，Adaboost，和以Boosting decision tree 为代表的Gradient boosting，Xgboost 等，这些算法，清参考：

02

—

Adaboost算法

全称 Adaptive Boosting 自适应增强，前一个基分类器分错的样本权值会得到增强，分对的权值减弱，得到样本点的新权值分布，并用于下一次迭代。算法简单来说分为3步：

初始化训练数据的权值分布；

训练若分类器；

将步骤2中得到的弱分类器组合。

03

—

例子

这个例子参考csdn博客，经过精简重写，可能更加容易理解adaboost算法的迭代过程，以及观察分对样本权值减少，反之增大。

训练之前，各个样本的权值都一样，D1 = (0.1, 0.1,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1)；

第一轮迭代：x在2和3间分割

样本“6 7 8”被分错，对应的误差率e1=P(G1(xi)≠yi) = 3*0.1 = 0.3；

此第一个基本分类器在最终的分类器中所占的权重为 a1 = 0.4236；

样本新的权值为D2= (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715,0.1666, 0.1666, 0.1666, 0.0715)；

第二轮迭代：x在8和9间分割

样本“3 4 5”被分错，对应的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143；

第二个分类器所占权重为a2 = 0.6496；

样本新的权值为D3= (0.0455, 0.0455, 0.0455,0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)；

第三轮迭代：x在5和6间分割

样本“0 1 2 9”被分错，对应的误差率e3= P(G3(xi)≠yi) = 0.0455*4 = 0.1820；

第三个基本分类器所占的权重为a3 = 0.7514；

样本新的权值为D4= (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065,0.125)。

最终得到的分类器为：0.4236*G1(x) +0.6496*G2(x) +0.7514*G3(x)

其中，G1(x) = 1 , x2.5

10个样本点带入最终的分类器，分类的结果都是正确的。

04

—

再进一步

上面的例子足够精简了，特征x的分割点，通过肉眼基本便能观察出怎么分割，误差会最小，但是问题是实际任务中，数据集会含有多个特征，每次迭代该选取哪个特征呢？分割点在哪里？

在每一轮训练过程中，在每个属性上根据分割的阈值不同得到多个单层分类器，在这些分类器中选取一个带权误差率最小的单层分类器作为该轮训练的弱分类器。

一般只进行一次判定，可以包含两个或者多个叶结点，可以选择属性的一个阈值做为分割点进行判定，大于该阈值分配到一类，小于该阈值分配到另一类；当然也可以选取多个阈值并由此得到多个叶结点。

算法channel会有系统地，认真地推送：机器学习（包含深度学习，强化学习等）的理论，算法，实践，源码实现。期待您的参与！