决策树在成绩分析中的应用

1、-. z.学年论文决策树在成绩分析中的应用学院：计算机科学与工程学院班级：*: * : * 导师： * TOC o 1-3 h u HYPERLINK l _Toc6171 摘要 PAGEREF _Toc6171 1 HYPERLINK l _Toc1297 Abstract PAGEREF _Toc1297 1 HYPERLINK l _Toc9424 第一章绪论 PAGEREF _Toc9424 1 HYPERLINK l _Toc1885 1.1数据挖掘的历史、开展 PAGEREF _Toc1885 1 HYPERLINK l _Toc31047 数据挖掘技术的商业需求分析 PAGERE

2、F _Toc31047 1 HYPERLINK l _Toc31242 数据挖掘研究的开展趋势 PAGEREF _Toc31242 1 HYPERLINK l _Toc19113 第二章数据挖掘的根本知识 PAGEREF _Toc19113 1 HYPERLINK l _Toc7366 2.1 数据挖掘的定义 PAGEREF _Toc7366 1 HYPERLINK l _Toc25713 2.2数据挖掘的分类 PAGEREF _Toc25713 1 HYPERLINK l _Toc30103 数据挖掘按挖掘任务类型 PAGEREF _Toc30103 1 HYPERLINK l _Toc25

3、375 2.2.2 按挖掘对象 PAGEREF _Toc25375 1 HYPERLINK l _Toc27468 2.2.3 按挖掘方法 PAGEREF _Toc27468 1 HYPERLINK l _Toc1385 2.2.4 按数据挖掘所能发现的知识 PAGEREF _Toc1385 1 HYPERLINK l _Toc28761 2.3数据挖掘技术的主要方法 PAGEREF _Toc28761 1 HYPERLINK l _Toc20513 关联规则方法 PAGEREF _Toc20513 1 HYPERLINK l _Toc10675 决策树方法 PAGEREF _Toc10675

4、 1 HYPERLINK l _Toc25131 2.3.3 神经网络方法 PAGEREF _Toc25131 1 HYPERLINK l _Toc6504 遗传算法 PAGEREF _Toc6504 1 HYPERLINK l _Toc308 2.4数据挖掘的实现过程 PAGEREF _Toc308 1 HYPERLINK l _Toc21245 2.4.1 数据准备 PAGEREF _Toc21245 1 HYPERLINK l _Toc27910 数据挖掘 PAGEREF _Toc27910 1 HYPERLINK l _Toc12265 2.4.3 模式的评估解释 PAGEREF _T

5、oc12265 1 HYPERLINK l _Toc14007 2.4.4 知识运用 PAGEREF _Toc14007 1 HYPERLINK l _Toc27801 第三章决策树技术 PAGEREF _Toc27801 1 HYPERLINK l _Toc510 3.1决策树技术 PAGEREF _Toc510 1 HYPERLINK l _Toc6883 3.2算法描述 PAGEREF _Toc6883 1 HYPERLINK l _Toc2668 3.2.1 ID3算法 PAGEREF _Toc2668 1 HYPERLINK l _Toc31960 3.2.2 改良算法 PAGERE

6、F _Toc31960 1 HYPERLINK l _Toc21358 3.2.3 ID3算法计算学生的成绩信息 PAGEREF _Toc21358 1 HYPERLINK l _Toc13134 3.2.4 改良算法计算学生的信息 PAGEREF _Toc13134 1 HYPERLINK l _Toc24884 第四章总结 PAGEREF _Toc24884 1 HYPERLINK l _Toc17824 参考文献： PAGEREF _Toc17824 1-. z.决策树在成绩分析中的应用摘要数据挖掘的提出是在20世纪80年代，它是一个新兴的、面向商业应用的AI研究领域，20世纪末，随着I

7、nternet的普及，全球信息量以惊人的速度急剧增长，据估计每二十个月增加一倍。目前的数据库系统虽然可以高效的实现数据的录入、查询、和统计等功能，但却无法发现海量数据中隐藏的知识和规律；人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效的利用这些数据。如何将这些海量的数据从数据库中提取出来，并转为有用的信息；面对这一挑战，数据挖掘和知识发现技术应运而生，并显示强大的生命力。数据挖掘和知识发现使数据处理技术进入一个更高级的阶段。它不仅能对过去的数据进展查询，而且能够找出过去数据进展查询，而且能够找出过去数据之间潜在的联系，进展更高层次的分析，以便更好的解决决策、预测等

8、问题。数据挖掘，从技术角度而言，数据挖掘是从大量的，不完全的，有噪声的、模糊的、随机的实际数据中，提取隐含在其中人们事先不知道但有潜在有用的信息和知识的过程。从商业角度，数据挖掘是一种新的商业信息处理技术，其主要的特点是对数据库中的大量业务数据进展抽取、转换、分析和其他模型换处理，从中提取辅助商业决策的关键性信息和知识。本论文主要论述的是利用决策树技术对于大量的学生数据进展分析，在其中挖掘有用的信息，目的是提高教学质量。决策树技术，用于分类和预测的主要的技术，决策树学习是以实例为根底的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出决策树表示形式的分类规则，它包括两个步骤：一，利用训练

9、样本集来建立并精化出一颗决策树，建立决策树模型。即从数据中获取知识，进展机器学习的过程。二，利用建好的决策树对新的数据进展分类。关键字：数据挖掘，决策树技术，成绩分析Application of decision tree in performance analysisAbstract Data mining is put forward in 1980s，it is a new, twentieth Century for the mercial application of AI research field,at the end, with the popularity of Inter

10、net, the global information has dramatically increased at an alarming rate, is estimated to be doubled every twenty months. Although the current database system can achieve data entry, efficient the query and statistical functions, but can not find the knowledge and rules hidden in massive data; the

11、 main problems that people are facing is not lack of enough information can be used, but the face of the vast ocean of data and how to use these data effectively. How these massive data e*tracted from the database, and turn them into useful the information; in the face of this challenge, data mining

12、 and knowledge discovery technology came into being, and show strong vitality. Data mining and knowledge discovery, data processing technology into a A more advanced stage. It can not only query on past data, and can identify the past data query, and to find out the potential link between past data,

13、 higher level of analysis, in order to better solve the decision problem. Data mining, prediction, from a technical point of view, data mining is from a large number of, inplete, noisy, fuzzy and random of the actual data, e*tract some unknown but potentially useful information and knowledge process

14、. From the business perspective, the data mining is a new business information processing technology, its main characteristic is to a large number of business data in the database the e*traction, transformation, analysis and other models for processing, e*traction business decisions from the key inf

15、ormation and knowledge. This paper mainly discusses the use of decision tree technology for the analysis of a large number of student data, in which mining useful information, the purpose is to improve the quality of teaching. Decision tree for classification and prediction of the main technology an

16、d decision tree learning is instance based inductive learning algorithm, it looks from a group of out of order, irregular instance reasoning decision tree representation of classification rules, which includes two steps: a using training sets to establish and refine the decision tree, decision tree

17、model is built. From the data access to knowledge, carry on the machine learning process. Second, using the built decision tree to classify new data.Keywords: data mining, decision tree technology， performance analysis第一章绪论1.1数据挖掘的历史、开展数据挖掘技术的商业需求分析由于大型数据系统的广泛使用和把数据转换成有用知识的迫切的需要，数据挖掘引起了各行业的关注。20世纪60

18、年代，为了适应信息的电子话需求，信息技术一直从简单的文件处理系统向有效的数据库系统变革。20世纪70年代，数据库系统的三个主要的模式：层次，网络，关系型数据库的研究和开发取得了重要的进展。20世纪80年代，关系型数据库及其相关的数据模型相关工具，数据索引技术局组织被广泛采用，并且成为了整个数据库市场的主导。20世纪80年代中期开场，关系型数据库技术和新型技术的结合成为数据库研究和开展的重要标志。从数据的分布角度看，分布式数据库及其透明性、并发控制、并行处理等成为必须面对的课题。许多的商业活动中，由于数据库的普及，人工去整理和理解如此大的数据源已经存在效率、准确性等问题，并不是每个人都能够从过去

19、的销售情况预测将来的开展趋势或做出正确的决策。20世纪80年代，产生了数据技术并得到了广泛的应用。高性能的关系数据库引擎以及相关的分布式查询、并发控制等技术的应用，已经提升了数据库的应用能力。在数据的快速访问、集成和抽取等问题上有了突破，数据仓库作为一种新型的数据存储和处理手段，被数据库厂商广泛的应用。20世纪80年代后期，产生了数据挖局等思想。90年代，分布式数据库理论上趋于成熟，然而本质上查询是对数据库的被动的使用。由于简单查询只是数据库容的选择性输出，因此它和人们期望的分析预测、决策支持等高级应用人有很大的距离。近年来，由于数据采集技术的更新，决策所面对的数据量在不断的增长，随着数据的急

20、剧增长，现有信息管理系统中的数据分析工具已无法适应新的需求。人们希望能够提供更高层次的数据分析功能，自动和智能地将待处理的数据转化为有用的信息和知识。数据挖掘研究的开展趋势数据挖掘必须经过概念的提出、概念的承受、广泛研究和探索、逐步应用和大量应用等阶段。目前，大局部的学者认为数据挖掘仍然处于广泛研究和探索阶段。数据挖掘应在如下方面进展开展： 1.数据挖掘技术与商业逻辑的平滑集成问题 2.数据挖掘技术与特定的数据存储类型的适应问题 3.大型数据的选择与规格化问题 4.数据挖掘系统的构架与交互式挖掘技术 5.数据挖掘语言与系统的可视化问题 6.数据挖掘理论与算法研究第二章数据挖掘的根本知识2.1

21、数据挖掘的定义从技术角度而言，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中，提取隐含在其中人们事先不知道但又潜在有用的信息和知识的过程。这一定义包括多层含义、及数据源必须是真实的、海量的、发现的知识应是用户感兴趣的，并且是可承受的、可理解的和可应用的，可以仅支持特定的问题。从商业角度而言，数据挖掘是一种新的商业信息处理技术，其主要的特点数对数据库中的大量业务数据进展抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性信息和知识。数据挖掘的本质是一种深层次的数据分析方法。因此数据挖掘可以描述为按企业既定业务目标，对大量的企业数据进展探索和分析，提醒隐藏的、未知的或验

22、证的规律性，并进一步将其模型化的有效方法。2.2数据挖掘的分类数据挖掘按挖掘任务类型分类或预测模型发现2.数据总结与聚类发现3.关联规则发现4.序列模式发现5.相似模式发现6.混沌模式发现7.依赖关系或依赖模型发现异常和趋势发现等2.2.2 按挖掘对象1.关系型数据库挖掘2.面向对象数据挖掘3.空间数据库挖掘4.时态数据库挖掘5.文本数据源挖掘6.多媒体数据库挖掘7.异质数据库挖掘8.遗产数据库挖掘9.web数据库挖掘 2.2.3 按挖掘方法 1.机器学习方法2.统计方法 3. 聚类分析方法 4.神经网络方法 5.遗传算法方法 6.数据库方法 7.近似推理和不确定性推理方法 8.给予证据理论和

23、元模式的方法 9.现代数学分析方法 10.粗糙集或模糊集方法 11.集成方法等2.2.4 按数据挖掘所能发现的知识1.挖掘广义型知识 2.挖掘差异型知识 3.挖掘关联型知识 4.挖掘预测性知识 5.挖掘偏离型知识 6.挖掘不确定性知识2.3数据挖掘技术的主要方法关联规则方法从数据集中发现关联规则，该规则显示给定数据集中经常一起出现的属性-值元组。例如：*y说吧表达的含义是满足*远足有可能满足Y。关联分析在交易数据分析、支持定向、商品目录设计和其他业务决策等方面有着广泛的应用。决策树方法ID3算法是最典型的决策树分类算法，决策树是从机器学习角度研究和开展起来的，对于大训练样本集很难适应。决策树是

24、通过一系列规则对数据进展分类的过程。以树的形式来表达模型，主要是对属性值进展归纳分类，它采用自顶向下的递归方式，在决策树部节点进展属性值的比拟，并根据不同的属性值来判断从该节点向下的分支，在决策树的叶节点得到结论。采用决策树可以将数据规则可视化，不需要更长时间的构造过程，输出结果容易理解，精度较高。2.3.3 神经网络方法是人们在模拟人脑处理问题的过程中开展起来的新型智能信息处理理论。它通过大量的称为神经元的简单处理单元构成非线性动力学系统，对人脑的形象思维、联想记忆等进展模拟和抽象，实现与人脑相似的学习、识别、记忆等信息处理能力。遗传算法是模拟自然界生化进化过程的随机化搜索算法，它以很强的解

25、决问题能力和广泛的适应性渗透到研究与工程的各个领域。遗传算法是一种高效的全局并行搜索优化算法。2.4数据挖掘的实现过程2.4.1 数据准备数据挖掘的处理对象是海量的数据，是长期积累的结果。这些数据不适合直接进展挖掘，需要进展预处理。数据预处理包括数据的选择、清洁消除噪声、冗余数据、推测推算缺失数据、转换离散型数据与连续型数据之间的转换、数据缩减减少数据量。数据挖掘根据挖掘的目标，选取相应算法的参数，分析数据，得到可能形成知识的模型2.4.3 模式的评估解释通过上述步骤得到的模式，有可能是没有意义或没有实用价值的，因此需要评估，确定哪些是有效的、有用的模式。此外，大局部模式是数学表达式，需要将其

26、解释成可理解的方式呈现给用户。2.4.4 知识运用运用只是主要有两种途径。一、只许看知识本身描述的关系或结果，就可以对决策提供支持；二、要求对新的数据运用知识，由此可能产生新的问题，并需要对知识做进一步优化。第三章决策树技术3.1决策树技术决策树是分类预测的主要方法，采用基于实例的归纳学习算法，旨在从一组无次序、无规则的实例中推理出决策树形式的分类规则，采用自顶向下的递归方式，在决策树的部节点进展属性值的比拟并根据不同属性判断从该节点向下的分枝，在决策树的叶节点得到结论，所以从根到叶节点对应一条合取规则，整颗树对应一组析取规则。决策树分类是利用属性值对各子集逐级划分，直到一个结点仅含有同一类样

27、本为止。3.2算法描述3.2.1 ID3算法根本思路是首先在数据集中采用信息增益作为属性选择的标准，找出最有影响力的属性，将数据集分成多个子集，每个子集又选择最具影响力的属性进展划分，一直进展到所有自己仅包含同一类型的样本为止，最后得到一颗决策树。决策树的构造采用自上而下，分而治之的递归方式。初始时根节点包含数据集的所有的样本。假设一个结点包含的样本均为同一个类别，则该结点成为叶结点并标记为该类别；否则采用信息增益的度量选择适宜的分类属性，将数据集划分为假设干个子集。该属性成为相应结点的测试属性。对测试属性的每个值都创立一个分支，同时也包含一个被划分的子集。递归的对所获得的每个划分形成一颗决策

28、树。一旦一个属性出现在*个结点上，则不能出现在该结点之后所产生的子树结点上。当一个结点包含的所有样本均为同一类别或没有样本满足测试属性值，则算法终止。属性信息增益选择测试属性的方法如下：设数据集S有s个样本，类别属性有m个不同的取值。定义m个不同的类Ci，i1,2,3m。设si为类别Ci的样本个数，则对一个数据集分类所需的期望信息为：Is,ss)=-log3.1其中p是任意一个样本，类别属性有m个不同的取值，定义m个不同的类C的概率，可以按s/S计算。因为采用二进制编码，所以对数函数以2为底。设属性A可取v个不同的值a,a,aa.可以用属性A将S划分为v个子集S，S,S,其中Sj包含S中属性A

29、中取值a为1的样本。假设属性A为测试属性，设s为子集S中属于C类别的样本数。则利用属性A划分当前集合所需要的期望信息计算如下：EA=Is,s,ss) 其中成为第j个子集的权值。EA)值越小，表示子集划分结果越好。而对于一个给定子集S，其期望信息如式3.1，其中p=为子集S中任意一个样本属于类别C的概率。由此利用属性A对当前分支结点进展划分所获得的信息增益是： Gain(A)=I(s,s,s)-E(A)Gain(A)是根据属性A进展集合划分所获得的信息熵的减少量。3.2.2 改良算法C4.5算法是由ID3算法演变而来，除了具有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能。(1)

30、信息增益比例的概念信息增益比例是在信息增益概念根底上开展来的，表示为：GainRatioA=GainA/SplitIA其中SplitIA=-设属性A具有V个不同的值a1,a2,av,可以用属性A将S划分为V个子集s1,s2,sv,其中Sj包含S中这样一些样本：它们在A上具有值aj.(2)合并具有连续值的属性 ID3算法最初假定属性离散值，但在实际环境中，很多属性值是连续的.对于连续属性值，C4.5其处理过程如下：*根据属性的值，对数据集排序；*用不同的阈值将数据集动态地进展划分；*当输出改变时确定一个阈值；*取两个实际值中的中点作为一个阈值；*取两个划分，所有的样本都在这两个划分中；*得到所有

31、可能的阈值、增益、及增益比；*在每一个属性会变为两个取值，即小于阈值或大于阈值；处理含有未知属性值的训练样本 C4.5处理样本中可以含有未知的属性值，其处理方法是用最常用的值分在同一类中。具体采用概率的方法，依据属性的值，对属性和每一个值赋予一个概率，取得这些概率依赖于该属性的值。规则的产生一旦树被建立。就可以把树转换成if-then的规则，规则存储于一个二维的数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。表中的每列存放着树中的结点。3.2.3 ID3算法计算学生的成绩信息理工科学生成绩分析表如下：*性别根底程度上机时间学习成绩001女良好=3良好002女一般1-2一般003男好

32、12一般004男一般=1一般005男一般0不及格006女好=1一般007男好=1良好008女良好=3良好011女一般1-2一般012男好=3良好014男一般=1一般.从表中选取14个样本，其中良好的人数有6个，一般的人数有7个，不及格一个人；选择是否良好为类别属性。其中良好用yes表示，一般用no表示，Yes有6人，no有7人；即I6,7=-6/13log6/13-7/13log7/13=0.9957依次计算各个属性，性别属性 A性别=男，yes有4个，no有4个I4,4=1B.性别=女，yes有2个，no有3个I2,3=0.9710E性别=8/13+5/13*0.9710=0.9888Gai

33、n(性别=0.9957-0.9888=0.0069根底程度属性A.根底程度=良好，yes有2个，no有0个I(2，0)=0 B根底程度=好，yes有2个，no有3个I2,3=0.9710 C.根底程度=一般，yes有2个，no有4个 I2,4=0.9180E根底程度=5/13*0.9710+6/13*0.9180=0.7972 Gain根底程度=0.9957-0.7972=0.1985上机时间属性 A.上机时间=3,yes有3个，no有0个 I3,0=0 E上机时间=6/13=0.4615 Gain(上机时间=0.9957-0.4615=0.5342由此可知，上机时间的信息增益值最大，因此选做

34、根节点。上机时间=3*性别根底程度成绩001女良好良好013男一般良好确定叶节点得到的决策树如下所示：3.2.4 改良算法计算学生的信息*性别根底程度上机时间学习成绩001女良好=3良好002女一般1-2一般003男好12一般004男一般=1一般005男一般0不及格006女好=1一般007男好=1良好008女良好=3良好011女一般1-2一般012男好=3良好014男一般=3,S11=3, s21=0, I(3,0)=0 2.上机时间=1-2，s21=4, s22=0, I(4,0)=0 3.上机时间=3计算每个子树的生成过程：对于第一个子树，yes有3个，no有3个，I(3,3)=11.计算

35、性别属性的SplitI值得到： SplitI(性别=4/6log4/6 - 2/6log2/6=0.9183对于决策学习成绩，计算性别的两个属性的分布的期望信息得到：1.性别=男，S11=2，s21=2, I(2,2)=12.性别=女，S12=1，s22=1, I(1,1)=1因此得性别属性的熵为：E性别=1对应的信息增益为：Gain 性别=1-1=0信息增益比例：GainRatio(性别=0计算根底程度属性的SplitI值得到： SplitI根底程度=-2/6log2/6 - 3/6log3/6-1/6log1/6=1.4591对于决策学习成绩属性来说，计算根底程度的每个分布的信息增益： 1.根底程度=一般，S11=2，S21=0，I2,0=0 2.根底程度= 好，S12=2，s22=1, I(2,1)=0.9180 3.根底程度=良好，s13=1,s33=0 , I(1,0)=0因此得根底程度属性的熵为： E根底程度=4/6*0.9180=0.6120对应的信息增益为：Gain根底程度=1-0.612=0.3880信息增益比例GainR