机器学习(二十五) ——adaboost算法与实现

机器学习(二十五)——adaboost算法与实现

(原创内容,转载请注明来源,谢谢)

一、概述

当进行监督学习时,除了使用某个分类器外,还可以将各个分类器结合起来使用,或者多次使用某个分类器,也可以是数据集分给不同的分类器后进行集成。本文主要介绍基于同一种分类器多个不同实例的方法,基础算法基于单层决策树。

二、bagging

首先,先介绍bagging算法,这个算法是一种自举汇聚法,方法如下:

1)获取数据源

假设样本容量为m,则进行m次放回抽样(即每次抽到样本后再将样本放回),获取一个新的样本集,这个样本集可能用重复数据。

接着,进行S次上述操作,获取S个样本集。

2)分类器

把某种分类器(如决策树)作用于这S个样本集,得到S个分类器。

3)使用

当需要分类的时候,则把新的数据给这S个分类器进行分类,会得到S个分类结果,并返回这S个分类结果中出现次数最多的分类(又称为票数最多的分类结果)。

三、boosting

boosting和bagging非常类似,唯一的区别在于,bagging中,每个分类器的投票权重是一样的,而boosting则会根据上一次的分类结果,对下一次的分类调整分类器对不同样本的权重。

boosting集中关注被已有分类器错分的那些数据,并主要用这些数据来训练新的分类器。多种boosting版本中,最流行的就是adaboosting。

主要步骤如下:

1)权重

对于训练数据的每个样本,赋予一个权重,这个权重代表上一轮迭代的成功度,上一轮成功的降低权重,上一轮错误的增加权重。

2)在训练数据上训练一个弱分类器,并计算该分类器的错误率,然后在同一数据集上再次训练弱分类器。

3)在分类器的二次训练中,会重新调整每个样本的权重。

4)公式

错误率e=未正确分类样本数/所有样本数,α=0.5ln((1-e)/e)。

上一轮该样本正确分类,则该轮样本Di(t+1)=Di(t)e-α/sum(D);若错误分类,则Di(t+1)=Di(t)eα/sum(D)。

四、python实现adaboost

1、获取数据

这里有两种方式,一个是固定一个数据集,用于小范围的测试;另一个是载入一个文件,从文件中获取样本和分类结果。

2、构建单层决策生成树

1)阈值比较

首先需要一个辅助函数,可以通过比较阈值,来进行预测,这里预测的分类结果不是0和1,而是-1和1。

2)构建树

这里通过三层的循环,来构建一个单层的最佳的树,第一层是遍历所有特征,第二层是遍历所有样本,第三层是遍历大于和小于。

对照之前的决策树,是通过信息熵的大小来确定选择哪个节点最好,而这里不考虑信息熵,而是通过选择单层决策树的错误率,错误率最低的作为最佳的决策树,返回构建决策树的样本的第i个特征值、阈值、大于或是小于、最低错误率、最低错误率情况下的预测分类结果。

3、完整adaboost算法

上面有了构建决策树后,就可以来实现完整的adaboost了。实现方式主要基于上面的公式,如下:

错误率e=未正确分类样本数/所有样本数,α=0.5ln((1-e)/e)。

上一轮该样本正确分类,则该轮样本Di(t+1)=Di(t)e-α/sum(D);若错误分类,则Di(t+1)=Di(t)eα/sum(D)。

整个过程比较简单,代码如下图所示:

唯一不一样的,是α的计算,不是直接除以e,是为了防止e=0时发生除以0的异常。

测试分类结果是否正常的代码如下:

一共迭代10次,实现10层的单层决策树。

结果如下(部分):

可以看到,虽然每次的错误率都在0.5左右,但是最终的错误率在0.35,且这里返回了每层决策树的分类依据、阈值等数据。

4、使用adaboost进行分类

使用过程,即不断的获取单层的树,并且动态的加权后,将结果进行sign的运算即可。

五、总结

adaboost算法,可以理解为一个算法的大合集,里面可以放各种的内容,这里是以单层决策树为例,实际上可以放各种函数,有点类似svm的核函数的意义。

由于每次训练完,有反馈和权重,故多层的叠加后,效果会更好。

——written by linhxx 2018.01.30

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-30

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏项勇

笔记68 | 切换fragmengt的replace和add方法笔记

1444
来自专栏刘君君

JDK8的HashMap源码学习笔记

3008
来自专栏Java Edge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

422
来自专栏java闲聊

JDK1.8 ArrayList 源码解析

当运行 ArrayList<Integer> list = new ArrayList<>() ; ,因为它没有指定初始容量,所以它调用的是它的无参构造

1192
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1692
来自专栏xingoo, 一个梦想做发明家的程序员

AOE关键路径

这个算法来求关键路径,其实就是利用拓扑排序,首先求出,每个节点最晚开始时间,再倒退求每个最早开始的时间。 从而算出活动最早开始的时间和最晚开始的时间,如果这两个...

2507
来自专栏学海无涯

Android开发之奇怪的Fragment

说起Android中的Fragment,在使用的时候稍加注意,就会发现存在以下两种: v4包中的兼容Fragment,android.support.v4.ap...

3155
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

1938
来自专栏后端之路

LinkedList源码解读

List中除了ArrayList我们最常用的就是LinkedList了。 LInkedList与ArrayList的最大区别在于元素的插入效率和随机访问效率 ...

19510
来自专栏拭心的安卓进阶之路

Java 集合深入理解(6):AbstractList

今天心情比天蓝,来学学 AbstractList 吧! ? 什么是 AbstractList ? AbstractList 继承自 AbstractCollec...

19110

扫码关注云+社区