《毕业设计（论文）数据挖掘决策树算法的研究与改进》由会员分享，可在线阅读，更多相关《毕业设计（论文）数据挖掘决策树算法的研究与改进（34页珍藏版）》请在金锄头文库上搜索。
1、海南师范大学本科毕业论文海 南 师 范 大 学 本科生毕业论文（设计）题目：决策树算法的研究与改进姓 名： 学 号： 专 业： 计算机科学与技术 年 级： 05专升本 系 别： 计算机科学与教育技术 完成日期： 2007年5月20日 指导教师： 3本科生毕业论文（设计）独创性声明 本人声明所呈交的毕业论文（设计）是本人在导师指导下进行的研究工作及取得的研究成果，除了文中特别加以标注和致谢的地方外，本论文中没有抄袭他人研究成果和伪造数据等行为 。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。论文（设计）作者签名： 日期：2007年5月21日本科生毕业论文（设计）使
2、用授权声明海南师范大学有权保留并向国家有关部门或机构送交毕业论文（设计）的复印件和磁盘，允许毕业论文（设计）被查阅和借阅。本人授权海南师范大学可以将本毕业论文（设计）的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复印手段保存、汇编毕业论文（设计）。论文（设计）作者签名： 日期：2007年5月21日指 导 教 师 签 名： 日期： 目录1.引言12.决策树算法的研究22.1.基本定义22.1.1.归纳学习的基本概念22.1.2.信息论的基本概念22.1.3.决策树的基本概念32.2.几种常见的决策树算法的简单介绍42.2.1.ID3 算法42.2.2.C4.5算法简介112.2
3、.3.遗传算法GA(Genetic Algorithm)122.3.决策树的评价标准1132.4.决策树的进展与发展方向152.4.1.数据挖掘中决策树算法的主要进展152.4.2.决策树技术面临的挑战及目前研究方向153.关于决策树算法的改进153.1.基于样本离散度6的特征选择方法163.1.1.基本概念163.1.2.基于离散度的改进算法173.1.3.分析与比较183.1.4.小结183.2.利用条件概率的思想来改进决策树算法183.2.1.算法的理论基础与基本思想193.2.2.举例分析193.2.3.分析与比较273.2.4.小结274.总结285.结束语286.致谢28参考文献2
4、9挖掘决策树算法的研究与改进作者： 指导老师：（海南师范大学，海口，571158）摘 要：在大量信息展现给人们的时候，“知识爆炸”给人们带来了极大的困扰，如何有效的利用数据成为人们事业成败的关键。本论文主要对决策树的常见算法做初步的研究与探讨，并给出决策树的评价标准。并在此基础上利用最新的决策树算法思想由本人设计实例集验证相关文献中笔者的思想，最后提出自己一点意见和看法。关键词：数据挖掘；决策树；研究；改进 The Research and Improvement Of Data Mining decision-making tree algorithm Author: Tutor: (Hai
5、nan Normal University,HaiKou,571158)Abstract: Nowadays there are so much information tounfold in the people at present, which causes our eyes taking out all in, the knowledge explosion has brought the enormous puzzle to the people, how does the effective use data become the people enterprise success
6、 or failure the key. This paper mainly discussed the preliminary research and the discussion to the policy-making trees common algorithm, and produces the policy-making trees evaluation criteria, as well as to policy-making tree future discussion. Using the newest policy-making algorithm thought in
7、this foundation to design in the example collection confirmation correlation literature after myself authors thought, finally proposes a Propose his viewpoint and the view.Key words: Data Mining; decision-making tree; Research; Improvement1.引言随着现代信息技术的飞速发展，在全球范围内掀起了信息化（Information）浪潮。信息产生的渠道多而且宽广，更新
8、的频率日益加快，各行业均产生了大量的信息。面对大量多的数据，人们往往无法找到自己所需要的知识或信息，这就是所谓“信息爆炸3”（Information detonation）以及它给人们带来的困惑。如何有效地利用和处理大量的信息成为当今世界共同关心的问题。随着数据库技术（Database technology）、人工智能（Artificial intelligence）、数理统计（Mathematical statistic）和并行计算（Parallel computation）等技术的发展与融合，数据挖掘（data mining，DM）技术应运而生。自数据挖掘技术诞生以来，关于数据挖掘技术的研
9、究也就开始了。数据挖掘是一门新兴的交叉学科，自提出以来，引起了众多专家学者的广泛关注，数据开采（Data mining）、数据采掘（Data excavation）、知识发现（Knowledge discovery）和信息抽取（Information extracts）等许多同义词相继出现。目前，普遍采用的主要有数据挖掘（DM）和数据库中的知识发现（Knowledge Discovery in Database，简称KDD）。数据挖掘有广义和狭义之分，广义的数据挖掘，指从大量的数据中发现隐藏的、内在的和有用的知识或信息的过程。狭义的数据挖掘是指知识发现中的一个关键步骤，是一个抽取有用模式或建立
10、模型的重要环节。数据挖掘是在对数据实例集全面而深刻认识的基础上，对数据内在和本质的高度抽象与概括，也是对数据从感性认识到理性认识的升华2。如今有多种数据挖掘技术方法，可以分为两大类。决策树就是其中的一种，决策树主要是基于数据的属性值进行归纳分类，常用于分类的层次方法有“if-then1”规则。决策树方法的最大优点就是可理解性，比较直观。它与神经网络（另外一种数据挖掘技术方法）最大的区别是，决策树可以解释如何得出结果的决策过程。其缺点是处理复杂性的数据时，分支数目非常多，管理难度大。同时，还存在数据的“缺值”处理问题。其经典算法有ID3、C4.5、CART、CHAID、SLIQ和SPRINT等。
11、本论文主要对决策树的常见算法（ID3算法、C4.5算法）做初步的研究与探讨，（由于遗传算法与决策树的构造类型相似，这里也有涉及。）并给出决策树的评价标准以及决策树的发展现状和以后的发展方向。并在此基础上利用最新的决策树算法思想由本人设计实例集验证相关文献中笔者的思想，最后提出自己一点意见和看法。2.决策树算法的研究2.1.基本定义2.1.1.归纳学习的基本概念归纳学习(induction Learning) 是符号学习中研究最为广泛的一种方法。给定关于某个概念的一系列已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得新的概念，创立新的规则，发现新的理论。它的一般操作是泛化（gen
12、eralization）和特化（specialization）。泛化用来扩展一假设的语义信息，以使其能够包含更多的正例，应用于更多的情况。特化是泛化的相反操作，用于限制概念描述的应用范围。2.1.2.信息论的基本概念信息论在决策树学习中有着重要的意义，1948年Shannon1提出并发展了信息论，研究以数学的方法度量并研究信息。通过通信后对信源中各种符号出现的不确定程度的消除来度量信息量的大小。他提出了一系列概念：（1）自信息量。在收到之前，收信者对信源发出的不确定性定义为信息符号的自信息量。即，其中为信源发出的概率。（2）信息熵。自信息量只能反映符号的不确定性，而信息熵可以用来度量信源X整体
13、的不确定性，定义如下： H（X）=p()I（）+P（）I（）+P（）I（） = -其中r为信源X所有可能的符号数，即用信源每发一个符号所提供的平均自信息量来定义信息熵。（3）条件熵。如果信源X与随机变量Y不是相互独立的，收信者收到信息Y。那么，用条件熵H（X/Y）来度量收信者在收到随机变量Y之后，对随机变量X仍然存在的不确定性。设X对应信源符号，Y对应信源符号，为当Y为时X为的概率，则有： H（X/Y）= -（4）平均互信息量。用它来表示信号Y所能提供的关于X的信息良的大小，用I（X，Y）表示： H（X，Y）= H（X）-H（X/Y）信息论的这些基本概念，对决策树来说是非常重要的，是决策树算法
14、的设计与实现基础。2.1.3.决策树的基本概念决策树是定义布尔函数的一种方法,其输入是一组属性描述的对象,输出为yes/ no 决策。它代表一个假设,可以写成逻辑公式。其表达能力限于命题逻辑,该对象的任一个属性的任一次测试均是一个命题。在命题逻辑范围内,决策树的表达能力是完全的。一棵决策树可以代表一个决定训练实例集分类的决策过程,树的每个结点对应于一个属性名或一个特定的测试,该测试在此结点根据测试的可能结果对训练实例集进行划分。划分出的每个部分都对应于相应训练实例集子空间的一个分类子问题,该分类子问题可以由一棵决策树来解决。因此,一棵决策树可以看作是个对目标分类的划分和获取策略。一棵决策树的内
15、部结点是属性或属性的集合（又称测试属性），叶结点是所要学习划分的类。根据决策树各种不同的属性，可分为以下几种：（1）决策树的内结点的测试属性可能是单变量的，即每个内结点只包含一个属性。也可能是多变量的。（2）根据测试属性的不同属性值的个数，可能使得每个内结点有两个或多个分支。如果每个内结点只有两个分支则称之为二叉决策树。（3）每个属性可能是值类型，也可能是枚举类型。（4）分类结果既可能是两类有可能是多类，如果只有两类则称为布尔决策树。因为决策树有不同的等价表示形式，所以会有不同的算法来实现与决策树学习相同的功能。例如：ID3、C4.5、CART、CHAID、SLIQ和SPRINT等等。2.2.几种常见的决策树算法的简单介绍2.2.1.ID3 算法2.2.1.1.ID3 算法简介
