基于譜聚類和LFM的選課推薦算法設(shè)計(jì)

摘? 要：高校教務(wù)系統(tǒng)中學(xué)生數(shù)量和課程種類的飛速增長，使得傳統(tǒng)推薦算法難以處理海量、高維的選課數(shù)據(jù)，為進(jìn)一步提升大學(xué)生的選課效率，文章提出一種改進(jìn)的LFM隱語義模型推薦算法，首先構(gòu)造選課評分?jǐn)?shù)據(jù)的相似矩陣，通過譜聚類進(jìn)行初始分類，然后分類別構(gòu)建LFM模型并計(jì)算合理的推薦算法。通過在某高校的選課數(shù)據(jù)集上的對比實(shí)驗(yàn)，證明了本文算法具有較高的預(yù)測精度和較低的空間復(fù)雜度。

關(guān)鍵詞：推薦算法;隱語義模型;譜聚類算法

中圖分類號：TP391? ? ? 文獻(xiàn)標(biāo)識碼：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? 引? 言

人工智能時(shí)代的到來，使得高校教務(wù)系統(tǒng)逐漸成為大學(xué)生進(jìn)行自選課的主要平臺和途徑，由于選修課程種類的增多，大多學(xué)生對課程缺乏了解且選擇盲目。為了使學(xué)生更高效地選擇與自身學(xué)習(xí)興趣相似的課程，在傳統(tǒng)教務(wù)選課系統(tǒng)中加入了推薦算法，過濾出符合學(xué)生要求的課程。目前，主流的推薦算法主要包括協(xié)同過濾、聚類推薦、奇異值分解等。例如文獻(xiàn)[1]基于加權(quán)方式改進(jìn)協(xié)同過濾算法，成功應(yīng)用在學(xué)生課程推薦系統(tǒng)中，但忽視了數(shù)據(jù)的稀疏性;文獻(xiàn)[2]通過計(jì)算選課數(shù)據(jù)間的相似性確定學(xué)生的近鄰集合，采用概率矩陣分解的協(xié)同過濾算法進(jìn)行推薦;文獻(xiàn)[3]根據(jù)評論數(shù)據(jù)構(gòu)建用戶的偏好特征，并將相似偏好的用戶聚類，然后使用LFM[4]模型（潛在因子模型，Latent Factor Model）進(jìn)行推薦。

目前，諸多地方院校的選課推薦系統(tǒng)在處理海量選課信息時(shí)，存在推薦質(zhì)量差、反饋時(shí)間長等問題，難以滿足學(xué)習(xí)興趣與教學(xué)效果的需求。LFM算法作為一種隱語義模型方法，通過分析學(xué)生與課程的歷史評分行為來尋找潛在聯(lián)系，減少對其他因素的依賴，相比其他推薦算法具有邏輯簡單、空間復(fù)雜度低且推薦結(jié)果更優(yōu)等優(yōu)點(diǎn)，非常適合處理大規(guī)模、高維的選課數(shù)據(jù)。但隨著數(shù)據(jù)規(guī)模的擴(kuò)大，LFM算法的運(yùn)算效率也大幅降低，且不同學(xué)生群體的選課興趣也有較大差異，籠統(tǒng)地混為一談進(jìn)行計(jì)算會(huì)受到噪聲數(shù)據(jù)的干擾，導(dǎo)致評分推薦結(jié)果不理想。

本文首先采用余弦距離作為相似度度量標(biāo)準(zhǔn)，計(jì)算學(xué)生選課評分的相似度矩陣，然后通過譜聚類方法對學(xué)生數(shù)據(jù)進(jìn)行聚類，將學(xué)生群體進(jìn)行劃分，最后采用LFM算法分別構(gòu)建不同類簇的評分?jǐn)?shù)據(jù)矩陣，然后選取Top-N作為推薦結(jié)果。

1? 相關(guān)理論

1.1? LFM推薦算法原理

LFM通過奇異值矩陣分解（SVD）處理評分矩陣，得到用戶的潛在特征，以此評分缺失項(xiàng)目[5]。對于高校學(xué)生的選課評分?jǐn)?shù)據(jù)，LFM認(rèn)為課程評分值是學(xué)生對課程屬性的喜好程度與每門課程在這些屬性上的表現(xiàn)結(jié)果，并將評分矩陣R分解成為課程屬性P和學(xué)生喜好Q兩個(gè)矩陣的乘積，然后計(jì)算新的評分矩陣。

LFM通過尋找隱藏因子將學(xué)生的喜好和課程屬性聯(lián)系起來。假設(shè)R是一個(gè)U×I（學(xué)生×課程）大小的評分矩陣，LFM的核心思想是尋找兩個(gè)低維矩陣P=U×K（課程的屬性分類）和Q=I×K（學(xué)生的喜好分類），K是隱因子的個(gè)數(shù)，通過P和Q的重新計(jì)算，得到新的預(yù)測評分矩陣R=P×Q，R的表達(dá)式及損失函數(shù)分別如式（1）、式（2）所示：

這里，‖PU‖2+‖QI‖2是防止過度擬合的正則項(xiàng)系數(shù)，RUI為學(xué)生U對課程I的實(shí)際評分矩陣。通過計(jì)算損失函數(shù)C中兩個(gè)參數(shù)的偏導(dǎo)數(shù)，根據(jù)式（3）的梯度下降法，通過不斷迭代調(diào)整優(yōu)化參數(shù)，找到最優(yōu)的特征矩陣P和Q，最后用Q和P兩個(gè)矩陣的乘積，得到更新后的評分矩陣R，以此預(yù)測的未評價(jià)的課程分?jǐn)?shù)。

1.2? 譜聚類

譜聚類是一種基于圖論知識的降維聚類方法，具有計(jì)算量小、易于實(shí)現(xiàn)，善于處理高維數(shù)據(jù)的特點(diǎn)[6]。該方法首先構(gòu)建基于相似度的無向權(quán)重圖，然后按照切邊規(guī)則將圖分割為不同的子圖，從而實(shí)現(xiàn)聚類，基于課程評分?jǐn)?shù)據(jù)的譜聚類實(shí)現(xiàn)過程如下：

（1）輸入n名學(xué)生對m門課程的評分樣本集D={xij，i=1，…，n;j=1，…，m}，設(shè)定學(xué)生評分?jǐn)?shù)據(jù)S?={x1，…，xn}間的相似性度量標(biāo)準(zhǔn)，以此構(gòu)造相似矩陣S;

（2）根據(jù)相似矩陣S構(gòu)建鄰接矩陣W以及度矩陣O;

（3）計(jì)算拉普拉斯矩陣L=O-W，并計(jì)算出L的前k個(gè)最小特征值所對應(yīng)的特征向量：u1，u2，…，uk;

（4）將上面的k個(gè)列向量組成n×k矩陣并標(biāo)準(zhǔn)化：V={u1，u2，…，uk};

（5）使用K-means算法進(jìn)行聚類，得到類簇集合B= {b1，b2，…，bh}（h為聚類個(gè)數(shù)）。

由于譜聚類算法是基于降維的方法，所以更適用于高維度數(shù)據(jù)的處理，而且無需考慮樣本空間的形狀，僅需計(jì)算數(shù)據(jù)集間的相似度矩陣就能實(shí)現(xiàn)聚類，相比傳統(tǒng)聚類方法在處理高校課程評分的高維、稀疏數(shù)據(jù)時(shí)更加有效。

2? 基于譜聚類的LFM推薦算法

針對學(xué)生的部分課程分?jǐn)?shù)據(jù)集的高維性與稀疏性，本文首先計(jì)算數(shù)據(jù)間的相似度矩陣，然后采用譜聚類進(jìn)行初始分類，使得具有相同選課興趣的學(xué)生聚集到一起，最后根據(jù)不同興趣的群體分別采用LFM模型進(jìn)行評分預(yù)測，并從中選取Top-N門課程推薦給相應(yīng)的學(xué)生。

2.1? 譜聚類過程

根據(jù)數(shù)據(jù)維度高、數(shù)值稀疏等特點(diǎn)，本文采用余弦距離度量學(xué)生評分間的相似性。假設(shè)學(xué)生i和學(xué)生j對評分課程的相似度表示為：

其中：Ti和Tj分別為學(xué)生i和j的評分課程集合;Tij為學(xué)生i和j所有的評分課程;rli與rlj分別為學(xué)生i和j對課程l的評分。

基于相似度權(quán)重采用全連接法構(gòu)造初始的相似性矩陣S，以此作為1.2節(jié)譜聚類的初始輸入，然后利用K-means聚類得到n個(gè)選課興趣類別的學(xué)生群體。

2.2? LFM推薦過程

LFM模型通過輸入課程評分矩陣，計(jì)算得到學(xué)生對課程隱藏興趣分類的喜好程度。由于譜聚類分解了初始評分矩陣的規(guī)模，且每一類的數(shù)據(jù)相似度更高，提升了LFM的抗噪性，使得LFM的推薦結(jié)果更準(zhǔn)確，具體步驟如下：

（1）隨機(jī)初始化評分矩陣P和M的值;

（2）根據(jù)式（3）計(jì)算P和M的梯度?P和?M，確定最快的下降方向;

（3）然后通過式（4）計(jì)算新的PUK與QUK，其中α表示學(xué)習(xí)速率，其值越大，則迭代下降得越快，λ為正則化參數(shù)，用于防止過擬合。α和λ均可通過實(shí)驗(yàn)統(tǒng)計(jì)得到：

（4）循環(huán)迭代步驟（2）（3），直到開始收斂或設(shè)置指定的迭代次數(shù)時(shí)停止;

（5）根據(jù)得到的最優(yōu)P和M計(jì)算出最終的評分預(yù)測矩陣。

2.3? 改進(jìn)算法的詳細(xì)步驟

輸入數(shù)據(jù)：m名學(xué)生對n門課程的評分表R（存在大部分缺失值）。

輸出數(shù)據(jù)：m名學(xué)生的推薦課程列表。

Step1 根據(jù)評分表R，采用式（4）計(jì)算m名學(xué)生之間的相似度矩陣S。

Step2 根據(jù)S譜聚類得到B個(gè)學(xué)生類簇。

Step3 初始化B個(gè)矩陣集合{P1，P2，…，PC}和{Q1，Q2，…，QC}，采用LFM計(jì)算得到新的評分預(yù)測矩陣R。

Step4 基于Top-N算法從R中選擇分值較大的k門課程推薦給相應(yīng)學(xué)生。

3? 實(shí)驗(yàn)比較

3.1? 數(shù)據(jù)來源

本文的實(shí)驗(yàn)數(shù)據(jù)來源于某大學(xué)教務(wù)管理Web系統(tǒng)中學(xué)生選課數(shù)據(jù)集，共1057名計(jì)算機(jī)專業(yè)學(xué)生，15門選修課程，15687條在2018學(xué)年的選課評分信息，總共包含600條課程評分，每名學(xué)生至少對6門課程進(jìn)行了評分。

3.2? 實(shí)驗(yàn)評測標(biāo)準(zhǔn)

本文實(shí)驗(yàn)中使用均方根誤差（RMSE）和時(shí)間作為主要評價(jià)標(biāo)準(zhǔn)，均方根誤差項(xiàng)又可稱為標(biāo)準(zhǔn)誤差，它是用來反映一個(gè)數(shù)據(jù)的離散程度。

式中，Rij為推薦算法計(jì)算出的學(xué)生i對選修課j的預(yù)測評分， 為教務(wù)系統(tǒng)中學(xué)生i對選修課j的實(shí)際評分，N為數(shù)據(jù)集中的課程評分?jǐn)?shù)。

3.3? 實(shí)驗(yàn)分析

本文實(shí)驗(yàn)環(huán)境為：Python3.6、Win10系統(tǒng)、內(nèi)存16G、處理器i7-7400。針對該校的選課評分統(tǒng)計(jì)數(shù)據(jù)，將本文算法與UserCF[7]、ItemCF[7]和LFM算法進(jìn)行試驗(yàn)對比。

（a）隱因子個(gè)數(shù)影響

（b）推薦項(xiàng)目數(shù)影響

首先分析LFM矩陣分解過程中隱因子個(gè)數(shù)K對算法的影響，觀察圖1（a）可知，當(dāng)推薦項(xiàng)目數(shù)固定時(shí)，隨著K的增大，LFM和本文算法的RMSE均逐步降低，當(dāng)K>15時(shí)，RMSE逐漸趨于穩(wěn)定，且本文算法較LFM誤差降低。其次測試Top-N推薦中，推薦課程數(shù)目對推薦結(jié)果的影響，對比算法在不同N值下的誤差如圖1（b）所示，各算法隨著推薦數(shù)目的增加，誤差逐漸提高，當(dāng)N>8之后，RMSE開始趨于穩(wěn)定。在評分準(zhǔn)確率上，本文算法在不同的推薦數(shù)目上，均取得最優(yōu)，說明通過譜聚類，不僅分解了數(shù)據(jù)規(guī)模，而且優(yōu)化了LFM的初始評分矩陣，在一定程度上降低了噪聲干擾，從而使推薦結(jié)果更精確。

4? 結(jié)? 論

本文在LFM的基礎(chǔ)上融合了譜聚類，改進(jìn)算法在推薦過程中需要考慮到相似學(xué)生間選課的關(guān)聯(lián)性，通過聚類優(yōu)化LFM的初始評分矩陣，從而提高算法的推薦準(zhǔn)確性。如何增量式地處理動(dòng)態(tài)選課評分?jǐn)?shù)據(jù)，是本文未來的研究重點(diǎn)。

參考文獻(xiàn)：

[1] 沈苗，來天平，王素美，等.北京大學(xué)課程推薦引擎的設(shè)計(jì)和實(shí)現(xiàn) [J].智能系統(tǒng)學(xué)報(bào)，2015，10（3）：369-375.

[2] 陳萬志，張爽，王德建，等.基于近鄰模型與概率矩陣分解的高校選課推薦算法 [J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），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] 陳曄，劉志強(qiáng).基于LFM矩陣分解的推薦算法優(yōu)化研究 [J].計(jì)算機(jī)工程與應(yīng)用，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-），男，漢族，河南信陽人，講師，碩士，研究方向：數(shù)據(jù)挖掘、模式分析。