君，已阅读到文档的结尾了呢~~
利用PCA和AdaBoost建立基于贝叶斯的组合分类器
Construct Ensembles of Bayes-based Classifiers Using PCA and AdaBoost
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
利用PCA和AdaBoost建立基于贝叶斯的组合分类器
Construct Ensembles of Bayes-based Classifiers Using PCA and AdaBoost
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口我的图书馆
一、Boosting算法的发展历史
　　Boosting算法是一种把若干个分类器整合为一个分类器的方法，在boosting算法产生之前，还出现过两种比较重要的将多个分类器整合 为一个分类器的方法，即boostrapping方法和bagging方法。我们先简要介绍一下bootstrapping方法和bagging方法。
　　1）bootstrapping方法的主要过程
　　主要步骤：
　　i)重复地从一个样本集合D中采样n个样本
　　ii)针对每次采样的子样本集，进行统计学习，获得假设Hi
　　iii)将若干个假设进行组合，形成最终的假设Hfinal
　　iv)将最终的假设用于具体的分类任务
　　2）bagging方法的主要过程 &-----bagging可以有多种抽取方法
　　主要思路：
　　i)训练分类器
　　从整体样本集合中，抽样n* & N个样本 针对抽样的集合训练分类器Ci
　　ii)分类器进行投票，最终的结果是分类器投票的优胜结果
　　但是，上述这两种方法，都只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。直到1989年，Yoav Freund与 Robert Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖（Godel price）。
　　Schapire还提出了一种早期的boosting算法，其主要过程如下：
　　i)从样本整体集合D中，不放回的随机抽样n1 & n个样本，得到集合 D1
　　训练弱分类器C1
　　ii)从样本整体集合D中，抽取 n2 & n个样本，其中合并进一半被C1 分类错误的样本。得到样本集合 D2
　　训练弱分类器C2
　　iii)抽取D样本集合中，C1 和 C2 分类不一致样本，组成D3
　　训练弱分类器C3
　　iv)用三个分类器做投票，得到最后分类结果
　　到了1995年，Freund and schapire提出了现在的adaboost算法，其主要框架可以描述为：
　　i)循环迭代多次
　　更新样本分布
　　寻找当前分布下的最优弱分类器
　　计算弱分类器误差率
　　ii)聚合多次训练的弱分类器
　　在下图中可以看到完整的adaboost算法：
图1.1& adaboost算法过程
　　现在，boost算法有了很大的发展，出现了很多的其他boost算法，例如：logitboost算法，gentleboost算法等等。在这次报告中，我们将着重介绍adaboost算法的过程和特性。
二、Adaboost算法及分析
　　从图1.1中，我们可以看到adaboost的一个详细的算法过程。Adaboost是一种比较有特点的算法，可以总结如下：
　　1）每次迭代改变的是样本的分布，而不是重复采样（re weight)
　　2）样本分布的改变取决于样本是否被正确分类
　　 & & & & & & & &总是分类正确的样本权值低
　　 & & & & & & & &总是分类错误的样本权值高（通常是边界附近的样本）
　　3）最终的结果是弱分类器的加权组合
　　 & & & & & & & &权值表示该弱分类器的性能
　　简单来说，Adaboost有很多优点:
　　1)adaboost是一种有很高精度的分类器
　　2)可以使用各种方法构建子分类器，adaboost算法提供的是框架
　　3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
　　4)简单，不用做特征筛选
　　5)不用担心overfitting！
　　总之：adaboost是简单，有效。
　　下面我们举一个简单的例子来看看adaboost的实现过程：
　　图中，“+”和“-”分别表示两种类别，在这个过程中，我们使用水平或者垂直的直线作为分类器，来进行分类。
　　第一步：
　　根据分类的正确率，得到一个新的样本分布D2-，一个子分类器h1
　　其中划圈的样本表示被分错的。在右边的途中，比较大的“+”表示对该样本做了加权。
　　第二步：
　　根据分类的正确率，得到一个新的样本分布D3，一个子分类器h2
　　第三步：
　　得到一个子分类器h3
　　整合所有子分类器：
　　因此可以得到整合的结果，从结果中看，及时简单的分类器，组合起来也能获得很好的分类效果，在例子中所有的。
　　Adaboost算法的某些特性是非常好的，在我们的报告中，主要介绍adaboost的两个特性。
一是训练的错误率上界，随着迭代次数的增加，会逐渐下降；
二是adaboost算法即使训练次数很多，也不会出现过拟合的问题。
　　下面主要通过证明过程和图表来描述这两个特性：
　　1）错误率上界下降的特性
　　从而可以看出，随着迭代次数的增加，实际上错误率上界在下降。
　　2）不会出现过拟合现象
　　通常，过拟合现象指的是下图描述的这种现象，即随着模型训练误差的下降，实际上，模型的泛化误差（测试误差）在上升。横轴表示迭代的次数，纵轴表示训练误差的值。
而实际上，并没有观察到adaboost算法出现这样的情况，即当训练误差小到一定程度以后，继续训练，返回误差仍然不会增加。
　　对这种现象的解释，要借助margin的概念，其中margin表示如下：
　　通过引入margin的概念，我们可以观察到下图所出现的现象：
　　从图上左边的子图可以看到，随着训练次数的增加，test的误差率并没有升高，同时对应着右边的子图可以看到，随着训练次数的增 加，margin一直在增加。这就是说，在训练误差下降到一定程度以后，更多的训练，会增加分类器的分类margin，这个过程也能够防止测试误差的上 升。
三、多分类adaboost
　　在日常任务中，我们通常需要去解决多分类的问题。而前面的介绍中，adaboost算法只能适用于二分类的情况。因此，在这一小节中，我们着重介绍如何将adaboost算法调整到适合处理多分类任务的方法。
　　目前有三种比较常用的将二分类adaboost方法。
　　1、adaboost M1方法
　　主要思路： adaboost组合的若干个弱分类器本身就是多分类的分类器。
　　在训练的时候，样本权重空间的计算方法，仍然为：
　　在解码的时候，选择一个最有可能的分类
　　2、adaboost MH方法
　　主要思路： 组合的弱分类器仍然是二分类的分类器，将分类label和分类样例组合，生成N个样本，在这个新的样本空间上训练分类器。
　　可以用下图来表示其原理：
　　3、对多分类输出进行二进制编码
　　主要思路：对N个label进行二进制编码，例如用m位二进制数表示一个label。然后训练m个二分类分类器，在解码时生成m位的二进制数。从而对应到一个label上。
　　最后，我们可以总结下adaboost算法的一些实际可以使用的场景：
　　1）用于二分类或多分类的应用场景
　　2）用于做分类任务的baseline
　　 & & &无脑化，简单，不会overfitting，不用调分类器
　　3）用于特征选择（feature selection)
　　4）Boosting框架用于对badcase的修正
　　 & & &只需要增加新的分类器，不需要变动原有分类器
　　由于adaboost算法是一种实现简单，应用也很简单的算法。Adaboost算法通过组合弱分类器而得到强分类器，同时具有分类错误率上界随着训练增加而稳定下降，不会过拟合等的性质，应该说是一种很适合于在各种分类场景下应用的算法。
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&[转]&《机器学习实战》学习笔记：利用Adaboost元算法提高分类性能
关于boosting算法的起源
boost 算法系列的起源来自于PAC Learnability（直译过来称为：PAC 可学习性）。这套理论主要研究的是什么时候一个问题是可被学习的。
我们知道，可计算性在计算理论中已经有定义，而可学习性正是PAC Learnability理论所要定义的内容。另外，在计算理论中还有很大一部分精力花在研究问题是可计算的时候，其复杂度又是什么样的。因此，在计算学习理论中，也有研究可学习的问题的复杂度的内容，主要是样本复杂度 (Sample Complexity) 。
最后，在可计算的时候，得到实现计算的具体算法也是计算理论中的一个重要部分；而更多的在“机器学习”这个领域中，我们往往会探讨针对可学习的问题的具体的学习算法。
听起来很复杂，简而言之，就是：PAC 模型的作用相当于提供了一套严格的形式化语言来陈述以及刻画这里所提及的可学习性 Learnability 以及（样本）复杂度 (Sample) Complexity 问题。
这套理论是由Valiant提出来的，作者曾获得了2010年的图灵奖。
PAC 定义了学习算法的强弱：
弱学习算法：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）；
强学习算法：识别准确率很高并能在多项式时间内完成的学习算法。
更为严格的定义：
弱学习算法：一个概念如果存在一个多项式的学习算法能够学习它，并且学习的正确率仅比随机猜测略好(高于50%)，那么，这个概念是弱可学习的；
强学习算法：一个概念如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么，这个概念是强可学习的。
同时 ,Valiant和Kearns还提出了PAC学习模型中弱学习算法和强学习算法的等价性问题，即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果弱学习算法和强学习算法二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 ,而不必寻找很难获得的强学习算法。 也就是这种猜测，让无数研究人员去设计算法来验证PAC理论的正确性。
不过很长一段时间都没有一个切实可行的办法来实现这个理想。细节决定成败，再好的理论也需要有效的算法来执行。终于功夫不负有心人， Schapire在1996年提出一个有效的算法真正实现了这个夙愿，它的名字叫AdaBoost。AdaBoost把多个不同的决策树用一种非随机的方式组合起来，表现出惊人的性能和优点：
把决策树的准确率大大提高，可以与SVM媲美；
当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
速度快，且基本不用调参数；
简单，无需做特征筛选；
不用担心Overfitting。
“我估计当时Breiman和Friedman肯定高兴坏了，因为眼看着他们提出的CART正在被SVM比下去的时候，AdaBoost让决策树起死回生！Breiman情不自禁地在他的论文里赞扬AdaBoost是最好的现货方法（off-the-shelf，即“拿下了就可以用”的意思）。”（这段话摘自统计学习那些事）
二. 基于数据集多重抽样的分类器
前面我们已经尝试设计多种分类器，如果我们尝试将不同的分类器组合在一起，这种组合的结果就是集成方法（或称为元算法）。使用集成方法时会有多种形式，它可以是不同算法的集成，也可以是同一算法在不同设置下的集成，还可以是数据集的不同部分分配给不同分类器后的集成。通常的集成方法有bagging方法和boosting方法。
1.bagging：基于数据随机重抽样的分类器构建方法
bagging方法，又称为自举汇聚法(bootstrap aggregating)，是在从原始数据集重选择（有放回，可以重复）得到S个新数据集的一种技术，新数据集与原数据集大小相等，每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到。
建立好S个新数据集后，将某个学习算法分别作用于每一个数据集，就得到S个分类器。对这S个分类器进行叠加，他们的权重都相等(当然这里S个分类器采用的分类算法不一样的话，可以考虑使用投票)，这样就可以得到一个强学习器。
以下给出bagging方法的主要步骤：
重复地从一个样本集合D中采样n个样本
针对每次采样的子样本集，进行统计学习，获得假设Hi
将若干个假设进行组合，形成最终的假设Hfinal
将最终的假设用于具体的分类任务
2.boosting方法
书中给出以下解释：boosting是一种与bagging很类似的技术。不论是在boosting还是bagging方法中，所使用的多个分类器的类型都是一致的。不同的是，bagging方法通过串行训练获得不同的分类器，每个新分类器都根据以训练出的分类器性能来进行训练；boosting则是通过集中关注被已有分类器错分的那些数据来获得新的分类器。
boosting方法的分类结果是基于所有分类器的加权求和结果，每个分类结果的权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。
boosting方法拥有多个版本，Adaboost就是属于其中一种。
三. Adaboost：基于错误提升分类器的性能
Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器，即弱分类器，然后把这些弱分类器集合起来，构造一个更强的最终分类器，比起弱分类器，这个“强”分类器的错误率会低很多。
Adaboost算法本身是改变数据分布实现的，它根据每次训练集之中的每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改权值的新数据送给下层分类器进行训练，然后将每次训练得到的分类器融合起来，作为最后的决策分类器。以下给出 Adaboost算法的运行过程：
训练数据中的每个样本，并赋予其一个权重，这些权重构成向量D，一开始时权重D初始化为相等的值；
先在训练样本上训练得到第一个弱分类器并计算分类器的错误率 ；
在同一数据集上再次训练弱分类器，在分类器的二次训练中，会重新调整每个样本的权重，其中第一次分类正确的样本的权重将会降低，而分类错误的样本权重将会提高 ；
为了从所有弱分类器中得到最终的分类结果，Adaboost为每个分类器都分配了一个权重值alpha，这一组值是基于每个弱分类器的错误率进行计算的。
其中，错误率由以下公式定义：
而alpha的计算公式如下：
Adaboost算法的流程图如下：
图中的左边表示数据集，其中直方图的不同宽度表示每个样例上的不同权重。在经过一个分类器之后，加权的预测结果会通过三角形中的alpha值进行加权，每个三角形中输出的加权结果在圆形中求和，从而得到最终的输出结果。
计算出alpha值后，可以对权重向量D进行更新，使得那些正确分类的样本的权重降低而错分样本的权重升高。计算方法如下：
对于正确分类的样本，其权重更改为：
对于错误分类的样本，其权重更改为：
在计算出权重向量D后，Adaboost方法开始进入下一轮的迭代。Adaboost方法会不断地重复训练和调整权重的过程，知道训练错误率为0（或达到用户指定的条件）为止。
一个博客给出一种容易理解的解释：Adaboost的训练过程有如一个学生学习的过程：我们把每个训练样例看做一道练习题，所有的训练样本看做一本习题集。第一次做题的时候，由于每道题都没有做过，不知道哪些难哪些简单，所以一视同仁，做完了对照答案，可能会有很多题目做的不对，那么对于做错的题目，我们就重点标记，给予更高的重视程度，这个用权重w来标示，到第二轮做题的时候就重视这些没做对的“难题”，对于第一次就做对的题目，可以认为是比较简单的，那么第二次的时候稍微看下就可以了，可以降低他的权重。并且，对于第一轮做完以后的效果给一个整体的评分，评价这轮做题的能力，这个就是alpha。在第二轮做题的时候，就按照上一轮调整过的权重对不同的题目给予不同的重视程度和时间分配。如此不断练习，几轮下来，难题就逐渐被攻克了。每轮做题都是有收获的，只不过每次收获的知识权重不同（alpha），这样，我们最后就得到m个分类器，综合每个分类器的权重，我们就能得到一个“学习成绩很好”的分类器了。
四. 基于单层决策树构建分类器
使用Python实现：
def loadSimDat():
dataMat = matrix([[1, 2.1],
[2.0, 1.1],
[1.3, 1.0],
[1.0, 1.0],
[2.0, 1.0]])
classLabels = [1.0, 1.0, -1.0, -1.0, 1.0]
return dataMat, classLabels
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):
retArray = ones((shape(dataMatrix)[0],1))
if threshIneq == 'lt':
retArray[dataMatrix[:,dimen] &= threshVal] = -1.0
retArray[dataMatrix[:,dimen] & threshVal] = -1.0
return retArray
def buildStump(dataArr, classLabels, D):
dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
m,n = shape(dataMatrix)
numSteps = 10.0; bestStump = {}; bestClassEst = mat(zeros((m,1)))
minError = inf
for i in range(n):
rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
stepSize = (rangeMax - rangeMin)/numSteps
for j in range(-1, int(numSteps)+1):
for inequal in ['lt','gt']:
threshVal = (rangeMin + float(j)*stepSize)
predictedVals = stumpClassify(dataMatrix, i, threshVal, inequal)
errArr = mat(ones((m,1)))
errArr[predictedVals == labelMat] = 0
weightedError = D.T * errArr
if weightedError & minError:
minError = weightedError
bestClassEst = predictedVals.copy()
bestStump['dim'] = i
bestStump['thresh'] = threshVal
bestStump['ineq'] = inequal
return bestStump, minError, bestClassEst
下一节将应用Adaboost算法，处理非均衡的分类问题。
参考链接：
看过本文的人也看了：
我要留言技术领域：
取消收藏确定要取消收藏吗？
删除图谱提示你保存在该图谱下的知识内容也会被删除，建议你先将内容移到其他图谱中。你确定要删除知识图谱及其内容吗？
删除节点提示无法删除该知识节点，因该节点下仍保存有相关知识内容！
删除节点提示你确定要删除该知识节点吗？机器学习（18）
第七章 利用AdaBoost元算法提高分类性能
7.1 基于数据集多重抽样的分类器
7.2 训练算法：基于错误提升分类器的性能
7.3 基于单层决策树构建弱分类器
7.4 完整AdaBoost算法的实现
7.5 测试算法：基于AdaBoost的分类
7.6 示例：在一个难数据集上应用AdaBoost
7.7 非均衡分类问题
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：283629次
积分：4283
积分：4283
排名：第6422名
原创：120篇
转载：153篇
评论：31条
(1)(1)(1)(3)(5)(3)(3)(2)(13)(12)(1)(7)(11)(4)(14)(2)(4)(1)(13)(44)(15)(3)(2)(5)(23)(29)(52)