基于知识图谱的多目标学习资源推荐算法①

东 苗

(上海行健职业学院 信息技术与机电工程系,上海 200072)

随着“互联网+”的发展,各种E-learning在线学习系统在教育领域中普遍应用,海量的网络教学资源在为用户提供了便利的同时,也出现了“认知过载”和“学习迷航”等问题.为解决这些问题,个性化推荐系统应运而生,根据用户的信息需求、兴趣偏好等,将匹配度高的资源推荐给用户.推荐策略主要包括:基于内容的推荐、协同过滤推荐、混合推荐、基于网络结构的推荐、基于关联规则的推荐、基于知识的推荐等[1–6].学习资源的推荐与电影、音乐、旅游等商品推荐的不同之处在于:除了用户的兴趣偏好之外,还应考虑用户的认知水平、学习目标等个性化因素,以及知识点之间的逻辑关系.

2012年谷歌正式提出了“知识图谱”这个术语,知识图谱旨在描述真实世界中存在的各种实体或概念,以及他们之间的关联关系[7].在知识图谱中,将每条知识表示为<实体,实体关系,实体>或<实体,属性,属性值>的三元组,将所有数据组织成一张有向图[8].基于知识图谱的推荐方法大致分为基于本体(Ontology)的推荐生成和基于开放链接数据(LOD)的推荐生成两大类[7],近年来广泛地应用在旅游推荐、电影/音乐推荐、电子商务和职位推荐等领域.

因此,本文将知识图谱融入学习资源推荐模型,构建语义网络,综合考虑用户的兴趣偏好、学习资源所涵盖知识点的关联度与中心度,建立多目标优化模型.使用自适应多目标粒子群(AMOPSO)算法得到Pareto最优解集,进行个性化学习资源的推荐.

1 学科知识图谱的构建

本体这一概念源于哲学领域,是对某一特定领域中共享概念模型的明确的形式化规范化说明,包含了“概念模型”、“明确化”、“形式化”和“共享”4 层含义[9].利用本体进行知识表示有利于呈现目标知识的逻辑关系,查询以及共享.在学科资源本体模型中知识点是资源描述的基本单位,每个知识点对应多个相关的学习资源,包括文本、图像、音视频等[8].将知识点作为知识图谱中的实体,将知识点的特征作为知识点实体的属性,以这样的规则关联到知识图谱中展开研究.本体的构建方法和表示语言有很多种,适用于不同的学科领域和工程应用.本文首先抽取知识点并挖掘知识点之间的关联关系和知识点的属性,然后根据知识点结构构建学科知识图谱.

1.1 实体抽取

在学科知识图谱中将知识点作为图谱中的实体,实体抽取即提取出教学资源中的概念、定义、定理、性质、公式等领域术语.常用的实体抽取方法有基于规则与词典的方法、基于传统机器学习识别的方法、基于深度学习的抽取方法等[10].本文利用网络爬虫从指定的网页上完成对学习资源文本内容数据的抓取和保存,使用中国科学院计算技术研究所分词工具NLPIR进行数据清洗和预处理后,通过TF-IDF算法进行知识点的提取.TF-IDF算法采用文本逆频率IDF(Inverse Document Frequency,逆文本频率指数)对TF(Term Frequency,词频)值加权取权值大的作为关键词.

其中,nij表示词条ti在学习资源dj中的词频,表示学习资源dj中的全部词条数,|D|表示课程学习资源库中全部的文档数,表示包含ti的学习资源文档数,|N|表示学习资源dj中词条的个数.

1.2 关系抽取

关系抽取是为了解决实体间语义链接的问题.Google 推出的Word2Vec 通过训练将每个词映射成K维实数向量后,可通过词之间的距离(比如余弦相似度、欧氏距离等)来判断它们之间的语义相似度,然后在词条间建立其层次关系树.本文中根据实际需要,定义以下5 种知识点之间的关系:前驱关系、后继关系、包含关系、并列关系、同义关系.具体含义如表1所示.

表1 知识点间的关系定义

1.3 本体构建

本文以C 语言程序设计课程为例,采用斯坦福大学开发的Protégé工具进行本体的构建.如图1.

图1 课程本体部分关系示例

2 基于知识图谱的多目标学习资源推荐模型的构建

2.1 学习资源数学模型的建立

学习资源特征用向量R=(V(R),T(R))表示.其中,V(R)={vi|1≤i≤N}表示学习资源R与N个知识点的关联关系.资源是由一个或多个知识点组合而成的,vi即学习资源R与第i个知识点ki之间的相关系数.资源类型分为文本、图片、音视频、互动软件4 种,很多学习资源同时采用多种表达方式,因此用向量T(R)={t1,t2,t3,t4}描述学习资源R采用各种知识表达方式的程度,s.t.0≤t1,t2,t3,t4≤1,且

2.2 用户数学模型的建立

将用户特征模型表示为:U=(K(U),P(U)).其中,K(U)表示由用户历史学习行为得到的用户知识库.P(U)={p1,p2,p3,p4}表示用户U的学习风格,学习风格的不同对学习资源类型的选择会有影响,依据Kolb学习风格类型将学习风格类型分为发散型、聚合型、同化型和调节型4 种.同一个用户会表现出多种学习类型的倾向,p1、p2、p3、p4分别表示用户U属于4种学习风格的倾向程度,s.t.0≤p1,p2,p3,p4≤1,且

2.3 基于知识图谱的推荐模型

本文提出基于知识图谱的多目标学习资源推荐模型.本模型包两个目标函数:学习资源包含的知识点与用户知识库的距离(Resource Knowledge Distance,RKD)和用户对学习资源类型的偏好(Resource Type Preferences,RTP),即Func={RKD,RTP},两者决定推荐的学习资源与用户特征的符合程度.

学习资源包含的知识点与用户知识库的距离如下:

其中,K(R)表示学习资源R的所包含的知识点库;K(U)表示用户知识库;ki表示学习资源R的所包含的用户尚未掌握的知识点;S hortestPath(ki,K(U))表示知识点ki与用户知识库K(U)中所有知识点的最短路径,Degree|ki|表示知识点ki的度.度为知识点在整个知识图谱中影响力的大小,代表了知识点的重要程度[11].

如图2示例,用户知识库K(U)={k1,k2,k3},每个学习资源可涵盖一个或多个知识点,资源知识库K(R1)={k5},K(R2)={k4,k7},K(R3)={k2,k4}.可分别计算资源到K(U)的距离:

计算后得到距离K(U)最小的资源即最值得推荐的学习资源.

学习资源类型与用户学习偏好之间的差异如下:

其中,ti表示学习资源类型,s.t.0≤ti≤1,且pi表示用户学习偏好,s.t.0≤pi≤1,且

图2 用户知识库与资源知识库的关系示意图

3 基于知识图谱的多目标学习资源推荐模型求解

个性化学习资源推荐问题是一个多目标优化问题(MOP),本文采用自适应多目标粒子群算法(AMOPSO)进行基于Pareto 非劣解集下的多目标规划.粒子群算法(PSO)是一种模拟鸟群觅食的随机搜索算法,能够在一次迭代过程中产生多个Pareto 近似最优解,在求解多目标优化问题上具有较强的优势.AMOPSO 充分利用PSO 快速收敛的优点,兼顾避免陷入局部极值的弱点,通过进化环境反馈信息来自适应调节粒子运动参数和极值扰动策略,从而有效平衡开发与开采过程,保证粒子具有很好的全局搜索能力和较快的收敛速度[12,13].

3.1 自适应多目标粒子群算法

标准多目标粒子群算法(MOPSO)迭代公式为:

其中,r1、r2为0～1 之间均匀分布的随机数;pi为粒子个体的最佳位置;pg为群体所发现的最佳位置;xi(t)为t时刻粒子的位置;vi(t)为t时刻粒子的速度;ωi为算法惯性权重;c1、c2为学习因子.

MOPSO有迭代初期局部搜索能力较弱、迭代后期易陷于局部最优的缺点[14].为了平衡MOPSO 算法的全局搜索能力和局部更新能力,自适应多目标粒子群算法(AMOPSO)采用非线性的惯性权重因子公式,使惯性权重因子 ωi随粒子的目标函数值而自动改变,当各粒子的目标函数值趋于一致或趋于局部最优时,使 ωi增大;当各粒子的目标函数值较为分散时,使ωi减小.

其中,fi为粒子当前的目标函数值;假定当前所有粒子的平均目标值为favg,favg1、favg2分别为目标函数值大于favg的粒子的平均目标值和目标函数值小于favg的粒子的平均目标值;α为种群多样性的指标.

c1、c2第t次迭代时取值公式为:

其中,c1,ini和c2,ini分别代表c1、c2的初始值,c1,fin和c2,fin分别代表c1、c2的迭代终值.改进后的速度权重自适应变化因子 ωi可以有效的平衡算法的搜索区域,学习因子的异步变化使得粒子加强了算法初始阶段的全局搜索能力,在算法后期有利于收敛到全局最优.

3.2 算法流程

以最小值 minFunc=min{RKD,RTP}为目标的自适应多目标粒子群算法流程(如图3)如下:

Step 1.初始化种群和速度.计算目标函数值并将非支配解加入外部种群存档NDset.

Step 2.将本次迭代中内部种群中的非支配解复制至NDset,并删除其中的重复个体.计算NDset中所有个体的拥挤距离并按降序排列,取前M(设定的外部种群最大个体数)个.

Step 3.更新全局最优位置.

Step 4.根据式(11)计算自适应权重系数 ωi,粒子更新速度vi和位置xi,判断速度和位置是否越界,如果速度越界则取边界速度值,如果位置越界则取范围内随机位置.

Step 5.判断是否满足终止条件,如果达到则输出NDset,获得Pareto 最优解集;否则,t=t+1,返回Step 2 继续运行.

图3 AMOPSO 资源推荐流程图

4 实验与分析

4.1 实验环境与数据集

本文利用Matlab R2016a 实现上述算法,为了观测算法的有效性和可行性,以标准MOPSO、AMOPSO做对比实验分析推荐性能的差别.求解后从Pareto 解集中选取Top-10 作为推荐的学习资源;若Pareto 解集中的数据小于10 条,则选择所有的候选集作为推荐内容.

从某网络学习平台数据中爬取了部分包含C 语言课程知识的文档与在线学习数据信息,经过数据清洗和分词处理后抽取知识点和关系,构建课程本体并经过补全形成实验数据集.

4.2 算法参数设置

MOPSO和AMOPSO中特征参数的选取如表2所示.

表2 算法参数设置

4.3 实验结果分析

为了观察推荐效果,使用HV (Hyper Volume)值对实验结果进行分析.由表3和图4可知,AMOPSO的HV 指标最好值、均值、最差值均高于MOPSO,说明AMOPSO的收敛性和多样性优于MOPSO;同时AMOPSO的HV 值分布范围窄于MOPSO,说明AMOPSO的稳定性更好,在进行学习资源推荐时的综合性能更好.

表3 实验中HV 值的统计结果

图4 MOPSO和AMOPSO的HV 箱线图

如图5所示,使用MOPSO和AMOPSO 算法分别进行资源推荐的计算可以得到两个不同的Pareto 前沿面.X 轴为目标函数RTP,表示学习资源类型与用户学习偏好之间的差异;Y 轴为目标函数RKD,表示学习资源包含的知识点与用户知识库的距离.AMOPSO 求得的Pareto 前沿具有良好的分布特征和较好的多样性,且收敛效果更好,表明AMOPSO在Pareto 前沿面上的寻找更有优越性,更适合求解多目标学习资源推荐问题.

图5 MOPSO和AMOPSO的Pareto 前沿面

传统MOPSO 算法采用固定惯性权重因子,AMOPSO中通过式(11)使惯性权重因子 ωi随粒子的目标函数值而自动改变.在迭代初期 ωi较大,粒子以较大的步长进行全局搜索,使得算法快速收敛;在后期ωi较小,趋于精细的局部搜索,有更强的寻优能力.惯性权重随迭代次数的变化曲线见图6所示.

学习因子c1、c2分别调节粒子向个体最优和群体最优方向飞行的最大步长.本文通过式(12)、式(13)使学习因子异步变化,在迭代初期学习因子较大,加强了全局搜索能力;在后期学习因子较小,有利于收敛到全局最优.

图6 AMOPSO 算法惯性权重随迭代次数变化曲线图

4.4 收敛性能分析

反向世代距离(Inverted Generational Distance,IGD)指标可用于评估多目标优化算法中非支配解集对真实Pareto 前沿最优解集的逼近程度.IGD 值越小,表明推荐精度越高,算法收敛性和分布性能越好[15].

其中,P表示真实Pareto 面上的最优解集,|P|为真实Pareto 面上的最优解集的个体数,Q为算法获取的非支配解集,d(v,Q)表示个体v到种群Q的最小欧氏距离.

由表4可知,AMOPSO的IGD 指标均值和方差均比MOPSO 小,表明AMOPSO在收敛性和分布均匀性上均优于标准MOPSO.

表4 实验中IGD 指标的统计结果

4.5 推荐效用的评价指标

本文采用五折交叉验证,将数据集随机分为5 份,每次选取其中一份作为测试集,另外4 份作为训练集,重复5 次,每次选取不同的训练集.将5 次实验的平均值作为推荐效用的评价指标.对推荐算法结果的分析,使用3个指标:查准率(Precision,P),召回率(Recall,R)以及F1-Score 值(F):

其中,TP(True Positive)指推荐了且用户会使用的资源,FN(False Negative)指推荐了但用户未使用的资源,FP(False Positive)指用户喜欢但没推荐的资源,TN(True Negative)指用户不喜欢且没推荐的资源.据上述,P反映了推荐算法的推荐水平;R反映了被推荐算法所推荐的资源占用户真正喜欢的资源的比重;F值是P和R的加权平均,均匀地反映了推荐效果.3个指标通常都是越高越好[15,16].

如图7所示,AMOPSO在P、R、F值上均优于MOPSO,说明AMOPSO 算法在解决本问题时综合性能较高,推荐效果更好.

图7 评价指标条形图

5 结论

本文在进行学习资源推荐时基于知识图谱建立学习资源推荐模型,综合考虑用户的兴趣偏好、用户原有的知识结构与学习资源所涵盖知识点之间的关联度,建立多目标优化模型.对模型求解时使用AMOPSO 算法,个体拥挤距离降序排列进行外部种群规模的缩减和全局最优值的更新,获得了分布特征良好的两目标Pareto 前沿,输出推荐资源序列.实验时通过与经典MOPSO 算法对比并使用HV、IGD 指标对模型进行评价,验证了其多样性和稳定性,证明了算法良好的全局寻优和收敛性能.并采用五折交叉验证,使用查准率、召回率以及F1-Score 值验证了算法的推荐效用.在后续工作中将进一步完善用户模型和学习资源模型,优化推荐算法以提升学习资源推荐性能.