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

基于最大 margin 决策树归纳的研究 王海波符号学习研究组报告提纲 国内外研究现状 存在问题 研究目的与意义 实现思路 进一步的工作国内外研究现状之 SVM SMO 算法 （ Platt 1998 ） 聚类 SVM （ Boley 2004 ） Margin Tree （ Tibshirani 2007 ） SVM 的提出（ Vapnik 1995 ）聚类 SVM返回Margin Tree国内外研究现状之 SVM 反问题 SVM 反问题求解——遗传算法 SVM 反问题求解—— K-means 聚类 SVM 反问题在决策树中的应用 SVM 反问题的提出SVM 反问题在决策树中的应用基于最大 margin 的决策树归纳()0w xb()0w xb求解 SVM 反问题获得具有最大 margin的最优超平面存在问题时间复杂度SVM 反问题的求解cmSMO1(21)mcm SVM 反问题聚类解决 SVM 反问题1(21)kcm 研究目的与意义目的：使 SVM 反问题的求解在多项式时间内完成，使决策树的训练时间大大缩短。意义：由于训练过程的加快，使得基于 Margin 的决策树归纳可以得到更广泛的应用实现思路04.244.202.342.30聚类算法描述及时间复杂度1 原始数据聚类：三类2 求 margin 矩阵： 3×(3-1)/2 次 SMO 求解3 再次聚类得到 margin tree4 求划分超平面 : 一次 SMO 求解新算法时间复杂度：(1)2()2k kmccmk23cm进一步工作 Margin tree 算法的实现及修改 增加聚类的类别数遇到的问题 Margin 矩阵的求解修改 SMO 方法，使得不进行数据处理也可得到margin找一种方法，把数据变换后的 margin 还原回去参考文献一V.N. Vapnik. The Nature of Statistical Learning Theory, Springer, New York, ISBN 0-387-98780-0,2000.Platt J C. Fast Training of SVM Using Sequential Minimal Optimization. In Scholkopf B, Burgs CJC, Smola A J eds. Advances In Kernel Methods-Support Vector Machine, Cambridge, MA:MIT press, 1998, 185-208.Daniel Boley, Dongwei Cao. Training support vector machine using adaptive clustering[A]. Proc. of Fourth SIAM International Conference on Data Mining [ C ] . Lake Buena Vista, FL, United States, 2004.Robert Tibshirani, Trevor Hastie. Margin trees for high-dimensional classification, Jour...