可变空间树分类器

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 机器学习
• 1.1.1 发展过程
• 1.1.2 研究内容
• 1.2 分类
• 1.2.1 决策树
• 1.2.2 贝叶斯方法
• 1.2.3 人工神经网络
• 1.2.4 近邻
• 1.2.5 支持向量机
• 1.2.6 集成分类器
• 1.3 流形学习
• 1.4 谱方法
• 1.5 论文的主要工作
• 1.6 论文组织
• 第二章 Fast C4.5
• 2.1 引言
• 2.2 决策树与C4.5 算法
• 2.2.1 决策树
• 2.2.2 C4.5 算法
• 2.3 C4.5 算法瓶颈
• 2.3.1 连续属性分裂点的评价
• 2.3.2 分割点的确定
• 2.4 Fast C4.5 算法
• 2.4.1 预处理
• 2.4.2 决策树构建
• 2.4.2.1 属性列表的使用方法
• 2.4.2.2 快速连续属性分裂点评价
• 2.4.2.3 快速分割点寻找
• 2.5 实验
• 2.5.1 实验设计
• 2.5.2 运行性能实验
• 2.5.3 可扩放性实验
• 2.5.4 关于输出的讨论
• 2.6 本章小结
• 第三章 潜在属性空间树分类器
• 3.1 引言
• 3.2 奇异值分解和奇异向量空间
• 3.2.1 奇异值分解
• 3.2.2 奇异向量空间
• 3.3 潜在属性空间树分类器框架
• 3.4 奇异向量空间树分类器
• 3.4.1 奇异向量空间斜决策树
• 3.4.2 全局奇异向量空间斜决策树
• 3.4.3 局部奇异向量空间斜决策树
• 3.4.4 时间复杂度分析
• 3.5 实验
• 3.5.1 评价指标
• 3.5.2 实验设计
• 3.5.3 实验结果及讨论
• 3.5.3.1 测试错误率
• 3.5.3.2 决策树大小
• 3.5.3.3 决策树构建时间
• 3.5.4 小结
• 3.6 本章小节
• 第四章 谱空间树分类器
• 4.1 引言
• 4.2 图谱方法
• 4.2.1 图的分割准则
• 4.2.2 图的构建
• 4.3 基于非线性流形映射的分类器框架
• 4.3.1 流形映射
• 4.3.2 分类器构建
• 4.3.3 测试数据的分类
• 4.4 谱空间树分类器
• 4.4.1 基本理论
• 4.4.1.1 谱空间变换
• 4.4.1.2 测试数据的分类
• 4.4.2 具体实现及改进
• 4.4.2.1 基于连续化-最近邻的局部尺度全连通图构建
• 4.4.2.2 归一化的拉普拉斯矩阵
• 4.4.2.3 谱空间树分类器算法
• 4.5 基于有监督流形映射的谱空间树分类器
• 4.5.1 有监督的谱空间变换
• 4.6 基于非线性流形映射分类器框架的其它实现
• 4.6.1 流形降维
• 4.6.1.1 等度规映射
• 4.6.1.2 局部线性嵌入
• 4.7 实验
• 4.7.1 实验设计
• 4.7.2 实验结果及讨论
• 4.7.2.1 测试错误率
• 4.7.2.2 决策树大小
• 4.8 本章小结
• 第五章 结论
• 5.1 研究成果
• 5.2 工作展望
• 参考文献
• 致谢
• 攻读学位期间发表学术论文目录
• 攻读学位期间参与科研项目