【作者】 王海波；

【导师】 王熙照； 翟俊海；

【作者基本信息】 河北大学 ， 计算机应用技术， 2008， 硕士

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

【Abstract】 Induction of decision tree is one of the most important machine learning algorithms. Exploring heuristic algorithms becomes a focus because heuristic algorithms are usually employed to construct decision tree. The induction of decision tree based on the largest margin, also named large margin decision tree induction (LMDTI), is a new classification technique in which the large margin between two classes is used as heuristic information for the decision tree generation. It has good generalization, but very large time complexity. Motivated by reducing the time complexity of LMDTI, some researches have been done in this paper.In order to improve the efficiency of LMDTI, we propose two new methods based on LMDTI. The first one is the parallel algorithm of LMDTI, which parallely solves the inverse problem of SVM with message passing interface (MPI). The other is a new algorithm for solving the inverse problem of SVM. It has polynomial time complexity, and gets the optimal partition using margin matrix after clustering. Experimental results show that, both methods presented enormously improve the algorithm in time complexity, and at the same time, the speed of constructing the large margin decision tree becomes much faster.更多还原