基于聚类的协作学习分组方法

祁天龙,任美睿,2,赵建宇,郭龙江,2

(1.陕西师范大学 计算机科学学院,陕西 西安 710062;2.陕西师范大学 现代教学技术教育部重点实验室,陕西 西安 710062)

0 引 言

近年来,在线学习平台取得了长足的发展,据统计,中国目前有12 500门左右的在线课程,学习人数已超过2亿人次[1]。然而,在线学习平台的课程完成率仅有不到5%[2],限制了平台的发展。协作学习是以小组为单位的学习方式,对同一个主题感兴趣的学习者组成一个小组,组员间可以一起探讨主题,相互帮助,共同完成学习目标[3]。协作学习的过程中,不仅使学习者的能力得以提升,还促进了组员之间的交流,从而有效地降低辍学率。

构建协作学习小组是协作学习中的关键问题,已有不少研究者提出了多种不同的分组方法。Andrejczuk等[4]分组时考虑了学习者的性别、个性、能力和小组规模。Nand等[5]以形成技能均衡的小组为目的,依据学习者的技能偏好和水平,使用萤火虫算法进行分组。

Flores-Parra等[6]考虑了学习者在小组中可能的角色分工,使用社交网络的方法分组。桑治平等[7]依据学习者的兴趣、学习动机、知识水平等构建小组。潘芳等[8]考虑了在线学习者的性格、学习目标、风格、动机、认知水平等因素,使用了Multi-Agent分组。李浩君等[9]结合混合遗传算法提出了在线学习环境中基于任务驱动的协作学习小组构建方法。

聚类算法由于其复杂度低,可解释性强,近年来出现了基于聚类的协作学习分组方法。Akbar等[10]考虑了小组规模和主题意愿,结合HK-Means算法(一种基于K-Means的改进算法)提出了改善学习者团队的形成方法(Improving Formation of Student Teams,IFST),取得了较好的实验效果。

曹天生等[11]考虑了学习者的信息素养、学习风格、认知能力和知识基础等因素,使用聚类算法分组。Sanz-Martínez等[12]通过页面浏览量、作业提交量等活动量化学习者的参与度,再依据参与度使用K-Means聚类算法分组。罗凌等[13]考虑了学习者的学习风格、知识水平和学习目标等因素,使用模糊C均值算法分组。陈甜甜等[14]考虑了在线学习者的人口因素(如性别、国籍)、课程参与度、行为信息,分组时也使用了模糊C均值算法。

然而,现有的研究中还没有同时兼顾学习者的主题意愿、学习时间规律、小组规模这三个重要因素的协作学习分组方法。首先,相同的主题有助于减少组内分歧,且给予学习者对主题的自由选择权可以提高其参与度和积极性[15]。其次,在线学习平台中的课程大多没有固定的时间表,学习者在任意时刻都有可能进入平台,将学习时间规律相同的学习者分配到同一小组中有助于提高组员间的沟通效率。最后,小组规模过大时会提高组员间的沟通成本[16],进而降低学习效率,小组规模过小会使单个学习者承担更多的工作,不利于学习目标的完成。综上所述,对于协作学习分组,主题意愿、学习时间规律、小组规模是三个必要的考虑因素。

为了填补上述分组研究中的空白,该文综合考虑了学习者的主题意愿、学习时间规律、小组规模三个因素,提出了基于聚类的协作学习分组方法。

1 基于聚类的协作学习分组方法

1.1 相关符号与定义

定义1(满意度)：若学习者所在的小组成员数在上下限之间(包括上下限),且该小组被分配的主题是当前学习者的第一个意愿,则认为当前学习者是满意的。满意的学习者数占学习者总数的比例称为满意度。

定义2(时间重合度)：时间重合度衡量了小组中学习者的学习时间规律的相似程度。时间重合度的计算方式如下：

定义3(协作学习分组)：给定主题集合P,学习者集合S,学习者的主题意愿向量{wi|1≤i≤N},学习者的学习时间规律{ti|1≤i≤N},以及小组人数上下限ceil和floor。最终,将学习者集合S划分为互不相交、组内学习者数在给定上下限之间的协作学习小组{Gj|1≤j≤M}。使得满意度和时间重合度最大化。

1.2 协作学习分组方法

基于聚类的协作学习分组方法(Cooperative Learning Grouping Method Based on Clustering,CLGC)大致包含以下四个步骤：第一步,预分组;第二步,处理预分组集合;第三步;使用聚类算法分组;第四步,处理聚类后的分组结果集合。分组过程如图1所示,图中floor=3,ceil=5。

图1 基于聚类的协作学习分组方法示意图

1.2.1 预分组

1.2.2 处理预分组集合

依次遍历预分组集合{Bl|1≤l≤L},若预分组集合中学习者数大于等于floor,则进入下一个步骤,使用聚类算法进行分组(详见1.2.3节)。若当前预分组集合中学习者数小于小组成员数下限floor,则依次将该预分组集合中的学习者重新分配到当前学习者第二意愿对应的预分组集合中,如图1步骤②中将s5从B1分配到B5,如果第二意愿对应的预分组集合中学习者数仍小于floor,则将其分配到该学习者第三意愿对应的预分组集合,依此类推,直到将该学习者分配到某个预分组集合中为止。

1.2.3 使用聚类算法分组

依次遍历经过处理后的预分组集合{Bl|1≤l≤L},若预分组集合中的学习者数大于小组成员数上限ceil,则依据学习者的学习时间向量,使用聚类算法将预分组集合中的学习者划分为2个子集,若子集中的学习者数仍大于ceil,则继续将子集划分为2个更小的子集,重复这个过程,直到子集中的学习者数小于等于ceil,最后,将满足条件的子集加入到分组结果集合。如图2所示,若预分组集合非空且其中的学习者数小于等于ceil,则直接将该预分组集合加入到分组结果集合。

图2 基于聚类的协作学习分组方法流程

上述过程中可使用的聚类算法大致分为三种：基于划分的聚类算法,如K-Means[17];层次聚类算法,如Agglomerative Clustering[18](简称为AC算法)、BIRCH[19];以及近邻传播算法Affinity Propagation[20](简称为AP算法)。需要注意的是,使用基于划分的聚类算法和层次聚类算法时,指定聚类中心数为2,而AP算法不需要指定聚类中心数,可以对所有划分后的子集递归地调用自身再次聚类,所以也可用于分组。其他的聚类算法,如基于密度的聚类算法需要指定聚类半径,针对不同的学习者集合该聚类半径也不相同,因此难以确定合适的聚类半径,而基于网格的聚类和谱聚类算法由于其计算复杂度高,不适用于学习者规模较大的在线学习平台。

1.2.4 处理聚类结果集合

遍历聚类后分组结果集合中的所有子集,若子集中的学习者数小于floor,则将该子集中的学习者依次分配到和当前学习者在同一个预分组集合中的其他子集,目标子集须满足：floor≤目标子集中的学习者数

遍历结果集合中的所有子集后,若待分配集合非空,则依次遍历待分配集合中的学习者,先找到该学习者的第二意愿对应的预分组集合中的结果集合,再从这些结果集合中找到满足条件的目标子集,将当前学习者分配到该目标子集中,如图1步骤④中将s29分配到B3;若第二意愿对应的预分组集合中找不到满足条件的目标子集,则依次在后续意愿对应的预分组集合中寻找,直到将学习者分配到某一个目标子集中。

最后,遍历所有经过处理后的结果集合,若当前结果集合满足：floor≤结果集合中的学习者数≤ceil,则将其作为一个协作学习小组,小组所在的预分组集合对应的主题即为指派给该小组的主题,如图1步骤④中指派给小组G1的主题是p2。

2 实验及结果分析

2.1 数据集和预处理

学习者的主题意愿是由计算机模拟生成的,学习时间规律来源于公开的真实数据集,由在线学习平台XuetangX收集[2]。

2.1.1 主题意愿

2.1.2 学习时间规律

XuetangX平台收集的数据集中包含了从2015年8月至2017年8月的1 213门课程中共378 237名学习者的活动记录[2],活动发生的时间精确到秒。学习者的时间数据需要将其预处理为标准化的0-1向量用于后续的聚类。

时间数据的预处理过程如下：首先,将活动记录文件分别按照学习者的学号和课程分割,若某个学习者参与了多门课程,那么将对应多个分割后的文件。然后,随机选取一门课程,并统计该课程中的学习者在平台的累计学习时长,为了保证有充足的数据量化学习时间规律,仅保留了累计学习时长超过20小时的学习者。最后,遍历该门课程中被保留的学习者的记录,将其记录编码为0-1向量,具体地,若si的活动发生在ti的第q个时间段,则tiq=1,否则tiq=0。

2.2 基于聚类的协作学习分组方法有效性

为了验证提出的协作学习分组方法的有效性,将其与随机分组方法(Random Grouping Method,RGM)以及Akbar等[10]提出的IFST分组算法进行对比。

随机选取了课程“TsinghuaX_30640014X”中自2015.10.13-0：0：0至2015.10.19-23：59：59期间有记录的1 754名学习者,平均每个学习者每天的学习时长是138分钟。将他们在这7天内的活动记录预处理为0-1向量,将其作为学习者的学习时间规律。编码时,将Q设置为56,即一周被均分为56个时间段,每个时间段的长度为3小时。主题数L设置为8,floor设置为3,ceil设置为5。

CLGC在分组时可使用的聚类算法有多个,这里仅选择其中的三个聚类算法。将基于K-Means算法的协作学习分组方法记作CLGC(KM),将基于BIRCH算法的分组方法记作CLGC(BC),将基于AP算法的分组方法记作CLGC(AP)。上述三种分组方法和IFST以及随机分组方法的实验结果见表1,表中展示的结果是重复10次实验后的平均值。

表1 五种分组方法的实验结果

从表1可以看出,相对于IFST和RGM,CLGC在满意度和时间重合度上都有更好的表现。其中,基于BIRCH算法的CLGC表现最好,时间重合度约是IFST和RGM的3倍,相当于平均每个学习者每天可参与协作学习的时长为60分钟,大约占每天学习时长的一半。在运行时长方面,IFST的开销最大,CLGC次之,RGM的运行时长最短。综合考虑满意度、时间重合度和运行时长,该文提出的CLGC优于IFST和RGM,验证了其有效性。

2.3 基于聚类的协作学习分组应用

将2.2节中的1 754名学习者作为实验对象,Q设置为56,L设置为8,floor设置为3,ceil设置为5。采用与2.2节相同的方式预处理后,使用CLGC(BC)将学习者划分为361个协作学习小组。其中,组员数为3的小组有23个,组员数为4的小组有5个,组员数为5的小组有333个。指派给各个小组的主题都是组员的前三个意愿之一,较好地满足了学习者的自由选择权。组员平均每天可参与协作学习的时长是64分钟,大约占平均每天总学习时长的一半,保证了学习者有充足的时间协作完成学习目标。

图3显示了其中100个小组可参与协作学习的时长,图中虚线表示平均值。从图中可以看出,不同的小组可用于协作学习的时长差异很大,这主要是因为内学习者在选定的这段时间内活跃程度各不相同,该文提出的分组算法倾向于将活跃程度高的学习者划分到同一个小组中,因此这些小组可用于协作学习的时长普遍高于其他小组。

图3 部分小组的可参与协作学习时长

3 结束语

提出了一种基于多种聚类算法的协作学习分组方法,该方法综合考虑了学习者的选题意愿、学习时间规律和小组规模,形成的小组有充分的协作学习时间,指派给小组的主题能够很好地满足学习者的意愿,且各个小组之间成员数均衡。以上三点都为提高协作学习小组的沟通效率提供了保证,不仅有助于学习目标的完成,还可以有效地降低辍学率。