Adaboost算法的前世今生.doc

Adaboost算法的前世今生
转载▼
标签:
it
Adaboost算法的前世今生
引言
众所周知,模式识别的方法可以按照参与识别特征的属性来区分,可以分为两大类:一、使用定量特征(可度量)如物体长度、宽度等,来描述的各种模式,这一类主要是指决策理论,有匹配、统计、神经网络等方法;二、使用定性特征如特征结构、排列顺序等,来描绘的各种模式,这一类主要是指结构判别,主要有串和树的匹配等方法。
模式识别的完整的流程顺序是:传感器——分割组织——特征提取——分类器——后处理。其中分类器的设计部分,可以使用的理论有很多,目前主要包括:基于统计理论的方法(贝叶斯理论)、线性判别函数、神经网络的方法、随机方法(对于复杂的问题)、非度量方法(定性结构特征)
分类器得到的模型不仅要很好拟合输入数据,还要能够正确地预测未知样本的类标号。因此,训练算法的主要目标就是要建立具有很好的泛化能力模型,即建立能够准确地预测未知样本类标号的模型。
通常我们用“方差”和“偏差”来测量学习算法与给定分类问题的“匹配”和“校准”程度。“偏差”度量的是匹配的“准确性”和“质量”:一个高的偏差意味着一个坏的匹配,“方差”度量的是匹配的“精确性”和“特定性”:一个高的方差意味着一个弱的匹配。
研究表明,使用重采样技术可以提高分类器的准确率,而boosting算法就是涉及分类器设计中的重采样技术。其思想内涵在于:从给定的数据集中抽取多个数据子集,使得有可能计算任意统计量的值及其范围。
说道boosting,不得不说Arcing(adaptive reweighting bining)自适应的权值重置和组合:重新使用和选择数据,以期达到改善分类器性能的目的。最简单的arcing版本就是bagging算法。
Bagging一个多分类器系统
bagging算法的基本思想:
给定一个弱学习算法,和一个训练集;单个弱学习算法准确率不高;将该学习算法使用多次,得出预测函数序列,进行投票,最后结果准确率将得到提高。
步骤1:从大小为n的原始数据集D中,分别独立随机的抽取n’个数据(n’<n),形成自助数据集,将这个过程独立重复多次,直到产生很多独立的自助数据集。
步骤2:每一个自助数据集都被独立的用于训练一个“分量分类器”。
步骤3、最终的分类判决由这些“分量分类器”各自的判决结果投票决定。
Bagging算法是第一个多分类器系统,后面还有(组合分类器系统)。
算法:
For t = 1, 2, …, T Do
从数据集S中取样(放回选样)
训练得到模型Ht
对未知样本X分类时,每个模型Ht都得出一个分类,得票最高的即为未知样本X的分类,也
可通过得票的平均值用于连续值的预测。
Bagging 和boosting的区别
 
训练集:
预测函数
准确性
使用要求
Bagging
随机选择,各轮训练集相互独立
没有权重;可以并行生成
在有些数据集中,boosting会引起退化
要求“不稳定”的分类方法
Boosting
各轮训练集并不独立,它的选择与前轮的学习结果有关
有权重;只能顺序生成
在大多数数据集中,boosting的准确性比bagging高
要求“不稳定”的分类方法
训练集的小变动能够使得分类模型显著变动
B