基于改进信息熵离散化的决策树算法研究

论文摘要

在解决分类问题的各种方法中,决策树方法是运用最广泛的一种。但是由于C4.5算法的对连续属性进行离散化处理时易出现的一些问题,即基于熵的离散化算法(EBD),致使不具备较好的易操作性。针对此问题,在博弈演化思想的启发下,对EBD算法进行了改进,提出了基于博弈论的离散化算法,即将离散化过程视作博弈演化的过程,经过不断的演化达到较为满意的均衡解,并根据实际问题适当的优化算法的计算复杂性,使其较为实用。离散化过程中所建立的博弈模型,其纯策略nash均衡,即为离散化的全局最优解,对于求解过程,第四章提出了一种新的搜索策略。其特点在于一是在遍历开始之前选择较优的遍历策略,二是通过遍历过程得到的信息来动态调整遍历策略空间,三是尽可能缩小遍历空间。这样在求解nash均衡时会降低系统的时间开销。为了尽可能减少算法的计算量,本文对算法进行了一定的优化,并进行了实验验证。由于并非所有的离散化所转化的博弈模型都存在全局nash均衡解,为了防止博弈演化进入无限循环,要根据情况定义演化的停止准则,同时对离散化的结果进行初步评估,从而获得较为满意的结果,为分类算法提供高质量的数据基础。本文实验分两个部分,其一是将所提的nash均衡求解算法,与几个经典的求解算法进行对比,说明该算法具有较好的收敛效果;其二是将本文提出的离散化的算法与EBD算法进行多方面对比,说明该算法具有较好的有效性。实验结果表明,与EBD算法相比,改进后的算法不仅保持简单性、一致性和精确性,而且容易操作。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状与发展动态
• 1.3 本文内容及组织结构
• 第2章 决策树分类算法
• 2.1 决策树方法概述
• 2.1.1 决策树的表示
• 2.1.2 决策树算法的学习过程
• 2.1.3 决策树适用的问题
• 2.1.4 决策树的评价标准
• 2.2 基于信息论的决策树算法
• 2.2.1 信息论在ID3 算法中的应用
• 2.2.2 ID3 算法描述
• 2.2.3 ID3 算法的评价
• 2.2.4 决策树归纳的扩展
• 2.3 决策树算法分析总结
• 2.4 决策树学习中常见问题的分析
• 2.4.1 连续属性的处理
• 2.4.2 属性值空缺的处理
• 2.4.3 避免过度拟合训练数据
• 第3章 改进的信息熵离散化算法
• 3.1 引言
• 3.2 信息熵离散化算法
• 3.3 改进的离散化算法
• 3.3.1 连续性随机变量的信息熵定义
• 3.3.2 基于信息熵的离散化数学表示
• 3.3.3 建立离散化过程的博弈演化模型
• 3.3.4 改进的离散化算法提出
• 3.4 算法优化
• 3.4.1 选取候选断点的优化
• 3.4.2 博弈演化初始局势的优化
• 3.4.3 博弈演化停止准则的优化
• 3.5 实例分析
• 3.5.1 EBD 算法离散化此数据集
• 3.5.2 改进算法离散化此数据集
• 3.5.3 两种算法的比较分析
• 第4章 改进的求解纳什均衡算法
• 4.1 相关概念与符号
• 4.2 算法基础
• 4.3 求解纳什均衡解算法
• 第5章 实例测试
• 5.1 测试数据
• 5.2 实验环境
• 5.3 实验结果
• 结论与展望
• 1. 本文总结
• 2. 展望
• 参考文献
• 致谢
• 附录 A 攻读硕士期间发表的论文
• 附录 B 攻读学位期间参加的项目