基于决策树的学生成绩分类研究

阴爱英，杨晓花

（福州大学至诚学院 计算机工程系，福建 福州 350002）

基于决策树的学生成绩分类研究

阴爱英，杨晓花

（福州大学至诚学院 计算机工程系，福建 福州 350002）

本文根据决策树分类技术对福建省计算机等级考试中的成绩进行分析和挖掘.首先对成绩数据进行离散化处理，设置成决策树分类的属性数据；接着利用ID3改进算法构建成绩分类的决策树模型，并对其剪枝；最后根据模型给出相应的规则和几个教学建议.实验结果表明，利用决策树分类技术在计算机等级考试中进行挖掘分析的方法是有效可行的.

数据挖掘；决策树；信息增益；计算机等级考试

1 引言

随着数据挖掘技术的发展，各行各业均利用数据挖掘技术来为其提供决策支持.数据挖掘技术是从大量的数据中，挖掘出人们开始并不知道的但又隐含在数据库中的并且有用的信息[1].随着高等教育行业的信息化技术的发展，越来越多的管理者或老师更加关注学生的学习情况，通过对历年来的教学数据进行分析，挖掘出影响学生学习成绩的一些关键信息，以此提高教学质量.

近年来，国内外学者对数据挖掘的应用进行了深入研究，如：Abeer等[2]根据现有的教学数据库，利用决策树分类技术预测学生的最终成绩；Rupp等[3]通过EDM(Education Data Mining)和学习分析技术对学生学习能力进行挖掘；Alejandro[4]通过对EDM平台进行维护和扩展，并对该平台利用数据挖掘的方法进行分析和讨论；Abdullah等[5]利用关联规则对电子管理系统进行挖掘，为教育管理机构提供决策支持；姜永超通过关联规则和序列模式进行挖掘，分别对学生选课和学习兴趣的行为进行分析研究[6]；顾辉等[7]利用对关联规则Apriori算法的改进，并应用于《计算机基础》课程的学生成绩进行研究与分析；王华等[8]根据关联规则技术对学生成绩进行挖掘，并对学生的成绩进行预警，及时找出可能出现不及格的课程，对部分学生给出警告.

本文通过在前期工作研究的基础上[9]，利用决策树分类挖掘技术，对福建省计算机等级考试二级（C语言）进行挖掘，用决策树分类技术构建学生成绩是否合格与哪些题型得分情况有关的决策树分类模型，为老师更好地教授好这门课程提供一些有用信息，也为学生能更好地通过等级考试提供了参考资料.

2 相关知识

决策树（Decision Tree）又称判定树[10]，是采用树型结构对数据进行分类的.它是从一堆没有任何规则且是无序的数据中，根据分类规则，利用树的形状来表示这些数据的分类情况.在构造的决策树中，树的最顶层是根结点，它是表示第一次选择分裂的属性，而树的其它内部结点（不是叶子结点）表示对其它属性数据的测试，叶子结点表示数据属性的分类情况，而对于一个决策树的分支来说，其代表着某个测试数据属性的分类情况输出.

一般来说，利用决策树进行分类挖掘时，需要经历下面的过程：第一步是构建决策树模型，即利用先知类型的样本数据对其实行分类，构造一个决策树模型.在这个步骤中要经历两个阶段，即建树和剪枝；第二步是通过使用已经构建好的树型对数据集进行分类挖掘.为了找到输入数据所属的分类情况，需要对决策树进行遍历，即从根结点到叶子结点，依次对输入数据进行测试，直到找到该数据所属分类为止.

下面简要介绍决策树构造的基本方法：

(1)从训练样本的单个结点开始，构建决策树.

(2)假如训练数据都是归属于某个类型，则该结点成为树叶节点，并对该树叶节点进行类型标记.

(3)要不然的话，算法会继续使用各种分裂技术来对样本数据进行分类，其分类的依据是采用更好的分类属性来进行的.

(4)为测试数据的每个值建立一个分支，并以此来划分样本.

(5)重复应用上面的步骤，直到整个决策树构建完成.

3 决策树的学生成绩分类模型

3.1 改进ID3算法

ID3算法是Quinlan于上个世纪八十年代后期提出的[1]，是决策树分类中最为典型的算法之一.它通过对各个测试数据属性进行计算它们各自的信息增益值，根据它们值的大小，来决定选取哪个数据作为分裂节点.在ID3算法中，是通过选择增益值最大的属性，作为分裂的属性.信息增益值的计算公式如式（1）所示：

上述公式中，数据集D根据类别属性的值可以分成相互独立的类C1，C2，…，Cn，其出现的概率分别为pi，而v表示属性A具有不同的值.

然而ID3算法存在着一些不足：ID3算法对于属性的选择通常是离散数据，而对连续值的属性就无法应对；在对各个属性数据进行计算其信息增益时，往往会选择数据取值较多的属性数据，但并不是所有属性值大的属性就是最优属性；对于噪声数据较为敏感等问题.

在前期对ID3算法进行改进的基础上[9]，主要思想是(具体算法请查看文献[9])：一类为正例，一类为反例.假设，正例的个数为n个，反例的个数为m个.在训练集D中，有属性A，A有v个不同的值，当且有A=ai时，以属性A分裂下的元素一共有ni+mi个.其中n为正例，则有ni个正例.同理，反例个数为mi.由此，我们可以得到：

改进的新算法是将作为新的信息期望，简化了原先的计算方法，得出新的公式结论，计算每个属性过后，值最小的信息作为分类标准.

3.2 数据处理

本文是针对福建省计算机等级考试二级（C语言）的成绩利用决策树分类模型进行分类挖掘.对于成绩是连续型数据，而决策树分类技术是需要离散的属性值，因此就要对连续型数据转变成离散型数据.在数据处理中所采用的是概念分层技术，如：将选择题的得分情况按30～40分、19～29分、0～18分划分为“高”、“中”、“低”三类，填空题、改错题和编程题都是20分，它们得分情况按15～20分、8～14分、0～7分可以划分为“高”、“中”和“低”三类，对于成绩来说，我们挖掘的内容是成绩合格与否，因而将成绩按0～59分和60分以上划分为“不合格”和“合格”两类数据.经过数据预处理工作后，得到挖掘的数据源（共8483条），如表1所示.

表1 数据预处理后的数据集

3.3 信息增益的计算

根据上述数据处理后的数据集，利用公式（4）可以计算出各个属性值的信息增益值：

（1）选择题的信息增益值：

在计算选择题的信息增益时，需要分别计算选择题得分情况为高、中、低三种属性值情况下，它们成绩合格人数和不合格人数.在测试样本数据集中，选择题得分为高，成绩为合格的人数有2545人，成绩为不合格的人数有328人，选择题得分为中，成绩为合格的人数有1193人，成绩为不合格的人数有2656人，而选择题得分为低，成绩为合格的人数有15人，成绩为不合格的人数有1263人.根据这些信息，我们得到计算平时成绩的信息增益如下：

（2）改错题的信息增益值：

在测试样本数据集中，改错题的得分情况有三种属性值，在改错题得分为高下，成绩为合格的人数有3074人，成绩为不合格的人数有814人，改错题得分为中，成绩为合格的人数有651人，成绩为不合的人数有1728人，改错题得分为低，成绩为合格的人数有28人，成绩为不合的人数有1705人，因此其信息增益值为：

（3）编程题的信息增益值：

编程题有三个属性值，在编程题得分为高，成绩为合格的人数有589人，成绩为不合格的人数有10人，在编程题得分为中，成绩为合格的人数有2625人，成绩为不合格的人数有804人，在编程题得分为低，成绩为合格的人数有539人，成绩为不合格的人数有3433人，因此其信息增益值为：

（4）填空题的信息增益值：

填空题有三个属性值，在填空题得分为高，成绩为合格的人数有2744人，成绩为不合格的人数有371人，在填空题得分为中，成绩为合格的人数有893人，成绩为不合格的人数有1419人，在填空题得分为低，成绩为合格的人数有116人，成绩为不合格的人数有2457人，因此其信息增益值为：

3.4 成绩分类的决策树构建

首先就是创建根节点，然后选取各个属性的信息增益值为最小的属性作为分裂属性，根据上面对各个属性的信息增益值进行计算，填空题的信息增益值最小，因而将填空题作为决策树的根节点，建立一个决策树，决策树上的根节点标记为“填空题”.对于填空题的三种取值，即高、中和低，分别建立相应的子集，引出相应的分支，如图1所示.

在图1种决策树只有一层，那么在填空题的每个分支上继续按照上面的方法建立相应的决策树，通过递归算法，计算相应属性的信息增益值，确定每个分支中各个节点，直到子集为空或者没有属性可以划分为止，最终可以形成一颗决策树.

在形成了决策树中，树型比较复杂，树枝比较繁杂，比较难于理解，因而需要对生产的决策树进行剪枝，剪枝的目的是使树型变得更小、复杂度更低、更容易理解.如在构造的等级考试成绩分类的决策树上，填空题得分为中且改错题得分为中且选择题得分为中的情况下，编程题得分为高、中、低情况下，其合格的人数分别为13人、60人和0人，而不及格的人数分别为1人、168人和354人，从这些情况看基本是不及格占绝大多数，因此可以把它们合并为不合格，同样，在填空题得分为高且改错题得分为中且选择题得分为中的情况下，编程题得分为高、中、低情况下，其分数为合格的人数分别为15人、128人和5人，而分数为不合格的人数分别为0人、22人和118人，这样就可以把编程题得分为高和中合并为“≥中”等等.最终经过剪枝后生成的决策树如图2所示.

3.5 决策树分类规则及建议

根据图2生成学生成绩分类决策树模型，可以得出一些分类规则，具体的表述如下：

IF填空题=高and改错题=高THEN成绩为合格的概率95.3%（即：如果填空题得分在15～20分且改错题在15～20分时，成绩为合格的人数为2271，不合格的人数为111，下面规则的解释也是一样，就不再进行详细解释）

IF填空题=高and改错题=低THEN成绩为不合格的概率75.8%

IF填空题=高and改错题=中and选择题=高THEN成绩为合格的概率96.2%

IF填空题=高and改错题=中and选择题=低THEN成绩为不合格的概率100%

根据以上得出的分类规则，我们可以给出以下一些建议：

(1)从学生角度来说，要想更好地通过福建省计算机等级考试二级（C语言），那么应该在填空题和改错题两题中得分高些.而省等级计算机考试在考察填空题和改错题的内容上，恰恰是考察学生的阅读程序和修改程序的能力，因此建议学生平时要多注重阅读程序能力的培养，只有大量的阅读程序，才能更好的修改程序和编写程序.

(2)从教师角度来说，要想让学生更好地通过省计算机等级考试，则应该在课堂授课中注重理论与实践相结合，不关是简单地讲解基本理论知识，更应该在课堂上机过程中培养学生读和写程序的能力.

4 结论

本文针对现阶段福建省计算机等级考试二级（C语言）的学生成绩，利用决策树分类技术，对等级考试中的成绩建立决策树模型，为提高教师的教学质量提供决策支持.首先，将等级考试中连续型数据进行离散化处理，构建符合决策树分类的属性数据，接着利用前期提出了ID3改进算法，计算出各个属性的增益值，选择信息增益值最小的属性作为分类的根节点，并用递归算法完成整个决策树的构建，然后对构建的决策树进行了剪枝，使其变成较为简单的决策树模型，最后根据决策树模型得出了一些有关教学的规则，并给出一些相关的教学建议.

现阶段随着教学质量的提升，各个高校对提高教学质量也投入了大量精力，下一步工作，我们将继续采用数据挖掘技术对教学数据进行分析和挖掘，构建更为合理的模型，为提高教学质量提供一些建议.

〔1〕范明,孟小峰,等.数据挖掘概念与技术[M].北京:机械工业出版社，2010.

〔2〕Abeer B E D A,Sayed Elaraby I.Data Mining:A prediction forStudent'sPerformance Using Classification Method[J].World Journal of Computer Application&Technology,2014,2 (2):43-47.

〔3〕Rupp A A,Leighton J P,Baker R S,et al. Educational Data Mining and Learning Analytics[M].Learning Analytics.2014:379-396.

〔4〕Pena-AyalaA.Educationaldatamining:A survey and a data mining-based analysis of recent works[J].Expert Systems with Applications,2014,41(4):1432–1462.

〔5〕Abdullah Z,Herawan T,Deris M M.Discovering Interesting Association Rules from Student Admission Dataset[J].Lecture Notes in Electrical Engineering,2014,285:135-142.

〔6〕姜永超.基于数据挖掘的学生选课及学习行为分析算法研究 [J].现代电子技术,2016,39(13): 145-148.

〔7〕顾辉,杨青,蒋成功,等.关联规则在成绩分析中的研究及应用[J].计算机应用,2015(S1):149-151.

〔8〕王华,刘萍.改进的关联规则算法在学生成绩预警中的应用[J].计算机工程与设计,2015(3):679-682.

〔9〕阴爱英.决策树ID3算法的一种改进[J].电子世界,2014(22):433-434.

〔10〕梁亚声,徐欣,成小菊,等.数据挖掘原理、算法与应用[M].北京:机械工业出版社,2015.

TP391

A

1673-260X（2017）08-0018-04

2017-05-23

福建省教育厅中青年教师教育科研项目（NO.JAT160658）