教育数据挖掘简称EDM,是指通过应用数据挖掘技术分析教育过程中各种类型的数据,从而解决教育研究中遇到的问题[1]。由于互联网的普及,创造了一种新教育情境,称为电子学习或基于网络的教育,其中不断产生大量关于教学互动的信息[2],这些教学互动信息提供了教育数据的金矿[3]。EDM试图使用这些数据存储库以更好地了解学习者及其学习效果,并通过相关教学互动数据发现新知识,以帮助验证评估教育系统,改善教学质量。
聚类算法是数据挖掘技术中的一个重要方法,在挖掘任务面临领域知识不多或不够完整时,可采用聚类分析技术将无标识的数据自动分为不同类别,同时可不受前人经验知识的干扰与约束,进而获得在数据集中隐藏的有价值的信息。本文主要将代码仓库中学习者的提交与修改行为作为学习者的主要行为特征进行聚类,通过对聚类结果的分析,分析同一聚类中学习者代码提交与修改行为特征,找出体现学习者学习情况的重要因素,从而对学习者学习情况进行更精准地评判,为高校的计算机专业实践教学提供有力支持。
EDM的目标主要是将来自教育系统的原始数据转换为有用信息,这些信息可能会对教育研究与实践产生重大影响[4]。因此,其过程与普通的数据挖掘过程一样,主要包括数据预处理、数据挖掘以及结果评估与分析[5]。同时,其数据来源于教学环境,分析的结果信息也将用于教学环境。教育数据挖掘具体流程如1所示。
从图1可清楚看到数据、预处理、数据挖掘、评估与分析、知识以及教学环境5部分[6]。数据是教育数据挖掘的基础,作为主要研究内容,其主要是从教学环境中获取的,且形式多样化,涉及学科非常广,语义也十分复杂[7]。传统教学方式中的数据主要来自于手写的文本和调查问卷等,在互联网普及后,教学活动数据主要来自于教学管理系统的结构化关系数据库,或在线学习系统的半结构化日志文件,以及可提供文本、音频等非结构化数据的贴吧、知乎APP和哔哩哔哩等学习网站。经过数据挖掘、分析后的结果数据称为知识,主要包括原理类知识、实践类知识和优化类知识,其根据不同用途进行区分,但最终目的都是为了改善教学环境。
教育数据挖掘方法主要分为以下4类:
(2)聚类。该方法主要利用数据之间的相似性对数据进行归类,从而可发现学生抄袭行为或归类相同的知识点。与分类最大的不同是,聚类是无监督的,用于划分未知类别,而分类是有监督的,用于划分已知或已规定的类别。聚类算法主要包括层次聚类算法[13]、K均值聚类算法[14]、近邻聚类[15]等。
(4)关联规则挖掘。该方法主要用于找到数据对象之间的关系或关联规则,例如发现抄袭作业的学生与错误作业及课程之间的关系。
本节介绍两个代码仓库之间的相似性计算方法,该方法主要针对代码仓库中不同仓库提交内容的相似度匹配问题。此问题产生的原因是由于代码仓库中不同学习者的仓库提交次数不同,本文提出的相似性计算方法通过匈牙利算法进行提交内容的最大匹配,从而提高仓库间相似度计算的准确率。该方法计算过程如图2所示。
两个代码仓库相似性计算方法是在获取完整的代码仓库提交的修改信息后,首先对代码仓库中每次提交的修改内容使用文本分词器进行分词;然后使用文本相似度计算器计算两个仓库中每两个提交的修改内容之间的相似度,该计算器主要包括两部分,一部分生成代码仓库中提交的修改内容分词后的词频向量,另一部分计算两个词频向量的余弦相似度,余弦相似度越大表示越相似;接下来使用带权值的KM算法进行相似度最大匹配,将两个仓库的每次提交当作一个点,余弦相似度作为两个点之间相连边的权重,通过匈牙利算法得到两个仓库相似度最大的提交节点对;最后进行代码仓库的相似度计算,通过匈牙利匹配算法得到匹配节点对的余弦相似度之和,再除以两个代码仓库中所有提交次数之和,得到两个代码仓库之间的相似度。
设代码仓库M与代码仓库N是需要计算相似度的两个代码仓库,M仓库有k次提交,N仓库有t次提交,SMN表示两个仓库之间的相似度,则两个代码仓库之间的相似度为:
其中,mi、ni表示匈牙利算法匹配的两个代码仓库的对应提交,Sim(mi,ni)表示根据匈牙利算法匹配的M仓库一次提交与N仓库一次提交的余弦相似度。
聚类是一种无监督的分类,其不使用任何经验和知识。代码仓库聚类的相关形式描述如下:
其中,E表示所有代码仓库集合,xi表示所有代码仓库中的第i个仓库。
其中,类别Ft为聚类结果。
通过使用代码仓库相似性计算方法,可得到表示代码仓库之间相似性的相似矩阵。聚类算法的输入是样本点,在使用聚类算法之前,需要先将相似性矩阵转化成坐标点作为聚类输入的样本点,因此需要采取多维缩放的方法。多维缩放有多种类型,如经典多维缩放、公制多维缩放、非度量多维缩放、广义多维缩放等。本文主要采用经典多维缩放方法,又称为PCoA分析。
聚类算法可分为层次化聚类算法、划分式聚类算法、基于密度与网格的聚类算法及其他聚类算法。根据代码仓库的数据集特性,本文主要采用层次化聚类算法中的层次聚类算法,划分式聚类算法中的K均值聚类算法以及近邻聚类算法共3种聚类算法。假定样本集为n个样本。
(1)层次聚类算法流程。层次聚类算法使用数据的关联规则,通过一种层次的架构方法,反复将数据类别进行分裂或聚合,从而形成一个层次序列的聚类类别。其流程是首先进行初始化,将每个代码仓库均作为一个类,总共形成n个类别,即F1,F2,…Fn;然后寻找最相似的两个类,即从所有代码仓库类中找到相似度最大的两个类Fi和Fj;之后将Fi与Fj合并成一个新类Fij,同时将现有类别数量减1;最后进行判断与循环,如果所有样本都是一个类别,则停止算法循环,否则返回第二步进行循环寻找与合并。
(2)K均值聚类算法流程。K均值聚类算法的核心是找到K个聚类中心F1,F2,…Fk,这K个聚类中心满足每个数据点都与其最近聚类中心Fi的平方和最小,即偏差之和最小。其流程是首先进行初始化,随机选择K个代码仓库作为初始类的中心,即F1,F2,…Fk;然后进行分配,对于每一个代码仓库样本xi,找到与其相似性最小的聚类中心Fi,同时将其分配到Fi所属的聚类类别;接下来进行修正,将聚类中心Fi移动到聚类类别中心位置;之后进行偏差计算,计算每个数据点与其最近聚类中心Fi的平方和;最后进行判断与循环,若偏差值收敛即足够小,则返回K个聚类中心F1,F2,…Fk,同时终止算法,否则重新进行第二步的分配步骤。
(3)近邻聚类算法流程。近邻聚类算法同样是一种基于距离阈值的聚类算法。其流程是首先进行初始化,任取一个代码仓库Xi作为第一个聚类中心的初始值,例如取第一个代码仓库X1作为第一个聚类中心,即X1=F1;然后进行首次分配,计算代码仓库样本X2与第一个聚类中心F1的相似度D21,如果相似度D21>阈值T,则定义一个新聚类,其以代码仓库样本X2为中心,即F2=X2,否则将代码仓库样本X2分配到第一个以第一聚类中心F1为中心的聚类中;最后进行循环分配,计算代码仓库样本Xi与第一个聚类中心F1的相似度Di1,若相似度Di1<阈值T,则将代码仓库样本Xi分配到第一个以第一聚类中心F1为中心的聚类中,否则继续计算代码仓库样本Xi与第二个聚类中心F2的相似度。直到将代码仓库样本分配到一个聚类中,或与所有聚类中心的相似度都计算完成(若所有聚类中心的相似度均大于阈值T,则定义一个新的聚类中心),遍历完全部样本则终止算法。
本文主要研究以下两个问题:
RQ1:层次聚类算法、K均值聚类算法及近邻聚类算法在代码仓库中的应用效果如何?
RQ2:聚类结果对分析学习者行为有何帮助?该问题主要研究同一聚类中学习者行为表现的相关程度。
本文获得的代码仓库数据集是高校教师在程序设计课程时收集的,因此是客观、真实的。实验数据集分别来源于5个班级共136名学习者的代码仓库,所获取的原始数据集存放在136个Excel表格和1 893个文本文件中。其中,Excel表格存放的是学习者代码仓库中Commit提交行为的信息,文本文件存放的是学习者代码仓库中每两次提交过程的Diff增量文本信息。Excel表格与文本文件中部分初始数据如图3、图4所示。
本节介绍采用基于代码仓库相似性的聚类算法对学习者修改提交行为特征研究分析的实验过程。该算法总体流程如图5所示。
如图5所示,该实验过程总共分为3个步骤:
步骤1:获取代码仓库信息。主要获取代码仓库中学习者提交的信息和修改内容信息,通过调用JGit的Java开发包中相关接口,得到代码仓库中的学习者相关信息(Diff增量文本信息)。
步骤2:获取所有代码仓库的相似度。主要通过代码仓库相似度计算方法得到两个代码仓库的相似度,之后利用选择排序思想遍历所有仓库,得到所有代码仓库的相似度。
步骤3:获得聚类后的代码仓库列表,通过聚类算法实现代码仓库的聚类。
本实验数据集是136个学生提交作业的代码仓库。采用层次聚类算法的聚类结果如图6所示(彩图扫OSID码可见,下同),此图主要是根据对主坐标分析后的坐标点进行层次聚类得到的。图中每个点表示一个代码仓库,每种颜色表示代码仓库的一个类别,因此总共得到4个不同的簇,即将所有代码仓库分成4类。采用K均值聚类算法的聚类结果如图7所示,此图是根据对主坐标分析后的坐标点进行K均值聚类得到的。在图中也总共得到4个聚类中心,聚类中心是指代码仓库同一类别靠近的中心点,因此可得到4个不同的簇,即代码仓库的4个分类。采用邻近聚类算法的聚类结果如图8所示,此图是根据对主坐标分析后的坐标点进行邻近聚类得到的。图中每个点表示一个代码仓库,每种颜色表示代码仓库的一种类别,因此也得到4个不同的簇,即4个代码仓库的类别。采用3种不同的聚类算法均得到了相同的簇,即分类数量,但3种聚类算法的聚类结果仍存在一些差异。其中层次聚类结果与K均值聚类结果比较相似,因此这两种聚类算法对本实验数据集而言,效果比较接近。另外,在近邻聚类算法中一些有用的点被当作噪音去除,所以图中显示的聚类点少于另外两种聚类结果图中的点。因此,通过以上分析可知,层次聚类算法与K均值聚类算法的聚类结果均优于邻近聚类算法。
本文采用K均值聚类方法对学习者代码仓库进行聚类,将学习者分成4种类别,如表1所示。第一种类别的学习者人数为114,占总人数的83.4%;第二种类别的学习者人数为3,占总人数的2.2%;第三种类别的学习者人数为2,占总人数的1.5%;第四种类别的学习者人数为17,占总人数的12.5%。
根据实验数据集的学习者行为聚类结果对学习者进行分类,并根据每个类别的学习者行为表现评价学习者学习状态及学习效果。学习者行为主要包括提交行为和修改行为,对于提交行为表现,主要从Commit提交的内容和时间两方面进行分析;对于修改行为表现,主要从符合要求的代码数量方面进行分析。根据提交的标题和内容,通过人工判断是否符合实验要求。对一个代码仓库的判断实例如表2所示。
(1)第一种类别的代码仓库学习者行为表现分析(良好型)。对第一种类别的所有代码仓库进行统计分析,可发现这一类学习者的提交行为比较符合实验要求。另外,提交时间为2019年12月3日-2019年12月10日,所有代码仓库学习者的提交时间都在该区间内,此类代码仓库中的学习者代码大部分能达到实验要求。第一种类别的Commit提交内容与实验要求符合情况如表3所示。
表3 第一种类别的Commit提交内容与实验要求符合情况 下载原图
Table 3 Compliance situation between the submitted content of the Commit in the first category and the code required by the experiment
因此,第一种类别代码仓库的学习行为表现可评定为良好。该等级的代码仓库在提交内容上比较符合实验要求,提交时间从实验开始时间算起,不超过一星期完成,实验代码大部分符合实验要求。
(2)第二种类别的代码仓库学习者行为表现分析(中等型)。对第二种类别的所有代码仓库进行统计分析,可发现这一类学习者提交行为符合实验要求的次数均在一半以下。另外,提交时间为2019年12月3日-2019年12月11日,所有代码仓库的学习者提交时间都在该区间内,此类代码仓库中达到实验要求的代码数量也均在一半以下。第二种类别的Commit提交内容与实验要求符合情况如表4所示。
表4 第二种类别的Commit提交内容与实验要求符合情况 下载原图
Table 4 Compliance situation between the submitted content of the Commit in the second category and the code required by the experiment
因此,第二种类别代码仓库的学习行为表现可评定为中。该等级的代码仓库在提交内容上不太符合实验要求,提交时间从实验开始时间算起,在一星期左右完成,实验代码不太符合实验要求。
(3)第三种类别的代码仓库学习者行为表现分析(差型)。对第三种类别的所有代码仓库进行统计分析,可发现这一类学习者的Commit内容均较少,甚至没有按照实验要求完成。另外,提交时间为2019年12月8日-2019年12月17日,所有代码仓库学习者的提交时间都在该区间内。此类代码仓库中的学习者代码很少达到实验要求,甚至没有达到实验要求的代码。第三种类别的Commit提交内容与实验要求符合情况如表5所示。
因此,第三种类别代码仓库的学习行为表现可评定为差。该等级的代码仓库在提交内容上较少甚至不能符合实验要求。
(4)第四种类别的代码仓库学习者行为表现分析(优秀型)。对第四种类别的所有代码仓库进行统计分析,可发现这一类代码仓库学习者的Commit提交内容均符合实验要求。另外,提交时间为2019年12月3日-2019年12月8日,所有代码仓库的学习者提交时间都在该区间内,此类代码仓库中的学习者代码均能达到实验要求。第四种类别的Commit提交内容与实验要求符合情况如表6所示。
表5 第三种类别的Commit提交内容与实验要求符合情况 下载原图
Table 5 Compliance situation between the submitted content of the Commit in the third category and the code required by the experiment
表6 第四种类别的Commit提交内容与实验要求符合情况 下载原图
Table 6 Compliance situation between the submitted content of the Commit in the forth category and the code required by the experiment
因此,第四种类别的代码仓库学习行为表现可评定为优秀。该等级的代码仓库在提交内容上符合实验要求,提交时间从实验开始时间算起,不超过5天完成,实验代码符合实验要求。
本文实验结果表明,可通过代码仓库中学习者的提交与修改行为评价学习者学习状态,该方法为教育工作者评定学习者成绩与了解学习者学习情况提供了方向,也为教育工作者优化决策与教学方法提供了依据,从而提高教学质量与学习者学习效率及效果。下一步工作是针对此平台聚类分析的结果改进评分标准,并进行自动评分系统的设计与实现。
标签:
下一篇: 仓库管理系统优与劣