程序在线测评系统的知识图谱构建与应用

宋玮情，崔焕庆，杨峻铸

（山东科技大学计算机科学与工程学院，山东 青岛 266590）

0 引言

随着大数据时代来临，数据价值日益增加。面对多样化的数据形式，传统关系型数据库只能处理简单的数据关系，而知识图谱能高效地存储和应用复杂的关系知识，受到了学者们的广泛关注和研究，目前已成为知识应用和资源管理的重要技术之一［1］。知识图谱由节点和边组成，其中节点表示概念和实体，概念指抽象出的事物。实体指具体事物，基本特征通过属性表示；边表示实体与概念之间的关系。知识图谱本质是一个具有属性的实体，通过关系相互连接所构建的网状知识库，并以结构化的形式描述客观世界的概念、实体和两者之间的相互关系［2］。因此，知识图谱不仅表示语义关系，还能联系各类信息构建关系网络，从“关系”的角度分析问题。

近年来，传统课堂教学模式存在教师教学强度大、学生学习效率低、教学资源利用率低等问题。为了解决上述问题，提出了程序在线评测（Online Judge，OJ）系统，该系统在程序设计等课程的教学、竞赛中受到广泛应用，获取了海量的数据资源，这些资源是计算机教育的重要组成部分［3］。如何从数据资源中分析出有价值的信息辅助教学是目前的研究热点。基于此，本文结合知识图谱对OJ 系统的数据进行处理，构建OJ 知识图谱，并通过挖掘、分析数据，为个性化教学和学习提供数据支撑，最后以个例分析的形式讨论OJ知识图谱对学情分析与路径规划的实际应用价值。

1 相关工作

知识图谱由三元组表示，表达式为head,relation,tail，简记为h,r,t。其中，h和t分别表示三元组的头实体和尾实体，r表示头实体和尾实体之间的关系，每个节点和关系都通过键值对（Key-value）进行表示［4］。知识图谱可通过关系型数据库、RDF 三元组库和图数据库进行存储。其中，图数据库是基于图形式存储的新型非关系型数据库，具有存储灵活、查询高效等优势，适合表示如（实体，属性名，属性值）、（实体1，关系，实体2）等形式数据，并且关联查询无需复杂操作［5］。

马腾等［6］建立了个性化教学知识图谱，将知识图谱融入教师备课、课堂教学、课下作业布置、课外辅导等一系列教学环节当中，自动为学生提供感兴趣的学习内容，实现了精准化和个性化教学。黄梅根等［7］创建了初、高中知识图谱，基于知识图谱使用改进的认知诊断模型诊断学生对特定知识点的认知程度。Yan［8］以“国际贸易实务”课程为研究实例，通过融合教学理论与教学资源构建知识图谱，帮助学生提高学习效率；通过培养逻辑思维能力和改进教学方法，提高教师教学水平。Zheng［9］从MOOC 网站上获取课程的相关信息，对实体和关系进行提取，构建高等教育知识图谱。

本文基于Neo4j 构建OJ 数据的知识图谱，给出了OJ 数据的预处理过程。然后，Web 端通过可视化方式展现OJ 数据的网络关系，进一步分析OJ 知识图谱在学情分析、个性化教学和学习方面的应用。

2 OJ 知识图谱的本体设计

为了构建实用性强、结构合理的OJ 知识图谱，本文设计主要从2个方面考虑：①OJ系统中实体和关系的组织；②现实应用对OJ 知识图谱的功能需求。OJ 系统中包含的节点种类较少，但节点之间的关系数量很多，需要设计明确的知识架构作为创建知识图谱的基础［10］，即定义OJ 知识图谱中包含各实体的概念以及它们之间的关系。如表1 所示，OJ 知识图谱中主要包含测试、题、学生、老师4 类实体，为了准确描述各实体信息，定义了每类实体的相关属性。实体属性分为对象属性和数据属性，其中对象属性描述实体之间的关系，值为相关的另一实体；数据属性表示实体的属性，值为XSD（XML Schema Definition）的数据类型。基于上述设计，将各类实体和关系相互组合构成了一个纵横交错复杂的知识图谱，如图1 所示（彩图扫OSID 码可见，下同）。

3 构建OJ 知识图谱

3.1 数据采集

首先需要采集、分析数据。OJ 系统使用关系型数据库存储数据，先将数据以逗号分隔的CSV 文件导出，为了防止乱码，所有CSV 文件格式都使用UTF-8 进行编码。如表2 所示，文件存储了OJ 系统的实体、关系及它们之间的属性，每条记录都拥有唯一的ID 属性，然后利用Neo4j 中Cypher 的LOAD CSV 命令将数据导入至Neo4j。

Table 1 Entity attribute table表1 实体属性表

Fig.1 Ontology structure of OJ knowledge graph图1 OJ 知识图谱的本体结构

Table 2 CSV file table表2 CSV 文件表

3.2 知识图谱的构建方式

知识图谱构建的主要方式有：自底向上、自顶向下和自动构建3 种。自底向上的构建方式根据人们已知知识为主导，对相关领域概念进行层次划分，该方式适合构建通用型知识图谱；自顶向下的构建方式先从比较权威的公开数据集或专业的网站中获取数据信息，再通过技术手段获取所需的信息实体、关系及属性，适合在知识明确、关系清晰的领域构建知识图谱；自动构建则通过机器学习、数据自动获取、统计等技术构建知识图谱。由于OJ 系统应用于特定领域，本文采用自顶向下的构建方式，将实体、关系及属性信息输入图形数据库Neo4j 中实现知识图谱的可视化展示及存储。

基于山东科技大学OJ 系统中2019 年程序设计基础（C语言）实验课程数据构建知识图谱，其中数据包括924 个实体（6 名老师、298 道题目、164 次测试和456 名学生）和153 612 条关系。图2 展示了OJ 知识图谱的部分内容，其中学生、题目之间的提交关系占据了非常重要的地位，它们不仅展示了学生对某个题目所涵盖知识点的学习情况，还体现了学生的努力程度、学习能力和学习效果。此外，对这些关系进行分析有助于教师提供个性化辅导和教学，有助于实现学生学习效果的形成性评价。

Fig.2 Partial knowledge graph图2 部分知识图谱

4 OJ 知识图谱的应用

目前，在线教育领域存在老师获取反馈不及时、学生定位［11］和学习路径［12］不清晰、教师学生数据管理繁琐等问题，借助OJ 知识图谱可有效解决上述问题。本文基于Neo4j 的查询语言Cypher 对知识图谱信息进行检索，分别从学生、教师和教学管理人员角度，以个例分析方式对OJ知识图谱的潜在应用进行说明。

从学生角度而言，由于学生存在学习努力程度、学习能力、兴趣爱好等个体差异，基于知识图谱分析学生题目提交和通过情况及各种信息，对学生进行画像［13-14］，能够更好掌握每个学生的特点。进一步，根据K-means 聚类算法分析学生的学习情况，提取学生之间的相似度，如图3 所示。通过聚类分析后，选择相似用户有助于后续工作的研究。例如：如图4 所示，通过分析学习者的相似度，结合知识图谱可个性化定制学生的学习路径［15］。

Fig.3 Student clustering图3 学生聚类

Fig.4 Student learning path planning图4 学生学习路径规划

从教师角度而言，OJ 知识图谱帮助教师分析学生对不同问题的掌握程度，判断学生的学习水平和能力，实现学情分析，从而有针对性地调整教学计划和提供个性化辅导。如图5所示，76.8%的学习者在答题过程中出现答案错误，表明学习者对相关知识点的学习程度不够，还需加强练习。

Fig.5 Students'errors in one test图5 一次测试中学生的错误情况

从教学管理者角度而言，借助知识图谱能有效掌握教学质量。如图6 所示，以两位老师（实体为红色节点）为例，分析代表测试集的橙色节点顺序，可生成每位教师的教学路径。如果当测试集由题目组成时，则分析题目的先后顺序可生成教学路径，进一步分析可为教师进行教学画像。

Fig.6 Analysis of teaching paths of different teachers图6 不同教师的教学路径分析

5 结语

本文对OJ 知识图谱进行本体设计，通过图数据库Neo4j 和程序在线测评系统数据构建OJ 知识图谱，并利用可视化方法分析OJ 知识图谱的潜在应用。首先，OJ 知识图谱能显著提高学生学习兴趣和学习效果，其次能协助教师进行学情分析，协助教学管理人员进行评教和评学，OJ知识图谱能在一定程度上满足现实课程教学需求。未来将进一步完善OJ 知识图谱，为智能问答、成绩预测分析、个性化课程推荐、关系挖掘等应用提供更强大的推动力。