基于局部择优离散技术的C4.5改进算法及其在学生成绩评价中的应用

吴玉春，龙小建



基于局部择优离散技术的C4.5改进算法及其在学生成绩评价中的应用

*吴玉春1，龙小建2

（1.井冈山大学电子与信息工程学院，江西，吉安 343009；2.井冈山大学继续教育学院，江西，吉安 343000）

针对高校教务管理系统中学生成绩数据连续值偏多的情况，导致无法对学生成绩有效地进行智能分析等问题，提出了基于局部择优离散技术的C4.5改进算法，进而构建学生成绩分析模型，并采用后剪枝算法对模型进行了优化，抽取了学生成绩的分类规则。实验表明，改进后的C4.5算法保证较高分类正确率的同时，执行效率得到了提高，有助于挖掘出学生成绩与各种因素之间的潜在联系，为教学工作改革提供决策依据和支持。

C4.5算法；离散技术；后剪枝；学生成绩分析模型

0 引言

学生成绩是各个高校衡量学生知识掌握程度和评判教学质量的主要依据。近几年，随着我国高校体制的不断改革，高校招生规模日益扩大，师生比例不均衡，一定程度上影响了高校的教学质量，如何提高教学质量，培养适应社会的人才是摆在各个高校面前需要解决的问题。21世纪是信息时代，高校都已引入教务管理信息系统平台，在日常教学管理中，积累了海量的数据，但这些数据仍然停留在传统数据分析阶段，通过查询统计可以迅速地得到学生的各科成绩信息，但无法了解学生取得这些成绩深层次的原因。怎样建立一种智能化的信息分析手段，有效挖掘出影响学生成绩的因素，是目前高校教务管理工作热点研究问题之一。

数据挖掘技术是从模糊、有噪声、随机的海量信息中提取有用的信息的过程，与传统的查询、报表、联机应用分析等数据分析方法本质上的区别在于，它是在没有明确假设的前提下去挖掘信息和发现知识，获取的信息具有未知、有效和实用性[1-2]。数据挖掘技术被应用于各行各业，近几年也被众多学者应用到学校管理及教学领域中，从而提高学校管理决策水平和教学质量[3-4]。决策树是以分类精度高、速度快、决策规则直观易懂等优点成为数据挖掘应用领域中极其广泛的重要技术[5-6]。构造决策树的算法众多，最常用是ID3算法和C4.5算法，C4.5算法是ID3的改进算法，克服了ID3不能处理连续型属性数据的缺点，并采用最大信息增益率作为决策树的属性选择标准，弥补了ID3偏向于选择取值多属性的缺陷[7-8]。

本文针对学生成绩数据连续值偏多的情况，采用局部择优的离散化技术，提出了基于局部择优离散技术的C4.5改进算法，将连续数据离散化为分类值，构造学生成绩分析模型并进行优化，挖掘出学生成绩与各种因素之间的潜在联系，为今后的教师教学改革提供决策依据和支持，并为高校教学管理的智能化数据处理提供一条有效途径。

1 基于局部择优离散技术的C4.5改进算法

学生成绩信息中存在大量的连续型数据，如试卷难易程度、考试成绩、平时成绩、实验成绩等，不利于决策树的有效分类，必须对连续型数进行离散化处理，转化成相应的分类值。C4.5算法能将连续型属性的数据值转化成离散的类别数据[9-10]。对一连续型属性，在它不同的取值处插入若干个分割点，计算每个分割点的信息增益率，属性取值越多，相应的分割点越多，选择信息增益率最大的分割点的阈值作为该属性的分割阈值。但当该决策树的连续型属性较多且相应的属性取值多时，算法计算量非常大，这直接影响了决策树的执行效率。在连续属性被离散化时，如何快速获取最佳分割阈值，降低计算复杂度，提高决策树的效率，是建立学生成绩有效分析模型一个亟需解决的问题。

本文采用局部择优法进行连续属性离散化处理，无论用于学习的数据集有多少个类别，不管类别分布如何，连续型属性的最佳分割点总在边界点处。首先将某一连续属性按取值大小进行升序排列，选取相邻的两个类别边界点处的6个属性值：ci-2、ci-1、ci、ci+1、ci+2、ci+3，其中ci-2

基于局部择优离散技术的C4.5改进算法思路: 对样本训练集进行预处理，如果存在连续型属性，采用局部择优法将其离散化，将训练集视为根结点，分裂属性采用最大信息增益率来决定，利用分裂属性的不同值，生成根结点的第一层子结点，再分别将第一层的子结点作为“根结点”，重复以上步骤，直到满足终止条件，即停止构造，得到所需的决策树；采用后剪枝法对生成的决策树进行优化，去除噪声，简化决策树；抽取决策规则，构成分类器。基于局部择优离散技术的C4.5改进算法的伪代码如图1所示：

基于局部择优离散技术的C4.5改进算法：CDT（T，D）Input : 训练集 T；T属性的集合D；分类属性C。output:一颗未剪枝的C4.t5决策树。(1) 建立根结点Root；(2) IF T为Empty then 返回结点Root并标记为Failure；(3) IF T的值为同一类别C then返回Root标记为叶结点，类别为C；(4) IF D 为empty Or T 剩余样本数少于某给定值 then(5)返回Root 标记为叶结点，并记Root为 T中出现最多的类；(6) END IF (7) FOR each D (8) IF D是连续值then(9)采用局部择优法选择最佳分割阈值对D进行离散化处理(10) END IF(11) IF D 是离散型 then(12)按D的取值类型将T划分成若干子集；(13) END IF(14)计算信息增益率； (15) End FOR(16)Select D中最高信息增益率的属性，并将其标记为结点Root的属性；(17)FOR each 由结点Root 生成New叶子结点 （18）IF 该叶子结点样本子集*T 为Empty（19）则标记新叶结点，并记为 T 中出现最多的类；（20）ELSE (21) 递归调用CDT(T, *T .D)为该分支创建子树； (22) END IF（23）END FOR

2 基于局部择优离散技术的C4.5改进算法在学生成绩分析的应用

本文采用基于局部择优离散技术的C4.5改进算法对影响学生成绩的属性特征进行分类和归纳，首先采集学生成绩信息并进行预处理，生成学生成绩样本训练集，构建学生成绩分析模型并进行优化，得到决策树表示形式的学生成绩分类规则，决策树的结点是与成绩相关的属性，每个分支为成绩属性取值的判断条件，实施过程如图2所示。

图2 学生成绩评价模型的实施流程图

2.1 数据采集和预处理

数据挖掘要有明确的数据分析对象，我们的挖掘对象是某高校教务管理信息系统抽取近几年的计算机专业的程序设计课程的期末成绩数据，这些信息来自于学生基本信息表、学生成绩信息表、课程信息表及学生课程评议表，见表1，最终的分析数据要从这四个表中提取。对这四个表进行以下的数据预处理：

表1 表结构

2.1.1 数据集成

数据集成是将在不同数据表中相关的数据集合在同一个数据表中。将以上四个表通过SQL语句合并成学生成绩分析表。由于学生成绩分析表中的属性字段很多，而有些属性和数据挖掘任务相关性小或存在冗余，为了减少不必要的计算开销，应当删除这些属性。选择期末成绩、实验成绩、试卷难度、教师评价、感兴趣否这些属性作为决策树模型的依据。

2.1.2 数据清洗

决策树中节点的测试输出取决于单个属性的取值，如果训练样本集或测试集中某个样本数据的属性值缺失时，会导致当前节点的测试输出异常。学生成绩分析表中，一些记录的属性为空缺值，可以采用直接忽略元组法，将其记录舍弃。学生缺考或作弊，他们的成绩为无效数据，也应当进行删除。

2.1.3 连续属性离散化

学生成绩分析表中的属性取值大都为连续值，不利于分类，应当对这些连续属性值进行泛化操作，将其转化为离散值。教师评价、学生成绩的值均为百分制，采用局部择法将其离散为类别值。例如：优（85分以上）、良（70—85分之间）、差（70分以下）；试卷难度取值为（0，1）之间的值，值越大，表明试卷越容易，将其离散为类别值。例如：高（0.4以下）、中（0.4-0.7之间），低（0.7以上）。为了直观，将各个属性名及其值用编号来替代，见表2。

表2 属性及值代号

2.2 属性信息增益率计算

信息增益率用于确定属性分类，计算信息增益率的公式为：

在构建学生成绩分析决策树过程中，信息熵、集信息熵、信息期望值、信息增益、分裂信息、信息增益率等计算步骤如下：

①根据公式（1），计算训练集中分类属性的信息熵；

②根据公式（1）,计算其它属性的值所划分的子集信息熵；

③根据公式（2），利用②中的结果计算每个属性的的信息期望值；

④根据公式（3），利用①③的结果计算每个属性的信息增益；

⑤根据公式（5），计算每个属性的分裂信息；

⑥根据公式（4），利用④⑤的结果计算各个属性的信息增益率；

2.3 建立学生成绩分析决策树

本文以预处理后学生成绩分析表中记录作为训练样本集，以总成绩C1，C2，C3作为分类属性，采用局部择优法对连续属性离散，采用上述①-⑥步骤计算各个属性的信息增益率，结果“实验成绩”属性为最大信息增益率，因此成为该决策树的根结点，并根据它的属性值类别建立树的分支，对每个分支重复子树的创建步骤，直至结点的训练样本属于同种分类属性。形成的学生成绩分析决策树如图3所示。

图 3 学生成绩分析决策树

2.4 修剪决策树

在创建决策树时，由于训练集中的样本的噪声和离群点，导致一些分枝存在异常，为了提高决策树的可用性，降低树的复杂度，必须对决策树进行剪枝。设T为原始树，Ti1是由Ti中一个剪枝树， Ti,Ti1,ti2,…, tik分别是第i次对Ti的可能剪枝结果，可采用公式(6)的评价函数筛选出一种最好的剪枝形式。

M是剪枝树分类错误增加数，N是总样本数，L(S) 是被剪枝的叶结点数。用相同的样本集对各剪枝树T1,T2,…,Ti测试并计算其分类错误率，最优剪枝决策树是错误率最小的剪枝树。本文采用后剪枝方法，利用公式（6）对图3的决策树进行剪枝优化，得到剪枝后的决策树，如图4所示。

图 4 修剪后的决策树

Fig.4 The decision tree after pruning

2.5 生成分类规则

决策树最大优点是可以直接提取分类规则，从根结点到每个叶子结点都一一对应相应的分类规则，根据图4，抽取部分规则如下：

①IF B=c1∧C=d3 THEN A=c1；

②IF B=c1∧C=d2 THEN A=c1；

③IF B=c1∧C=d1∧E=y∧D=c1 THEN A=c1；

④IF B=c2∧C=d3 THEN A=c1；

⑤IF B=c2∧C=d2∧D=c1 THEN A=c1；

⑥IF B=c3 THEN A=c3；

⑦IF B=c2∧C=d1∧E=n THEN A=c1。

从以上分类规则可以得出，不论试卷难度多大，只要学生的实验成绩好，那么学习成绩好的概率就高；在学生实验成绩中等时，学生对课程感兴趣度决定了最终的学习成绩。因此，在教学中，特别是理工类的学生，如何加强实践环节的培养，激发学生对课程的兴趣，是教学改革的重中之重。

2.6 实验及结果分析

本文采用某高校2005~2012年计算机专业数据库原理的成绩数据，共900份，其中600份作为训练数据，300份作为测试数据。训练数据是用来生成决策树和分类规则，测试数据用来对决策树进行测试评判它的准确率。实验环境为Pentium 4 ,2.80GHZ CPU, 512MB内存，Windows Xp Sp3。用以上数据对C4.5算法和基于局部择优离散技术的C4.5改进算法进行测试，测试结果如表3所示，两种算法的分类准确率均较高，但是基于局部择优离散技术的C4.5改进算法运行效率要高出C4.5算法将近16.67%。表明当样本集中连续型属性离散类别为2-3个时，基于局部择优离散技术的C4.5改进算法算法的性能要好于C4.5算法。

表3 评判分类规则

3 结论

本文采用基于局部择优离散技术的C4.5改进算法构建学生成绩分析树型结构，并利用后剪枝算法对决策树进行了优化，提取了学生成绩分析的分类规则，并评判了该分类法的准确率，取得了较好的挖掘效果。学生成绩决策树推理出的潜在规则为教学质量改革提供了决策依据。随着数据挖掘技术的推广及改进，数据挖掘技术在教育行业的应用将不断深入。

[1] 孙晓莹,郭飞燕. 数据挖掘在高校招生预测中的应用研究[J]. 计算机仿真, 2012, 29(4):387-391.

[2] 宋雅婷,孟莉秋,孙道层,等. 数据挖掘技术在教学中的应用[J]. 中国教育技术装备,2013, 3:55-57.

[3] 翟立波. 数据挖掘与知识发现[J]. 潍坊学院学报, 2005, 5(2):29-30, 53.

[4] Roiger R J, Geatz M W. 数据挖掘教程[M]. 翁敬农, 译. 北京:清华大学出版社, 2008: 60-85.

[5] 高阳,廖家平,吴伟. 基于决策树的ID3算法与C4.5算法[J]. 湖北工业大学学报,2011(2):54-56.

[6] 栾丽华,吉根林. 决策树分类技术研究[J].计算工程，2004,30(9): 94-96.

[7] 于露,杨亚宁. C4.5 算法的研究与应用[J]. 云南大学学报:自然科学版,2010,32 (S2) :136-140.

[8] 张琳,陈燕,李桃迎,等.决策树分类算法研究[J]. 计算机工程, 2011,37(13):66-70.

[9] 杨学兵,张俊. 决策树算法及其核心技术[J]. 计算机技术与发展, 2007,17(1):44-46.

[10] Zhu Xiaoliang, Wang Jian, Yan Hongcan, et al. Research and application of the improved algorithm C4.5 on decision tree[C].IEEE International Conference on Test and Measurement, Hongkong, 2009: 184- 187.

Improved C4.5 algorithm based on a partial selection of the discrete technology and its application in the evaluation of student achievement

*WU Yu-chun，LONG Xiao-jian

(1. School of Electronics and Information Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China; 2. School of Continuing Education , Jinggangshan University, Ji’an, Jiangxi 343000, China)

For student Performance data in teaching Management System existing consecutive values above normal, intelligent analysis of student achievement cannot be effectively. We propose the improved C4.5 algorithm based on a partial selection of the discrete technology. We also build the student achievement analysis model, which had been optimized by using after pruning algorithm. Furthermore, we also generated classification rules of student achievement. Experiments have shown that the improved decision tree algorithm ensured higher classification accuracy at the same time; the implementation efficiency had been improved. It will help to dig out the potential link between student achievements with a variety of factors and provide basis of decision making for educational reform.

C 4.5 algorithm; discrete technology; after pruning; student achievement analysis model

1674-8085(2013)05-0050-05

TP391

A

10.3969/j.issn.1674-8085.2013.05.012

2013-05-07；

2013-06-10

*吴玉春(1975-），女，江西石城人，副教授，硕士，主要从事数据挖拙、智能算法的研究与应用(E-mail:wuyuchun@jgsu.deu.cn);

龙小建(1971-），男，江西永新人，工程师，主要从事计算机软件开发与设计、数据库技术研究(E-mail:jianninglong@163.com).