Machine Learning -- Boosting

本来想写随机森林的但是由于其中用到了太多提升的思想,所以就先整理整理提升的相关概念。

Boosting方法是一种用来提高弱分类算法准确度的方法,这种方法通过构造一个预测函数系列,然后以一定的方式将他们组合成一个预测函数。Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于 Valiant提出的 PAC ( Probably Approxi mately Correct)学习模型。

Boosting算法起源

Boosting是一种提高任意给定学习算法准确度的方法。它的思想起源于 Valiant提出的 PAC ( Probably Approximately Correct)学习模型。Valiant和 Kearns提出了弱学习和强学习的概念 ,识别错误率小于1/2,也即准确率仅比随机猜测略高的学习算法称为弱学习算法;识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。同时 ,Valiant和 Kearns首次提出了 PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 ,而不必寻找很难获得的强学习算法。1990年, Schapire最先构造出一种多项式级的算法 ,对该问题做了肯定的证明 ,这就是最初的 Boosting算法。一年后 ,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷 ,那就是都要求事先知道弱学习算法学习正确的下限。1995年 , Freund和 schap ire改进了Boosting算法 ,提出了 AdaBoost (Adap tive Boosting)算法[ 5 ],该算法效率和 Freund于 1991年提出的 Boosting算法几乎相同 ,但不需要任何关于弱学习器的先验知识 ,因而更容易应用到实际问题当中。之后 , Freund和 schapire进一步提出了改变 Boosting投票权重的 AdaBoost . M1,AdaBoost . M2等算法 ,在机器学习领域受到了极大的关注。

Boosting方法概述

Boosting方法是一种用来提高弱分类算法准确度的方法,这种方法通过构造一个预测函数系列,然后以一定的方式将他们组合成一个预测函数。他是一种框架算法,主要是通过对样本集的操作获得样本子集,然后用弱分类算法在样本子集上训练生成一系列的基分类器。他可以用来提高其他弱分类算法的识别率,也就是将其他的弱分类算法作为基分类算法放于Boosting 框架中,通过Boosting框架对训练样本集的操作,得到不同的训练样本子集,用该样本子集去训练生成基分类器;每得到一个样本集就用该基分类算法在该样本集上产生一个基分类器,这样在给定训练轮数 n 后,就可产生 n 个基分类器,然后Boosting框架算法将这 n个基分类器进行加权融合,产生一个最后的结果分类器,在这 n个基分类器中,每个单个的分类器的识别率不一定很高,但他们联合后的结果有很高的识别率,这样便提高了该弱分类算法的识别率。在产生单个的基分类器时可用相同的分类算法,也可用不同的分类算法,这些算法一般是不稳定的弱分类算法,如神经网络(BP) ,决策树(C4.5)等。

Adaboost算法

由于Boosting算法在解决实际问题时有一个重大的缺陷,即他们都要求事先知道弱分类算法分类正确率的下限,这在实际问题中很难做到。后来 Freund 和 Schapire提出了 AdaBoost 算法,该算法的效率与 Freund 方法的效率几乎一样,却可以非常容易地应用到实际问题中。AdaBoost 是Boosting 算法家族中代表算法,AdaBoost 主要是在整个训练集上维护一个分布权值向量 D( x) t ,用赋予权重的训练集通过弱分类算法产生分类假设 Ht ( x) ,即基分类器,然后计算他的错误率,用得到的错误率去更新分布权值向量 D( x) t ,对错误分类的样本分配更大的权值,正确分类的样本赋予更小的权值。每次更新后用相同的弱分类算法产生新的分类假设,这些分类假设的序列构成多分类器。对这些多分类器用加权的方法进行联合,最后得到决策结果。这种方法不要求产生的单个分类器有高的识别率,即不要求寻找识别率很高的基分类算法,只要产生的基分类器的识别率大于 0.5 ,就可作为该多分类器序列中的一员。

寻找多个识别率不是很高的弱分类算法比寻找一个识别率很高的强分类算法要容易得多,AdaBoost 算法的任务就是完成将容易找到的识别率不高的弱分类算法提升为识别率很高的强分类算法,这也是 AdaBoost 算法的核心指导思想所在,如果算法完成了这个任务,那么在分类时,只要找到一个比随机猜测略好的弱分类算法,就可以将其提升为强分类算法,而不必直接去找通常情况下很难获得的强分类算法。通过产生多分类器最后联合的方法提升弱分类算法,让他变为强的分类算法,也就是给定一个弱的学习算法和训练集,在训练集的不同子集上,多次调用弱学习算法,最终按加权方式联合多次弱学习算法的预测结果得到最终学习结果。包含以下2 点:

样本的权重

AdaBoost 通过对样本集的操作来训练产生不同的分类器,他是通过更新分布权值向量来改变样本权重的,也就是提高分错样本的权重,重点对分错样本进行训练。

(1) 没有先验知识的情况下,初始的分布应为等概分布,也就是训练集如果有 n个样本,每个样本的分布概率为1/ n。

(2)每次循环后提高错误样本的分布概率,分错的样本在训练集中所占权重增大,使得下一次循环的基分类器能够集中力量对这些错误样本进行判断。

弱分类器的权重

最后的强分类器是通过多个基分类器联合得到的,因此在最后联合时各个基分类器所起的作用对联合结果有很大的影响,因为不同基分类器的识别率不同,他的作用就应该不同,这里通过权值体现他的作用,因此识别率越高的基分类器权重越高,识别率越低的基分类器权重越低。权值计算如下:

基分类器的错误率:

e = ∑( ht ( x i) ≠yi) Di (1)

基分类器的权重:W t = F( e) ,由基分类器的错误率计算他的权重。

算法流程及伪码描述

算法流程描述

算法流程可用结构图 1 描述,如图 1 所示 AdaBoost重复调用弱学习算法(多轮调用产生多个分类器) ,首轮调用弱学习算法时,按均匀分布从样本集中选取子集作为该次训练集,以后每轮对前一轮训练失败的样本,赋予较大的分布权值( Di 为第i 轮各个样本在样本集中参与训练的概率) ,使其在这一轮训练出现的概率增加,即在后面的训练学习中集中对比较难训练的样本进行学习,从而得到 T个弱的基分类器, h1 , h2 , …, ht ,其中 ht 有相应的权值 w t ,并且其权值大小根据该分类器的效果而定。最后的分类器由生成的多个分类器加权联合产生。

图 1 算法流程

算法伪码描述

输入: S = { ( x1 , y1 ) , …( x i , y i) …, ( x n , y n) } , x i ∈X,yi ∈Y ;训练轮数为 T; 初始化分发权值向量:

(2)

for t = 1 , …, T :

(1) 使用分发权值向量 Dt训练基分类器ht = R( x , y ,Dt) ; R为一弱的分类算法;

(2) 计算错误率:e = ∑( ht ( x i) ≠y i) Di (3)

(3) if e≥ 015 ,break ;

(4) 计算基分类器的权值 ht :wt ∈w;

(5) 更新权值:Dt+1 ( i) = Dt ( i) ×F( e) (4)

其中 F( x)为更新函数,他以该次得到的基分类器的分类

错误率 e为自变量;

(6) 将多个基分类器进行联合,输出最后的分类器。

在上面的算法中:

①x i ∈X , yi ∈Y , x i 表示样本属性组成的向量, yi 表示该样本的类别标签;

②Dt 为样本的分发权值向量:没有先验知识的情况下,初始的分布应为等概率分

布,也就是训练集如果有 n个样本,每个样本的分布概率为1/ n;

每次循环后提高错误样本的分布概率,分错的样本在训练集中所占权重增大,使得下一次循环的弱学习算法能

够集中对这些错误样本进行判断;Dt 总和应该为1 ;

③wt 为分类器的权值:准确率越高的分类器权重 w越大。

主要以Adaboost为例,首先来看看Adaboost的流程图,如下:

从图中可以看到,在训练过程中我们需要训练出多个弱分类器(图中为3个),每个弱分类器是由不同权重的样本(图中为5个训练样本)训练得到(其中第一个弱分类器对应输入样本的权值是一样的),而每个弱分类器对最终分类结果的作用也不同,是通过加权平均输出的,权值见上图中三角形里面的数值。那么这些弱分类器和其对应的权值是怎样训练出来的呢?

  下面通过一个例子来简单说明。

  书中(machine learning in action)假设的是5个训练样本,每个训练样本的维度为2,在训练第一个分类器时5个样本的权重各为0.2. 注意这里样本的权值和最终训练的弱分类器组对应的权值α是不同的,样本的权重只在训练过程中用到,而α在训练过程和测试过程都有用到。

  现在假设弱分类器是带一个节点的简单决策树,该决策树会选择2个属性(假设只有2个属性)的一个,然后计算出这个属性中的最佳值用来分类。

  Adaboost的简单版本训练过程如下:

  1. 训练第一个分类器,样本的权值D为相同的均值。通过一个弱分类器,得到这5个样本(请对应书中的例子来看,依旧是machine learning in action)的分类预测标签。与给出的样本真实标签对比,就可能出现误差(即错误)。如果某个样本预测错误,则它对应的错误值为该样本的权重,如果分类正确,则错误值为0. 最后累加5个样本的错误率之和,记为ε。

  2. 通过ε来计算该弱分类器的权重α,公式如下:

  3. 通过α来计算训练下一个弱分类器样本的权重D,如果对应样本分类正确,则减小该样本的权重,公式为:

  如果样本分类错误,则增加该样本的权重,公式为:

  4. 循环步骤1,2,3来继续训练多个分类器,只是其D值不同而已。

  测试过程如下:

  输入一个样本到训练好的每个弱分类中,则每个弱分类都对应一个输出标签,然后该标签乘以对应的α,最后求和得到值的符号即为预测标签值。

Boosting算法的优点:

  低泛化误差;

  容易实现,分类准确率较高,没有太多参数可以调;

缺点:

  对outlier比较敏感;

本文分享自微信公众号 - 机器学习算法与Python学习(guodongwei1991),作者:guodongwe1991

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-06-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货 | 机器学习算法大总结(ML岗面试常考)

    键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 找工作时(IT行业),除了常见的软件...

    昱良
  • 精华 | 机器学习岗面试,这些是基础!(ML,DL,SL相关知识整理)

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 明天推出第3期送书活动 数量10本 ...

    昱良
  • 【算法面经】重读:机器学习面试算法梳理

    找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究方向是机器学习/数据挖掘之类,且...

    昱良
  • 【干货】数据挖掘的10大分析方法

    1.C4.5 C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法.C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进...

    CDA数据分析师
  • 真正想做算法的,不要害怕内卷

    也不知道从啥时候开始,内卷这个词就火起来了。具体到数据和算法等技术岗位方面,内卷可以理解为一年比一年高的入行门槛以及愈发激烈的同行竞争。比如说前段时间知乎上的一...

    石晓文
  • 谈下程序设计算法的准备心得与体会-nCov隔离也许帮你提升能力

    1.上班的时候一直在奔跑,现在总算可以有集中的时间来思考一些之前一直没能好好整理的内容

    麦克-堂
  • 【学习】数据挖掘领域十大经典算法

    数据挖掘 国际权威的学术组织ICDM,于06年12月年评选出的数据挖掘领域的十大经典算法: ? 1 C4.5 分类决策树算法 决策树构造方法其实就是每次选择一个...

    小莹莹
  • 机器学习萌新必学的Top10算法

    Spark学习技巧
  • 机器学习萌新必学的Top10算法

    导读:在机器学习领域里,不存在一种万能的算法可以完美解决所有问题,尤其是像预测建模的监督学习里。

    华章科技
  • 机器学习常见算法及优缺点!

    2、使用基于决策树的combination算法,如bagging算法,randomforest算法,可以解决过拟合的问题。

    Datawhale

扫码关注云+社区

领取腾讯云代金券