adaboost算法原理.ppt

Adaboost
Adaboost 算法的原理与推导
目录
1
2
3
Adaboost算法基础
Adaboost算法原理
Adaboost算法示例
Adaboost
2
1 Adaboost算法基础
Adaboost
分类是数据挖掘的一种非常重要的方法。分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型(即:分类器(Classifier))。该函数或模型能够把数据库中的数据纪录映射到给定类别中的某一个,从而可以应用于数据预测。总之,分类器是数据挖掘中对样本进行分类的方法的统称,包含决策树、逻辑回归、朴素贝叶斯、神经网络等算法。
分类器
3
1 Adaboost算法基础
Adaboost
强分类器、弱分类器
分类器的强弱是其分类能力的一种描述。能够迅速正确的识别的过程就是强分类器,而易错的则是弱分类器(基本分类器)。强分类器可以由多个弱分类器组成。
4
1 Adaboost算法基础
Adaboost
分类器训练
基本分类器1
G1(X)
弱分类器n
Gn(x)
弱分类器i+1
Gi+1(x)
弱本分类器i
Gi(x)
弱分类器2
G2(X)
...
...
权重
a1
权重
an
权重
ai+1
权重
ai
权重
a2
样本1
样本2
样本i
样本i+1
样本n
...
...
强分类器f(x)=∑Gi(x)*ai
分类器训练过程
5
2 Adaboost算法原理
Adaboost
AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于:前一个基本分类器分错的样本会得到加强,加权后的全体样本再次被用来训练下一个基本分类器。针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,构成一个更强的最终分类器(强分类器),同时,在每一轮中加入一个新的弱分类器,直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
Adaboost是什么
6
Adaboost
步骤
1、初始化训练数据的权值分布。如果有N个样本,则每一个训练样本最开始时都被赋予相同的权重:1/N。
2、训练弱分类器。具体训练过程中,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它的权重就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。然后,权重更新过的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。
3、将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,使其在最终的分类函数中起着较大的决定作用,而降低分类误差率大的弱分类器的权重,使其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的权重较大,否则较小。
7
给定一个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)},其中实例,而实例空间,yi属于标记集合{-1,+1},Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器,然后将这些弱分类器组合成一个强分类器。
2 Adaboost的原理
Adaboost
Adaboost算法流程
8
Adaboost
步骤1
初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权重:1/N。
9
c. 计算Gm(x)的系数,am表示Gm(x)在最终分类器中的重要程度(目的:得到基本分类器在最终分类器中所占的权重):
(这里的log表示ln, 的推导式在《统计学习方法》第八章)
由上述式子可知,em <= 1/2时,am >= 0,且am随着em的减小而增大,意味着分类误差率越小的基本分类器在最终分类器中的作用越大
Adaboost
步骤2
进行多轮迭代,用m = 1,2, ..., M表示迭代的第多少轮
a. 使用具有权值分布Dm的训练数据集学习,得到基本分类器:
由上述式子可知,Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。
b. 计算Gm(x)在训练数据集上的分类误差率
(这里相当于概率论里面的数学期望:E=∑Xi*Pi)
由上述式子可知,Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。
d. 更新训练数据集的权值分布(目的:得到样本的新的权值分布),用于下一轮迭代
使得被基本分类器Gm(x)误分类样本的权值增大,而被正确分类样本的权值减小。就这样,通过这样的方式,AdaBoost方法能“聚焦于”那些较难分的