决策树分类算法数据挖掘

1、欢迎共阅本科毕业论文（设计）（题目：决策树分类算法在教学分析中的应用）姓 名：学 号：专 业：计算机科学与技术院 系： 信息工程学院指导老师：袁张露职称学历：助教/研究生完成时间：教务处制安徽新华学院本科毕业论文（设计）独创承诺书本人按照毕业论文（设计）进度计划积极开展实验（调查）研究活动，实事 求是地做好实验（调查）记录，所呈交的毕业论文（设计）是我个人在导师指导 下进行的研究工作及取得的研究成果。据我所知，除文中特别加以标注引用参考 文献资料外，论文（设计）中所有数据均为自己研究成果，不包含其他人己经发 表或撰写过的研究成果。与我一同工作的同志对本研究所做的工作己在论文中作 了明确说明并表

2、示谢意。毕业论文（设计）作者签名：日期：决策树分类算法在教学分析中的应用摘要随着信息科技的高速发展，人们对于积累的海量数据量的处理工作也日 益增重，需求是发明之母，数据挖掘技术就是为了顺应这种需求而发展起來 的一种数据处理技术。数据挖掘技术乂称数据库中的知识发现，是从一个大规模的数据库的数 据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。在学生 管理以及教学科学化的今天，传统的教学分析己经不能适应社会发展的需求。学生信息数据不断的增多，教学分析工作也日益加重。学生信息数据量 不断的增多，对之前所累计的大量学生考试成绩数据运用数据挖掘技术进行 分析挖掘是具有重大的意义的，这样可以把所

3、挖掘分析出來的信息反馈用于 指导学校的教学分析，从而提高学生的学习成绩。本文通过学生成绩信息运用数据挖掘技术，对所采集的数据进行预处理, 运用决策树分类算法中的C4. 5算法对成绩进行分析得到了成绩分析决策树, 分析研究出有用的信息找到影响学生的因素，发现某些规律的存在，用以指 导学校教学分析工作的开展。关键词:数据挖掘；学生成绩；决策树Application of decision tree in computer grade examinationanalysisAbstractWith the rapid development of Information Technology, pe

4、ople are facing much more work load in dealing with the accumulated mass data However, Data Mining Technique is a kind of data processing technique that follows this change In recent years, colleges and other institutions of higher education had increased their enrollments, more and more students go

5、t enrolled and consequently, the students information data pool gets much bigger However, the traditional data processing technology can， t accommodate itself to study and analyze the accumulated mass data at a deeper level any more, while Data Mining Technique can solve these problems much better.T

6、he increasing data base of the students concludes much, like students test score With the rapid development of computer technology, Computer Rank Examination becomes more and more popular; hence, the data base of students， test score becomes much bigger So, to use Data Mining Technique to mine the a

7、ccumulated mass CRE score is of great meaning with regarding to the improvement of the studentsJ score on CRE, since people can apply the results of data mining in school computer teaching researchThis paper intends to show the use of Data Mining Technique in the analysis of studentsJ score informat

8、ion in Computer Rank Examination, from the pretreatment on the collected data to the use of decision tree technique in data analysis This employs ID3 algorithm in decision tree technique to get the decision tree of the students， score Then byanalyzing the useful information to find out the elements

9、that can11.1.1.1.22.2.2.2.2.2.2.2.2.2.2.2.33.绪论12数据挖掘的产生1研究背景与意义1错误!未定义书签。3数据挖掘的国内外研究现状24论文研究内容及结构安排2数据挖掘技术31数据挖掘的概念31. 1数据挖掘的定义42数据挖掘的过程42. 1数据对象确立阶段42. 2数据挖掘阶段2. 2数据预处理阶段5错误!未定义书签。2. 3结果的解释和评估阶段错误!未定义书签。8错误!未定义书签。1011123数据挖掘的主要方法4数据挖掘的功能5数据挖掘的系统结构.6数据挖掘应用的成功案例7本章小结决策树技术1决策树简介123. 2决策树的主要算法123. 2.

10、1 ID3 算法133. 2. 2 C4. 5 算法143. 3决策树剪枝173. 3. 1决策树剪枝的方法183. 4本章小结194决策树在计算机等级考试成绩分析中的应用204. 1成绩分析方法的依据204.2决策树算法在计算机等级考试成绩分析中的应用204. 2. 1确定对象集目标204.2.2数据的采集214. 2. 3数据预处理224.2.4数据挖掘工作的展开234. 2. 5结果分析265总结与展望265. 1研究结果265. 2后续研究与展望27参考文献28研究背景与意义无论在企业应用领域，还是在科学领域，数据挖掘技术有着广泛的应用价值。 在企业应用领域，用于制定好的市场策略以及企

11、业的关键性决策。在商业方面， 数据挖掘技术可以增强企业的竞争优势，缩短销售周期，降低生产成本，有助于 制定市场计划和销售策略，并己经成为电子商务中的关键技术。近年來，随着我国高等教育的飞速发展，高校的教学管理信息不断增多。教 学工作信息化有了很大的进步，好多高校在管理学生和教师信息方面有了很好的 方式。比如我校的教务系统，这些系统为老师和学生提供了很好的帮助。这些系 统中积累了大量的数据。目前的这些数据库系统虽然基本上都可以实现数据的录 入、修改、统计、查询等功能，但是这些数据所隐藏的价值并没有被充分的挖掘 和利用，信息资源的浪费还是比较严重的。随着数据挖掘技术的不断扩展，许多高校为了避免信息

12、浪费，己经将数据挖 掘技术应用于高校的教学分析中。数据挖掘技术的应用将对提高学生成绩和提高 教学水平起到很好的指导作用。为了提高教学质量，将数据挖掘技术引入到高校学生成绩分析中，对这些数 据进行深入的挖掘和合理的分析，从而挖掘出传统的分析方法所无法得出的结论。 进而利用分析结果引导教学的开展，从而有利于提高教学质量。本文主要是基于如下背景开展的：以安徽新华学院历届学生成绩为背景，首 先学习数据挖掘的理论知识以及决策树技术，然后建立新华学院学生成绩数据库, 并利用数据挖掘技术中的决策树对自己建立的数据库进行深入的挖掘。最后对自 己的挖掘结果进行分析，得到影响学生成绩的因素。从而更好的辅助今后学校

13、的 教学分析工作。1.2数据挖掘的国内外研究现状1989年8月在美国召开的第十一届国际人工智能联合会议的专题讨论会 上，与数据挖掘(Date Mining)极为相似的术语一一从数据库中发现知识一词 被提出。1993年以后，美国计算机协会美年都举行了专门研究探讨数据挖掘技 术的会议，会议的规模也发展成为国际学术大会，并且在各个领域里取得了很多 研究成果。最近，Gartner Group的一次高级技术调查将数据挖掘和人工智能列 为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并 行处理体系和数据挖掘列为未來五年内投资焦点的十大新兴技术前两位。根据 最近Gartner的HPC研究

14、表明，“随着数据捕获、传输和存储技术的快速发展, 大型系统用户将更多地需要釆用新技术來挖掘市场以外的价值，采用更为广阔的 并行处理系统來创建新的商业增长点。”国外研究数据挖掘的组织、机构或大学很多。比较着名的如卡内基梅隆大学、 斯坦福大学、麻省理工学院。着名的研究机构如：ACM、KDNet、NCDM等。国外 比较着名的挖掘工具:IBM公司的Intelligent Miner、SAS公司的Enterprise Miner SGI 公司的 SetMiner、SPSS 公司的 Clementines Oracle Darwin 等。不 少的软件在国外得到了广泛的应用，并收到了明显的效益。与国外相比，

15、国内对DMKD的研究稍晚，没有形成整体力量。1993年国家自 然科学基金首次支持我们对该领域的研究项目。目前，国内的许多科研单位和高 等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中 科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统 工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在 开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科技 大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和 改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数 据的知识发现以及Web数据挖掘。1

16、3论文研究内容及结构安排本课题的主要工作是将数据挖掘技术和学校的信息管理系统相结合，新华学院多 年來的信息化教学管理工作积累了大量的教学数据，从新华学院的数据库中收集 学生的考试成绩信息。利用数据挖掘技术对这些数据进行分析，获得影响学生成 绩的因素，更好的辅助学校如何提高学生成绩以及提高教学质量。本课题根据指导老师提供的11级学生成绩的信息，建立安徽新华学院11 级学生成绩库，采用数据挖掘技术对成绩库进行挖掘。通过对实验结果进行深入 分析，获得影响学生考试成绩的因素，辅助教师在以后的教学工作中釆用更恰当 的教学方式，指导学生应该具有什么样的学习态度，从而提高学生考试成绩。论文结构如下：第一章

17、绪论。主要介绍了论文的研究背景与意义，叙述了国内外数据挖 掘技术的研究现状。第二章 数据挖掘的基础知识。 主要叙述了数据挖掘的定义、数据挖掘的 过程以及数据挖掘的方法。第三章 决策树。主要简要介绍了决策树以及决策树的经典算法。第四章 决策树在计算机等级考试成绩分析中的应用第五章总结与展望。总结本篇论文并展望今后论文的继续研究方向内容方 向。2数据挖掘技术2. 1数据挖掘的概念2.1.1数据挖掘的背景随着信息技术的高速发展，人们积累的数据量急剧增长，如何从海量的数据中提 取有用的知识成为当务之急。数据库技术的成熟以及数据应用的普及，虽然目前 的数据库系统可以高效的实现数据的录入、查询、统计的功能

18、，但无法发现数据 中潜在的信息和价值，无法利用这些数据來预测未來的发展趋势。于是，新的问 题就被提出來了：人类如何在这浩瀚的数据中及时发现有用的知识，提高数据的 利用率呢？在不懈的努力下，从数据库中发现知识(Knowledge Discovery inDatebases)及其核心技术数据挖掘(Date Mining)便应运而生，并得以蓬 勃的发展，越來越显出其强大的生命力。2.1.1数据挖掘的定义数据挖掘(Data Mining), 乂译为资料探勘、数据采矿。它是数据库中的知 识发现(Knowledge Discovery in Datebases,简称：KDD),是目前人工智能和数 据库领域

19、研究的热点问题，数据挖掘一般是指从大量的数据中通过算法搜索隐藏 于其中信息的过程。所谓数据挖掘是指从大量的、不完全的、有噪声的、模糊的、 随机的数据中自动搜索隐藏于其中的有着特殊关系的信息，提取隐含在其中的, 人们事先不知道的、但乂是潜在有用的信息和知识的过程。2. 2数据挖掘的过程数据挖掘(Data Mining)的过程可以分为以下儿个部分：理解数据和数据的 來源(understanding) 获取相关知识与技术(acquisition)、整合与检查 数据(integration and checking)、去除错误或彳、一致的数据(data cleaning) 建立模型和假设(model

20、and hypothesis development) 实际数据挖掘工作 (data mining) 测试和验证挖掘结果、解释和应用(interpretation and use)。 大概可以四个部分数据对象的确立(Date Object Determined)数据预处理(Date Preprocessing)、数据挖掘(Date Mining)及结果的解释和评估(Interpretation and Evaluation)。图2. 1数据挖掘的过程2.2.1数据对象的确立明确我们研究问题所需要的数据，理解数据并提出问题，需要进行数据挖掘的数 据信息，明确数据挖掘的目标的定义。确定数据挖掘目标

21、是数据挖掘重要的一步。 我们进行数据挖掘时，挖掘的结果往往是不可预测的，但对要进行挖掘的目标是 可预见的，即明确数据挖掘的最终目标。数据对象的确立，包括对大量数据的选取、数据属性的确定等。本文是安 徽新华学院学生成绩的数据挖掘技术应用，这些数据包含新华学院历届的学生考 试成绩数据，数据属性包括学生姓名、性别。年龄、专业、成绩等。2. 2. 2数据预处理阶段现实世界中数据大体上都是不完整的、含有噪声的、其至不一致的脏数据，我们 无法直接对其进行数据挖掘，或者挖掘结果会差强人意。为了提高数据挖掘的质 量，人们提出了数据预处理技术山:。数据预处理是数据挖掘过程中的一个很重要的步骤，数据预处理有很多种

22、方 法，一般将数据预处理乂分为四个步骤：数据清洗、数据集成、数据变换、数据 归约。数据清洗处理过程通常包括：填补遗漏的数据值、光滑有噪声数据、识别或 删除异常值、以及解决不一致问题。数据集成就是将多个数据源的数据合并到一起并统一存储，建立数据仓库的 过程实际上就是数据集成。在数据集成时要特别注意消除数据的冗余。数据变换主要是对数据进行规格化操作，将数据转换成适用于数据挖掘的形 式。数据挖掘时对应的数据量往往是非常大的，数据归约是缩小所挖掘数据的规 模，但保持数据的完整性。2. 2. 3数据挖掘阶段数据挖掘阶段是数据挖掘的核心步骤，也是技术难点所在。而数据挖掘阶段 的核心就是模式的发现此阶段主要

23、是确定对数据进行分类还是聚类，确定数据的关联规则等等。然 后确定用什么数据挖掘算法对数据进行挖掘，再利用数据挖掘的工具和一系列方 法对之前所确定以及转换后的数据进行分析、产生一个特定的有意义的模式以更 好的对己处理好的数据进行分析，获取有用信息。2.2.4结果的解释和评估阶段数据挖掘阶段会产生的模式或数据集经过评估存在冗余或多余的模式，这时 需要将其剔除，过滤出有用的知识。过滤后用于呈现给用户；一般情况下，为了 方便用户理解产生的模式，处理员应该利用可视化技术将数据挖掘产生的有意义 模式以图形或者其他可视化的形式表示，让用户更容易理解。例如把分类决策树 转换为"ifthen”的形式。

24、如果数据挖掘过程中的发现的知识不能满足用户的需求，我们则需要重新对 数据进行处理，选择一些其他的数据挖掘方法、算法对数据进行再次挖掘，并分 析结果，直到满足用户的需求。2. 3数据挖掘的主要方法（1）关联规则在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概 念由AgrawaK Imielinskix Swami提出，是数据中一种简单但很实用的规则。 关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。关 联规则是描述了数据库中数据项之间所存在的关系的规则，即根据一个事务中某 些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互 关系。（2）决

25、策树所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起來的树。一种用树枝状展现数据受各变量的影响情况的分析预测模型，根据对目标变 量产生效应的不同而制定分类规则，它是建立在信息论基础之上，对数据进行分 类的一种方法。它首先通过一批己知的训练数据建立一棵决策树，然后采用建好 的决策树对数据进行预测。决策树的建立过程是数据规则的生成过程，因此这种 方法实现了数据规则的可视化，其输出结果容易理解，精确度较好，效率较高, 因而较常用。常用的方法有分类及回归树法、卡方自动交互探测法等。?决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。 树中每个节点表示某个对象，而每个分叉路径

26、则代表的某个可能的属性值，而每 个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅 有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数 据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进 行分析。本质上决策树是通过一系列规则对数据进行分类的过程。（3）神经网络一种模仿人脑思考结构的数据分析模式，由输入变量或数值中自我学习并根（7）粗糙集粗糙集算法将知识理解为对数据的划分，每一被划分的集合称为概念，主要 思想是利用己知的知识库，将不精确或不确定的知识用己知的知识库中的知识来

27、 近似刻划处理粗糙集理论，是继概率论、模糊集、证据理论之后的乂一个处理不 确定性的数学工具。作为一种较新的软计算方法，粗糙集近年來越來越受到重视， 其有效性己在许多科学与工程领域的成功应用中得到证实，是当前国际上人工智 能理论及其应用领域中的研究热点之一。在很多实际系统中均不同程度地存在着 不确定性因素，釆集到的数据常常包含着噪声，不精确其至不完整。它将知识理解为对数据的划分，每一被划分的集合称为概念，主要思想是利 用己知的知识库，将不精确或不确定的知识用己知的知识库中的知识來近视刻划 处理。24数据挖掘的功能数据挖掘的功能是从大型数据集中提取人们感兴趣的知识，这些知识是隐含 的、具有一定可信

28、度的、对用户而言是新颖的且有潜在价值的知识，提取的知识 表示为概念、规则、模式等多种形式。一般情况下，数据挖掘的任务可以大体分为两类：描述和预测。描述性挖掘 任务描述数据库中数据的一般性质，而预测性挖掘任务是指对当前数据进行处理、 分析和推断，以做出相应的预测。数据挖掘在实际的工作中，有时候用户并不清楚自己需要什么样的数据，因 此数据挖掘工作有必要挖掘出多种类型的模式，以达到满足不同的用户需求和应 用。一般情况下，数据挖掘的功能以及可能发现的模式类型如下：（1）分类目的是构造一个分类函数或分类模型（也常常称作分类器），该模型能把数 据库中的数据项映射到给定类别中的某一个。要构造分类器，需要有一

29、个训练样 本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有 关字段（乂称属性或特征）值组成的特征向量，此外，训练样本还有一个类别标 记。一个具体样本的形式可表示为：（vl, v2,，vn； c）,其中vi表示字段 值，c表示类别。例如：银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据 这些來区分新申请贷款的客户，以釆取相应的贷款方案。(2) 关联分析关联分析就是从大量的数据中发现项集之间有趣的关联或因果结构。关联分析展示了属性与值频繁的在给定的数据集中的一起出现的条件。一般 如下形式：如X=Y,即AnBlA.BJ'的规则。其中，Aie(il, -.m)

30、?,BjG (j 1,.n)是属性一值对。关联规则XF 即表示“满 足X中条件的数据库元组多半也满足Y中的条件”。简而言之，就是分析两个事物之间的一些特性，通过一个事物去预测另外一 个事物，这就是关联分析。(3) 概念/类描述概念描述(concept description)就是通过对与某类对象关联数据的汇总、 分析和比较，对此类对象的内涵进行描述，并概括这类对象的有关特征。 这种描述是汇总的、简洁的和精确的知识。(4) 聚类分析聚类分析就是将物理或抽象对象的集合分组成由类似的对象组成的多个类的过 程。聚类是把整个数据库分成不同的群组。它的目的是使群与群之间差别很明 显，而同一个群之间的数据尽

31、量相似。这种方法通常用于客户细分。在开始细分 之前不知道要把用户分成儿类，因此通过聚类分析可以找出客户特性相似的群体, 如客户消费特性相似或年龄特性相似等。在此基础上可以制定一些针对不同客户 群体的营销方案。对象根据最大化类内部的相似性、最小化类之间的相似性的原则进行聚类或 分组。也就是说，对象的簇(cluster)这样形成，使得相比之下在一个簇中的 对象具有很高的相似性，而与其他簇中的对象很不相似。所形成的每个簇可以看 作一个对象类，由它可以导出规则。聚类也便于分类法组织形式(taxonomy formation),将观测组织成类分层结构，把类似的事件组织在一起。通过聚类，人们能够认识到密集

32、和稀疏的区域，因而发现全局的分类模式, 以及数据属性之前的相互关系。（5）离群点分析数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是离群点（outlier） o大部分数据挖掘方法将离群点视为噪声或异 常而丢弃。然而，在一些应用中（如欺骗检测），罕见的事件可能比正常出现的 事件更令人感兴趣。离群点数据分析称作离群点挖掘（outlier mining）。可以假定一个数据分布或概率模型，使用统计检验检测离群点；或者使用距 离度量，将远离任何簇的对象视为离群点。基于偏差的方法通过考察一群对象主 要特征上的差别來识别离群点，而不是使用统计或距离度量。（6）演变分析数据演变

33、分析（evolution analysis）描述行为随时间变化的对象的规律或趋势, 并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联和相关分析、 分类、预测或聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模 式匹配和基于相似性的数据分析。25数据挖掘应用的成功案例（1）、中国宝钢集团（直接数据挖掘，分类分析方法）宝钢自1985年投产至今，积累了大量的生产数据，从每一炉钢到每一块板 坯到每一个钢圈，各级计算机系统可以把这些数据完整地收集起來。釆用数据挖 掘技术对钢材生产的全流程进行质量监控和分析（通过全流程实时监控获得了丰 富的生产数据），构建故障地图，实时分析产品出现瑕疵的

34、原因，有效提高了产 品的优良率。宝钢釆用了两个数据挖掘工具，一个是自行研发的基于SAS的practicalMiner,另一个是美国SAS公司的Enterprise Miner。在冷轧和热轧的产品质量 控制中，仅2001年就取得超过3000万元的经济效益。在配矿优化项目中，通过 确定不同铁矿石的合理比例，每年可为宝钢降低成本6000万元。另外，通过分 析轧制计划，分析和优化库存结构，降低库存成本和平衡物流成本Credilogros CiaFinanciera S. A.是阿根廷第五大信贷公司，资产估计价值为9570万美元， 对于Credilogros而言，重要的是识别与潜在预先付款客户相关的潜在

35、风险，以 便将承担的风险最小化。（2）、沃尔玛超市里的尿布与啤酒（间接数据挖掘，关联规则）大家都应该了解这个事件，数据挖掘中的经典成功案例。在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个 奇怪的举措却使尿布和啤酒的销量双双增加了。沃尔玛拥有世界上最大的数据仓 库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行 为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里 集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利 用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起 购买最多的商品竟是啤酒！经过大量

36、实际调查和分析，揭示了一个隐藏在"尿布 与啤酒背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要 到超市去买婴儿尿布，而他们中有30%40%的人同时也为自己买一些啤酒。产 生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而 丈夫们在买尿布后乂随手带回了他们喜欢的啤酒。（3）、股票预测股票市场是一个具有大量相互作用因素的复杂系统，它受政治形势、金融政 策、公司状况和重大消息等多方面因素的影响。股票价格一般要受一国货币、财 政政策、物价、利率、汇率、上市公司重大事项、国际经济环境、投资者心理等 信息的作用，其内部规律非常复杂，变化周期无序，更使行情的走势变

37、化莫测。利用决策树分类算法中的ID3算法并适当调整以对股票交易数据样本集进 行测试分析，由此生成决策树作为分类器并对其结果进行了检验，最后根据决策 树分类规则开发出一淘股票分析预测系统。更早之前,通过相关分析，可以找出一支股票与另一支股票走势的潜在规律， 比如数据挖掘曾经得到过这个结论“如果微软的股票下跌4%,那么IBM的股票 将在两周内下跌5%”2. 7本草小结本章在介绍数据挖掘基本概念的基础上，简要的概括了数据挖掘的过程、数 据挖掘的方法、数据挖掘的功能，并简要介绍了几个数据挖掘应用的成功案例。这些基本理论知识为数据挖掘的实践应用研究奠定了理论基础。3决策树技术3. 1决策树简介随着社会的

38、发展，数据挖掘显的尤为的重要。在数据挖掘中决策树算法是目 前数据挖掘领域中应用的最广泛、最流行的推理算法之一。决策树分类算法是将 数据分类、预测和规格的提取。随着ID3算法和C4.5算法的提出，决策树技术 在数据挖掘领域得到了进一步的拓展，并且在人们生产生活中得到了广泛应用。 决策树是一种根据自变量的值进行递归划分以及预测因变量的方法。决策树的主 要作用是揭示数据中的结构化信息。它提供一种在什么条件下会得到什么值的类 似规则的方法。若因变量为分类变量，我们称相应的决策树为分类树；若因变量 为连续变量，我们称相应的决策树为回归树。分类树对离散变量做决策树，回归 树对连续变量做决策树。一般的数据挖

39、掘工具，允许选择分裂条件和修剪规则, 以及控制参数（最小结点的大小，最大树的深度等等），來限制决策树的。决策 树作为一棵树，树的根节点是整个数据集合空间，每个分节点是对一个单一变量 的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于一类别 的记录。图3.1为以典型的决策树。图3.1决策树3. 2决策树的主要算法近年來，决策树方法在很多机器学习、知识的探究等过程中得到了广泛的应 用。迄今为止，国内外研究人员先后提出了十几种决策树的分类方法，因此决策 树的算法还是挺多的，本文介绍了两种比较经典的决策树算法，分别是ID3算法 和C4.5算法。3. 2.1 ID3 算法ID3 (indu

40、ction decision-tree)算法，它是一种用来由数据构造决策树的递归过 程，是在1986年由Quinlan首先提出的，该算法以信息论为基础，信息论是数 学中的概率论和数理统计的一个分支，用于处理信息和信息爛、通信系统、数据 传输和率失真理论、密码学、信噪比、数据压缩和相关课题。以信息爛和信息增 益度为衡量标准，从而实现数据的归纳分类，它是一个从上到下、分而治之 的归纳过程。ID3算法的大概过程是：我们试探性的选择一个属性放置在根节点，并对该 属性的每个值产生一个分支。这样，分裂根节点上的数据集，并一道子女节点, 产生一个局部的树。在决策树各级结点上选择属性时，通过计算信息增益来选择

41、 属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录的最大的类 别信息。其具体方法是：我们需要检测所有的属性，在它们中间选择信息增益最 大的属性作为决策树结点，由该属性的不同取值建立分支，再对各分支的子集递 归调用该方法建立决策树结点的分支，直到所有的子集仅包含同一类别的数据为 止。最后得到的一棵决策树，它可以用來对新的样本进行分类。要想了解ID3算法，我们要了解ID3算法中的一些基本概念：爛爛是一个物理名词，源于热力学的概念，数值为温度除热量所得的值。1948 年Shannon提出并发展了信息论并引入了信息爛。一个训练集合S根据类别属性的值被分成m个互相独立的类G、G、. .、5

42、则识别D的一个元组所属哪个类所需的信息量为Inf。(S) o设G.d是S中C, 类的元组的集合，C.的概率分布，P二P.-PJ ,任意元组属于分类G的概率 为匕，则由该分布传递的信息量称为S的爛，记为：Info (S) = -士 PJog：(巳)=Plog2 P®-Plog2 POZ=1上述公式中，p+代表正样例，而P-则代表反样例。(2)信息增益度信息增益度是两个信息量之间的差值，？己经有了爛作为衡量训练样例集合 纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。这个标准被称 为"信息增益(information?gain)"。简单的说，一个属性的信息增

43、益就是由 于使用这个属性分割样例而导致的期望爛降低(或者说，样本按照某属性划分时 造成爛减少的期望)。更精确地讲，一个属性A相对样例集合S的信息增益 Gain(S,A)被定义为：G (S,A)=Info (D) -Info (A)最后根据信息增益最大的原则选择根节点來构成决策树。3. 2. 2 C4. 5 算法C4. 5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行 改进后的一种重要算法，相比于ID3算法，改进有如下儿个要点：1、用信息增益率來选择属性。ID3选择属性用的是子树的信息增益，这里以用 很多方法來定义信息，ID3使用的是® (entropy, 是一种不纯度

44、度量准则)， 也就是爛的变化值，而C4. 5用的是信息增益率。2、在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造 的决策树过适应(Overfitting),如果不考虑这些结点可能会更好。3、对非离散数据也能处理。4、能够对不完整数据进行处理由于ID3算法在实际应用中的一些局限,Quinlan再次改进了 ID3算法。C4. 5 算法是ID3算法的改进版本，C4.5算法可以处理多种数据类型。此外，C4.5的 效率相比于ID3算法也有了很多的提高。通过对ID3算法的介绍我们己经了解爛，和信息增益。在C4. 5算法中我们 引入了新的概念信息增益率。C4.5算法的具体步骤如下：(1)

45、 创建节点N；(2) 如果训练集为空，在返回节点N标记为Failure；(3) 如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N；(4) 如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；(5) for each 候选属性 attribute_list；(6) if候选属性是连续的then：(7) 对该属性进行离散化；(8) 选择候选属性attribute_list中具有最高信息增益的属性D：(9) 标记节点N为属性D；(10) for each属性D的一致值d；(11) 由结点N长出一个条件为D二d的分支；(12) 设s是训练集中D二d的训练样本的集合；(13) i

46、f s 为空；(14) 加上一个树叶，标记为训练集中最普通的类；(15) else 加上一个有 C4. 5 (R - D,C, s)返回的点。我们以一个典型被引用多很多次的数据训练集D为例，來说明C4. 5算法如何计 算信息节点并切选择决策树结点。如图3. 2:天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消图3. 2根据图3. 2我们可以看出上面的训练集有4个属性：天气，温度，湿度，风速,而类标签有2个，即类标签

47、集合C二Yes, No,分别表示适合户外运动和不适合 户外运动。根据前面的介绍，我们來计算信息爛，信息增益，以及信息增益率。数据D中一共用14个训练样本，其中9个为正样例，5个位反样例。因此它的 信息爛为：Info (D) =-9/14*log2 (9/14) -5/141og2 (5/14) =0. 940下面计算属性集合中每个属性的信息爛：1： Info(天气)=5/14 * - 2/5 * log2 (2/5) - 3/5 * log2 (3/5)1 + 4/14 * - 4/4 * log2(4/4) - 0/4 * log2(0/4)1 + 5/14 * - 3/5 * log2(3

48、/5)- 2/5 * log2 (2/5)1 = 0.6942： Info(温度)=4/14 * - 2/4 * log2(2/4) - 2/4 * log2(2/4) + 6/14 * - 4/6 * log2(4/6) - 2/6 * log2(2/6)1 + 4/14 * - 3/4 * log2(3/4)- 1/4 * log2 (1/4)1 = 0.9113： Info(湿度二 7/14 * - 3/7 * log2(3/7) - 4/7 * log2(4/7) + 7/14 * -6/7 * log2(6/7) - 1/7 * log2(l/7) = 0. 7894： Info(风

49、速)二 6/14 * - 3/6 * log2(3/6) 3/6 * log2(3/6)1 + 8/14 * -6/8 * log2(6/8) - 2/8 * log2 (2/8) = 0. 892根据上面的数据我们可以计算出信息增益:0. 940 - 0. 694 = 0. 2460.940 - 0.911 = 0. 0290. 940 - 0. 789 = 0. 1511： Gain(天气)=Info (D) - Info(天气)2： Gain(温度)=Info(D) - Info(温度)3： Gain(湿度)=Info(D) - Info(湿度)4： Gain(风速)Info (D) -

50、 Info (风速)二 0. 940 - 0. 892 = 0. 048接下來，我们计算分裂信息度量H(V)：1、天气属性属性天气有3个取值，其中晴有5个样本、雨有5个样本、阴有4个样本，则H(天气)=- 5/14 * log2 (5/14) - 5/14 * log2(5/14) - 4/14 * log2 (4/14)2、温度属性属性温度有3个取值，其中热有4个样本、适中有6个样本、寒冷有4个样本, 则H（温度3、湿度属性属性湿度有2个取值，其中高有7个样本、正常有7个样本，则H （HUMIDITY） = - 7/14 * log2（7/14） - 7/14 * log2 （7/14） =

51、1.04、风速属性属性风速有2个取值，其中强有6个样本、弱有8个样本，则H（风速根据上面计算结果，我们可以计算信息增益率，如下所示：IGR（A）=Gain（A）/H（A）IGR（天气）=Gain（天气）/ H（天气IGR（温 度）=Gain（温 度）/H（温 度）=0.029IGR（湿 度）=Gain（湿 度）/H（湿 度）=0.151/1.0 = 0.151IGR（风速）=Gain（风速）/ H（风速根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点 进行分裂。3. 3决策树剪枝决策树主要是基于ID3算法实现的决策树生成。ID3算法的基本思想是贪心 算法，釆用自上而下的分

52、而治之的方法构造决策树。首先检测训练数据集的所有 特征，选择信息增益最大的特征A建立决策树根节点，由该特征的不同取值建立 分枝，对各分枝的实例子集递归，用该方法建立树的节点和分枝，直到某一子集 中的数据都属于同一类别，或者没有特征可以在用于对数据进行分割。ID3算法 总是选择具有最高信息增益（或最大爛压缩）的属性作为当前结点的测试属性。该 属性使得结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或 “不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最 小，并尽量确保一棵简单的（但不必是最简单的）树來刻画相关的信息。？在ID3算法中，计算信息增益时，由于信息增益存在

53、一个内在偏置，它偏袒 具有较多值的属性，太多的属性值把训练样例分割成非常小的空间。因此，这个 属性可能会有非常高的信息增益，而且被选作树的根结点的决策属性，并形成一 棵深度只为一级但却非常宽的树，这棵树可以理想地分类训练数据。但是这个决 策树对于测试数据的分类性能可能会相当差，因为它过分地完美地分割了训练数 据，不是一个好的分类器。？在J. Mingers关于ID3算法的研究中，通过对五种包含噪音的学习样例的实 验发现，多数情况下过度拟合导致决策树的精度降低了 10% 25%。过度拟合不 仅影响决策树对未知实例的分类精度，而且还会导致决策树的规模增大。一方面, 叶子节点随分割不断增多。在极端的

54、情况下，在一棵完成分割的决策树中，每个 叶子节点中只包含一个实例。此时决策树在学习样例上的分类精度达到100%, 而其叶子节点的数目等于学习样例中实例的数目。但是显然这棵决策树对任何未 见的实例都是毫无意义的。另一方面，决策树不断向下生长，导致树的深度增加。 因为每一条自根节点到叶子节点的路径都对应一条规则，所以树的深度越大，其 对应的规则越长。作为一种蕴含于学习样例中的知识，这样一组过长的规则集合 是很难被人理解的。过度拟合现象的存在，无论是对决策树的分类精度，还是对 其规模以及可理解性都产生了不利的影响。因此对与决策树的剪枝是非常有必要 的。3. 3. 1决策树剪枝的方法一般情况下可以使用

55、如下两类方法來减小决策树的规模：(1) 在决策树完美分割学习样例之前，停止决策树的生长。这种提早停止树 生长的方法，称为预剪枝方法。(2) 与预剪枝方法尽量避免过度分割的思想不同，一般情况下即使决策树可 能出现过度拟合现象，算法依然允许其充分生长。在决策树完全生长之后，通过 特定标准去掉原决策树中的某些子树。通常称这种方法为后剪枝方法。(1)预剪枝方法预剪枝方法实际上是对决策树停止标准的修改。在原始的ID3算法中，节点 的分割一直到节点中的实例属于同一类别时才停止。对于包含较少实例的节点, 可能被分割为单一实例节点。为了避免这种情况，我们给出一个停止阈值a。当 由一个节点分割导致的最大的不纯度

56、下降小于a时，就把该节点看作是一个叶子 节点。在该方法中，阈值a的选择对决策树具有很大的影响。当阈值a选择过大 时，节点在不纯度依然很高时就停止分割了。此时由于生长不足，导致决策树过 小，分类的错误率过高。假设在一个两类问题中，根节点Root 共包含100个 学习样例，其中正例和负例均为50。并且使用属性b可以将正例与负例完全分 开，即决策树在学习样例上的分类精度R(T)=100%o由信息增益公式可知，使用 属性b分割节点可以得到不纯度下降的最大值0.5。如果设a二0.7,因为Gain (Root, a)=0. 5<0. 7,所以根节点Root不需要分割。此时导致决策树在学习 样例上的分类精度下降为R(T)=50%o当阈值a选择过小时，例如