本科毕业论文---决策树分类算法在教学分析中的应用.doc

本科毕业论文(设计)题目：决策树分类算法在教学分析中的应用姓 名： 学 号： 专 业： 院 系： 信息工程 指导老师： 职称学位： 助教硕士 完成时间： 教务处制 安徽新华学院本科毕业论文（设计）独创承诺书本人按照毕业论文（设计）进度计划积极开展实验（调查）研究活动，实事求是地做好实验（调查）记录，所呈交的毕业论文（设计）是我个人在导师指导下进行的研究工作及取得的研究成果。据我所知，除文中特别加以标注引用参考文献资料外，论文（设计）中所有数据均为自己研究成果，不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的工作已在论文中作了明确说明并表示谢意。毕业论文（设计）作者签名: 日 期： I安徽新华学院2015届本科毕业论文（设计）决策树分类算法在教学分析中的应用摘 要随着信息科技的高速发展，人们对于积累的海量数据量的处理工作也日益增重，需求是发明之母，数据挖掘技术就是为了顺应这种需求而发展起来的一种数据处理技术。数据挖掘技术又称数据库中的知识发现，是从一个大规模的数据库的数据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。在学生管理以及教学科学化的今天，传统的教学分析已经不能适应社会发展的需求。学生信息数据不断的增多，教学分析工作也日益加重。学生信息数据量不断的增多，对之前所累计的大量学生考试成绩数据运用数据挖掘技术进行分析挖掘是具有重大的意义的，这样可以把所挖掘分析出来的信息反馈用于指导学校的教学分析，从而提高学生的学习成绩。本文通过学生成绩信息运用数据挖掘技术，对所采集的数据进行预处理，运用决策树分类算法中的C4.5算法对成绩进行分析得到了成绩分析决策树，分析研究出有用的信息找到影响学生的因素，发现某些规律的存在，用以指导学校教学分析工作的开展。关键词: 数据挖掘；学生成绩；决策树 Application of decision tree in grade examination analysisAbstractWith the rapid development of Information Technology, people are facing much more work load in dealing with the accumulated mass data. Data mining technology is also called the knowledge discovery in database, data from a large database of effectively, implicit, previously unknown and potentially use value of information process. In todays scientific management and teaching, the traditional teaching analysis already can not adapt to the demand of social development. Continuous increase in the number of student information data, analysis of teaching work is also growing. Student information data quantity unceasing increase, a large number of students test scores of previously accumulated data mining analysis on applying data mining technology is of great significance, it can put the information feedback from our mining analysis, used to guide the schools teaching analysis, so as to improve the students academic performance. This paper intends to show the use of Data Mining Technique in the analysis of students score information in Examination, from the pretreatment on the collected data to the use of decision tree technique in data analysis. This employs C4.5 algorithm in decision tree technique to get the decision tree of the students score. Then by analyzing the useful information to find out the elements that can influence score and the rules in these influences to instruct school teaching work. Key words:Data mining；grade examination；decision tree；II目 录1 绪 论11.1研究背景与意义11.2数据挖掘的国内外研究现状11.3论文研究内容及结构安排22 数据挖掘技术42.1数据挖掘的概念42.1.1数据挖掘的背景42.1.2 数据挖掘的定义42.2 数据挖掘的过程42.2.1 数据对象的确立52.2.2数据预处理阶段52.2.3数据挖掘阶段62.2.4结果的解释和评估阶段62.3数据挖掘的主要方法62.4数据挖掘的功能72.5本章小结93 决策树技术103.1决策树简介103.2决策树的主要算法113.2.1 ID3算法113.2.2 C4.5算法123.3决策树剪枝153.4本章小结184 C4.5算法在学生考试成绩中的应用194.1成绩分析方法的依据194.2 决策树算法在考试成绩分析中的应用194.2.1 确定对象集目标194.2.2 数据的采集204.2.3 数据预处理214.2.4 数据挖掘工作的展开224.2.5结果分析275 总结与展望285.1研究结果285.2后续研究与展望28参考文献311 绪 论1.1研究背景与意义 无论在企业应用领域，还是在科学领域，数据挖掘技术有着广泛的应用价值。 在企业应用领域，用于制定好的市场策略以及企业的关键性决策。在商业面，数据挖掘技术可以增强企业的竞争优势，缩短销售周期，降低生产成本，有助制定市场计划和销售策略，并已经成为电子商务中的关键技术。近年来，随着我国高等教育的飞速发展，高校的教学管理信息不断增多。教学工作信息化有了很大的进步，好多高校在管理学生和教师信息方面有了很好的方式。比如我校的教务系统，这些系统为老师和学生提供了很好的帮助。这些系统中积累了大量的数据。目前的这些数据库系统虽然基本上都可以实现数据的录入、修改、统计、查询等功能，但是这些数据所隐藏的价值并没有被充分的挖掘和利用，信息资源的浪费还是比较严重的。随着数据挖掘技术的不断扩展，许多高校为了避免信息浪费，已经将数据挖掘技术应用于高校的教学分析中。数据挖掘技术的应用将对提高学生成绩和提高教学水平起到很好的指导作用。为了提高教学质量，将数据挖掘技术引入到高校学生成绩分析中，对这些数据进行深入的挖掘和合理的分析，从而挖掘出传统的分析方法所无法得出的结论。进而利用分析结果引导教学的开展，从而有利于提高教学质量。本文主要是基于如下背景开展的：以安徽新华学院历届学生成绩为背景，首先学习数据挖掘的理论知识以及决策树技术，然后建立新华学院学生成绩数据库，并利用数据挖掘技术中的决策树对自己建立的数据库进行深入的挖掘。最后对自己的挖掘结果进行分析，得到影响学生成绩的因素。从而更好的辅助今后学校的教学分析工作。1.2数据挖掘的国内外研究现状1989年8月在美国召开的第十一届国际人工智能联合会议的专题讨论会上，与数据挖掘（Date Mining）极为相似的术语从数据库中发现知识一词被提出。1993年以后，美国计算机协会美年都举行了专门研究探讨数据挖掘技术的会议，会议的规模也发展成为国际学术大会，并且在各个领域里取得了很多研究成果。最近，Gartner Group的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。1根据最近Gartner的HPC研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点。”国外研究数据挖掘的组织、机构或大学很多。比较著名的如卡内基梅隆大学、斯坦福大学。著名的研究机构如：KDNet 、ACM、NCDM等。国外比较著名的挖掘工具：IBM公司的Intelligent Miner 、SAS公司的Enterprise Miner、SGI公司的SetMiner、SPSS公司的Clementine、Oracle Darwin等。不少的软件在国外得到了广泛的应用，并收到了明显的效益。相对国外而言，我国的研究还没有形成整体的力量。国家在93年首次支持该领域的研究。现如今，国内的许多高等院校和科研单位积极开展知识发现的基础理论以及知识发现的应用研究，这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及Web数据挖掘。1.3论文研究内容及结构安排 本课题的主要工作是将数据挖掘技术和学校的信息管理系统相结合，新华学院多年来的信息化教学管理工作积累了大量的教学数据，从新华学院的数据库中收集学生的考试成绩信息。利用数据挖掘技术对这些数据进行分析，获得影响学生成绩的因素，更好的辅助学校如何提高学生成绩以及提高教学质量。本课题根据指导老师提供的11级学生成绩的信息，建立安徽新华学院11级学生成绩库，采用数据挖掘技术对成绩库进行挖掘。通过对实验结果进行深入分析，获得影响学生考试成绩的因素，辅助教师在以后的教学工作中采用更恰当的教学方式，指导学生应该具有什么样的学习态度，从而提高学生考试成绩。 论文结构如下：第一章 绪论。 主要介绍了论文的研究背景与意义，叙述了国内外数据挖掘技术的研究现状。第二章 数据挖掘的基础知识。 主要叙述了数据挖掘的定义、数据挖掘的过程以及数据挖掘的方法。第三章 决策树。 主要简要介绍了决策树以及决策树的经典算法。第四章 决策树在计算机等级考试成绩分析中的应用第五章 总结与展望。总结本篇论文并展望今后论文的继续研究方向内容方向。2 数据挖掘技术2.1数据挖掘的概念2.1.1数据挖掘的背景 随着信息技术的高速发展，人们积累的数据量急剧增长，如何从海量的数据中提取有用的知识成为当务之急。数据库技术的成熟以及数据应用的普及，虽然目前的数据库系统可以高效的实现数据的录入、查询、统计的功能，但无法发现数据中潜在的信息和价值，无法利用这些数据来预测未来的发展趋势。于是，新的问题就被提出来了：人类如何在这浩瀚的数据中及时发现有用的知识，提高数据的利用率呢？在不懈的努力下，从数据库中发现知识（Knowledge Discovery in Datebases）及其核心技术数据挖掘（Date Mining）便应运而生，并得以蓬勃的发展，越来越显出其强大的生命力。2.1.2 数据挖掘的定义数据挖掘(Data Mining)，又译为资料探勘、数据采矿。它是数据库中的知识发现(Knowledge Discovery in Datebases,简称：KDD)，是目前人工智能和数据库领域研究的热点问题，数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。所谓数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中自动搜索隐藏于其中的有着特殊关系的信息，提取隐含在其中的，人们事先不知道的、但又是潜在有用的信息和知识的过程2。2.2 数据挖掘的过程数据挖掘的过程可以分为以下几个部分：理解数据和数据的来源（unders tanding）、 获取相关知识与技术（acquisition）、 整合与检查数据（integration and checking）、 去除错误或不一致的数据（data cleaning）、 建立模型和假设（model and hypothesis development）、 实际数据挖掘工作（data mining）、测试和验证挖掘结果、解释和应用（interpretation and use）。大概可以四个部分数据对象的确立(Date Object Determined)数据预处理(Date Preprocessing)、数据挖掘(Date Mining)及结果的解释和评估(Interpretation and Evaluation)3。2.2.1 数据对象的确立 明确我们研究问题所需要的数据，理解数据并提出问题，需要进行数据挖掘的数据信息，明确数据挖掘的目标的定义。确定数据挖掘目标是数据挖掘重要的一步。我们进行数据挖掘时，挖掘的结果往往是不可预测的，但对要进行挖掘的目标是可预见的，即明确数据挖掘的最终目标4。 数据对象的确立，包括对大量数据的选取、数据属性的确定等。本文是安徽新华学院学生成绩的数据挖掘技术应用，这些数据包含新华学院历届的学生考试成绩数据，数据属性包括学生姓名、性别、年龄、专业、成绩等。2.2.2数据预处理阶段 现实世界中数据大体上都是不完整的、含有噪声的、甚至不一致的数据，我们无法直接对对这些数据进行挖掘，有时挖掘的结果差强人意。为了提高数据挖掘的质量，数据预处理技术被提出了5。数据预处理是数据挖掘过程中的一个很重要的步骤，数据预处理有很多种方法，一般将数据预处理又分为四个步骤：数据清洗、数据集成、数据变换、数据归约。数据清洗处理过程通常包括：填补遗漏的数据值、光滑有噪声数据、识别或删除异常值、以及解决不一致问题。数据集成就是将多个数据源的数据合并到一起并统一存储，建立数据仓库的过程实际上就是数据集成。在数据集成时要特别注意消除数据的冗余。数据变换主要是对数据进行规格化操作，将数据转换成适用于数据挖掘的形式。数据挖掘时对应的数据量往往是非常大的，数据归约是缩小所挖掘数据的规模，但保持数据的完整性。2.2.3数据挖掘阶段数据挖掘阶段是数据挖掘的核心步骤，也是技术难点所在。而数据挖掘阶段的核心就是模式的发现6。此阶段主要是确定对数据进行分类还是聚类，确定数据的关联规则等等。然后确定用什么数据挖掘算法对数据进行挖掘，再利用数据挖掘的工具和一系列方法对之前所确定以及转换后的数据进行分析、产生一个特定的有意义的模式以更好的对已处理好的数据进行分析，获取有用信息。2.2.4结果的解释和评估阶段数据挖掘阶段会产生的模式或数据集经过评估存在冗余或多余的模式，这时需要将其剔除，过滤出有用的知识。过滤后用于呈现给用户；一般情况下，为了方便用户理解产生的模式，处理员应该利用可视化技术将数据挖掘产生的有意义模式以图形或者其他可视化的形式表示，让用户更容易理解。例如把分类决策树转换为“ifthen”的形式。如果数据挖掘过程中的发现的知识不能满足用户的需求，我们则需要重新对数据进行处理，用其他的数据挖掘技术对数据进行挖掘，并分析结果，直到满足用户的需求。2.3数据挖掘的主要方法（1）关联规则关联规则在数据挖掘的知识模式中是比较重要的一种。关联规则的概念由国外一些著名的学者提出，例如：Agrawal、Imielinski、Swami。是数据中一种简单但很实用的规则。关联规则是描述了数据库中数据项之间所存在的关系的规则，即根据一个事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互关系7。（2）决策树 决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。 决策树是一个预测模型，是对象属性与对象值之间的一种映射关系。树中每个节点代表着某个对象，而每个分叉路径则表示某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出8（3）遗传算法遗传算法是一种空间搜索方法，遗传算法的搜索方向是由算法的适应函数来决定的，用拟生物化的人工运算过程进行一代一代的周而复始的演化，最终得出一个最佳结果。遗传算法的特点是具有求值空间的独立性与强固形。强固形使问题的限制条件降到最低，并可以大幅度的提高系统的容错能力；而求值空间的独立性则使遗传算法的设计比较简单，且适用于不同领域不同性质的问题。遗传算法在数据挖掘中的应用，可以挖掘出与众不同的信息，是别的算法所不能替代的9。（4）粗糙集粗糙集算法将知识理解为对数据的划分，每一被划分的集合被称为概念，主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来近似刻画处理粗糙集理论，是继模糊集、证据理论、概率论之后的又一个可以处理不确定性的数学工具。作为一种较新的算法，粗糙集近年来越来越受到重视，其有效性已在诸多的领域的成功应用得到了证实，是当前国际上人工智能理论及其应用领域中的研究热点之一。2.4数据挖掘的功能数据挖掘的功能是从大型数据集中提取人们感兴趣的知识，这些知识是隐含的、具有一定可信度的、对用户而言是新颖的且有潜在价值的知识，提取的知识表示为概念、规则、模式等多种形式9。一般情况下，数据挖掘的任务可以大体分为两类：描述和预测。描述性挖掘任务描述数据库中数据的一般性质，而预测性挖掘任务是指对当前数据进行处理、分析和推断，以做出相应的预测。数据挖掘在实际的工作中，有时候用户并不清楚自己需要什么样的数据，因此数据挖掘工作有必要挖掘出多种类型的模式，以达到满足不同的用户需求和应用。一般情况下，数据挖掘的功能以及可能发现的模式类型如下：（1）分类分类的目的是构造一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段（又称属性或特征）值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可表示为：（v1，v2，vn；c），其中vi表示字段值，c表示类别。 例如：银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些来区分新申请贷款的客户，以采取相应的贷款方案。（2）关联分析 关联分析就是从大量的数据中发现项集之间有趣的关联或因果结构。关联分析展示了属性与值频繁的在给定的数据集中的一起出现的条件。一般如下形式： 如XY，即“|A1 .An B1.Bn”的规则。其中，Ai (i1,.m),Bj (j1,.n)是属性值对。关联规则XY即表示：“满足X中条件的数据库元组多半也满足Y中的条件”。 简而言之，就是分析两个事物之间的一些特性，通过一个事物去预测另外一个事物，这就是关联分析。（3）概念/类描述概念描述（concept description）就是通过对与某类对象关联数据的汇总、分析和比较，对此类对象的内涵进行描述，并概括这类对象的有关特征。这种描述是汇总的、简洁的和精确的知识。 （4）离群点分析在数据库中有时会包含一些数据对象，它们与数据的模型或一般行为不一致。这些数据对象是离群点（outlier）。大部分数据挖掘方法将离群点视为噪声或异常丢弃。然而，在一些应用中，稀奇的事件可能比正常的事件更令人关注。（5） 演变分析 数据演变分析描述行为随时间变化的对象的规律，并对其进行建模。尽管这可能包括时间相关数据的区分、特征化、关联和相关分析、预测、分类或聚类，这类分析的不同特点包括序列或周期模式匹配、时间序列数据分析和基于相似性的数据分析。2.5本章小结本章在介绍数据挖掘基本概念的基础上，简要的概括了数据挖掘的过程、数据挖掘的方法、数据挖掘的功能，并简要介绍了几个数据挖掘应用的成功案例。这些基本理论知识为数据挖掘的实践应用研究奠定了理论基础。3 决策树技术3.1决策树简介随着社会的发展，数据挖掘显的尤为的重要。在数据挖掘中决策树算法是目前数据挖掘领域中应用的最广泛、最流行的推理算法之一。决策树分类算法是将数据分类、预测和规格的提取。随着ID3算法和C4.5算法的提出，决策树技术在数据挖掘领域得到了进一步的拓展，并且在人们生产生活中得到了广泛应用。 决策树是一种根据自变量的值进行递归划分以及预测因变量的方法10。决策树的主要作用是揭示数据中的结构化信息。它提供一种在什么条件下会得到什么值的类似规则的方法。若因变量为分类变量，我们称相应的决策树为分类树；若因变量为连续变量，我们称相应的决策树为回归树。分类树对离散变量做决策树，回归树对连续变量做决策树。一般的数据挖掘工具，允许选择分裂条件和修剪规则，以及控制参数（最小结点的大小，最大树的深度等等），来限制决策树的。决策树作为一棵树，树的根节点是整个数据集合空间，每个分节点是对一个单一变量的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于一类别的记录。图3.1为以典型的决策树。图3.1 决策树3.2决策树的主要算法近年来，决策树方法在很多机器学习、知识的探究等过程中得到了广泛的应用。迄今为止，国内外研究人员先后提出了十几种决策树的分类方法，因此决策树的算法还是挺多的，本文介绍了两种比较经典的决策树算法，分别是ID3算法和C4.5算法。3.2.1 ID3算法 ID3(induction decision-tree)算法，它是一种用来由数据构造决策树的递归过程，是在1986年由Quinlan首先提出的，该算法以信息论为基础，信息论是数学中的概率论和数理统计的一个分支，用于处理信息和信息熵、通信系统、数据传输和率失真理论、密码学、信噪比、数据压缩和相关课题。以信息熵和信息增益度为衡量标准，从而实现数据的归纳分类，它是一个从上到下、分而治之 的归纳过程12。ID3算法的大概过程是：我们试探性的选择一个属性放置在根节点，并对该属性的每个值产生一个分支。这样，分裂根节点上的数据集，并一道子女节点，产生一个局部的树。在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录的最大的类别信息。其具体方法是：我们需要检测所有的属性，在它们中间选择信息增益最大的属性作为决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有的子集仅包含同一类别的数据为止。最后得到的一棵决策树，它可以用来对新的样本进行分类。要想了解ID3算法，我们要了解ID3算法中的一些基本概念：（1）熵熵是一个物理名词，源于热力学的概念，数值为温度除热量所得的值。1948年Shannon提出并发展了信息论并引入了信息熵。一个训练集合S根据类别属性的值被分成m个互相独立的类C1、C2、.、Cn，则识别S的一个元组所属哪个类所需的信息量为Info（S）。Info（S）= Pilog2（Pi）Plog2 P-Plog2 P上述公式中，p+代表正样例，而p-则代表反样例。（2）信息增益度信息增益度是两个信息量之间的差值，已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益（informationgain）”。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：G（S,A）=Info（S）-Info（A）最后根据信息增益最大的原则选择根节点来构成决策树。3.2.2 C4.5算法C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点：1、用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度度量准则），也就是熵的变化值，而C4.5用的是信息增益率。2、在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。3、对非离散数据也能处理。4、能够对不完整数据进行处理由于ID3算法在实际应用中的一些局限，Quinlan再次改进了ID3算法。C4.5算法是ID3算法的改进版本，C4.5算法可以处理多种数据类型。此外，C4.5的效率相比于ID3算法也有了很多的提高。 通过对ID3算法的介绍我们已经了解熵，和信息增益。在C4.5算法中我们引入了新的概念信息增益率。 C4.5算法的具体步骤如下：（1）计算集合D的熵；（2）计算各个属性的信息熵；（3）计算信息增益；（4）计算分裂信息度量；（5）计算信息增益率；（6）选择增益率最大的作为根节点； (7)建立决策树；本文以一个典型被引用多很多次的数据训练集D为例，来说明C4.5算法如何计算信息节点并切选择决策树结点。如图3.2:天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消图3.2根据图3.2我们可以看出上面的训练集有4个属性：天气，温度，湿度，风速，而类标签有2个，即类标签集合C=Yes, No，分别表示适合户外运动和不适合户外运动。根据前面的介绍，我们来计算信息熵，信息增益，以及信息增益率。数据D中一共用14个训练样本，其中9个为正样例，5个位反样例。因此它的信息熵为：Info（D）=-9/14*log2（9/14）-5/14log2（5/14）=0.940下面计算属性集合中每个属性的信息熵：1：Info(天气) = 5/14 * - 2/5 * log2(2/5) 3/5 * log2(3/5) + 4/14 * - 4/4 * log2(4/4) - 0/4 * log2(0/4) + 5/14 * - 3/5 * log2(3/5) 2/5 * log2(2/5) = 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) + 4/14 * - 3/4 * log2(3/4) 1/4 * log2(1/4) = 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(1/7) = 0.7894：Info(风速) = 6/14 * - 3/6 * log2(3/6) 3/6 * log2(3/6) + 8/14 * - 6/8 * log2(6/8) - 2/8 * log2(2/8) = 0.892根据上面的数据我们可以计算出信息增益：1：Gain(天气) = Info(D) - Info(天气) = 0.940 - 0.694 = 0.2462：Gain(温度) = Info(D) - Info(温度) = 0.940 - 0.911 = 0.0293：Gain(湿度) = Info(D) - Info(湿度) = 0.940 - 0.789 = 0.1514：Gain(风速) = Info(D) - 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) =1.577406282852342、温度属性属性温度有3个取值，其中热有4个样本、适中有6个样本、寒冷有4个样本，则H(温度) = - 4/14 * log2(4/14) - 6/14 * log2(6/14) - 4/14 * log2(4/14) = 1.55665670746282283、湿度属性属性湿度有2个取值，其中高有7个样本、正常有7个样本，则H(HUMIDITY) = - 7/14 * log2(7/14) - 7/14 * log2(7/14) = 1.04、风速属性属性风速有2个取值，其中强有6个样本、弱有8个样本，则H(风速) = - 6/14 * log2(6/14) - 8/14 * log2(8/14) = 0.9852281360342516根据上面计算结果，我们可以计算信息增益率，如下所示：IGR(A)=Gain(A)/H(A)IGR(天气) = Gain(天气) / H(天气) = 0.246/1.577406282852345 = 0.15595221261270145IGR(温 度) = Gain(温 度) / H(温 度) = 0.029 / 1.5566567074628228 = 0.018629669509642094IGR(湿 度) = Gain(湿 度) / H(湿 度) = 0.151/1.0 = 0.151IGR(风速) = Gain(风速) / H(风速) = 0.048/0.9852281360342516 = 0.048719680492692784根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点，对该结点进行分裂。3.3决策树剪枝决策树主要是基于ID3算法实现的决策树生成。ID3算法的基本思想是贪心算法，采用自上而下的分而治之的方法构造决策树。首先检测训练数据集的所有特征，选择信息增益最大的特征A建立决策树根节点，由该特征的不同取值建立分枝，对各分枝的实例子集递归，用该方法建立树的节点和分枝，直到某一子集中的数据都属于同一类别，或者没有特征可以在用于对数据进行分割。ID3算法总是选择具有最高信息增益(或最大熵压缩)的属性作为当前结点的测试属性。该属性使得结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目达到最小，并尽量确保一棵简单的(但不必是最简单的)树来刻画相关的信息。在ID3算法中，计算信息增益时，由于信息增益存在一个内在偏置，它偏袒具有较多值的属性，太多的属性值把训练样例分割成非常小的空间。因此，这个属性可能会有非常高的信息增益，而且被选作树的根结点的决策属性，并形成一棵深度只为一级但却非常宽的树，这棵树可以理想地分类训练数据。但是这个决策树对于测试数据的分类性能可能会相当差，因为它过分地完美地分割了训练数据，不是一个好的分类器。在J.Mingers关于ID3算法的研究中，通过对五种包含噪音的学习样例的实验发现，多数情况下过度拟合导致决策树的精度降低了10%一25%。过度拟合不仅影响决策树对未知实例的分类精度，而且还会导致决策树的规模增大13。一方面，叶子节点随分割不断增多。在极端的情况下，在一棵完成分割的决策树中，每个叶子节点中只包含一个实例。此时决策树在学习样例上的分类精度达到100%，而其叶子节点的数目等于学习样例中实例的数目。但是显然这棵决策树对任何未见的实例都是毫无意义的。另一方面，决策树不断向下生长，导致树的深度增加。因为每一条自根节点到叶子节点的路径都对应一条规则，所以树的深度越大，其对应的规则越长。作为一种蕴含于学习样例中的知识，这样一组过长的规则集合是很难被人理解的。过度拟合现象的存在，无论是对决策树的分类精度，还是对其规模以及可理解性都产生了不利的影响。因此对与决策树的剪枝是非常有必要的。一般情况下可以使用如下两类方法来减小决策树的规模:(l)在决策树完美分割学习样例之前，停止决策树的生长。这种提早停止树生长的方法，称为预剪枝方法。(2)与预剪枝方法尽量避免过度分割的思想不同，一般情况下即使决策树可能出现过度拟