基于信息增益的完全决策树算法研究

论文摘要

决策树分类算法作为数据挖掘技术中一个重要的分类方法,具有简洁且高效的分类效果。决策树算法通过数据样本集建立决策树模型,进而利用生成的模型对未知分类数据进行分类。目前对于决策树的研究已经有40多年的历史,这期间诞生了许许多多不同的算法。其中较为经典的ID3、C4.5、C5.0等算法均是基于信息增益理论的分类算法,这些算法有着理论清晰、方法简单且分类速度较快的特点。但同时信息增益理论在决策树属性分裂时,也存在着多值偏向等问题。本文结合信息增益理论的优势,着眼于改进决策树算法的分类精度,主要研究内容是基于信息增益的完全决策树算法。本文通过引入一种新型的决策树节点,在属性分裂时并非选择单一分裂属性,而是根据信息增益的评估结果,通过提出的范围界定参数来选择一系列分裂属性,将此方法所得的决策树称为完全决策树。节点的引入使得在保留了熵值计算的选择标准前提下,进一步改进了算法稳定性,提高了准确度,更大的发挥了基于信息增益理论的决策树算法潜力。本文将基于信息增益的完全决策树算法应用于UCI的Car Evaluation数据集中进行验证测试,同时与非完全决策树的ID3、C4.5算法进行比较。根据算法中范围界定参数的不同,完全决策树最高精度比ID3与C4.5有了一定提升。此时完全决策树构建时间相较ID3与C4.5增加并不明显。在对各算法分类准确率和时间复杂度等方面分析后得出,基于信息增益的完全决策树算法可在牺牲较少的时间复杂度情况下,有效提高分类准确率。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 选题背景和意义
• 1.2 国内外研究概况
• 1.3 本文主要工作和章节安排
• 2 数据挖掘理论及决策树分类
• 2.1 数据挖掘理论
• 2.2 决策树分类
• 2.3 本章小结
• 3 典型的决策树算法分析
• 3.1 决策树中的信息增益理论
• 3.2 基于信息增益的决策树算法
• 3.3 其他经典决策树算法
• 3.4 各典型决策树算法比较分析
• 3.5 几种基于信息增益的改进决策树算法
• 3.6 本章小结
• 4 基于信息增益的改进算法
• 4.1 算法存在的问题及改进思路
• 4.2 改进算法描述
• 4.3 算法分析与比较
• 4.4 本章小结
• 5 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢