决策树在成绩分析中的应用.docx
《决策树在成绩分析中的应用.docx》由会员分享，可在线阅读，更多相关《决策树在成绩分析中的应用.docx（24页珍藏版）》请在冰点文库上搜索。
决策树在成绩分析中的应用
学年论文《决策树在成绩分析中的应用》
学院：
计算机科学与工程学院
班级：
*********
学号:
*************
姓名:
***
导师：
**
决策树在成绩分析中的应用
摘要
数据挖掘的提出是在20世纪80年代，它是一个新兴的、面向商业应用的AI研究领域，20世纪末，随着Internet的普及，全球信息量以惊人的速度急剧增长，据估计每二十个月增加一倍。
目前的数据库系统虽然可以高效的实现数据的录入、查询、和统计等功能，但却无法发现海量数据中隐藏的知识和规律；人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效的利用这些数据。
如何将这些海量的数据从数据库中提取出来，并转为有用的信息；面对这一挑战，数据挖掘和知识发现技术应运而生，并显示强大的生命力。
数据挖掘和知识发现使数据处理技术进入一个更高级的阶段。
它不仅能对过去的数据进行查询，而且能够找出过去数据进行查询，而且能够找出过去数据之间潜在的联系，进行更高层次的分析，以便更好的解决决策、预测等问题。
数据挖掘，从技术角度而言，数据挖掘是从大量的，不完全的，有噪声的、模糊的、随机的实际数据中，提取隐含在其中人们事先不知道但有潜在有用的信息和知识的过程。
从商业角度，数据挖掘是一种新的商业信息处理技术，其主要的特点是对数据库中的大量业务数据进行抽取、转换、分析和其他模型换处理，从中提取辅助商业决策的关键性信息和知识。
本论文主要论述的是利用决策树技术对于大量的学生数据进行分析，在其中挖掘有用的信息，目的是提高教学质量。
决策树技术，用于分类和预测的主要的技术，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出决策树表示形式的分类规则，它包括两个步骤：
一，利用训练样本集来建立并精化出一颗决策树，建立决策树模型。
即从数据中获取知识，进行机器学习的过程。
二，利用建好的决策树对新的数据进行分类。
关键字：
数据挖掘，决策树技术，成绩分析
Applicationofdecisiontreeinperformanceanalysis
Abstract
Dataminingisputforwardin1980s，itisanew,twentiethCenturyforthecommercialapplicationofAIresearchfield,attheend,withthepopularityofInternet,theglobalinformationhasdramaticallyincreasedatanalarmingrate,isestimatedtobedoubledeverytwentymonths.Althoughthecurrentdatabasesystemcanachievedataentry,efficientthequeryandstatisticalfunctions,butcannotfindtheknowledgeandruleshiddeninmassivedata;themainproblemsthatpeoplearefacingisnotlackofenoughinformationcanbeused,butthefaceofthevastoceanofdataandhowtousethesedataeffectively.Howthesemassivedataextractedfromthedatabase,andturnthemintousefultheinformation;inthefaceofthischallenge,dataminingandknowledgediscoverytechnologycameintobeing,andshowstrongvitality.Dataminingandknowledgediscovery,dataprocessingtechnologyintoaAmoreadvancedstage.Itcannotonlyqueryonpastdata,andcanidentifythepastdataquery,andtofindoutthepotentiallinkbetweenpastdata,higherlevelofanalysis,inordertobettersolvethedecisionproblem.Datamining,prediction,fromatechnicalpointofview,dataminingisfromalargenumberof,incomplete,noisy,fuzzyandrandomoftheactualdata,extractsomeunknownbutpotentiallyusefulinformationandknowledgeprocess.Fromthebusinessperspective,thedataminingisanewbusinessinformationprocessingtechnology,itsmaincharacteristicistoalargenumberofbusinessdatainthedatabasetheextraction,transformation,analysisandothermodelsforprocessing,extractionbusinessdecisionsfromthekeyinformationandknowledge.
Thispapermainlydiscussestheuseofdecisiontreetechnologyfortheanalysisofalargenumberofstudentdata,inwhichminingusefulinformation,thepurposeistoimprovethequalityofteaching.
Decisiontreeforclassificationandpredictionofthemaintechnologyanddecisiontreelearningisinstancebasedinductivelearningalgorithm,itlooksfromagroupofoutoforder,irregularinstancereasoningdecisiontreerepresentationofclassificationrules,whichincludestwosteps:
ausingtrainingsetstoestablishandrefinethedecisiontree,decisiontreemodelisbuilt.Fromthedataaccesstoknowledge,carryonthemachinelearningprocess.Second,usingthebuiltdecisiontreetoclassifynewdata.
Keywords:
datamining,decisiontreetechnology，performanceanalysis
第一章绪论
数据挖掘的历史、发展
数据挖掘技术的商业需求分析
由于大型数据系统的广泛使用和把数据转换成有用知识的迫切的需要，数据挖掘引起了各行业的关注。
20世纪60年代，为了适应信息的电子话需求，信息技术一直从简单的文件处理系统向有效的数据库系统变革。
20世纪70年代，数据库系统的三个主要的模式：
层次，网络，关系型数据库的研究和开发取得了重要的进展。
20世纪80年代，关系型数据库及其相关的数据模型相关工具，数据索引技术局组织被广泛采用，并且成为了整个数据库市场的主导。
20世纪80年代中期开始，关系型数据库技术和新型技术的结合成为数据库研究和发展的重要标志。
从数据的分布角度看，分布式数据库及其透明性、并发控制、并行处理等成为必须面对的课题。
许多的商业活动中，由于数据库的普及，人工去整理和理解如此大的数据源已经存在效率、准确性等问题，并不是每个人都能够从过去的销售情况预测将来的发展趋势或做出正确的决策。
20世纪80年代，产生了数据技术并得到了广泛的应用。
高性能的关系数据库引擎以及相关的分布式查询、并发控制等技术的应用，已经提升了数据库的应用能力。
在数据的快速访问、集成和抽取等问题上有了突破，数据仓库作为一种新型的数据存储和处理手段，被数据库厂商广泛的应用。
20世纪80年代后期，产生了数据挖局等思想。
90年代，分布式数据库理论上趋于成熟，然而本质上查询是对数据库的被动的使用。
由于简单查询只是数据库内容的选择性输出，因此它和人们期望的分析预测、决策支持等高级应用人有很大的距离。
近年来，由于数据采集技术的更新，决策所面对的数据量在不断的增长，随着数据的急剧增长，现有信息管理系统中的数据分析工具已无法适应新的需求。
人们希望能够提供更高层次的数据分析功能，自动和智能地将待处理的数据转化为有用的信息和知识。
数据挖掘研究的发展趋势
数据挖掘必须经过概念的提出、概念的接受、广泛研究和探索、逐步应用和大量应用等阶段。
目前，大部分的学者认为数据挖掘仍然处于广泛研究和探索阶段。
数据挖掘应在如下方面进行开展：
1.数据挖掘技术与商业逻辑的平滑集成问题
2.数据挖掘技术与特定的数据存储类型的适应问题
3.大型数据的选择与规格化问题
4.数据挖掘系统的构架与交互式挖掘技术
5.数据挖掘语言与系统的可视化问题
6.数据挖掘理论与算法研究
第二章数据挖掘的基本知识
数据挖掘的定义
从技术角度而言，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中，提取隐含在其中人们事先不知道但又潜在有用的信息和知识的过程。
这一定义包括多层含义、及数据源必须是真实的、海量的、发现的知识应是用户感兴趣的，并且是可接受的、可理解的和可应用的，可以仅支持特定的问题。
从商业角度而言，数据挖掘是一种新的商业信息处理技术，其主要的特点数对数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性信息和知识。
数据挖掘的本质是一种深层次的数据分析方法。
因此数据挖掘可以描述为按企业既定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的有效方法。
数据挖掘的分类
数据挖掘按挖掘任务类型
1.分类或预测模型发现
2.数据总结与聚类发现
3.关联规则发现
4.序列模式发现
5.相似模式发现
6.混沌模式发现
7.依赖关系或依赖模型发现异常和趋势发现等
按挖掘对象
1.关系型数据库挖掘
2.面向对象数据挖掘
3.空间数据库挖掘
4.时态数据库挖掘
5.文本数据源挖掘
6.多媒体数据库挖掘
7.异质数据库挖掘
8.遗产数据库挖掘
数据库挖掘
按挖掘方法
1.机器学习方法
2.统计方法
3.聚类分析方法
4.神经网络方法
5.遗传算法方法
6.数据库方法
7.近似推理和不确定性推理方法
8.给予证据理论和元模式的方法
9.现代数学分析方法
10.粗糙集或模糊集方法
11.集成方法等
按数据挖掘所能发现的知识
1.挖掘广义型知识
2.挖掘差异型知识
3.挖掘关联型知识
4.挖掘预测性知识
5.挖掘偏离型知识
6.挖掘不确定性知识
数据挖掘技术的主要方法
关联规则方法
从数据集中发现关联规则，该规则显示给定数据集中经常一起出现的属性--值元组。
例如：
x--->y说吧表达的含义是满足X远足有可能满足Y。
关联分析在交易数据分析、支持定向、商品目录设计和其他业务决策等方面有着广泛的应用。
决策树方法
ID3算法是最典型的决策树分类算法，决策树是从机器学习角度研究和发展起来的，对于大训练样本集很难适应。
决策树是通过一系列规则对数据进行分类的过程。
以树的形式来表达模型，主要是对属性值进行归纳分类，它采用自顶向下的递归方式，在决策树内部节点进行属性值的比较，并根据不同的属性值来判断从该节点向下的分支，在决策树的叶节点得到结论。
采用决策树可以将数据规则可视化，不需要更长时间的构造过程，输出结果容易理解，精度较高。
神经网络方法
是人们在模拟人脑处理问题的过程中发展起来的新型智能信息处理理论。
它通过大量的称为神经元的简单处理单元构成非线性动力学系统，对人脑的形象思维、联想记忆等进行模拟和抽象，实现与人脑相似的学习、识别、记忆等信息处理能力。
遗传算法
是模拟自然界生化进化过程的随机化搜索算法，它以很强的解决问题能力和广泛的适应性渗透到研究与工程的各个领域。
遗传算法是一种高效的全局并行搜索优化算法。
数据挖掘的实现过程
数据准备
数据挖掘的处理对象是海量的数据，是长期积累的结果。
这些数据不适合直接进行挖掘，需要进行预处理。
数据预处理包括数据的选择、清洁（消除噪声、冗余数据）、推测（推算缺失数据）、转换（离散型数据与连续型数据之间的转换）、数据缩减（减少数据量）。
数据挖掘
根据挖掘的目标，选取相应算法的参数，分析数据，得到可能形成知识的模型
模式的评估解释
通过上述步骤得到的模式，有可能是没有意义或没有实用价值的，因此需要评估，确定哪些是有效的、有用的模式。
此外，大部分模式是数学表达式，需要将其解释成可理解的方式呈现给用户。
知识运用
运用只是主要有两种途径。
一、只许看知识本身描述的关系或结果，就可以对决策提供支持；二、要求对新的数据运用知识，由此可能产生新的问题，并需要对知识做进一步优化。
第三章决策树技术
决策树技术
决策树是分类预测的主要方法，采用基于实例的归纳学习算法，旨在从一组无次序、无规则的实例中推理出决策树形式的分类规则，采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分枝，在决策树的叶节点得到结论，所以从根到叶节点对应一条合取规则，整颗树对应一组析取规则。
决策树分类是利用属性值对各子集逐级划分，直到一个结点仅含有同一类样本为止。
算法描述
ID3算法
基本思路是首先在数据集中采用信息增益作为属性选择的标准，找出最有影响力的属性，将数据集分成多个子集，每个子集又选择最具影响力的属性进行划分，一直进行到所有自己仅包含同一类型的样本为止，最后得到一颗决策树。
决策树的构造采用自上而下，分而治之的递归方式。
初始时根节点包含数据集的所有的样本。
若一个结点包含的样本均为同一个类别，则该结点成为叶结点并标记为该类别；否则采用信息增益的度量选择合适的分类属性，将数据集划分为若干个子集。
该属性成为相应结点的测试属性。
对测试属性的每个已知值都创建一个分支，同时也包含一个被划分的子集。
递归的对所获得的每个划分形成一颗决策树。
一旦一个属性出现在某个结点上，则不能出现在该结点之后所产生的子树结点上。
当一个结点包含的所有样本均为同一类别或没有样本满足测试属性值，则算法终止。
属性信息增益选择测试属性的方法如下：
设数据集S有s个样本，类别属性有m个不同的取值。
定义m个不同的类Ci，i
{1,2,3.......m}。
设si为类别Ci的样本个数，则对一个数据集分类所需的期望信息为：
I（s
s
.......s
）=-
log
（）
其中p
是任意一个样本，类别属性有m个不同的取值，定义m个不同的类C
的概率，可以按s
/S计算。
因为采用二进制编码，所以对数函数以2为底。
设属性A可取v个不同的值{a
a
a
.........a
}.可以用属性A将S划分为v个子集{S
，S
.......S
},其中Sj包含S中属性A中取值a
为1的样本。
若属性A为测试属性，设s
为子集S
中属于C
类别的样本数。
则利用属性A划分当前集合所需要的期望信息计算如下：
E（A）=
I（s
s
s
......s
）
其中
成为第j个子集的权值。
E（A）值越小，表示子集划分结果越好。
而对于一个给定子集S
，其期望信息如式（），其中p
=
为子集S
中任意一个样本属于类别C
的概率。
由此利用属性A对当前分支结点进行划分所获得的信息增益是：
Gain（A）=I（s
s
.........s
）-E（A）
Gain（A）是根据属性A进行集合划分所获得的信息熵的减少量。
改进算法
算法是由ID3算法演变而来，除了具有ID3算法的功能外，算法引入了新的方法和增加了新的功能。
（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算法最初假定属性离散值，但在实际环境中，很多属性值是连续的.对于连续属性值，其处理过程如下：
*根据属性的值，对数据集排序；
*用不同的阈值将数据集动态地进行划分；
*当输出改变时确定一个阈值；
*取两个实际值中的中点作为一个阈值；
*取两个划分，所有的样本都在这两个划分中；
*得到所有可能的阈值、增益、及增益比；
*在每一个属性会变为两个取值，即小于阈值或大于阈值；
（3）处理含有未知属性值的训练样本
处理样本中可以含有未知的属性值，其处理方法是用最常用的值分在同一类中。
具体采用概率的方法，依据属性已知的值，对属性和每一个值赋予一个概率，取得这些概率依赖于该属性已知的值。
（4）规则的产生
一旦树被建立。
就可以把树转换成if-then的规则，规则存储于一个二维的数组中，每一行代表树中的一个规则，即从根到叶之间的一个路径。
表中的每列存放着树中的结点。
ID3算法计算学生的成绩信息
理工科学生成绩分析表如下：
学号
性别
基础程度
上机时间
学习成绩
001
女
良好
>=3
良好
002
女
一般
1--2
一般
003
男
好
1---2
一般
004
男
一般
<=1
一般
005
男
一般
0
不及格
006
女
好
<=1
一般
007
男
好
<=1
良好
008
女
良好
<=1
良好
009
男
好
1--2
一般
010
男
一般
>=3
良好
011
女
一般
1--2
一般
012
男
好
<=1
良好
013
男
一般
>=3
良好
014
男
一般
<=1
一般
...
...
...
...
...
...
...
...
...
...
从表中选取14个样本，其中良好的人数有6个，一般的人数有7个，不及格一个人；选择是否良好为类别属性。
其中‘良好’用yes表示，‘一般’用no表示，
Yes有6人，no有7人；
即I（6,7）=-6/13log
6/13-7/13log
7/13=
依次计算各个属性，
1.性别属性
A性别=‘男’，yes有4个，no有4个
I（4,4）=1
B.性别=‘女’，yes有2个，no有3个
I（2,3）=
E（性别）=8/13+5/13*=
2.Gain（性别）=基础程度属性
A.基础程度=‘良好’，yes有2个，no有0个
I（2，0）=0
B基础程度=‘好’，yes有2个，no有3个
I（2,3）=
C.基础程度=‘一般’，yes有2个，no有4个
I（2,4）=
E（基础程度）=5/13*+6/13*=
3.Gain（基础程度）=上机时间属性
A.上机时间<=1,yes有3个，no有3个
I（3,3,）=1
B.上机时间=1--2，yes有0个，no有4个
I（0,4）=0
C.上机时间>=3,yes有3个，no有0个
I（3,0）=0
E（上机时间）=6/13=
Gain（上机时间）=由此可知，上机时间的信息增益值最大，因此选做根节点。
上机时间<=1
学号
性别
基础程度
学习成绩
004
男
一般
一般
006
女
好
一般
007
男
好
良好
008
女
良好
良好
012
男
好
良好
014
男
一般
一般
Yes有3个，no有3个
I（3,3）=1
1.性别属性
A.性别=‘男’，yes有2个，no有2个
I（2,2）=1
B.性别=‘女’，yes有1个，no有1个
I（1,1）=1
E（性别）=1
Gain（性别）=0
2.基础程度属性
A.基础程度=一般，yes有0个，no有2个
I（0,2）=0
B.基础程度=‘好’，yes有2个，no有1个
I（2,1）=
C.基础程度=‘良好’，yes有1个，no有0个
I（1,0）=0
E（基础程度）=3/6*=
Gain（基础程度）==
因此，以基础程度作为根节点
基础程度=‘一般’
学号
性别
学习成绩
004
男
一般
014
男
一般
因此，确定一个叶节点。
基础程度=‘好’
学号
性别
学习成绩
006
女
一般
007
男
良好
012
男
良好
Yes有2个，no有1个
I（2,1）=
因为只有属性性别，所以性别属性作为根节点
性别=‘男’
学号
学习成绩
007
良好
012
良好
确定一个叶节点，
性别=‘女’
学号
学习成绩
006
一般
确定叶节点
上机时间=1--2
学号
性别
基础程度
成绩
002
女
一般
一般
003
男
好
一般
009
男
好
一般
011
女
一般
一般
确定叶节点
上机时间>=3
学号
性别
基础程度
成绩
001
女
良好
良好
013
男
一般
良好
确定叶节点
得到的决策树如下所示：
改进算法计算学生的信息
学
升级会员 