范文一:决策树分类算法
决策树分类算法
决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是:利用训练集数据自动地构造决策树,然后根据这个决策树对任意实例进行判定。
1( 决策树的组成
决策树的基本组成部分有:决策节点、分支和叶,树中每个内部节点表示一个属性上的测试,每个叶节点代表一个类。图1就是一棵典型的决策树。
图1 决策树
决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如,CART算法得到的决策树每个节点有两个分支,这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。
下面介绍一个具体的构造决策树的过程,该方法
是以信息论原理为基础,利用信息论中信息增益寻找数据库中具有最大信息量的字段,建立决策树的一个节点,然后再根据字段的不同取值建立树的分支,在每个分支中重复建立树的下层节点和分支。
ID3算法的特点就是在对当前例子集中对象进行分类时,利用求最大熵的方法,找出例子集中信息量(熵)最大的对象属性,用该属性实现对节点的划分,从而构成一棵判定树。
首先,假设训练集C中含有P类对象的数量为p,N类对象的数量为n,则利用判定树分类训练集中的对象后,任何对象属于类P的概率为p/(p+n),属于类N的概率为n/(p+n)。
当用判定树进行分类时,作为消息源“P”或“N”有关的判定树,产生这些消息所需的期望信息为:
ppnnI(p,n),,log,log 22p,np,np,np,n
如果判定树根的属性A具有m个值,A, A, ?, 12A,,它将训练集C划分成,C, C, ?, C,,其中m12mA包括C中属性A的值为A的那些对象。设C包iii括p个类P对象和n个类N对象,子树C所需的iii期望信息是I(p, n)。以属性A作为树根所要求的期ii
望信息可以通过加权平均得到
m,pnii,E(A)I(pi,ni), ,pn,i1
(p+n)/(p+n)就是第i个分支的权值,显然,它与训ii
练集C中属于C 的对象数量成比例。所以按A分i
支的信息增益为:
Gain(A)=I(p, n)-E(A)
ID3算法在构造树的过程中,选择增益最大的属性A作为根节点。然后,对子树C, C, ?, C做k12m同样处理,递归形成判定树。
1假设表1是一个天气情况的气候数据,描述气候的特征属性有四个:outlook、temperature、humidity、windy,而每个特征属性的可取值为:outlook={sunny,overcast,rain},temperature={cool,mild,hot},humidity={high,normal},windy={true,false}。
如果某天早晨的天气描述为:
Outlook(天象) :overcast(阴)
Temperature(温度) :cool
Humidity(湿度) :normal
Windy(风) :false
那么,它属于哪种类型的气候呢,
下面介绍用ID3算法如何从表1所给的训练集中
构造出一棵能对训练集进行正确分类的判定树。
表1 气候训练集
Attributes
No. Class
Outlook Temperature Humidity Windy 1 Sunny Hot High False N 2 Sunny Hot High True N 3 Overcast Hot High False P 4 Rain Mild High False P 5 Rain Cool Normal False P 6 Rain Cool Normal True N 7 Overcast Cool Normal True P 8 Sunny Mild High False N 9 Sunny Cool Normal False P 10 Rain Mild Normal False P 11 Sunny Mild Normal True P 12 Overcast Mild High True P 13 Overcast Hot Normal False P 14 Rain Mild High True N
在表1所示的训练集中,总共有14个对象,其中9个
正例(P类),5个反例(N类)。分类要求的信息是
I(p, n)=-(9/14)log(9/14)-(5/14)log(5/14)=0.94bit
下面分别计算四个属性A,outlook,A,temperature,A123,humidity,A,windy的信息增益,选择信息增益最大的4
属性作为判定树的树根。
A,outlook的取值为{sunny,overcast,rain}。训练集1
C中14个对象有5个是sunny,2个是正例P,3个是反例N,即
p,2 n=3 11
I(p, n)=0.97 11
同理可得:
p,4 n=0 I(p, n)=0 2222
p,3 n=2 I(p, n)=0.971 3333
则属性A,outlook的期望信息要求为: 1
E(A)=(5/14) I(p, n)+(4/14) I(p, n)+(5/14) I(p, n) 1112233
,0.694bit
属性outlook的信息增益为:
Gain(outlook)=I(p, n)-E(A)=0.940-0.694=0.246bit 1
类似分析可得:
Gain (temperature)=0.029 bit
Gain (humidity) =0.151 bit
Gain (windy) =0.048 bit
? 构建判定树的树根和分枝
ID3算法将选择信息增益最大的属性outlook作为判定
树的根节点,在14个例子中对outlook的3个取值进行分枝,3个分枝对应3个子集,分别是:
F={1,2,8,9,11},F={3,7,12,13}, 12
F={4,5,6,10,14} 3
其中F中的例子全属于P类,因此对应分枝标记为P,2
其余两个子集既含有正例又含有反例,将递归调用建树算法。
? 递归建树算法
分别对F和F子集利用ID3算法,在每个子集中对各13
特征(仍为四个特征)求信息增益。
(a) F中的outlook全取sunny值,则I(p, n)= E(outlook),1
有Gain(outlook),0,在余下三个特征属性中求出
humidity的信息增益最大,以它为该分枝的根结点,
再向下分枝。Humidity取high全为N类,该分枝标
记N,取值normal全为P类,该分枝标记P。
(b) 在F中,对四个特征属性求信息增益,得到windy特3
征属性的信息增益最大,则以它为该分枝根结点,再
向下分枝,它取ture时全为N类,该分枝标记为N,
取false时全为P类,该分枝标记P。
这样就得到如图2所示的判定树。
图2 用ID3算法得到的有关气候的判定树
Outlook
Sunny Rain
Overcast Humidity Windy
High Normal True False
P
N N P P
范文二:决策树分类算法
决策树分类算法
决策树(decision tree)分类算法
决策树(decision tree)分类算法
决策树是以实例为基础的归纳学习算法。它从一组无次序、无规则的元组中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式,在决策树的内部结点进行属性值
的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类。从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则。1986年
Quinlan提出了著名的ID3算法。在ID3算法的基础上,1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要,后来又提出了若干改进的算法,其中SLIQ(super-
vised learning in quest)和SPRINT(scalable parallelizableinduction of decision trees)是比较有代表性的两个算法。
(1)ID3算法
ID3算法的核心是:在决策树各级结点上选择属性时,用信息增益(information gain)作为属性的选择标准,以使得在每一个非叶结点进行测试时,能获得关于被测试记录最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。
某属性的信息增益按下列方法计算。通过计算每个属性的信息增益,并比较它们的大小,就不难获得具有最大信息增益的属性。
设S是s个数据样本的集合。假定类标号属性具有m个不同值,定义m个不同类Ci(i=1,…,m)。设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出:
其中pi=si/s是任意样本属于Ci的概率。注意,对数函数以2为底,其原因是信息用二进制编码。
设属性A具有v个不同值{a1,a2,…,av}。可以用属性A将S划分为v个子
…,Sv},其中Sj中的样本在属性A上具有相同的值aj(j=1,2,…,v)。集{S1,S2,
设sij是子集Sj中类Ci的样本数。由A划分成子集的熵或信息期望由下式给出:
熵值越小,子集划分的纯度越高。对于给定的子集Sj,其信息期望为
其中pij=sij/sj是Sj中样本属于Ci的概率。在属性A上分枝将获得的信息增益是
Gain(A)=I(s1,s2,…,sm)-E(A)
ID3算法的优点是:算法的理论清晰,方法简单,学习能力较强。其缺点是:只对比较小的数据集有效,且对噪声比较敏感,当训练数据集加大时,决策树可能会随之改变。
(2)C4.5算法
C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:
1)用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;
2)在树构造过程中进行剪枝;
3)能够完成对连续属性的离散化处理;
4)能够对不完整数据进行处理。
C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。
(3)SLIQ算法
SLIQ算法对C4.5决策树分类算法的实现方法进行了改进,在决策树的构
预排序"和"广度优先策略"两种技术。 造过程中采用了"
1)预排序。对于连续属性在每个内部结点寻找其最优分裂标准时,都需要对训练集按照该属性的取值进行排序,而排序是很浪费时间的操作。为此,SLIQ算法采用了预排序技术。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序,以消除在决策树的每个结点对数据集进行的排序。具体实现时,需要为训练数据集的每个属性创建一个属性列表,为类别属性创建一个类别列表。
2)广度优先策略。在C4.5算法中,树的构造是按照深度优先策略完成的,需要对每个属性列表在每个结点处都进行一遍扫描,费时很多,为此,SLIQ采用广度优先策略构造决策树,即在决策树的每一层只需对每个属性列表扫描一次,就可以为当前决策树中每个叶子结点找到最优分裂标准。
SLIQ算法由于采用了上述两种技术,使得该算法能够处理比C4.5大得多的训练集,在一定范围内具有良好的随记录个数和属性个数增长的可伸缩性。
然而它仍然存在如下缺点:
1)由于需要将类别列表存放于内存,而类别列表的元组数与训练集的元组数是相同的,这就一定程度上限制了可以处理的数据集的大小。
2)由于采用了预排序技术,而排序算法的复杂度本身并不是与记录个数成线性关系,因此,使得SLIQ算法不可能达到随记录数目增长的线性可伸缩性。
(4)SPRINT算法
为了减少驻留于内存的数据量,SPRINT算法进一步改进了决策树算法的数据结构,去掉了在SLIQ中需要驻留于内存的类别列表,将它的类别列合并到每个属性列表中。这样,在遍历每个属性列表寻找当前结点的最优分裂标准时,不必参照其他信息,将对结点的分裂表现在对属性列表的分裂,即将每个属性列表分成两个,分别存放属于各个结点的记录。
SPRINT算法的优点是在寻找每个结点的最优分裂标准时变得更简单。其缺点是对非分裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点,若内存能够容纳下整个哈希表,其他属性列表的分裂只需参照该哈希表即可。由于哈希表的大小与训练集的大小成正比,当训练集很大时,哈希表可能无法在内存容纳,此时分裂只能分批执行,这使得SPRINT算法的可伸缩性仍然不是很好。
转自:空间完美搬家到新浪博客~
范文三:决策树分类算法研究
第18卷第4期
2005年12月
盐城工学院学报(自然科学版)
JournalofYanchengInstituteofTechnology(NaturalScience)
Vol.18No.4Dec.2005
决策树分类算法研究
沈晨鸣
3
(南京工程学院计算机工程系,江苏南京 210013)
摘 要:决策树分类算法是数据挖掘研究中的一个以样本数据集为基础的归纳学习方法,它
着眼于从一组无次序、无规则的样本数据集中推理出决策树表示形式的分类规则,提取描述样本数据集的数据模型。讨论了决策树分类算法的基本原理,给出了算法的特性并通过一个实例给出了具体的使用方法。
关键词:决策树;数据挖掘;信息增益中图分类号:TP39 文献标识码:A 文章编号:1671-5322(2005)04-0022-03 数据挖掘(DataMining,简称DM),是一种从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。它是数据库技术和智能技术的最前沿研究内容之一。
分类算法(classification),模型,其划分到某个数据类别中去。分类是数据挖掘领域中一个非常重要的研究课题。目前的技术和方法主要有决策树算法、贝叶斯分类和贝叶斯网络、神经网络、遗传算法、粗糙集和实例推理等。本文对最常用的决策树分类算法进行分析并通过一个实例说明其应用方法
[1]
,最有影响的是R.ID3算法,在ID3算法,Quilan又提出了C4.5算,后又提出了。
ID3算法的基本原理是:首先在数据集中用信息增益(informationgain)作为属性选择的标准找出最有影响力的属性,将数据集分成多个子集,每个子集又选择最有影响力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止,
[2]
最后得到一棵决策树
决策树分类算法采用自上而下,分而治之的递归方式来构造决策树。决策树开始时,作为一个单个节点(根节点)包含所有的样本数据集。若一个节点的样本均为同一类别,则该节点就成为叶节点并标记为该类别。否则该算法将采用信息增益的基于熵的度量作为启发信息来帮助选择合适的分类属性,以便将样本数据集划分为若干子集。该属性称为相应节点的“测试”属性。对测试属性的每个已知值都将被创建一个分支,同时也对应着一个被划分的子集。上述算法使用同样的过程,递归地对所获得的每个划分形成一个决策子树。一旦一个属性出现在一个节点上,则
。
1 决策树分类算法
决策树是一种从无次序、无规则的样本数据集中推理出决策树表示形式的分类规则方法。它采用自顶向下的递归方式,在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向下的分支,在决策树的叶节点得到结论,因此从根节点到叶节点的一条路径就对应着一条规则,整棵决策树就对应着一组表达式规则。
3
收稿日期:2005-09-17 作者简介:沈晨鸣(1963-),男,江苏南京人,南京工程学院副教授,主要研究方向为数据库、数据挖掘的教学和研
究。
第4期沈晨鸣:决策树分类算法研究?23?
它就不能再出现在该节点之后的所产生的子树节点中。当一个节点的所有样本均为同一类别或没
有样本满足test_attribute=ai,递归算法便终止。
在决策树方法中,树的每个节点使用信息增益来确定测试属性。选择具有最高信息增益(或最大熵压缩)的属性作为当前节点的测试节点属性。该属性使得对结果划分中的样本分类所需的信息量最小。具体方法如下:
设S是s个数据样本的集合,类别属性可以取m个不同的值,对应于m个不同的类别Ci,i∈{1,2,3,……m}。设si为类别Ci中的样本个数,则对一个数据集进行分类所需要的期望信息为:
m
对于一个给定子集Sj,它的期望信息为:
m
I(s1j,s2j,……,smj)=-
∑p
i=1
ij
log2(pij)
其中pij=
sij
|Sj|
,即为子集Sj中任一个数据样本属
于类别Ci的概率。
这样利用属性A对当前分支节点进行相应样本集合划分所获得的信息增益就是:
Gain(A)=I(s1,s2,……,sm)-E(A)
Gain(A)被认为是根据属性A取值进行样本集合划分所获得的信息熵的减少量。
ID3算法计算每个属性的信息增益,并从中选择出信息增益最大的属性作为给定集合的测试属性并由此产生相应的分支节点。所产生的节点被标记为相应的属性,并根据这一属性的不同取值分别产生相应决策树分支,每个分支代表一个被划分的样本子集。
ID3,学习能力较强,,且对噪声比较,。
ID3算法的优点,同时对I。如它能够完成对连续属性
I(s1,s2,……,sm)=-
∑plog
i
i=1
2
(pi)
其中pi是任意一个数据对象属于类别Ci的概
率,可以按si/s计算。因为信息用二进制编码,所以对数函数以2为底。
设一个属性A可取v个不同的值{a1,a2,……,av}。可以用属性A将S划分为v个子集{S1,S2,……,Sv},其中Sj包含了集合S中属性A取aj值的数据样本。若属性A设sij为子集Sj中属于Ci属性A以计算如下: E(A)=i=1v
的离散化处理,能够对不完整数据进行处理等。
s1j+s2j+mj
ss
2 决策树分类算法在实际中的应用
I(s1j,s2j,……,smj)
其中项
s1j+s2j+……+smj
被称为第j个子集的权
现有一样本数据集,描述的是某地早晨关于气象的类型,数据集如表1。该样本数据集的类别有两类N和P。
值。E(A)的值越小,表示子集划分结果越好。而
表1 样本数据集序号
1234567891011121314
天气晴晴多云雨雨雨多云晴晴雨晴多云多云雨
气候热热热适中冷冷冷适中冷适中适中适中热适中
湿度高高高高正常正常正常高正常正常正常高正常高
风无风有风无风无风无风有风有风无风无风无风有风有风无风有风
类别
NNPPPNPNPPPPPN
?4? 2 盐城工学院学报(自然科学版)第18卷
下面利用决策树的基本算法来构造决策树,产生判定规则。
样本数据集中有两个不同的类别,即m=2。设C1对应于P类别,共有9个样本;C2对应于N类别,共有5个样本。
为计算每个属性的信息增益,根据公式计算出对一个给定样本进行分类所需要的期望信息:
I(s1,s2)=I(9,5)=-log2-log2=0.9414141414
对于属性“天气”,有:{晴,多云,雨}
取值为“晴天”的样本中有2个属于P类,3个属于N类,即
s11=2 s21=3 I(s11,s21)=I(2,3)=0.971取值为“多云”的有
s12=4 s22=0 I(s12,s22)=I(4,0)=0取值为“雨”的有
s13=3 s23=2 I(s13,s23)=I(3,2)=0.971
大,因此被作为决策树的树根,在样本中对属性“天气”的3个取值进行分支,3个分支对应3个
子集,分别是:
F1={1,2,8,9,11},F2={3,7,12,13},F3={4,5,6,10,14}
其中F2中的样本都为P类,因此对应分支标记为P,其余两个子集既有P类又含有N类,这是需对F1和F3子集分别递归调用决策树算法。
在F1中可求出余下的三个属性:气候、湿度、风中,湿度的信息增益最大,以它为该分支的节点,再向下分支,湿度取“高”的全部为N类,该分支标记为N,湿度取“正常”的全部为P类,该分支标记为P。
在F3中可求出属性“风”的信息增益最大,以它为该分支的节点,再向下分支,风取“有风”的全部为N类,N,风取“无风”的全部为P,,),则属于P类。
最后计算出根据属性“天气”对样本集合进行划分而需要的期望信息:
E(天气)I(s11,s21)I(s12,s22)I(s13,s23)=0.694
141414由此获得利用属性“天气”划分所获得的信息增益为:
Gain=(天气)s12-()0.245 类似可得:
Gain(气温)=0.029
Gain=(湿度)=0.151Gain=(风)=0.048
决策树分类算法被广泛应用到许多进行分类识别的应用领域,尤其是在数据挖掘方面,是一种知识获取的有用工具。由于分类的效果一般和数据的特点有关,目前还不存在能适合各种不同数据的分类方法,因此分类算法有待进一步研究。
显然选择属性“天气”所获得的信息增益最参考文献:
[1]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002.[2]范明.数据挖掘概念与技术[M].北京:机械工业出版社,2001.
ResearchintotheDecisionTreeClassificationAlgorithmsrule
SHENChen-ming
(DepartmentofComputerEngineering,NanjingInstituteofEngineering,JiangsuNanjing 210013,China)
Abstract:Thedecisiontreeclassificationalgoriellmisainductivelearningmethodcolichisbasedonthedatasetsindata-scoo2pingresearch.Themethoolfocusesondeducingtheclassificationrulesintheformofdecisiontreefromagroupofrandom,irregu2larsampledatasets,anddrawingthedatamodelwhichcandescuibethesampledatasets.Thebasicprinciplesofthemethodarealsodiscassedtopointoutitsclcaracteristics,inwhichtherealusageisillustrctedbyanexanple.Keywords:decisiontree;data-scooping;informationgain
范文四:决策树分类算法介绍
【摘要】分类挖掘是数据挖掘中最重要的技术之一,是数据挖掘中的一个重要课题,而分类技术中的决策树方法又是重点研究的方向。本文就几种常用的决策树算法进行介绍,比较分析。
【关键词】决策树 信息增益 剪枝
一、决策树
三、树剪枝
当决策树创建时,由于数据中的噪声和离群点,许多分枝反映的是训练数据中的异常。同时对最终的决策树来说,在建立过程中让其生长的枝繁叶茂是没有必要的,这样既降低了树的可理解性和可用性,同时也使决策树对历史数据的依赖性增大,也就是说,这棵树对当前的样例数据可能非常准确,一旦用到新的数据时准确性急剧下降,称这种情况为训练过度。为了使得到的决策树所蕴涵的规则具有普遍意义,必须防止训练过度,这样也减少了训练时间,因此必须对决策树进行剪枝。剪枝是一种克服噪声的基本技术,同时它也能使决策树得到简化而变得更容易理解。
剪枝有两种常用的方法:先剪枝和后剪枝。先剪枝通过提前停止树的构造而对树剪枝。常用诸如统计显著性、信息增益、Gini指标等度量评估分裂的优劣。如果划分一个节点的元祖导致低于预定义阀值的分裂,则给定子集的进一步划分将停止。后剪枝由完全生长的树剪去子树,通过删除节点的分枝并用树叶替换它而剪掉给定节点的子树。树叶用被替换的子树中最频繁的类标记。
四、结束语
C4.5 针对ID3算法的不足进行改进。其思想简单,结果可靠。但其本身也存在达不到全局最优的结果、评价决策树主要依据错误率等不足。CART算法计算量相对来说不是很大,并且可以处理连续和种类字段,结果清晰的显示哪些字段比较重要。但当类别太多时,错误增加较快。通过分析,每种算法各有优势和适用范围,因此需要根据特定问题和特定的数据选择适合的算法。
范文五:决策树分类算法 数据挖掘
本科毕业论文(设计) (题目:决策树分类算法在教学分析中的应用 )
姓 名:
学 号: 1142151204
专 业:计算机科学与技术
院 系:信息工程学院
指导老师:袁张露
职称学历:助教 /研究生
完成时间:
教务处制
安徽新华学院本科毕业论文(设计)独创承诺书
本人按照毕业论文(设计)进度计划积极开展实验(调查)研究活动,实事求是地做好 实验(调查)记录,所呈交的毕业论文(设计)是我个人在导师指导下进行的研究工作及取 得的研究成果。据我所知,除文中特别加以标注引用参考文献资料外,论文(设计)中所有 数据均为自己研究成果, 不包含其他人已经发表或撰写过的研究成果。 与我一同工作的同志 对本研究所做的工作已在论文中作了明确说明并表示谢意。
毕业论文(设计)作者签名:
日 期 :
决策树分类算法在教学分析中的应用
摘 要
随着信息科技的高速发展,人们对于积累的海量数据量的处理工作也日 益增重,需求是发明之母,数据挖掘技术就是为了顺应这种需求而发展起来 的一种数据处理技术。
数据挖掘技术又称数据库中的知识发现,是从一个大规模的数据库的数 据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。在学生 管理以及教学科学化的今天, 传统的教学分析已经不能适应社会发展的需求。 学生信息数据不断的增多,教学分析工作也日益加重。学生信息数据量 不断的增多, 对之前所累计的大量学生考试成绩数据运用数据挖掘技术进行 分析挖掘是具有重大的意义的, 这样可以把所挖掘分析出来的信息反馈用于 指导学校的教学分析,从而提高学生的学习成绩。
本文通过学生成绩信息运用数据挖掘技术,对所采集的数据进行预处理, 运用决策树分类算法中的 C4.5算法对成绩进行分析得到了成绩分析决策树, 分析研究出有用的信息找到影响学生的因素,发现某些规律的存在,用以指 导学校教学分析工作的开展。
关键词 :数据挖掘;学生成绩;决策树
Application of decision tree in computer grade examination analysis
Abstract
With the rapid development of Information Technology, people are facing much more work load in dealing with the accumulated mass data. However, Data Mining Technique is a kind of data processing technique that follows this change. In recent years, colleges and other institutions of higher education had increased their enrollments, more and more students got enrolled and consequently, the students ’ information data pool gets much bigger. However, the traditional data processing technology can’ t accommodate itself to study and analyze the accumulated mass data at a deeper level any more, while Data Mining Technique can solve these problems much better.
The increasing data base of the students concludes much, like students’ test score. With the rapid development of computer technology, Computer Rank Examination becomes more and more popular; hence, the data base of students’ test score becomes much bigger. So, to use Data Mining Technique to mine the accumulated mass CRE score is of great meaning with regarding to the improvement of the students’ score on CRE, since people can apply the results of data mining in school computer teaching research.
This paper intends to show the use of Data Mining Technique in the analysis of students ’ score information in Computer Rank Examination, from the pretreatment on the collected data to the use of decision tree technique in data analysis. This employs ID3 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 CRE score and the rules in these influences to instruct school teaching work.
Keywords :Data mining; computer examination; decision tree; SqlServer2008
目 录
1 绪 论 ................................................ 1 1.1研究背景与意义 ....................................... 1 1.2数据挖掘的产生 ...................... 错误!未定义书签。 1.3数据挖掘的国内外研究现状 . ............................. 1
1.4论文研究内容及结构安排 . ............................... 2
2 数据挖掘技术 ........................................... 3 2.1数据挖掘的概念 ....................................... 3 2.1.1 数据挖掘的定义 ..................................... 4 2.2 数据挖掘的过程 ....................................... 4 2.2.1 数据对象确立阶段 ................................... 4 2.2.2数据预处理阶段 ...................................... 5 2.2.2数据挖掘阶段 ...................... 错误!未定义书签。 2.2.3结果的解释和评估阶段 . .............. 错误!未定义书签。 2.3数据挖掘的主要方法 . ................................... 6 2.4数据挖掘的功能 ....................................... 8 2.5数据挖掘的系统结构 . .................. 错误!未定义书签。 2.6数据挖掘应用的成功案例 . .............................. 10
2.7本章小结 ............................................ 12
3 决策树技术 ............................................ 12 3.1决策树简介 .......................................... 12
3.2决策树的主要算法 ..................................... 13 3.2.1 ID3算法 .......................................... 13 3.2.2 C4.5算法 ......................................... 15 3.3决策树剪枝 .......................................... 18 3.3.1决策树剪枝的方法 . .................................. 19
3.4本章小结 ............................................ 20
4 决策树在计算机等级考试成绩分析中的应用 ................ 21 4.1成绩分析方法的依据 . .................................. 21 4.2 决策树算法在计算机等级考试成绩分析中的应用 .......... 22 4.2.1 确定对象集目标 .................................... 22 4.2.2 数据的采集 ........................................ 22 4.2.3 数据预处理 ........................................ 24 4.2.4 数据挖掘工作的展开 ................................ 24
4.2.5结果分析 .......................................... 28
5总结与展望 ............................................ 29 5.1研究结果 ............................................ 29 5.2后续研究与展望 ...................................... 30 参考文献 ................................................ 32
1 绪 论
1.1研究背景与意义
无论在企业应用领域, 还是在科学领域, 数据挖掘技术有着广泛的应用价值。 在企业应用领域,用于制定好的市场策略以及企业的关键性决策。在商业方面, 数据挖掘技术可以增强企业的竞争优势, 缩短销售周期, 降低生产成本, 有助于 制定市场计划和销售策略,并已经成为电子商务中的关键技术。
近年来,随着我国高等教育的飞速发展,高校的教学管理信息不断增多。教 学工作信息化有了很大的进步, 好多高校在管理学生和教师信息方面有了很好的 方式。 比如我校的教务系统, 这些系统为老师和学生提供了很好的帮助。 这些系 统中积累了大量的数据。 目前的这些数据库系统虽然基本上都可以实现数据的录 入、修改、统计、查询等功能,但是这些数据所隐藏的价值并没有被充分的挖掘 和利用,信息资源的浪费还是比较严重的。
随着数据挖掘技术的不断扩展,许多高校为了避免信息浪费,已经将数据挖 掘技术应用于高校的教学分析中。 数据挖掘技术的应用将对提高学生成绩和提高 教学水平起到很好的指导作用。
为了提高教学质量, 将数据挖掘技术引入到高校学生成绩分析中, 对这些数 据进行深入的挖掘和合理的分析, 从而挖掘出传统的分析方法所无法得出的结论。 进而利用分析结果引导教学的开展,从而有利于提高教学质量。
本文主要是基于如下背景开展的:以安徽新华学院历届学生成绩为背景, 首 先学习数据挖掘的理论知识以及决策树技术, 然后建立新华学院学生成绩数据库, 并利用数据挖掘技术中的决策树对自己建立的数据库进行深入的挖掘。 最后对自 己的挖掘结果进行分析, 得到影响学生成绩的因素。 从而更好的辅助今后学校的 教学分析工作。
1.2数据挖掘的国内外研究现状
1989年 8月在美国召开的第十一届国际人工智能联合会议的专题讨论会
上,与数据挖掘(Date Mining)极为相似的术语——从数据库中发现知识一词 被提出。 1993年以后,美国计算机协会美年都举行了专门研究探讨数据挖掘技 术的会议, 会议的规模也发展成为国际学术大会, 并且在各个领域里取得了很多 研究成果。最近, Gartner Group 的一次高级技术调查将数据挖掘和人工智能列 为“未来三到五年内将对工业产生深远影响的五大关键技术”之首, 并且还将并 行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。 [1]根据 最近 Gartner 的 HPC 研究表明,“随着数据捕获、传输和存储技术的快速发展, 大型系统用户将更多地需要采用新技术来挖掘市场以外的价值, 采用更为广阔的 并行处理系统来创建新的商业增长点。”
国外研究数据挖掘的组织、 机构或大学很多。 比较著名的如卡内基梅隆大学、 斯坦福大学、麻省理工学院。著名的研究机构如:ACM 、 KDNet 、 NCDM 等。 国外比较著名的挖掘工具:IBM 公司的 Intelligent Miner 、 SAS 公司的 Enterprise Miner 、 SGI 公司的 SetMiner 、 SPSS 公司的 Clementine 、 Oracle Darwin等。不少 的软件在国外得到了广泛的应用,并收到了明显的效益。
与国外相比,国内对 DMKD 的研究稍晚,没有形成整体力量。 1993年国家 自然科学基金首次支持我们对该领域的研究项目。 目前, 国内的许多科研单位和 高等院校竞相开展知识发现的基础理论及其应用研究,这些单位包括清华大学、 中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中,北京系 统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究, 北京大学也 在开展对数据立方体代数的研究,华中理工大学、复旦大学、浙江大学、中国科 技大学、 中科院数学研究所、 吉林大学等单位开展了对关联规则开采算法的优化 和改造; 南京大学、 四川联合大学和上海交通大学等单位探讨、 研究了非结构化 数据的知识发现以及 Web 数据挖掘。
1.3论文研究内容及结构安排
本课题的主要工作是将数据挖掘技术和学校的信息管理系统相结合, 新华学院多 年来的信息化教学管理工作积累了大量的教学数据, 从新华学院的数据库中收集 学生的考试成绩信息。 利用数据挖掘技术对这些数据进行分析, 获得影响学生成 绩的因素,更好的辅助学校如何提高学生成绩以及提高教学质量。
本课题根据指导老师提供的 11级学生成绩的信息, 建立安徽新华学院 11级 学生成绩库, 采用数据挖掘技术对成绩库进行挖掘。 通过对实验结果进行深入分 析, 获得影响学生考试成绩的因素, 辅助教师在以后的教学工作中采用更恰当的 教学方式,指导学生应该具有什么样的学习态度,从而提高学生考试成绩。 论文结构如下:
第一章 绪论。 主要介绍了论文的研究背景与意义,叙述了国内外数据挖 掘技术的研究现状。
第二章 数据挖掘的基础知识。 主要叙述了数据挖掘的定义、 数据挖掘的 过程以及数据挖掘的方法。
第三章 决策树。 主要简要介绍了决策树以及决策树的经典算法。
第四章 决策树在计算机等级考试成绩分析中的应用
第五章 总结与展望。 总结本篇论文并展望今后论文的继续研究方向内容方 向。
2 数据挖掘技术
2.1数据挖掘的概念
2.1.1数据挖掘的背景
随着信息技术的高速发展, 人们积累的数据量急剧增长, 如何从海量的数据中提 取有用的知识成为当务之急。 数据库技术的成熟以及数据应用的普及, 虽然目前 的数据库系统可以高效的实现数据的录入、 查询、 统计的功能, 但无法发现数据 中潜在的信息和价值, 无法利用这些数据来预测未来的发展趋势。 于是, 新的问 题就被提出来了:人类如何在这浩瀚的数据中及时发现有用的知识, 提高数据的 利用率呢?在不懈的努力下,从数据库中发现知识(Knowledge Discovery in
Datebases )及其核心技术——数据挖掘(Date Mining )便应运而生,并得以蓬 勃的发展,越来越显出其强大的生命力。
2.1.1 数据挖掘的定义
数据挖掘 (Data Mining) ,又译为资料探勘、数据采矿。它是数据库中的知 识发现 (Knowledge Discovery in Datebases,简称:KDD) ,是目前人工智能和数据 库领域研究的热点问题, 数据挖掘一般是指从大量的数据中通过算法搜索隐藏于 其中信息的过程。所谓数据挖掘是指从大量的、不完全的、有噪声的、模糊的、 随机的数据中自动搜索隐藏于其中的有着特殊关系的信息,提取隐含在其中的, 人们事先不知道的、但又是潜在有用的信息和知识的过程 [5]。
2.2 数据挖掘的过程
数据挖掘 (Data Mining)的过程可以分为以下几个部分:理解数据和数据的来 源(understanding )、 获取相关知识与技术(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) 。
图 2.1 数据挖掘的过程
2.2.1 数据对象的确立
明确我们研究问题所需要的数据, 理解数据并提出问题, 需要进行数据挖掘的数 据信息, 明确数据挖掘的目标的定义。 确定数据挖掘目标是数据挖掘重要的一步。 我们进行数据挖掘时, 挖掘的结果往往是不可预测的, 但对要进行挖掘的目标是 可预见的,即明确数据挖掘的最终目标 [7]。
数据对象的确立,包括对大量数据的选取、数据属性的确定等。本文是安
徽新华学院学生成绩的数据挖掘技术应用, 这些数据包含新华学院历届的学生考 试成绩数据,数据属性包括学生姓名、性别。年龄、专业、成绩等。
2.2.2数据预处理阶段
现实世界中数据大体上都是不完整的、 含有噪声的、 甚至不一致的脏数据, 我们 无法直接对其进行数据挖掘, 或者挖掘结果会差强人意。 为了提高数据挖掘的质 量,人们提出了数据预处理技术 [7]。
数据预处理是数据挖掘过程中的一个很重要的步骤, 数据预处理有很多种方 法,一般将数据预处理又分为四个步骤:数据清洗、数据集成、数据变换、数据 归约。
数据清洗处理过程通常包括:填补遗漏的数据值、 光滑有噪声数据、 识别或 删除异常值、以及解决不一致问题。
数据集成就是将多个数据源的数据合并到一起并统一存储, 建立数据仓库的 过程实际上就是数据集成。在数据集成时要特别注意消除数据的冗余。
数据变换主要是对数据进行规格化操作, 将数据转换成适用于数据挖掘的形 式。
数据挖掘时对应的数据量往往是非常大的, 数据归约是缩小所挖掘数据的规 模,但保持数据的完整性。
2.2.3数据挖掘阶段
数据挖掘阶段是数据挖掘的核心步骤, 也是技术难点所在。 而数据挖掘阶段 的核心就是模式的发现 [13]。
此阶段主要是确定对数据进行分类还是聚类, 确定数据的关联规则等等。 然 后确定用什么数据挖掘算法对数据进行挖掘, 再利用数据挖掘的工具和一系列方 法对之前所确定以及转换后的数据进行分析、 产生一个特定的有意义的模式以更 好的对已处理好的数据进行分析,获取有用信息。
2.2.4结果的解释和评估阶段
数据挖掘阶段会产生的模式或数据集经过评估存在冗余或多余的模式, 这时
需要将其剔除,过滤出有用的知识。过滤后用于呈现给用户;一般情况下,为了 方便用户理解产生的模式, 处理员应该利用可视化技术将数据挖掘产生的有意义 模式以图形或者其他可视化的形式表示, 让用户更容易理解。 例如把分类决策树 转换为“ if — then ”的形式。
如果数据挖掘过程中的发现的知识不能满足用户的需求, 我们则需要重新对 数据进行处理, 选择一些其他的数据挖掘方法、 算法对数据进行再次挖掘, 并分 析结果,直到满足用户的需求。
2.3数据挖掘的主要方法
(1)关联规则
在数据挖掘的知识模式中, 关联规则模式是比较重要的一种。 关联规则的概 念由 Agrawal 、 Imielinski 、 Swami 提出,是数据中一种简单但很实用的规则。关 联规则模式属于描述型模式, 发现关联规则的算法属于无监督学习的方法。 关联 规则是描述了数据库中数据项之间所存在的关系的规则, 即根据一个事务中某些 项的出现可导出另一些项在同一事务中也出现, 即隐藏在数据间的关联或相互关 系。
(2)决策树
所谓决策树,顾名思义,是一种树,一种依托于策略抉择而建立起来的树。 一种用树枝状展现数据受各变量的影响情况的分析预测模型, 根据对目标变 量产生效应的不同而制定分类规则, 它是建立在信息论基础之上, 对数据进行分 类的一种方法。 它首先通过一批已知的训练数据建立一棵决策树, 然后采用建好 的决策树对数据进行预测。 决策树的建立过程是数据规则的生成过程, 因此这种 方法实现了数据规则的可视化,其输出结果容易理解,精确度较好,效率较高, 因而较常用。常用的方法有分类及回归树法、卡方自动交互探测法等。
决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。 树中每个节点表示某个对象, 而每个分叉路径则代表的某个可能的属性值, 而每 个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。 决策树仅 有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。
决策树算法是一种逼近离散函数值的方法。 它是一种典型的分类方法, 首先对数 据进行处理, 利用归纳算法生成可读的规则和决策树, 然后使用决策对新数据进 行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
(3)神经网络
一种模仿人脑思考结构的数据分析模式,由输入变量或数值中自我学习并根 据学习经验所得的知识不断调整参数, 以期得到资料的模式。 是建立在自学习的 数学模型基础之上, 它可以对大量复杂的数据进行分析, 并能完成对人脑或计算 机来说极为复杂的模式抽取及趋势分析。 神经网络的处理过程主要是通过网络的 学习功能找到一个恰当的连接加权值来得到最佳结果。 比较典型的学习方法是回 溯法。 通过将输出结果同一些已知值进行一系列比较, 加权值不断调整, 得到一 个新的输出值,再经过不断的学习过程,最后该神经网络得到一个稳定的结果。 (4)相关规则
是一种简单而实用的关联分析规则, 它描述一个事物中某些属性同时出现的 规律和模式,由一连串的“如果 —— 则”的逻辑规则对资料进行细分的技术。关 联规则一般应用在事物数据库中, 其中每个事物都由一个记录集合组成。 这种事 物数据库通常都包括极为庞大的数据, 因此当前的关联规则发现技巧正努力根据 基于一定考虑的记录支持度来削减搜索空间。 其中的支持度是一种基于用户事物 在事物日志中出现的数目的度量。
(5)遗传算法
一种新的最佳化空间搜索方法,它应用算法的适应函数来决定搜索的方向, 运用一些拟生物化的人工运算过程进行一代一代的周而复始的演化, 求得一个最 佳结果。 特点是具有强固形与求值空间的独立性。 强固形使问题的限制条件降到 最低, 并大幅度提高系统的容错能力; 而求值空间的独立性则使遗传算法的设计 单一化,且适用于多种不同性质、领域的问题。将遗传算法运用于数据挖掘,可 以开采出与众不同的信息,是别的算法所不能替代的。
(6)连机分析处理
简称 OLAP , 是基于大型数据库或数据仓库的信息分析过程, 是大型数据库 或数据仓库的用户接口部分, 其目的是满足决策支持或多维环境特定的查询和报 表要求。
OLAP 具有快速性、可分析性、多维性、信息性和共享性等特点,它是跨部
门、面向主题的。 OLAP 不同于传统的连机事物处理的应用。 OLAP 主要是用来 完成客户的事务处理, 如民航、 车船的订票系统等, 通常要进行大量的更新操作, 对响应时间要求也比较高。而 OLAP 主要是对用户当前及历史数据进行分析, 辅助决策。 其典型的应用有对银行信用卡风险的分析与预测等, 主要是进行大量 的查询操作,对时间的要求不太严格。
(7)粗糙集
粗糙集算法将知识理解为对数据的划分, 每一被划分的集合称为概念, 主要 思想是利用已知的知识库, 将不精确或不确定的知识用已知的知识库中的知识来 近似刻划处理粗糙集理论, 是继概率论、 模糊集、 证据理论之后的又一个处理不 确定性的数学工具。 作为一种较新的软计算方法, 粗糙集近年来越来越受到重视, 其有效性已在许多科学与工程领域的成功应用中得到证实, 是当前国际上人工智 能理论及其应用领域中的研究热点之一。 在很多实际系统中均不同程度地存在着 不确定性因素,采集到的数据常常包含着噪声,不精确甚至不完整。
它将知识理解为对数据的划分, 每一被划分的集合称为概念, 主要思想是利 用已知的知识库, 将不精确或不确定的知识用已知的知识库中的知识来近视刻划 处理。
2.4数据挖掘的功能
数据挖掘的功能是从大型数据集中提取人们感兴趣的知识, 这些知识是隐含 的、 具有一定可信度的、 对用户而言是新颖的且有潜在价值的知识, 提取的知识 表示为概念、规则、模式等多种形式。
一般情况下, 数据挖掘的任务可以大体分为两类:描述和预测。 描述性挖掘 任务描述数据库中数据的一般性质, 而预测性挖掘任务是指对当前数据进行处理、 分析和推断,以做出相应的预测。
数据挖掘在实际的工作中, 有时候用户并不清楚自己需要什么样的数据, 因 此数据挖掘工作有必要挖掘出多种类型的模式, 以达到满足不同的用户需求和应 用。
一般情况下,数据挖掘的功能以及可能发现的模式类型如下:
(1)分类
目的是构造一个分类函数或分类模型(也常常称作分类器),该模型能把数
据库中的数据项映射到给定类别中的某一个。 要构造分类器, 需要有一个训练样 本数据集作为输入。 训练集由一组数据库记录或元组构成, 每个元组是一个由有 关字段(又称属性或特征)值组成的特征向量,此外,训练样本还有一个类别标 记。一个具体样本的形式可表示为:(v1, v2,?, vn ; c ),其中 vi 表示字段 值, c 表示类别。
例如:银行部门根据以前的数据将客户分成了不同的类别, 现在就可以根据 这些来区分新申请贷款的客户,以采取相应的贷款方案。
(2)关联分析
关联分析就是从大量的数据中发现项集之间有趣的关联或因果结构。
关联分析展示了属性与值频繁的在给定的数据集中的一起出现的条件。 一般 如下形式:
如 X ?Y , 即 “ |A1∧..........An ?B1∧…… .B n ” 的 规 则 。 其 中 , Ai ∈(i{1,… ..m}) ,Bj∈(j{1,… ..n})是属性—值对。关联规则 X ?Y 即表示::“满足 X 中条件的数据库元组多半也满足 Y 中的条件”。
简而言之, 就是分析两个事物之间的一些特性, 通过一个事物去预测另外一 个事物,这就是关联分析。
(3)概念 /类描述
概念描述 (concept description ) 就是通过对与某类对象关联数据的汇总、 分析和比较,对此类对象的内涵进行描述,并概括这类对象的有关特征。
这种描述是汇总的、简洁的和精确的知识。
(4)聚类分析
聚类分析就是将物理或抽象对象的集合分组成由类似的对象组成的多个类的过 程。
聚类是把整个数据库分成不同的群组。它的目的是使群与群之间差别很明 显, 而同一个群之间的数据尽量相似。 这种方法通常用于客户细分。 在开始细分 之前不知道要把用户分成几类, 因此通过聚类分析可以找出客户特性相似的群体, 如客户消费特性相似或年龄特性相似等。 在此基础上可以制定一些针对不同客户 群体的营销方案。
对象根据最大化类内部的相似性、 最小化类之间的相似性的原则进行聚类或
分组。也就是说,对象的簇(cluster )这样形成,使得相比之下在一个簇中的对 象具有很高的相似性, 而与其他簇中的对象很不相似。 所形成的每个簇可以看作 一个对象类,由它可以导出规则。聚类也便于分类法组织形式(taxonomy formation ),将观测组织成类分层结构,把类似的事件组织在一起。
通过聚类,人们能够认识到密集和稀疏的区域,因而发现全局的分类模式, 以及数据属性之前的相互关系。
(5)离群点分析
数据库中可能包含一些数据对象, 它们与数据的一般行为或模型不一致。 这 些数据对象是离群点(outlier )。大部分数据挖掘方法将离群点视为噪声或异常 而丢弃。然而,在一些应用中(如欺骗检测),罕见的事件可能比正常出现的事 件更令人感兴趣。离群点数据分析称作离群点挖掘(outlier mining)。
可以假定一个数据分布或概率模型, 使用统计检验检测离群点; 或者使用距 离度量, 将远离任何簇的对象视为离群点。 基于偏差的方法通过考察一群对象主 要特征上的差别来识别离群点,而不是使用统计或距离度量。
(6) 演变分析
数据演变分析(evolution analysis )描述行为随时间变化的对象的规律或趋势, 并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联和相关分析、 分类、 预测或聚类, 这类分析的不同特点包括时间序列数据分析、 序列或周期模 式匹配和基于相似性的数据分析。
2.5数据挖掘应用的成功案例
(1)、中国宝钢集团(直接数据挖掘,分类分析方法)
宝钢自 1985年投产至今, 积累了大量的生产数据, 从每一炉钢到每一块板 坯到每一个钢圈, 各级计算机系统可以把这些数据完整地收集起来。 采用数据挖 掘技术对钢材生产的全流程进行质量监控和分析 (通过全流程实时监控获得了丰 富的生产数据),构建故障地图,实时分析产品出现瑕疵的原因,有效提高了产 品的优良率。
宝钢采用了两个数据挖掘工具,一个是自行研发的基于 SAS 的 practical Miner ,另一个是美国 SAS 公司的 Enterprise Miner 。在冷轧和热轧的产品质量
控制中, 仅 2001年就取得超过 3000万元的经济效益。 在配矿优化项目中, 通过 确定不同铁矿石的合理比例,每年可为宝钢降低成本 6000万元。另外,通过分 析轧制计划, 分析和优化库存结构, 降低库存成本和平衡物流成本 Credilogros Cía Financiera S.A. 是阿根廷第五大信贷公司,资产估计价值为 9570万美元,对 于 Credilogros 而言,重要的是识别与潜在预先付款客户相关的潜在风险,以便 将承担的风险最小化。
(2)、沃尔玛超市里的尿布与啤酒(间接数据挖掘,关联规则)
大家都应该了解这个事件,数据挖掘中的经典成功案例。
在一家超市里, 有一个有趣的现象:尿布和啤酒赫然摆在一起出售。 但是这个 奇怪的举措却使尿布和啤酒的销量双双增加了。 沃尔玛拥有世界上最大的数据仓 库系统, 为了能够准确了解顾客在其门店的购买习惯, 沃尔玛对其顾客的购物行 为进行购物篮分析, 想知道顾客经常一起购买的商品有哪些。 沃尔玛数据仓库里 集中了其各门店的详细原始交易数据。 在这些原始交易数据的基础上, 沃尔玛利 用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是:
(3)、股票预测
股票市场是一个具有大量相互作用因素的复杂系统,它受政治形势、金融政 策、 公司状况和重大消息等多方面因素的影响。 股票价格一般要受一国货币、 财 政政策、物价、利率、汇率、上市公司重大事项、国际经济环境、投资者心理等 信息的作用,其内部规律非常复杂,变化周期无序,更使行情的走势变化莫测。 利用决策树分类算法中的 ID3算法并适当调整以对股票交易数据样本集进 行测试分析, 由此生成决策树作为分类器并对其结果进行了检验, 最后根据决策 树分类规则开发出一淘股票分析预测系统。
更早之前, 通过相关分析, 可以找出一支股票与另一支股票走势的潜在规律, 比如数据挖掘曾经得到过这个结论 “如果微软的股票下跌 4%, 那么 IBM 的股票
将在两周内下跌 5%”
2.7本章小结
本章在介绍数据挖掘基本概念的基础上, 简要的概括了数据挖掘的过程、 数 据挖掘的方法、数据挖掘的功能,并简要介绍了几个数据挖掘应用的成功案例。 这些基本理论知识为数据挖掘的实践应用研究奠定了理论基础。
3 决策树技术
3.1决策树简介
随着社会的发展, 数据挖掘显的尤为的重要。 在数据挖掘中决策树算法是目 前数据挖掘领域中应用的最广泛、 最流行的推理算法之一。 决策树分类算法是将 数据分类、预测和规格的提取。随着 ID3算法和 C4.5算法的提出,决策树技术 在数据挖掘领域得到了进一步的拓展,并且在人们生产生活中得到了广泛应用。 决策树是一种根据自变量的值进行递归划分以及预测因变量的方法。 决策树的主 要作用是揭示数据中的结构化信息。 它提供一种在什么条件下会得到什么值的类 似规则的方法。 若因变量为分类变量, 我们称相应的决策树为分类树; 若因变量 为连续变量, 我们称相应的决策树为回归树。 分类树对离散变量做决策树, 回归 树对连续变量做决策树。一般的数据挖掘工具,允许选择分裂条件和修剪规则, 以及控制参数(最小结点的大小,最大树的深度等等),来限制决策树的。决策 树作为一棵树, 树的根节点是整个数据集合空间, 每个分节点是对一个单一变量 的测试, 该测试将数据集合空间分割成两个或更多块。 每个叶节点是属于一类别 的记录。图 3.1为以典型的决策树。
图 3.1 决策树
3.2决策树的主要算法
近年来, 决策树方法在很多机器学习、 知识的探究等过程中得到了广泛的应
用。 迄今为止, 国内外研究人员先后提出了十几种决策树的分类方法, 因此决策
树的算法还是挺多的, 本文介绍了两种比较经典的决策树算法, 分别是 ID3算法
和 C4.5算法。
3.2.1 ID3算法
ID3(induction decision-tree) 算法,它是一种用来由数据构造决策树的递归过程,
是在 1986年由 Quinlan 首先提出的,该算法以信息论为基础,信息论是数学中
的概率论和数理统计的一个分支, 用于处理信息和信息熵、 通信系统、 数据传输
和率失真理论、密码学、信噪比、数据压缩和相关课题。以信息熵和信息增益度
为衡量标准,从而 实 现数据 的 归纳分 类 ,它是一 个从上 到下、分而 治之 的归纳过程。
ID3
算法的大概过程是:我们试探性的选择一个属性放置在根节点,并对该
属性的每个值产生一个分支。这样,分裂根节点上的数据集,并一道子女节点, 产生一个局部的树。 在决策树各级结点上选择属性时, 通过计算信息增益来选择 属性, 以使得在每一个非叶结点进行测试时, 能获得关于被测试记录的最大的类 别信息。 其具体方法是:我们需要检测所有的属性, 在它们中间选择信息增益最 大的属性作为决策树结点, 由该属性的不同取值建立分支, 再对各分支的子集递 归调用该方法建立决策树结点的分支, 直到所有的子集仅包含同一类别的数据为 止。最后得到的一棵决策树,它可以用来对新的样本进行分类。
要想了解 ID3算法,我们要了解 ID3算法中的一些基本概念:
(1)熵
熵是一个物理名词, 源于热力学的概念, 数值为温度除热量所得的值。 1948年 Shannon 提出并发展了信息论并引入了信息熵。
一个训练集合 S 根据类别属性的值被分成 m 个互相独立的类 C 1、 C 2、 .. 、 C n ,则识别 D 的一个元组所属哪个类所需的信息量为 Info (S )。设 C i , d 是 S 中 C i 类的元组的集合, C n 的概率分布, P={P 1, … P n },任意元组属于分类 C i 的概 率为 P i ,则由该分布传递的信息量称为 S 的熵,记为:
Info (S ) = -1n
i =∑P i log 2(P i )=-P ○
+log2 P○ +-P ○ -log2 P○ - 上述公式中, p+代表正样例,而 p-则代表反样例。
(2)信息增益度
信息增益度是两个信息量之间的差值, 已经有了熵作为衡量训练样例集合 纯度的标准, 现在可以定义属性分类训练数据的效力的度量标准。 这个标准被称 为 “ 信息增益(information gain)”。简单的说,一个属性的信息增益就是由于 使用这个属性分割样例而导致的期望熵降低 (或者说,样本按照某属性划分时造 成熵减少的期望 ) 。 更精确地讲, 一个属性 A 相对样例集合 S 的信息增益 Gain(S,A)被定义为:
G (S,A ) =Info(D ) -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)创建节点 N ;
(2)如果训练集为空,在返回节点 N 标记为 Failure ;
(3)如果训练集中的所有记录都属于同一个类别,则以该类别标记节点 N ;
(4)如果候选属性为空,则返回 N 作为叶节点,标记为训练集中最普通的类;
(5) for each 候选属性 attribute_list;
(6) if 候选属性是连续的 then ;
(7)对该属性进行离散化;
(8)选择候选属性 attribute_list中具有最高信息增益的属性 D ;
(9)标记节点 N 为属性 D ;
(10)for each 属性 D 的一致值 d ;
(11)由结点 N 长出一个条件为 D=d的分支;
(12)设 s 是训练集中 D=d的训练样本的集合;
(13)if s为空;
(14)加上一个树叶,标记为训练集中最普通的类;
(15)else加上一个有 C4.5(R - {D},C, s )返回的点。
我们以一个典型被引用多很多次的数据训练集 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.694 2: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.911 3: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.789
4: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.246
2:Gain(温度 ) = Info(D) - Info(温度 ) = 0.940 - 0.911 = 0.029
3:Gain(湿度 ) = Info(D) - Info(湿度 ) = 0.940 - 0.789 = 0.151
4: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.57740628285234
2、温度属性
属性温度有 3个取值,其中热有 4个样本、适中有 6个样本、寒冷有 4个样本, 则
H(温 度 ) = - 4/14 * log2(4/14) - 6/14 * log2(6/14) - 4/14 * log2(4/14) = 1.5566567074628228
3、湿度属性
属性湿度有 2个取值,其中高有 7个样本、正常有 7个样本,则
H(HUMIDITY) = - 7/14 * log2(7/14) - 7/14 * log2(7/14) = 1.0
4、风速属性
属性风速有 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.15595221261270145
IGR(温 度 ) = Gain(温 度 ) / H(温 度 ) = 0.029 / 1.5566567074628228 = 0.018629669509642094
IGR(湿 度 ) = Gain(湿 度 ) / H(湿 度 ) = 0.151/1.0 = 0.151
IGR(风 速 ) = Gain(风 速 ) / H(风 速 ) = 0.048/0.9852281360342516 = 0.048719680492692784
根据计算得到的信息增益率进行选择属性集中的属性作为决策树结点, 对该结点 进行分裂。
3.3决策树剪枝
决策树主要是基于 ID3算法实现的决策树生成。 ID3算法的基本思想是贪心 算法, 采用自上而下的分而治之的方法构造决策树。 首先检测训练数据集的所有 特征,选择信息增益最大的特征 A 建立决策树根节点,由该特征的不同取值建 立分枝, 对各分枝的实例子集递归, 用该方法建立树的节点和分枝, 直到某一子 集中的数据都属于同一类别,或者没有特征可以在用于对数据进行分割。 ID3算 法总是选择具有最高信息增益 (或最大熵压缩 ) 的属性作为当前结点的测试属性。 该属性使得结果划分中的样本分类所需的信息量最小, 并反映划分的最小随机性 或 “不纯性” 。 这种信息理论方法使得对一个对象分类所需的期望测试数目达到 最小,并尽量确保一棵简单的 (但不必是最简单的 ) 树来刻画相关的信息。
在 ID3算法中, 计算信息增益时, 由于信息增益存在一个内在偏置, 它偏袒 具有较多值的属性, 太多的属性值把训练样例分割成非常小的空间。 因此, 这个 属性可能会有非常高的信息增益, 而且被选作树的根结点的决策属性, 并形成一 棵深度只为一级但却非常宽的树, 这棵树可以理想地分类训练数据。 但是这个决 策树对于测试数据的分类性能可能会相当差, 因为它过分地完美地分割了训练数 据,不是一个好的分类器。
在 J.Mingers 关于 ID3算法的研究中,通过对五种包含噪音的学习样例的实 验发现,多数情况下过度拟合导致决策树的精度降低了 10%一 25%。过度拟合 不仅影响决策树对未知实例的分类精度, 而且还会导致决策树的规模增大。 一方 面,叶子节点随分割不断增多。在极端的情况下,在一棵完成分割的决策树中, 每个叶子节点中只包含一个实例。此时决策树在学习样例上的分类精度达到 100%,而其叶子节点的数目等于学习样例中实例的数目。但是显然这棵决策树 对任何未见的实例都是毫无意义的。 另一方面, 决策树不断向下生长, 导致树的 深度增加。 因为每一条自根节点到叶子节点的路径都对应一条规则, 所以树的深 度越大, 其对应的规则越长。 作为一种蕴含于学习样例中的知识, 这样一组过长 的规则集合是很难被人理解的。 过度拟合现象的存在, 无论是对决策树的分类精 度, 还是对其规模以及可理解性都产生了不利的影响。 因此对与决策树的剪枝是 非常有必要的。
3.3.1决策树剪枝的方法
一般情况下可以使用如下两类方法来减小决策树的规模 :
(l)在决策树完美分割学习样例之前,停止决策树的生长。这种提早停止树 生长的方法,称为预剪枝方法。
(2)与预剪枝方法尽量避免过度分割的思想不同,一般情况下即使决策树可 能出现过度拟合现象, 算法依然允许其充分生长。 在决策树完全生长之后, 通过 特定标准去掉原决策树中的某些子树。通常称这种方法为后剪枝方法。
(1) 预剪枝方法
预剪枝方法实际上是对决策树停止标准的修改。 在原始的 ID3算法中, 节点 的分割一直到节点中的实例属于同一类别时才停止。对于包含较少实例的节点, 可能被分割为单一实例节点。为了避免这种情况,我们给出一个停止阈值 a 。当 由一个节点分割导致的最大的不纯度下降小于 a 时, 就把该节点看作是一个叶子 节点。在该方法中,阈值 a 的选择对决策树具有很大的影响。当阈值 a 选择过大 时, 节点在不纯度依然很高时就停止分割了。 此时由于生长不足, 导致决策树过 小,分类的错误率过高。假设在一个两类问题中,根节点 Root 一共包含 100个 学习样例,其中正例和负例均为 50。并且使用属性 b 可以将正例与负例完全分
开, 即决策树在学习样例上的分类精度 R(T)=100%。 由信息增益公式可知, 使用 属性 b 分割节点可以得到不纯度下降的最大值 0.5。 如果设 a=0.7, 因为 Gain(Root, a)=0.5<0.7,所以根节点 root="" 不需要分割。="" 此时导致决策树在学习样例上的分类="" 精度下降为="" r(t)="50%。当阈值" a="" 选择过小时,例如="" a="" 近似为="" 0,节点的分割过="" 程近似等同于原始的分割过程。="" 由此可见,="" 预剪枝方法虽然原理简单,="" 但是在实="" 际应用中,="" 阈值="" a="" 的选择存在相当大的主观性。="" 如何精确的给出适当的阈值="" a="" 以="">0.7,所以根节点>
(2)后剪枝方法
决策树是一种树形结构。一棵树是一个或者多个节点的有限集合 T ,使得 ①有一个特别指定的节点,叫做树的根节点 ;
②除根节点以外, 剩余的节点被划分成 m>=0个不相交的集合 Tl , ?, Tm , 而且每一个集合也都是树。树 Tl ,?, Tm 称为这个根节点的子树。根据上述树 的定义, 可以直观地将决策树的后剪枝看作是去掉某些子树中除根节点外所有节 点的过程。 移除子树后, 还需要对新生成的叶子节点赋予一个类别标志, 一般是 叶子节点中所占比例最大的类别标志。
如图 3.2所示,为决策树剪枝的过程。
图 3.2 决策树剪枝过程
3.4本章小结
本章具体介绍了数据挖掘技术中得到广泛应用的决策树方法, 详细的介绍了 决策树中的 ID3算法的具体计算过程。后面简要介绍了 C4.5算法,并介绍了决 策树的剪枝。
4 决策树在学生考试成绩中的应用
经过前三章的详细介绍数据挖掘技术的基本理论知识, 着重的学习决策树的 相关知识。 本章将结合前面三张的内容, 深入探讨决策树分类算法在学生考试成 绩分析中方案, 本章自己介绍了实施的步骤以及过程, 对学生考试成绩进行分析, 找出影响学生的因素, 并且利用数据挖局所产生的隐藏信息指导学校的教学工作, 从而提高学校学生的学生的考试成绩。
4.1成绩分析方法的依据
经过前面的详细介绍, 在数据挖掘分类技术中, 一般有粗糙集、 K-最近邻分 类、 神经网络分类、 贝叶斯分类、 决策树分类和等方法。 经过认真的研究和分析, 本文决定用主要对决策树方法进行研究,依据如下:
(1)首先,由于数据挖掘技术的应用还不是很普及,很多的教师和学校的 教学工作者并不具备相关的知识, 决策树是以树形结构表示最终分类结果, 可以 让不具备数据挖掘及时知识的人很直观的了解挖掘结果。
(2)其次是,速度快:计算量相对较小,且容易转化成分类规则。只要沿 着树根向下一直走到叶, 沿途的分裂条件就能够唯一确定一条分类的谓词。 准确 性高:挖掘出的分类规则准确性高, 便于理解, 决策树可以清晰的显示哪些字段 比较重要。
(3)最后,决策树可以更加直接明了地显示出各属性的重要程度。决策树 是通过计算信息熵选择分裂属性的, 所以, 决策树的结点越接近根结点, 该点所 代表的属性就越重要。
4.2 决策树算法在考试成绩分析中的应用
4.2.1 确定对象集目标
在高校中, 每学期都会对学生的学习成绩进行考核, 进而来观察学生的学习 状况。 学生成绩的好坏是衡量学生的学习状况和老师的教学水平。 因此提高学生 的学习成绩是当代每所大学教学的重要目标。
学生是否能过通过每学期的成绩考核与课程的教学, 以及学习状况有着密切 的关系。 但是传统的成绩分析方法, 不能发现隐藏在考试成绩中的有用信息。 恰 巧, 数据挖掘技术能够做到这点, 本文将采用决策树技术对安徽新华学院考试成 绩进行深入的分析,获取传统的方法无法发现的隐藏信息。
在学校的教学过程中,得到相应的结论,更好的支持学校教学活动的展开, 从而提高学生的学习成绩以及改善学校的教学水平。
4.2.2 数据的采集
为了数据挖掘技术及时在学生考试成绩分析中的应用研究, 本人通过调查问 卷的方式, 采集了 50名学生的学习基本状况以及学生的考试成绩信息。 如表 4.1所示:
编号 姓名 作业
完成
情况
学前知识 了解
上课 是否 认真
平时成绩 成绩 总评
表 4.1学生成绩和基本信息
4.2.3 数据预处理
本文选择中采集到数据中与成绩属性相关性较大的平时成绩、 上课听课情况、 课堂作业完成情况和学前对知识了解情况以及学生计算机等级考试总评作为建 立成绩分类决策树模型的依据。 对成绩没有影响的数据属性将不参与数据挖掘的 工作。最后经过数据削减和数据整合得到如图 4.2所示的学生成绩分析表。
编号 姓名 作业
完成
情况
学前知识 了解
上课 是否 认真
平时成绩 总评
图 4.2学生成绩分析表
4.2.4 数据挖掘工作的展开
本次数据挖掘工作是对处理后的数据进行分析, 本次采用的数据挖掘的主要放大 是决策树算法,并运用决策树方法中的 C4.5算法构造学生成绩分析决策树。 表 4.2是经过数据清理集成之后学生成绩训练集,其中考试成绩有 2类,因此,
将这个训练集分成 2类和 C
2
,分别代表合格和不合格。
(1)计算熵
本次数据挖掘中,计算机等级考试成绩的输出结果是合格、不合格,一共 是 50条记录, 取值为合格的有 28条, 取值为不合格的有 22条, 则样本 D 记为:
D 1 =28, D
2
=22,根据熵的计算公式 Info (D ) = -
1
n
i =
∑P i log 2(P i )。,计算得到: Info (D ) =-
28
50
*log
2
28
50
-
22
50
*log
2
22
50
=0.925
(2)计算信息增益
分别以平时成绩、 上机作业完成情况、 学前对知识的了解以及课堂作业完成
情况作为根节点,计算其信息增益:
属性为平时成绩中取值为较好的有 17个, 其中 13个计算机等级考试成绩为 合格, 4个计算机等级考试成绩为不合格。取值为中等的有 20个,其中考试成 绩合格的有 14个,不合格的有 16个。取值为较差的有 13个,其中考试成绩合 格的有 1个,不合格的为 12个。我们可以计算出相应的熵为:
Info (较好) =- 13
17
log
2
13
17
-
4
17
log
2
4
17
=0.322
Info (中等) =- 14
20
log
2
14
20
-log
2
6
20
=0.722 6 20
Info (较差) =- 12
13
log
2
12
13
-
1
13
log
2
1
13
=0.359
现在就可以根据信息增益计算公式:
计算出相应的信息增益了:Gain (X , D ) =Info(D )-Info (X , D )
Gain (平时成绩) =Info(D ) - 17
50
* Info(较好) -
20
50
* Info(中等) -13 50
* Info(较差) =0.723 同理,如果以上机作业完成情况为根节点:
Info (较好) =- 19
20
log
2
19
20
-
1
20
log
2
1
20
=0.276
Info (一般) =- 14
21
log
2
14
21
-
7
21
log
2
7
21
=0.583
Info (较差) =- 8
9
log
2
8
9
-
1
9
log
2
1
9
=0.602
所以,上机作业完成情况的信息增益为:
Gain (上机作业完成情况) =0.925- 20
50
*0.276-
21
50
*0.583-
9
50
*0.602=0.461
以学前对知识了解情况为根节点:
Info (完全了解) =- 16
17
log
2
16
17
-
1
17
log
2
1
17
=0.370
Info (基本了解) =- 13
17
log
2
13
17
-
4
17
log
2
4
17
=0.531
Info*(了解一些 )= -
3
16
log
2
3
16
-
13
16
log
2
13
16
=0.696
所以,学前对知识的了解情况的信息增益为: Gain (学前对知识的了解情)
=0.925- 17
50
*0.370-
17
50
*0.531-
16
50
*0.696=0.395
以课堂作业完成情况为根节点:
Info (较好) =- 17
18
log
2
17
18
-
1
18
log
2
1
18
=0.306
Info (一般) =- 15
29
log
2
15
29
-
14
29
log
2
14
29
=0.997
Info (较差) =- 2
3
log
2
2
3
-
1
3
log
2
1
3
=0.917
所以,课堂作业完成情况的信息增益为:
Gain (课堂作业完成情况) =0.925- 18
50
*0.306-
29
50
*0.997-
3
50
*0.917=0.182
这样,我们就可以得到以上四个属性相应的信息增益值:
Gain (平时成绩) =0.723
Gain (上机作业完成情况) =0.461
Gain (学前对知识的了解情) =0.395
Gain (课堂作业完成情况) =0.182
最后 Gain (平时成绩)最大,按照 ID3算法的根节点选取原则:信息增益 最大的选为根节点, 选择平时成绩为根节点, 然后根据平时成绩取值为较好、 中 等、 较差三个方向, 对每一颗子树按照以上的方法递归计算, 最后得出的决策树 如图 4.5所示。
图 4.5 成绩分析决策树
在决策树创建时, 由于数据中的噪声和离群点, 许多分支反映的是训练数据 中的异常, 同时决策树枝繁叶茂是没有必要的, 这样降低了树的可理解性和可用 性, 同时也使得决策树对历史数据依赖性大, 为了使得到的决策树所蕴涵的规则 具有普遍意义, 为了防止训练过度, 减少训练时间, 因此需要对得到的决策树进 行剪枝,剪枝的方法有:先剪枝和后剪枝。这里我们采用后剪枝法,即通过衡量 某一分支的存在对分类性能的提高程度和它对整棵树的复杂性的增加程度来决 定是否对此分支给予保留。 本文研究出的决策树, 由于最后的学前知识了解属性 过大的增加了树的复杂性, 而且子树递归计算的信息增益很小, 因此对其进行剪 枝。图 4.6为剪枝后的分裂决策树。可以看出,剪枝后的树更小、复杂度低,因 此容易理解。
图 4.6 修剪后的决策树
4.2.5结果分析
决策树的最大优点就是可以直接提取分类规则。 由于本例中, 希望了解到影 响学生计算机考试成绩合格的因素, 因此, 所提取的规则主要考虑分类为 “ yes ” (即学生计算机等级考试成绩为合格) 的百分比规则。 所生成的计算机考试成绩 为合格的分类规则如下:
IF 平时成绩 =“较好” AND 课堂作业完成情况 =“较好” THEN 学生计算机考 试成绩合格率为 100%
IF 平时成绩 =“较差” AND 课堂作业完成情况 =“一般” THEN 学生计算机考 试成绩合格率 =71%
IF 平时成绩 =“较好” AND 课堂作业完成情况 =“较差”” THEN 学生计算机 考试成绩合格率 =33%
IF 平时成绩 =“中等” AND 课堂作业完成情况 =“较好” THEN 学生计算机考 试成绩合格率
=80%
IF 平时成绩 =“中等” AND 课堂作业完成情况 =“较差” THEN 学生计算机考 试成绩合格率 =33%
IF 平时成绩 =“中等” AND 课堂作业完成情况 =“较好” AND 上机作业完成情 况 =“较好” THEN 学生计算机考试成绩合格率 =83%
IF 平时成绩 =“中等” AND 课堂作业完成情况 =“一般” AND 上机作业完成情 况 =“较好” THEN 学生计算机考试成绩合格率 =67%
IF 平时成绩 =“中等” AND 课堂作业完成情况 =“较差” AND 上机作业完成情 况 =“较好” THEN 学生计算机考试成绩合格率 =67%
5总结与展望
5.1研究结果
本文介绍了一个基于决策树和 SqlServer2008数据库的学生计算机等级考试成绩 的数据挖掘与分析。 对数据挖掘技术中的决策树在学生计算机等级考试成绩分析 中的应用进行了深入的研究, 提出和实施了决策树方法和数据库应用的方法在计 算机等级考试成绩分析中的实施方案。
本次数据挖掘对象, 学生计算机等级考试成绩, 从数据属性可以找出影响学
生计算机等级考试成绩的因素包括:平时成绩、 课堂作业完成情况、 上机作业完 成情况、 学前对知识的了解情况, 分析出影响学生计算机等级考试的通过率的因 素。通过初期的数据采集、数据清理工作,然后应用决策树算法、数据库 sql 查 询分析器构造出学生计算机等级考试成绩决策树。 在这其中, 我们可以发现平时 成绩这个属性的信息增益最大,对成绩影响也最大,然后通过所建立的决策树, 我们可以得到一系列的 IF — THEN 的知识模式便于人们理解。
通过前篇内容的研究, 我们得到的学生计算机等级考试成绩决策树, 我们可 以进一步的挖掘出, 扩大数据的规模, 增加更多的数据属性, 找出计算机等级考 试成绩通过率的差异。
上述这些挖掘出来的知识对于今后的学校计算机教育的决策是有帮助的, 今 后学校计算机教育要着重加强通过率比较低的院系、 调整好院系学生语种学习的 选择等方法来提高学校学生计算机等级考试的通过率。
目前, 许多高等院校的研究人员已经开始将数据挖掘技术广泛应用于学校教 学管理中, 这样做能够很有效地提高学校教学信息管理水平。 其中, 利用决策树 技术对学生的学习成绩分析, 得到有意义的知识, 从而帮助学校教育工作者制定 相应的教学计划,有利于提高学校的教育质量。
5.2后续研究与展望
本文初步实现了关于决策树在计算机等级考试成绩分析中的应用,取得了良好 的挖掘效果。 当然, 随着数据挖掘技术的不断改进, 应用数据挖掘技术中的决策 树在学校计算机等级考试成绩分析需要在各个方面不断的加深。 例如, 学校可以 学校在校考试成绩系统中的学生在校考试成绩信息、 学校课程信息以及学校教师 管理信息系统和学生计算机等级考试成绩系统相结合, 这样可以更进一步地对学 生计算机等级考试成绩进行数据挖掘分析, 得到更有用的数据挖掘模式, 从而更 有效地提高学校的教学质量。 同时, 决策树技术不断可以应用在学生计算机等级 考试成绩分析, 我们还可以用于其他教学信息管理系统中, 比如英语四六级考试 成绩等,这些方面的应用都是有待研究的新课题。
致 谢
历时将近两个月的时间终于将这篇论文写完, 在论文的写作过程中遇到了无 数的困难和障碍, 都在同学和老师的帮助下度过了。 尤其要强烈感谢我的论文指 导老师—袁张露老师, 她对我进行了无私的指导和帮助, 不厌其烦的帮助进行论 文的修改和改进。 另外, 在校图书馆查找资料的时候, 图书馆的老师也给我提供 了很多方面的支持与帮助。 在此向帮助和指导过我的各位老师表示最中心的感谢! 感谢这篇论文所涉及到的各位学者。 本文引用了数位学者的研究文献, 如果没有 各 位 学 者 的 研 究 成 果 的 帮 助 和 启 发 , 我 将 很 难 完 成 本 篇 论 文 的 写 作 。 感谢我的同学和朋友, 在我写论文的过程中给予我了很多你问素材, 还在论文的
撰 写 和 排 版 的 过 程 中 提 供 热 情 的 帮 助 。 由于我的学术水平有限, 所写论文难免有不足之处, 恳请各位老师和学友批评和 指正!
参考文献
[1]冯红伟 . 数据挖掘技术的研究及应用 [D].西北工业大学 .2002年 .
[2]张保稳 . 时间序列数据挖掘研究 [D].西北工业大学 .2002年 .
[3]俞珏民 . 基于项 -事务关联数据库的相联规则挖掘算法的研究 [D].郑州大学 .2000年 . [4]姚亚辉 . 基于电子商务数据挖掘技术的研究与应用 [J].安阳师范学院学报 .2007年 02期 . [5]王轶 . 达新宇 . 分布式并行数据挖掘计算框架及其算法研究 [A].2006年全国开放式分布 与并行计算学术会议论文集(一) [C].2006年 .
[6]李志云 . 周国祥 . 基于 FP-Growth 的关联规则挖掘算法研究 [A].计算机技术与应用进 展·2007——全国第 18届计算机技术与应用(CACIS )学术会议论文集 [C].2007年 . [7]张 建 同 , 邱 玥 . 数 据 挖 掘 技 术 及 其 在 电 子 商 务 中 的 应 用 [A].Proceedings of 2010
International Conference on Management Science and Engineering (MSE 2010) (Volume 3)[C].2010年 .
[8]朱小栋 . 基于扩展预测模型标记语言的数据流挖掘系统建模研究 [D].南京航空航天大 学 .2009年 .
[9]王宏 . 基于粗糙集数据挖掘技术的客户价值分析 [D].哈尔滨工程大学 ;2006年 .
[10]陆垂伟 . 电子商务中数据挖掘技术的研究与应用 [J].商场现代化 .2006年 10期 .
[11]许 华 虎 , 孙 柏 林 , 高珏 , 陈 开 . 基 于 校 园 一 卡通 的 学 生 体 育 锻 炼 数 据挖 掘 的 研 究 [A].Proceedings of 2010 International Conference on Computer Science and Sports Engineering (CSSE 2010)[C].2010年 .
[12]张松 , 周亚建 , 刘念 . 数据挖掘基本算法比较分析 [A].2010年全国通信安全学术会议论 文集 [C].2010年 .
[13]李开宇 , 黄建军 , 田长春 . 把“数据挖掘”作用发挥出来 [N].中国国防报 .2009年 . [14]晏燕 . 数据挖掘让决策者告别“拍脑袋” [N].科技日报 .2006年 .
[15]刘革平 . 基于数据挖掘的远程学习评价研究 [D].西南师范大学 .2005年 .
[16]郑宏 . 数据挖掘可视化技术的研究与实现 [D].西安电子科技大学 .2010年 .
[17]徐路 . 基于决策树的数据挖掘算法的研究及其在实际中的应用 [D].电子科技大学 .2009年 .
[18]王浩 . 数据挖掘在上海市职业能力考试院招录考试优化管理项目中的运用研究 [D].华东 理工大学 .2012年 .