机器学习算法总结--提升方法

转自:http://blog.****.net/lc013/article/details/56481016

参考自:

简介

提升方法(boosting)是一种常用的统计学习方法,在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提供分类的性能。

boosting和bagging

boosting和bagging都是集成学习(ensemble learning)领域的基本算法boosting和bagging使用的多个分类器的类型是一致的。

Bagging

bagging也叫自助汇聚法(bootstrap aggregating),比如原数据集中有N个样本,我们每次从原数据集中有放回的抽取,抽取N次,就得到了一个新的有N个样本的数据集,然后我们抽取S个N次,就得到了S个有N个样本的新数据集,然后拿这S个数据集去训练S个分类器,之后应用这S个分类器进行分类,选择分类器投票最多的类别作为最后的分类结果。一般来说自助样本的包含有63%的原始训练数据,因为:

假设共抽取个样本,则次都没有抽到的概率是

则一个样本被抽到的概率有

所以,当很大时有:

这样,在一次bootstrap的过程中,会有36%的样本没有被采样到,它们被称为out-off-bag(oob),这是自助采样带给bagging的里一个优点,因为我们可以用oob进行“包外估计”out-of-bag estimate

bagging通过降低基分类器的方差改善了泛化误差,bagging的性能依赖于基分类器的稳定性。如果基分类器是不稳定的,bagging**有助于减少训练数据的随机波动导致的误差,如果基分类器是稳定的,即对训练数据集中的微小变化是鲁棒的,则组合分类器的误差主要由基分类器偏移所引起的,这种情况下,**bagging可能不会对基分类器有明显的改进效果,甚至可能降低分类器的性能。

boosting与bagging的区别

  • bagging通过有放回的抽取得到了S个数据集,而boosting用的始终是原数据集,但是样本的权重会发生改变。
  • boosting对分类器的训练是串行的,每个新分类器的训练都会受到上一个分类器分类结果的影响。
  • bagging里面各个分类器的权重是相等的,但是boosting不是,每个分类器的权重代表的是其对应分类器在上一轮分类中的成功度。

AdaBoost是boosting方法中最流行的版本

AdaBoosts算法

AdaBoost(adaptive boosting)是元算法,通过组合多个弱分类器来构建一个强分类器。我们为训练数据中的每一个样本都赋予其一个权重,这些权重构成了向量,一开始,这些权重都初始化成相等值,然后每次添加一个弱分类器对样本进行分类,从第二次分类开始,将上一次分错的样本的权重提高,分对的样本权重降低,持续迭代。此外,对于每个弱分类器而言,每个分类器也有自己的权重,取决于它分类的加权错误率,加权错误率越低,则这个分类器的权重值越高,最后综合多个弱分类器的分类结果和其对应的权重得到预测结果,AdaBoost是最好的监督学习分类方法之一。

其算法过程如下所示:

机器学习算法总结--提升方法

其中,注意:

机器学习算法总结--提升方法

训练误差分析

AdaBoost算法的最基本性质是在学习过程中不断减小训练误差,对训练误差的上界有如下定理:

定理1:AdaBoost最终分类器的训练误差界为: 


定理2:二类分类问题 

算法解释

AdaBoost算法还可以解释为模型是加法模型,损失函数是指数函数,学习算法是前向分步算法的二类分类学习方法。

加法模型是形如的函数形式,其中是基函数,而是基函数的系数,是基函数的参数。对于AdaBoost算法,其基本分类器的线性组合为正是一个加法模型。

AdaBoost算法的损失函数是指数函数,公式为

此外,经过轮迭代可以得到。而前向分步算法的过程如下所示:

机器学习算法总结--提升方法

通过上述步骤,前向分步算法将同时求解从所有参数的优化问题简化为逐步求解各个的优化问题。

优缺点

优点

  1. 泛化误差低
  2. 容易实现,分类准确率较高,没有太多参数可以调

缺点

对异常值比较敏感