融合章節(jié)信息的信息技術(shù)教育試題推薦算法

田 鈺, 張嘯晨,王華彬

(1.合肥市教育科學研究院 信息技術(shù)應(yīng)用研究中心，安徽 合肥 230071； 2.安徽大學 計算機科學與技術(shù)學院，安徽 合肥 230039)

隨著題庫規(guī)模的不斷增加，學生從海量試題中及時、準確地尋找到適合自身學習情況的試題越發(fā)困難.針對此種情況，云平臺利用了個性化試題推薦系統(tǒng)給學生推送適合的題目[1].個性化推薦技術(shù)近年來發(fā)展迅速，它在電子商務(wù)、社交網(wǎng)絡(luò)、風險評估和在線教育等行業(yè)展示了一定價值.

在教育個性化推薦領(lǐng)域，協(xié)同過濾(collaborative filtering，簡稱CF)技術(shù)不僅可以提高教學效果，還可以提高學生的學習自主性，使學生學習效率更高.該技術(shù)通過學習相似學生偏好特征從而得到目標學生的預測偏好.協(xié)同過濾技術(shù)中以記憶為基礎(chǔ)的協(xié)同過濾依賴于較為完整的用戶-項目評分矩陣完成預測[2].另一種以模型為基礎(chǔ)的協(xié)同過濾技術(shù)[3]，引入了隱因子的分解模型.

矩陣分解(matrix factorization，簡稱MF)是基于模型的協(xié)同過濾算法[4-5]，當今國內(nèi)外大型教育資源平臺都會使用MF算法為用戶提供個性化內(nèi)容[5].在該算法中，學生對教學資源的評分信息用學生-資源評分矩陣表示，使用機器學習的方法，從該學生-資源評分矩陣中分解出學生和資源的潛因子特征向量(隱藏因子)，再在潛因子特征空間(低維空間)上將學生和資源進行重表示，兩者的低維向量內(nèi)積代表了他們之間的關(guān)聯(lián)性[6].非負矩陣分解推薦(nonnegative matrix factorization，簡稱NMF)被用來對非負矩陣進行多維分析，它與MF算法區(qū)別在于：NMF將學生-資源評分矩陣分解為兩個潛因子矩陣相乘，評分矩陣里的每一項都不能為負數(shù)[7].奇異值分解算法在NMF的基礎(chǔ)上，用奇異值涵蓋了數(shù)據(jù)集的特征值，并且依據(jù)特征值的重要程度排序，忽略掉排名靠后的特征向量可以實現(xiàn)數(shù)據(jù)的降維[8-9].但奇異值分解(singular value decomposition，簡稱SVD)算法受到系統(tǒng)數(shù)據(jù)高稀疏性影響，容易造成過擬合，影響到推薦精度降低[10].而后SVD方法被Simon Funk改進，縮減了分解因子矩陣的個數(shù)，稱之為Funk-SVD[11].LFM(latent factor model)潛因子模型在KDDCup[12]和Netflix[13]比賽中被證明比傳統(tǒng)方法推薦精度更高.然而一般的推薦場景以及教育推薦系統(tǒng)中的數(shù)據(jù)有著高度稀疏和分布不均勻等性質(zhì)，它們會降低算法在教育資源推薦中的精度[14].

為了消除數(shù)據(jù)稀疏和分布不均帶來的影響，科研工作者在模型中引入了隱式外部信息.類似于在線視頻教育網(wǎng)站上有學生的課程歷史瀏覽記錄和評論信息[15-16]，利用這些信息能推測出學生間社交關(guān)聯(lián)信息[17].該方法明顯提高了系統(tǒng)推薦準確性.

1 相關(guān)工作

在電子教學和在線學習等領(lǐng)域，推薦系統(tǒng)被視為解決教育資源信息過載問題的一個方案，它擔負著向?qū)W生推薦相關(guān)學習與教育資源的重要職責.論文通過所使用的技術(shù)的不同來對推薦系統(tǒng)進行分類，目前在在線教育和編程學習平臺使用較多的推薦技術(shù)有：協(xié)同過濾推薦、上下文感知推薦(context-aware recommender，簡稱CA)以及基于知識推薦(knowledge-based recommender，簡稱KB)[18]等.

協(xié)同過濾(CF)是依據(jù)有相似興趣的用戶的決策來提供項目推薦.一種隱含的推測是假設(shè)用戶在過往的選擇中有相似的興趣，他們在往后也將保持這種興趣的相似性.依據(jù)用戶評分、購買次數(shù)或者做題提交次數(shù)等，算法計算得到不同用戶興趣的相似度.基于此種規(guī)則，計算用戶或者項目之間的相似度是CF算法的核心原則.圖1展示了CF中的計算流程.

協(xié)同過濾可分成user-based和item-based兩種技術(shù)[19].user-based技術(shù)應(yīng)用在智慧教學云平臺中，首先根據(jù)Jaccard相似度計算出兩個學生之間學習進度或知識點掌握情況的相似度.設(shè)N(u)為學生u多次練習提交的試題集合，N(v)為學生v多次練習提交的試題集合，則Jaccard相似度為

(1)

根據(jù)Jaccard相似度計算得到學生做編程題的偏好相似度矩陣S，從該矩陣中找出目標學生u最相似的k個學生，用集合S(u,k) 表示.將S(u,k)中所有學生偏好多次練習的試題全部取出，并除去學生u的偏好多次練習的試題.對于每個候選試題i，學生u對它的偏好程度或?qū)W習愿望有下述表達式

(2)

其中：rvi表示學生v對試題i的學習愿望程度，這樣就能計算出所有學生對題庫里所有試題的偏好程度或?qū)W習愿望，將偏好學習程度排序后，取排名前列的試題推薦給學生便完成了user-based推薦過程.

item-based類似地會計算題庫中題目被學生偏好并被學習的相似度矩陣，得到題庫中所有試題被學生偏好學習的程度列表，再將試題推薦給列表中前列的學生.雖然協(xié)同過濾目前被廣泛使用，但是新用戶和新項目(新注冊學生和新添加試題)問題仍降低了它的推薦精度.由于最初缺乏對新學生或試題的評分或者提交次數(shù)而無法得出精確的預測，協(xié)同過濾的其他缺點包括可伸縮性和數(shù)據(jù)稀疏性敏感問題，表現(xiàn)在智慧教學云平臺中即某些試題只有很少的學生會去練習，所以這些試題幾乎沒有提交做題記錄，這導致它們幾乎難以被推薦系統(tǒng)預測評分.

在推薦系統(tǒng)中上下文指的是用來描述一個實體的信息[20].實體可以是與用戶和應(yīng)用程序之間的交互相關(guān)的人、對象或位置，它包括用戶、算法或應(yīng)用系統(tǒng)本身.在編程教育平臺或在線學習網(wǎng)站的語境中，學生語境信息包括知識水平和學習目標.當學生獲得更多的知識時，這些語境特征會隨著學生知識掌握水平的變化而變化.在線學習或電子教育平臺中的情境感知推薦系統(tǒng)分析學生所處的學習情境，向目標學生推薦學習和教育資源.在上下文感知場景中，預測評分的數(shù)學模型包含用戶、項目和上下文的功能，有

R:User×Item×Context→Prediction，

其中：User和Item為用戶集合和項目集合的域，Prediction為預測集合的域，Context為與推薦環(huán)節(jié)相關(guān)的上下文信息.上下文感知推薦系統(tǒng)中的評級矩陣樣例如表1所示.

表1 上下文感知推薦系統(tǒng)中評級矩陣樣例

將學生的語境信息融合到推薦算法過程中，能為具有相似興趣或?qū)W習意向的學生提供更精確的學習教育資源推薦.在推薦過程中融入學生學習過程中產(chǎn)生的上下文信息，這種混合上下文情境感知的推薦系統(tǒng)能為學生提供更加個性化的教育資源推薦.但是CA依賴上下文信息，當數(shù)據(jù)稀疏度較大或冷啟動等情況，預測精度不能保證.

KB是考慮用戶偏好的領(lǐng)域內(nèi)專業(yè)知識，利用其關(guān)聯(lián)性向用戶推薦項目[21].基于知識的推薦系統(tǒng)使用到了3類知識：用戶知識、項目知識、項目與用戶需求的匹配程度知識.依靠網(wǎng)絡(luò)學習的背景、基于知識的算法將學生和學習資源的知識匹配融合應(yīng)用于推薦過程.相較于協(xié)同過濾和基于內(nèi)容的推薦，基于知識的推薦系統(tǒng)避免了快速/冷啟動問題或評級稀疏問題，該算法的預測不依賴于評分記錄而是利用專業(yè)領(lǐng)域知識.因此，以知識為基礎(chǔ)的技術(shù)適合與其他推薦技術(shù)混合使用.

2 融合章節(jié)信息的矩陣分解算法

2.1 智慧教育平臺

信息技術(shù)智慧教學云平臺是一個能進行智慧編程教學的智能信息化系統(tǒng),它支持多種人工智能編程語言來進行智慧教學.目前系統(tǒng)可以對用戶提交的程序代碼進行編譯、鏈接、執(zhí)行，最后將執(zhí)行結(jié)果與數(shù)據(jù)庫中存儲的標準結(jié)果進行比較，從而判斷程序的正確與否.

2.2 學生-題目提交次數(shù)矩陣

將學生對題目提交次數(shù)的數(shù)據(jù)計入數(shù)據(jù)集，構(gòu)成學生-題目提交次數(shù)矩陣.矩陣由學生對每道題目的提交次數(shù)和未做過該題目的情況構(gòu)成，樣例如表2所示.

表2 學生-題目提交次數(shù)矩陣樣例

若要求出推薦給學生的題目列表，首先需要對如表2所示數(shù)據(jù)做矩陣補全，之后對任意一個學生預測出所有未做過題目的提交次數(shù)，并按提交次數(shù)從高到低的順序?qū)?yīng)的題目推薦給學生.傳統(tǒng)SVD在做較大的矩陣分解時效率較低，而FunkSVD縮減了分解因子矩陣的個數(shù)，提高了算法性能.

2.3 FunkSVD

FunkSVD方法在應(yīng)用于智慧教學云平臺時，將學生-題目提交次數(shù)矩陣分解為學生和題目兩個因子矩陣相乘.學生-題目提交次數(shù)矩陣中的真實提交次數(shù)與矩陣W(學生因子矩陣)和H(題目因子矩陣)的關(guān)系為

(3)

2.4 BiasSVD

BiasSVD[22]加入了平均評分μ、用戶偏差bu與項目偏差bi信息，預測模型為

(4)

其中：μ為數(shù)據(jù)集里全部記錄的評分算出的全局平均數(shù)，即訓練數(shù)據(jù)集的總體評分概況;bu為用戶偏置項，即用戶的評分偏好中和物品無關(guān)的因子;-bi為物品偏置項，即物品受到的評分中和用戶無關(guān)的因子.

2.5 SVD++

SVD++[23]算法在BiasSVD算法上做了增強，預測模型為

(5)

SVD++推薦系統(tǒng)中，除了用戶對于項目的顯式評分記錄之外，用戶的偏好可以從他的歷史瀏覽記錄、點贊、收藏等操作信息中間接反映.這些隱式反饋信息雖不代表該用戶與該項目發(fā)生了直接互動，但可以從中得出該用戶對這個項目產(chǎn)生了關(guān)注.然而編程試題推薦系統(tǒng)由于業(yè)務(wù)特征的原因很難得到上述的隱式反饋信息，所以作者利用編程知識章節(jié)信息替代傳統(tǒng)外部隱式反饋信息.

2.6 融合章節(jié)信息的SVD++

一般情況下，學生對于做錯或者不熟練的題目會多次提交，下次練習中同類型或相同章節(jié)題目會有更大概率被該學生選擇.這種現(xiàn)象與電子商務(wù)、音樂和電影等領(lǐng)域的用戶行為模式相類似.在電影、購物和音樂網(wǎng)站上，用戶對喜歡的項目打分較高，不喜歡的項目打分相對較低.類似地，在信息技術(shù)智慧教學云平臺上，學生對已經(jīng)掌握的題目編寫代碼很少會出現(xiàn)問題，一次提交即可通過編譯返回提示成功，這樣該學生在該道題目上提交次數(shù)會較少；對掌握不牢固的題目，編寫的代碼存在問題，提交會被返回提示出錯，需要學生數(shù)次修改并提交代碼后才能修復問題，這種情況下該學生在該道題目上提交次數(shù)便會較多.因此，對于掌握牢固的知識點，該知識點包含的題目提交次數(shù)便會較少；對于掌握不好的知識點，該知識點包含的題目提交次數(shù)便會較多.

綜上分析，編程試題推薦系統(tǒng)使用矩陣分解技術(shù)補全學生-題目提交次數(shù)矩陣，以此預測學生做題興趣.但編程試題推薦系統(tǒng)與電子商務(wù)推薦系統(tǒng)業(yè)務(wù)屬性存在差距，智慧教學云平臺難以獲得學生的社交信息或評價記錄，傳統(tǒng)外部信息不適用于編程試題推薦系統(tǒng).所以論文在先前介紹的矩陣分解技術(shù)基礎(chǔ)之上，為信息技術(shù)智慧教學云平臺提高試題推薦效果，在SVD++模型的基礎(chǔ)上，融合題目的章節(jié)信息，提出了融合試題章節(jié)信息的SVD++推薦算法.如圖2所示，左邊是推薦系統(tǒng)中經(jīng)典的學生-試題二部圖網(wǎng)絡(luò)，如果學生對某道試題有提交記錄，就會與該題目連接，學生掌握的潛在的知識點和試題章節(jié)信息矩陣顯示在圖2右側(cè).

圖2 編程平臺中學生掌握的潛在知識點和試題章節(jié)知識點的概念圖

一般情況下，學生做完當前章節(jié)習題后，會按固有章節(jié)順序去做下一章節(jié)題目，所以論文將章節(jié)映射的題號作為學生做題的隱式反饋加入模型偏置項中，得到預測評分公式

(6)

最小化目標函數(shù)為

(7)

其中：‖pu‖2和‖yj‖2分別為用戶偏差矩陣和章節(jié)隱式反饋矩陣所有元素的平方和.

bu+γ·(eui-λ·bu)→bu，

(8)

bi+γ·(eui-λ·bi)→bi，

(9)

qi+γ·(eui·pu-λ·qi)→qi，

(10)

(11)

(12)

其中：γ為步長，λ為正則化參數(shù).

2.7 引入編程語言隱含標簽

MF方法根據(jù)隱因子找到學生的做題偏好并在智慧編程平臺取得了良好的推薦效果，在實際場景中，還發(fā)現(xiàn)了一類隱因子，即學生和題目都有隱式的編程語言偏好.經(jīng)過智慧編程平臺的數(shù)據(jù)統(tǒng)計，在平時的訓練和考試中，掌握不同編程語言的學生面對編程題目，總是優(yōu)先會使用自己擅長的語言來解答，在選擇做題時會潛在偏好選擇適合自己強勢編程語言的題目.有些題目也會被認為用某種編程語言來解答最為快捷，此種經(jīng)驗會在學生之間交流從而給該編程題潛在標記了某一編程語言的標簽，即學生和題目都會有隱式的編程語言社團屬性[24].在編程教育平臺推薦系統(tǒng)MF方法里引入學生和題目的隱式編程語言標簽相似度，可以提高該系統(tǒng)的推薦試題精度.下面給出推薦評分引入編程語言相似性權(quán)重(code similarity weight，簡稱CSW)的計算公式為

(13)

(14)

其中：式(13)中SVD_chapteru,i是引入章節(jié)信息的SVD++算法預測出的推薦分數(shù)；式(14)中kui表示學生u的編程語言書簽向量和題目i的編程語言隱向量的余弦相似度(cosine similarity)，其中書簽向量表達為：學生或題目-平臺編程語言的1行7列矩陣，學生擅長的編程語言或題目最常被使用解題的編程語言為1，學生不熟悉的編程語言或題目幾乎不被使用解題的編程語言為0；μ是數(shù)據(jù)集樣本里的均值；σ是范圍內(nèi)的標準差.

2.8 算法步驟

算法.基于SVD++的融合章節(jié)信息的協(xié)同過濾算法

輸入: 學生-題目提交次數(shù)矩陣R

1. 通過R得到評分均值μ

2. 初始化偏置向量bu,bi.試題因子矩陣qi,用戶因子矩陣pu和因子個數(shù)k

3. for eachuinRdo: 按用戶id分組計算

4. for eachiinRdo:

5. while 誤差err沒有收斂 do

8. 按迭代公式(8)～(12)更新bu,bi,qi,pu,yj的值

9. end while

10. 根據(jù)公式(2)～(6)得到Kui,即是學生u的編程語言書簽向量和題目i的編程語言隱向量的余弦相似度

12. end for

13. end for

3 實驗及結(jié)果分析

運行該次實驗的計算機配置CPU為Intel Core-i3-8100-3.60GHz，內(nèi)存大小為8G，搭載的操作系統(tǒng)為Windows10-64位.實驗環(huán)境為：Python-3.7.1版本，使用的工具庫包括：tensorflow-1.14.0，pandas-0.23.4，numpy-1.16.3.論文的實驗數(shù)據(jù)來自信息技術(shù)智慧教學云平臺數(shù)據(jù)庫，從中抽取出了學生平時練習和多場競賽考試的代碼提交數(shù)據(jù).該次實驗調(diào)出了1 664個學生針對521道題目的共計24 556條做題記錄.原始數(shù)據(jù)中因?qū)W生個人原因或網(wǎng)絡(luò)延遲存在多次提交情況，導致提交次數(shù)字段數(shù)據(jù)明細偏離正常值范圍，該實驗對此做了規(guī)范化處理.設(shè)置提交次數(shù)范圍為 1～10，1表示這道題提交過1次，10類似指提交了10次，超過10次的置為10次.數(shù)據(jù)集還包含題庫信息，其中521道編程題目所屬的章(chapter)和節(jié)(node) 數(shù)據(jù)，題庫題目共含17章，每章均有1～4節(jié)不等.平均絕對偏差( mean absolute error，簡稱MAE) 和均方誤差(root mean squared error,簡稱RMSE)作為論文衡量算法推薦精度的指標工具.MAE計算預測的學生編程試題提交次數(shù)與真實的學生提交次數(shù)的平均誤差，通過誤差大小衡量算法的推薦精度.MAE，RMSE的公式為

正則化參數(shù)和因子個數(shù)k是融合章節(jié)信息的SVD++算法的重要參數(shù)，對智慧教學云平臺試題推薦精度有較大的影響.k值對MAE和RMSE值的影響如圖3，4所示.從圖3，4可以看出，在因子數(shù)等于15時，該模型效果最好.

圖3 k值對MAE值影響 圖4 k值對RMSE值影響

參數(shù)λ表示學生偏置項、試題偏置項和章節(jié)隱式反饋對編程平臺推薦算法結(jié)果的作用.當λ設(shè)置為 0 時，該矩陣分解算法不考慮學生偏置項、編程試題偏置項和試題章節(jié)信息的反饋，只計算了學生和編程題的提交做題次數(shù)，如圖5，6所示.

圖5 λ值對MAE值影響 圖6 λ值對RMSE值影響

由實驗結(jié)果可知，當λ取0.015、步長γ取0.007而其他參數(shù)固定時，算法的MAE和RMSE值均取得了較低值.

論文分別在傳統(tǒng)BiasSVD方法、傳統(tǒng)基于相似性的協(xié)同過濾算法和融合了章節(jié)信息的SVD++算法上進行了實驗，實驗結(jié)果如表4所示.

表4 對比實驗結(jié)果

在測試集/訓練集分別為20%，30%和40%的比例下進行10次實驗取平均值.實驗先采用沒有融合任何外部信息的BiasSVD方法和傳統(tǒng)的基于相似性的協(xié)同過濾方法，得到不同測試集比例下的MAE和RMSE值;然后為驗證融合外部章節(jié)信息方法和引入編程語言相似性權(quán)重方法的有效性，采用消融實驗分別對傳統(tǒng)的BiasSVD方法引入編程語言相似性權(quán)重、BiasSVD方法融合外部章節(jié)信息以及對融合了外部章節(jié)信息的SVD++方法引入編程語言相似性權(quán)重.3個實驗分別獨立驗證SVD方法引入編程語言相似性權(quán)重、SVD方法融合外部編程章節(jié)信息以及這兩種方法同時應(yīng)用在編程教育推薦系統(tǒng)中的效果，如圖7，8所示.從表4和圖7，8中可以看出：(1)傳統(tǒng)BiasSVD方法在引入了編程語言相似性權(quán)重后得到的MAE和RMSE值均有降低；(2)融合了外部章節(jié)信息的SVD++方法比傳統(tǒng)的BiasSVD方法和基于相似性的協(xié)同過濾方法在MAE和RMSE值上有明顯降低；(3)在基于融合外部章節(jié)信息的SVD++方法基礎(chǔ)上引入編程語言相似性權(quán)重后，MAE和RMSE值進一步降低，證明了論文算法的有效性.

圖7 測試集比例對MAE的影響 圖8 測試集比例對RMSE的影響

4 結(jié)束語

通過研究云平臺的習題推薦系統(tǒng)算法調(diào)優(yōu)，提出了引入題目的章節(jié)知識點外部信息，融合到SVD++算法的正則項中.算法首先結(jié)合學生-題目提交次數(shù)數(shù)據(jù)建立LFM模型，進一步將章節(jié)信息融合到題目隱因子特征向量中，最后訓練模型預測提交次數(shù)，將預測值高的題目列表推薦給學生.實驗證明了融合編程章節(jié)知識點信息的SVD++推薦算法的合理性和可解釋性.編程題目間存在知識點的前后序關(guān)聯(lián)性，因此可以在后續(xù)工作中將知識圖譜引入到推薦系統(tǒng)中，提高題目的推薦精度和可解釋性.