基于譜聚類和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-），男，漢族，河南信陽人，講師，碩士，研究方向：數據挖掘、模式分析。