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