基于谱聚类协作学习分组的研究

邓广华　李文彪

摘 要：协作学习系统构建了一个协作学习的环境，为教师与学生、学生与学生进行在线讨论、协作与交流提供了一个良好的平台。在线学习过程进行科学的分组，把具有相似兴趣的用户分到一组进行专题或自由讨论提高学习效率。用谱聚类算法进行分组，用户的兴趣模型通过向量空间创建，用余弦夹角公式计算相似程度。

关键词：协作学习 谱聚类 向量空间 余弦夹角

中图分类号：G420 文献标识码：A 文章编号：1672-3791（2016）06（b）-0167-02

协作学习系统可以在用户自主学习过程中根据用户的兴趣主动推荐学习资源给用户进行在线学习，满足个性化学习[1]需要，实现“因材施教”的教育理念；同时可以根据各自的兴趣，通过聚类算法实现自动分组，使兴趣相同的用户组成一个学习小组，实现协作学习，从而有效提高学习过程中的主动参与性以及团队合作精神和沟通交流能力。为了更准确的把兴趣相似的学生分在同一组，该文通过改进谱聚类算法对在线学习用户进行自动分组，兴趣模型通过向量空间建模，创建为20维。用余弦夹角公式构建相似矩阵，再通过谱聚类NJW[2]算法进行聚类分组，自动确定用户集划分为几个组，以实现协作学习。

1 兴趣模型与余弦夹角

学生兴趣模型同样采用向量空间表示法表示，如：

Student（ui）={（ki1，wi1），（ki2，wi2），...，（kih，wih）}，其中ui为学生i，kih为表示学生兴趣的关键词，wih为学生对关键词kih的感兴趣的程度。假设学生兴趣模型总数为n，我们构造一个n×n的距离矩阵S，S[i][j]的值表示学生i和学生j的距离权值，学生兴趣模型之间的距离采用余弦夹角值的倒数计算：

2 基于谱聚类算法分组

谱聚类算法要先构建相似矩阵， 相似矩阵体现了一组量化评估数据集之间的相对相似性。相似矩阵通常可以使用欧式距离、余弦相似度、高斯核函数来构建，该文采用高斯核函数进行构建。因为高斯核函数构建的相似矩阵做谱聚类分析的效果较好[3]。

按照公式（3）计算出兴趣相似程度值，进而构建谱聚类算法的相似矩阵W。该文使用Ng，Jordan在2001年提出的NJW算法[2]。相似矩阵W构建好后选取规范拉氏矩阵L=DWD做特征值分解，D为度矩阵，是对角矩阵，D等于相似矩阵W的第i行各元素的累加值，其中i（1，n）。分解出拉普拉斯矩阵L的特征值和对应的特征向量，特征值从高到低排序，然后选取前K个特征值对应的特征向量，每个特征向量作为一列，构成矩阵H，再对矩阵H的每一行进行归一化处理后得到矩阵Y，，构成n×k的矩阵，其中n为原数据点数（待分组的用户数），这样把矩阵Y的每一行看成是空间Rk上的一个新点，它与原数据点一 一对应着，然后对空间Rk进行普通聚类处理，该文使用K-means聚类算法对空间Rk新数据点集进行聚类，得到k个聚类，即分成k组。

谱聚类的类目选取直接影响聚类效果，得到特征值后对他从大到小排序，选取拉氏矩阵L的前k个最大特征值就是聚类数目。第k个的特征值与第k+1个的特征值有个跳跃即谱隙（eigen gap），当样本空间中所有数据点划分成K类时的聚类效果越好那么第k个特征值与第K+1个特征值的跳跃谱隙就越大这种关系。该文采用Azran和Ghahramani于2006年提出的根据M步随机游走后的概率矩阵PM的eigen gap[3]来确定K值，它更接近真实的聚类数目。基于谱聚类NJW算法对学生进行分组算法如下：

算法的输入为：n个学生兴趣模型；输出为：j个组；

（1）对于待分组的学生数据集X={xi}，其中n为总学生数，通过公式（3）高斯核函数计算出学生之间的兴趣相似度，得到一个n×n的相似矩阵W，并由相似矩阵W构造Laplician矩阵L。（2）通过eigen gap方法确定K值。（3）计算矩阵L的前K个特征值及其所对应的特征向量，以每个特征向量作为一列构建n×k的矩阵H=[h1，h2，…，hk]Rn×k。（4）将H向量中的行向量做归一化处理得到Y矩阵，即。（5）把矩阵Y中的每一行看成是Rk空间上的数据点，这些数据点与原数据点一 一对应做K-means聚类，得到k个聚类。（6）假如矩阵Y的第i行属于K-means聚类的第j类，那么原数据点也归为第j类，如果没有完成转到Step5，直到全部数据归类完成为止。

3 结语

兴趣模型通过余弦夹角公式计算出的是0～1之间的值，模型之间越相似就越接近1，使用这个值的倒数值作为谱图的权重值，兴趣模型之间越相似就靠得越近，从而很好的创建相似矩阵。兴趣模型的元素是键值对，选用余弦夹角比较合适，该文实现了通过高斯核函数构建相似矩阵后谱聚类算法对键值对向量空间模型的聚类分组，实现协作学习。

参考文献

[1] ZPOLATE，AKARGB.学习风格对学习系统的自动检测[J].计算机与教育，2009（2）：355-367.

[2] Ng A.Y.，Jordan M.I.，Weiss Y.谱聚类算法分析[Z].2001：849-856.

[3] Azran A.，Ghahramani Z.自动多尺度数据聚类的谱方法[Z].IEEE计算机学会计算机视觉与模式识别程序，2006：190-197.