基于最大margin决策树归纳的研究

[e-mail]基于最大margin决策树归纳的研究王海波符号学习研究组[e-mail]报告提纲国内外研究现状存在问题研究目的与意义实现思路进一步的工作[e-mail]国内外研究现状之SVMSMO算法（Platt1998）聚类SVM（Boley2004）MarginTree（Tibshirani2007）SVM的提出（Vapnik1995）[e-mail]聚类SVM返回[e-mail][e-mail]国内外研究现状之SVM反问题SVM反问题求解——遗传算法SVM反问题求解——K-means聚类SVM反问题在决策树中的应用SVM反问题的提出[e-mail]反问题在决策树中的应用基于最大margin的决策树归纳()0wxb()0wxb求解SVM反问题获得具有最大margin的最优超平面[e-mail]存在问题时间复杂度SVM反问题的求解cmSMO1(21)mcmSVM反问题聚类解决SVM反问题1(21)kcm[e-mail]研究目的与意义目的：使SVM反问题的求解在多项式时间内完成，使决策树的训练时间大大缩短。意义：由于训练过程的加快，使得基于Margin的决策树归纳可以得到更广泛的应用[e-mail]实现思路04.244.202.342.30聚类[e-mail]算法描述及时间复杂度1原始数据聚类：三类2求margin矩阵：3×(3-1)/2次SMO求解3再次聚类得到margintree4求划分超平面:一次SMO求解新算法时间复杂度：(1)2()2kkmccmk23cm[e-mail]进一步工作Margintree算法的实现及修改增加聚类的类别数[e-mail]遇到的问题Margin矩阵的求解修改SMO方法，使得不进行数据处理也可得到margin找一种方法，把数据变换后的margin还原回去[e-mail]参考文献一V.N.Vapnik.TheNatureofStatisticalLearningTheory,Springer,NewYork,ISBN0-387-98780-0,2000.PlattJC.FastTrainingofSVMUsingSequentialMinimalOptimization.InScholkopfB,BurgsCJC,SmolaAJeds.AdvancesInKernelMethods-SupportVectorMachine,Cambridge,MA:MITpress,1998,185-208.DanielBoley,DongweiCao.Trainingsupportvectormachineusingadaptiveclustering[A].Proc.ofFourthSIAMInternationalConferenceonDataMining[C].LakeBuenaVista,FL,UnitedStates,2004.RobertTibshirani,TrevorHastie.Margintreesforhigh-dimensionalclassification,JournalofMachineLearningResearchVol.8,pp.637-652,[e-mail]参考文献二VolkanVural,JenniferG.Dy.Ahierarchicalmethodformulti-classsupportvectormachines.InternationalConferenceonMachineLearning;ProceedingSeries;Vol.69,2004.Xi-zhaoWang,QiangHe,De-GangChen,DanielYeung.Ageneticalgorithmforsolvingtheinverseproblemofsupportvectormachines.Neurocomputing68(2005):225-238.JieZhu,Shu-fangWu,LiXue,Xi-zhaoWang.Animprovedalgorithmforinverseproblemofsvmsbasedonclustering.IEEESystem,ManandCyberneticsSociety,vol.8,pp.4694-4698,2006.NingLi,Xi-zhaoWang,LiXue.Decisiontreeinductionbasedonlargemarginheuristic.IEEESystem,ManandCyberneticsSociety,vol.8,pp.4699-4702,[e-mail]参考文献三Platt,J.,Cristianini,N.,&Shawe-Taylor,J.(2000).Largemargindagsformulticlassclassification.AdvancesinNeuralInformationProcessingSystems12(pp.547–553)[e-mail]谢谢！A&Q