ECOC多分类算法在慕课数据挖掘中的应用

潘丽芳，谢书童，曹秀娟

(1.集美大学理学院，福建 厦门 361021；2.集美大学计算机工程学院，福建 厦门 361021)

0 引言

近年来，随着慕课在线学习课程迅速普及，更多的学生得到了便捷高效的学习体验[1]。然而，慕课动则成千上万名学生在一起大规模的学习模式，与现代教育理念中学生学习的个性化需求形成了尖锐的矛盾。在慕课规模化教学条件下，合理引导并实现学生的个性化学习是一个教育和学术并重的问题，具有重要研究价值[2-3]。

蒋卓轩等[4]对北京大学在Coursera平台上开设的6门慕课的学习行为数据进行分析与挖掘。结果表明，基于学习行为特征的数据分析能有效地判别一个学生最后能否获得课程证书。Qiu等[5]基于清华大学学堂在线的慕课数据，提出用潜在动态因子图模型(latent dynamic factor graph，LadFG)来预测学生作业情况，以及能否通过考试获得证书。Xu等[6]通过分析学生在慕课平台上的活动日志，归纳出不同学生的学习动机，设计出基于支持向量机(SVM)的分类算法预测学生能否取得证书。Zhang等[7]对北大《数据结构与算法》与《计算机导论》两门慕课，汇聚多源异构数据，分析学生的学习内容，识别课程中的重要概念，通过学生测验数据来评估学生的知识状态，并设计出算法预测学生是否中途退课。Yu等[8]根据学生的视频点击流日志，识别出学生的七种认知参与模型，设计了基于K最近邻(KNN)、SVM、人工神经网络(ANN)的分类算法，预测学生能否通过课程考试。

为了提高传统线下课程与线上慕课的教学效率，Meier等[9]利用课程的历史教学数据(主要包括作业、小测、期中考试等)，预测学生在后继学习中的可能表现(好/差)，为提前对学习不佳的学生进行教学干预赢得时间。Xu等[10]设计了一个双层结构的集成分类系统，对学生不断变化的学习状态进行动态预测，并提出了一种基于潜在因子模型和概率矩阵分解的数据驱动方法，发现了课程的相关性，从而提高预测准确度。Ulloa-Cazarez等[11]提出遗传规划(genetic programming，GP)算法预测学生能否通过期末考试。为了识别出学习《数字设计》课程有困难的学生，Hussain等[12]使用ANN与SVM等算法，利用学习系统上的学习行为数据，预测出学习困难的学生，方便提前教学干预。

上述研究工作大多根据慕课中的学习行为数据，设计分类预测算法来预测后续学习成效，即预测学生能否通过考试、提前退课、顺利毕业等，这实质上是一个二分类问题的研究。然而，学生学习成效的多分类预测比二分类更有利于学生个性化教学的实施，但多分类预测难度较大，目前国内外有关慕课数据的多分类预测的研究很少。本文提出基于数据复杂度的纠错输出编码(error correct output codes，ECOC)多分类算法，对慕课数据进行挖掘，以期实现对学生成绩的多分类预测，即预测学生成绩的四个等级(优、良、合格、不合格)，为个性化和差异化的教学干预提供理论基础与技术条件。

1 基于数据复杂度的ECOC分类算法

本文提出的基于数据复杂度的ECOC分类算法，首先利用数据复杂度降低两个分类的复杂度，然后，利用ECOC算法实现多个二分类预测，从而实现多分类预测。该算法主要分为二个步骤：基于数据复杂度的二分类调整方法;基于ECOC的多分类预测。

1.1 基于数据复杂度的调整方法

数据复杂度是通过分析数据特征来衡量数据样本分类的难易程度[13-14]。数据复杂度越高的分类问题，算法越难以实现正确的分类预测。因此，本文采用了多种数据复杂度方法降低二分类问题的分类复杂程度，它们分别是费希尔判别率(F1)、交叉重叠体积(F2)、重叠区域数据点数(F3)、同类实例与异类实例距离比(N2)、基于最近邻分类器的错误率(N3)、INN分类器的误差率(N4)、非线性分类器的非线性特点(L3)，以及基于质心匹配的方法(C1)[13]。

1.2 ECOC多分类算法

ECOC多分类算法最早由通信领域为解决信号传输问题而提出，其处理问题的关键在于选择高效优秀的编码策略和解码策略[15]。ECOC多分类算法的主要策略是将多类问题转化为多个二分类问题进行求解。ECOC多分类算法包括三个基本步骤：编码、训练、解码。

编码策略的设计是为了得到实现多类分解和基分类器集成的编码矩阵。编码矩阵是由二元(-1，+1)或者三元(-1，+1，0)组成，其中-1代表负类，0代表对应的类在分类时被忽略，+1代表正类；行向量表示一个类别，列向量表示一个基二分类器。此外，编码策略分数据无关和数据相关两种类型。数据无关主要是指编码时不依赖数据样本，数据相关是指编码时样本特征的分布紧密联系着编码矩阵。数据无关算法包括一对一(One Vs.One, OVO)、一对多(One Vs.All,OVA)、稀疏随机(sparse random)和密集随机(dense random)策略。数据相关算法包括DECOC、Forest-ECOC、ECOC-ONE等。编码矩阵行列应尽可能不同，减少基二分类器和码字之间的相关性。训练步骤就是通过训练数据对ECOC及其相应的基分类器进行训练，从而调整ECOC及其基分类器的参数。

解码策略是指在测试某个样本时，每个基二分类器都会产生一个相同长度的向量作为输出，然后计算出输出向量与编码矩阵中的码字之间的距离，选择距离最小的码字作为最终结果，并将相应的类别标签赋予该样本。解码策略包括AED、ED、ELB、ELW、HD、LAP、LLB等。

1.3 算法框架

首先，基于数据复杂度的ECOC分类算法需将所有的类别随机分成数量尽可能相同的两组，然后对每个类别进行相同的数据复杂度评估，再交换两个组中具有最高复杂度的两个类，从而降低两个组组内整体的数据复杂度，提高对应基二分类器的泛化能力。通过降低类别之间的数据复杂度，使得分类算法更容易区分不同类别，从而达到提高预测准确率的目标。在追求降低组内整体复杂度时，F1和F3两种数据复杂度评价指标是相反的，应尽可能提高组内F1或F3指标的值才能降低复杂性。不断调整以上类别分组过程以达到最优分配，即组内数据复杂度达到最低，形成类别树形分布。将节点编码为+1或-1(没有参与分类的节点编码为0)，形成编码矩阵的一列，得到编码矩阵后，再用训练分类器对样本进行预测，算法整体框架如图1所示。

2 实验结果与分析

2.1 数据集与实验参数设置

收集并整合三所高校的计算机基础课程的慕课数据，预处理后的类别数量、特征数量、样本数量如表1所示。根据学生的期末成绩，把学生样本划分成四类:分数位于0(含0)到60之间判为第4类，分数位于60(含60)到75之间判为第3类，分数位于75(含75)到85之间判为第2类，分数位于85(含85)到100(含)之间判为第1类，亦即为不合格、合格、良与优四个等级。该课程的知识点包括硬件系统组成、操作系统与常用软件、音频和图像处理、数据库技术、算法、无线通信技术、加密解密算法，以及网络安全等。将相应的知识点做成教学视频放于慕课平台供学生学习，且每章均有课后习题，另有阶段性小测，以巩固学生对知识点的掌握。本研究收集了学生在慕课平台观看教学视频的行为数据(包括访问时间、访问时长、所用电子设备)、教学视频中的答题数据、章节作业数据、小测数据，以及线下期末成绩等大量细粒度的学习行为数据。

表1 学生慕课学习行为数据集

算法在Matlab上实现，并调用Sklearn工具包。为充分验证算法的有效性，实验均采用十折交叉法进行测试，取平均值作为评价标准；均采用了两种基二分类器，即SVM和朴素贝叶斯(NB)；所有算法的解码策略均采用ELW(即指数损失加权解码)方式。五种传统ECOC算法，即编码策略为OVO、OVA、DECOC、ECOC-ONE、Forest-ECOC的均进行了相应的实验，以对比本文提出的基于数据复杂度的ECOC与传统ECOC的算法性能。

2.2 实验结果分析

如表2和表3所示，准确率最高的实验结果采用下划线并加粗标识。从表2基于SVM的ECOC算法的预测结果可以发现：在学校A数据集上，基于数据复杂度的ECOC算法和其他ECOC算法性能相近，准确率在81%左右；在学校B数据集上，基于质心匹配的数据复杂度C1的ECOC算法预测准确率最高，达到73.32%，与基于数据复杂度的ECOC算法性能相近，但比传统ECOC算法准确率平均提升约0.6%；在学校C数据集上，基于质心匹配的数据复杂度C1的ECOC算法获得最高准确率，可达73.55%，基于数据复杂度的ECOC算法相比其他ECOC算法准确率平均提升约0.51%；在所有编码方式中，基于质心匹配的数据复杂度C1的ECOC算法获得最优平均准确率为75.95%。综上分析可得，基于数据复杂度的ECOC算法相比于传统ECOC算法具有更优的性能。

表2 基于SVM的不同ECOC算法的准确率对比

基于NB的ECOC算法的结果如表3所示。在所有算法中，基于最近邻分类器的错误率数据复杂度N3的ECOC算法在三个数据集上平均分类准确率最高，达到68.95%。在学校A数据集上，OVA算法取得最好的准确率，即71.56%，其余ECOC算法的准确率相近；在学校B数据集上，DECOC算法取得最好的准确率，即70.26%；在学校C数据集上，基于最近邻分类器的错误率数据复杂度N3的ECOC算法取得最好的准确率，即67.63%。从平均准确率上看，基于数据复杂度的ECOC算法和传统ECOC算法并没有明显的差距。

由表2和表3的结果可得，在学校A、B、C三个数据集上，基于SVM的ECOC算法的性能明显优于基于NB的ECOC算法，平均预测准确率分别提高了约11%、4%、6%。由图2可以看出，基于SVM的ECOC算法预测的平均准确率(三个数据集的准确率平均值)明显优于基于NB的ECOC算法。进一步可以发现，在采用SVM为基分类器情况下，ECOC算法结果总体波动较小，其中基于数据复杂度的ECOC算法性能更加稳定，且优于传统ECOC。相反地，在基于NB分类器情况下，ECOC算法准确率波动较大，其中基于数据复杂度的ECOC算法效果较好。

表3 基于NB的不同ECOC算法的准确率对比

3 结论

本文收集并整合三个高校学生的慕课学习行为数据，设计了包括多种基于数据复杂度的ECOC算法，并与传统ECOC算法在内的十多种基于ECOC的多分类算法进行比较。实验结果表明，相比于传统的ECOC算法，基于数据复杂度的ECOC多分类算法预测精度更高、更稳健，其对学生成绩进行四个等级的预测，平均准确率可达75%以上，为提前教学干预提供了参考。

未来可考虑用更多的数据复杂度算法来计算三所高校数据的复杂度，衡量数据内部分布情况。此外，算法中基分类器的多样性影响着ECOC算法的性能，因此，丰富基分类器的多样性也是值得深入研究的方向。