協(xié)同過(guò)濾技術(shù)在高校選課推薦系統(tǒng)中的應(yīng)用*

曹秀麗

(仰恩大學(xué)工程技術(shù)學(xué)院，福建 泉州 362014)

目前，大多數(shù)高校的選課系統(tǒng)智能性不強(qiáng).在目標(biāo)學(xué)生沒(méi)有明確需求的情況下，智能選課推薦系統(tǒng)可以通過(guò)學(xué)生的已學(xué)課程分析出他的偏好，并為其推薦可能喜歡的課程.學(xué)生有學(xué)生特定的屬性，課程也有課程特定的屬性，根據(jù)已有的學(xué)生和課程的數(shù)據(jù)信息分析出學(xué)生可能喜愛(ài)的課程并進(jìn)行智能推送[1-4]，是本研究所要解決的主要問(wèn)題.

1 研究思路

圖1 IW-UW-CF算法實(shí)現(xiàn)課程推薦的思路Fig. 1 Course Recommendation Based on IW-UW-CF Algorithm

智能選課推薦系統(tǒng)通過(guò)協(xié)同過(guò)濾(CF)算法來(lái)實(shí)現(xiàn)選課推薦功能.基于用戶(hù)的協(xié)同過(guò)濾(U-CF)算法是：首先采集學(xué)生的專(zhuān)業(yè)、課程等信息，構(gòu)造學(xué)生-課程評(píng)分表，并利用它來(lái)實(shí)現(xiàn)最基本的課程推薦；然后基于學(xué)生的信息來(lái)計(jì)算學(xué)生評(píng)分的相似度，根據(jù)相似度進(jìn)行課程推薦.基于項(xiàng)目的協(xié)同過(guò)濾(I-CF)算法是根據(jù)課程的屬性考慮課程的相似度，根據(jù)相似度進(jìn)行課程推薦.[5-8]為提高推薦精度，采用基于項(xiàng)目-用戶(hù)加權(quán)協(xié)同過(guò)濾(IW-UW-CF)算法實(shí)現(xiàn)學(xué)生選課推薦功能.IW-UW-CF算法實(shí)現(xiàn)課程推薦的思路如圖1所示.

2 CF算法

CF算法中，一種是U-CF算法，以用戶(hù)為研究對(duì)象，計(jì)算用戶(hù)與用戶(hù)對(duì)項(xiàng)目的評(píng)分相似度；另一種是I-CF算法，以項(xiàng)目為研究對(duì)象，計(jì)算用戶(hù)對(duì)項(xiàng)目與項(xiàng)目的評(píng)分相似度.下面就這2種推薦技術(shù)的具體流程給出相應(yīng)描述[9-10].

2.1 I-CF算法

I-CF算法，是根據(jù)用戶(hù)-項(xiàng)目評(píng)分表獲得項(xiàng)目之間的評(píng)分相似度，將相似度一致的項(xiàng)目推薦給目標(biāo)用戶(hù).用戶(hù)l對(duì)項(xiàng)目a和b的評(píng)分相似度為

其中：Ta和Tb分別為項(xiàng)目a和b的評(píng)分用戶(hù)；Tab為項(xiàng)目a和b所有的評(píng)分用戶(hù)；rl,a和rl,b分別為用戶(hù)l對(duì)項(xiàng)目a和b的評(píng)分.算法具體流程[11]如下：

(ⅰ)轉(zhuǎn)換采集到的數(shù)據(jù)，將用戶(hù)對(duì)項(xiàng)目的評(píng)分以二維表的形式表示.

(ⅱ)根據(jù)用戶(hù)-項(xiàng)目評(píng)分表，獲得項(xiàng)目之間的評(píng)分相似度，構(gòu)造項(xiàng)目相似度矩陣.

(ⅲ)找出項(xiàng)目相似度最高的k個(gè)最近鄰.

(ⅳ)將最近鄰?fù)扑徒o目標(biāo)用戶(hù).

因?yàn)轫?xiàng)目的特征屬性相對(duì)穩(wěn)定，所以項(xiàng)目的分類(lèi)容易確定，可以在線(xiàn)下獲取項(xiàng)目之間的評(píng)分相似度，生成高效的項(xiàng)目推薦列表.但同時(shí)也存在缺陷，如在評(píng)分表信息較少的情況下，因可用數(shù)據(jù)不多而難以獲得項(xiàng)目相似度，導(dǎo)致無(wú)法實(shí)現(xiàn)項(xiàng)目推薦功能.[12]

2.2 U-CF算法

U-CF算法[13]是計(jì)算用戶(hù)與用戶(hù)對(duì)項(xiàng)目的評(píng)分相似度，根據(jù)最近鄰預(yù)估目標(biāo)用戶(hù)的評(píng)分，將預(yù)估評(píng)分最高的項(xiàng)目推薦給目標(biāo)用戶(hù).用戶(hù)i和j對(duì)項(xiàng)目c的評(píng)分相似度為

(1)

其中：Ti和Tj分別為用戶(hù)i和j的評(píng)分項(xiàng)目；Tij為用戶(hù)i和j所有的評(píng)分項(xiàng)目；ri,c與rj,c分別為用戶(hù)i和j對(duì)項(xiàng)目c的評(píng)分.算法具體流程如下：

(ⅰ)轉(zhuǎn)換系統(tǒng)中的初始數(shù)據(jù)，根據(jù)用戶(hù)對(duì)項(xiàng)目的評(píng)分構(gòu)建二維表，記為R.

(ⅱ)計(jì)算用戶(hù)i和j對(duì)項(xiàng)目c的評(píng)分相似度，找出目標(biāo)用戶(hù)i的最近鄰，構(gòu)造近鄰用戶(hù)集.

(ⅲ)計(jì)算出用戶(hù)對(duì)項(xiàng)目的預(yù)估評(píng)分加權(quán)，通過(guò)Top-N給出推薦列表.

用戶(hù)i對(duì)未評(píng)分項(xiàng)目d的預(yù)估評(píng)分為

(2)

3 CF算法在選課推薦系統(tǒng)中的應(yīng)用

3.1 U-CF算法的應(yīng)用

圖2 U-CF算法在選課推薦系統(tǒng)中的應(yīng)用流程Fig. 2 Procedures of Applying U-CF Algorithm in Course Recommendation System

U-CF算法應(yīng)用流程如圖2所示.算法的實(shí)現(xiàn)主要包括3個(gè)過(guò)程：

(1)數(shù)據(jù)集的選取.采用二維矩陣表示學(xué)生對(duì)課程的評(píng)分，即m學(xué)生-n課程評(píng)分表R，其中m表示學(xué)生數(shù)，n表示課程數(shù)，第l個(gè)學(xué)生對(duì)第c門(mén)課程的評(píng)分為rl,c.[14]

(2)計(jì)算學(xué)生對(duì)課程的評(píng)分相似度.相似度計(jì)算公式(1)是目標(biāo)學(xué)生尋找最近鄰的主要工具，也是目標(biāo)學(xué)生獲取最終Top-N推薦集的關(guān)鍵步驟.根據(jù)學(xué)生對(duì)課程的評(píng)分相似度建立學(xué)生相似度二維表.

(3)實(shí)驗(yàn)結(jié)果.選取50名學(xué)生-30門(mén)課程進(jìn)行模擬實(shí)驗(yàn).近鄰數(shù)k取10時(shí)，系統(tǒng)將預(yù)估評(píng)分最高的10門(mén)課程推薦給目標(biāo)學(xué)生.以50名學(xué)生對(duì)30門(mén)課程的評(píng)分作為輸入數(shù)據(jù).因?yàn)閷?shí)驗(yàn)過(guò)程類(lèi)似，所以?xún)H以學(xué)號(hào)是12322的目標(biāo)學(xué)生為例來(lái)演示實(shí)驗(yàn)過(guò)程.根據(jù)選課推薦原理，給出如下3個(gè)具體步驟：

(ⅰ)計(jì)算最近鄰.在50名學(xué)生-30門(mén)課程的記錄里，目標(biāo)學(xué)生12322最近鄰集及其相似度如表1所示.

(ⅱ)根據(jù)最近鄰集預(yù)估目標(biāo)學(xué)生對(duì)未評(píng)分課程的評(píng)分.以學(xué)生11677為例，根據(jù)(2)式預(yù)估學(xué)生12322對(duì)30門(mén)課程的評(píng)分，結(jié)果如表2所示.

表1 目標(biāo)學(xué)生12322的最近鄰集

表2 學(xué)生12322對(duì)30門(mén)課程的預(yù)估評(píng)分

(ⅲ)獲取目標(biāo)學(xué)生的Top-N推薦課程列表.根據(jù)目標(biāo)學(xué)生12322對(duì)30門(mén)課程的預(yù)估評(píng)分，將評(píng)分最高的10門(mén)課程(課程號(hào)47，56，46，90，57，62，77，85，69，75，評(píng)分為5)推薦給目標(biāo)學(xué)生.

3.2 改進(jìn)算法的應(yīng)用

3.2.1 基于項(xiàng)目加權(quán)的協(xié)同過(guò)濾(IW-CF)算法的應(yīng)用 (1)基本思想.考慮不同課程的權(quán)重作用，通過(guò)項(xiàng)目加權(quán)調(diào)整目標(biāo)學(xué)生對(duì)課程的評(píng)分相似度，從而影響課程最近鄰的選取.[15-16]

加權(quán)之前先計(jì)算課程c和d的相似度sim(c,d).對(duì)于已評(píng)分課程c(c∈Tij),其權(quán)重為

(3)

(2)算法過(guò)程.求權(quán)重是加權(quán)相似度的關(guān)鍵部分.將已有信息數(shù)據(jù)表示為學(xué)生-課程二維表，再構(gòu)建課程相似度二維表，尋找目標(biāo)課程最近鄰，對(duì)目標(biāo)學(xué)生給出可能會(huì)選修的課程.

算法：計(jì)算課程相似度權(quán)重.

輸入數(shù)據(jù)：學(xué)生i、學(xué)生j、學(xué)生-課程評(píng)分表R、課程相似度表H、共同評(píng)分課程Tij.

輸出數(shù)據(jù)：學(xué)生i和j對(duì)已評(píng)分課程c的權(quán)重wi,j(c)，c∈Tij.

Step 1p=0,T1=Tij；

Step 2 在T1里獲取c，T1=T1-{c}，p++；

Step 3T2=Tij，wi,j(c)=0,q=1；

Step 4 在H里獲取sim(c,d),其中d∈T2且d≠c；

Step 5q++，T2=T2-j5i0abt0b；

Step 6wi,j(c)=wi,j(c)+sim(c,d)；

Step 7 若q<|Tij|,則執(zhí)行Step 4；

Step 8wi,j(c)=wi,j(c)×(ri,c+rj,c)；

Step 9 若p<|Tij|，則執(zhí)行Step 2,否則結(jié)束.

根據(jù)這9個(gè)步驟獲得課程所占的權(quán)重后，通過(guò)課程相似度加權(quán)獲得學(xué)生加權(quán)相似度，然后查找目標(biāo)課程的最近鄰，構(gòu)造最近鄰集，得到推薦課程列表.

3.2.2 基于用戶(hù)加權(quán)的協(xié)同過(guò)濾(UW-CF)算法 (1)基本思想.考慮不同學(xué)生的權(quán)重作用，通過(guò)用戶(hù)加權(quán)調(diào)整預(yù)估評(píng)分公式，從而提高學(xué)生對(duì)課程的預(yù)估準(zhǔn)確度，提高推薦精度.

判定兩個(gè)學(xué)生是否具有相似度，既要考慮學(xué)生的專(zhuān)業(yè)特征和對(duì)某課程的評(píng)分，還要兼顧所選課程的方向性.可以采用修正的相似度公式進(jìn)行計(jì)算，通過(guò)某學(xué)生的某課程評(píng)分減去該學(xué)生的所有課程評(píng)分平均值來(lái)改進(jìn)相似度的缺陷，提高計(jì)算結(jié)果的精確度.修正的學(xué)生i和j對(duì)課程c的評(píng)分相似度為

(4)

(2)算法過(guò)程.

算法:將N門(mén)課程推薦給目標(biāo)學(xué)生.

輸入數(shù)據(jù):構(gòu)造m學(xué)生-n課程評(píng)分表R.

輸出數(shù)據(jù)：利用Top-N算法給出推薦課程列表.

Step 1 利用(4)式計(jì)算修正的學(xué)生i和j對(duì)課程c的評(píng)分相似度.

Step 2 計(jì)算目標(biāo)學(xué)生i對(duì)未評(píng)分課程d的預(yù)估評(píng)分，

(5)

Step 3 用預(yù)估評(píng)分構(gòu)造預(yù)估集，并按分值進(jìn)行排序.

Step 4 輸出分值較大的N門(mén)課程，即推薦課程.

圖3 基于項(xiàng)目-用戶(hù)加權(quán)的推薦過(guò)程Fig. 3 Recommendation Procedures Based on Item Weighting and User Weighting

3.2.3 基于項(xiàng)目-用戶(hù)加權(quán)協(xié)同過(guò)濾(IW-UW-CF)算法的應(yīng)用 U-CF算法存在可擴(kuò)展性、稀疏性、冷啟動(dòng)等問(wèn)題，因此在它的基礎(chǔ)上，采用基于項(xiàng)目-用戶(hù)加權(quán)來(lái)實(shí)現(xiàn)智能選課功能，以提高課程推薦精度.基于項(xiàng)目-用戶(hù)加權(quán)的推薦過(guò)程如圖3所示.

(1)基本思想.同時(shí)考慮課程加權(quán)和學(xué)生加權(quán)，分別利用基于項(xiàng)目加權(quán)的用戶(hù)相似度和基于用戶(hù)加權(quán)的用戶(hù)預(yù)估評(píng)分來(lái)提高課程推薦精度.[17-18]

(2)算法過(guò)程.

輸入數(shù)據(jù)：目標(biāo)學(xué)生i、學(xué)生-課程評(píng)分表R,課程相似度表H,近鄰數(shù)k.

輸出數(shù)據(jù)：目標(biāo)學(xué)生i的Top-N推薦集.

Step 1 從學(xué)生-課程評(píng)分表R里找出系統(tǒng)中所有學(xué)生、課程和目標(biāo)學(xué)生i的已評(píng)分課程，分別記為Um,In,Ii.

Step 2 根據(jù)不同課程的權(quán)重作用，利用(3)式獲得學(xué)生加權(quán)相似度，將加權(quán)相似度最高的前k個(gè)學(xué)生選為目標(biāo)學(xué)生i的最近鄰集，Ni={j1,j2,…,jk}.

Step 3 對(duì)于目標(biāo)學(xué)生i的任一未評(píng)分課程,根據(jù)(5)式計(jì)算預(yù)估評(píng)分.

Step 4 將預(yù)估評(píng)分較大的N門(mén)課程作為目標(biāo)學(xué)生l的推薦集.

4 實(shí)驗(yàn)結(jié)果與討論

4.1 實(shí)驗(yàn)信息來(lái)源

以某大學(xué)教務(wù)系統(tǒng)oracle數(shù)據(jù)庫(kù)中的記錄為實(shí)驗(yàn)數(shù)據(jù)來(lái)源，提取的信息包含教務(wù)管理系統(tǒng)近4年5 000多條課程的歷史信息、2萬(wàn)多條學(xué)生訪(fǎng)問(wèn)網(wǎng)站課程的信息和1 000多份學(xué)生回訪(fǎng)表.對(duì)獲取的原始數(shù)據(jù)進(jìn)行整理，保留有用數(shù)據(jù)，刪除無(wú)關(guān)記錄，以提高算法的效率和準(zhǔn)確率.

4.2 U-CF與UW-CF算法的比較

圖4 U-CF和UW-CF算法的召回率Fig. 4 Recall Rates of U-CF and UW-CF Algorithms

根據(jù)召回率評(píng)估方法，比較U-CF和UW-CF算法在課程推薦中的有效性.利用U-CF算法尋找目標(biāo)學(xué)生最近鄰，預(yù)估目標(biāo)學(xué)生對(duì)課程的評(píng)分，找出預(yù)估評(píng)分大于4的課程推送給目標(biāo)學(xué)生.將近鄰的個(gè)數(shù)k依次取10，20，30，40，50，60，70，80，90，100，計(jì)算不同k值下的召回率，結(jié)果如圖4所示.從圖4可以看出，k值不同，召回率也不同.在k<40時(shí)，U-CF算法的召回率比UW-CF算法的高；在k=40時(shí)，UW-CF算法的召回率比U-CF算法的高；k繼續(xù)增大，UW-CF算法的召回率增大的速度大于U-CF算法的.

4.3 UW-CF與IW-UW-CF算法的比較

通過(guò)對(duì)比UW-CF和IW-UW-CF算法的絕對(duì)偏差(MAE)，來(lái)驗(yàn)證同時(shí)考慮項(xiàng)目加權(quán)和用戶(hù)加權(quán)的有效性.對(duì)于UW-CF算法，利用訓(xùn)練集數(shù)據(jù)構(gòu)建學(xué)生-課程評(píng)分二維表，計(jì)算學(xué)生對(duì)課程的評(píng)分相似度，并考慮不同學(xué)生的權(quán)重對(duì)預(yù)估評(píng)分的影響.IW-UW-CF算法同時(shí)考慮基于項(xiàng)目-用戶(hù)加權(quán).更新訓(xùn)練集中1/4的數(shù)據(jù)，重新構(gòu)建評(píng)分表，對(duì)其進(jìn)行測(cè)試.對(duì)比UW-CF和IW-UW-CF算法的MAE，結(jié)果如圖5所示.從圖5可以看出，采用IW-UW-CF算法后，推薦課程的準(zhǔn)確率顯著提高，表明項(xiàng)目和用戶(hù)同時(shí)加權(quán)的推薦算法可以提高推薦精度.

為更充分地展示這個(gè)結(jié)果，增加s門(mén)課程，對(duì)比UW-CF和IW-UW-CF算法的根均方差(RMSE)，結(jié)果如圖6所示.從圖6可以看出：當(dāng)s增大時(shí)，UW-CF算法的RMSE變化緩慢，說(shuō)明推薦精度變化不大；IW-UW-CF算法的RSME隨著k值的增加迅速變小，說(shuō)明推薦精度增高.這進(jìn)一步驗(yàn)證了IW-UW-CF算法比UW-CF算法的推薦結(jié)果更加準(zhǔn)確.

圖5 UW-CF和IW-UW-CF算法的MAEFig. 5 MAE of UW-CF and IW-UW-CF Algorithms

圖6 UW-CF和IW-UW-CF算法的RMSEFig. 6 RMSE of UW-CF and IW-UW-CF Algorithms

5 結(jié)語(yǔ)

將CF算法應(yīng)用到高校選課系統(tǒng)中，比較U-CF和UW-CF算法發(fā)現(xiàn)，在一定的k值下UW-CF算法的召回率表現(xiàn)比U-CF算法的更好.為提高課程推薦精度，提出了基于項(xiàng)目和用戶(hù)同時(shí)加權(quán)的IW-UW-CF算法，并在 Top-N方式下，通過(guò)MAE和RSME驗(yàn)證了在一定的范圍內(nèi)，IW-UW-CF算法的推薦精度比UW-CF算法的更高.

[1] 弗朗西斯科·里奇.推薦系統(tǒng)技術(shù)、評(píng)估及高校算法[M].北京：機(jī)械工業(yè)出版社，2015(7)：1-2.

[2] 何佳知．基于內(nèi)容和協(xié)同過(guò)濾的混合算法在推薦系統(tǒng)中的應(yīng)用研究[D]．上海：東華大學(xué)，2016：3-4.

[3] 高繼勛，張黎爍．基于協(xié)同過(guò)濾算法的智能教學(xué)系統(tǒng)研究[J]．信陽(yáng)師范學(xué)院學(xué)報(bào),2013(10)：29-31.

[4] 牛溫佳，劉吉強(qiáng)，石 川.用戶(hù)網(wǎng)絡(luò)行為畫(huà)像[M].北京：中國(guó)電子工業(yè)出版社,2016:58-60.

[5] 羅麗霞.基于用戶(hù)協(xié)同過(guò)濾的圖書(shū)推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].新余學(xué)院學(xué)報(bào),2014,12(2):10-13.

[6] HENRY LIEBERMAN.Letizia:An Agent That Assists Web Browsing[C].Proceeding of the 14th International Joint Conference on Artifical Intelligence,Montréal Québec,Canada,Aug 20-25,1995.San Francisco,USA:Morgan Kaufmann Pubishers Inc.,1995.

[7] CHEN Yan,HARPER FRANKLIN MAXWELL,KONSTAN JOSEPH A,et al.Social Comparisons and Contributions to Online Communities:A Field Experiment on Movielens[J].American Economic Review,2010,100(4):1 358-1 398.

[8] 徐蘭芳，胡懷飛，桑子夏,等.基于灰色系統(tǒng)理論的信譽(yù)報(bào)告機(jī)制[J].軟件學(xué)報(bào)，2007，18(7):1 730-1 737.

[9] 郝立燕.協(xié)同過(guò)濾技術(shù)中若干問(wèn)題的研究[D].福州：華僑大學(xué)，2013.

[10] BREEZE J,HECKERMAN D,KADIE C.Empirical Analysis of Predictive Algorithms for Collaborative Filtering[C].Proceedings of th 14th Conference on Uncertainty in Artificial Intelligent.San Francisco CA:Morgan Kaufmann Publishers Inc.,1998:43-52.

[11] 吳步祺.電子商務(wù)中協(xié)同過(guò)濾推薦技術(shù)研究[D].南昌：南昌大學(xué)，2010.

[12] 孫小華.協(xié)同過(guò)濾系統(tǒng)的稀疏性和冷啟動(dòng)問(wèn)題研究[D].杭州：浙江大學(xué)，2005.

[13] SARWAR B,KARYPIS G,KONSTAN J,et al.Item-Based Collaborative Filtering Recommendation Algorithms[C]∥Proceedings of the 10th International conference on World Wide Web.ACM,2001:285-295.

[14] SU Xiaoyuan,KHOSHGOFTAAR T M.A Survey of Collaborative Filtering Techniques[J].Advances in Artificial Intelligence,Volume 2009(2009),Article ID 421425,19 Pages.DOI:10.1155/2009/421425.

[15] UNGAR L H,FOSTER D P.Clustering Methods of Collaborative Filtering[C].Workshop on Recommendation Systems at the Fifteenth National Conference on Artificial Intelligence.Menol Park:AAAI Press,1998:112-125.

[16] ZHANG Sheng,WANG Weihong,FORD JAMES,et al.Using Singular Value Decomposition Approximation for Collaborative Filtering[C]∥7th IEEE International Conference on E-Commerce Technology.Ankara:IEEE,2005:257-264.

[17] PRYOR M H.The Effects of Singular Value Decomposition on Collaborative Filtering[EG/OL].(1998-06-10).http:∥cs.dartmouth.edu/cms_file/SYS_techReport/211/TR98-338.pdf.

[18] SARWAR BADRUL M,KARYPIS GEORGE,KONSTAN JOSEPH A,et al.Application of Dimensionality Reduction in Recommender System-A Case Study[R].Boston,USA:Workshop Proceedings of the 6th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,2000.