《基于决策树的ID3算法的研究与改进》由会员分享，可在线阅读，更多相关《基于决策树的ID3算法的研究与改进（48页珍藏版）》请在金锄头文库上搜索。
1、河北工业大学硕士学位论文基于决策树的ID3算法的研究与改进姓名：王鹤申请学位级别：硕士专业：计算机应用技术指导教师：彭玉青20081101河北工业大学硕士学位论文 i 基于决策树的基于决策树的 ID3 算法的研究与改进算法的研究与改进 摘摘 要要 数据分类是数据挖掘中一个重要的内容。常见的分类模型有决策树、神经网络、遗传算法、粗糙集等。其中决策树算法是以实例为基础的归纳学习算法，以其易于提取显示规则、 计算量相对较小、 可以显示重要决策属性和较高的分类准确率等优点而得到广泛的应用。 论文从学习数据挖掘的基础理论出发，重点介绍和研究了决策树的 ID3 算法，并分析了 ID3 算法存在的以下缺点：
2、1、ID3 不能处理连续性数据。2、ID3 算法在选择分裂属性时倾向于选择属性值多的属性。3、计算效率低。 针对以上的缺点，论文的主要工作体现在以下几个方面： 第一、归纳了数据挖掘技术的总体研究情况，包括数据挖掘的定义，挖掘的主要过程和主要技术手段等。 第二、 从宏观上介绍了分类技术的理论基础， 对几种常见决策树算法进行了分析和比较，例如 ID3、C4.5、CART 算法，并重点分析了决策树的 ID3 算法。 第三、论文对决策树算法进行了优化研究，提出了一种改进的 ID3 算法，改进的算法与决策树的 ED(Effective- Degree)算法相结合，选取新的标准作为选择分类属性。通过对新算
3、法在测试样例上训练得出的结果表明：改进算法在能有效提高分类的精度，改善ID3算法选择分裂属性时倾向取值较多的不足， 总体性能上优于目前广泛应用的ID3算法。 关键字：数据挖掘，决策树，ID3 基于决策树的 ID3 算法的研究与改进 ii THE RESEARCH AND IMPROVEMENT OF ID3 ALGORITHM BASED ON DECISION- TREE ABSTRACT Data classification is one of important contents in Data Mining.There are many methods for data classi
4、fication，such as decision tree induction，neural networks，genetic algorithms，rough sets，and so on.The decision tree classification algorithm based on the instances amongst these is widely used with its advantages of convenience for getting apparent rules，smaller calculation workload，showing important
5、 decision characteristics，higher classification correctness etc. This paper begins with basic theory of data mining, focuses on the introduction and researches decision- trees ID3 algorithm,analysis its shortcomings following:1. ID3 algorithm can not handle coninuous- type of data;2.ID3 algorithm pr
6、efers to the attributes with more options attribute when choosing split attribute;3.low efficiency of calculating. To deal with above shortcomings,the main work of this paper is as follows: Firstly,this paper commented data mining,including the definition of data mining,the main process and main tec
7、hnology of data mining and so on. Secondly,paper introduces the basic theory of classification macroscopically,analyses and compares some decision tree algorithms,for example ID3,C4.5,CART etc.And emphasized on the ID3 algorithms of decision tree. Thirdly,the algorithm of decision tree optimized in
8、this paper is the improved algorithm combined with the ED(Effective- Degree) algorithm,and selects a new standard as split attribute.By testing the new algorithm on the training examples produces a decision tree we can conclude that:the improved algorithm can effectively improve the classification a
9、ccuracy and make up the shortcoming in choosing split attribute.Compared with the algorithm of ID3 which used widely,the improved algorithm has a good performance. Keyword: Datamining，Decision- Tree，ID3 原创性声明原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。 除文中已经注明引用的内容外， 本学位论文不包含任何他人或集体已经发表的作品内容， 也不包含本
10、人为获得其他学位而使用过的材料。 对本论文所涉及的研究工作做出贡献的其他个人或集体， 均已在文中以明确方式标明。 本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 日期： 关于学位论文版权使用授权的说明关于学位论文版权使用授权的说明 本人完全了解河北工业大学关于收集、保存、使用学位论文的以下规定：学校有权采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供本学位论文全文或者部分内容的阅览服务； 学校有权将学位论文的全部或部分内容编入有关数据库进行检索、 交流；学校有权向国家有关部门或者机构送交论文的复印件和电子版。 （保密的学位论文在解密后适用本授权说明） 学位论文作者签
11、名： 日期： 导师签名 ： 日期： 河北工业大学硕士学位论文 1 第一章第一章 绪绪 论论 随着数据库、网络等技术的迅速发展，人们积累的数据越来越多，人们需要有新的、更有效的方法对各种大量的数据进行分析、 提取以挖掘其潜能。 数据挖掘正是在这样的应用需求环境下产生并迅速发展起来的，它的出现为智能地把海量的数据转化为有用的信息和知识提供了新的思路和手段。 数据挖掘技术不仅是面向特定数据库的简单检索查询调用， 而且要对这些数据进行微观、 中观乃至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用己有的数据对未来的活动进行预测。分类挖掘是数据挖掘中的一种非常重要的
12、方法，可以应用于数据预测，划为决策树学习、贝叶斯分类、遗传算法和粗糙集等等。决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、 无规则的事例中推理出决策树表示形式的分类规则。 它采用自顶向下的递归方式， 在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支， 在决策树的叶结点得到结论。 1- 1 课题研究背景课题研究背景 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据库中表达信息的数据亦随着时间和业务的发展而急剧膨胀。人们需要对信息数据进行更高层次的处理，从中找出规律和模式，以帮助人们更好的进行决策和研究。目前，数据库系统虽然可以实现高效的数据录入
13、、查询、统计等功能，却无法发现数据中存在的关系和规则，无法利用现有的数据预测未来的发展趋势。正因为缺乏挖掘数据背后隐藏知识的手段和方法，从而导致了目前这种“数据爆炸但知识贫乏”的现象。面对这种“数据爆炸但知识贫乏”的挑战，数据挖掘技术应运而生，并得到了蓬勃发展，并越来越显示出其强大的生命力1。 数据挖掘是一个多学科交又研究领域。它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果。数据挖掘之所以被称为未来信息处理的骨干技术之一， 主要在于它以一种全新的概念改变着人们利用数据的方式。二十世纪，数据库技术取得了决定性的成果并
14、且已经得到广泛的应用。但是，数据库技术作为一种基本的信息存储和管理方式仍然以联机事务处理 OLTP(On- Line Tarnsactino Porcessing)为核心应用，缺少对决策、分析、预测等高级功能的支持机制。众所周知，随着数据库容量的膨胀特别是数据仓库 基于决策树的 ID3 算法的研究与改进 2 (DataWarehouse)以及 Web 等新型数据源的日益普及， 联机分析处理 OLAP、 决策支持(Decision Support)以及分类(Classification)聚类(Clusetring)等复杂应用成为必然，面对这一挑战，数据挖掘显示出强大的生命力，它使数据处理技术进入
15、了一个更高级的阶段，它不仅能对过去的数据进行查询，并且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地作出理想的决策，预测未来的发展趋势等。 数据挖掘的方法有多种，包括分类、预测、聚类、关联规则挖掘、序列模式挖掘等，其中分类是被广泛研究的课题之一。分类是指对给定的一组输入的属性向量，用归纳的方法将数据项映射到一个事先定义的类中的学习的过程，其目标是构建一个分类模型，在构造模型时需要知道训练集中每个样本所属的类，因此是有指导的学习方法。数据挖掘中应用分类方法的领域有很多，如金融市场走向的分类、大型图像数据库中对象的识别、医疗诊断、渔业生产、保险业务、顾客的信用度分析等。分类研究在国
16、外发展很快，己有很多成型的算法和模型，而在我国发展相对滞后。因此，数据挖掘分类算法的研究对数据挖掘技术有很大的意义。 目前，针对分类问题己有若干不同领域方法的算法，其中从机器学习中引出的决策树方法是一种较为通用并深入研究的分类函数逼近法。它是一种常用于预测模型的算法，通过将大量数据有目的的分类，从中找到具有价值的、潜在的信息。由于基于决策树的分类模型方法结构简单，便于人们理解，适合于大量数据，通常不需要训练数据外的知识等优点被人们广泛使用。目前，已有多种决策树算法，如 ID3、CLS、CART、SLIQ、SPRINT 等。 因此，对数据挖掘理论和算法的探讨将是长期而艰巨的任务。从上面可以看出，数据挖掘研究和探索的内容是及其丰富和具有挑战性的。本文正是在这样的背景下展开数据挖掘的相关研究。 1- 2 数据挖掘的研究现状数据挖掘的研究现状 决策树方法起源于概念学习系统(CLS：Concept Learning System)，国
