基于改进C4.5的E-learning教学辅助系统的研究与实现①

谢修娟， 李香菊， 操凤平， 孙 丽

(东南大学成贤学院计算机工程系，江苏 南京 210000)

0 引 言

E-learning (Electronic Learning)，译作"数字化学习"，是指学生利用网络学习平台上的数字化学习资源,进行自主学习的一种全新式以学生为主体的学习方式[1]。在《国家中长期教育改革和发展规划纲要(2010-2020年》的指挥棒作用下[2]，越来越多的高校开始使用E-learning平台，将其作为传统课堂教学的辅助系统，形成线下学习与线上学习融为一体的混合式学习[3]。使用数据挖掘技术对在线学习过程进行学习分析，以提高在线学习的效率，被排在目前影响高校教育的六大信息技术的首位[4]。

孙玉荣等人采用关联规则技术对学生在线学习历史数据进行分析，得到学习行为间的关联[5]；梁燕红用web日志挖掘技术，找出访问频度高的知识点网页，并挖掘出知识点之间的访问序列，从而了解学生的学习需求趋势[6]；针对监督学习和分类问题，赵强利提出选择性集成与增量学习相结合的在线学习模型，利用模式挖掘技术解决选择性集成问题，并给出相关算[7]；攀妍妍将ID3决策树算法用于对学生在线学习信息的挖掘，找出影响学生学习效果的分类规则[8]；武靖娜提出了一个针对大规模分布式网络学习机的数据挖掘应用程序的通用框架，并基于局部学习者间的关系研究了一种高效的在线学习算法[9]。

在借鉴和参考多位学者研究成果的基础上，在自构建的E-learning教辅系统中，引入改进后的C4.5决策树算法，对采集到的学生学习行为数据进行挖掘，构建“学习行为-学习效果”间的决策树模型，并运用此模型对参与在线学习的学生的课程学习效果进行预测，一是便于学生能够及时发现自身学习的不足之处，尽快调整学习行为，二是帮助教师及时发现课程学习中的一些问题学生，早期介入和引导。

1 C4.5算法及其改进

1.1 C4.5算法

C4.5算法由ID3算法改进而来。相较于ID3算法，第一，C4.5算法能够处理连续属性，第二，用信息增益率代替信息增益进行选择属性，有效避免ID3算法在确定分支时容易倾向于取值较多的属性的情况发生[10～12]。C4.5算法[13]的具体步骤如下：

已知数据源样本集D={D1，D2，…，Dn}，D被分为k类，记为类标号集合C={C1，C2,…，Ck}，D中每个样本用一包含p项属性的属性向量(A1，A2,…，Ap)来表示，其中任意一个属性Ai(0≤i≤p) ，假设有v个不同取值。

Step1：对数据源样本集进行预处理，保证每个属性变量都是离散型取值，若存在连续性属性变量，则按照step8中的操作进行；

Step2：计算样本集D对分类C的平均信息熵Entropy(D)； Step3：计算任意的离散属性Ai(0≤i≤p)，划分样本集D的信息熵EntropyA(D)；

Step4：计算每个属性Ai对样本集D的信息增益Gain(A)，即Ai对D进行划分前后信息熵的差；

Step5：计算每个属性Ai对样本集D的信息增益率GainRation(A)，其等于信息增益与分割信息量(SplitInfoA(D) )的商；

Step6：选取信息增益率最大的属性作为决策树的根节点，根节点的每一个不同取值对应一个分支，递归地执行Step2- Step5，选择分支中信息增益率最大的属性作为子节点，以此类推，直至每个分支的属性取值相同，得到叶结点，从而完成决策树的构建；

Step7：根据构造的决策树提取分类规则，对新的数据集进行分类预测；

Step8：C4.5算法处理连续属性时，首先，将连续属性的取值按照从小到大排序，得到属性的值序列{Av1，Av2，…，Avn}，取相邻两个属性值之间的中点作为分割阈值点，值序列{Av1，Av2，…，Avn}有n个属性值，共生成n-1个分割阈值点，每个阈值点将数据集划分为大于阈值和小于等于阈值的两个子集，然后计算每个阈值点的信息增益，选择信息增益最大的阈值点作为最佳分割阈值点，最后计算最佳分割阈值点的信息增益率，并将其作为该属性的信息增益率，跳转至step6。

1.2 C4.5算法改进

C4.5算法在处理连续属性时，需要对n-1个分隔阈值点分别计算其信息增益，这一过程中涉及到大量的对数函数运算，由此预见，当样本集中连续属性数量比较多，而每个连续属性的取值又比较多，算法的计算工作量相当之繁重，从而影响算法的执行效率。为此，提出两点改进措施，第一，运用Fayyad边界点判定原理[14]，减少分割阈值点的判定数量；第二，利用基于泰勒公式和麦克劳林公式得到的等价无穷小理论，将对数运算用线性运算代替，降低计算复杂度。

Fayyad定理：若T使得E(A，T，S)最小，则T是一边界点，其中，A是属性，S为属性的值集合，E表示平均信息熵，T为某一分割阈值点。

边界定理表明，对于连续属性A，离散化后的最佳分割阈值点必定出现在两个相邻且不同类别的边界点处。算法中具体做法是：将某一连续属性的所有取值按照升序排列，然后找出导致类标号发生变化的点，计算前后两个相邻点的属性平均值，作为分割阈值点。例如下面的属性/类别数据：

上述14组数据，如果用传统C4.5算法中的连续属性处理方法，共得到13个分割阈值点，而运用Fayyad定理，得到7个分割阈值点(一条分割线代表一个点)。 可见，当相同类标号集中在一起时，此方法能大大减少分割阈值点的个数，最坏情况下，相邻的两两类标号均不同，此时分割阈值点的个数与传统方法得到的个数相当。

此外，还运用数学等价无穷小理论改进算法，下面来验证该方法的可行性。为简单起见，假设样本集D仅有两个类别，用P和N表示分别D中属于正例和反例的记录个数，那么该样本集能作出正确分类所需要的信息熵为：

根据等价无穷小理论，当x很小时，有ln(1+x)≈x，因此上述式子可简化为：

(1)

任意一个属性A，有v个不同取值，它将样本集D划分为D1，D2，…，DV共v个子集，假设每个子集Di中含有Pi个正例和Ni个反例，则子集Di的信息熵为：

采用同公式(6)相同的处理方法，得到：

(2)

某个属性有v个不同取值，第i个取值对应的样本记录个数为PSi，该值外其它取值对应的样本数据被划到另一个类，样本记录个数记为NSi，则该属性的分割信息量为：

化简后得到：

(3)

改进的C4.5算法在计算信息熵以及分割信息量时，采用仅包含四则混合运算的公式(1)～(3)，而且实际运算中，可将公式中的常数部分忽略，如“2”，“ln2”，因为对同一类数据作相同倍数变化对于判定结果没有影响，如此一来，相较于传统算法的大量对数运算，计算复杂度大大降低，算法的执行效率大大提高。

2 基于改进C4.5算法的E-learning教辅系统

2.1 系统体系结构设计

系统体系结构如图1所示，一切学习/教学活动都是通过用户接口登录后进行，“数据采集和预处理”模块负责收集并处理学生的在线学习数据，存储至用户信息库。“决策分析”模块再从库中提取学习行为数据进行预测分析。

图1 系统体系结构图

2.2 构造决策树模型

2.2.1 数据采集与预处理

实验的数据是E-learning中2016 -2017年第1学期的《C语言程序设计》课程的学生在线学习数据，共计900条。参与挖掘的在线学习行为属性项有5个：在线总时长(Time)、在线单元测试的平均成绩(UnitScore)、在线单元测试的次数(UnitCount)、BBS的参与次数(BBS)、作业提交次数(Work)。将教务系统中调取得到的课程期末成绩(Grade)作为度量学习效果的类别项，成绩使用等级制，分别为A(100-80)，B(70-79)，C(60-69)，D(<60)。表1为经过处理后的部分数据。

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

由于数据采集来源和渠道的多样性，导致存在有些学生成绩缺失的问题，为保证数据的完整性和一致性，在数据预处理阶段需要处理缺失值，处理的方法包括：

(1) 如果是因为缺考或缓考原因导致成绩缺失，将用补考成绩替换缺失值，实在找不到可替代的值，将其置为0或者不及格。

(2) 对于存在多次补考、重考的学生，选择第一次有效成绩，替换缺失值；

(3) 如果学生因为辍学或者转专业原因导致成绩缺失，那么这些学生的数据将被过滤掉，因为他们的数据对于构建学生成绩模型没有意义。

2.2.2 构造决策树模型并导出分类规则

上述的900条数据中，抽取其中的三分之二作为训练样本集，三分之一作为测试样本集，对600条训练集数据应用改进后的C4.5算法构建决策树模型，并使用if-then形式表示分类规则，从树根到叶的每条路径对应一条规则，记为：if Cond1 && Cond2 &&…&& Condn then Class C[15]，其中if部分称为规则前件，是若干属性值的合取，then部分称为规则后件，对应所属的类别。导出分类规则的具体做法是：从树的根节点出发，沿着某条路径上的每个属性值对应规则前件的一个合取项，叶子节点则为规则的后件。本次实验共得到23条“学习行为-学习效果”的分类规则，形如：

(1) if time >43 then A

(2)if 20=8 then B

(3)if 20=95 then A

……

2.2.3 改进算法的有效性评估

为验证分类模型的准确性，本实验中将对剩下的300条测试集中的学习行为样本数据进行预测，获得其成绩等级，并通过验证测试结果与实际情况相吻合的程度来计算分类预测准确率，测试结果如表2所示。

表2 准确性评估结果

从表2的测试评估结果得知，总的预测准确率为87.83%，具有很好的预测效果，因此能够利用改进的C4.5算法挖掘得到的“学习行为-学习效果”分类模型，对未来在线学习的学生的课程学习效果进行预测。

2.3 E-learni ng系统中学习效果的预测

融入决策树技术的E-learning教辅系统能够对课程学习效果提前预测，如图2所示。参与某课程学习的学生能够根据现有的在线学习行为预测课程最终的成绩，同时课程任课教师能够预测所带班级所有学生的课程成绩。对于预测结果不理想的学生，可以根据系统提示信息，如：在线学习时间不足，BBS参与少，作业提交次数少等，作出学习方法的自我调整，或者由教师加以个性化辅导。

图2 学习效果预测

3 结 语

基于Fayyad边界点判定原理和数学的等价无穷小理论，对传统决策树C4.5算法进行了优化，优化后的算法在处理连续属性时能减少分割阈值点的个数，以及用加减乘除运算代替传统算法中大量的对数运算，并将改进后的C4.5算法应用于E-learning教辅系统的成绩预测分析中，以《C语言程序设计》课程为例，对采集到的900条学生历史学习数据，进行分类建模，得出能够有效识别学生学习行为并预测学生未来成绩的决策树模型，这些信息在后续教学和学习中有非常重要的参考价值。融入了学习效果预测机制的E-learning教辅系统，在课程教学和学习实践中有广阔的发展空间，一方面，教师能够根据学生的在线学习数据，随时预测本门课程的学习效果，以尽早发现问题学生，另一方面，学习者自身在学习过程中，利用预测的数据及时发现问题，从而及时调整学习方法等。

[1] 黄海. 高校数字化学习建设和应用推广研究——以中山大学数字化学习“115”模式为例[J]. 现代教育技术, 2013, 23(4):56-63.

[2] 袁贵仁. 国务院关于实施《国家中长期教育改革和发展规划纲要(2010—2020年)》工作情况的报告[C].第十一届全国人民代表大会常务委员会第二十四次会议,2012:58-65.

[3] 陈瑞增. 信息化环境下高校混合式学习探索与实践[D]. 湖北:华中师范大学, 2014.

[4] Siemens G.1st International conference on learning analytics and knowledge 2011.https://tekri.athabascau.ca/analytics/about.

[5] 孙玉荣, 罗立宇, 黄慧华. 数据挖掘在网络教学中的应用[J]. 现代教育技术, 2009, 19(6):104-106.

[6] 梁燕红. Web数据挖掘技术在网络教学中的应用[J]. 科技信息, 2011(22).

[7] 赵强利. 基于选择性集成的在线机器学习关键技术研究[D]. 国防科学技术大学, 2010.

[8] 樊妍妍. ID3决策树算法对教学辅助系统的优化[J]. 齐齐哈尔大学学报(自然科学版), 2016(1):85-89.

[9] 武靖娜, 杨姝, 王剑辉. 一种分布式大数据挖掘的快速在线学习算法[J]. 沈阳师范大学学报(自然科学版), 2016, 34(1):100-104.

[10] 徐鹏, 林森. 基于C4.5决策树的流量分类方法[J]. 软件学报, 2009, 20(10):2692-2704.

[11] 刘兴文, 王典洪, 陈分雄. 一种基于变精度粗糙集的C4.5决策树改进算法[J]. 计算机应用研究, 2011, 28(10):3649-3651.

[12] 苗煜飞, 张霄宏. 决策树C4.5算法的优化与应用[J]. 计算机工程与应用, 2015,51(13):255-258.

[13] Quinlan J R.C4.5：Program for machine learning[M].San Marteo：Morgan-Kaufmann Publishers，1993.

[14] Fayyad U M, Irani K B. On the handling of continuous-value attributes in decision tree generation[J]. Machine Learning, 1992,8(1): 87-102.

[15] 范洁, 杨岳湘, 温璞. C4.5算法在在线学习行为评估系统中的应用[J]. 计算机工程与设计, 2006, 27(6):946-948.