基于Online Judge 进行程序设计类课程实践的混合推荐

2019-03-04肖春芸贺樑窦亮杨静

现代计算机 2019年36期

肖春芸，贺樑，窦亮，杨静

（华东师范大学计算机科学与技术学院，上海200062）

0 引言

近年来，教育的个性化需求越来越受到教育工作者的重视。2018 年4 月，教育部印发的《教育信息化2.0 行动计划》中提出要“探索在信息化条件下实现差异化教学、个性化学习、精细化管理、智能化服务的典型途径”[1]。在计算机专业教学中，对使用信息化工具有着得天独厚的优势，Online Judge（简称OJ，在线判题）平台是其中的典型。OJ 平台最初用于ACM 国际大学生程序设计竞赛中的自动判题和排名，现已广泛应用于世界各地高校学生的程序设计实践、参赛队员的训练和选拔、程序设计竞赛以及各种编程语言、数据结构和算法等课程的作业自动提交判断中。依托OJ平台进行计算机编程实践的优势十分明显，一方面，平台判题客观，反馈及时；另一方面，对学生提交程序的过程记录全面，每个学生的提交记录、提交次数、测试数据通过的详细情况都在平台中有客观记录。

在传统编程教学中，OJ 平台的使用方式一般包括：

（1）教师在OJ 平台上出题，布置编程作业，设定提交期限；利用学生提交程序的通过情况了解教学生对知识点的掌握情况；

（2）组织在线测试，及时客观考查学生的学习效果等。

在此基础上，教师可以给出题目难度分层，建议学生根据自身情况选择不同难度的题目来练习。题目难度一般由教师从对教学内容的理解出发、基于经验进行估算。理想情况下，学生根据由简单到复杂的学习路径完成实践作业题，这样的学习路径有助于循序渐进掌握课程内容并提高编程能力。但在实际教学中，经常发生由于学生间的差异较大导致整体学习效果不佳的情形。例如：部分学生完成实践作业题花费时间多，问题积累后无法跟上教学进度；而少量学生（特别是参加过程序竞赛训练的学生）完成速度快，认为实践作业题缺乏挑战和含金量；部分学生在已学习过的前导课程中有知识点缺漏，很难完成教师给定的任务；另外，还出现一些题目的某些测试点难度大，学生提交反复受挫，降低了学习的积极性。

在某学期的《数据结构》课程中，笔者对开课4 周后OJ 平台上的数据结构课程实践作业题的完成情况进行了分析，发现进度很不均衡，一些典型实例见表1。

从表1 的实例分析看出，虽然教师通过定期布置实践作业题的方式给出了在OJ 平台中的编程练习的学习路径，但学生间的个体差异不容忽视，题目难度的差异也不容忽视。在上例的分析中发现，题集中的第28 题，有一位学生提交了89 次后才通过，主要原因是该题的测试数据量非常大，对算法要求较高。如果学生们在这道题目上反复提交而不能通过，会在时间花费及学习兴趣方面都受到影响。因此，需要给出更个性化和智能化的学习路径，才能有效激发学生的学习兴趣，减少因反复提交失败受挫而放弃的情况发生。

表1 某学期数据结构课程中学生OJ 实践作业题情况分析

因此，我们在程序设计类教学中提出了利用混合推荐的思想，结合以下几个维度为学生进行个性化学习路径推荐的方法：①教师给出的学习路径；②同类学生的学习路径协同推荐；③结合学生上下文信息（做题习惯、时间段、个性等）给出的推荐。在进行个性化推荐时，给出推荐理由，根据学生对推荐理由的认可度反馈来动态更新推荐算法的权重参数。同时，基于协同推荐的思想建立学习“群组”，有利于碰到同类问题的学生之间的交流。综合上述方式，以期对学生的学习兴趣、信心和效率等产生正向的促进作用。

1 工作基础和现状分析

1.1 EOJ及编程类课程实践题集

本校计算机专业建设的OJ 平台称为EOJ[2]，已支持C、C++、Java、Python、Pascal、PHP 等10 多种语言的编程解题，属于国内领先的、支持语言较多的OJ 平台。平台最初是为了训练本科生参加程序设计竞赛而设计开发的，目前本专业将大部分专业课程的上机练习和考试建设在EOJ 中，既真实地考查学生的编程能力，又方便教师的教学管理。目前基于平台的程序设计类课程有：《程序设计基础》、《程序设计能力实训》、《数据结构》、《算法分析与设计》。这些课程2018-2019学年在EOJ 平台上的上机情况如表2 所示。

表2 EOJ 平台上的课程开设情况

从表2 的数据分析得到，在每门课程中，每道题目的平均提交次数均大于学生人数，说明学生在一道题目上都多次提交。

在程序设计类课程的教学中，我们发现有很多课程知识点有叠加的部分，我们把不同课程的知识点标签进行了集中梳理，尽量做到同一个知识点用同样的标签进行标记。本课题将分析课程的提交日志，进行个性化学习路径的推荐。

1.2 学习路径

学习路径是个性化学习中的核心部分，大量研究者从不同的视角对学习路径的产生进行了研究。目前已有研究工作中需要进一步改进的问题包括：①学习路径中的学习内容粒度较粗，常见的仅为课程序列和知识点序列；②路径缺乏动态性；③路径产生中的推荐原因不够清晰。本文将探索如何进行细粒度的推荐，并给出推荐理由，根据学生的认可度动态调整推荐策略，生成个性化的学习路径。

1.3 推荐算法

自推荐算法被提出以来，先后有很多改进方法，其中经典的方法有协同过滤方法、矩阵分解方法、混合推荐方法及近年来流行的基于深度学习的方法等。这些算法中已有一部分被尝试用于OJ 平台的题目推荐中。文献[3]中的工作依据用户是否已经成功解决相应的问题及用户做题提交次数与阈值的大小关系对用户进行详细的划分，使用Jaccard 测量两个集合的交叠率，并将其作为相似性函数测量两位用户之间的相似度。文献[4]中的工作在之前研究的基础上添加了噪音处理技术，使用Simple Matching Coefficient（SMC）函数作为相似性函数得到目标用户的最近邻，并使用最近邻数据进行相关题目的推荐。此外，在OJ 推荐上还存在一些其他的方法，如文献[5]中提出的基于关联规则挖掘的方法，当目标用户解决一道题目之后，算法可根据题目之间的关联规则为用户生成下一题的推荐。

混合推荐算法是将几种推荐算法进行融合，算法既可以同时采用多种推荐技术给出多个推荐结果供用户参考选择，也可以将多种推荐技术进行加权得到一种推荐结果。算法还可以将不同推荐方法产生的特征进行相应的融合得到最佳的推荐。本文的探讨背景是特定课程中的细粒度学习路径推荐，将采用混合推荐的思想来实现个性化学习路径推荐。

2 基于OJ平台的编程实践类课程学习路径混合推荐

2.1 总体结构

基于OJ 平台的混合推荐的总体思想是：在教师给出的学习路径基础上，将用户（即学生）自身的因素考虑在内，结合基于用户的协同过滤方法和上下文信息（时间、登录的设备、情绪等因素）动态产生学习路径，并同时生成推荐理由，以便用户根据自身的需求选择合适的题目作为“下一题”。另外，教师和学生都可以对推荐结果进行评价，相关的评价信息用于动态调整混合推荐中各部分权重，以获得越来越准确的推荐效果。图1 所示是混合推荐总体思想的示意图，后续分节具体阐述各部分。

2.2 教师给出的学习路径

作为应用于特定课程的学习路径推荐，由教师首先根据课程知识点结构给出基础学习路径。学习路径包含3 个关键要素：知识点的前后关联、题目难度和跳转条件。在本文的研究中，借助基础Petri 网结构来给出学习路径的可视化表示：

（1）结点：每个结点表示OJ 平台中上机实践题集的一道题目，可以在结点上标记难度值和相关知识点等属性；

（2）变迁：若题目涉及的知识点之间具有前导和后续的关系，则在它们之间增加一个变迁；

（3）变迁规则：变迁规则指的是激活变迁的若干条件。例如，变迁t1 有n 个输入结点，可以定义这n 个结点中的80%完成即激活变迁。变迁被激活后，学生可以做变迁的输出结点对应的题目；变迁规则也可以根据题目难度进行定义，例如完成了难度值大于阈值的题目后即可以激活变迁。

教师在课程教学中，首先需要对OJ 中编程练习题的所属知识点进行分类和相互关联的梳理，基于这些分类，教师给题目打上标签并根据经验预估难度。对于表示一道题目的结点来说，其属性包括：题目编号、知识点标签和难度。最后，根据学习顺序、难度层次，把结点通过“变迁”关联起来，即形成了教师给出的学习路径。

以《数据结构》课程的实践题集为例，图2 所示是《数据结构》课程中教师在“线性结构”部分给出的链表学习路径的示意图。图中T1、T2、T3即为变迁，表示学习的先后顺序。每个变迁根据需要进行规则叠加。在T3 上，目前设置的规则是“完成题目1007 或题目1014”可激活变迁，这表示完成两道题目中的一道就可以进入下一个题目。但是对于不同的学生，做题习惯可能不同，有的学生希望在一个知识点上进行多道题目的练习以夯实基础，而有的学生乐于挑战更有难度的题目。因此，在这个教师给出的路径上如何增加个性化推荐是本文要研究的主要内容。由于要单独采集学生个体的偏好比较困难，而平台已经积累了大量的提交记录，所以我们选择使用协同推荐的思想来完成推荐。

图1 混合推荐总体思想示意图

图2 教师给出的链表部分学习路径示意图

2.3 基于用户的协同过滤推荐算法

以基于用户的协同过滤方法为基础，可以根据目标用户解题时的尝试提交次数和最后解题结果找出和目标用户相似的n 位用户，根据这最相似的n 位用户已经做过并最终通过的题目且目标用户未做过的题目为目标用户生成Top-k 道题推荐。这部分使用的推荐算法的关键步骤如下。

（1）创建用户-题目的0/1 二进制矩阵M[u,p]，如果用户解题成功，则结果为1，否则为0，见表3，以用户U1 为例，该用户成功解题P1～P4,P6～P9，但P5,P10没有通过。放缩到-1～1 的范围中，结果（保留2 位小数）见表5。

表3 用户-问题二进制矩阵M[u,p]

X_norm=(X-X_min)/(X_max-X_min) （1）

表4 用户-问题扩充矩阵

表5 用户-问题扩充矩阵归一化结果

（2）使用用户解题时的尝试提交次数细粒度地表示用户-题目矩阵并生成矩阵，以获取精确的相似用户。其中，若用户解题成功，则使用解题成功前的尝试提交次数正数表示，反之使用尝试提交次数的负数形式表示，0 表示未进行过提交，见表4。

为便于计算和统计，将M1[ ]u,p 取绝对值后，对每个问题按照公式（1）进行归一化计算，计算结果加上原来对应的正负号后生成矩阵M2[ ]u,p ，M2 矩阵将数据

（3）使用归一化后的用户尝试提交次数作为用户的向量表示，基于余弦相似度函数，利用公式（2），求解用户u,v 之间的相似度，并生成相应的相似度矩阵。

利用上式得到的用户之间的相似度矩阵见表6。

表6 用户-用户相似度矩阵

以上述用户之间的相似度矩阵为例，对于用户U6，最相似的三位用户为：U4、U3 和U1。

（4）遍历目标用户在二进制矩阵M[u,p]中分数为0的题目，将目标用户U6 前n 位相似用户做题情况利用公式（3）进行求和得到题目的推荐分数，将推荐分数降序排列取前k 道为用户生成推荐。

以用户U6 为例，最相似的前3 位用户为U4、U3、U1，将其代入公式（3）中，得到对于用户U6 未做或未提交通过的题目P6、P7、P8、P9、P10、P5 的系统推荐分数，分别为2.417、0.722、2.417、2.417、1.695、0.0。若取k=3，本例中即得到协同过滤推荐算法结果为UserCFtopk={P6，P8，P9}。

2.4 上下文相关策略

除了教师给出的学习路径及基于用户协同的过滤推荐算法产生的若干候选题之外，在生成个性化的学习路径时还应该考虑用户的上下文信息。例如，当前时间、用户的本次登录持续在线时间、用户的性格特征等。在本次教改尝试中，我们考虑了三个方面的内容。

（1）时间因素：在较晚的时间段（0 点～8 点）或者用户本次登录持续在线超过平均值后，将协同过滤得到的推荐列表按照题目原有难度升序排序，生成一个新的推荐列表Context-topk 用于题目推荐，即在“凌晨或用户在线时间过长”这个上下文环境中，倾向于将简单的题目优先推荐，以调节学生的学习强度。

（2）反馈信息：个性化的学习路径是否能符合学生的需求，需要在实际使用中不断探索。因此，我们在推荐算法中设置了反馈环节。学生每次在推荐的题目中选择某道题目开始练习，如果在此次登录中成功提交，则认为推荐成功。每道推荐成功的题目在上下文相关策略中都会增加一次权重，可以按照这个策略对协同推荐的结果进行再次排序。

（3）知识点补缺：在我们的EOJ 系统中，每门程序设计类课程的练习题都给出了“知识点”标签，在此基础上，算法会选择一些非本课程题库中的同类知识点题目放入候选推荐列表推给学生，便于需要复习和夯实基础的学生快速找到同类练习。

2.5 推荐结果生成

本文工作最终生成的推荐结果是一个细粒度的个性化学习路径。根据学生解题情况，在教师给出的学习路径上求出后续的结点。同时，使用协同过滤推荐算法得到排序后的k 道题目，将包含这些题目结点的学习路径子图取出，生成的个性化学习路径推荐。在此基础上，附加推荐理由及根据上下文相关策略生成的排序结果，帮助学生选择合适的题目继续学习。

3 应用案例

在华师大计算机专业的专业课程《数据结构》的教学中，我们使用了混合推荐算法为每个学生的每次登录生成个性化学习路径推荐。课程题库共100 道编程练习，有知识点标签和难度标记，教师在布置作业时给出了根据知识点生成的学习路径。如图3 所示，在某位学生的一次登录中，根据系统中的做题记录，他已成功提交了1009,1006,1007 三道题，依据教师给出的学习路径，他后续可以选择的题目是1014,1106,1064,1065。依序后台的协同推荐及上下文相关推荐，排序后的前3 道题目是UserCF-top3={1014,1065,1064}。

据初步统计，在EOJ 平台上实施了个性化学习路径混合推荐后，《数据结构》课程中，学生通过推荐链接点击进入下一题的比例占70%，在学期结束时练习题集的完成比例比上一学年上升约10%。