adaboost算法原理教案.ppt

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