如果Boosting 你懂、那 Adaboost你懂么?

作者:崔家华

编辑:王抒伟

转载请注明作者和出处:

https://zhuanlan.zhihu.com/ml-jack

机器学习知乎专栏:

https://zhuanlan.zhihu.com/ml-jack

CSDN博客专栏:

http://blog.csdn.net/column/details/16415.html

Github代码获取:

https://github.com/Jack-Cherish/Machine-Learning/

Python版本:

Python3.x

运行平台:

Windows

IDE:

Sublime text3

全篇概述:

前面的文章已经介绍了五中不同的分类器,它们各有优缺点。我们可以很自然地将不同的分类器组合起来,而这种组合结果则被成为集成方法(ensemble method)或者元算法(meta-algorithm)。

使用集成方法时会有多种形式:可以是不同算法的集成,也可以是同一种算法在不同设置下的集成,还可以是数据集不同部分分配给不同分类器之后的集成。

本文出现的所有代码和数据集,均可在我的github上下载,欢迎Follow、Star:https://github.com/Jack-Cherish/Machine-Learning

集成方法:

分析:

集成方法(ensemble method)通过组合多个基分类器(base classifier)来完成学习任务,颇有点“三个臭皮匠顶个诸葛亮”的意味。基分类器一般采用的是弱可学习(weakly learnable)分类器,通过集成方法,组合成一个强可学习(strongly learnable)分类器。

所谓弱可学习,是指学习的正确率仅略优于随机猜测的多项式学习算法;强可学习指正确率较高的多项式学习算法。

集成学习的泛化能力一般比单一的基分类器要好,这是因为大部分基分类器都分类错误的概率远低于单一基分类器的.

集成方法主要包括Bagging和Boosting两种方法,Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来,形成一个性能更加强大的分类器,更准确的说这是一种分类算法的组装方法,即将弱分类器组装成强分类器的方法

1、Bagging:

自举汇聚法(bootstrap aggregating),也称为bagging方法。Bagging对训练数据采用自举采样(boostrap sampling),即有放回地采样数据,主要思想:

  • 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本(在训练集中,有些样本可能被多次抽取到,而有些样本可能一次都没有被抽中),共进行k轮抽取,得到k个训练集。(k个训练集之间是相互独立的)
  • 每次使用一个训练集得到一个模型,k个训练集共得到k个模型。(注:这里并没有具体的分类算法或回归方法,我们可以根据具体问题采用不同的分类或回归方法,如决策树、感知器等)
  • 对分类问题:将上步得到的k个模型采用投票的方式得到分类结果;对回归问题,计算上述模型的均值作为最后的结果。(所有模型的重要性相同)

2、Boosting

Boosting是一种与Bagging很类似的技术。Boosting的思路则是采用重赋权(re-weighting)法迭代地训练基分类器,主要思想:

  • 每一轮的训练数据样本赋予一个权重,并且每一轮样本的权值分布依赖上一轮的分类结果。

基分类器之间采用序列式的线性加权方式进行组合。

3、Bagging、Boosting二者之间的区别

样本选择上:

  • Bagging:训练集是在原始集中有放回选取的,从原始集中选出的各轮训练集之间是独立的。
  • Boosting:每一轮的训练集不变,只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

样例权重:

  • Bagging:使用均匀取样,每个样例的权重相等。
  • Boosting:根据错误率不断调整样例的权值,错误率越大则权重越大。

预测函数:

  • Bagging:所有预测函数的权重相等。
  • Boosting:每个弱分类器都有相应的权重,对于分类误差小的分类器会有更大的权重。

并行计算:

  • Bagging:各个预测函数可以并行生成。
  • Boosting:各个预测函数只能顺序生成,因为后一个模型参数需要前一轮模型的结果。

4、总结

这两种方法都是把若干个分类器整合为一个分类器的方法,只是整合的方式不一样,最终得到不一样的效果,将不同的分类算法套入到此类算法框架中一定程度上会提高了原单一分类器的分类效果,但是也增大了计算量。

下面是将决策树与这些算法框架进行结合所得到的新的算法:

  • Bagging + 决策树 = 随机森林
  • AdaBoost + 决策树 = 提升树
  • Gradient Boosting + 决策树 = GBDT

集成方法众多,本文主要关注Boosting方法中的一种最流行的版本,即AdaBoost,让我们一探究竟!

AdaBoost算法:

AdaBoost算法是基于Boosting思想的机器学习算法,AdaBoost是adaptive boosting(自适应boosting)的缩写,其运行过程如下:

1、计算样本权重

训练数据中的每个样本,赋予其权重,即样本权重,用向量D表示,这些权重都初始化成相等值。假设有n个样本的训练集:

设定每个样本的权重都是相等的,即1/n。

2、计算错误率

利用第一个弱学习算法h1对其进行学习,学习完成后进行错误率ε的统计:

3、计算弱学习算法权重

弱学习算法也有一个权重,用向量α表示,利用错误率计算权重α:

4、更新样本权重

在第一次学习完成后,需要重新调整样本的权重,以使得在第一分类中被错分的 样本的权重,在接下来的学习中可以重点对其进行学习:

其中,h_t(x_i) = y_i表示对第i个样本训练正确,不等于则表示分类错误。Z_t是一个归一化因子:

这个公式我们可以继续化简,将两个公式进行合并,化简如下:

5、AdaBoost算法

重复进行学习,这样经过t轮的学习后,就会得到t个弱学习算法、权重、弱分类器的输出以及最终的AdaBoost算法的输出,分别如下:

其中,sign(x)是符号函数。具体过程如下所示:

AdaBoost算法总结如下:

基于单层决策树构建弱分类:

建立AdaBoost算法之前,我们必须先建立弱分类器,并保存样本的权重。弱分类器使用单层决策树(decision stump),也称决策树桩,它是一种简单的决策树,通过给定的阈值,进行分类。

1、数据集可视化

为了训练单层决策树,我们需要创建一个训练集,编写代码如下:

点击图片放大查看代码

现在来看看代码运行结果:

可以看到,如果想要试着从某个坐标轴上选择一个值(即选择一条与坐标轴平行的直线)来将所有的蓝色圆点和橘色圆点分开,这显然是不可能的。这就是单层决策树难以处理的一个著名问题。通过使用多颗单层决策树,我们可以构建出一个能够对该数据集完全正确分类的分类器。

2、构建单层决策树

我们设置一个分类阈值,比如我横向切分,如下图所示:

蓝横线上边的是一个类别,蓝横线下边是一个类别

显然,此时有一个蓝点分类错误,计算此时的分类误差,误差为1/5 = 0.2。这个横线与坐标轴的y轴的交点,就是我们设置的阈值,通过不断改变阈值的大小,找到使单层决策树的分类误差最小的阈值。同理,竖线也是如此,找到最佳分类的阈值,就找到了最佳单层决策树,编写代码如下:

点击图片放大查看代码

代码运行结果如下:

代码不难理解,就是通过遍历,改变不同的阈值,计算最终的分类误差,找到分类误差最小的分类方式,即为我们要找的最佳单层决策树。

这里lt表示less than,表示分类方式,对于小于阈值的样本点赋值为-1,gt表示greater than,也是表示分类方式,对于大于阈值的样本点赋值为-1。

经过遍历,我们找到,训练好的最佳单层决策树的最小分类误差为0.2,就是对于该数据集,无论用什么样的单层决策树,分类误差最小就是0.2。

这就是我们训练好的弱分类器。

接下来,使用AdaBoost算法提升分类器性能,将分类误差缩短到0,看下AdaBoost算法是如何实现的。

好长好长累了吧? 快给作者和编辑鼓掌!!!

还有么? 有!!!

未完待续。。。

还有adaboost(二)、(三)?

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-10-25

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

干货 | 深度学习之卷积神经网络(CNN)的前向传播算法详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 在(干货 | 深度学习之卷积神...

3535
来自专栏Pytorch实践

深度学习之句子表达

在之前的文章里,我们介绍了词语表达的训练,使用skip-gram模型训练word2vec。既然词语能表达,那句子也同样能被分布式的向量表示。这里主要介绍几种句子...

42211
来自专栏机器之心

入门 | 一文了解神经网络中的梯度爆炸

3408
来自专栏智能算法

机器学习三人行(系列九)----千变万化的组合算法(附代码)

上节中我们讲解了决策树的使用: 机器学习三人行(系列八)----神奇的分类回归决策树(附代码) 本文我们在决策树的基础上,更进一步的讨论由常用机器学习算法进行组...

36210
来自专栏企鹅号快讯

深入机器学习系列8-Gradient-boosted tree

梯度提升树 1 Boosting   是一类将弱学习器提升为强学习器的算法。这类算法的工作机制类似:先从初始训练集中训练出一个基学习器,再根据基学习器的表现对训...

2016
来自专栏人工智能LeadAI

Bagging

1624
来自专栏AI研习社

完全图解RNN、RNN变体、Seq2Seq、Attention机制

本文主要是利用图片的形式,详细地介绍了经典的RNN、RNN几个重要变体,以及Seq2Seq模型、Attention机制。希望这篇文章能够提供一个全新的视角,帮助...

3835
来自专栏机器学习算法与Python学习

SoftMax回归详解

Contents 1 关键词 2 引言 3 代价函数 4 softmax回归模型参数化的特点 5 权重衰减 6 softmax与logistics回归的关系 1...

3378
来自专栏marsggbo

DeepLearning.ai学习笔记(四)卷积神经网络 -- week1 卷积神经网络基础知识介绍

一、计算机视觉 ? 如图示,之前课程中介绍的都是64* 64 3的图像,而一旦图像质量增加,例如变成1000 1000 * 3的时候那么此时的神经网络的计...

20210
来自专栏大数据挖掘DT机器学习

Python的机器学习实战:AadBoost

目录: 1. Boosting方法的简介 2. AdaBoost算法 3.基于单层决策树构建弱分类器 4.完整的AdaBoost的算法实现 5.总结 1. B...

2063

扫码关注云+社区