一种知识图谱增强的在线评测系统习题推荐算法研究

叶俊民,宋家琦,张 珂,于 爽

(华中师范大学 计算机学院,武汉 430079)

1 引 言

个性化学习的核心在于以学习者为中心,适应学习者的个体差异,从而充分发展学习者的个性优势.个性化学习的思想渊源可以追溯到我国古代教育家孔子“因材施教”的教育理念,有关个性化学习的思想内核已被当代教育实践充分吸收.《中国教育现代化2035》[1]提出“更加注重因材施教” 是教育现代化的八大基本理念之一.随着信息技术的发展,网络学习资源数量源源不断地增加,造成了“信息过载”的现象,学习者面对海量习题,难以高效地从中筛选出最适合自己的习题,因此学习者的个性化学习需求也更加强烈.个性化推荐是缓解信息过载的有效手段之一,为了实现面向学习者的个性化习题推荐,本文针对在线测评系统的特点,设计并实现了融合知识图谱的在线测评系统习题个性化推荐算法,具体做法是在采集学习者做题数据的基础之上,构建习题知识图谱并将知识图谱中所蕴含的丰富语义信息融合到推荐系统中,以综合考量习题的知识点、难度、相关度等影响因素,最终设计出面向学习者的个性化习题推荐算法,为学习者推荐符合其学习状态的习题,使学习者的练习更有针对性,提高学习者的学习效率.20世纪末,个性化推荐技术便被提出,国内外学者积极投入研究.国外学者的相关工作如Walker[2]等通过用户的访问搜索数据、提交的评论数据、他人的评价数据等信息寻找具有相似兴趣的用户,以此实现个性化学习资源推荐;Pinter[3]等构建了一个用于教授编程课程的在线学习平台,并使用协同过滤的推荐算法为学生生成学习路径;Hsu[4]等使用基于内容的分析方法,采用协同过滤和数据挖掘技术分析学生的浏览记录,再根据分析结果帮助学生选择合适的英语课程;Milicevic[5]等设计了一个编程辅导系统的推荐模块Protus,其首先使用AprioriA II算法挖掘频繁序列,分析相似学生的习惯和兴趣,再根据对频繁序列的评级实现可以自动适应学生兴趣和知识水平的个性化学习资源推荐;Toledo[6]等使用协同过滤算法设计并实现了在线测评平台的推荐系统,并提出了一种适用于该领域的用户相似性度量方法;Hana[7]等通过使用学习者的成绩数据来计算学生的相似度,并通过协同过滤技术预测参加课程的学生最终成绩.国内学者的相关工作如李浩君[8]等通过匹配学习者与在线学习资源之间的相关特征,同时嵌入三维特征,构建了融合深度学习算法的学习资源推荐模型,同时关注学习者与学习资源两者间的关联度,设计一种用于学习资源推荐的深度神经网络模型,这两种模型都能深度挖掘学习者的隐藏个性,把符合学习者个性的学习资源推荐给学习者;Lv[9]在个性化习题推荐的过程中,考虑了知识点之间的先决关系,以此来提高习题推荐的精准度;Huo[10]利用知识追踪技术,分别基于内容和长短时记忆网络构建了两种使用知识成分上下文化表示的方法,从而在智能教育系统中实现了个性化习题推荐;Jiang[11]提出了一种基于知识层次图的个性化习题推荐算法Re-KHG,根据学生对知识的掌握程度和知识的层次结构图向学生推荐合适的习题;Mao[12]提出了一个学习行为感知认知诊断(LCD)框架,可以利用学习者的学习行为记录和做题记录进行学生的认知建模,从而更有效地预测学生的做题表现.Weng[13]通过将众包知识图与教学系统相结合,构建教学领域的完整分层知识图,再基于知识图的算法制定面向学习者的个性化习题;汤胤[14]利用深度强化学习算法从学习者历史习题作答数据中提取有效隐含信息,在构造题库网络图的基础上,建立引导式教学场景下的深度强化学习模型,为学习者推荐最佳习题.

虽然国内外相关研究利用推荐系统等方法能够向学习者推荐个性化的课程资源或者学习路径等,但较少将习题知识图谱与推荐系统进行融合,以达到更优的个性化推荐效果,该研究工作还有许多方面的问题值得进一步研究:1)当前学习资源个性化推荐任务多数从学习者的角度出发,通过寻找相似学习者达到协同过滤推荐的目的,没有在推荐系统中引入习题相关知识的结构性信息,算法的推荐准确度还有提升的空间;2)传统推荐算法中存在的冷启动问题.

本文针对以上问题,提出了一种知识图谱增强的在线测评系统习题推荐算法,该方法结合习题知识图谱,基于多任务特征学习(MFL)方法构建MKR模型完成习题推荐任务.首先,基于在线测评系统中的赛事集与习题知识体系构建习题知识图谱;其次,根据习题难度和学习者的能力水平,构建“学习者-习题”匹配矩阵;最后,利用交叉压缩单元,使用交替训练方法训练知识图谱嵌入(KGE)任务和习题推荐任务,完成学习者个性化习题推荐任务.

本文工作主要在于:1)提出了适用于习题推荐的关系矩阵计算方法——UEMD-GA用户-习题匹配度生成算法,在用户历史做题记录的基础上,综合考量当前时刻下用户对习题的兴趣度及难度适应度,从而得到承载信息丰富的用户-习题匹配度矩阵;2)缓解传统推荐算法中的冷启动问题.本文用交替训练的方法,交替优化推荐算法模型和知识图谱嵌入模型,将习题信息融入到习题推荐系统中,使得即使在用户的做题数较少的情况下,推荐系统也可以借助习题知识图谱的信息向用户推荐合适的习题.

2 问题形式化定义

设为在线评测系统的用户数,M为在线评测系统的习题数,为了更好地完成知识图谱增强的在线测评系统习题推荐算法研究工作,本节先定义相关术语如下.

定义1.知识点.知识点K是知识与理论相对独立的最小单元,是知识最为具体的内容.

在本文中,知识点指的是在线评测(OJ)系统考察学生的具体内容,例如“广度优先搜索”、“贪心算法”、“最短路算法”等.

定义2.习题.习题是为学习者提供的,可供练习和实践的,并且具有已知答案的问题.一个习题T由一个或多个互不相同的知识点ki组成,即T=(k1,k2,…).

定义3.用户-习题匹配矩阵.用户-习题匹配矩阵UEMM(User-Exercise Matching Matrix)表示当前时刻下,受用户能力水平、兴趣导向等综合因素影响下的用户与习题的匹配程度.Y∈RN×M表示在线评测系统内被研究用户与所有习题的匹配程度矩阵,其中,R表示由用户与习题构成的二维点阵空间,矩阵元素yij的取值为0～1之间的实数,即yij∈[0,1].特别地,yut表示用户u与习题t的匹配度为y.

定义4.UEMD-GA用户-习题匹配度生成算法.用户-习题匹配度生成算法UEMD-GA(User-Exercise Matching Degree-Generate Algorithm)是本文提出的多维度关系矩阵算法.这个算法的主要思想是:首先根据用户的历史做题记录计算习题知识点分布,得到用户对习题的兴趣度;然后根据每道习题被解决的总次数计算习题的全局难度,得到习题与用户能力值的契合度;再将用户对习题的兴趣度与难度契合度的值相乘得到用户对习题的匹配度,当习题推荐系统中包含更多纬度的评价指标时,只需一并累积叠加即可.通过遍历计算被研究用户对所有习题的匹配度,即可得到最终多维度融合的习题-用户匹配度矩阵.

定义5.习题知识图谱.习题知识图谱EKG(Exercise Knowledge Graph)表示在线评测系统内,以习题为主要元素,包含习题与知识点、赛事等实体之间关系的语义网络.G={(h,r,t)|h,t∈E,r∈R}表示习题知识图谱,其中E表示在线评测系统内的实体集,例如,习题、知识点、赛事等,R表示实体之间的关系,例如,包含、属于等,h,t表示某一个实体的具体实例,如习题t、赛事c、知识点k等,r表示实体h和实体t的关系.

问题定义.知识图谱增强的在线评测系统习题推荐问题.本文要解决的相关推荐问题描述如下.

输出：向用户ui推荐的习题集Recommend(ui).

针对上述问题,本文基于知识图谱与深度学习技术设计了一种知识图谱增强的在线评测系统习题推荐框架,如图1所示.

图1 知识图谱增强的在线评测系统习题推荐框架Fig.1 Exercise recommendation framework of OJ system enhanced by knowledge graph

该框架中的处理步骤分为4个阶段:1)数据采集阶段.使用网络爬虫技术采集在线测评系统上的相关数据,包括习题集、用户集以及用户的做题记录等;2)模型输入构建阶段.根据第一阶段获取的在线评测系统数据,分别构建习题知识图谱和用户-习题匹配度矩阵.在构建习题知识图谱时,首先将习题集转换为知识图谱的习题节点,然后根据每道习题所包含的知识点添加习题节点到知识点节点的关系边,最后按照习题所在的赛事添加习题节点到赛事节点的关系边,得到习题知识图谱;在构建用户-习题匹配度矩阵时,首先根据用户的历史做题数据,统计分析用户对不用知识点的兴趣度分布情况,然后根据用户的能力水平和习题的难度水平计算用户对习题的难度适应度,最后综合考量用户对习题的兴趣度以及难度适应度计算得到用户-习题匹配度矩阵;3)模型训练阶段.MKR模型[15]由3个主要部分组成,推荐模块、知识图谱嵌入模块和交叉压缩单元.推荐模块将用户和习题作为输入,使用多层感知器(MLP)和交叉压缩单元分别提取用户和习题的特征,提取出的特征再一起输入另一个多层感知器,输出用户-习题匹配的预测值;知识图谱嵌入模块将知识图谱中的上位节点和关系边作为输入,使用多层感知器和交叉压缩单元分别提取上位节点和关系边的特征,使用上位节点和关系边预测出下位节点的表示;交叉压缩单元是将推荐模块和知识图谱嵌入模块连接起来的关键,这个单元可以自动的学习推荐模块中习题和知识图谱中节点的高阶交互特征;4)习题推荐阶段.输入用户信息和用户的做题记录,输入训练完毕的MKR模型中,完成习题推荐,得到针对当前用户的个性化推荐习题列表.

3 知识图谱增强的在线测评系统习题推荐

3.1 UEMD-GA用户-习题匹配度生成算法

基于用户的协同过滤习题推荐算法是以用户为研究对象,通过分析用户所偏好的习题来计算用户之间的相似度,找到相似度最大的其他用户,然后根据其他相似用户的偏好为目标用户推荐他可能感兴趣的习题.现有的基于协同过滤推荐方法的用户个性化习题推荐算法在构建U-V矩阵时,都是按照用户是否通过某一道习题来衡量用户与习题的关系值,这种方法的缺点是,由于用户所做过的习题之间时间跨度很大,随着用户能力的提升,在当前时刻下用户可能已经不再对以前做过的某一类简单的习题,或者已经完全掌握的习题表现出较大的兴趣,缺乏对用户当前状态的适应性考量.为此,本文提出了UEMD-GA用户-习题匹配度生成算法,能够综合考量用户在当前时刻下对所有知识点的兴趣度以及用户能力水平与习题难度的适应度,进而得到用户-习题匹配度矩阵,其中学习者的能力值采用ELO积分算法[16]根据用户历史参赛(测验)的答题记录进行测算,在本实验数据集上,用户能力值由在线评测系统给出.具体过程如算法1所示.

算法1.用户-习题匹配度生成算法

算法功能：根据用户对习题的兴趣度及难度适应度得到用户-习题匹配度矩阵

输入：习题集T={t1,t2,…,tm}、

用户集U={u1,u2,…,un}、

知识点集K={k1,k2,…,kp}、

输出：用户-习题匹配度矩阵UT(U,T)

Begin:

1.Inter(U,K)←[[0,…,0],…,[0,…,0] ]

2.for∀Ui→Uj//对于每一个用户

3.for∀Tp→Tq//做过的每一道题

4.for∀Km→Kn//包含的每一个知识点

5.Inter(Ui,Km)+=1//统计知识点次数

6.Inter(U,K)←1-1/(1+Inter(U,K))

//将统计值转换为知识点兴趣度,取值为[0,1]

7.Inter(U,T)←[1,…,1]

8.for∀Tp→Tq//对于每一道题

9.for∀Km→Kn//包含的每一个知识点

10.Inter(U,T)←avg(Inter(U,Km))//习题兴趣度

11.Difficultt(T)←[0,…,0]

12.Difficulty(T)←1/(1+Pass(T))//习题难度值

13.Ability(T)←1-1/(1+Ability(U))//用户能力值

14.Suit(U,T)←1-(|Difficulty(T)-Ability(U)|)

//得到用户对习题的难度适应度

15.UT(Ui,Tj)←Inter(Ui,Tj)×Suit(Ui,Tj)

//综合兴趣度和难度适应度得到用户-习题匹配度

END

具体而言,UEMD-GA用户-习题匹配度生成算法包括以下4个步骤.

第4步.计算用户-习题匹配度.结合第2步计算得到的用户对习题的兴趣度Inter(ui,tj)和第3步得到的用户对习题的难度适应度Suit(ui,tj),根据计算公式Inter(ui,tj)×Suit×(ui,tj)可以得到最终的用户-习题匹配度矩阵UT(ui,tj).

UEMD-GA算法的时间复杂度为O(M×N×P),其中M为习题数、U为用户数、P为知识点数.根据如上的算法步骤,可以看出,在第一步计算用户对知识点的兴趣分布时需要耗费的时间最多,因为在这一步需要嵌套遍历所有的用户、所有的题目、所有的知识点才能得到用户ui对知识点集的兴趣度分布Inter(ui,K).

3.2 习题知识图谱构建算法

虽然在线评测系统中有海量的习题,但是这些习题之间并不是彼此相互孤立的,它们之间有很多不同形式的关联关系.1)每一道习题都与某些特定知识点有关联,用户对一道习题ta感兴趣的时候,较大程度上也会对与习题ta知识结构相似的习题tb感兴趣;2)在线测评系统中的赛事,将习题以习题组的形式进行汇总发布,同属于一场赛事的习题在知识体系构成以及习题难度上有合理的递进关系,用户完成一场赛事中的一道习题tc的时候,也会倾向于继续做同属于这场赛事的习题td.为了在习题推荐系统中捕捉到上述习题间的关系,本文基于在线评测系统数据构建了习题知识图谱.具体过程如图2所示.

图2 习题知识图谱构建过程Fig.2 Construction process of exercise knowledge graph

习题知识图谱G={(h,r,t)|h,t∈E,r∈R}的构建过程包括以下3个步骤:(a)构建习题节点.首先以习题T作为实体集E的实例,把习题集T={t1,t2,…,tm}中的每一道习题转化成知识图谱G的习题节点;(b)构建习题-知识点关系.首先将知识点K作为实体集E的实例,把知识点集K={k1,k2,…,kp}中的每一个知识点转化成知识图谱G的知识点节点,然后根据习题ti所包含的知识点kj,在习题知识图谱G中添加习题-知识点关系(ti,has,kj);(c)构建习题-赛事关系.首先将赛事C作为实体集E的实例,把赛事集C={c1,c2,…,co}中的每一个赛事转化成知识图谱G的赛事节点,然后根据习题ti所属的赛事ck,在习题知识图谱G中添加习题-赛事关系(ti,belong,ck).

在传统的基于协同过滤的推荐算法,普遍存在冷启动问题,即当新用户加入系统时,由于系统中可供参照的用户较少,推荐系统难以在有限的协同信息下向新用户给出较为合适的推荐结果,而本文引入的习题知识图谱的目的正是为了缓解这个问题,在习题知识图谱中,习题与习题之间通过共同的知识点或者共同的赛事而取得关联,可以在仅知少量用户所感兴趣的习题的前提下,通过习题知识图谱所带来的关联信息,为此用户推荐更多其感兴趣的习题.

3.3 知识图谱增强的习题推荐算法

本文使用MKR模型完成基于知识图谱增强的在线评测系统习题推荐,MRK模型结构如图3所示,其由3个主要部分组成,推荐模块、知识图谱嵌入模块和交叉压缩单元.

MKR模型利用交叉压缩单元和交替训练将知识图谱特征学习融入到推荐任务的训练过程中,从而利用知识图谱信息协助提升推荐任务的效果.

3.3.1 交叉特征压缩单元

交叉特征压缩单元是一个可以让两个任务交换信息的模块.由于用户-习题中的习题向量和习题知识图谱中的习题实体向量实际上是对同一个对象的两种描述,它们之间的信息交叉共享可以让两者都获得来自对方的额外信息,从而弥补了自身的信息稀疏性的不足,以此来降低数据稀疏性给推荐模型的性能所带来的负面影响,交叉特征压缩单元的结构如图4所示.

图4 交叉特征压缩单元的结构Fig.4 Structure of cross feature compression

其中,vi∈Rd、el∈Rd,d表示向量vi和向量ei的长度,

交叉操作如公式(1)所示:

(1)

交叉操作是基于vl和el构建一个d×d大小的成对矩阵.

压缩操作如公式(2)所示:

(2)

其中,wl∈Rd、bl∈Rd是交叉特征压缩单元的训练权重和偏差向量,vl和el经过交叉特征压缩后得到vl+1和el+1.

本文后续将交叉特征压缩单元表示为如公式(3)所示的形式:

[vl+1,el+1]=C(vl,el)

(3)

3.3.2 知识图谱嵌入模块

知识图谱嵌入模块将知识图谱G的实体E和关系R映射到连续的低维向量空间,同时保留它们原来的空间结构,知识图谱嵌入的计算过程如公式(4)所示:

(4)

(5)

3.3.3 推荐模块

使用多层感知器提取用户特征向量的计算过程如公式(6)所示:

uL=M(M(…M(u)))=ML(u)

(6)

其中,u表示用户u的原始特征向量,ML表示L层的多层感知机.

全连接神经网络如公式(7)所示:

M(x)=σ(Wx+b)

(7)

使用L个交叉特征压缩单元提取习题v特征向量的计算过程如公式(8)所示:

vL=ee～S(v)[CL(v,e)[v]]

(8)

其中,S(v)表示与习题v相关的实体.

(9)

4 实 验

本文在真实的在线评测(OJ)系统数据集进行了实验,论证了本文方法的有效性.

4.1 数据集

本文使用的实验数据是从CodeForces(OJ)上爬取的在线评测系统真实数据.该数据集由6部分组成:1)习题数据;2)习题被解决次数统计数据;3)用户数据;4)赛事数据;5)用户做题提交记录数据;6)知识点类型数据.上述CodeForces用户-习题相关数据集详情如表1所示.

表1 CodeForces用户-习题相关数据集Table 1 Codeforces user-exercise related dataset

由表1可知,该数据集包含6919道习题,所有习题所涉及的知识点为36个,所有习题所涉及知识点的出现频次分布如图5所示,由图5可知,该数据集中所有习题所涉及知识点中K1(implementation)、K3(math)以及K2(greedy)出现的频次较高.

图5 所有习题所涉及知识点的出现频次分布Fig.5 Frequency distribution of knowledge involved in all exercise

在本文实验中,习题推荐模型向用户所推荐习题与用户的匹配度若大于0.8则认为该推荐结果正确,反之错误.

4.2 习题知识图谱的构建

根据4.1节所介绍的习题数据、赛事数据、知识点类型数据可构建出在线评测系统习题知识图谱EKG,具体来说,该习题知识图谱包括习题节点T、知识点节点K、赛事节点C,以及习题-知识点关系(ti,has,kj)和习题-赛事关系(tj,belong,ck).在该习题知识图谱中,不同的习题之间通过知识点或者赛事间接构成了某种关系,这些关系的存在缩短了知识分布相似或者难度相似的习题在知识图谱上的距离,从而提升了它们之间的相似度.

在线评测系统习题知识图谱构建的具体步骤如算法2所示,由于知识图谱是图结构的数据,因此采用图数据库Neo4j来实现知识图谱数据的存储.

算法2.在线评测系统习题知识图谱构建步骤

流程功能：根据在线评测系统的习题数据、赛事数据、知识点类型数据构建习题知识图谱

输入：习题集T={t1,t2,…,tm}、

赛事集C={c1,c2,…,cn}、

知识点集K={k1,k2,…,kp}

输出：在线评测系统习题知识图谱

PKG={(h,r,t)|h,t∈E,r∈R}

构建语言:CypherQueryLanguage(Neo4j)

Begin:

Step1.CREATE(n:TAG{name:$Knowledge_name})

//构建知识点节点

Step2.GREATE(n:Contest{name:$Contest_name})

//构建赛事节点

Step3.GREATE(n:Exeicise{name:$Exeicise_name})

//构建习题节点

Step4.MATCH(a:Exeicise{name:$Exeicise_name}),

(b:Contest{name:$Contest_name})

MERGE(a)-[:belong]→(b)

//构建习题-赛事关系边

Step5.MATCH(a:Exeicise{name:$Exeicise_name}),

(b:Tag{name:$Tag_name})

MERGE(a)-[:knowledge]→(b)

//构建习题-知识点关系边

End

4.3 在线评测系统习题推荐实验结果和分析

MKR是一个通用的、端对端的深度推荐框架,旨在利用知识图谱嵌入协助推荐任务,这两个任务是相互独立的,但是由于推荐模块中的习题和知识图谱中的习题实体是相互联系且高度相关的,因此在模型训练的过程中,可以通过交替优化两个任务的方法来进行,这赋予了MKR在真实推荐场景中高度的灵活性和适应性.MKR与若干基线模型在习题推荐任务上的结果如表2所示.

表2 MKR与若干基线模型在习题推荐任务上的结果Table 2 Results of MKR and some baseline models on exercise recommendation tasks

PER模型将知识图谱视为异构信息网络,并提取基于元路径的特征来表示用户和项目之间的连接;CKE模型将CF与结构、文本和视觉知识结合在一个统一的推荐框架中;DKN将实体嵌入和单词嵌入视为多个通道,并在CNN中将它们组合在一起以进行CTR预测;LibFM是一种基于特征的因子分解模型.在MKR系列(实验5～8)模型的对照实验组中采用了4种不同的用户-习题(UI)匹配度计算方法(Pass、Interest、Suit和Interest+Suit).其中Pass方法是以二值编码表示用户是否通过一道题,用户ui通过了习题tj则UI(ui,tj)=1,否则UI(ui,tj)=0;Interest方法是根据用户历史所做习题的知识点分布计算用户对知识点的兴趣度进而计算出用户对习题的兴趣度,作为用户对习题的匹配度;Suit方法是依次计算归一化的用户能力水平和习题难度值,再用两者之间的差值来衡量用户对习题的难度适应度,作为用户对习题的匹配度;而Interest+Suit方法是将通过Interest方法和Suit方法得到的兴趣度和难度适应度相乘,作为用户与习题的匹配度.从如表2所示的实验结果可以得出以下结论:

1)CKE模型(实验2)由于在推荐系统中融合了更丰富的信息,总体推荐效果比PER(实验1)和DKN(实验3)好;

2)采用Pass作为UT匹配度计算方法的MKRpass模型(实验5)能够取得比PER和DKN更优的表现,但是由于Pass方法在知识图谱模块引入的信息不够丰富,总体上的表现还是不如LibFM(实验4);

基于上述基础工作,现说明一下相关对照实验结果.

第1组对照实验,为了验证习题知识图谱模块对个性化习题推荐的增强作用,分别使用含有习题知识图谱模块和不含有习题知识图谱模块的推荐模型开展习题推荐实验.实验结果如表3所示.

表3 用不同的习题知识图谱进行习题推荐的结果Table 3 Results of exercise recommendation with different exercise knowledge graph

对照实验组采用了4种不同的习题知识图谱类型(NULL、Knowledge、Contest和Knowledge+Contest)进行习题推荐任务.其中NULL类型是指不在推荐系统中添加习题知识图谱模块;Knowledge类型是以习题-知识点关系构建习题知识图谱,合并到推荐系统模型中,它能够捕捉到涉及同一个知识点的不同题目之间的关联;Contest类型是以习题-赛事关系构建习题知识图谱,然后参与习题推荐系统模型的训练和推荐;Knowledge+Contest是指合并了习题-知识点关系与习题-赛事两种关系而构建的习题知识图谱.从实验结果可以得出以下结论:在该实验数据集上,在推荐系统中引入习题知识图谱模块能够提升习题推荐准确率,特别地,采用Knowledge+Contest类型的习题知识图谱增强推荐模型在精确率P、召回率R和F13个指标上都取得了优于对照实验组中采用其他习题知识图谱类型的结果,说明通过习题知识图谱模块在推荐系统中引入更丰富的习题信息,能够提升习题推荐系统的推荐准确率.

第2组对照实验,在推荐系统中融合知识图谱是缓解冷启动问题的一个常用手段,为了验证本文所使用的习题知识图谱能够有效缓解习题推荐的冷启动问题,针对不同的用户做题数,分别使用含有习题知识图谱模块和不含有习题知识图谱模块的推荐模型开展TOP-10习题推荐对比实验.实验结果如表4与图6所示.

表4 采用不同图谱类型在不同用户做题数下进行习题推荐的召回率Table 4 Recall of exercise recommendation with different graph types and different number of questions done by users

图6 对不同的用户做题数进行TOP-10习题推荐的召回率Fig.6 Results of recall in TOP-10 exercise recommendation for different users

对照实验组采用了4种不同的习题知识图谱类型(NULL、Knowledge、Contest和Knowledge+Contest)进行习题推荐任务.横向坐标轴表示用户的做题数,纵向坐标轴表示召回率,图中的折线表示融合了不同的知识图谱后习题推荐系统向做题数不同的用户进行top-10习题推荐的召回率.可以看到在用户做题数小于5的时候,NULL类型推荐模型的召回率表现低于0.05,能够正确推荐的概率很低,也就是所谓的冷启动问题;同时可以看到,Knowledge+Contest类型推荐模型的top-10推荐召回率(0.104)相比不融合知识图谱的NULL类型推荐模型(0.028)在用户做题数较少的情况下(<5)提升了2.71倍,表明了本文的习题知识图谱能够有效缓解OJ系统下的习题推荐冷启动问题.

5 结束语

本文提出了一种多维度关系矩阵算法UEMD-GA,并基于MKR模型完成了知识图谱增强的在线评测系统习题推荐任务.在理论研究的基础上,本文通过在真实数据集上的实验得到了两个结论:1)综合考虑用户对习题的兴趣度及难度适应度能够比直接根据用户的历史做题记录来做用户-习题匹配度计算更准确地刻画用户与习题间的关系,从而带来个性化习题推荐准确率的提升;2)习题知识图谱增强的习题推荐算法能够比直接利用推荐算法带来更丰富的用户-习题-赛事间信息,进而提升习题推荐准确率.在今后的研究中,还可以从以下方面对模型进行改进,计算用户-习题匹配度矩阵时,在考量用户对习题的兴趣度与难度匹配度的基础之上,新增引入用户的学习路径信息,为用户个性化推荐更符合他学习进程的习题.