羅文劼,肖梓良

(河北大學(xué) 網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院,河北 保定 071000)

1 引 言

在線編程(Online Judge,OJ)系統(tǒng)是一種在線學(xué)習(xí)平臺(tái),主要應(yīng)用于計(jì)算機(jī)科學(xué)教育中的編程實(shí)踐[1]和國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽等編程競(jìng)賽的輔助培訓(xùn)[2,3].通常用戶與OJ系統(tǒng)的交互順序如下:

1)用戶從OJ題庫(kù)中選擇要解答的題目.

2)用戶編寫題目的解答方案代碼并提交.

3)OJ將用戶的代碼編譯成可執(zhí)行文件,將輸出結(jié)果與標(biāo)準(zhǔn)答案進(jìn)行即時(shí)比較.

4)OJ自動(dòng)反饋該方案是否正確.如果不正確,則反饋編譯錯(cuò)誤、運(yùn)行超時(shí)與內(nèi)存超限等錯(cuò)誤提示,并允許用戶再次提交該題目的解答方案代碼.

隨著科技的發(fā)展,世界各國(guó)都意識(shí)到了編程和編程人才對(duì)于未來的重要性,過去幾年中OJ在世界范圍內(nèi)被廣泛使用,相關(guān)的信息量也隨之不斷增加,如北京大學(xué)OJ擁有60萬用戶與3000個(gè)題目,浙江大學(xué)OJ擁有16萬用戶與6000個(gè)題目.面對(duì)OJ系統(tǒng)中海量的題目資源引發(fā)的信息過載,用戶很難自主找到與當(dāng)前編程能力匹配的題目.當(dāng)用戶選擇了超出自身編程能力的題目時(shí),會(huì)產(chǎn)生強(qiáng)烈的沮喪感與挫折感,容易導(dǎo)致用戶放棄學(xué)習(xí)[4];而當(dāng)用戶選擇了過于容易的題目時(shí),雖然最終解答了題目,但是自身編程能力并沒有提升,浪費(fèi)了時(shí)間與精力.

推薦系統(tǒng)能夠精準(zhǔn)定位用戶興趣,提供最適合用戶偏好和需求的項(xiàng)目,解決信息過載問題,所以在實(shí)際應(yīng)用越來越多[5-9],也被應(yīng)用到OJ系統(tǒng)中,以增強(qiáng)用戶的學(xué)習(xí)興趣,提高用戶的編程能力.但受限于在線用戶的隱私問題,大部分推薦方法需要高質(zhì)量的交互數(shù)據(jù)計(jì)算用戶相似度與項(xiàng)目相似度以進(jìn)行推薦.雖然OJ系統(tǒng)擁有大量的題目與用戶資源,但缺乏指導(dǎo)與監(jiān)督,用戶學(xué)習(xí)方式變得盲目,用戶往往在隨機(jī)嘗試少量題目后便放棄學(xué)習(xí),這使得用戶與題目之間的交互數(shù)據(jù)非常稀疏.已有方法對(duì)數(shù)據(jù)稀疏問題的處理能力較差,在高稀疏度時(shí)已有方法計(jì)算的用戶相似度與項(xiàng)目相似度質(zhì)量較差,影響推薦效果.

為此本文提出一種融合知識(shí)點(diǎn)與圖卷積的OJ題目推薦算法LGCNR,以解決數(shù)據(jù)稀疏問題.首先通過潛在狄利克雷分布模型提取題目文本中的知識(shí)點(diǎn)特征,結(jié)合統(tǒng)計(jì)信息構(gòu)建題目相似度矩陣,提高題目相似度計(jì)算的質(zhì)量.同時(shí)將用戶的提交記錄轉(zhuǎn)換為用戶答題意愿度,以解釋用戶提交記錄與用戶偏好的關(guān)系.之后利用隱語義模型處理用戶答題意愿度,得到題目潛在特征.最后應(yīng)用圖卷積層融合題目相似度矩陣與題目潛在特征矩陣,約束題目潛在特征的表達(dá).并使用自注意力機(jī)制動(dòng)態(tài)分配特征權(quán)重,通過雙線性函數(shù)擬合答題意愿度.在一個(gè)真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,該方法可以有效地預(yù)測(cè)用戶答題意愿度,在高稀疏度下有較優(yōu)表現(xiàn).

2 相關(guān)工作

2.1 在線教育題目推薦

互聯(lián)網(wǎng)的普及和相關(guān)技術(shù)的發(fā)展帶來了海量的數(shù)據(jù)信息,在線教育進(jìn)入大數(shù)據(jù)時(shí)代,在給用戶帶來更多選擇的同時(shí),也帶來了信息過載問題.近年來許多研究人員開始關(guān)注如何解決在線教育中的題目推薦問題,主要有以下兩種思路.

基于用戶的答題記錄,Yera等人對(duì)用戶失敗的提交次數(shù)進(jìn)行降噪預(yù)處理,結(jié)合模糊數(shù)學(xué)將嘗試次數(shù)轉(zhuǎn)換為題目的解答難度,提高用戶相似度計(jì)算的準(zhǔn)確性,使用傳統(tǒng)的協(xié)同過濾算法進(jìn)行推薦[10].Pereira 等人考慮到用戶以往的做題記錄,建模為用戶的努力程度,結(jié)合協(xié)同過濾構(gòu)建推薦模塊[11].Vincent等人對(duì)降噪自編碼器進(jìn)行了改良,在訓(xùn)練時(shí)加入噪音數(shù)據(jù),通過堆疊多個(gè)降噪自編碼器處理用戶答題矩陣,加強(qiáng)了題目推薦的魯棒性[12].

基于用戶的學(xué)習(xí)規(guī)律,Prisco等人利用ELO模型為用戶推薦題目,通過匹配題目難度與用戶能力提高用戶參與度[13].Zhao等人觀察用戶學(xué)習(xí)軌跡,發(fā)現(xiàn)用戶主要以相同試卷或相同知識(shí)點(diǎn)的順序解答題目,因此利用雙模式馬爾科夫主題模型預(yù)測(cè)題目難度并推薦[14].Mascio等人為培養(yǎng)用戶的學(xué)習(xí)興趣,通過游戲化的頒發(fā)獎(jiǎng)?wù)路椒ㄟM(jìn)行題目推薦[15].

2.2 潛在狄利克雷分布模型

潛在狄利克雷分布模型(Latent Dirichlet Allocation,LDA)是一種文檔主題生成模型,常用于挖掘大規(guī)模文集中潛藏的主題信息.由于主題信息的相似度計(jì)算可以緩解數(shù)據(jù)稀疏問題,因此已經(jīng)被廣泛應(yīng)用于推薦系統(tǒng)中.

Krestel等人設(shè)計(jì)了基于LDA的項(xiàng)目主題推薦方法,以克服新項(xiàng)目的冷啟動(dòng)問題[16].Harvey等人使用LDA獲得的主題概率分布設(shè)計(jì)了三層主題模型,以便為用戶提供個(gè)性化的推薦[17].Zhou等人認(rèn)為高評(píng)分的相似主題項(xiàng)目更受歡迎,所以添加評(píng)分信息設(shè)計(jì)了用于協(xié)同過濾的評(píng)級(jí)LDA模型[18].Yu等人將用戶評(píng)論情感與對(duì)應(yīng)評(píng)分相結(jié)合,提出了一種基于主題和情感的擴(kuò)展隱因子模型[19].Zhao等人分析目標(biāo)用戶top-k相似用戶中主題出現(xiàn)的頻率,向目標(biāo)用戶推薦最相關(guān)的主題[20].Liang等人利用主題特征構(gòu)造評(píng)分矩陣,結(jié)合用戶的海明距離編碼,緩解了推薦系統(tǒng)的數(shù)據(jù)稀疏與冷啟動(dòng)問題[21].

2.3 圖卷積模型

卷積神經(jīng)網(wǎng)絡(luò)具有優(yōu)良的特征學(xué)習(xí)和表達(dá)能力,但是需要數(shù)據(jù)分布在規(guī)則空間中,難以應(yīng)用于不規(guī)則的圖結(jié)構(gòu)數(shù)據(jù).為此Kipf等人提出圖卷積模型(Graph Convolution Network,GCN),將卷積運(yùn)算進(jìn)行推廣,提取空間特征進(jìn)行機(jī)器學(xué)習(xí)[22].Hu等人分析課程之間的連貫性,利用GCN引入前置課程知識(shí)對(duì)目標(biāo)課程的重要程度,以預(yù)測(cè)學(xué)生在目標(biāo)課程的成績(jī)[23].Li等人利用GCN處理交互式題庫(kù)中學(xué)生與題目的關(guān)系,并在隱含層之間增加殘差連接解決過平滑問題,更好地預(yù)測(cè)了學(xué)生在題目上的表現(xiàn)[24].楊光澤等人利用GCN融合學(xué)生的成績(jī)與社交關(guān)系,挖掘了影響學(xué)生就業(yè)去向的關(guān)鍵因素[25].

2.4 注意力機(jī)制

近年來研究者借鑒人類視覺的信息選擇能力提出了注意力機(jī)制,以更好地學(xué)習(xí)特征的表達(dá).人類視覺通過快速掃描全局圖像以獲得需要重點(diǎn)關(guān)注的區(qū)域,向其分配更多的注意力資源,并抑制無用區(qū)域信息的表達(dá).注意力機(jī)制的本質(zhì)是對(duì)特征權(quán)重的分配,突出重要特征,降低資源消耗.楊明極等人利用注意力機(jī)制為用戶的歷史收聽音樂賦權(quán),結(jié)合循環(huán)神經(jīng)網(wǎng)絡(luò)更好地學(xué)習(xí)了用戶的偏好[26].Zhang等人利用用戶在大規(guī)模開放在線課程的訪問記錄為用戶推薦課程,通過注意力機(jī)制學(xué)習(xí)課程之間的關(guān)系,以捕獲用戶的全局偏好[27].Li等人利用注意力機(jī)制分別對(duì)學(xué)生的第1階段成績(jī)與第2階段成績(jī)賦權(quán),設(shè)計(jì)了一個(gè)基于雙路注意力機(jī)制的學(xué)生成績(jī)預(yù)測(cè)模型,并取得了較好的效果[28].

3 融合知識(shí)點(diǎn)與圖卷積的題目推薦算法

針對(duì)已有推薦算法在高稀疏度中表現(xiàn)較差的問題,本文提出了一種融合知識(shí)點(diǎn)與圖卷積的題目推薦算法LGCNR.算法整體研究框架如圖1所示,具體流程如下:

1)利用LDA模型提取題目文本中的知識(shí)點(diǎn)分布,結(jié)合題目解答情況的統(tǒng)計(jì)數(shù)據(jù),計(jì)算高質(zhì)量的題目相似度.

2)根據(jù)用戶答題的提交次數(shù)構(gòu)建用戶答題意愿度矩陣,并通過隱語義模型建模題目潛在特征與用戶編程能力.

3)通過GCN層融合題目相似度與題目潛在特征,結(jié)合自注意力機(jī)制挖掘題目特征的權(quán)重,使用雙線性函數(shù)擬合最終的答題意愿度.

圖1 LGCNR研究框架Fig.1 Research framework of LGCNR

LGCNR算法利用圖卷積模型與自注意力機(jī)制挖掘題目特征的表達(dá),使LDA模型和隱語義模型充分發(fā)揮了各自的優(yōu)勢(shì),提高了題目潛在特征的質(zhì)量,根據(jù)修正后的題目特征向量計(jì)算出的答題意愿度會(huì)更加準(zhǔn)確.

3.1 題目相似度矩陣

3.1.1 題目知識(shí)點(diǎn)相似度

OJ題目用于考察用戶編程知識(shí)的掌握情況,所以天然的具備知識(shí)點(diǎn)特征.本文借助LDA模型從題目中挖掘?qū)?yīng)的潛在知識(shí)點(diǎn)分布,利用潛在知識(shí)點(diǎn)計(jì)算題目的相似度,可以更客觀地反映題目之間的關(guān)系,緩解OJ系統(tǒng)中數(shù)據(jù)稀疏的問題.

傳統(tǒng)的TF-IDF方法判斷兩個(gè)文檔相似性是通過分析兩個(gè)文檔中共同分詞出現(xiàn)的頻率,這種方法沒有考慮到分詞背后的主題信息.LDA模型假設(shè)每個(gè)文檔都是多個(gè)主題的概率分布,每個(gè)主題都是多個(gè)分詞的概率分布,因此文檔-分詞概率矩陣可以分解為文檔-主題概率矩陣與主題-分詞概率矩陣.通過挖掘文檔與分詞的關(guān)系,LDA模型計(jì)算潛在主題的概率分布,模型如圖2所示.

圖2 LDA模型Fig.2 LDA model

圖2中k是主題編號(hào).Zn,l是文檔n中第l個(gè)分詞對(duì)應(yīng)的主題編號(hào),wn,l是文檔n中第l個(gè)分詞的編號(hào).θn與φk分別代表文檔n的主題分布和主題k的詞匯分布.α與β是狄利克雷分布先驗(yàn)參數(shù).

給定文檔n的情況下,wn,l由觀察可知,先驗(yàn)參數(shù)α、β選取默認(rèn)值,使用吉布斯采樣法學(xué)習(xí)LDA模型中的主題分布θn,流程如下:

1)給定主題總數(shù)K、α、β和分詞編號(hào)wn,l.

2)給每篇文檔的每個(gè)詞匯隨機(jī)分配主題編號(hào),初始化Zn,l.

3)利用吉布斯公式對(duì)每個(gè)詞匯進(jìn)行采樣,求出它對(duì)應(yīng)的主題編號(hào),并更新Zn,l.

4)重復(fù)3),直到吉布斯采樣收斂或達(dá)到迭代次數(shù).

5)輸出每篇文檔的主題分布θn.

首先對(duì)OJ題目文本進(jìn)行分詞與去停用詞處理,獲得題目集合N.將其與超參數(shù)α、β和知識(shí)點(diǎn)總數(shù)K輸入LDA模型,采用吉布斯采樣學(xué)習(xí)的方式進(jìn)行參數(shù)估計(jì),迭代后輸出N個(gè)題目在K個(gè)知識(shí)點(diǎn)上的概率分布Iφ,如式(1)所示:

(1)

在LDA模型中,題目可以看作知識(shí)點(diǎn)的集合,每個(gè)知識(shí)點(diǎn)都可以視為該題目的特征,因此將題目映射到知識(shí)點(diǎn)的特征向量空間中,可以使用余弦相似度計(jì)算Iφ中每個(gè)題目之間的知識(shí)點(diǎn)相似度.

設(shè)題目Nu與題目Nv對(duì)應(yīng)的知識(shí)點(diǎn)分布為矩陣Iφ中兩行,則Nu與Nv的知識(shí)點(diǎn)相似度ksim(u,v)計(jì)算如式(2)所示:

(2)

其中θu=[iu1,iu2…iuK],θv=[iv1,iv2…ivK],且0≤ksim(u,v)≤1.ksim(u,v)越大,題目Nu與Nv的知識(shí)點(diǎn)分布越接近,題目越相似,反之越不相似.

3.1.2 題目統(tǒng)計(jì)特征相似度

OJ題目一旦被提交到題庫(kù)中,系統(tǒng)就會(huì)自動(dòng)記錄用戶提交代碼后的反饋情況,并統(tǒng)計(jì)反饋情況的類型與數(shù)量.整理所有用戶的提交記錄后,題目的統(tǒng)計(jì)數(shù)據(jù)如表1所示.

表1 題目統(tǒng)計(jì)數(shù)據(jù)Table 1 Question statistics dataset

題目的統(tǒng)計(jì)數(shù)據(jù)對(duì)相似度具有重要影響,因此本文將統(tǒng)計(jì)數(shù)據(jù)引入題目的相似度計(jì)算.在眾多類型的反饋情況中,經(jīng)過數(shù)據(jù)統(tǒng)計(jì)與占比分析,本文選取3種數(shù)量最多也是最基本的反饋情況,并整理其余的答題情況,構(gòu)建題目的統(tǒng)計(jì)特征S=[ac,pac,ce,mf].

其中ac為答案正確,代表題目的客觀難度.pac為部分正確,映射了題目的考點(diǎn)設(shè)置.ce為編譯錯(cuò)誤,與代碼的細(xì)節(jié)處理相關(guān).mf為多種錯(cuò)誤,對(duì)反饋情況信息進(jìn)行補(bǔ)全.

類似地,使用余弦相似度計(jì)算題目Nu與Nv的統(tǒng)計(jì)相似度dsim(u,v),如式(3)所示:

(3)

dsim(u,v)越大,題目Nu與Nv的統(tǒng)計(jì)特征越相似,題目越相似,反之越不相似,且0≤dsim(u,v)≤1.

3.1.3 題目綜合相似度

在題目知識(shí)點(diǎn)相似度與題目統(tǒng)計(jì)相似度的基礎(chǔ)上,計(jì)算題目Nu與題目Nv的綜合相似度sim*(u,v),如式(4)所示:

sim*(u,v)=p·ksim(u,v)+(1-p)·dsim(u,v)

(4)

sim*(u,v)越接近1則題目越相似,反之越不相似.在使用sim*(u,v)進(jìn)行題目綜合相似度計(jì)算時(shí),知識(shí)點(diǎn)相似度與統(tǒng)計(jì)相似度的比例由相似度參數(shù)p調(diào)節(jié),p的取值范圍為[0,1].特別的,當(dāng)p=1時(shí),綜合相似度退化為知識(shí)點(diǎn)相似度,當(dāng)p=0時(shí),綜合相似度退化為統(tǒng)計(jì)特征相似度.

計(jì)算題目集N中每個(gè)題目之間的綜合相似度sim*,構(gòu)建題目相似度矩陣A.由計(jì)算可知相似度矩陣A對(duì)角線上的值始終為1,如式(5)所示:

(5)

3.2 基于隱語義模型的題目特征構(gòu)建

3.2.1 用戶答題意愿度矩陣

為了將用戶代碼提交記錄用于推薦,本文首先創(chuàng)建了用戶答題情況矩陣E以描述用戶的答題情況.用戶答題情況矩陣描述了用戶最終是否正確解答題目,其中第m行n列為用戶m解答題目n的情況,如果最終正確解答則為1,否則為0.用戶答題情況矩陣如圖3所示.

圖3 用戶答題情況矩陣Fig.3 User answer matrix

傳統(tǒng)的答題方式僅需要考慮用戶是否正確解答題目,但OJ系統(tǒng)允許用戶多次進(jìn)行解答,最終的答題情況隨之動(dòng)態(tài)變化,僅使用最終解答情況的用戶答題情況矩陣E難以描述用戶的能力與題目的難度是否匹配,因此本文利用用戶解答題目時(shí)的提交次數(shù)豐富矩陣信息.

具體來說,將用戶答題情況轉(zhuǎn)化為答題意愿度,即用戶愿意為正確解答題目而嘗試提交代碼的次數(shù).較多的提交次數(shù)代表用戶認(rèn)為自己可以通過努力正確解答題目,愿意付出更多的精力進(jìn)行嘗試.較少的提交次數(shù)代表題目對(duì)于用戶過于簡(jiǎn)單或困難,因此用戶僅進(jìn)行少次嘗試之后便結(jié)束解答.

為了衡量用戶提交次數(shù)在用戶群體中的水平,本文首先計(jì)算每個(gè)題目提交次數(shù)的平均值與標(biāo)準(zhǔn)差,如式(6)與式(7)所示:

(6)

(7)

其中,Sn為提交過題目n解答方案代碼的用戶集合,submn為用戶m解答題目n時(shí)的提交次數(shù),μn為題目n的平均提交次數(shù),σn為題目n提交次數(shù)的標(biāo)準(zhǔn)差.

根據(jù)以下分類將用戶的提交次數(shù)轉(zhuǎn)化為答題意愿度r:

1)用戶m從未解答過或錯(cuò)誤解答題目n,r=0.

2)用戶m正確解答題目n,且提交次數(shù)submn∈(0,μn-σn)時(shí),r=1.

3)用戶m正確解答題目n,且提交次數(shù)submn∈[μn-σn,μn+σn]時(shí),r=2.

4)用戶m正確解答題目n,且提交次數(shù)submn∈(μn+σn,∞)時(shí),r=3.

在以上4類轉(zhuǎn)換的基礎(chǔ)上用戶的答題情況矩陣E轉(zhuǎn)換為用戶答題意愿度矩陣RM×N.

3.2.2 題目特征構(gòu)建

隱語義模型[29]((Latent Factor Model,LFM)作為一種有效的特征映射方法,可以精確描述用戶興趣偏好和項(xiàng)目本身特性,因此在推薦系統(tǒng)中得到了廣泛應(yīng)用[30].本文通過LFM模型分解用戶答題意愿度矩陣RM×N,得到用戶編程能力矩陣UM×L與題目潛在特征矩陣VN×L.用戶編程能力矩陣表示M個(gè)用戶對(duì)L個(gè)編程屬性的掌握程度,題目特征矩陣為N個(gè)題目在L個(gè)編程屬性上的隸屬程度,即式(8):

(8)

隨機(jī)地對(duì)U、V賦予初始值,不斷迭代使得U和V的內(nèi)積預(yù)測(cè)值與真實(shí)值R的誤差達(dá)到最小,損失函數(shù)如式(9)所示:

(9)

3.3 融合知識(shí)點(diǎn)與圖卷積的題目推薦

3.3.1 圖卷積層

OJ系統(tǒng)中交互數(shù)據(jù)的稀疏度非常高,因此LFM模型分解獲得的題目潛在特征質(zhì)量較差.本文在3.1節(jié)中引入了題目之間的相似關(guān)系,嘗試?yán)孟嗨脐P(guān)系對(duì)題目的潛在特征進(jìn)行約束,進(jìn)而緩解OJ系統(tǒng)中的數(shù)據(jù)稀疏問題.這一思路的重點(diǎn)是為如何確認(rèn)目標(biāo)題目的相似題目,如果將目標(biāo)題目相似度計(jì)算中top-k的題目作為相似題目,會(huì)導(dǎo)致相似題目信息利用不足,或引入低相似度題目的噪音數(shù)據(jù),不利于特征的學(xué)習(xí).因此本文將高于全局平均相似度的題目視為相似題目,每個(gè)題目的相似題目數(shù)量不再相同,能夠更好地利用題目相似關(guān)系.

傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)(CNN)等常用網(wǎng)絡(luò)難以將數(shù)量不固定的相似題目數(shù)據(jù)嵌入規(guī)則的題目潛在特征數(shù)據(jù)中,而圖卷積(GCN)可以較好地解決這個(gè)問題.GCN通過圖結(jié)構(gòu)將相似結(jié)點(diǎn)的特征傳播到目標(biāo)結(jié)點(diǎn),通過挖掘結(jié)點(diǎn)之間的連接關(guān)系對(duì)結(jié)點(diǎn)特征進(jìn)行約束.

具體來說,給定題目相似圖G,包含圖中結(jié)點(diǎn)的特征與結(jié)點(diǎn)之間的連接關(guān)系.通過式(10)將題目相似度矩陣作為邊信息嵌入到包含題目潛在特征中,獲取題目的融合特征V′.

(10)

3.3.2 自注意力層

由于知識(shí)點(diǎn)重要性并不平等,存在側(cè)重性,因此本文使用自注意力機(jī)制[31]計(jì)算題目知識(shí)點(diǎn)特征的權(quán)重,突出影響用戶偏好的關(guān)鍵特征.不同于注意力機(jī)制,自注意力機(jī)制考慮題目特征之間的內(nèi)在聯(lián)系,所以更容易突出題目特征中的重要信息.因此在GCN層后添加一層自注意力層,對(duì)權(quán)重高的潛在特征給予更多的關(guān)注,而不重要的潛在特征則消耗更少的資源,以提高網(wǎng)絡(luò)的效率,同時(shí)得到更有價(jià)值的特征表示.

自注意力層的輸入為題目融合特征V′,首先進(jìn)行線性轉(zhuǎn)換,獲得查詢向量Qv、鍵向量Kv與值向量Vv,見式(11):

QV=WQV′∈dQ×N
KV=WKV′∈dK×N
VV=WVV′∈dV×N

(11)

其中WQ、WK、Wv為需要訓(xùn)練的參數(shù)矩陣,dQ、dK、dV分別為矩陣WQ、WK、WV的維度.

之后計(jì)算查詢向量中各個(gè)特征之間的關(guān)聯(lián)程度,即注意力分布score,如式(12)所示:

(12)

最后將注意力分布與題目融合特征相乘獲得自注意力層輸出的題目高階特征V″,如式(13)所示:

V″=softmax(score)×V′

(13)

3.3.3 答題意愿度預(yù)測(cè)

(14)

(15)

本文基于softmax函數(shù)計(jì)算了每個(gè)答題意愿度的概率,因此基于交叉熵構(gòu)建損失函數(shù),損失函數(shù)的計(jì)算公式如式(16)所示:

(16)

4 實(shí) 驗(yàn)

4.1 評(píng)測(cè)數(shù)據(jù)集

本文研究的是 OJ題目推薦算法,因此使用OJ系統(tǒng)作為數(shù)據(jù)集來源.浙江大學(xué)OJ系統(tǒng)ZOJ是國(guó)內(nèi)最早也最常用的OJ系統(tǒng)之一,擁有程序設(shè)計(jì)類實(shí)驗(yàn)輔助教學(xué)平臺(tái)(Programming Teaching Assistant,PTA)和計(jì)算機(jī)程序設(shè)計(jì)能力考試.

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental dataset

本文關(guān)注在線教育中的題目推薦問題,因此使用PTA平臺(tái)中的數(shù)據(jù).爬取某大學(xué)計(jì)算機(jī)學(xué)院2018級(jí)與2019級(jí)本科生的真實(shí)使用記錄,兩個(gè)年級(jí)的用戶整體編程能力相近,整理為實(shí)驗(yàn)數(shù)據(jù)集.實(shí)驗(yàn)數(shù)據(jù)集涵蓋457名用戶使用OJ系統(tǒng)的15208條提交記錄,部分原始提交記錄如表2所示.

4.2 數(shù)據(jù)預(yù)處理

4.2.1 題目文本處理

由于本文利用到題目的文本信息,因此實(shí)驗(yàn)前需要對(duì)每個(gè)題目的文本數(shù)據(jù)進(jìn)行以下預(yù)處理:

1)去除一些無意義的文本,如輸入樣例與輸出樣例.

2)將圖片形式的文字信息轉(zhuǎn)化為字符串格式.

3)根據(jù)空格進(jìn)行分詞.

4)去停用詞,刪除沒有意義的符號(hào).

5)保留函數(shù)、坐標(biāo)等具有特殊意義的分詞.

4.2.2 數(shù)據(jù)降噪

為減少噪音數(shù)據(jù)的影響,本文對(duì)異常的提交次數(shù)進(jìn)行處理.具體而言,如果用戶的提交次數(shù)submn?[μn-3σn,μn+3σn],則令submn=μn,避免過少的提交次數(shù)與過多的提交次數(shù)造成的噪音影響,節(jié)省資源以提高算法的效率.

4.3 評(píng)價(jià)標(biāo)準(zhǔn)

為衡量不同算法對(duì)OJ題目推薦結(jié)果的好壞,本文所有實(shí)驗(yàn)采用推薦算法常用的均方根誤差(Root Mean Square Error,RMSE)對(duì)預(yù)測(cè)結(jié)果進(jìn)行評(píng)估.RMSE表示預(yù)測(cè)值和真實(shí)值之間標(biāo)準(zhǔn)差的平均值,RMSE值越小預(yù)測(cè)效果越好,定義如式(17)所示:

(17)

4.4 算法參數(shù)確定

推薦算法中,相關(guān)參數(shù)的選取對(duì)推薦準(zhǔn)確度有較大影響,本節(jié)主要討論題目知識(shí)點(diǎn)數(shù)K和相似度參數(shù)p的選取.

4.4.1 題目知識(shí)點(diǎn)數(shù)

LDA模型輸出為知識(shí)點(diǎn)的概率分布,因此使用困惑度作為題目知識(shí)點(diǎn)數(shù)K的選取標(biāo)準(zhǔn).樣本的困惑度被定義為樣本概率分布的熵,是信息論中用來比較兩個(gè)概率分布性能好壞的指標(biāo).在LDA模型中,低困惑度的概率分布不確定性小,相比高困惑度的概率分布能更好地預(yù)測(cè)主題.困惑度的計(jì)算公式如式(18)所示,其中Ln表示文檔n的分詞數(shù).

(18)

圖4 知識(shí)點(diǎn)數(shù)Fig.4 Knowledge points number

本文使用困惑度作為評(píng)估指標(biāo),選取LDA模型中的K值.由于OJ題目涉及的知識(shí)點(diǎn)存在層次樹結(jié)構(gòu),樹的上層具有寬泛的知識(shí)點(diǎn)概念,樹的下層具有粒度較細(xì)的知識(shí)點(diǎn)概念,且同一道題目往往具有多個(gè)下層知識(shí)點(diǎn).過于細(xì)致的劃分不利于相似度的計(jì)算,因此本文考慮上層知識(shí)點(diǎn)數(shù)量作為L(zhǎng)DA模型的K值.根據(jù)經(jīng)驗(yàn)進(jìn)行范圍設(shè)置,選取知識(shí)點(diǎn)數(shù)K∈[10,30],并以1為步長(zhǎng)取值.隨機(jī)選擇70%的OJ題目為訓(xùn)練集,其余30%為測(cè)試集.在不同的主題數(shù)下,模型困惑度變化如圖5所示,實(shí)驗(yàn)數(shù)據(jù)集為題目數(shù)據(jù)集.

在圖4中,困惑度開始隨著K值增大而波動(dòng)下降,在K值為22時(shí)達(dá)到了最低,而后開始不斷上升.因此本文綜合實(shí)驗(yàn)結(jié)果與實(shí)際經(jīng)驗(yàn)選擇22作為L(zhǎng)DA模型的主題數(shù)K,以進(jìn)行后續(xù)的推薦效果實(shí)驗(yàn).

4.4.2 相似度參數(shù)p

在構(gòu)建題目相似度矩陣的過程中,本文通過引入閾值p調(diào)節(jié)不同特征的權(quán)重.當(dāng)p越大時(shí),算法更關(guān)注題目的知識(shí)點(diǎn)特征;當(dāng)p越小時(shí),算法更多關(guān)注題目的統(tǒng)計(jì)特征,不同p值下LGCNR答題意愿度預(yù)測(cè)結(jié)果如圖5所示.

圖5 相似度參數(shù)值Fig.5 Similarity parameter value

圖5顯示了在不同p值時(shí),評(píng)價(jià)指標(biāo)與p之間的變化關(guān)系.實(shí)驗(yàn)結(jié)果證明p值對(duì)預(yù)測(cè)準(zhǔn)確率有明顯影響,并且在p=0.6時(shí)預(yù)測(cè)效果最佳,因此選擇0.6作為相似度閾值.

4.5 實(shí)驗(yàn)對(duì)比與分析

本文提出的LGCNR算法是在傳統(tǒng)的推薦算法基礎(chǔ)上加入了應(yīng)對(duì)數(shù)據(jù)稀疏性的機(jī)制,為評(píng)估其有效性,將本文算法與以下方方法進(jìn)行對(duì)比:

LFM:模型將用戶項(xiàng)目的交互矩陣分解成兩個(gè)低秩的用戶潛在特征矩陣和項(xiàng)目潛在特征矩陣,通過學(xué)習(xí)使重構(gòu)評(píng)分逼近實(shí)際評(píng)分.

BiasSVD[32]:模型假設(shè)整個(gè)用戶項(xiàng)目交互矩陣中存在用戶固有屬性、項(xiàng)目固有屬性與全局固有屬性,在LFM的基礎(chǔ)上引入用戶評(píng)分均值、項(xiàng)目被評(píng)分偏置與全局評(píng)分偏置3個(gè)偏置因素.

GCMC[33]:模型將用戶項(xiàng)目評(píng)分矩陣視為二部圖,將每個(gè)等級(jí)的評(píng)分分解為一個(gè)子圖,在每一個(gè)子圖上分別進(jìn)行圖卷積操作,最后將其聚合為節(jié)點(diǎn)最終的特征.

此外還設(shè)計(jì)了變種算法CNNR進(jìn)行對(duì)比分析,CNNR使用固定數(shù)量確定目標(biāo)題目的相似題目,并使用CNN代替GCN進(jìn)行特征卷積.

隨機(jī)選擇70%用戶為訓(xùn)練集,其余30%用戶為測(cè)試集.所有實(shí)驗(yàn)均使用訓(xùn)練集調(diào)優(yōu)參數(shù),使用測(cè)試集計(jì)算評(píng)價(jià)指標(biāo),多次實(shí)驗(yàn)取RMSE平均值作為最終結(jié)果.并且隨機(jī)刪除用戶答題意愿度矩陣中部分?jǐn)?shù)據(jù),模擬不同稀疏度(答題意愿度矩陣中0值數(shù)據(jù)的占比)下各算法的表現(xiàn),實(shí)驗(yàn)結(jié)果如圖6所示.

由圖6可知,隨著交互數(shù)據(jù)的減少,各算法的RMSE值逐漸提高,但是本文提出的LGCNR算法在各個(gè)稀疏度上始終擁有較好表現(xiàn).從變化率的角度看,LGCNR也優(yōu)于基線方法,尤其在稀疏度0.90以后,LGCNR增長(zhǎng)更平緩,優(yōu)勢(shì)更加明顯.這是因?yàn)閭鹘y(tǒng)方法僅使用用戶與題目之間的交互數(shù)據(jù),

圖6 稀疏度對(duì)結(jié)果的影響Fig.6 Effect of sparsity on RMSE

在交互數(shù)據(jù)過少時(shí)會(huì)因?yàn)閿?shù)據(jù)稀疏題目導(dǎo)致推薦精度快速降低.引入了題目相似度信息的CNNR與LGCNR效果較好,但由于題目樣本存在知識(shí)點(diǎn)特征與統(tǒng)計(jì)特征不平衡現(xiàn)象,而CNN的卷積過程需要固定相似題目的數(shù)量,導(dǎo)致CNNR在高稀疏度時(shí)更關(guān)注統(tǒng)計(jì)特征的相似度,但實(shí)際過程中用戶往往按照同知識(shí)點(diǎn)的順序進(jìn)行學(xué)習(xí),因此CNNR推薦效果低于LGCNR.LGCNR通過引入圖卷積與自注意力機(jī)制學(xué)習(xí)題目的潛在特征,相似度信息的利用方式更加合理,使得算法在數(shù)據(jù)稀疏度不斷增大時(shí)仍然具有較好的預(yù)測(cè)效果.

5 結(jié)論與展望

針對(duì)傳統(tǒng)推薦算法在高稀疏度的OJ題目推薦中效果較差的問題,本文挖掘題目信息緩解數(shù)據(jù)稀疏度問題.在傳統(tǒng)的矩陣分解推薦方法的基礎(chǔ)上,利用LDA模型挖掘題目的知識(shí)點(diǎn)信息,結(jié)合統(tǒng)計(jì)數(shù)據(jù)計(jì)算題目相似度.之后通過圖卷積進(jìn)行同質(zhì)結(jié)點(diǎn)間的特征傳遞,引入自注意力機(jī)制學(xué)習(xí)不同特征的權(quán)重,利用題目信息對(duì)潛在特征加以約束,緩解了數(shù)據(jù)稀疏問題,提高了推薦效果.

科技素養(yǎng)對(duì)于信息時(shí)代的重要性已經(jīng)不言而喻,本文通過推薦用戶更愿意嘗試的OJ題目,培養(yǎng)用戶在知識(shí)獲取過程中的學(xué)習(xí)樂趣,使得用戶更快地提高編程能力,進(jìn)而培養(yǎng)適應(yīng)未來社會(huì)需要的高素質(zhì)專業(yè)人才.在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本文提出的題目推薦算法具有較好的實(shí)用性.

后續(xù)的研究中將關(guān)注以下幾點(diǎn):本文僅計(jì)算了題目的相似度,后續(xù)研究中可以通過用戶的提交規(guī)律引入用戶相似度研究,進(jìn)一步緩解數(shù)據(jù)稀疏問題;可以針對(duì)不同OJ平臺(tái)引入更多的題目個(gè)性化特征,例如將題目的平均解答時(shí)間特征引入相似度計(jì)算;可以將結(jié)合圖卷積的題目推薦方法推廣到在線教育的其他任務(wù)中,如預(yù)測(cè)用戶是否會(huì)放棄在線學(xué)習(xí)等.