一种基于知识地图的多约束学习路径推荐方法

摘要

本发明公开了一种基于知识地图的多约束学习路径推荐方法：首先，结合课程知识地图和用户在移动端和PC端的学习日志，在知识地图上对知识元进行标记，生成用户在t时刻的已学知识子图G(id,t)；其次，给定一对起始知识元和目标知识元(S,E)，基于深度优先遍历算法获取(S,E)间的所有路径，进而得到用户目标子图G’(id,t,S,E)；最后，通过计算学习路径的约束因子f，在G’(id,t,S,E)上挖掘满足约束条件的网络学习路径并推荐给用户。本发明解决了不同网络学习场景下，基于知识地图的网络学习路径集成分析与推荐问题，可以为网络学习者提供满足多约束条件的学习路径。

说明书

技术领域

本发明涉及一种网络学习路径分析与推荐算法，特别涉及一种基于知识地图的多约束 学习路径推荐方法。

背景技术

根据联接主义(Connectivism)认知理论的观点，学习是一个不断联接知识节点/资源 的过程，知识间的内在关联在该过程中具有重要作用。最新的认知科学研究也表明：知识 间的关联关系对认知具有显著影响。与传统的文本资源或视频课件相比，知识地图通过知 识元以及知识元之间的关系很好地展现了知识间的关联关系。通过知识元检索功能，学习 者可以很容易找到自己感兴趣的知识元，进而通过知识元之间的关系进行导航式学习。但 知识迷航、知识过载等问题也随之而来。因此，如何结合用户的先验知识和学习目标，为 用户推荐个性化的学习路径是基于知识地图学习中亟待解决的一个重要问题。

从已有的研究来看，Vazquez等提出基于蚁群优化的学习路径生成方法，该方法采用 贝叶斯网络描述知识单元之间的认知序关系；程岩等提出基于群体智能的学习路径推荐方 法，选取邻近用户对启发信息与信息素的贡献进行路径的选择；Yang等人通过对学习风格 进行分类，测量了某一学习路径被某一特定学习风格用户采用的频率，从而提高了群体智 能算法的效率；Chun-HsiungLee和Gwo-GuangLee等提出建立“鹰架学习路径”，通过挖 掘评估优秀学生的学习路径来建立学习导航路径，但该方法面临优秀学生日志缺失的问 题；张超等根据知识地图上知识单元之间的学习先后序关系计算出了知识地图节点的偏序 层次，对目标知识节点补偿集以学习中心度进行再次排序，得出学习导航路径；Kuo-Kuang Chu等人提出用本体的思想解决学习导航路径的生成问题。

综合来看，以上研究中并没有针对移动端和PC端混合学习的路径分析，且普遍缺乏 对知识间本身约束的考虑，未考虑学习者当前的先验知识到学习目标的必要性，也忽略了 学生间先验知识的不同，且多针对某些特定属性或者特定目标进行路径生成，缺乏对用户 需求的全面定制分析。

发明内容

本发明的目的在于提供一种基于知识地图的多约束学习路径推荐方法。

为达到以上目的，本发明采用了以下技术方案：

1)采用邻接矩阵表示知识地图

将某门课程的知识地图中各知识元的依赖关系用邻接矩阵表示，得到所述知识地图的 邻接矩阵；

2)获取用户的已学知识子图

依据标识号为id的用户的学习日志，在所述知识地图的邻接矩阵上对所述用户学习知 识元的情况进行标注，得到所述用户在t时刻的已学知识子图G(id,t)；

3)构造用户目标子图

经过步骤2)后，在所述用户的已学知识子图G(id,t)上获取学习知识元对(S,E)中起 始知识元S与目标知识元E之间的所有学习路径，得到用户目标子图G'(id,t,S,E)；

4)获得满足约束条件的推荐路径

根据给定的约束条件，计算步骤3)获取的每条学习路径的约束因子，根据约束因子 从用户目标子图G'(id,t,S,E)中确定满足约束条件的学习路径并推荐给所述用户。

对于包含n个知识元的有向知识地图KM＝(KU,KE)，ku_i∈KU，ku_j∈KU， 0≤i<n，0≤j<n，i≠j，定义一个n×n的矩阵A＝(a_ij)_n×n，若矩阵A满足公式(1)， 则称A是KM的邻接矩阵：

$\left(\begin{array}{cc}{a}_{ij}=1& ({\mathrm{ku}}_i,{\mathrm{ku}}_j)\in KE\\ a_{ij}=0& ({\mathrm{ku}}_i,{\mathrm{ku}}_j)\notin KE\end{array}\right)---\left(1\right)$

其中，KU表示KM中的知识元集合，KE表示KM中知识元间的邻接关系集合。

所述用户的已学知识子图G(id,t)采用邻接矩阵表示，对于每个知识元采用存放于数组 的权值进行标注，权值包括用户是否学习过知识元的标记、用户对知识元的学习次数、学 习端来源以及该知识元是否适合于移动端学习。

G(id,t)＝{ku,ke,(sig,w,p,mo)}

其中，ku表示知识地图上的知识元；ke表示知识元之间的邻接关系；sig是用户在知 识元ku上的学习标记，sig＝1表示学习过的知识元，sig＝0表示没有学习过的知识元； w是用户在知识元ku的学习次数；p表示用户学习知识元ku的学习端来源，p＝-1对应 未学习知识元学习端不确定的情况，p＝0代表来自PC端，p＝1代表同时来自移动端和 PC端，p＝2代表来自移动端；mo表示根据知识元ku对应视频的长短，确定知识元ku是 否适合移动端学习，mo＝0表示知识元ku适合通过PC端学习，mo＝1表示知识元ku适 合通过移动端学习。

在G(id,t)上利用深度优先遍历算法获取起始知识元S与目标知识元E之间的所有学 习路径。

所述约束条件为未学知识元个数、加权路径长度、学习路径长度或适合移动端学习中 的任意一种或多种的组合。

所述约束因子的计算方法如公式(2)所示：

$f=\alpha \times \frac{n_t}{m_u+1}+\beta \times \frac{1}{l_w}+\gamma \times \frac{l}{l_M}+\eta \times \frac{l}{l_{mo}}---\left(2\right)$

其中，m_u是所述起始知识元S与目标知识元E之间某一学习路径中包含的未学知识元个 数；n_t是用户的已学知识子图G(id,t)包含的未学知识元个数；l是所述起始知识元S与 目标知识元E之间某一学习路径的学习路径长度；l_w是所述起始知识元S与目标知识元E 之间某一学习路径的加权路径长度，所述加权路径长度是指一条学习路径上包含的知识元 的权重之和，记为w_i是该学习路径中的第i个知识元的权重，所述权重的取 值为对应知识元的学习次数；l_M是所述起始知识元S与目标知识元E之间学习路径长度的 最大值，学习路径长度用一条学习路径包含的已学和未学知识元个数总和表示；l_mo是所述 起始知识元S与目标知识元E之间某一学习路径中适合移动端学习的知识元个数；α、β、 γ和η是权重因子，其中α、β和γ的取值范围均为[0，1]，η取值为0或1，0表示不区分 学习端，1表示推荐采用移动端学习。

根据公式(2)计算出所述起始知识元S与目标知识元E之间所有学习路径各自的约束 因子，并将约束因子取值最小的学习路径推荐给所述用户。

与现有技术对比，本发明的有益效果体现在：

本发明以基于知识地图的网络学习为背景，通过用户学习日志，构建用户的已学知识 子图和用户目标子图，进而提出一种面向多终端网络学习的学习路径推荐算法。该算法考 虑了移动端学习者在学习时间和学习内容上更加呈现离散化、碎片化等特点，解决了移动 端和PC端混合学习出现后基于知识地图的网络学习路径集成分析与推荐问题，并且可以 为网络学习者提供满足多约束条件的学习路径。

附图说明

图1为本发明方法涉及的数据处理流程图；

图2为本发明涉及的用户的已学知识子图，图中括号内数字对应(sig,w,p,mo)；

图3为本发明(ku₂,ku₅)的用户目标子图，图中括号内数字对应(sig,w,p,mo)。

具体实施方式

下面结合附图和实施例对本发明作详细描述，所述是对本发明的解释而不是限定。

不同于传统的网络学习路径分析与推荐，本发明方法应用于基于知识地图(又称主题 图)的网络学习模式。这里知识地图是以知识元为节点，由知识元与其之间的学习依赖关 系构成的有向图，是描述某一个领域(课程或学科)内的知识以及这些知识之间的关联的 实体。知识元是指具有完备表达能力的基本知识单位，诸如定义、定理、算法等。通过知 识元检索功能，学习者可以很容易找到自己感兴趣的知识元，进而通过知识元之间的关系 进行导航式学习。与传统的面向文本资源或课件资源的网络学习系统相比，基于知识地图 的网络学习模式以知识地图的形式对学习资源进行组织，能为用户提供更加细粒度的知识 元导航式学习。

随着移动学习的发展，网络学习的形式更加多元化。用户既可以采用传统的PC端学习， 也可以采用手机、平板电脑等移动设备进行随时随地的自主学习。相比PC端而言，移动 端学习者在学习时间和学习内容上更加呈现离散化、碎片化等特点，学习内容之间缺乏连 贯性。另一方面，网络教育中学习者的知识背景不同、学习目标不同，如何结合用户学习 目标，通过有效分析用户在不同终端的碎片化学习行为，从而为用户提供个性化的学习指 导是本发明研究的重点。本发明针对知识地图下的网络学习，提出基于知识地图的多约束 学习路径推荐算法，用于根据用户的约束条件生成所需的学习路径；另一方面，本发明融 合用户在不同学习端的日志数据，动态记录学习轨迹，结合用户的先验学习知识和学习目 标，生成个性化学习路径。本发明所述基于知识地图的多约束学习路径推荐算法，主要包 括以下几个方面：

1)采用邻接矩阵表示某门课程的知识地图

知识地图的邻接矩阵完整地表示了知识地图中各节点间的依赖关系(邻接关系)。对于 包含n个节点的有向知识地图KM＝(KU,KE)，ku_i,ku_j∈KU，0≤i<n，0≤j<n， i≠j，定义一个n×n的矩阵A＝(a_ij)_n×n，满足公式(1)，则称A是知识地图KM的邻接矩 阵：

$\left(\begin{array}{cc}{a}_{ij}=1& ({\mathrm{ku}}_i,{\mathrm{ku}}_j)\in KE\\ a_{ij}=0& ({\mathrm{ku}}_i,{\mathrm{ku}}_j)\notin KE\end{array}\right)---\left(1\right)$

2)生成用户的已学知识子图

依据用户在移动端和PC端的学习日志，在知识地图上对知识元进行标注，得到一个包 含节点标记的有向图称为用户的已学知识子图，记为G(id,t)。相应的，采用邻接矩阵表 示用户的已学知识子图，用数组存放每个知识元的权值。权值可以包括学习标记、用户对 知识元的学习次数、学习端来源(移动端、PC端)以及该知识元是否适合于移动端学习：

G(id,t)＝{ku,ke,(sig,w,p,mo)}

ku表示知识地图KM上的知识元，ku∈KU；ke表示知识元之间的依赖关系， ke∈KE；sig是用户在知识元上的学习标记，sig＝1表示学习过的知识元，sig＝0表 示没有学习过的知识元；w是用户(标识号为id)在知识元ku上的权重，这里将权重定 义为学习次数。p标记用户在哪个用户端学习的知识元，p＝-1对应未学习知识元学习端 不确定的情况，p＝0代表来自PC端，p＝1代表同时来自移动端和PC端，p＝2代表来 自移动端。mo表示根据知识元对应视频的长短，确定其是否适合移动端学习，一般的对 于较长的视频推荐PC端学习。根据视频长短确定一个时间阈值，大于等于时间阈值的视 频，mo＝0，表示知识元适合通过PC端学习，反之，小于时间阈值的视频，mo＝1，表 示知识元适合通过移动端学习。

3)生成用户目标子图

在G(id,t)上获取起点为S、终点为E之间的所有学习路径，可以采用常规算法，例 如深度优先遍历算法，S为起始知识元，E为目标知识元，即学习知识元对(S,E)，从而 构建用户目标子图G'(id,t,S,E)。

4)计算约束因子

约束因子的计算如公式(2)所示：

$f=\alpha \times \frac{n_t}{m_u+1}+\beta \times \frac{1}{l_w}+\gamma \times \frac{l}{l_M}+\eta \times \frac{l}{l_{mo}}---\left(2\right)$

其中，m_u是学习路径中包含的未学知识元个数，n_t是用户的已学知识子图中包含的所 有未学知识元个数，l是学习路径长度，l_w是加权路径长度，l_M是用户的已学知识子图中 (S,E)之间的最长学习路径长度，l_mo是学习路径中适合移动端学习的知识元个数，α、β、 γ和η是权重因子。随着权重因子的不同，f可以表示不同的约束条件，分别对应不同的 学习需求。

5)获得满足多约束条件的推荐路径

对于用户的已学知识子图上(S,E)之间的所有学习路径，根据约束条件，计算所有学 习路径各自的约束因子，从而确定满足约束条件的学习路径，并推荐给用户。

下面举例说明本发明的数据处理流程，如图1所示：

1.图的邻接矩阵表示

在提出多约束路径生成算法之前，首先确立知识地图的存储形式，这是学习路径分析 的前提。本发明采用邻接矩阵表示知识地图，知识地图的邻接矩阵完整地表示了图中各节 点间的邻接关系。

定义邻接矩阵：对于包含n个节点的有向知识地图KM＝(KU,KE)，ku_i,ku_j∈KU， 0≤i,j<n，定义一个n×n的矩阵A＝(a_ij)_n×n，满足公式(1)，则称A是知识地图KM的 邻接矩阵。

$\left(\begin{array}{cc}{a}_{ij}=1& ({\mathrm{ku}}_i,{\mathrm{ku}}_j)\in KE\\ a_{ij}=0& ({\mathrm{ku}}_i,{\mathrm{ku}}_j)\notin KE\end{array}\right)---\left(1\right)$

以“汇编语言程序设计”课程为例，该课程的知识地图中包含总节点(知识元)57个， 总边65条，如表1所示。

表1“汇编语言程序设计”知识地图信息

2.生成用户的已学知识子图

每一门课程或者学科的知识元都可以组建成一个有向知识地图。学习者依据学习目标 及其自身的背景知识，在知识地图上进行自主学习，既可以按照知识元的上下位关系进行 顺序学习，也可以跳过自己掌握的知识元进行有选择的学习。依据用户的学习日志，在知 识地图KM上知识元进行标记，得到用户的已学知识子图。表2是用户在“汇编语言程序 设计”课程上的部分学习日志。其中“平台号”记录用户访问的是哪个平台，“3”代表移 动端，“2”代表PC端。

表2用户学习日志

定义用户的已学知识子图(users'sub-learninggraph)：依据用户学习日志，在知识地 图上对知识元进行标注，得到一个包含节点标记的图称为用户的已学知识子图，记为 G(id,t)＝{ku,ke,(sig,w,p,mo)}。图2给出了三个不同用户的已学知识子图示例。生成 用户的已学知识子图的具体步骤是：

步骤1：打开知识地图文件km.txt，读取节点和边；

步骤2：生成邻接矩阵it；

步骤3：打开用户日志文件log.txt；

步骤4：从文件读取用户标识号id以及知识元序号b；

步骤5：在it矩阵上标注该用户已学知识元、次数及学习端来源等；这里将单次学习 时长超过知识元对应视频时长80％的网络学习记为一次有效学习，学习次数以有效学习为 准进行统计。

步骤6：输出该用户在某一时刻t的用户的已学知识子图G(id,t)。

3.生成用户目标子图(即获取S和E之间的学习路径)

定义用户目标子图(users’goalgraph)：在G(id,t)上获取起点为S、终点为E的 学习知识元对(S,E)之间的学习子图，记为用户目标子图G'(id,t,S,E)。用户目标子图是 通过获取S和E之间的所有学习路径生成的。下面给出学习路径及其相关定义。

定义学习路径(users’learningpath)：指多个知识元组成的序列，记为 p＝{ku_i,ku_j...,ku_m}，其中ku_i,ku_j,...,ku_m∈KU。

定义学习路径长度(thelengthofusers’learningpath):指一个学习路径上包含的已学 和未学知识元个数总和，记为l＝l_u+l_s，其中l_s表示已学知识元个数，l_u表示未学知识元 个数。

定义加权路径长度(theweightedlengthofusers’learningpath)：指学习路径上包含的 知识元权重之和，记为l_w值越大，表示用户对该路径上包含的知识元学习次数 越多。

图3给出三个不同用户在(ku₂,ku₅)上的用户目标子图。采用深度优先遍历算法生成用 户目标子图的步骤包括：

步骤1：输入用户id，起始节点S，目标节点E；

步骤2：递归调用pathf(s,e)，获取用户的已学知识子图G(id,t)上(S,E)间的所有路 径；

步骤2.1：若s＝e，调用结束，输出路径；

步骤2.2：否则，遍历用户的已学知识子图上的节点，如果(S,E)间有边且另一点

不在已有的路径内，把该点添加到路径中；

步骤3：输出用户在(S,E)间的目标子图G'(id,t,S,E)。

以“汇编语言程序设计”课程为例，程序读取处理后的用户日志文件log.txt和知识 地图文件km.txt，生成用户目标子图，包含路径信息(路径总数，每条路径的长度，加 权路径长度，未学知识元个数，适合移动端学习的知识元个数)以及起始节点S到目 标节点E的所有路径，存储为以用户id为名的文本文件。现选取起始知识元S为知识 元序号为5的知识元，目标知识元E为知识元序号为30的知识元，计算出XX035用 户在(5,30)间的所有学习路径如表3所示。

表3用户XX035在(5,30)间的所有路径

4.生成满足多约束条件的学习路径

约束学习路径是指满足一定约束条件的，在用户目标子图上通过图搜索生成的学习路 径。以网络教育学院为例，可以生成适合用户考前复习的包含未学知识元个数最少的路径 或者最短路径。

定义约束学习路径(theconstrainedlearningpath)：在G'上满足约束条件c的(S,E) 之间的学习路径，记为P(S,E,G',c)＝{s'}，其中s'∈G'。

这里的约束条件(constraintcondition)可以是路径长度、未学知识元个数等单个约束条 件，或是多个约束条件的结合；

$f=\alpha \times \frac{n_t}{m_u+1}+\beta \times \frac{1}{l_w}+\gamma \times \frac{l}{l_M}+\eta \times \frac{l}{l_{mo}}---\left(2\right)$

随着权重因子的不同，f可以表示不同的约束条件，选择不同的学习路径，推荐给不 同学习需求的用户。η＝0表示不区分学习端，η＝1表示推荐采用移动端学习。比如：

β＝0，γ＝0，α＝1，η＝0：所推荐给用户的路径中包含的未学知识元个数越多，f值 越小，适用于用户进行知识元的查漏补缺；

α＝0，β＝1，γ＝0，η＝0：路径中已学习知识元的次数越多，值越小，f值越小， 适用于用户回顾已学知识元；；

α＝0，β＝0，γ＝1，η＝0：路径中包含的知识元个数越少，值越小，f值越小，适 用于推荐最短学习路径；

α＝0，β＝0.5，γ＝0.5，η＝0：路径短且已学习知识元的次数多，为用户推荐快速学习 路径，可用于考前突击；

η＝1时，α、β和γ可以是上述的任一种组合，用于表示移动学习端的各种需求。值越 小，路径中所包含的适合移动端学习的知识元越多，适用于推荐给偏好移动端学习的用户。

在用户目标子图上查找起点为S、终点为E的学习知识元对(S,E)之间的满足约束条 件的学习路径P＝{s'}，从而对学习者进行个性化的学习路径推荐。这里的约束条件是 指用户给定的学习需求，针对不同的学习需求，约束因子的权重因子取值不同。

生成满足多约束条件学习路径的具体步骤是：

步骤1：输入用户目标子图G'(id,t,S,E)，学习路径约束条件c；

步骤2：计算约束因子f中的对应各个参数(m_u、n_t、l_w、l、l_M以及l_mo)；

步骤3：计算每一条学习路径的约束因子f的值；

步骤4：返回满足约束条件c的学习路径P(S,E,G',c)并输出；

基于上述算法，对XX035用户求得的推荐路径如表4所示。

表4XX035用户的推荐路径