基于聚类和案例推理的个性化教学序列生成

朱忠旭，刘竞杰

(安徽工贸职业技术学院 计算机技术系，安徽 淮南232007)

智能教学系统(Intelligent Tutoring System，ITS)是人工智能技术在教学领域的应用，目标是代替教师对不同知识需求和个性特征的学生实施个别化教学，为学习者生成个性化的教学序列是实现智能教学的关键问题之一.当前，大多数ITS生成教学序列的方式是通过分析教学内容包含的知识点和知识点之间的关系建立知识模型，再结合学习者的特征模型抽取知识序列的产生规则来生成教学序列的［1］.也有学者提出采用神经网络［2］、强化学习［3］等方法来生成学习序列.

利用由模型提取的知识序列生成规则来完成教学序列生成的方法，面临着学生的个性数据难于测定、规则难以获取与描述、系统难以自我完善等瓶颈.然而，案例推理(Case Based Reasoning，CBR)技术规避了规则获取这一困难环节，而且基于CBR的系统随着存储案例数量的逐步增加，系统解决问题的能力也不断增长.因此，CBR技术在智能教学系统开发中的应用逐渐受到了人们的重视.Hidayah等［4］用CBR方法来创建学生模型，以获取学生对当前课题内容的掌握状态，从而对学生进行个性化的教学指导.Kharrat等［5］将CBR技术用于智能教学系统的课程安排.González等［6］提出采用CBR进行智能教学系统开发的方法学，开发了基于MAS和CBR进行ITS设计的总体框架.CBR作为一种依据以往经验解决问题的方法，为ITS系统的开发提供了新的途径.

1 基于CBR生成知识序列的实现

1.1 知识模型与学生案例的定义

定义1知识点是与特定主题相关的基本知识容量单位，知识点标志和教学内容之间具有一对一的对应关系.知识点表示为KP=(id，name，content，dif，pre，post，mast).id为知识点的编号，name为知识点的名称，content为知识点对应的内容，dif为知识点的难度水平，pre为知识点的前提知识点，post为知识点的后继知识点.系统中，覆盖相同领域内容的知识点的编号和名称是唯一的，不同课程包含相同的知识点时，对知识点要求的掌握水平可能不同，用mast表示.

学生案例的内容包括问题特征描述、问题解决方法和对案例解答质量的评价3个部分，定义2规范了用于生成教学序列的案例的结构.

定义2(学生案例)知识序列求解案例库中的每条案例定义为Ck=(S_Bk，S_Tupsk(C，G)，WPk，L_Sk，C_Evak)，其中S_Bk=(Name，Department，Major，Class)，表示学生的姓名、所在系、专业、班级等基本信息;S_Tupsk(C，G)=Set((C，G))是一个课程和成绩的二元组集合，描述学生在校期间学习的主要专业课程及成绩;WPk是指学生所选择的实习岗位;L_Sk=Queue(KP)，是一个由多个知识点构成的队列结构，保存了学生在实习期间要学习的知识，知识点在队列中的先后顺序表示学习知识点的时间先后;C_Evak是学生学习任务完成后对知识序列质量的评价.

1.2 学生案例相似度的计算

采用CBR方法进行问题求解时，首先要能够快速地从案例库中找到与当前求解问题最相似的案例，案例之间相似度的定义直接关系到检索结果的可用性.

案例的相似度包括总体相似度与局部相似度.影响学习序列生成的主要因素有学生的知识领域、知识水平和选择的工作岗位.因此，计算案例之间的相似度时需要从3个方面考虑:学生的专业知识类别KC、知识水平KL、选择的岗位P.学生案例相似度的计算公式定义为

式中，wkc，wkl，wp分别是专业知识类别、知识水平和岗位相似度在案例相似度计算中所占的比例，wkc+wkl+wp=1，sim(KC)，sim(KL)和sim(P)分别为知识类别、知识水平和岗位的相似度.

1.2.1 学生专业知识类别相似度的计算

定义3专业知识类别树为对学生的专业知识类别逐步细分所得到的树形结构，记为T(KC).T(KC)的根结点代表总类别，其下层结点表示各个专业大类，每个专业大类又细分为若干个类别，每个类别所属的各个专业构成其子类别，各专业所设置的专业方向为叶结点，由此形成一个层次式的专业知识类别划分结构.

学生知识类别相似程度取决于学生所学专业(或专业方向)在知识类别树T(KC)中的共同父类别的数量［7］，相似度计算方法如下式:

式中，kci和kcj分别为学生i与学生j所学习的专业(方向)，用函数common-super(kci，kcj)计算kci和kcj的公共的父结点，deep(T(KC))为类别树的深度.

1.2.2 学生知识水平相似度的计算

学生知识水平相似度的计算公式如下:

1.2.3 工作岗位相似度的计算

学生工作岗位所需要的知识集合K-Set(post)定义为一个二元组(KPi，Mai)的集合，KPi为需要的知识点，Mai为工作岗位所需要的对此知识点的掌握水平.根据每个知识点对工作岗位的重要性的不同，规定了相应的掌握级别如了解、理解、掌握和精通等，即K-Set(post)=Set((KPi，Mai)).

不同工作岗位知识需要的差别从所需知识点的不同及对每个知识点要求掌握程度的不同两个方面比较.设工作岗位Posti与Postj需要掌握的知识点数量分别是ni和nj，它们都需要的知识点集合为CKS(Posti，Postj)，则岗位相似度的计算公式为

计算岗位相似度时，先求出岗位Posti和Postj需要的知识点集合的交集CKS，对CKS中的每个知识点，如果岗位Posti与Postj对其要求的掌握水平相同，则将其权重设为1，否则将其权重设为岗位Posti与Postj要求的掌握水平的最小值.两岗位之间的距离定义为

1.3 基于岗位聚类对案例分类

定义5(岗位聚类)对就业岗位根据其所需要的专业知识进行分类，同一个聚类中的工作岗位要求学生具有的知识类别、知识水平的相似程度较高(即距离小于规定的阈值).

在CBR中，案例库的案例数量随着问题求解过程的进行不断增加，所以必须根据案例库中案例的变化及时调整案例组织.文献［8］通过不断使用聚类算法对案例库中的案例进行聚类，控制案例聚类中案例的数量来加快案例检索的速度.由于聚类算法的时间复杂度高、系统生命周期中算法需重复运行等因素，使得用于案例聚类的时间过多，不利于案例检索速度的提高.为了减少用于聚类运算的时间，对经典2-中心点算法进行了改进，形成惰性2-中心点算法.所谓惰性，是指通过设定特殊的算法启动和结束条件来尽可能地减少聚类算法在软件运行期间的执行次数以降低聚类所需时间，具体做法如下:①不直接对案例进行聚类，而是对案例中的某个关键属性进行聚类;②算法的激活由与关键属性聚类中的属性相关的案例的数量决定，仅当案例数量超出规定的阈值时才运行聚类算法;③算法执行时，随机选择两个对象作为聚类中心，与中心距离不超过规定阈值的对象为一族，超过阈值的对象放入离外集，将要分类的对象分为两个主要聚类.

惰性2-中心点算法描述如下:

(1)判断要进行聚类的对象集S中的对象数量是否超出设定的最大值，若超出则转至第(2)步，否则转至第(6)步;

(2)随机选择两个对象o1，o2作为聚类中心;

(3)计算各对象到o1，o2的距离，若某个对象到o1，o2的距离均大于设定的阈值，则将其放入集合S1;

(4)将S1以外的对象根据其与o1，o2的距离分为两个聚类C1，C2;

(5)返回所得的分类C1，C2，S1及C1，C2的中心点o1，o2，转至第(1)步;

(6)结束.

使用惰性2-中心点算法对学生选择的实习岗位进行聚类运算.由于现实中岗位选择的不均匀性，随着新案例的不断加入，会导致各个岗位聚类的不均匀生长，即选择某些岗位聚类所包含的学生数量过多，而有的聚类包含的案例数量过少.为了解决这一问题，规定了一个聚类包含个体数量的最大值，当超过该值时，对该聚类应用上述算法时进行拆分，从而保证每个聚类涉及的案例数目都不会过大.每当对岗位聚类进行一次拆分之后，需要重新生成案例的索引，动态索引创建算法如下:

(1)统计每个岗位聚类中的岗位所关联的案例数量m;

(2)对m＞阈值M的岗位聚类，判断其含有的岗位数n，若n≥2，则应用惰性2-中心点算法对其进行聚类，将聚类中心点作为属性聚类的代表对象，聚类产生的孤点加入到孤点集S中;若n＜2，表示选择此岗位的学生案例过多，需要对其进行优化，保留学生评价高的案例，去除学生评价较低的案例;

(3)判断孤点集S中的岗位所关联的案例数量是否超出阈值，若超出，则转至第(2)步;

(4)根据聚类结果修改索引表.

1.4 基于CBR生成学习序列的过程

由于几乎不存在与目标案例完全相同的源案例，所以为了使源案例的解决方案能够成功地应用于目标案例，需要对源案例的答案进行适当调整.为了提高系统的自治性、实现改编过程的自动化，设计了两种生成目标方案的策略:

(1)当案例库中不存在与目标案例相似的源案例时，由领域模型获得实习岗位所需要的知识点，将其作为学生要学习的知识序列.将学生学习知识序列前已掌握的知识点从知识序列中删除，得到的知识序列与学生数据一起作为案例存入案例库.

(2)当案例库中存在与目标案例相似的源案例时，如果目标案例的岗位属性与源案例不同，则根据目标案例的岗位属性对相似的源案例的教学序列进行调整，将目标案例岗位需要而源案例岗位不需要的知识点加入教学序列.生成教学序列的详细过程如图1所示.

图1 教学序列的生成过程Fig.1 Teaching sequence generating process

2 原型系统应用分析

为了验证上述CBR技术生成个性化学习序列的有效性，基于JADE平台开发了学生顶岗实习阶段智能化教学的原型系统，采用Oracle 11g数据库进行案例存储，用户界面使用Java Swing设计.规定聚类时岗位距离阈值为0.9，每个岗位聚类涉及的案例最大数量为100个，通过学院2013级的1 000名顶岗实习学生的数据对原型系统进行检验，结果见图2至图4.

图2 教学序列生成时间与学生数量的关系Fig.2 Relation between teaching sequence generatingtime and the number of students

图3 岗位和岗位聚类数量与学生数量的关系Fig.3 Relation between post，post categoryand the number of students

由图2可看出，知识序列生成所需的时间随着学生数量的增加而增长.起初，案例库中源案例的数量较少，案例检索所需要的时间t1较短.另外，由案例检索算法可知，在检索不到与目标案例相匹配的源案例时，学习序列的生成完全由岗位知识需要进行规则推理决定.当案例库中案例数量增加时，案例检中率越来越高，匹配成功的知识序列生成所需时间即为案例检索所需时间.

随着使用系统学生数量的增加，学生选择实习岗位的数量和聚类算法对实习岗位进行聚类的结果的变化情况见图3，可以看出岗位聚类的数量比同期的岗位数量少得多.

系统初始运行时，学习序列较长，经过一段时间的运行，当案例库中的案例数增加到一定程度时，绝大多数目标案例求解都可以从案例库中检索到相似案例，此时平均序列长度较初始时有较大减少并逐步趋于稳定，如图4所示.

图4 教学序列长度与学生数量的关系Fig.4 Relation between the length of teaching sequence and the number of students

3 结论

通过CBR技术将以往为学生生成学习序列的经验应用到当前的教学实例中，有效规避了教学序列生成规则的提取这一难点，降低了系统开发的难度.利用惰性2-中心点算法对学生实习岗位进行聚类，缩小了案例检索的范围并提高了系统效率.结合领域模型，实现了对源案例解答的自动改编及案例检索失败时教学序列的自动生成和案例库的自动更新等操作.

［1］蒋艳荣，韩坚华，吴伟民.一种自适应的个性化学习序列生成研究［J］.计算机科学，2013，40(8):204-209.

［2］Hassina，Sari T，SellamiM.A neural network for generating adaptive lessons［J］.Journal of Computer Science，2005(2):232-243.

［3］Iglesias A，Martinez P，Fernandez F.An experience applying reinforcement learning in a web-based adaptive and intelligent educational system［J］.Informatics in Education，2003(2):223-240.

［4］Hidayah I，Syahrina A，Permanasari A E.Studentmodeling using case-based reasoning in conventional learning system［J］.International Journal of Computer Science and Information Security，2012(10):1-5.

［5］KharratM，ReyhaniN，Badie K.A case-based reasoning approach to intelligent tutoring system by considering learner stylemodel［C］∥Systems and Information Engineering Design Symposium，VA:Charlottesville，2003:41-46.

［6］González C，Burguillo JC，Llamas M.Designing intelligent tutoring systems:a personalization strategy using case-based reasoning and multi-agent systems［J］.Advances in Distributed Computing and Artificial Intelligence Journal，2013(4):41-53.

［7］谢红薇，李建伟.基于本体的案例推理模型研究［J］.计算机应用研究，2009，26(4):1422-1424.

［8］乔丽，姜慧霖.一种k-means聚类的案例检索算法［J］.计算机工程与应用，2011，47(4):185-187.