基于ID3算法的CET6关键影响因素分析

本科毕业设计（论文）基于 ID3 算法的 CET6 关键影响因素分析学 院 管理学院 专 业 信息管理与信息系统 年级班别 2008 级（6）班 学 号 3108006406 学生姓名 张钟权 指导教师 胡凤 2012 年 5 月 论文封面书脊基于ID3算法的CET6关键影响因素分析 张钟权 管理学院摘 要通过本次研究调查，影响大学生英语六级考试通过的因素有很多。想要在众多不完全、有噪声、模糊、随机的调查数据中找出关键影响因素，是一件比较复杂的事情。显然，传统的分析方法已经不再适用。于是，本文尝试用数据挖掘技术进行相应的实证分析。数据挖掘，作为一门快速发展的新兴技术，不仅可以对收集到的数据进行查询，而且能够找出数据之间的潜在联系，进行更高层次的分析，从而更好地帮助我们进行决策和预测。其重要性越来越突出，并将保持良好的发展势头。本次毕业设计采用了数据挖掘技术中的ID3决策树分类算法，对在校大学生的英语六级考试通过情况进行调查和分析，通过一系列的计算并构建出决策树，找出影响大学生英语六级考试通过的关键因素。同时提取出重要规则，获取相关知识，以达到解决问题的目的，进而科学地指导广大考生备考。本文在结构上先提出课题的背景及目的意义，并介绍一些国内外研究情况和叙述研究思路和方法。接着从决策树分类的基础理论知识出发，先后介绍了三种经典的决策树分类算法。最后重点介绍和研究ID3算法在找出影响大学生英语六级考试通过的关键因素中的应用，结合具体步骤，分步讲解，每个步骤详细具体，且通俗易懂，衔接到位。研究结果表明，ID3决策树分类算法能够较好地对数据进行分类，所生成的分类规则有助于科学地指导广大考生备考，同时也有助于指导开展今后大学英语相关教学工作，具有非常重大的现实意义。关键词：数据挖掘，决策树，ID3，CET6AbstractThrough this survey, There are many factors that affect college students pass CET6. To identify the key factors is a complicated thing among the many, incompleted, noisy, fuzzy random survey data . Clearly, the traditional analytical methods is no longer applicable. Thus, this paper tries to use the data mining technology for the corresponding empirical analysis.Data mining, as a fast-growing emerging technology ,can not only query the data collected, but also to identify potential links between the data, a higher level of analysis in order to help us make our decision-making and forecasting better. The importance of data mining is becoming more and more prominent, and it will keep the good momentum of development.The author use the ID3 classification algorithm in data mining techniques to investigate the situation and analysis of college students CET6 in this graduation project, through a series of calculations and construct a decision tree to identify the key factors for passing CET6 . At the same time, extract important rules, access to relevant knowledge, to achieve the purpose of solving problems and to guide the students getting ready for CET6.In this paper, first, proposed the structure of the background and purpose and significance of the subject, then introduce some domestic and foreign research ,narrative ideas and methods. Second, starting from the basic theoretical knowledge of the decision tree classification, introduce three classic decision tree classification algorithm. Finally,the author focus on using the ID3 algorithm ,how to find the key factors that affect the college students pass CET6. With specific steps, and then explain each step detailed specific, easy to understand, the cohesion in position.The results show that the ID3 decision tree classification algorithm is able to better classify the data .Generated by the classification rules can guide the students be ready for CET6 in a science way. in the mean time, it can help to guide the future of college English teaching, with the great practical significance.Key words：Data Mining，Decision-Tree，ID3， CET6目 录1 绪论 .11.1 课题背景及目的意义 .11.2 国内外研究现状 .21.3 研究方法与思路 .42 决策树分类 .52.1 决策树分类概述 .52.2 决策树分类经典算法介绍 .62.2.1 ID3 算法 .62.2.2 C4.5 算法 .82.2.3 CART 算法 .93 基于 ID3 算法的 CET6 关键影响因素分析框架 .123.1 问题定义 .123.2 数据准备 .133.3 建立模型 .153.4 解释模型 .164 实证分析 .174.1 数据预处理 .174.1.1 属性选取 .174.1.2 数据清理 .184.1.3 数据的变换与规约 .184.1.4 数据的离散化处理 .194.1.5 得到最终的样本训练集 .194.2 构造决策树 .204.2.1 给定样本分类的期望信息计算 .204.2.2 每个属性的信息增益计算 .214.2.3 测试属性的确定 .224.2.4 对分支节点进行进一步的划分 .224.2.5 决策树的修剪 .234.3 提取分类规则 .254.3.1 提取出来的分类规则 .254.3.2 模型分析 .26结论 .31参考文献 .32致谢 .33附录 A .341 绪论近年来, 随着大学英语六级考试的报考规模不断扩大，而通过比例却没有明显的突破，原因何在？未来的几年时间里，随着报考人数将进一步增长，其通过率又会如何变化呢？如何才能帮助广大考生找到关键原因，从而更好地通过大学英语六级考试？本次毕业设计通过深入分析对部分考生的调查数据，计算并递归地构建决策树，来寻找一些相关知识，并找出关键影响因素，从而更好地为大学英语教学工作的开展提供可参考的意见，同时也为广大考生备考英语六级指明了前进的方向。1.1 课题背景及目的意义CET6（College English Test-6） ，即大学英语六级考试，是由国家教育部主管的一项全国性的教学考试，其目的在于对在校大学生的实际英语能力进行客观、准确的测量，从而更好地为大学英语教学工作的开展提供服务。当然，目前的大学英语六级考试已经得到了社会各界的广泛认可，而且已经成为各级人事部门录用大学毕业生的一项非常重要的标准之一，可见，大学英语六级的重要性已经日益突出。近年来, 大学英语六级考试的报考规模和以前相比也出现了大幅度的增长，可见，越来越多的在校大学生开始意识到大学英语六级考试的重要性，但是却仍然普遍存在着考试通过比例不乐观的现象。如何才能帮助广大考生找到关键原因所在，从而更好地通过大学英语六级考试？先进的数据挖掘技术正好可以用来帮助解决这个问题。数据挖掘是基于人工智能、机器学习、模式识别、数据库、统计学、可视化等相关技术的，它能够从大量的业务数据中提取出关键性的数据，并进行高度自动化的数据分析，做出归纳性的推理，从而挖掘出潜在的模式，帮助决策者调整策略，减少风险，最终做出正确的决策。 1鉴于大学英语六级考试的重要性和通过率低下的迥况，也鉴于数据挖掘技术功能的强大，本文采用了数据挖掘技术中的 ID3（Induction Decision-tree ）决策树分类算法，对可能影响大学英语六级通过的各大因素进行调查和分析，从大量的调查数据样本中，构造出一棵决策树，并对决策树进行分析，从中提取出一些重要规则，获取相关知识，找出关键影响因素所在，并提出合理的解决策略，继而科学地指导广大考生备考，具有非常重要的现实意义。1 陈安，陈宁，周龙骧等.数据挖掘技术及应用M.北京:科学出社，2006.1.2 国内外研究现状最早的决策树学习系统要追溯到Hunt E B于1966年研制的一个概念学习系统CLS(Concept Learning System)，该系统第一次提出使用决策树进行概念学习，是许多决策树学习算法的基础。1979年，Quinlan J R提出了ID3(Iterative Dichotomizer 3)算法，引入了信息论中熵的概念，利用分割前后的熵来计算信息增益，在决策树中各级结点上选择属性，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类别信息。该算法学习能力较强，适于处理大规模的数据库问题，但该算法不能够处理连续属性，计算信息增益时偏向于选择取值较多的属性。针对这些问题，学者们提出了一系列改进算法。 11983年，Patterson A和Niblett T扩展了ID3算法，提出了类似概念学习系统ACLS(Analog Concept Learning System)算法，ACLS 算法允许属性取任意的整数值，这种改进极大地扩展了决策树算法的应用范围，使决策树可以处理一些比较复杂的任务。分类和回归树CART(Classification And Regression Trees)分类方法，是由Breiman L，Friedman J H和Olshen R A等人在1984年提出的一种决策树分类方法。这种方法选择具有最小基尼指数值(GINI) 的属性作为测试属性，最终生成二叉树，然后利用重采样技术进行误差估计和树剪枝(基于最小代价复杂性)，然后选择最优的作为最终构建的决策树。 21993年，Quinlan J R提出了C4.5算法，该算法可以看作是ID3算法的一个扩展，旨在克服ID3 算法在应用中的不足，该算法采用信息增益比例作为属性的选择标准，它继承了ID3 算法的全部优点，同时解决了ID3算法偏向于取值较多的候选属性的问题。 3SLIQ(Supervised Learning In Quest)分类方法，是Mehta M ,Agrawal R和Rissanen J 等人在1996年提出的一种高速可伸缩的有监督的寻找学习分类方法，它针对数据量远大于内存容量的情况,采用了类表和属性表两种数据结构，利用换入换出策略来处理大数据量。 4SPRINT(Scalable PaRallelizable INduction of decision Trees)分类方法，是由Shafer 1 王鹤 .基于决策树的 ID3 算法的研究与改进D.河北：河北工业大学，2008.2 梁循 .数据挖掘算法与应用M.北京:北京大学出版社，2006.3 黄炜 .C4.5算法在信息检索结果分类中的应用J.电脑知识与技术，2011，7（9）：2126-2128.4 李卿 .决策树优化算法研究D.成都：西南交通大学，2009.J，Agrawal R和Mehta M等人在1996年，继SLIQ分类方法后提出的一种规模可变的、支持并行计算的分类方法。该方法最大的优点就是可以避免内存空间的限制，利用多个并行处理器构造一个稳定的、分类准确率很高的决策树，具有很好的可伸缩性，扩容性，但该算法因使用属性列表，使得存储代价大大增加，并且结点分割处理的过程较为复杂，加大了系统的负担。1998年，Rastogi R等人提出一种将建树和树的调整阶段集成在一起的PUBLIC(Pruning and Building Integrated In Classification)算法，该算法提出了结点代价的目标函数，其主要思想是在决策树建立阶段，计算每个结点相关的目标函数值，估计该结点在将来调整阶段是否被删除。如果该结点将被删除，则不对该结点进行扩张，否则，扩展该结点。从而建树和修剪阶段结合成为一个阶段，而不是依次执行这两个阶段，提高了决策树的执行效率。1998年，Gehrke J和Ramakrishnan R等人提出雨林(Rain Forest)分类方法，它是一种针对大规模数据集，快速构造决策树的分类框架。其核心思想是根据每一次计算所能使用的内存空间，合理地调整每次计算所处理的数据集的大小，使框架内所使用的分类方法在每次计算的过程中，对内存资源的利用率达到最大，在有限的资源下，用最少的时间完成决策树的构建。 12002年，Ruggieri S提出了C4.5的改进算法一高效C4.5(EC4.5 ：Efficient C4.5)算法。EC4.5算法采用二分搜索取代线性搜索,在生成同样一棵决策树时，与 C4.5相比，EC4.5将效率提高了5倍，但EC4.5占用内存比C4.5多。2003年，Olaru C提出一种新的模糊决策树分类方法一软决策树。软决策树综合决策树的生成和修剪来决定其本身的结构，并利用重修和磨合来提高树的归纳能力，因此软决策树比一般决策树的正确率要高。2004年，ZHAO H M和RAM S提出了一种有限制的分层归纳决策树算法。这种算法的思想来自未扩展分层归纳方法，通过引入一个最大归纳深度参数来限制归纳层次，调整这个限制参数，可以得到各个归纳层次的决策树，从而选择性能最好的一棵作为预测器。2005年，Witold Pedrycz和Zenon A提出了一种C一模糊决策树算法(C-Fuzzy Decision Trees，CFDT)。 CFDT使用模糊聚类方法(fuzzy clustering method)进行分类，1 李卿 .决策树优化算法研究D.成都：西南交通大学，2009.取代传统决策树根据信息熵或者信息增益进行分类。CFDT在决策树建立时可同时考虑多个维度，并且能直接处理连续性数据，无需离散化。2007年，Chengming Qi提出一种改量的模糊决策树算法(modified fuzzy decision trees，MFDT)。MFDT在选择测试属性时，多值属性和连续属性的熵在模糊化后根据模糊理论计算得出，其它属性的熵还是传统计算熵的方法，利用这种方法生成的决策树效率高且易于理解。国内决策树的相关研究大部分集中于应用部分，但也有不少国内学者在决策树算法上进行了深入的研究。如：在特征属性选择的问题上，1998年刘小虎等学者在选择一个新属性时，并不仅仅计算该属性引起的信息增益，而是同时考虑树的两层结点，即选择该属性后，继续选择属性带来的信息增益；洪家荣等学者在分枝属性的选择上仍采用基于信息增益率的方法，但在树的扩展过程中，采用属性聚类的方法进行分枝合并；1999年吴菲，黄梯云采用遗传算法构造二元决策树，对数据进行特征识别，根据识别的结果选择模型，并以趋势预测模型为例进行了验证；2005年张括等提出一种基于遗传算法的多重决策树组合分类方法，该算法与单个决策树相比，具有更高的分类精度。 11.3 研究方法与思路本次毕业设计，我首先设计了一份调查问卷，主要通过网络途径发布并进行调查，同时收集大量数据。接着，结合课题要求进行数据预处理，最大可能地去除数据中的噪音，使其适合数据挖掘的要求，其中主要涉及到属性的选取、数据清理、数据的变换与规约和数据的离散化处理等预处理过程。处理完原始数据后，得到了适合于做数据挖掘的数据，然后再根据决策树分类算法中的 ID3 算法，求出每一个属性的信息增益值，并将信息增益值最大的属性选为当前的测试属性，直至符合决策树停止条件时结束，创建一个初始的决策树模型。由于该模型不一定是非常准确的，因此，还要根据相关的剪枝理论和方法，对该模型进行剪枝处理，包括前剪枝和后剪枝。最后，得出最终的决策树，提取出分类规则，找出关键影响因素，并进行分析和预测。1 李卿 .决策树优化算法研究D.成都：西南交通大学，2009.2 决策树分类2.1 决策树分类概述分类，是数据挖掘中一项非常重要的任务，目前在商业领域应用的最多。所谓分类模式，就是通过分析训练集中的数据,为每个类别做出准确的描述，并建立分析模型和挖掘出分类规则,然后用这个分类规则对其他数据库中的记录进行分类,从而对未来的数据进行预测。分类的技术和方法有很多，像决策树分类、贝叶斯分类、神经网络分类和遗传算法。其中，决策树分类方法是目前应用得最广泛的逻辑方法之一，在诸多的分类方法中，决策树分类是一种常用、直观的快速分类方法。它不仅能够作出分类和预测，而且它的生成过程以及分类和预测过程易于理解，从决策树中提取出来的分类规则也有很强的可理解性。决策树的概念最早是出现在 CLS( Concept Learning System)中的。决策树是一棵有向的无环树，是一个类似于树形结构的流程图。它的每一个内部节点表明了在一个属性上的测试，每个分支则代表了一个测试结果, 而每个叶子节点 (终节点)就代表了某个类或类分布。决策树提供了一种展示类似“在什么条件下会得到什么值 ”的这类规则的方法。 1决策树算法通常分为两个阶段：即决策树的构建(Building)阶段和决策树的修剪(Pruning)阶段。构造决策树采用的是自上而下的递归方式，如果训练例子集合中的所有例子都是同类的，则将其作为一个叶子节点，节点内容为该类别的标记。否则，就根据某种策略确定一个测试属性，并按属性的各种取值把实例集合划分为若干个子集合，使每个子集上的所有实例在该属性上都具有相同的属性值。然后，再依次递归处理各个子集，直到得到满意的分类属性为止。 21 陈伟，程黄金.ID3 算法构造学生专升本考试成绩分析决策树J.电脑知识与技术，2009，5（3）：744-746 .2 冯 菁，姚宏亮.ID3算法在教学质量评估中的应用研究J.计算机技术与发展，2011，21（6）:250-253 .决策树的修剪则可以采用前剪枝、后剪枝或两者结合的方法，来检测和去掉那些反映训练数据中的噪声和孤立点的分支，以提高对未知数据集进行分类时的准确性。其中，在构建决策树阶段选择合适的分割方法是决策树算法的关键，根据分割方法的不同，决策树算法可以分为两类：即基于信息论的方法（如ID3算法、C4.5算法）和基于GINI 指标的方法（如CART算法） 。其中，影响最大的要数J.R.Quinlan于1986年提出的ID3 算法 , 该算法中他提出了用信息增益(即信息论中的互信息 )来选择属性作为决策树的节点，以使得在每一个非叶结点进行测试时, 能获得关于被测试记录最大的类别信息。由于ID3 算法理论清晰、方法简单、学习能力较强和识别样本效率高的特点，使得ID3算法成为当时机器学习领域中最有影响的方法之一。2.2 决策树分类经典算法介绍为了做好相关知识的延伸和扩展，也为了方便待会更好地理解第三部分中 ID3 算法在实际环境中的应用，下面便先分别介绍一下基于信息论的 ID3 算法、C4.5 算法和基于 GINI 指标的 CART 算法。2.2.1 ID3 算法ID3，即归纳决策树（Induction Decision-tree）版本 3，是一种由数据构造决策树的递归过程，由 J.R.Quinlan 于 1986 年提出，是一种基于信息熵的决策树分类算法，它根据属性集的取值来选择实例的类别，是当时机器学习领域中最有影响力的算法之一。该算法的基本思想是首先试探性地选择一个属性，把它放置在根节点，并对该属性的每个值产生一个分支。这样，分裂根节点上的数据集，并移到子女节点，产生一棵局部树（Partial Tree） ，对该划分的质量进行评估，对其他属性重复该过程，每个用于划分的属性产生一棵局部树。然后，根据局部树的质量，选择一棵局部树，实际上也就意味着选择了一个划分属性，换句话说，我们根据哪个属性会得到“好的”局部树来选择一个属性。对选定的局部树的每个子女节点重复该过程，这是一个递归的过程，如果一个节点上的所有实例都具有相同的类，则停止局部树的生长。 1创建决策树的方法主要由下面几个公式构成，它们分别是计算样本分类的期望信息、计算子集的熵、计算子集的期望信息和计算信息增益。1 Soman K P，Shyam Diwakar，Ajay V.数据挖掘基础教程M.范明，牛常勇，译.北京:机械工业出版社，2009:40-80.计算样本分类的期望信息：假设S是s个数据样本的集合，假定类标号属性具有n个不同的取值，定义n个不同的类C ( i1，2，3, ，n) ，设S 是类C 中的样本数，则ii对一个给定的样本分类所需的期望信息可以由下面的公式给出：I(S ，S ，S )=- （2.1）12n1ii2)p(log其中 是任意样本属于C 的概率，一般可用s /s来估计,对数函数以2为底，是因为信息ipi i用的是二进制编码。计算子集的熵: 假设属性A具有m个不同取值a ，a ，a )，可以用属性A12m将S划分为m 个子集S ，S ，S ，如果A作为测试属性(即最好的分裂属性)，则12m这些子集对应于由包含集合S的结点生长出来的分支。假设S 是子集S 中类C 的样本，ijji则由A划分成子集的熵的计算可以由下面的公式给出：E(A)= （2.2）)(2112 njjjmj mjjj SIS其中， 充当了第j个子集的权，并且等于子集中的样本个数除以 S中的Smjj21样本总数，熵值越小，子集划分的纯度就越高。计算子集的期望信息：对于给定的子集 S ，其期望信息可以根据公式：jI(S ，S ，S )=- （2.3）j1j2nj1iij2j)p(log计算得出，其中 = 是 中的样本属于类C 的概率。ijp|jij i计算信息增益：根据期望信息和熵值，可以得到对应的信息增益值，对于在A上分支将获得的信息增益，可以由下面公式计算得出：Gain(A)= I(S ，S ，S )E(A) （2.4）12n其中，Gain(A)是由于获得属性 A的值而导致的熵的期望压缩，决策树算法就是通过计算每个属性的信息增益，将具有最高信息增益的属性选作给定集合S的测试属性，创建一个节点，并以该属性标记，根据属性的每个值来创建树的分枝，并且据此来划分样本。 总而言之，ID3算法采用的是分治策略，通过选择窗口来形成决策树，并利用信息增益来寻找数据库中具有最大信息量的属性字段，从而建立决策树的一个节点，再根据该属性字段的不同取值来建立树的分枝，在每个分枝的子集中重复建立树的下层节点和分枝的过程。ID3算法描述简单、分类速度快，适合于处理大规模数据，绝大多数决策树算法都是在它的基础上加以改进实现的。当然，ID3 算法也有一些不足之处，例如当遍历决策树空间时，ID3 算法仅维护了单一的当前假设，却失去了表示所有一致假设所带来的优势；还有，ID3算法在搜索的过程中不进行回溯，每当在树的某一层次选择了一个属性进行测试时，它就不会再回溯重新考虑这个选择，因而，它容易受无回溯搜索中常见风险的影响，收敛到的是局部最优答案而不是全局最优答案，一个局部最优的答案对应着它在一条搜索路径上搜索时选择的决策树，但这个局部最优的答案可能不如沿着另一条分支搜索到的更令人满意；再者，由于信息增益存在一个内在偏置，它偏袒了具有较多取值的属性，太多的属性值会把训练样例分割成非常小的空间，导致这个属性可能会有非常高的信息增益，而且被选作树的根结点的决策属性，并形成一棵深度只为一级但却又非常宽的树，这棵树虽然可以理想地分类训练数据，但这个决策树对于测试数据的分类性能可能会非常差，因为它过分完美地分割了训练数据，所以并不是一个好的分类器。 12.2.2 C4.5 算法C4.5算法是众多决策树算法中比较成熟的、应用也是比较广泛的一个经典算法，由J.R.Quinlan于1993年提出。C4.5算法是由CLS和 ID3发展而来的决策树算法,它生成决策树形式的分类器，同时也可以生成规则集,它的后续发展为C5.0算法。由于该算法分类准确率高，且速度快，因此非常适合于数据的增量挖掘。与ID3算法相比，C4.5算法主要在下面几个方面作了修改并且引进了新的功能：用信息增益比率作为选择标准，弥补了ID3算法偏向于取值较多的属性的不足；合并连续属性的值；可以处理具有缺少属性值的训练样本；1 樊敏 .ID3算法在分析学生成绩中的应用J.软件导刊，2010，9（12）：65-66.运用不同的剪枝技术来避免决策树的过拟合现象。下面便大体描述一下C4.5算法的过程：先对训练样本S的各项属性数据进行数据预处理；创建根节点r，并确定候选属性集合 叶节点属性；计算候选属性中的每个属性,选取信息增益率大而信息增益不低于平均值的属性作为测试属性，因为高信息增益率保证了高分支属性不会被选取，从而决策树的树形不会因某节点分枝太多而过于松散，而信心增益不低于平均值则保证了该属性的信息量，使有利于分类的属性更早地出现。将当前选中的属性赋值给当前结点，将该属性的属性值作为该属性的分叉结点，并将这些分叉结点插入队列中；从候选属性中将当前的使用属性删除；从队列中选出一个节点，递归进行 到的步骤，直至候选属性集合为空；为每个叶子节点分配类别属性，对相同的类别属性进行合并，将其进行约减 。12可以看出，C4.5算法利用了熵原理,采用分而治之的方法来构造决策树,判断树的生长方向,通常基于信息增益或者增益率,即选择信息增益率最大的属性作为分类属性，其中信息增益率等于信息增益对分割信息量的比值。对样本集T，假设A有s个不同取值的离散属性, 划分为 s ，s ,s 共n个子集, 用12A分割样本集所得的信息增益与ID3算法相同, 分割信息量由下式得到：S(s,A)=- （2.5）)(log21sini信息的增益率则由公式：G-R(s，A)= （2.6）),(AsSG得到。 1简而言之，C4.5算法根据信息增益率来选择测试属性，它以信息增益率最高的属性作为根节点，根据属性的不同取值将样本划分为k个子集，根据这k个子集分别生成k1 高阳，廖家平，吴伟.基于决策树的ID3算法与C4.5算法J.湖北工业大学学报，2011，26（2）：54-56.个不同的子树，再以子树为根节点，寻找其余属性中信息增益率最大的节点作为根节点，直到得到网络类型为叶子节点，则得到了原始的决策树。C4.5算法作为ID3的改进算法,它优点在于简单直接、易于理解和应用 ,它较好地解决了ID3 算法多值属性偏向的问题,还可以简单地忽略缺失数据。但是也具有不够稳定、精度通常不是最高等缺点。2.2.3 CART 算法CART（Classification And Regression Tree） ，即分类和回归树算法，是由 Breiman等人于 1984 年提出的一种采用二分递归分割技术的算法，它将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支，因此，CART 算法生成的决策树是结构简洁的二叉树。与 ID3 算法相比，CART 算法有三个方面的不同：CART 算法中用于选择变量的不纯性度量是 Gini 指数（Gini Index） ；如果目标变量是标称的，并且具有两个以上的类别，则 CART 算法可能考虑将目标类别合并成两个超类别，该过程被称为“双化” （Twoing） ；如果目标变量是连续的（或者数值的） ，则 CART 算法找出一组基于树的回归方程来预测目标变量，如果目标变量是离散的，则该树是分类树，而如果是连续值目标变量，则该树是回归树。CART 模型的划分可以使用 4 种不同的不纯性度量：熵不纯度、方差不纯度、Gini不纯度和误分类不纯度。具体使用哪种不纯性度量，取决于目标变量的类型，对于离散的目标变量，我们可以使用 Gini、双化或有序双化；而对于连续的目标变量，我们则可以使用最小二乘偏差或最小绝对偏差。Gini指数常常在目标变量是离散变量时使用，Gini指数的最小值是0，最大值是1-1/k，其中k是目标变量的类别数。任一节点t的Gini指数GINI(t)定义为：GINI(t)= （2.7）ijtip)(其中，i和j是目标变量的类别。上面的式子还可以写成：GINI(t)=1- （2.8）)(2tjj其中， 表示目标类别j在节点t中出现的比例。)(p当节点上的实例在目标类别之间均匀分布时，Gini 指数取最大值1-1/k，其中k是目标变量的类别数。当节点上的所有数据属于一个目标类别时，Gini 指数取最小值0。 1节点t上划分s的Gini指标定义为：GINI (s,t)=GINI(t)-p GINI（t ）-p GINI(t ) （2.9）split LLRR其中，p 是t中送到左边子女节点的实例所占的比例，p 是t中送到右边子女节点的实L例所占的比例，s S是所有可能的划分集S中的一个具体划分。选择划分s，最大化GINI(s,t)的值，由于对于节点t上的任意划分s，GINI(t)是常量，可以说选择划分s ，即是plit使量Gain(s,t)= p GINI（ t ）+p GINI(t )的取值最小。LLRR对于分类（离散）变量，如果类别多于两个，则可以考虑将类别合并为两个超类别的所有可能组合，以求出最佳划分。CART分析的步骤如下：从根节点 t=1开始，从所有可能候选 s的集合中搜索使不纯性降低的最大划分s ，*然后使用划分s 将节点1(即t=1) 划分成两个节点t=2和t=3 ；*在t=2 和t =3上分别重复划分搜索的过程；继续树的生长过程，直到至少满足一个停止树生长的规则为止。 1CART算法的优点在于它易于实现，且运行速度快、准确性高，决策树结构的可解释性较强；它在获得最终选择树前可使用交叉检验来评估候选树的误分类率，特别适用于对复杂样本数据的分析；而且输入的数据类型可以是离散值也可为连续变量，非常的灵活；由于采用了变量替代方法，因此它对样本数据的缺失和错误的包容性较强。1 Soman K P，Shyam Diwakar，Ajay V.数据挖掘基础教程M.范明，牛常勇，译.北京:机械工业出版社，2009:40-80.1 Soman K P，Shyam Diwakar，Ajay V.数据挖掘基础教程M.范明，牛常勇，译.北京:机械工业出版社，2009:40-80.3 基于 ID3 算法的 CET6 关键影响因素分析框架对于 CET6 关键影响因素的分析，按照我们的处理步骤，我们可以建立下面的分析框架：图 3.1 框架图3.1 问题定义问题定义，实际就是分析应用领域，包括了应用过程中的各种知识和目标。我们要充分了解相关背景以及要解决的问题，例如：哪些工作可由系统自动完成，哪些工作需要人工处理，系统的目标是什么，追求什么样的性能指标，挖掘模型的可理解性是否重要等。本次毕业设计目标明确，主要是采用数据挖掘技术中的ID3决策树分类算法，对在校大学生的英语六级考试通过情况进行调查分析，通过构建决策树，找出影响大学生英语六级考试通过的关键因素，同时提取出重要规则，获取相关知识，从而科学地指导广大考生备考。我们可以得到如下的项目目标说明书：项目目标说明书1、项目：CET6关键影响因素分析；2、问题：寻找与CET6通过联系紧密的因素，分析在校大学生通过CET6的可能性；3、项目目标：建立一个CET6关键影响因素分析模型；4、初步想法：通过建立CET6关键影响因素分析模型，为广大考生备考和学校教学工作的开展提供决策支持；5、可行性研究：选择合适的技术方案，即ID3算法。3.2 数据准备数据准备，是一个关键的步骤，它直接影响最终模型的质量。据说，进行数据挖掘的人会将 90%的时间都用于数据的准备阶段，而只将约 10%的时间用于数据挖掘方案和输出的评估。原始数据是难以用于数据挖掘的，因为现实世界中经过初步采集后的数据多半都是不完整的、有噪声的和不一致的，并且可能存在冗余。因此必须对这些原始数据做一些必要的变换处理，产生对选择数据挖掘方法更有用的特征，使其符合数据挖掘算法的要求，并能够产生最为可靠和准确的结果。因此，必须重视数据的准备工作。图3.2 数据准备（1）属性选取，即根据选题的需要，对所有影响 CET6 通过的可能因素中，归纳并选取出一定数量的属性字段，并设置他们的取值，如：性别1=“男”，2=“女”。 （2）数据清理，