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

论文摘要

决策树归纳学习算法是机器学习中最重要的算法之一。目前通常采用启发式方法来构建决策树,因此探索各种启发式算法成了决策树研究的一个焦点。基于最大margin的决策树归纳是一种新的分类方法,它以支持向量机反问题作为启发式来构建决策树。该方法有着很好的泛化能力,但是时间复杂度却很高。本文在降低基于最大margin的决策树归纳算法的时间复杂度方面做了相关的研究。为了提高基于最大margin的决策树归纳学习算法的性能,本文在其基础上提出了两种新的算法。一个是基于最大margin的决策树的并行算法。此并行算法采用消息传递接口(MPI)实现,主要并行点是支持向量机反问题的求解。另一个是多项式级时间复杂度的支持向量机反问题求解算法。该方法首先对数据进行聚类,然后利用类间间隔矩阵寻找最优划分。实验结果表明,这两种算法都缩短了支持向量机反问题的求解时间,提高了基于最大margin的决策树的构建速度。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.2.1 决策树
• 1.2.2 支持向量机
• 1.2.3 支持向量机反问题
• 1.3 本文主要研究内容
• 1.4 本文组织
• 第2章 支持向量机及其反问题
• 2.1 支持向量机
• 2.1.1 线性可分情形
• 2.1.2 近似线性可分情形
• 2.1.3 线性不可分情形
• 2.2 支持向量机求解
• 2.2.1 常用求解方法
• 2.2.2 序贯最小优化算法（SMO）
• 2.3 支持向量机反问题
• 2.4 支持向量机反问题求解
• 2.4.1 遗传算法求解SVM反问题
• 2.4.2 K-means聚类求解SVM反问题
• 第3章 基于最大margin的决策树归纳及其并行算法
• 3.1 基于最大margin的决策树归纳
• 3.1.1 背景
• 3.1.2 算法设计
• 3.1.3 算法分析
• 3.2 基于最大margin决策树归纳的并行算法
• 3.2.1 并行算法设计
• 3.2.2 并行算法分析
• 3.2.3 并行算法实验结果
• 第4章 新的支持向量机反问题求解算法
• 4.1 多类问题的最大间隔
• 4.2 类间间隔矩阵
• 4.3 最远邻聚类得到最优划分
• 4.4 新算法描述
• 4.5 新算法时间复杂度分析
• 4.6 试验结果与分析
• 4.7 在基于最大margin决策树中的应用
• 第5章 总结与展望
• 参考文献
• 攻读硕士学位期间科研工作情况
• 致谢