分类是机器学习的一个核心研究内容。在多种现存的分类器中,最为简单有效的一种就是决策树。但是,传统的决策树算法由于实现的年代较早,运行效率为了适应当时有限的内存而有所牺牲;另一方面,传统决策树算法仅采用简单的单变量测试,所以只能产生平行于坐标轴的超矩形决策面,在需要斜线或曲线决策面的数据集上泛化性能不高。本论文针对以上不足,对决策树分类器进行了深入的研究,并得到以下三个研究成果。一、我们提出了一种基于主存的C4.5快速实现,称为Fast C4.5。Fast C4.5利用预处理首先将所有数据在各连续属性上的先后顺序提取出来,然后用间接桶排序结合位并行技术对连续属性的分裂点评价进行优化,通过在界定范围内的二分搜索来加速对测试属性分割点的寻找,并在此过程中进行一些结构上的整合来减少冗余计算,改进系统的整体性能。Fast C4.5改善了C4.5算法的部分时间复杂度,大大减少了决策树的构建时间,并在实验中得到验证。二、我们提出了一种潜在属性空间树分类器(LAST)框架,通过将原属性空间变换为更容易分离数据或更符合决策树分类特点的潜在属性空间,突破传统决策树算法的超矩形决策面局限,改善树分类器的泛化性能。在LAST框架下,我们提出了两种奇异向量空间斜决策树(SODT)算法,通过对全局或局部数据构建奇异向量空间,并在此新空间内构建传统的单变量决策树或树结点,最终间接获得原空间内近似最优的斜决策树分类器。实验结果显示,与传统的单变量决策树和其它斜决策树算法相比,SODT的分类准确率更高,构建的决策树大小更稳定,且决策树构建时间与单变量决策树相近,而远小于其它斜决策树算法。三、我们提出了一个基于非线性流形映射的分类器(NMMC)框架,通过结合流形映射,分类器和在测试数据集上的扩展三个可变元素,为非线性分类器的设计提供了一个统一的框架。在NMMC框架下,我们进一步提出了一种谱空间树分类器(SSDT),它将NMMC的流形映射实现为拉普拉斯矩阵的谱空间变换,将分类器实现为决策树,从简化新条件属性与类别属性之间关系的角度,提高决策树分类器的泛化能力。在SSDT的基础上,我们还提出了一种基于有监督流形映射的谱空间树分类器,通过在无监督的谱空间变换中加入已知训练数据的类别信息,从而有监督地指导不同类别的数据在新流形上更好地分离开来。实验结果显示,SSDT无论在分类准确率、构建的决策树大小,还是在分类稳定性方面,都远胜于传统的决策树算法。