AdaBoost算法

AdaBoost算法简介

AdaBoost算法的全称是自适应Boosting(Adaptive Boosting),是一种二分类器,它用弱分类器的线性组合构造强分类器。弱分类器的性能不用太好,只需要比随机猜测强,依靠它们可以构造出一个非常准确的强分类器。强分类器的计算公式为:

其中x是输入向量,F(x)是强分类器,f_{(x)}是弱分类器, a_{(t)}是弱分类器的权重值,是一个正数,T为弱分类器的数量。弱分类器的输出值为+1或-1,分别对应于正样本和负样本。分类时的判定规则为:

其中sgn是符号函数。强分类器的输出值也为+1或-1,同样对应于正样本和负样本。弱分类器和它们的权重值通过训练算法得到。之所以叫弱分类器是因为它们的精度不用太高。

训练算法

训练时,依次训练每一个弱分类器,并得到它们的权重值。训练样本同样带有权重,初始时所有样本的权重相等,被前面的弱分类器错分的样本会加大权重,反之会减小权重,因此接下来的弱分类器会更加关注这些难分的样本。弱分类器的权重值根据它的准确率构造,精度越高的弱分类器权重越大。给定l个训练样本( [公式] , [公式] ),其中 [公式] 是特征向量, [公式] 为类别标签,其值为+1或-1。训练算法的流程如下:

初始化样本权重值,所有样本的初始权重相等:

循环,对t=1,…,T依次训练每个弱分类器:

训练一个弱分类器 f_{(x)},并计算它对训练样本集的错误率 e_{t}

计算弱分类器的权重:

更新所有样本的权重:

其中Z_{t}为归一化因子,它是所有样本的权重之和:

结束循环

最后得到强分类器:

根据弱分类器权重的计算公式,错误率低的弱分类器权重大,它是准确率的增函数。在SIGAI之前的公众号文章“大话AdaBoost算法”中,我们给出了一个形象的例子。每个弱分类器类似于一个水平不太高的医生,如果在之前的考核中一个医生的技术更好,对病人情况的判断更准确,那么可以加大他在会诊时说话的分量即权重。而强分类器就是这些医生的结合。

给训练样本加权重是有必要的,如果样本没有权重,每个弱分类器的训练样本是相同的,训练出来的弱分类器也是一样的,这样训练多个弱分类器没有意义。AdaBoost算法的原则是:

关注之前被错分的样本,准确率高的弱分类器有更大的权重。

上面的算法中并没有说明弱分类器是什么样的,具体实现时我们应该选择什么样的分类器作为弱分类器?一般用深度很小的决策树。强分类器是弱分类器的线性组合,如果弱分类器是线性函数,无论怎样组合,强分类器都是线性的,因此应该选择非线性的分类器做弱分类器。

训练算法的推导

AdaBoost看上去是一个脑洞大开想出来的算法,你可能会问:为什么弱分类器的权重计算公式是这样的?为什么样本权重的更新公式是这样的?事实上,它们是有来历的。我们可以用广义加法模型+指数损失函数来推导出AdaBoost的训练算法。

广义加法模型拟合的目标函数是多个基函数的线性组合:

其中 ,\gamma _{i}为基函数的参数, \beta _{i}为基函数的权重系数。训练时这个模型要确定的是基函数的参数和权重值。训练的目标是最小化对所有样本的损失函数:

这是指数损失函数。如果标签值与强分类器的预测值越接近,损失函数的值越小,反之越大。使用指数损失函数而不用均方误差损失函数的原因是均方误差损失函数对分类问题的效果不好。将广义加法模型的拟合函数代入指数损失函数中,得到算法训练弱分类器时要优化的目标函数为:

这里将指数函数拆成了两部分,已有的强分类器,以及当前弱分类器对训练样本的损失函数,前者在之前的迭代中已经求出,可以看成常数。目标函数可以简化为:

其中:

它只和前面的迭代得到的强分类器有关,与当前的弱分类器、弱分类器权重无关,这就是样本权重。这个最优化问题可以分两步求解,首先将 \beta看成常数,由于 y_{i}F_{(x)}的取值只能为+1或-1,要让上面的目标函数最小化,必须让二者相等。因此损失函数对f(x)的最优解为:

其中I是指标函数,根据括号里的条件是否成立其取值为0或1。上式的最优解是使得对样本的加权误差率最小的分类器。得到弱分类器之后,优化目标可以表示成\beta 的函数:

上式前半部分是被正确分类的样本,后半部分是被错误分类的样本。这可以写成:

具体推导过程为:

函数在极值点的导数为0,即:

由此得到关于\beta的方程:

最优解为:

其中 eer_{j}为弱分类器对训练样本集的加权错误率:

对逼近函数做如下更新:

导致下次迭代时样本的权重为:

这就是样本权重的更新公式。AdaBoost训练算法就是求解上述最优化问题的过程

热门文章

暂无图片
编程学习 ·

mogodb日常工作记录

查询相关 db.getCollection(Examda_News_VisitLog).find({"newsId":"20061109480192959"})db.getCollection(Examda_News_VisitLog).find({"from":"xcx","share":{"$gt":0}}).limit(10); # status: "A"…
暂无图片
编程学习 ·

Spring Boot整合Zookeeper实现配置中心

简介 使用背景 说到配置中心,目前市面上用的较多的配置中心都广为人知,比如百度的Disconf、Spring Cloud Config、携程的Apollo、阿里的Nacos等。由于项目组一直是使用的zookeeper作为配置中心,所以来学习使用。 实现原理在Zookeeper建立一个根节点,比如/CONFIG,代表某个配…
暂无图片
编程学习 ·

python学习记录

变量和简单数据类型 message="Hello Python world!" print(message)message就是一个变量,绿色部分用双引号括起来的(也可以用单引号)就是一个字符串。变量的命名和使用: 1.变量名只能包含字母、数字和下划线。字母下划线可以打头数字不可以。 2.变量名不能包含空…
暂无图片
编程学习 ·

ssm学习笔记——spring——AOP配置

spring中基于XMl的AOP配置1、把通知的bean也交给spring来管理2、使用aop:config标签表明开始AOP配置3、使用aop:aspect标签表明配置切面id属性:给切面提供唯一标识ref属性:是指定通知类的Id4、在aop:aspect标签的内部使用对应标签来配置通知的类型示例:让printLog方法在切…
暂无图片
编程学习 ·

Python使用Request库实现PC端学小易(适用app版本1.0.6)

Python使用Request库实现PC端学小易app(适用app版本1.0.6)前言抓包登录操作抓包搜题操作抓包数据分析登录搜题重点代码实现导入库tkinter实现简易图形界面部分request库实现登录部分搜题部分整理输出至tkinter部分完整代码重点 前言 一直以来学小易只有安卓段与IOS端的app,在…
暂无图片
编程学习 ·

【面试】如果你这样回答“什么是线程安全”,面试官都会对你刮目相看

不是线程的安全 面试官问:“什么是线程安全”,如果你不能很好的回答,那就请往下看吧。 论语中有句话叫“学而优则仕”,相信很多人都觉得是“学习好了可以做官”。然而,这样理解却是错的。切记望文生义。 同理,“线程安全”也不是指线程的安全,而是指内存的安全。为什么如…
暂无图片
编程学习 ·

Web自动化测试:webdriver所有定位方式详解

在之前章节,我们已接触了webdriver中的8种基础定位方法,但是当我们在pycharm中打出:driver.find时,代码提示中其实是有18个被选项的,这里我们来讲讲剩余这10种定位方法都是什么,以及它们之间存在的关系。 首先有两个万能定位方法: find_element()寻找符合条件的第一个元…
暂无图片
编程学习 ·

Linux安全原理简介

Linux安全原理简介介绍在设置Linux计算机的所有阶段,安全性应是首要考虑之一。要在计算机上实施良好的安全策略,需要对Linux的基础知识以及所使用的某些应用程序和协议有充分的了解。Linux的安全性是一个非常重要的主题,并且有许多有关此主题的完整书籍。我不能在本教程中介…
暂无图片
编程学习 ·

异步FIFO学习

这里写自定义目录标题一、概述二、异步FIFO的设计基础2.1 FIFO指针2.2 格雷码的使用2.2.1 二进制码存在的问题2.2.2 格雷码计数器2.3 空满条件的判断三、异步FIFO设计实现3.1 fifo13.2 fifomem3.3 sync_r2w3.4 sync_w2r3.5 rptr_empty3.6 wptr_full 一、概述 在大规模ASIC或FPG…
暂无图片
编程学习 ·

Spark1.x升级Spark2.x常见异常Kafka篇【TopicMetadataRequest】

一.原因分析 当Spark从1.x升级到2.x时,如果使用SparkStreaming加载Kafka的数据,即使Kafka版本没有变化【一般会有所升级】,对应的spark-streaming-kafka也必须升级到对应版本,访问方式也会有所变化。 此处是从Spark1.6.0升级到Spark2.4.3,Kafka略有升级【从2.1.0升级到2.2…
暂无图片
编程学习 ·

flume采集多个文件夹日志

在flume1.6版本及之前,如果想要监控多个目录下的多个文件,可以使用Filelistener,在flume1.7之后,增加了TAILDIR,主要是监控文件的变化 参考配置: #配置Agent a1 的组件 a1.sources=r1 a1.sinks=s1 a1.channels=c1#描述/配置a1的source1 a1.sources.r1.type=TAILDIR #偏移量…
暂无图片
编程学习 ·

Web自动化测试:页面元素的定位方法

这一节,我们介绍一下页面元素定位的八种方式和如何通过火狐和谷歌浏览器获取元素定位信息.页面元素的定位方法 html页面是有一个个的标签组成的,我们定位元素其实就是定位这些标签。首先来看一下有哪儿几种定位方式:idnameclass nametag namelink textpartial link textxpat…
暂无图片
编程学习 ·

springboot aop 切到service层,不生效

今天发现一个问题,使用aop切到service层方法上,idea会有切成功的标志,编译也不报错,但就是不生效。研究了下发现,是因为我切的方法被同一个service中的其他方法调用,这样的话就不生效了,暂不清楚原因,解决方法时切到调用它的方法上,这只是切点不生效的一种情况,希望能…
暂无图片
编程学习 ·

前端面试题及答案.全全全!!!---js

HTML——CSS——JS——es6——Vue——微信小程序-----------服务器----------nodeJS面试题1.基本数据类型有哪几种?undefined,null,boolean,string,number,Symbol(es6)2.引用数据类型有哪些?Object,Array3.JavaScript的typeof返回的数据类型?string number array object fun…
暂无图片
编程学习 ·

关于HIVE增量同步的思考

方案一、如果业务库没有删除操作,并且更新时间完整,使用更新时间做增量同步,sqoop只同步更新时间变化的数据,合并到ODS层表 方案二、如果业务库有删除操作,可以先解析数据库操作日志,存到hdfs,T+1同步数据后,对增删改做一次merge操作即可,可能需要代码实现。
暂无图片
编程学习 ·

一些CTF 做题的tricks

一些CTF 做题的tricks,东拼西凑放到这里,方便查找 任意文件读取路径汇总任意文件读取漏洞和文件包含漏洞的表现相似,但是任意文件读取不能getshell,可以通过尝试读取相对路径的脚本文件,比如/read.php?file=index.php,如果可以读取到文件源码,说明是文件读取,如果不能…
暂无图片
编程学习 ·

二进制与十进制转换工具类

package util;/*** 二进制工具类* * @author 谢辉* @time 2020.07.01**/ public class BinaryUtil {/*** 十进制数字转二进制* * @param num 十进制数字* @param strResult 结果容器,追加结果用,* @return 返回结果字符串*/public static String DecimalToBinary(Integ…
暂无图片
编程学习 ·

mac OS中配置通过symbolink方式解决路径问题

mac OS中配置通过symlink方式解决路径问题 第一次在mac OS中安装Django,使用pip3 install Django安装了Django V3.0.8版本,出现以下的现象:使用python3 --version可以看到Python版本,正确 使用python3 -m django --version可以看到Django版本,正确 但在使用django-admin s…