决策树分类优化算法的研究

论文摘要

数据挖掘就是从大量的、不完全的、有噪声的数据中,提取出有效的和潜在规律性信息的过程。数据挖掘的任务就是从数据集中发现模式,它融合了数据库、人工智能,、机器学习、统计学等多个领域的理论和知识。在数据挖掘中,分类和预测是被广泛研究的技术,并且已经广泛地应用于许多领域,对未来商业和人们的生活也将产生深远的影响。决策树方法自20世纪60年代以来,在分类、预测、规则提取等领域有着广泛的应用,其中以Quilan于1986年提出的ID3算法最为著名。本文主要研究决策树ID3算法及其改进。本文深入研究了ID3算法的理论基础及构建决策树的过程等知识。Quinlan提出的ID3算法虽然很经典,但也有美中不足之处。第一,算法中使用了对数计算,而且计算过程复杂；第二,取值较多的属性被选择的机率比较大,即多值偏向问题。为了解决ID3的这些问题,本文引入了泰勒公式和麦克劳林公式,对原ID3算法进行化简,不仅属性信息增益的计算步骤减少,而且使信息熵的计算公式本身变得十分简洁；对于ID3算法偏向于选取有较多取值的属性的缺点,用一个与属性取值个数相关的函数对简化后的属性信息增益进行修正。通过以上两个方面的优化,新算法在构建决策树的速度上得到提高,同时也解决了ID3算法多值偏向的不足。然后,使用同一个小数据集对改进前后的算法进行实例分析,分别得到其对应的决策树。最后,用面向对象的JAVA高级语言实现了改进前后的ID3算法,并且在不同规模的数据集上进行仿真实验,把改进后算法分别与ID3算法、C4.5算法进行比较分析,验证了改进后算法在构建决策树时所需的时间及分类准确率两个方面都优于其他两个算法。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 前言
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文的主要研究内容
• 1.4 本文的组织结构
• 第二章 数据挖掘与决策树相关技术
• 2.1 数据挖掘的基础理论知识
• 2.1.1 数据挖掘的概念
• 2.1.2 数据挖掘的特点
• 2.1.3 数据挖掘的过程
• 2.1.4 数据挖掘的任务
• 2.2 数据挖掘的常用算法
• 2.2.1 神经网络（NN）
• 2.2.2 决策树
• 2.2.3 基因算法
• 2.2.4 贝叶斯网络算法
• 2.2.5 粗糙集方法
• 2.2.6 支持向量机方法
• 2.2.7 其他数据挖掘方法
• 2.3 数据挖掘常用软件
• 2.4 决策树核心技术
• 2.4.1 属性约简技术
• 2.4.2 属性选择技术
• 2.4.3 决策树剪枝技术
• 2.5 决策树常用算法
• 2.5.1 CLS算法
• 2.5.2 C4.5算法
• 2.5.3 SLIQ算法
• 2.5.4 其他决策树算法
• 2.5.5 决策树算法小结
• 2.6 本章小结
• 第三章 基于信息熵的分类算法研究
• 3.1 信息论原理
• 3.1.1 信息论基本概念
• 3.1.2 信息熵和条件熵的概念
• 3.1.3 互信息和信息增益
• 3.2 基于信息熵分类算法的基础知识
• 3.2.1 算法的基本思想
• 3.2.2 ID3建树算法描述
• 3.2.3 ID3建树算法的伪代码
• 3.2.4 算法实例应用分析
• 3.3 算法分析及总结
• 3.3.1 算法的性能分析
• 3.3.2 算法的优缺点
• 3.4 常见的测试属性选择方法
• 3.4.1 信息增益比例法
• 3.4.2 Gini指数法
• 3.4.3 用户兴趣度法
• 3.4.4 关联度函数法
• 3.5 ID3算法的改进思路
• 3.5.1 算法的改进方法
• 3.6 本章小结
• 第4章 决策树ID3算法的改进
• 4.1 算法的计算简化
• 4.1.1 泰勒公式及麦克劳林公式介绍
• 4.1.2 简化算法的理论描述
• 4.1.3 简化算法的实例分析
• 4.2 信息增益的修正
• 4.2.1 多值偏向的理论分析
• 4.2.2 信息熵的改进
• 4.2.3 时间复杂度分析
• 4.2.4 改进后ID3算法的实例分析
• 4.3 本章小结
• 第5章 算法仿真实验与应用
• 5.1 算法实验准备
• 5.1.1 实验环境
• 5.2 实验数据准备
• 5.2.1 ARFF格式文件的相关知识
• 5.2.2 数据预处理
• 5.3 实验内容
• 5.3.1 实验结果分析
• 5.3.2 算法的性能比较
• 5.4 改进后算法在数据库挖掘中的应用
• 5.4.1 数据准备
• 5.4.2 挖掘结果及性能分析
• 5.5 本章小结
• 总结与展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文