一种基于HIN的学习资源推荐算法研究

2019-05-05叶俊民黄朋威罗达雄王志锋

小型微型计算机系统 2019年4期

叶俊民，黄朋威，罗达雄，王志锋，陈曙

1(华中师范大学计算机学院，武汉 430079)2(华中师范大学教育信息技术学院，武汉 430079)

1 引言

如何更精准地进行学习资源推荐是自适应学习中有待进一步研究的问题.传统的的推荐方法主要是通过计算学习者之间的相似度，或者计算知识单元之间的相似度，以实现向学习者推荐学习资源.但相关方法没有注意到学习者和知识单元之间丰富的关联关系.由于异构信息网络能够很好支持对象及对象间的关联表达，因此基于异构信息网络来研究学习资源推荐具有较大的理论研究意义和实践应用价值.

国外关于自适应学习中学习资源推荐的研究主要集中在各类推荐算法在自适应学习平台的应用效果研究、各种学习环境因素对于推荐算法的影响，以及大数据技术在学习资源推荐中的应用.

X Peng等根据学习者的搜索行为和资源属性，提出了能够高效匹配搜索字符串与学习资源的推荐方法[1]；H Chen提出了基于主题模型的兴趣挖掘算法，实现了高效的个性化学习资源推荐[2]；M Salehi等应用隐式、显式属性，采用推荐序列模式挖掘算法得到了精度更高的学习资源推荐效果[3]；G Sun等基于概念图的本体构建方法，结合学习者的历史信息，开发了自适应教育资源推荐系统MLaaS[4]；T Liang等提出了一种基于内容过滤的PageRank学习资源推荐算法[5].

国内的研究工作主要关注推荐算法的改进、学习者和学习资源的特征与关联的使用，以及个性化因素的研究.程岩等根据学习者的知识水平、学习风格和对学习路径的评价，提出了一种扩展蚁群算法用以实现学习路径的推荐[6]；付芬等提出了一种基于隐式评分和相似度传递的学习资源推荐算法[7]；李浩君等将协同过滤算法和二进制粒子群算法进行结合，提出了基于多维特征差异的个性化学习资源推荐算法[8]；丁继红等基于张量理论实现了学习者和学习资源之间的精准匹配[9]；姜宇等基于学习网页的点击流数据实现了学习资源推荐[10].

相关研究工作表明，自适应学习的推荐研究所用算法主要有：协同过滤算法、聚类算法、基于内容的推荐算法和蚁群算法等.但对于如何从异构信息网络的角度来研究学习资源推荐，并使用异构信息网络基于元路径的相似性度量来设计推荐算法，这方面的研究目前还是处于初步探索阶段.

2 问题研究框架

2.1 问题定义

定义 1.自适应学习系统.自适应学习系统(Adaptive Learning System，简称ALS)是一种可针对个体学习者在学习过程中的差异而提供适合个体特征的学习支持系统，该系统通过对学习者学习风格、认知水平等因素的综合分析，为学习者营造出个性化的学习环境，以支持学习者在任何时间、地点都可以进行学习.常见的自适应学习系统依据学习者的学习风格和认知水平，向学习者推荐学习资源以实现对学习者个性化学习的支持.

定义 2.信息网络[11].信息网络是一个带有对象类型映射函数φ：V→A和链接类型映射函数ψ：E→R的有向图G=(V，E).其中，每个对象v∈V属于一个特定的对象类型集合A：φ(v)∈A，每个链接e∈E属于一个特定的关系类型R：ψ(e)∈R.

定义 3.异构信息网络[11].如果对象类型满足|A|>1或者关系类型满足|R|>1，则该信息网络为异构信息网络(Heterogeneous Information Network，HIN).

ALS是一种HIN，图1中的ALS涉及三类对象：学习者、课程知识和辅导老师.对象之间的关联关系主要有：学习者学习课程知识，课程知识被学习者学习，辅导老师辅导学习者，学习者被辅导老师辅导，辅导老师引用课程知识，课程知识被辅导老师引用，课程知识前驱课程知识，课程知识后继课程知识.

图1 自适应系统网络示意图Fig.1 Adaptive system network diagram

定义 4.网络模式[11].网络模式是指带有对象类型映射φ：V→A和链接类型映射ψ：E→R的异构信息网络G=(V，E)的元模板，记为TG=(A，R).

图2 自适应系统中的网络模式Fig.2 Network mode in adaptive system

网络模式描述了实体的类型及其二元联系，为HIN提供了元层面(模式层)上的表示，加强了信息网络的可理解性和可操作性.HIN的网络模式限定了对象集合与对象间关系的类型约束，而这些约束使得HIN具有了半结构化的特点，对网络语义的探究起着引导作用.通过分析ALS中对象和链接的类型，归纳得出ALS的网络模式如图2所示.

在HIN中，两个对象通过不同路径相关联.如学习者之间的路径可以是“学习者—课程知识—学习者”，“学习者—辅导老师—学习者”等.因为HIN中对象间的相似性是根据对象在网络中的链接方式确定的，所以对ALS进行元路径描述是确定本文推荐算法的重要依据.同时，不同的链接类型也代表了不同的语义.通过分析ALS中的链接类型，可给出几个有代表性的元路径实例，具体如表1所示，其中S代表学习者，K代表课程知识，T代表辅导老师.

表1 自适应系统中的元路径含义列表Table 1 A list of meta path meanings in adaptive systems

定义 6.基于元路径的相似性度量问题.基于元路径的相似性度量是指使用HIN的原理计算两个对象在特定元路径上的语义相似性.不同的元路径对应着不同的推荐服务，而语义相似性的计算是推荐算法的推荐依据，所以实现基于HIN的自适应学习推荐还要先进行元路径的选择，而元路径的选择取决于ALS的推荐需求.

相似度计算算法的输入和输出分别为：1)输入方面：学习者、课程知识与辅导老师之间交互的有向图(ALS中对象的异构信息网)；2)输出方面：ALS中对象间的相似性计算结果(学习者与课程知识的相似度、学习者与辅导老师的相似度等).

如果该资源越适合学习者当前的需求，则表示其关联关系的相似度值就越大，因此推荐算法可使用相似度top-K的资源对象来做推荐服务.可描述这种关联关系的一种有效手段即采用所谓的HIN，而这种关联关系相似度计算就恰好可以规约为HIN中的语义距离计算.

2.2 研究框架

为了更好地实现自适应学习系统的基本设计目标，首先需要将学习者与课程知识之间的关联关系刻画出来，然后通过这种关联关系的相似度计算来实现学习资源推荐.基于此思路，设计出的问题研究框架如图3所示.

图3的计算流程如下：

1)在获取了学生信息、教学资源信息、学习记录和辅导记录后，自适应推荐引擎首先根据学习者的学习目标为其定位课程知识的学习范围，初步筛选出适合学习者学习的知识单元集合φ；

2)根据规则匹配的内容对学习者与φ中的知识单元进行知识水平匹配、认知能力匹配，得到φ中所有知识单元最终的匹配值；

图3 学习资源推荐问题的研究框架Fig.3 Research framework for learning resource recommendation

3)将学习者与φ中匹配值top-K的学习单元进行学习风格匹配，得出适合学习者学习风格的学习资源类型，并将具体类型的学习资源推荐给学习者；

4)记录学习者的学习数据和辅导数据；

5)根据学习者、课程知识、辅导老师之间的交互信息，结合推荐需求选择元路径并计算对象间的相似度，根据相似度进行学习资源推荐；

6)迭代步骤4)及5)的计算活动.

3 构建模型

3.1 构建学习者模型

学习者模型描述了学习者内外部的学习特征，是实现学习分析工具的前提和基础[13]，其记录了出现在计算系统中学习者的状况，是学习者认知状况的一种描述，是系统中学习者的抽象表示.理想的学习者模型应该包括学习者过去与学习相关的所有要素、课程学习中的进步状态、学习类型以及其它所有与学习者相关的信息；同时，该模型允许系统储存学习者的相关知识，以便于为学习者的个性化学习途径提供选择.本文根据学习者模型规范和学习者个性化特征所构建的学习者模型如图4所示.

图4 学习者模型Fig.4 Student model

3.2 构建领域知识模型

领域知识模型构建包括如下内容：知识层次结构的梳理、知识表示方法的设计和知识转化关系的研究.

知识的层次结构将课程学习细分为一个个小的知识点的学习，不仅描述知识间的关联关系，也建立了学习知识与学习资源之间映射关系.知识层次结构将与知识相关的目标、概念、关系、资源、测试、属性等进行了清晰的划分，为实现知识元素的分类存储提供了指导.本文以知识点作为最小的课程内容学习单位，从目标层、概念层、关系层、任务层和实体层这五个层次对知识点表示进行了多层逻辑划分，得到知识点的层次结构如图5所示.

图5 知识的层次结构图Fig.5 Hierarchy of knowledge

知识的层次结构从多角度设计知识的逻辑结构，为实现学习系统对知识的查询、管理和呈现等操作提供了方法.例如可使用n元组表示知识，其中包括：知识点所属的学习目标范围，其取值为课程教学要求中的各阶段细化的学习目标；知识点的概念名称可对不同的知识点起到了标记作用，实现了对知识点的查找；知识点关系可以通过前驱知识点与后继知识点来表示；知识点难度用于将不同难度的知识点推荐给不同学习能力的学习者；知识点风格涉及理论型知识点、探索型知识点和应用型知识点等；知识点的学习时长；知识点对应的学习资源类型等.

知识之间的转化关系可以使用贝叶斯知识跟踪模型(Bavesian knowledge tramsing model，BKT)来描述[14].该模型为确定学习者知识掌握状况提供了一个更加直观的解决方法.例如可使用4个参数表示学习者进行知识学习时的状态，具体如表2所示.

表2 贝叶斯知识跟踪模型的4个参数Table 2 Four parameters of BKT

根据贝叶斯知识跟踪模型，可计算出学习者从已知某一知识点x的情况下，到掌握另一知识点y的概率：

(1)

其中，N表示知识点x到知识点y需要经历的中间知识点个数，i表示从知识点x到知识点y的过程中所经历到的第i个知识点.

4 学习资源推荐算法

实现学习资源的推荐依赖于对象间的相似性的度量，为此本文提出了基于元路径计算两个对象相似度的方法SimALS，并结合自适应学习的特点，给出了对包含“KK(知识点到知识点)”关系和“SK(学习者到知识点)”关系元路径相似度计算的改进算法，并在此基础上定义了学习资源推荐算法.

4.1 SimALS相似性度量

在计算两个集合A和B的相似性时，可使用杰卡德相似性算法：

(2)

根据杰卡德相似性算法和顶点可达性原理，设计元路径P=R1∘R2∘ …∘Rl上两个物体s和t之间的相似度SimALS(s∈R1.S和t∈Rl.T)为：

(3)

其中O(s|R1)是物体s基于关系R1的外邻域，I(t|Rl)是物体t基于关系Rl的内邻域，R.S和R.T分别表示关系R的源对象类型和目标对象.

SimALS(s，t|P)是一种基于两两随机游走的测量方法，当s沿着路径移动时，t沿着相反方向移动，它评估s和t到达同一节点的概率.因为该算法使用了迭代的递推方法，所以时间复杂度为O(nl/2)，l为元路径的长度.

s和t的移动过程如下：

4.2 基于“KK”关系改进的SimALS算法

SimALS(s，t|R1∘R2∘ …∘Rl)计算两个对象s和t在元路径P=R1∘R2∘…∘Rl上的相似性，其算法原理是逐步迭代Oi(s|R1)和Ij(t|Rl)，并累加每对Oi(s|R1)、Ij(t|Rl)的相似度之和.Oi(s|R1)和Ij(t|Rl)的相似度是通过判断其是否为同一对象来确定的，计算结果为1和0.当使用4.1节描述的SimALS算法计算含有“KK”元路径的两个对象间相似度时，会将不同知识点的相似度按照0做处理.但在实际情况中，知识点间存在者前驱、后继等联系，不同的知识点间的相互转化是有概率的.所以，对于自适应学习系统做推荐而言，4.1节的SimALS算法的局限性在于当计算含有“KK”的元路径中对象的相似度时，忽略了知识点间的传播(或转化概率)信息.

针对SimALS在知识点转化方面的局限性，本节使用贝叶斯知识跟踪模型将知识点间的链接信息(转化概率)引入至知识点间相似性的计算中.当∃Ri=KK且i∈{1，2，…，l}时，相似性的计算如下：

(4)

其中，Mxy表示贝叶斯知识跟踪模型中知识点转化概率的邻接矩阵M的第(x，y)项的取值，代表着从知识点x转化为知识点y的转化概率，其计算方法见公式1；Oi(s|R1)=x，Ij(t|Rl)=y.

4.3 基于“SK”关系改进的SimALS

对于推荐算法而言，用户行为是能够直接反应用户喜好的依据，也是验证一切推荐算法效果的主要参考，常常作为用户对资源兴趣程度的评分项.而自适应学习系统中学习者的行为信息，主要表现为学习者实时的学习反馈信息(主要包括：正在学习某一知识点、收藏某一知识点的内容、对某一知识点打标签等).自适应学习系统通过实时地接收学习者的学习反馈信息，并根据学习者的学习状况为学习者安排下一步的学习内容，以完成自适应推荐功能.由于学习者的学习反馈信息是实时收集的，具有热门效应，对提高推荐算法的准确度十分有意义.所以，在计算含有“SK”的元路径下两物体的相似性时，需要考虑学习者与知识点间的反馈信息.为此，本节进一步提出具有这一功能的算法.

当∃Ri=SK，且i∈{1，2，…，l}时，相似性的计算如下：

(5)

其中，λ=(a+b+c)/3表示学习者对于某一知识点的反馈信息量，a表示学习者是否正在学习某一知识点(若学习者正在学习某一知识点，则a=1；反之，a=0)，b代表学习者是否收藏了某一知识点，c代表学习者是否对某一知识点打标签.a、b、c∈{0，1}，0≤λ<1.

4.4 基于HIN的资源推荐算法

基于HIN的资源推荐算法，是以学习者为推荐对象，所产生的推荐资源主要为知识点、辅导老师和学习者.结合上述基于元路径的相似性算法，得到本文核心推荐算法如图6所示.

基于HIN的学习资源推荐算法的实现过程是：首先选择推荐资源的类型；其次根据基于元路径的相似性算法计算学习者与所有该类型学习资源的语义相似度；然后对该相似度进行排名并将排名top-K的学习资源推荐给学习者.该算法的时间复杂度为O(n(len/2)+2)，len为元路径的长度阈值.

算法功能：向ALS中的学习者s推荐学习资源

输入：学习者实例s；推荐资源类型T(知识点、辅导老师、学习者)；推荐资源个数K；领域知识库实例N；元路径长度阈值len

输出：与学习者相似度最高的K个T类型的学习资源

5 实证与分析

为了验证本文所设计的基于HIN的自适应学习资源推荐算法的有效性和准确度，本文将从算法的分类准确率P(L)和平均排序分RS两个角度进行实验论证.

5.1 实验数据

本文采集了国内某大学二年级某班的所有80名学习者在自适应学习系统中“数据结构”课程上9月份至10月份的学习数据，并通过量化手段从中抽取学习者信息库、领域知识库、辅导记录库三个方面所对应的数据集D1、D2、D3.

学习者信息库、领域知识库、辅导记录库记录了自适应学习系统中学习者、领域知识、辅导老师这三个主要对象及其交互的所有信息，存储了实现资源推荐算法的基础数据.为了对推荐结果进行有效的验证，可将上述数据集进行如下处理：(1)以月份分区.将9月份的数据作为训练集，10月份的数据作为测试集.使用学习者10月份的学习数据来验证通过计算9月份学习数据所得的推荐序列的准确度；(2)以学习者分区(按学习者成绩平均分配).将40名学习者的学习数据作为训练集，来训练知识点间的转化概率.将另外40名学习者作为测试集，来验证改进的推荐算法的有效性.

5.2 评价指标

推荐算法的准确度评价方法有多种，本文根据所设计的资源推荐算法的特点，从分类准确度和排序准确度两个方面选择相关指标来对推荐算法进行评价.

定义8.准确率.准确率是衡量推荐算法分类准确度的重要指标，是指推荐正确的信息条数占所有推荐信息条数的比例，即通过推荐算法产生的推荐资源中被学习者接受的推荐资源的比例.准确率的评价指标P(L)的计算方法见公式(6).

(6)

其中，N为学习者人数；Ii为第i个学习者所收到的推荐资源集合；|Ii|为资源集合Ii中的资源个数(设|Ii|=10，即向学习者推荐10个学习资源)；Si为第i个学习者接受推荐资源的个数.

定义9.平均排序分.平均排序分是衡量推荐算法排序准确度的重要指标，该定义是指用户需求的推荐资源在推荐算法所生成的推荐序列中的排名之和与推荐序列中所有资源的排名之和的比例.

在比较两个推荐算法时，如果两个算法推荐的n个推荐资源中都有m个资源是用户需要的，那么两者的推荐准确率都为m/n.但是在两个推荐算法中，用户需求的m个资源的排序并不相同.显然，能够使m个资源排名靠前的推荐算法更具有优势，所以本文使用排序准确度来衡量推荐算法的优劣.排序准确度指标度量推荐算法所生成的推荐序列与用户的需求序列的统一程度，可以通过使用平均排序分的方法来实现.平均排序分的评价指标RS(Average Rank Score)的计算方法见公式(7).

(7)

其中，U为推荐算法所产生的推荐资源集合；Ri为推荐资源i在推荐序列U中的排名；D为用户所需求的推荐资源集合；Rj为用户所需求的推荐资源j在U中的排序.平均排序分越低，则算法的准确度越高.采用平均排序分，不仅可以进一步对比本文所提出的推荐算法(SimALS1、SimALS2、SimALS3和SimALS4)之间的准确度，也可以实现将本文推荐算法与其他推荐算法作对比.

5.3 研究问题

为了区分两种情况下改进的相似性方法和原始的相似性方法所产生的推荐算法，本文将以SimALS为相似性度量的推荐算法记为SimALS1，以基于“KK”关系改进的相似性度量的推荐算法记为SimALS2，以基于“SK”关系改进的相似性度量的推荐算法记为SimALS3，以同时融合了基于“KK”关系和“SK”关系的相似性度量的推荐算法记为SimALS4.

本文将学习资源推荐算法的有效性验证细化为以下两个研究问题.

Question1：比起一般的推荐算法，SimALS4是否会有更好的分类准确度和排序准确度？

本文使用推荐系统中最常用的协同过滤算法来与SimALS4进行推荐效果的比较，以判断本文提出的学习资源推荐算法的有效性.

Question2：SimALS1、SimALS2、SimALS3、SimALS4的推荐准确度分别如何？

本文在SimALS1的基础上针对不同的情况，提出了SimALS2、SimALS3和SimALS4.为了验证改进之后的推荐算法是否会提高推荐的准确度，需要对SimALS1、SimALS2、SimALS3、SimALS4的推荐准确度进行比较分析.

5.4 实验结果

Question1的实验结果如图7和图8所示.图7展示了基于用户的协同过滤算法UserCF[15]与SimALS4算法的准确率对比结果.UserCF根据学习者各知识点的测试成绩计算相似的学习者，并将相似学习者的偏好进行推荐.可以看到随着推荐资源个数K逐渐增大，推荐算法的准确率也会逐渐降低，但本文所提出的学习资源推荐算法SimALS4的准确率均要高于UserCF准确率.

图7 准确率对比(Question1)Fig.7 Comparison of P(L)(Question1)

图8展示了基于物品的协同过滤算法ItemCF[15]与SimALS4算法的平均排序分对比结果.ItemCF将相似的知识点进行排名，并推荐给感兴趣的学习者.可以看到随着推荐资源个数K逐渐增大，推荐算法的平均排序分也会逐渐升高，但本文所提出的学习资源推荐算法SimALS4的平均排序分均要低于ItemCF的平均排序分.

图8 平均排序分对比(Question1)Fig.8 Comparison of RS (Question1)

通过实验对Question1的解答，可以得出结论：SimALS4比一般的推荐算法准确度更优(较高的分类准确度和较低的排序准确度).

图9 准确率对比(Question2)Fig.9 Comparison of P(L) (Question2)

Question2的实验结果如图9和图10所示.图9展示了SimALS1、SimALS2、SimALS3和SimALS4的准确率对比结果.可以看到，SimALS2、SimALS3、SimALS4的分类准确率均要高于SimALS1分类准确率，而SimALS4的准确率最高，SimALS2和SimALS3的准确率相差无几.

图10展示了SimALS1、SimALS2、SimALS3和SimALS4的平均排序分对比结果.可以看到，SimALS2、SimALS3、SimALS4的平均排序分均要低于SimALS1平均排序分，而SimALS4的平均排序分最低，SimALS2和SimALS3的平均排序分相差无几.通过实验对Question2的解答，可以得出结论.