摘要：该文采用分类决策树算法对高职学生在校英语平均成绩进行分析挖掘，找出有效的分类规则预测高职学生在英语四级考试中通过情况。
关键词：决策树算法；预测；熵；信息增益比例；规则
中图分类号：TP311文献标识码：A 文章编号：1009-3044(2011)11-2489-03
每年的英语四级考试不仅是高校学生关心的事，也是各院校关心的大事。如何提升学生的英语四级通过率成了各院校教学管理的重要内容。这个通过率是否与学生的平时英语成绩有一定的关系，能不能从平时成绩中预测出每位学生的四级通过情况呢。通过数据挖掘技术可从学生成绩管理系统的大量数据中挖掘出隐含的、未了解的、用户感兴趣的并能为决策提供潜在价值的知识和规则。数据挖掘要经过一系列如数据采集、预处理、数据分析、结果表示等过程。其使用的算法主要有：关联规则、决策树方法、人工神经网络、遗传算法、粗糙集方法、模糊论方法、贝叶斯模型等等。[1] 该文将采用分类决策树算法对高职学生在校英语平均成绩进行分析挖掘，找出有效的分类规则预测学生在英语四级考试中通过情况。
1 决策树算法
决策树能以一组没有任何次序规则的数据记录为基础，从中推理出以决策树表示形式的分类规则。决策树方法采用自顶向下的递归方式，在决策树内部结点进行属性值的比较，并根据不同的属性值判断出向下的分支，在决策树的叶结点得到结论。决策树的每个结点代表一个属性，每个分支代表该属性取值的判断条件。
决策树以及决策树规则属于输出的分类方法，主要针对解决分类和预测问题。此算法最关键的地方是决策树的构建。而一个有效的决策树的建立需要包括建树和剪枝两个步骤。第一步是利用训练集建立一棵决策树，建立决策树模型规则；第二步是利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根节点依次测试记录的属性值，直到到达某个叶子节点，从而找到该记录所在的类。在决策树的生成阶段要对决策树进行必要的修剪。剪枝的目的是降低由于训练集存在噪声而产生的起伏。我们常用的修剪技术有两种:一种是预修剪，另一种是后修剪。决策树停止分割的条件有:一个节点上的数据都是属于同一个类别;没有属性可以再用于对数据进行分割。[2]
决策树算法主要解决三个最优化问题:生成最少的叶子；生成的每个叶子的深度最小；生成的决策树叶子最少且每个叶子的深度最小。[3]
2 决策树构建算法
输入:训练样本S，均由离散值属性表示;候选属性的集合
A_L输出:一棵决策树
处理流程:
l)创建一个结点N；2)If S都在同一个类 d then；3)返回N作为叶结点，以类d标记；4)IF A_L为空，then；5)返回N作为叶结点，标记为该结点所含样本中类别个数最多的类别；6)选择A_L中具有最高信息增益的属性T_A7)标记结点N为T_A；8)for each T_A中的己知值ai；9)由节点N长出一个条件为T_A=ai的分枝；10)设Si是S中T_A=ai的样本的集合；11)If Si为空 then；12)将相应叶结点标记为该结点所含样本中类别个数最多的类别；13) else将叶结点标记为Generate_decision_tree(Si，A_L，T_A)。这是基本的ID3算法,它采用自顶而下，分而治之的递归方法来构造一个决策树。[1]
3 高职学生英语四级通过情况预测模块的工作步骤
1)通过高职学生的英语考试成绩信息的样本数据，采用决策树算法，计算出与预测最为相关的属性(即信息增益值最大的属性)作为决策树的根结点,然后再采用递归的方法将其他属性进行分类，构造出一个有效的分类预测决策树。
2)利用决策树形成的分类模型，形成IF一THEN分类规则。
4 高职学生英语四级通过情况预测模块中决策树构建的具体实现
提取毕业生的在校英语成绩采用ID3算法进行挖掘，预测学生在英语四级考试的通过情况。毕业生的成绩库的实验样本数据(如表1)，里面的数据经过属性归纳后，除去无关属性后将性别、班级类别、专业、在校英语平均成绩等属性作为构造决策树的条件属性结点。然后把其中的连续属性在校英语平均成绩经过分类转换为离散属性：S1[80-100]；S2[70-79];S3[60-69];S4[0-59]。
4.1 利用信息增益比例构造决策树
在这个实验样本中需要分类的属性是“英语四级通过结果”。四级通过情况的属性只有两个值：通过和未通过。而在样本数据中通过的有10个，未通过的有5个。则英语四级通过情况的期望信息如下：
I(s1，s2)=I(10，5)= -10/15log(10/15)-5/15log(5/15)=0.917(s1代表通过人数，s2代表未通过人数，以下相同)
然后再计算每一个属性的熵:
1)先从性别开始,对于女生：I(s1,s2)=I(7,1)=0.544；对于男生：I(s1,s2)=I(3,4)= 0.925
按性别来分，对应的熵：E=0.544*8/15+0.925*7/15=0.722；SplitI= -8/15log(8/15)-7/15log(7/15)=0.977；Gain=0.917-0.722=0.195
得到信息增益比例:GainRatio(性别)= Gain/ SplitI=0.200
2)再从专业开始，专业有网络，应用，软件。对于网络专业，I(s1,s2)=I(4,1)= = 0.722；对于应用专业，I(s1,s2)=I(2,3)= 0.971；对于软件专业，I(s1,s2)=I(4,1)= = 0.722
按专业来分，对应的熵：E=0.722*5/15+0.971*5/15+0.722*5/15=0.805；SplitI= -5/15log(5/15)-5/15log(5/15) -5/15log(5/15)= 1.585；Gain=0.917-0.805=0.112
得到信息增益比例:GainRatio(专业)= Gain/ SplitI=0.071
3)从班级类别开始，班级类别有高考，单招。对于高考类：I(s1,s2)=I(9,1) = 0.469；对于单招类，I(s1,s2)=I(1,4)=0.722；
按班级类别来分，对应的熵：
E=0.469*10/15+0.722*5/15=0.554；SplitI= -10/15log(10/15)-5/15log(5/15)= 0.918
Gain)=0.917-0.554=0.363
得到信息增益比例:GainRatio(班级类别)= Gain/ SplitI=0.395
4)最后从在校英语平均成绩开始,在校英语平均成绩有四类值:S1[80-100]；S2[70-79]；S3[60-69]；S4[0-59]。
对于成绩S1，I(s1,s2)=I(3,0)= 0；对于成绩S2，I(s1,s2)=I(3,0)= 0；对于成绩S3，I(s1,s2)=I(4,1)=0.722；对于成绩S4，I(s1,s2)=I(0,4)= 0
按在校英语平均成绩来分，对应的熵：
E=0*3/15+0*3/15+0.722*5/15+0*4/15=0.241；SplitI=-3/15log(3/15)-3/15log(3/15)-5/15log(5/15)- 4/15log(4/15)= 1.966；Gain=0.917-0.241=0.676
得到信息增益比例GainRatio(在校英语平均成绩)= Gain/ SplitI=0.344
四个属性的信息增益比例分别是GainRatio(性别)=0.200；GainRatio(专业)= 0.071；GainRatio(班级类别)=0.395；GainRatio(在校英语平均成绩)= 0.344。其中GainRatio(班级类别)=0.395最大，将班级类别属性作为决策树的根结点，可以把决策树分成两颗子树Tl和T2，T1是高职单招部分的学生子树，T2是高考部分的学生子树。
4.2 研究各子树的分枝
对于T1，继续计算各属性的的嫡和信息增益比例：
1)先从性别开始,对于女生I(s1,s2)=I(1,1)=1；对于男生I(s1,s2)=I(0,3)=0
按性别来分，对应的熵：
E=1*2/5=0.4；SplitI= -2/5log(2/5)-3/5log(3/5)=0.971；Gain=0.772-0.4=0.372
得到信息增益比例:GainRatio(性别)= Gain/ SplitI=0.383
2)从专业开始，专业有网络，应用。对于网络专业，I(s1,s2)=I(1,1)= 1；对于应用专业，I(s1,s2)=I(0,3)= 0
按专业性来分，对应的熵：
E=1*2/5=0.4；SplitI= -2/5log(2/5)-3/5log(3/5) = 0.971；Gain=0.772-0.4=0.372
得到信息增益比例:GainRatio(专业)= Gain/ SplitI=0.383
3)最后从在校英语平均成绩开始,在校英语平均成绩有四类值: S1[80-100]；S2[70-79]；S3[60-69]；S4[0-59]。
对于成绩S2，I(s1,s2)=I(1,0)= 0；对于成绩S3，I(s1,s2)=I(0,1)= 0；对于成绩S4，I(s1,s2)=I(0,3)= -3/3log(3/3) =0
按在校英语平均成绩来分，对应的熵：
E=0；SplitI= -1/5log(1/5)- 1/5log(1/5)-3/5log(3/5)= 1.371；Gain=0.722-0=0.722
得到信息增益比例:GainRatio(在校英语平均成绩)= Gain/ SplitI=0.708
对比以上几个属性的信息增益比例值，最大的是:GainRatio(在校英语平均成绩) =0.708，所以将在校英语平均成绩作为T1的根结点，得到T1的分枝分别是
成绩S2，成绩S3，成绩S4
对于T2，也同样以上操作：
1) 先从性别开始，对于女生，I(s1,s2)=I(6,0) =0；对于男生，I(s1,s2)=I(3,1)=0.811
按性别来分，对应的熵：
E=0.811*4/10=0.324；SplitI= -6/10log(6/10)-4/10log(4/10)=0.971；
Gain=0.469-0.324=0.145
得到信息增益比例:GainRatio(性别)= Gain/ SplitI=0.149
2)再从专业开始，专业有网络，应用，软件。对于网络专业，I(s1,s2)=I(3,0)= 0；对于应用专业，I(s1,s2)=I(2,0)= 0；对于软件专业I(s1,s2)=I(4,1)= 0.722
按专业性来分，对应的熵：
E=0.722*5/10=0.361；SplitI= -3/10log(3/10) -2/10log(2/10) -5/10log(5/10) = 1.485；Gain=0.469-0.361=0.108
得到信息增益比例:GainRatio(专业)= Gain/ SplitI=0.072
3) 最后从在校英语平均成绩开始,在校英语平均成绩有四类值: S1[80-100]；S2[70-79]；S3[60-69]；S4[0-59]。
对于成绩S1，I(s1,s2)=I(3,0)= 0；对于成绩S2，I(s1,s2)=I(2,0)= 0
对于成绩S3，I(s1,s2)=I(4,0)= 0；对于成绩S4，I(s1,s2)=I(0,1)= 0
按在校英语平均成绩来分，对应的熵：
E=0 ；SplitI= -3/10log(3/10)- 2/10log(2/10)-4/10log(4/10)-1/10log(1/10)= 1.846；
Gain=0.469-0=0.469
得到信息增益比例:GainRatio(在校英语平均成绩)= Gain/ SplitI=0.254
对比以上几个属性的信息增益比例值，最大的是:GainRatio(在校英语平均成绩) =0.254
所以将在校英语平均成绩作为T2的根结点，得到T2的分枝分别是成绩S1，成绩S2，成绩S3，成绩S4。
4.3 最终决策树与规则
最后得到最终决策树如图1。
决策树转化为IF_THEN规则如下：
规则一：IF学生所在班级是在高考班，且在校英语平均成绩是在S1，THEN可以通过英语四级考试。规则二：IF所在班级是在高考班，且其在校英语平均成绩是在S2，THEN可以通过。规则三：IF所在班级是在高考班，且其在校英语平均成绩是在S3，THEN可以通过。规则四：IF所在班级是在高考班，且其在校英语平均成绩是在S4，THEN肯定不能通过。规则五：IF所在班级是在高职单招班，且其在校英语平均成绩是在S2，THEN可以通过。规则六：IF所在班级是在高职单招班，且其在校英语平均成绩是在S3，THEN不能通过。规则七：IF所在班级是在高职单招班，且其在校英语平均成绩是在S4，THEN肯定不能通过。
5 小结
通过以上规则形成的分类模型，可以对学生的英语四级考试进行预测，当满足以上的IF条件后，可以很快得到THEN的预测结论。有了此预测模块，决策者可以加强高职单招班的英语教学工作。作为高职单招班的学生，由于不象高考班的学生经历过高中英语的磨砺，所以其英语能力较弱，更应在平时重视英语的学习。
参考文献：
[1] 韩家炜.数据挖掘概念与技术[M].北京:机械工业出版社,2008.22,66.
[2] [加]JiaweiHan.数据挖掘概念与技术[M].北京:机械工业出版社,2001
[3] 吴瑕.数据挖掘技术在教学管理中的应用研究[D].哈尔滨工程大学,2007:10.