一种新的自动概念图生成模型C-IK2

邬宝娴,谢 燚,郝天永,沈映姗

(华南师范大学 计算机学院,广东 广州 510631)

0 引言

随着教育信息化和现代化水平的不断提升,个性化教学和个性化测试系统应运而生。这些系统能够根据学习者的能力、行为和学习结构来定制学习内容[1-5]。因此,教师可以根据学生的具体学习情况来制定相应的教学策略。概念图是一种用节点代表概念、连线表示概念间关系的图示法,即利用图示的方法表达人们头脑中的概念、思想和理论等,其为教师提供了进一步分析和完善教学策略的方法。Markhan等人[6]提出将概念图作为一种教学原理和理论运用到教学活动中来帮助师生提高教学质量。在教学过程中,利用概念图可以帮助教师构建知识网络,以便于教师对相关知识点之间的内容进行梳理,促进学生进行有意义的学习。但是,有效地创建概念图是一项既复杂又耗时耗力的任务。因此,研究如何有效地自动生成概念图是必要的。

现有研究人员对概念图进行了诸多研究,并提出了一系列概念图的自动生成方法。Atapattu等人[7]提出了一种自然语言处理(NLP)算法,利用该算法从幻灯片中进行“概念-关系-概念”三重提取,形成概念图,替代了专家手工生成概念图的方法。然而,其生成的概念图是静态的,不能反映学生学习过程的连续表现,无法有效地分析出学生的学习理解能力。Huang等人[8]通过考虑问题的错对错关系和正确对正确关系,更精确地计算概念之间的关联度,从而提高概念图的准确性,该方法生成的概念图针对的是所有学生,忽略了不同学生对知识掌握程度的差异。Shao等人[9]提出TA-ARM自动生成概念图算法,该算法考虑概念之间的关联性,使用文本分类算法,并结合关联规则挖掘方法生成概念图。但该算法生成的概念图只考虑了概念间的方向性,没有考虑概念间内在的结构,很难从概念图中得到学生对概念的有效理解。

随着自动概念图生成方法研究的发展,贝叶斯网络作为一种概率图模型,近年来在自动概念图生成研究上得到了重视。贝叶斯网络的图结构表示为节点及节点之间的连边,边表示两个节点变量为因果关系。Alfonso[10]使用贝叶斯网络概念图模型,该模型采用关联规则挖掘技术来分析多项选择考试问题的学生答案,进而针对特定学习领域半自动地生成精准的能力图。Cooper 和 Herskovits[11]提出K2算法,该算法是基于两阶段的贪婪启发式算法。其第一阶段是对搜索空间进行剪枝;第二阶段是搜索满足有向图约束的网络结构,该算法的结果受输入变量的排序影响,因此,找到最佳变量排序顺序对提高算法性能至关重要。基于K2算法序列改进的图研究近年来得到越来越多的重视,例如,Tabar等人[12]提出利用L1正则化马尔可夫链获得K2算法的输入序列,以改进K2算法。但现有研究普遍存在准确性不高问题,并且存在忽视图质量这一重要指标的问题。

综合以上讨论,本文提出了一种新的自动概念图生成模型C-IK2,以解决概念图不能反映学生对概念的理解程度,同时忽略不同学生对概念的接受程度不同的问题。本文生成了概念之间具有内在层次关系的概念图,弥补现有研究仅考虑概念间关系的缺陷,为教师提供概念教学计划的指导。本文调研了LPG(Learning Paths Automatic Generation Algorithm)算法[13]所构造概念图的局限性。该算法虽然能够生成简洁的有向无环图,揭示概念之间的相互关系,但忽略了概念之间的层次关系,使得在教学等差异化应用中作用受限。K2算法是构建具有层次结构贝叶斯网络图方法,通过与LPG算法的结合,能够为构建具有层次结构的概念图提供新的思路。然而K2算法存在一个缺陷,即所使用的节点序列是以递增方式作为输入,而未充分考虑节点序列之间的实际关系。因此,在构建具有层次结构的概念图时,还需要充分考虑节点序列的关系,以更准确地反映概念之间的层次结构和相互关系。C-IK2 模型以LPG算法构造作为中间件以生成有效序列,该序列作为K2算法的输入序列,生成概念图。最终模型通过将改进K2算法和LPG算法结合形成一种新的自动化概念图生成模型。

本文主要贡献如下:

(1) 提出新的学习路径生成方法作为K2算法的输入序列。

(2) 构建基于LPG算法与K2算法相结合的C-IK2模型,用于生成具有层次结构特点的概念图,改进传统路径教学中的单一方向性问题,通过层次结构展现了概念之间的深度联系。

(3) 实验结果表明,C-IK2模型在图准确度和图结构质量上优于现有基于评分的贝叶斯网络结构学习方法。

1 国内外研究现状

1.1 自动概念图生成研究

近年来,智慧学习系统变得越来越流行,该系统可以根据学生的能力为学生提供定制的课程,以达到个性化学习的目的。为了满足个性化学习的需求,教师常常利用概念图为学生制定个性化的学习方案,从而更好地开展教学。然而,手动创建概念图既费时又费力。因此,如何实现概念图的自动生成已成为当前个性化学习研究的热点问题。Chen等人[14]为了实现从学术文章中生成电子信息领域概念图,以该领域的相关期刊文章和会议论文作为数据源,利用文本挖掘技术自动生成学习领域的概念图。Wang等人[15]提供了一个框架用于生成特定类型的知识图,即来自教科书的概念图。这些研究直接从教学文本分析中生成概念图,在一定程度上为教师合理根据教材进行教学过程设计提供一定参考,帮助学生更好地理解教材概念。盛泳潘等人[16]提出基于开放域抽取的多文档概念图构建方法。该方法先对文档进行排序,然后从多篇文章中抽取出大量具有事实表达能力的三元组实例。通过关系实例过滤算法得到显著关系实例,并构成多个概念子图,接下来进一步合并其中的等价概念,合并或增加新的关系类型,最终形成一张连通的概念图。然而这些直接从文本中提取关键字的方法并没有分析学生的学习行为,因此无法确定学生对概念的熟悉程度,也无法从学生的角度出发判断该概念图的创建是否真的适应学生的学习要求。

Tseng等人[17]提出了一个两阶段概念图构造方法(TP-CMC),通过学习者的历史测试记录自动生成概念图,第一阶段用于预处理测试记录,即转换数字等级数据和完善测试记录,并从输入数据中挖掘关联规则;第二阶段用于转换挖掘的关联规则,学习概念之间的先决条件关系以生成所有学习者概念图。Romero等人[18]提出了一种基于概念图的学习策略,学生自己生成概念图并将生成的概念图与其教师生成的概念图进行比较,发现学生在概念把握方面的不足。这些研究生成的概念图反映所有学生的学习情况,所有学生都以相同的学习方式和学习路径进行学习,如果后续要对概念图进行进一步分析则会相当耗时。Li等人[13]充分考虑了不同学生群体的学习性能,利用聚类算法和关联规则挖掘生成了具有不同学习特征的概念图,并利用拓扑排序算法生成了几种简化的学习路径,该算法生成的概念图考虑了概念间的联系,但是没有考虑概念间的内在结构层次。

总的来说,对概念图的研究分为三种类型。第一类利用文本挖掘技术直接从文本中提取概念以生成概念图,然而生成的概念图缺乏进一步的分析,不能反映学生对概念的实际理解程度;第二类研究考虑学生的学习表现,但是生成的概念图反映了所有学生的学习表现,不能根据学生对概念的掌握程度来区分学生;第三类研究能区分不同学生的学习情况,却不能反映概念之间的内在层次关系,无法指导教师制订概念教学计划。

1.2 贝叶斯网络结构学习方法

贝叶斯网路结构学习方法主要分为基于约束的贝叶斯网络结构学习方法和基于评分的贝叶斯网络结构学习方法[19]。基于约束的贝叶斯网络结构学习方法使用一系列的条件假设检验来学习模型中变量之间的独立性从而生成有向图。PC(PredictiveCausation)和IC(InductiveCausation)是这类方法的著名例子。基于评分的贝叶斯网络结构学习方法是通过衡量其评分函数从而找到最好有向图的,即当给定数据集D={D1,D2,…,Dn}时,找到一个结构G*,使得G*满足式(1)的条件。

(1)

其中,Gn为变量集V={X1,X2,…,Xn}在有向图搜索空间中的所有可能结构。

基于评分的贝叶斯网络结构学习方法有GOBNILP算法[20]、贪婪爬山搜索算法[21]、贪婪最大最小爬山算法[22]、K2算法[23]等。本文主要研究K2算法,该算法是以给定优先序列节点作为输入,从数据中学习到使得贝叶斯网络后验概率最大的贝叶斯结构网络。K2算法通过输入节点的先后顺序来降低计算复杂性,因而生成合理的点序列至关重要。基于K2的改进方法可以分为基于约束方法改进K2方法、基于互信息改进K2方法、基于先验序改进K2方法、基于领域知识改进K2算法和基于图论改进K2方法[24]。Aouay等人[25]提出一种基于粒子群算法和K2算法的结构学习新方法,此处的粒子群算法用于在有序空间中进行搜索,然后通过运用K2算法返回与其相符的贝叶斯网络。Chen等人[26]使用互信息(MI)和独立性检测来获得节点的正确排列。Ko 和 Kim[27]提出了一种新的评价度量方法,用来评估条件频率以确定节点的顺序,该算法让孩子节点的父节点使用离散Dirichlet概率密度函数,通过验证条件频率使子节点在连接到正确的父节点时具有更大的条件概率。Ai[28]证明了信息熵可以作为一个有效的度量指标来评估每个节点的重要性,可以将熵从低到高排序来建立节点的有效顺序。刘艳杰等人[29]提出以学生7门主干学科成绩作为数据样本,用节点间的条件互信息对各节点进行条件独立性检测, 确定贝叶斯网络的初步结构, 再利用K2算法进行全局优化, 最终确定网络结构。

虽然这些算法在提高图准确性上有一定的效果,但它们忽略了图结构质量这一重要指标,性能还有待进一步提升。

2 自动概念图生成模型C-IK2

2.1 K2算法

K2算法在给定一个数据集D的情况下,搜索具有最大后验概率网络结构的G,即求解最大的p(G|D)。K2算法运用启发式搜索方法,首先假设节点中缺少父节点,然后在每一步中逐步增加满足结构网络概率最大的父节点。当无法再提高网络结构概率时,K2算法停止增加父节点。因此,K2算法输入序列对减少计算复杂度有着至关重要的影响。这意味着,若节点xi在排序中优先于节点xj,则节点xj不能是节点xi的父节点。

2.2 LPG算法

基于K2算法输入序列特性,即如果节点xi在排序中优先于节点xj,则节点xj不能是节点xi的父节点,应用LPG[13]算法思想来构造节点有效序列。该算法利用QC和R两个数据集获得学生特征,根据学生的错误率进行聚类处理得到学生分簇G={G1,G2,…,Gi,…,Gk},对每个簇Gi矩阵计算其问题之间的一致性,符合一致性要求的簇进入下一步,计算Gi矩阵中问题之间的置信度。构造新的qc′,如式(2)所示。

(2)

(3)

其中,Rev (Cu,Cv)Qa→Qb表示由关联规则导出的问题Qa→Qb对应概念Cu和Cv的相关度,Confidence(Qa→Qb)是Qa→Qb的置信度。

接着利用此相关度生成概念图,最后利用拓扑排序来求得学习路径。相关实验证明生成概念图的合理性,而且生成的学习路径能有效区分学生。该算法生成的学习路径是一个线性序列,此线性序列能表示学生学习概念的顺序,即若概念Qa在Qb之前,则一定先学习概念Qa,这与K2算法的输入序列特性一致。

2.3 C-IK2模型

用LPG算法生成概念图和用K2算法生成概念图都存在缺陷,LPG算法生成的概念图,虽然考虑了概念之间的联系,但是概念之间的上下级关系却无法确定,而使用K2算法生成的概念图虽然考虑,变量之间的上下级关系,但是其输入是按照变量之间的递增序列,而不同学生行为有着不同的输入序列,它忽视了输入序列的合理性。

为了解决K2算法输入序列的合理性问题,本文改进LPG算法和K2算法,并将两个算法结合起来,提出了一种新自动概念图生成模型C-IK2,它同时具有LPG算法与K2算法的特点。

在C-IK2模型中,首先根据学生考试数据和概念与问题数据提取学生错误率信息;然后利用数据挖掘中的聚类技术将学生聚类成若干簇,将不同簇的学生进行理解水平的预处理;接着利用改进LPG算法求得概念间序列,将此序列作为K2算法的输入;最后使用改进K2算法生成具有层次结构的概念图,每个概念图反映了相应学生簇的学习表现。该算法的整体框架如图1所示。

图1 概念图生成模型C-IK2的框架示意

2.3.1 数据处理

在提取学生错误率之前,分析给定的两个矩阵,第一个矩阵表示试题和概念之间的关系,其中试题与概念之间的关系表示试题属于试卷中的哪个概念。当一个试题关联多个概念时,如果一个学生在问题上出现错误,我们无法仅凭这一错误判断他具体哪一个概念未掌握。因此,在该算法中一个试题只属于一个概念,但一个概念可以包含许多试题,将试题和概念之间的关系表示为QC,为了保证该数据集的正确性,QC由相关专家给出。对于上述参与试题(Q1,Q2,Q3,…,QNq)与概念(C1,C2,C3,…,CNc)间的关系,定义的问题概念矩阵如式(4)所示。

(4)

其中,qcij∈{0,1}表示第i个问题是否属于第j个概念,qcij=0表示第i个试题不属于第j个概念,qcij=1表示第i个试题属于第j个概念。

另一个矩阵是学生的测试记录,用SQ表示。该数据集表明学生(S1,S2,S3,…,SNs)对每个试题(Q1,Q2,Q3,…,QNq)的回答是否正确。该学生测试记录矩阵结果如式(5)所示。

(5)

其中,sqij表示第i个学生是否正确回答试题j,sqij∈{0,1},sqij=0表示第i个学生没有正确回答第j个试题,sqij=1表示第i个学生有正确回答第j个题。

下一步,使用聚类算法分析新的学生特征。聚类分析是一种无监督的机器学习方法,该方法可在非均匀大样本中构造具有均匀性质的簇,使簇内尽可能同质,各簇之间的差异尽可能大。因此根据学生特点将学生分成几个不同的簇,使同一簇的学生尽可能相似,即同一簇的学生在掌握概念方面尽可能相似。本文利用Birch聚类算法对学生进行分簇,再对不同的学生簇进行单独分析。学生簇表示为G={G1,G2,…,Gi,…,Gk},其中Gi表示第i簇,k表示簇数。其数据处理过程的正确性和有效性在Li等人[18]提出的论文中得到证实。

基于QC和G,将不同簇的学生正确回答试题程度转化为该簇学生对每个概念的掌握程度,表示为gx={gx1,gx2,…,gxi,…,gxk},其中k是小簇数目,gxi表示第i簇学生,第i个小簇对概念掌握程度的矩阵如式(6)所示。

11月中旬柑橘产量与降水量呈显著正相关，柑橘进入果实成熟采摘期，降水有利果实增重，干旱会使果实内的水分向叶片输出，单果重下降。但是，成熟期适度的干旱有利于提高果实品质和采收贮藏［12］。

(6)

其中,Nc是概念数目,sgxNiNj表示第i学生对概念j的掌握程度,sgxNiNj∈[0,1],表示学生回答试题的正确率。sgxNiNj值越大,第i簇学生对概念j的掌握就越好。第i簇学生回答试题的正确率可以转化为该簇学生对每个概念的掌握水平,表现为掌握与没掌握二种形式。如果sgxNiNj∈[0,0.6],则认为学生i在概念j上的掌握程度不符合要求;如果sgxNiNj∈[0.6,1],则认为学生i能较好地掌握概念j。在接下来的步骤中,分别对每簇进行上述处理。将GX转化为GX′={gx′1,gx′2,…,gx′i,…,gx′k},GX′表示学生是否掌握知识矩阵,其中n是小簇数目,gx′i表示第i簇学生是否掌握该知识,gx′i由式(7)表示。

(7)

2.3.2 实验方法

对数据处理后生成的GX′与QC进行分析,首先基于某个簇学生特征矩阵gxi′,计算问题Qa和Qb的计数器值,其Qa=[ga1,ga2,…gai,…,gaNc],Qb=[gb1,gb2,…gbi,…,gbNc]。计数器表示问题Qa和Qb之间的答案一致性,如式(8)所示。

只有当Count(Qa,Qb)>Nc×40%是真时,才转入下一步。

(8)

使用LPG算法分析学生掌握概念的关系图,挖掘概念之间潜在的联系。结合LPG算法生成关系图之前,要考虑两种情况: 情况一: 学生掌握了概念a且掌握概念b的情况;情况二: 学生没有掌握概念a且没有掌握概念b的情况。

基于学生概念掌握矩阵gxi′使用LPG算法进行挖掘,在进行LPG算法挖掘之前,先对gxi′进行分析,将其分为上述两种情况。接下来分别对这两种情况用LPG算法处理,过程如下: 第一构造概念1项集,表示学习者对该概念的掌握程度;第二构造概念2项集,即学习者同时掌握两个概念的学习程度,然后计算每组概念的支持度,设置支持度阈值。只有满足支持度阈值才能进行下一步,计算学生掌握概念Cx同时掌握概念Cy的置信度,和学生未掌握概念Cx也未掌握概念Cy的置信度。同样设置阈值来评估概念间关系的强弱,并最终得出概念关系图。为了避免概念之间的相关程度太小,使得关联规则不可信,再计算概念之间的关联规则设置支持度阈值,即支持度大于0.9的关联规则。再计算学生不能掌握概念a和不能掌握概念b的置信度。LPG算法在这之后还是用了问题概念数据集进行实验。为了使得算法更具有普遍性,能够获得更精确的概念图,对LPG算法进行改进。本文对问题概念数据集进行处理生成GX′,因此无需后续操作。将改进LPG算法得到的关系图作为生成概念图的中间件。在建立概念关系图的过程中,如果概念图表示掌握了x概念也掌握了y概念,那么概念图的箭头为Cx→Cy;如果概念图表示既没有掌握x概念也没有掌握y概念,那么概念图的箭头为Cy→Cx,以此生成k个概念关系图,表示RM={RM1,RM2,…,RMi,…RMk},其中RMi表示第i个概念关系图,k表示概念关系图的数量。每个概念关系图反映了相应的学生簇的学习表现。下面将对每个概念关系图进行分析。

当概念数量大时,概念之间的关联规则复杂,使用人力来分析概念非常耗时,因而使用K2算法来自动生成概念图是必要的。本文在使用K2算法之前需要将复杂的概念关系图自动转化为概念序列。拓扑排序算法是分析有向无环图[30]的常用算法,该算法可以将有向无环图转换为节点序列,由于任意两个概念之间要么具有确定的先后关系,要么没有关系,绝对不存在互相矛盾的关系,符合拓扑排序生成的节点序列的特性,因此使用拓扑排序来生成概念序列是合理的。

(9)

C-IK2模型的伪码如算法1所示,其中步骤1～5对数据集G进行预处理,步骤7～26生成概念关系图,步骤27～28将概念关系图转化为输入序列,步骤28利用输入序列和K2算法生成概念图CM。

算法1 C-IK2模型

3 实验与结果

实验的目标是对所提出的模型进行实证评估。首先借助ASIA网络,对Tabar等人[12]、Ko和Kim[21]、Ai[28]提出的三种基于节点排序的贝叶斯网络结构学习算法进行了性能评估。GOB-NILP算法[20]、贪婪爬山搜索算法[21]、贪婪最大最小爬山算法[22]、K2算法[23]和Behjati等人[31]提出的基于评分的算法进行比较。最后对所提出模型生成的概念图与K2算法生成的概念图做比较。实验从五个方面来对本文所提出的算法进行评价: 生成图结构的准确性、图结构质量、生成概念图的合理性、算法的时间复杂度以及数据变量序列的算法影响。其中生成图结构的准确性、图结构质量、生成概念图的合理性三个评价指标体现的自动生成的概念图的有效性。而算法的时间复杂度以及数据集变量序列算法的影响体现了C-IK2算法改进K2算法的有效性。

3.1 数据集和实验环境

为了测试C-IK2模型,实验使用了标准的性能度量。实验数据集使用著名ASIA基准网络, 该网络来自bnlearn R包[32]中包含的贝叶斯网络存储库的ASIA数据集,含有8个变量、8条边,并用公开教育数据集进行实验分析,此数据集包含6 866名学生在计算机文化基础课程中的大规模测验,有总计617 940条测试记录数据,涵盖90个问题、29个概念类型。

试题与概念之间的关系(QC)由相关领域的权威专家给出,保证了正确性和权威性。实验运行环境为Windows 10操作系统,编程语言为Python 3.6和Matlab。表1列出的是对实验中使用的数据库的描述。

表1 数据集统计

为了便于理解,测试记录数据和学生测试记录样例数据如表2和表3所见,0表示该学生未正确回答该问题,1表示该学生已正确回答该问题,横轴表示学生,纵轴表示问题。类似的在表3中,1表示问题属于该概念,0表示问题不属于该概念,横坐标代表问题,纵坐标代表概念.

表2 学生测试记录数据样例

表3 概念问题数据样例

续表

3.2 基线方法和评估标准

实验采用现有基于节点序列的重要相关方法作为基线方法。Tabar等人、Ko和Kim、Ai 中引入了新的节点序列算法,为了证明C-IK2模型解决贝叶斯网络结构学习问题的有效性,实验使用ASIA数据集。为与上述三种算法进行充分对比,以评估所提出的C-IK2模型的性能,本文使用以下评估指标: 真阳性(TP)表示正确识别的边的数量;错误阳性(FP)表示错误识别的边的数量;假否定(FN)指定错误识别的非链接边的数量。错误阳性和假否定描述了原始结构和推断结构之间的差异(Graph error)。准确率(P)、召回率(R)和F1值的计算如式(10)～式(12)所示。

同时,为了研究所提出的结构学习算法学习网络结构的准确性,实验研究了随数据集大小召回率、准确率和F1的变化情况。

对于教育数据集,实验考虑区分学生对概念理解程度,使用聚类算法,根据学生概念掌握程度特征进行分簇,分别使用K-means、Birch、高斯混合聚类算法进行分簇,使用Calinski Harabasz分数作为聚类算法的评估指标,其数学计算如式(13)所示。

(13)

其中,N为训练集样本,k为类别数,Bk为类别之间的协方差矩阵,Wk为类别内部数据的协方差矩阵。tr为矩阵的迹。类别内部数据的协方差越小越好,类别之间的协方差越大越好,当簇密度较小且分离较好时,Calinski Harabasz分数更高。

C-IK2自动概念图生成模型与5种基于评分的贝叶斯网络结构学习方法在标准数据集ASIA中进行比较。这五种方法分别是GOBNILP算法、贪婪爬山搜索算法、贪婪最大最小爬山算法、K2算法和Behjati等人提出的算法,实验使用BIC学习网络结构的质量和概念图的现实意义对三个方面对所提出的算法进行了评价,使用贝叶斯信息准则作为绩效衡量标准(Bayesian Information Criterion, BIC),BIC可用式(14)表示。

(14)

3.3 实验结果

使用准确率、召回率和F1在 ASIA 数据集中对不同的样本(1 000、2 000、5 000和10 000)来评估结构学习准确率。可以看出,C-IK2模型对于不同大小的样本产生了最接近原始ASIA网络的结构。在表4中,粗体值表示该算法部分最佳结果,C-IK2模型比其他三种算法在生成ASIA 网络上有最高的准确率、召回率和F1得分。而从稳定性来看,C-IK2方法无论是在样本较小的2 000数据,还是在样本较大的10 000数据中都能保持稳定且更接近原始ASIA网络结构。

表4 算法性能对比

实验对ASIA数据集取10 000个数据,算法的性能指标给出GOBNILP算法、贪婪爬山搜索算法,贪婪最大最小爬山算法、K2算法、Behjati等人提出的算法和C-IK2模型在ASIA网络的10个随机数据集上达到的得分的平均值。表5中粗体值表示该算法部分最佳结果。结果显示,C-IK2模型在ASIA数据集上网络结构得分较高。

表5 ASIA数据集BIC得分

将C-IK2模型应用到实际的教育测试记录数据集中,经过专家分析,将其聚类为5簇。分别使用K-means、Birch和高斯混合聚类算法进行分簇,其结果如表6所示。实验表明,使用Birch聚类算法的Calinski_Harabasz的分数较高,说明使用Birch聚类算法进行分簇,能有效地区分学生对概念的理解程度。

表6 聚类算法及评价结果

Birch聚类算法分簇结果如表7所示。对每簇数据进行分析,使用C-IK2模型与基于评分的贝叶斯网络结构学习方法进行了比较: GOBNILP算法、贪婪爬山搜索算法、贪婪最大最小爬山算法、K2算法。

表7 聚类分簇结果

实验为了与这四个算法进行比较,记录了每个算法找到的均值结构网络得分。总体上,C-IK2对K2 算法在基于教育测试记录上有提高,并且随着样本的增加,这种提高越明显,具体如图2所示。

图2 K2算法和C-IK2模型BIC精度对比

表8是C-IK2模型和基于评分的贝叶斯网络结构学习方法在教育测试记录数据中的BIC精度结果,其中黑色粗体表示每个数据在数据集所得到最佳结果。C-IK2模型在BIC精度方面总体上优于GOBNILP算法、贪婪爬山搜索算法、贪婪最大最小爬山算法和K2算法。其中,Bi concept map2数据集上贪婪爬山算法的精度最优,考虑其原因是在数据集较小时,贪婪爬山搜索算法的BIC 网络质量分数优于其他算法。

表8 概念图BIC得分

实验通过时间复杂度来对比K2算法和C-IK2算法,进行10次选取其时间的平均值。其中实验中所对比的时间复杂度是构建概念图过程的时间复杂度,不包含构建序列过程。如表9所示,C-IK2的时间复杂度比K2的时间复杂度少,说明C-IK2算法过程中生成的有效序列,能减少K2算法的搜索时间,提高K2算法的效率,高效生成概念图。

表9 时间复杂度比较

实验改变数据Bi_concept_map1变量和数据Bi_concept_map2变量顺序得到Bi_concept_map11、Bi_concept_map12、Bi_concept_map13、Bi_concept_map21、Bi_concept_map22和Bi_concept_map23,对比K2算法和C-IK2算法,结果如表10所示。从表10中可以看出,K2算法与C-IK2算法的BIC值都受数据集中变量位置的影响,但是C-IK2算法的BIC值比K2算法的BIC值高。

表10 改变变量位置的BIC比较

3.4 概念图分析

实验使用LPG算法、K2算法和C-IK2算法生成概念图,选取其中两个簇概念图进行分析。LPG算法生成簇1和簇3的概念图一致,如图3所示。概念图能清晰表示概念之间的相关关系,却无法判断从何处开始学习。此外,簇1与簇3生成的概念图相同,更进一步验证了。该算法只考虑了概念间关系,无法指导教师教学。图4、图5是利用K2算法生成的概念图,在由K2算法生成的概念图中,簇1和簇3以概念1作为根节点,这是由于生成概念图时只以递增作为输入序列,因此无法进行个性化教学。为改进上述缺点,实验采用C-IK2模型自动生成概念图。图6、图7是由C-IK2模型生成的概念图,从图中可以看出,由C-IK2生成的概念图,簇1和簇3分别以17和14作为根节点,这是由于该算法考虑了不同节点之间的关系,以此作为生成概念图的依据。同时,图6、图7概念图具有层次结构,能有效判断出概念学习的顺序。在实际学习中,不同学习群体的学习能力和理解具有差异,C-IK2模型能够针对不同学习群体的学习者绘制个性化概念图,指导教师开展个性化教育。

图3 LPG算法生成簇1和 簇3概念图

图4 K2算法生成簇1概念图

图5 K2算法生成簇3概念图

图6 C-IK2模型生成簇1概念图

图7 C-IK2模型生成簇3概念图

具体分析C-IK2生成概念图,以图6为例,教师在教导簇1的学生时可以首先学习概念17,接着教导概念12、9、20。这三个概念的教导可在同一节课中完成,也可分开教导,但是要注意必须学习完概念9,20才可以学习概念14,而概念8、20、21、22 在学习完概念20之后才可以学习。概念5、18、11则需要学完概念14和20以后才能学习。概念23不仅与概念22有直接关系,还与概念20有直接关系,因此在教学过程中,可以适当复习概念20的内容,教师再教导概念23以帮助学生构建知识点的联系,更好地理解概念。教师在教导完上述概念后,可教导概念1、10、26,接着教导概念13、6、19、25,最后教导概念29、27、24。由于7、15、16、28这四个概念与其他概念相关性并不大,可以选择任意时候进行教学。此外,教师在教学过程中可以按照纵向来教学,如某一节课教导概念17、20、8,可以让学生了解概念之间的关系;也可以按照横向教学,如教导12、7、15、16、28,让学生掌握几个知识点。由此可见,使用C-IK2概念图进行教学指导更为灵活。

4 总结和展望

为了生成具有层次结构特点能反映学生学习能力并能指导教师教学的概念图,本文提出了C-IK2模型。该模型具有以下特点: ①适应性好,对不同学生簇有不同概念图; ②通用性高,算法不仅在教育方面的数据集上有良好的结果,在ASIA公开数据集上也有较好的结果。

尽管C-IK2模型表现良好,但也有一些局限性。C-IK2模型只能对二分类数据有效,并且相应关系只能是一个问题针对一个概念的关系,然而现实中,一个问题可能包含多个对应概念,因此该模型在灵活性上有所欠缺。此外,该算法受数据集变量位置的影响,如何有效构建输入数据集,以提高C-IK2算法的图结构准确度,是亟待解决的问题。