C4.5算法在计算机等级考试管理中的应用

2021-05-31郑秀月

中阿科技论坛(中英文) 2021年5期

郑秀月

（福州黎明职业技术学院,福建福州 350001）

1 C4.5算法介绍

C4.5算法是决策树技术中较为典型的、应用广泛的分类算法，是ID3算法的提出者J.R Quinlan根据ID3算法存在的一些问题提出的一种改进算法[1]。C4.5不仅具备ID3算法的所有优点，还可以处理离散类型、连续类型的属性；在生成决策树时，可以采用边构造树边剪枝或者完整的树生成之后再进行剪枝的策略，也可以采用不同的剪枝技术如删除子树或结点的方法来避免生成不平衡的树[2]。

2 C4.5算法的改进

2.1 C4.5算法的不足

C4.5算法中，在生成决策树的过程中需要花大量的时间进行信息增长率的运算，对决策树的生成效率产生了很大的影响。它与ID3算法一样仍然是基于“贪心”策略的搜索方式，通过找到每棵子树的最优解，然后构造出一棵完整的决策树，这样只能保证子树是最优的，最后生成的决策树未必能达到整体最优。

2.2 C4.5算法的改进

在C4.5算法中，计算分类及测试属性的信息量时，涉及了对数运算，在进行数据挖掘时要反复地调用对数库函数，造成计算复杂度大，时间成本高等问题。这里，针对信息量的计算方法提出了改进措施。

假设在样本数据中，类“YES”的有m个，类“NO”的有n个，则该样本分类属性的信息量计算方法如公式(1-1)所示。

以A为测试属性，假设A有p个不同的取值，则它的信息量计算方法如公式(1-2)所示。

根据高等数学中的泰勒公式、麦克劳林公式和等价无穷小的思想，可以知道当x很小时，ln(1+x)≈x，因此可以得出如下公式(1-3)和公式(1-4)所示。

将公式(1-3)和(1-4)代入公式(1-2)可得如下公式(1-5)所示。

计算时，将公式(1-5)中的常数省略，得出如下公式(1-6)所示。

又因为属性A对D的分裂信息量计算方法如公式(1-7)所示。

因此可以得出信息增益率如下公式 (1-8)所示。

3 利用改进的C4.5算法生成计算机等级考试成绩的决策树模型

3.1 确定数据挖掘对象和目标

以福州某职业院校2019～2020学年计算机二级等级考试成绩为研究对象，随机抽取了1 100名学生的成绩。同时设计了一份问卷调查。希望对这两份表格的分析挖掘，从中找出影响学生成绩的因素，对今后教学工作的开展起到积极的指导作用。

3.2 数据采集

共收集了3张表格数据，分别为学生成绩表、平时作业情况表和问卷调查表。其中学生成绩表由准考证号、姓名、性别和成绩等字段组成，数据由学院的教务处提供，成绩为计算机二级等级考试成绩。平时作业完成情况表由准考证号、姓名、性别和平时上机作业完成情况等字段组成，数据由任课教师根据学生平时完成实验的情况给出的统计表。问卷调查表由准考证号、姓名、对该门课程的兴趣度、原有知识水平程度和课后复习巩固时间等字段组成。

3.3 数据预处理

上述所收集的数据如果直接用于挖掘工作，会直接影响挖掘的结果，因此要对收集到的原始数据进行数据清理、数据表合成、数据转换和数据降维等预处理。在数据转换中将连续型的成绩数据转换为离散型的数据类型，将“成绩”一栏用“是否通过”来标识，结果显示“通过”或“未通过”。在数据降维中删除对挖掘结果不产生影响的字段“姓名”和“性别”，保留能唯一标识一条记录的字段“准考证号”即可。预处理后最终生成的数据表如下表1-1所示。

3.4 构造成绩“未通过”的决策树模型

为了找出影响学生计算机等级二级考试成绩不及格的因素，因此将表1-1中的成绩“未通过”的记录提取出来组成新的表格来建立决策树：

表1 -1 学生成绩分析表

3.4.1 计算每个属性的信息量

在成绩“未通过”的学生成绩分析表，与“未通过”相关的属性有“对该门课程的兴趣度”、“原有知识水平程度”“平时上机作业完成情况”和“课后复习巩固时间”。根据公式1-6分别求出每个属性的信息量。

（1）计算属性“对该门课程的兴趣度”的信息量，该属性共有三个属性值，分别为“感兴趣”“不感兴趣”和“一般”，其样本数分别为：“感兴趣”的有305个，“不感兴趣”的有245个，“一般”的有400个。

“感兴趣”的305个样本中，类“YES”的有215个，类“NO”的有90个，可以表示为（215，90），其信息量：

同理计算“不感兴趣”的245个样本中，其信息量info(0,245)=0；

“一般”的400个样本中，其信息量info(175,225)=98.4375；

因此，属性“对该门课程的兴趣度”的信息量

info(兴趣度,D)=63.443+98.4375=161.8805

（2）计算属性“课后复习巩固时间”的信息量，该属性“大于2小时”“1-2小时”和“小于1小时”对应的样本数分别为165、340和445，分别计算他们的信息量为info(45,400)=40.449、info(200,140)=82.353、info(145,20)=17.576；

因此，属性“课后复习巩固时间”的信息量为：40.449+82.353+17.576=140.378

（3）计算属性“原有知识水平程度”的信息量，该属性共有三个属性值，其对应的样本数分别为：“好”的有275个，“中”的有395个，“差”的有280个，分别计算他们的信息量为info(205,70)=52.182、info(160,235)=95.190、info(25,255)=22.77；

因此，属性“原有知识水平程度”的信息量为：52.182+95.190+22.77=170.142

（4）计算属性“平时上机作业完成情况”的信息量，该属性共有三个值，其对应的样本数分别为：“优”的有305个，“良”的有330个，“差”的有315个。别计算他们的信息量为info(290,15)=14.26、info(100,230)=69.697、info(2,315)=1.9873

因此，属性“平时上机完成情况”的信息量为：14.26+69.697+1.9873=85.9443

3.4.2 根据公式1-7计算每个属性的分裂信息量

属性“对该门课程的兴趣度”的分裂信息量为：

依次分别算出属性“课后复习巩固时间”“原有知识水平程度”“平时上机作业完成情况”的分裂信息量分别为：26278.421、32015.789、33373.421。

3.4.3 根据公式1-8计算各属性的信息增益率

属性“对该门课程的兴趣度”的信息增益率为：

依次分别算出属性“课后复习巩固时间”“原有知识水平程度”“平时上机作业完成情况”的信息增益率分别为：0.99465、0.99468、0.99742。

3.4.4 选取信息增益率最大的属性作为决策树的根结点

综上所述，“平时上机作业完成情况”属性具有最大的信息增益率。因此将其作为测试属性，用“平时作业”来标识，并对每个属性值建立分支生成的决策树。同理，对于各个分支节点用以上的方法进一步进行划分，生成完整的决策树

3.5 决策树的剪枝

决策树的剪枝，就是在单个叶子结点的期望错误率低于相应子树结点的期望错误率时，用该叶子结点来代替一整棵子树[3]。目前，常用的决策树剪枝算法主要有两种即先剪枝方法和后剪枝方法[4]，对上述已生成的完整决策树模型采用了“后剪枝”的方法，通过剪枝后生成的决策树如下图1所示。

图1 决策树

3.6 生成规则

决策树算法很重要的一个优点就是能够直接生成以IF……THEN……语句的形式表示的规则，而且这种形式表示的规则易于被人们理解和接受[5]。从上面决策树中提取的成绩为“未通过”的规则有：

IF“平时作业”=“优”AND“复习时间”=“小于1”AND“原有知识程度”=“中”AND“兴趣度”=“一般”THEN“成绩是否通过”=“未通过”；

IF“平时作业”=“优”AND“复习时间”=“小于1”AND“原有知识程度”=“差”AND“兴趣度”=“一般”THEN“成绩是否通过”=“未通过”；

IF“平时作业”=“良”AND“原有知识程度”=“中”AND“兴趣度”=“一般”AND“复习时间”=“小于1”THEN“成绩是否通过”=“未通过”；

IF“平时作业”=“良”AND“原有知识程度”=“中”AND“兴趣度”=“不感兴趣”AND“复习时间”=“小于1”THEN“成绩是否通过”=“未通过”；

IF“平时作业”=“良”AND“原有知识程度”=“中”AND“兴趣度”=“不感兴趣”AND“复习时间”=“大于1小于2”THEN“成绩是否通过”=“未通过”；

IF“平时作业”=“差”THEN“成绩是否通过”=“未通过”；

IF“平时作业”=“良”AND“原有知识程度”=“差”THEN“成绩是否通过”=“未通过”；

从以上得出的分类规则可以看出，“平时上机作业完成情况”对考试是否通过影响很大。“课后复习巩固时间”也在很大程度上影响着考试是否通过。因此，教师在教学过程中要注重学生的实际动手能力，对学生“平时上机作业完成情况”要即时的进行讲评、反馈，即时解决学生在上机过程中遇到各种问题。同时要督促学生课后多花时间进行复习巩固，加深印象，以此来提高等级考试的通过率。