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

1、-作者xxxx-日期xxxx决策树在成绩分析中的应用【精品文档】学年论文 决策树在成绩分析中的应用 学院：计算机科学与工程学院 班级：* 学号: * 姓名: * 导师： * 摘要1Abstract2第一章 绪论31.1数据挖掘的历史、发展333第二章 数据挖掘的基本知识42.1 数据挖掘的定义4442.2.2 按挖掘对象4 2.2.3 按挖掘方法52.2.4 按数据挖掘所能发现的知识5552.3.2决策树方法 52.3.3 神经网络方法52.3.4遗传算法 62.4数据挖掘的实现过程 62.4.1 数据准备 662.4.3 模式的评估解释62.4.4 知识运用 6第三章 决策树技术663.2算

2、法描述 73.2.1 ID3算法73.2.2 改进算法83.2.3 ID3算法计算学生的成绩信息 83.2.4 改进算法计算学生的信息13第四章 总结17参考文献：18【精品文档】 决策树在成绩分析中的应用 摘要 数据挖掘的提出是在20世纪80年代，它是一个新兴的、面向商业应用的AI研究领域，20世纪末，随着Internet的普及，全球信息量以惊人的速度急剧增长，据估计每二十个月增加一倍。目前的数据库系统虽然可以高效的实现数据的录入、查询、和统计等功能，但却无法发现海量数据中隐藏的知识和规律；人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效的利用这些数据。如何将这

3、些海量的数据从数据库中提取出来，并转为有用的信息；面对这一挑战，数据挖掘和知识发现技术应运而生，并显示强大的生命力。数据挖掘和知识发现使数据处理技术进入一个更高级的阶段。它不仅能对过去的数据进行查询，而且能够找出过去数据进行查询，而且能够找出过去数据之间潜在的联系，进行更高层次的分析，以便更好的解决决策、预测等问题。数据挖掘，从技术角度而言，数据挖掘是从大量的，不完全的，有噪声的、模糊的、随机的实际数据中，提取隐含在其中人们事先不知道但有潜在有用的信息和知识的过程。从商业角度，数据挖掘是一种新的商业信息处理技术，其主要的特点是对数据库中的大量业务数据进行抽取、转换、分析和其他模型换处理，从中提

4、取辅助商业决策的关键性信息和知识。本论文主要论述的是利用决策树技术对于大量的学生数据进行分析，在其中挖掘有用的信息，目的是提高教学质量。决策树技术，用于分类和预测的主要的技术，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出决策树表示形式的分类规则，它包括两个步骤：一，利用训练样本集来建立并精化出一颗决策树，建立决策树模型。即从数据中获取知识，进行机器学习的过程。二，利用建好的决策树对新的数据进行分类。关键字：数据挖掘，决策树技术，成绩分析 Application of decision tree in performance analysisAbstract

5、 Data mining is put forward in 1980s，it is a new, twentieth Century for the commercial application of AI research field,at the end, with the popularity of Internet, the global information has dramatically increased at an alarming rate, is estimated to be doubled every twenty months. Although the cur

6、rent 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 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 t

7、hese data effectively. How these massive data extracted from the database, and turn them into useful the information; in the face of this challenge, data mining and knowledge discovery technology came into being, and show strong vitality. Data mining and knowledge discovery, data processing technolo

8、gy 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, higher level of analysis, in order to better solve the decision problem. Data mining, prediction, from a technical point of view, data mini

9、ng is from a large number of, incomplete, noisy, fuzzy and random of the actual data, extract some unknown but potentially useful information and knowledge process. From the business perspective, the data mining is a new business information processing technology, its main characteristic is to a lar

10、ge number of business data in the database the extraction, transformation, analysis and other models for processing, extraction business decisions from the key information and knowledge. This paper mainly discusses the use of decision tree technology for the analysis of a large number of student dat

11、a, in which mining useful information, the purpose is to improve the quality of teaching. Decision tree for classification and prediction of the main technology and decision tree learning is instance based inductive learning algorithm, it looks from a group of out of order, irregular instance reason

12、ing decision tree representation of classification rules, which includes two steps: a using training sets to establish and refine the decision tree, decision tree model is built. From the data access to knowledge, carry on the machine learning process. Second, using the built decision tree to classi

13、fy new data.Keywords: data mining, decision tree technology， performance analysis 第一章 绪论 1.1数据挖掘的历史、发展 由于大型数据系统的广泛使用和把数据转换成有用知识的迫切的需要，数据挖掘引起了各行业的关注。20世纪60年代，为了适应信息的电子话需求，信息技术一直从简单的文件处理系统向有效的数据库系统变革。20世纪70年代，数据库系统的三个主要的模式：层次，网络，关系型数据库的研究和开发取得了重要的进展。20世纪80年代，关系型数据库及其相关的数据模型相关工具，数据索引技术局组织被广泛采用，并且成为了整个数

14、据库市场的主导。20世纪80年代中期开始，关系型数据库技术和新型技术的结合成为数据库研究和发展的重要标志。从数据的分布角度看，分布式数据库及其透明性、并发控制、并行处理等成为必须面对的课题。许多的商业活动中，由于数据库的普及，人工去整理和理解如此大的数据源已经存在效率、准确性等问题，并不是每个人都能够从过去的销售情况预测将来的发展趋势或做出正确的决策。20世纪80年代 ，产生了数据技术并得到了广泛的应用。高性能的关系数据库引擎以及相关的分布式查询、并发控制等技术的应用，已经提升了数据库的应用能力。在数据的快速访问、集成和抽取等问题上有了突破，数据仓库作为一种新型的数据存储和处理手段，被数据库厂

15、商广泛的应用。20世纪80年代后期，产生了数据挖局等思想。90年代，分布式数据库理论上趋于成熟，然而本质上查询是对数据库的被动的使用。由于简单查询只是数据库内容的选择性输出，因此它和人们期望的分析预测、决策支持等高级应用人有很大的距离。近年来，由于数据采集技术的更新，决策所面对的数据量在不断的增长，随着数据的急剧增长，现有信息管理系统中的数据分析工具已无法适应新的需求。人们希望能够提供更高层次的数据分析功能，自动和智能地将待处理的数据转化为有用的信息和知识。 数据挖掘必须经过概念的提出、概念的接受、广泛研究和探索、逐步应用和大量应用等阶段。目前，大部分的学者认为数据挖掘仍然处于广泛研究和探索阶

16、段。数据挖掘应在如下方面进行开展： 1.数据挖掘技术与商业逻辑的平滑集成问题 第二章 数据挖掘的基本知识 2.1 数据挖掘的定义 从技术角度而言，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中，提取隐含在其中人们事先不知道但又潜在有用的信息和知识的过程。这一定义包括多层含义、及数据源必须是真实的、海量的、发现的知识应是用户感兴趣的，并且是可接受的、可理解的和可应用的，可以仅支持特定的问题。 从商业角度而言，数据挖掘是一种新的商业信息处理技术，其主要的特点数对数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性信息和知识。数据挖掘的本质是一种

17、深层次的数据分析方法。因此数据挖掘可以描述为按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的有效方法。 1. 分类或预测模型发现 2.数据总结与聚类发现 3.关联规则发现 5.相似模式发现 6.混沌模式发现 2.2.2 按挖掘对象1.关系型数据库挖掘 2.面向对象数据挖掘 3.空间数据库挖掘 4.时态数据库挖掘 5.文本数据源挖掘 6.多媒体数据库挖掘 7.异质数据库挖掘 8.遗产数据库挖掘 2.2.3 按挖掘方法 1.机器学习方法 2.统计方法 3. 聚类分析方法 5.遗传算法方法 6.数据库方法 7.近似推理和不确定性推理方法

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

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

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

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

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

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

24、其中Sj包含S中属性A中取值a为1的样本。若属性A为测试属性，设s为子集S中属于C类别的样本数。则利用属性A划分当前集合所需要的期望信息计算如下：E（A）=I（s,s,s.s) 其中成为第j个子集的权值。E（A)值越小，表示子集划分结果越好。而对于一个给定子集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算

25、法引入了新的方法和增加了新的功能。(1)信息增益比例的概念信息增益比例是在信息增益概念基础上发展来的，表示为：GainRatio（A）=Gain（A）/SplitI（A） 其中 SplitI（A）=- 设属性A具有V个不同的值a1,a2,.av,可以用属性A将S划分为V个子集s1,s2,.sv,其中Sj包含S中这样一些样本：它们在A上具有值aj.(2)合并具有连续值的属性 ID3算法最初假定属性离散值，但在实际环境中，很多属性值是连续的.对于连续属性值，C4.5其处理过程如下：*根据属性的值，对数据集排序；*用不同的阈值将数据集动态地进行划分；*当输出改变时确定一个阈值；*取两个实际值中的中点

26、作为一个阈值；*取两个划分，所有的样本都在这两个划分中 ；*得到所有可能的阈值、增益、及增益比；*在每一个属性会变为两个取值，即小于阈值或大于阈值；（3） 处理含有未知属性值的训练样本 C4.5处理样本中可以含有未知的属性值，其处理方法是用最常用的值分在同一类中。 具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率依赖于该属性已知的值。（4） 规则的产生 一旦树被建立。就可以把树转换成if-then的规则，规则存储于一个二维的数组中，每一行代表树中的一个规则，即从根到叶之间 的一个路径。表中的每列存放着树中的结点。 3.2.3 ID3算法计算学生的成绩信息 理工科

27、学生成绩分析表如下：学号性别基础程度上机时间学习成绩001女良好=3良好002女一般1-2一般003男好1-2一般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人；即 I（6,7）=-6/13log6/13-7/13log依次计算各个属性，1. 性别属性 A性别=男，yes有4个，no有4个I（4,4）=1B.性别=女，ye

28、s有2个，no有3个2. 基础程度属性 A.基础程度=良好，yes有2个，no有0个 I(2，0)=0 B基础程度=好，yes有2个，no有3个 C.基础程度=一般，yes有2个，no有4个 3. 上机时间属性 A.上机时间=3,yes有3个，no有0个 I（3,0）=0由此可知，上机时间的信息增益值最大，因此选做根节点。 上机时间=3学号性别基础程度成绩001女良好良好013男一般良好确定叶节点得到的决策树如下所示：3.2.4 改进算法计算学生的信息学号 性别基础程度上机时间学习成绩001女良好=3良好002女一般1-2一般003男好1-2一般004男一般=1一般005男一般0不及格006女

29、好=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.计算性别属性的SplitI值得到： SplitI(性别）=4/6log4/6 - 2/6log对于决策学习成绩，计算性别的两个属性的分布的期望信息得到：1.性别=男，S11=2，s21=2, I(2,2)=12.性别=女，S12=1，s22=1, I(1,1)=1因此得性别属性

30、的熵为：E（性别）=1对应的信息增益为：Gain （性别）=1-1=0信息增益比例：GainRatio(性别）=02. 计算基础程度属性的SplitI值得到： SplitI（基础程度）=-2/6log2/6 - 3/6log3/6-1/6log对于决策学习成绩属性来说，计算基础程度的每个分布的信息增益： 1.基础程度=一般，S11=2，S21=0，I（2,0）=0 2.基础程度= 好， 3.基础程度=良好，s13=1,s33=0 , I(1,0)=0因此得基础程度属性的熵为： 对应的信息增益为：信息增益比例因此选择信息增益比例最大的基础程度作为子根节点，根据基础程度的取值，分为三个分支，同时数据集被划分为三个子集。上机时间=1-2，确定为no。上机时间=3, 确定为yes。yesno基础程度上机时间=3yes性别yesno一般 好良好男女no学习成绩是否优良形成规则： IF 上机时间=1 and 基础程度=一般 then 学习成绩一般 IF 上机时间 =1and 基础程度=好and 性别=男