基于谱聚类和LFM的选课推荐算法设计

摘  要：高校教务系统中学生数量和课程种类的飞速增长，使得传统推荐算法难以处理海量、高维的选课数据，为进一步提升大学生的选课效率，文章提出一种改进的LFM隐语义模型推荐算法，首先构造选课评分数据的相似矩阵，通过谱聚类进行初始分类，然后分类别构建LFM模型并计算合理的推荐算法。通过在某高校的选课数据集上的对比实验，证明了本文算法具有较高的预测精度和较低的空间复杂度。

关键词：推荐算法;隐语义模型;谱聚类算法

中图分类号：TP391      文献标识码：A 文章编号：2096-4706（2020）01-0014-03

Abstract：The rapid growth of the number of students and the types of courses in the educational administration system of colleges and universities，make the traditional recommendation algorithm is difficult to deal with mass and course of high-dimensional data，in order to further enhance studentscourse selection efficiency，this paper proposes a recommendation algorithm to improve the LFM argot meaning of model，the first data structure course score of similar matrix，the initial classification by spectral clustering and classification build LFM model and calculate the reasonable recommendations. Through the comparison experiment on the data set of course selection in a university，it is proved that the algorithm in this paper has higher prediction accuracy and lower space complexity.

Keywords：recommendation algorithm;LFM（latent factor model）;spectral clustering algorithm

0  引  言

人工智能时代的到来，使得高校教务系统逐渐成为大学生进行自选课的主要平台和途径，由于选修课程种类的增多，大多学生对课程缺乏了解且选择盲目。为了使学生更高效地选择与自身学习兴趣相似的课程，在传统教务选课系统中加入了推荐算法，过滤出符合学生要求的课程。目前，主流的推荐算法主要包括协同过滤、聚类推荐、奇异值分解等。例如文献[1]基于加权方式改进协同过滤算法，成功应用在学生课程推荐系统中，但忽视了数据的稀疏性;文献[2]通过计算选课数据间的相似性确定学生的近邻集合，采用概率矩阵分解的协同过滤算法进行推荐;文献[3]根据评论数据构建用户的偏好特征，并将相似偏好的用户聚类，然后使用LFM[4]模型（潜在因子模型，Latent Factor Model）进行推荐。

目前，诸多地方院校的选课推荐系统在处理海量选课信息时，存在推荐质量差、反馈时间长等问题，难以满足学习兴趣与教学效果的需求。LFM算法作为一种隐语义模型方法，通过分析学生与课程的历史评分行为来寻找潜在联系，减少对其他因素的依賴，相比其他推荐算法具有逻辑简单、空间复杂度低且推荐结果更优等优点，非常适合处理大规模、高维的选课数据。但随着数据规模的扩大，LFM算法的运算效率也大幅降低，且不同学生群体的选课兴趣也有较大差异，笼统地混为一谈进行计算会受到噪声数据的干扰，导致评分推荐结果不理想。

本文首先采用余弦距离作为相似度度量标准，计算学生选课评分的相似度矩阵，然后通过谱聚类方法对学生数据进行聚类，将学生群体进行划分，最后采用LFM算法分别构建不同类簇的评分数据矩阵，然后选取Top-N作为推荐结果。

1  相关理论

1.1  LFM推荐算法原理

LFM通过奇异值矩阵分解（SVD）处理评分矩阵，得到用户的潜在特征，以此评分缺失项目[5]。对于高校学生的选课评分数据，LFM认为课程评分值是学生对课程属性的喜好程度与每门课程在这些属性上的表现结果，并将评分矩阵R分解成为课程属性P和学生喜好Q两个矩阵的乘积，然后计算新的评分矩阵。

LFM通过寻找隐藏因子将学生的喜好和课程属性联系起来。假设R是一个U×I（学生×课程）大小的评分矩阵，LFM的核心思想是寻找两个低维矩阵P=U×K（课程的属性分类）和Q=I×K（学生的喜好分类），K是隐因子的个数，通过P和Q的重新计算，得到新的预测评分矩阵R=P×Q，R的表达式及损失函数分别如式（1）、式（2）所示：

这里，‖PU‖2+‖QI‖2是防止过度拟合的正则项系数，RUI为学生U对课程I的实际评分矩阵。通过计算损失函数C中两个参数的偏导数，根据式（3）的梯度下降法，通过不断迭代调整优化参数，找到最优的特征矩阵P和Q，最后用Q和P两个矩阵的乘积，得到更新后的评分矩阵R，以此预测的未评价的课程分数。

1.2  谱聚类

谱聚类是一种基于图论知识的降维聚类方法，具有计算量小、易于实现，善于处理高维数据的特点[6]。该方法首先构建基于相似度的无向权重图，然后按照切边规则将图分割为不同的子图，从而实现聚类，基于课程评分数据的谱聚类实现过程如下：

（1）输入n名学生对m门课程的评分样本集D={xij，i=1，…，n;j=1，…，m}，设定学生评分数据S?={x1，…，xn}间的相似性度量标准，以此构造相似矩阵S;

（2）根据相似矩阵S构建邻接矩阵W以及度矩阵O;

（3）计算拉普拉斯矩阵L=O-W，并计算出L的前k个最小特征值所对应的特征向量：u1，u2，…，uk;

（4）将上面的k个列向量组成n×k矩阵并标准化：V={u1，u2，…，uk};

（5）使用K-means算法进行聚类，得到类簇集合B= {b1，b2，…，bh}（h为聚类个数）。

由于谱聚类算法是基于降维的方法，所以更适用于高维度数据的处理，而且无需考虑样本空间的形状，仅需计算数据集间的相似度矩阵就能实现聚类，相比传统聚类方法在处理高校课程评分的高维、稀疏数据时更加有效。

2  基于谱聚类的LFM推荐算法

针对学生的部分课程分数据集的高维性与稀疏性，本文首先计算数据间的相似度矩阵，然后采用谱聚类进行初始分类，使得具有相同选课兴趣的学生聚集到一起，最后根据不同兴趣的群体分别采用LFM模型进行评分预测，并从中选取Top-N门课程推荐给相应的学生。

2.1  谱聚类过程

根据数据维度高、数值稀疏等特点，本文采用余弦距离度量学生评分间的相似性。假设学生i和学生j对评分课程的相似度表示为：

其中：Ti和Tj分别为学生i和j的评分课程集合;Tij为学生i和j所有的评分课程;rli与rlj分别为学生i和j对课程l的评分。

基于相似度权重采用全连接法构造初始的相似性矩阵S，以此作为1.2节谱聚类的初始输入，然后利用K-means聚类得到n个选课兴趣类别的学生群体。

2.2  LFM推荐过程

LFM模型通过输入课程评分矩阵，计算得到学生对课程隐藏兴趣分类的喜好程度。由于谱聚类分解了初始评分矩阵的规模，且每一类的数据相似度更高，提升了LFM的抗噪性，使得LFM的推荐结果更准确，具体步骤如下：

（1）随机初始化评分矩阵P和M的值;

（2）根据式（3）计算P和M的梯度?P和?M，确定最快的下降方向;

（3）然后通过式（4）计算新的PUK与QUK，其中α表示学习速率，其值越大，则迭代下降得越快，λ为正则化参数，用于防止过拟合。α和λ均可通过实验统计得到：

（4）循环迭代步骤（2）（3），直到开始收敛或设置指定的迭代次数时停止;

（5）根据得到的最优P和M计算出最终的评分预测矩阵。

2.3  改进算法的详细步骤

输入数据：m名学生对n门课程的评分表R（存在大部分缺失值）。

输出数据：m名学生的推荐课程列表。

Step1 根据评分表R，采用式（4）计算m名学生之间的相似度矩阵S。

Step2 根据S谱聚类得到B个学生类簇。

Step3 初始化B个矩阵集合{P1，P2，…，PC}和{Q1，Q2，…，QC}，采用LFM计算得到新的评分预测矩阵R。

Step4 基于Top-N算法从R中选择分值较大的k门课程推荐给相应学生。

3  实验比较

3.1  数据来源

本文的实验数据来源于某大学教务管理Web系统中学生选课数据集，共1057名计算机专业学生，15门选修课程，15687条在2018学年的选课评分信息，总共包含600条课程评分，每名学生至少对6门课程进行了评分。

3.2  实验评测标准

本文实驗中使用均方根误差（RMSE）和时间作为主要评价标准，均方根误差项又可称为标准误差，它是用来反映一个数据的离散程度。

式中，Rij为推荐算法计算出的学生i对选修课j的预测评分， 为教务系统中学生i对选修课j的实际评分，N为数据集中的课程评分数。

3.3  实验分析

本文实验环境为：Python3.6、Win10系统、内存16G、处理器i7-7400。针对该校的选课评分统计数据，将本文算法与UserCF[7]、ItemCF[7]和LFM算法进行试验对比。

（a）隐因子个数影响

（b）推荐项目数影响

首先分析LFM矩阵分解过程中隐因子个数K对算法的影响，观察图1（a）可知，当推荐项目数固定时，随着K的增大，LFM和本文算法的RMSE均逐步降低，当K>15时，RMSE逐渐趋于稳定，且本文算法较LFM误差降低。其次测试Top-N推荐中，推荐课程数目对推荐结果的影响，对比算法在不同N值下的误差如图1（b）所示，各算法随着推荐数目的增加，误差逐渐提高，当N>8之后，RMSE开始趋于稳定。在评分准确率上，本文算法在不同的推荐数目上，均取得最优，说明通过谱聚类，不仅分解了数据规模，而且优化了LFM的初始评分矩阵，在一定程度上降低了噪声干扰，从而使推荐结果更精确。

4  结  论

本文在LFM的基础上融合了谱聚类，改进算法在推荐过程中需要考虑到相似学生间选课的关联性，通过聚类优化LFM的初始评分矩阵，从而提高算法的推荐准确性。如何增量式地处理动态选课评分数据，是本文未来的研究重点。

参考文献：

[1] 沈苗，来天平，王素美，等.北京大学课程推荐引擎的设计和实现 [J].智能系统学报，2015，10（3）：369-375.

[2] 陈万志，张爽，王德建，等.基于近邻模型与概率矩阵分解的高校选课推荐算法 [J].辽宁工程技术大学学报（自然科学版），2017，36（9）：976-982.

[3] GANU G，KAKODKAR Y，MARIAN A. Improving the quality of predictions using textual information in online user reviews [J].Information Systems，2013，38（1）：1-15.

[4] KOOPMAN S J，LUCAS A，MONTEIRO A A. The Multi-State Latent Factor Intensity Model for Credit Rating Transitions [J].SSRN Electronic Journal，2008，142（1）：399-424.

[5] 陈晔，刘志强.基于LFM矩阵分解的推荐算法优化研究 [J].计算机工程与应用，2019，55（2）：116-120+167.

[6] DHILLON I S，GUAN Y，KULIS B. Kernel k-means：spectral clustering and normalized cuts [C]//KDD04 Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining，Seattle，USA，August 22-25，2004. New York：ACM，2004：551-556.

[7] WANG J，VRIES A P D，REINDERS M J T. Unifying user-based and item-based collaborative filtering approaches by similarity fusion [C]//SIGIR 2006：Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，Seattle，Washington，USA，August 6-11，2006. ACM，2006.

作者簡介：刘旋（1991-），男，汉族，河南信阳人，讲师，硕士，研究方向：数据挖掘、模式分析。