决策树分类

Bagging&Boosting分类决策树分类:ID3C4.5贝叶斯分类后向传播分类其它分类分类法的准确性评估分类法的准确率保持（holdout）K-次交叉验证（k-foldcrossvalidation）提高分类法的准确率baggingboosting评估分类法的准确率保持（holdout）划分为两个独立的数据集：通常:训练集(2/3),测试集(1/3)变形：随机子选样数据训练集测试集导出分类法评估准确性评估分类法的准确率K-次交叉验证将数据集分为k个子集；用k-1个子集作训练集，1个子集作测试集，然后k次交叉验证；数据S1S2Sk···训练集测试集提高分类法的准确率BaggingBoosting数据C1C2Ct组合得票新数据样本类预测···Bagging基本思想:给定一个弱学习算法,和一个训练集;单个弱学习算法准确率不高;将该学习算法使用多次,得出预测函数序列,进行投票;最后结果准确率将得到提高.Bagging算法:Fort=1,2,…,TDo从数据集S中取样（放回选样）训练得到模型Ht对未知样本X分类时,每个模型Ht都得出一个分类，得票最高的即为未知样本X的分类也可通过得票的平均值用于连续值的预测Bagging…C1C2CTtraintraintrain…xc1(x)c2(x)cT(x)C*c*(x)=maxcnttct(x)S1S2STBaggingBagging要求“不稳定”的分类方法；比如：决策树，神经网络算法不稳定：数据集的小的变动能够使得分类结果的显著的变动。“Thevitalelementistheinstabilityofthepredictionmethod.Ifperturbingthelearningsetcancausesignificantchangesinthepredictorconstructed,thenbaggingcanimproveaccuracy.”(Breiman1996)Boosting背景来源于:PAC-LearningModelValiant1984-11提出问题:强学习算法:准确率很高的学习算法弱学习算法:准确率不高,仅比随机猜测略好是否可以将弱学习算法提升为强学习算法Boosting背景最初的boosting算法Schapire1989AdaBoost算法FreundandSchapire1995Boosting基本思想：每个样本都赋予一个权重T次迭代，每次迭代后，对分类错误的样本加大权重，使得下一次的迭代更加关注这些样本。Boosting也要求“不稳定”的分类方法Boosting过程:在一定的权重条件下训练数据，得出分类法Ct根据Ct的错误率调整权重SetofweightedinstancesClassifierCttrainclassifieradjustweightsBoostingAdaBoostAdaBoost.M1AdaBoost.M2…AdaBoost输入:(X1,Y1),(X2,Y2),…(Xn,Yn)Xi∈X,Yi∈Y={+1,-1}初始化:D1(i)=1/nFort=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学习得到分类法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24112ttttt22exp将γt=1/2-Et;FreundandSchapire证明:最大错误率为:即训练错误率随γt的增大呈指数级的减小.AdaBoostgeneralizationerror(1)最大总误差:m:样本个数d:VC维T:训练轮数Pr:对训练集的经验概率如果T值太大,Boosting会导致过适应（overfit）)())((mTdOyxHprAdaBoostgeneralizationerror(2)许多的试验表明:Boosting不会导致overfitAdaBoostgeneralizationerror(3)解释以上试验现象;样本(X,Y)的margin:margin(x,y)=αt=1/2ln((1-Εt)/Εt)较大的正边界表示可信度高的正确的预测较大的负边界表示可信度高的错误的预测xhytttAdaBoostgeneralizationerror(4)解释:当训练误差降低后,Boosting继续提高边界,从而增大了最小边界,使分类的可靠性增加,降低总误差.总误差的上界:该公式与T无关)()),(arg(2mdOyxinmPrBoosting其它应用Boosting易受到噪音的影响;AdaBoost可以用来鉴别异常;具有最高权重的样本即为异常.Bagging和boosting的区别训练集:Bagging:随机选择,各轮训练集相互独立Boosting:各轮训练集并不独立,它的选择与前轮的学习结果有关预测函数:Bagging:没有权重;可以并行生成Boosting:有权重;只能顺序生成Bagging,boosting,andC4.5J.R.Quinlan介绍在大多数应用中，准确率比运算速度更为重要，因为计算机的性价比提高很快。bagging和boosting都可以有效地提高分类的准确性。在大多数数据集中，boosting的准确性比bagging高。在有些数据集中，boosting会引起退化。---OverfitBagging和boosting方法的要求：最基本的是分类方法的不稳定性。即：训练集的小变动能够使得分类模型显著变动。Bagging试验：效果实验：CART，T=50，7个中等大小的数据集，使用bagging后的平均错误率为使用单个分类法的57%-94%.datasetBoosting试验:平均T=4.9时,训练准确率可以达到T=10时的训练准确率.但T=4.9时,总的错误率却比T=10时的错误率高改变boosting投票权重(1)AdaBoost.M1中的投票权重:log[1/βt]替代:SitiSititNNxHk21)(age?student?creditrating?noyesfairexcellent=3030……k…改变boosting投票权重(2)x1,x2,…,xnSbagging&boosting应用前景Internet上的文本过滤图像数据库中的图像识别手写体字符识别语音识别研究方向Bagging和boosting非常相似,是否存在统一的理论框架.Boosting发生overfit的条件.