资源描述：
《第七章 分类和预测 - pudncom.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Bagging&Boosting分类决策树分类:ID3C4.5贝叶斯分类后向传播分类其它分类分类法的准确性评估分类法的准确率保持（holdout）K-次交叉验证（k-foldcrossvalidation）提高分类法的准确率baggingboosting评估分类法的准确率保持（holdout）划分为两个独立的数据集： 通常:训练集(2/3),测试集(1/3)变形：随机子选样数据训练集测试集导出分类法评估准确性评估分类法的准确率K-次交叉验证将数据集分为k个子集；用k-1个子集作训练集，1个子集作测试
2、集，然后k次交叉验证；数据S1S2Sk···训练集测试集提高分类法的准确率BaggingBoosting数据C1C2Ct组合得票新数据样本类预测···Bagging基本思想:给定一个弱学习算法,和一个训练集;单个弱学习算法准确率不高;将该学习算法使用多次,得出预测函数序列,进行投票;最后结果准确率将得到提高.Bagging算法:Fort=1,2,…,TDo从数据集S中取样（放回选样）训练得到模型Ht对未知样本X分类时,每个模型Ht都得出一个分类，得票最高的即为未知样本X的分类也可通过得票的平均值用于
3、连续值的预测Bagging…C1C2CTtraintraintrain…xc1(x)c2(x)cT(x)C*c*(x)=maxcnttct(x)S1S2STBaggingBagging要求“不稳定”的分类方法；比如：决策树，神经网络算法不稳定：数据集的小的变动能够使得分类结果的显著的变动。“Thevitalelementistheinstabilityofthepredictionmethod.Ifperturbingthelearningsetcancausesignificantchangesi
4、nthepredictorconstructed,thenbaggingcanimproveaccuracy.”(Breiman1996)Boosting背景来源于:PAC-LearningModelValiant1984-11提出问题:强学习算法:准确率很高的学习算法弱学习算法:准确率不高,仅比随机猜测略好是否可以将弱学习算法提升为强学习算法Boosting背景最初的boosting算法Schapire1989AdaBoost算法FreundandSchapire1995Boosting基本思想：
5、每个样本都赋予一个权重T次迭代，每次迭代后，对分类错误的样本加大权重，使得下一次的迭代更加关注这些样本。Boosting也要求“不稳定”的分类方法Boosting过程:在一定的权重条件下训练数据，得出分类法Ct根据Ct的错误率调整权重SetofweightedinstancesClassifierCttrainclassifieradjustweightsBoostingAdaBoostAdaBoost.M1AdaBoost.M2…AdaBoost输入:(X1,Y1),(X2,Y2),…(Xn,Yn
6、)Xi∈X,Yi∈Y={+1,-1}初始化:D1(i)=1/nFort=1,…,T在Dt下训练,得到弱的假设ht:X->{-1,+1},错误率:Εt=ΣDt(i)[ht(Xi)≠Yi]选择αt=1/2ln((1-Εt)/Εt),更改权值:ifht(Xi)≠Yi,Dt+1(i)=Dt(i)*eαt/Ztifht(Xi)=Yi,Dt+1(i)=Dt(i)*e-αt/Zt输出:H(X)=sign(∑αtht(X))AdaBoost.M1初始赋予每个样本相等的权重1/N；Fort=1,2,…,TDo学习得到
7、分类法Ct；计算该分类法的错误率EtEt=所有被错误分类的样本的权重和；βt=Et/（1-Et）根据错误率更新样本的权重；正确分类的样本：Wnew=Wold*βt错误分类的样本：Wnew=Wold调整使得权重和为1；每个分类法Ct的投票价值为log[1/βt]Boosting……xc1(x)c2(x)cT(x)C*c*(x)=argmaxcmSct(x)=cmlog(1/bt)C1trainS,w1trainC2S,w2CTtrainS,wTAdaBoosttrainingerror将γt=1/2-
8、Et;FreundandSchapire证明:最大错误率为:即训练错误率随γt的增大呈指数级的减小.AdaBoostgeneralizationerror(1)最大总误差:m:样本个数d:VC维T:训练轮数Pr:对训练集的经验概率如果T值太大,Boosting会导致过适应（overfit）AdaBoostgeneralizationerror(2)许多的试验表明:Boosting不会导致overfitAdaBoostgeneralizationerror(3)解释以上
