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

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

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

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

目前，諸多地方院校的選課推薦系統(tǒng)在處理海量選課信息時(shí)，存在推薦質(zhì)量差、反饋時(shí)間長(zhǎng)等問(wèn)題，難以滿足學(xué)習(xí)興趣與教學(xué)效果的需求。LFM算法作為一種隱語(yǔ)義模型方法，通過(guò)分析學(xué)生與課程的歷史評(píng)分行為來(lái)尋找潛在聯(lián)系，減少對(duì)其他因素的依賴，相比其他推薦算法具有邏輯簡(jiǎ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)致評(píng)分推薦結(jié)果不理想。

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

1? 相關(guān)理論

1.1? LFM推薦算法原理

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

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

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

1.2? 譜聚類

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

（1）輸入n名學(xué)生對(duì)m門(mén)課程的評(píng)分樣本集D={xij，i=1，…，n;j=1，…，m}，設(shè)定學(xué)生評(píng)分?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è)最小特征值所對(duì)應(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ù)的處理，而且無(wú)需考慮樣本空間的形狀，僅需計(jì)算數(shù)據(jù)集間的相似度矩陣就能實(shí)現(xiàn)聚類，相比傳統(tǒng)聚類方法在處理高校課程評(píng)分的高維、稀疏數(shù)據(jù)時(shí)更加有效。

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

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

2.1? 譜聚類過(guò)程

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

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

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

2.2? LFM推薦過(guò)程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1? 數(shù)據(jù)來(lái)源

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

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

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

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

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

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

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

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

[2] 陳萬(wàn)志，張爽，王德建，等.基于近鄰模型與概率矩陣分解的高校選課推薦算法 [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.

作者簡(jiǎn)介：劉旋（1991-），男，漢族，河南信陽(yáng)人，講師，碩士，研究方向：數(shù)據(jù)挖掘、模式分析。