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

摘要

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

目录

文摘

英文文摘

声明

1 绪 论

2 数据挖掘理论及决策树分类

3 典型的决策树算法分析

4 基于信息增益的改进算法

5 总结与展望

参考文献

致 谢