基于粗糙集的决策树算法研究与改进

论文摘要

数据挖掘是指在数据中发现模式、知识或数据间的关系。分类挖掘是数据挖掘中最活跃、最成熟的研究方向,分类算法又是其中涉及到的关键技术。在各种分类算法中,决策树方法有更易被用户理解、更适合大训练数据集以及不需要处理训练数据集以外的信息等优点,已经得到广泛的研究和应用。但基于信息论的传统的决策树技术也存在缺点:偏向于选择属性值较多的属性、对样本质量依赖性强和被限制在每个结点上只检验单个属性等。为此,本文把粗糙集技术应用到决策树算法中。粗糙集是研究不精确、不确定知识的工具,具有很强的知识获取能力。在研究的过程中,发现以粗糙集为基础的区分价值属性选择判据优于传统的信息熵,可以降低决策树的规模,但是需要两两比较所有对象,时间性能不好。据此,本文提出了H-重要和L-重要两个概念,减少了比较次数,降低了时间开销。为了进一步降低树的规模,克服单变量决策树没有综合考虑属性间的联系等不足,本文用多变量构造算法结合H-重要和L-重要两个概念重新构造决策树。以H-重要集合中的部分属性作为初始的检验属性,对基于区分价值的决策树算法进行了进一步的改进。最后,利用实验对改进的基于区分价值的决策树算法和基于区分价值的多变量决策树算法进行对比分析。实验结果表明,前者降低了算法的时间开销,但是却并没有牺牲决策树分类的准确性,而后者构造的决策树在规模上得到了进一步的缩减,也就是构造了更为简单的决策树,也不失分类的准确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 国内外研究历史与现状
• 1.2.1 决策树研究历史与现状
• 1.2.2 粗糙集研究历史与现状
• 1.3 分类综述
• 1.3.1 分类的定义
• 1.3.2 分类的主要算法
• 1.4 研究内容及论文结构
• 第2章 决策树方法
• 2.1 决策树构建
• 2.2 决策树修剪
• 2.2.1 剪枝方法
• 2.2.2 剪枝策略
• 2.3 经典的决策树算法
• 2.4 本章小结
• 第3章 粗糙集技术
• 3.1 粗糙集理论的基本概念
• 3.1.1 不可分辨关系
• 3.1.2 上近似和下近似
• 3.1.3 属性的依赖度
• 3.1.4 属性重要度
• 3.2 粗糙集的化简
• 3.2.1 属性的化简
• 3.2.2 决策表的化简
• 3.3 本章小结
• 第4章 基于粗糙集的决策树研究
• 4.1 基于粗糙集的决策树算法研究
• 4.1.1 基于粗糙集明确区的决策树算法
• 4.1.2 基于区分价值的决策树算法
• 4.2 改进的基于区分价值的决策树算法
• 4.2.1 算法设计思想
• 4.2.2 算法正确性分析
• 4.2.3 决策树算法实例比较
• 4.3 基于区分价值的多变量决策树构造
• 4.3.1 属性选择标准重定义
• 4.3.2 相对泛化的定义
• 4.3.3 结合区分价值的多变量决策树的构造
• 4.3.4 实例分析比较
• 4.4 本章小结
• 第5章 实验结果与分析
• 5.1 实验数据来源
• 5.2 实验结果比较分析
• 5.3 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢