基于關(guān)聯(lián)規(guī)則與知識(shí)追蹤的編程題目推薦算法

向程冠，周東波，李 雷，王 英

(1.華中師范大學(xué) 教育大數(shù)據(jù)應(yīng)用技術(shù)國(guó)家工程實(shí)驗(yàn)室，湖北 武漢 430079；2.貴州師范學(xué)院 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，貴州 貴陽(yáng) 550018)

0 引 言

編程題目推薦是在線編程教學(xué)平臺(tái)不可缺少的智能導(dǎo)學(xué)功能之一，但目前大多數(shù)的在線編程教學(xué)平臺(tái)還停留在教師傳統(tǒng)課堂的網(wǎng)絡(luò)化時(shí)空延伸，缺乏智能，只是起到連接師生的作用，教師可以給學(xué)生安排編程練習(xí)或考試，但針對(duì)學(xué)生個(gè)性化差異的智能導(dǎo)學(xué)功能薄弱，缺少針對(duì)編程題目推薦的服務(wù)，并未很好發(fā)揮對(duì)學(xué)習(xí)者學(xué)習(xí)行為分析、學(xué)習(xí)意圖理解、學(xué)習(xí)狀態(tài)追蹤的作用，很難實(shí)現(xiàn)真正意義上的自適應(yīng)學(xué)習(xí)診斷與有效學(xué)習(xí)。因此，通過(guò)學(xué)習(xí)者做題情況推薦新的編程題目成為了編程教育智能導(dǎo)學(xué)的研究熱點(diǎn)之一。針對(duì)編程題目的特殊性與傳統(tǒng)推薦算法的缺點(diǎn)，提出一種基于關(guān)聯(lián)規(guī)則與知識(shí)追蹤的編程題目推薦算法。

1 相關(guān)工作

個(gè)性化題目推薦是智能教育領(lǐng)域中的重要問(wèn)題之一[1]。通過(guò)計(jì)算學(xué)生做題的歷史數(shù)據(jù)或用戶(hù)特征數(shù)據(jù)，給用戶(hù)推薦合乎規(guī)則的題目，以達(dá)到個(gè)性化的智能導(dǎo)學(xué)服務(wù)。題目推薦時(shí)大多采用基于協(xié)同過(guò)濾、基于認(rèn)知診斷與知識(shí)追蹤的推薦算法，然而基于協(xié)同過(guò)濾的算法忽略了題目之間的關(guān)聯(lián)信息，難以保證所推薦題目的解釋性與合理性。認(rèn)知診斷與知識(shí)追蹤的方法通過(guò)計(jì)算學(xué)生對(duì)知識(shí)點(diǎn)的掌握情況，預(yù)測(cè)待推薦題目的得分情況，但忽略了學(xué)生學(xué)習(xí)行為的共性，難以將隱藏的潛在屬性加入計(jì)算中，極易產(chǎn)生推薦誤差。

Raciel Yera等提出了一種基于問(wèn)題記憶的協(xié)同過(guò)濾算法[2]，用問(wèn)題矩陣記錄學(xué)生解決問(wèn)題時(shí)失敗的信息，從而為學(xué)生推薦編程題目，但未記錄問(wèn)題與知識(shí)點(diǎn)之間的關(guān)聯(lián)信息，不能判斷學(xué)習(xí)者是否已經(jīng)掌握知識(shí)點(diǎn)，反復(fù)推薦題目，浪費(fèi)了學(xué)習(xí)者寶貴的學(xué)習(xí)時(shí)間。馬驍睿等提出了一種結(jié)合深度知識(shí)追蹤的個(gè)性化習(xí)題推薦方法[3]，然而忽略了學(xué)習(xí)者學(xué)習(xí)行為過(guò)程，未考慮學(xué)習(xí)過(guò)程中推薦拔高題或鞏固題。Avi Segal等提出了一種將協(xié)同過(guò)濾與投票相結(jié)合的教學(xué)內(nèi)容個(gè)性化排序算法[4]，通過(guò)協(xié)同過(guò)濾算法計(jì)算相似學(xué)生在分?jǐn)?shù)、重試次數(shù)和解題時(shí)間方面的難度排名，從而預(yù)測(cè)學(xué)生的難度排名，給學(xué)生定制個(gè)性化的試題，但忽略了學(xué)生對(duì)知識(shí)點(diǎn)的掌握狀態(tài)。黃振亞提出了一種融合題目語(yǔ)義的知識(shí)追蹤框架[5]，挖掘題目?jī)?nèi)容的個(gè)性特征對(duì)學(xué)生學(xué)習(xí)行為過(guò)程的影響，并在英語(yǔ)與數(shù)學(xué)題目上作了驗(yàn)證，但對(duì)于編程題目卻很難從題目描述層面判斷題目間的關(guān)聯(lián)性。柏茂林通過(guò)計(jì)算能力水平相近的用戶(hù)組，將kNN協(xié)同過(guò)濾算法應(yīng)用于數(shù)學(xué)習(xí)題的個(gè)性化推薦中[6]。Surya Kant等提出了基于用戶(hù)和項(xiàng)目的協(xié)同過(guò)濾算法[7]，通過(guò)計(jì)算用戶(hù)相似度與項(xiàng)目相似度進(jìn)行推薦。萬(wàn)永權(quán)等提出反饋式個(gè)性化試題推薦方法[8]，從試題難度與認(rèn)知層次進(jìn)行標(biāo)準(zhǔn)化，構(gòu)造能力矩陣計(jì)算學(xué)生的能力進(jìn)行試題推薦，但只能應(yīng)用于客觀題，不能應(yīng)用于編程題目的推薦中。

知識(shí)追蹤通過(guò)歷史數(shù)據(jù)實(shí)時(shí)追蹤學(xué)習(xí)者對(duì)知識(shí)掌握狀態(tài)的變化，并預(yù)測(cè)學(xué)習(xí)者在未來(lái)學(xué)習(xí)中的表現(xiàn)，目前流行的知識(shí)追蹤方法主要有貝葉斯知識(shí)追蹤(BKT)模型與基于循環(huán)神經(jīng)網(wǎng)絡(luò)的深度知識(shí)追蹤(DKT)模型[9,10]，BKT只是將知識(shí)的掌握情況簡(jiǎn)單分為“掌握”與“未掌握”，忽略了學(xué)習(xí)過(guò)程，而DKT模型只能對(duì)學(xué)習(xí)者整個(gè)知識(shí)水平建模，不能反映學(xué)習(xí)者對(duì)各個(gè)知識(shí)點(diǎn)的掌握情況。Jiani Zhang等提出了基于記憶網(wǎng)絡(luò)的DKVMN模型[11]，用值矩陣表示學(xué)習(xí)者對(duì)各個(gè)知識(shí)點(diǎn)的掌握情況，并記錄題目與各知識(shí)點(diǎn)的依賴(lài)關(guān)系，從而追蹤學(xué)習(xí)者對(duì)各知識(shí)點(diǎn)的掌握情況，取得了良好的應(yīng)用效果，但忽略了學(xué)習(xí)者遺忘行為對(duì)知識(shí)點(diǎn)掌握的真實(shí)影響。Fangzhe Ai等在DKVMN模型的基礎(chǔ)上，加入了知識(shí)點(diǎn)的包含關(guān)系，改良了記憶矩陣[12]。李曉光等研究者提出了學(xué)習(xí)與遺忘融合的深度知識(shí)追蹤模型[13]，考慮了遺忘行為對(duì)知識(shí)追蹤影響，取得了較好的預(yù)測(cè)性能。

編程能力是計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的學(xué)生應(yīng)具備的關(guān)鍵能力之一，編程能力水平主要體現(xiàn)在完成編程題目的得分情況，學(xué)習(xí)者對(duì)于編程的學(xué)習(xí)過(guò)程不是簡(jiǎn)單的“對(duì)”與“錯(cuò)”，一道編程題往往要經(jīng)過(guò)多次提交與反復(fù)修改才能完成，見(jiàn)表1，學(xué)習(xí)者完成一道程序題嘗試提交了10次。因此，直接使用傳統(tǒng)的個(gè)性化題目推薦算法推薦編程題目是不合適的。同時(shí)，在推薦題目時(shí)不考慮學(xué)生對(duì)知識(shí)點(diǎn)的掌握狀態(tài)，不斷推薦題目將會(huì)浪費(fèi)學(xué)習(xí)者寶貴的時(shí)間。

表1 編程題目提交列表

針對(duì)現(xiàn)有算法在編程題目推薦中的缺點(diǎn)，結(jié)合編程題特點(diǎn)，考慮學(xué)習(xí)者的遺忘規(guī)律特征，本文提出了一種基于關(guān)聯(lián)規(guī)則與知識(shí)追蹤的編程題目推薦算法，將關(guān)聯(lián)規(guī)則挖掘與知識(shí)追蹤結(jié)合起來(lái)，按提交次數(shù)閾值，把同一學(xué)習(xí)者在同一知識(shí)點(diǎn)下同時(shí)做對(duì)或做錯(cuò)的題目組成交易記錄，從而挖掘出推薦規(guī)則，通過(guò)知識(shí)追蹤模型計(jì)算學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握情況，決定推薦鞏固題、拔高題或下一知識(shí)點(diǎn)的題目。

2 編程題目推薦算法

在編程題目推薦時(shí)，如果學(xué)習(xí)者已經(jīng)掌握了當(dāng)前知識(shí)點(diǎn)，就應(yīng)該推薦下一個(gè)知識(shí)點(diǎn)的題目，否則應(yīng)根據(jù)學(xué)習(xí)者的學(xué)習(xí)狀態(tài)，決定推薦鞏固題或者拔高題，以免浪費(fèi)學(xué)習(xí)時(shí)間，提高學(xué)習(xí)效率。因此，在設(shè)計(jì)推薦算法時(shí)需要解決兩個(gè)關(guān)鍵問(wèn)題：

(1)如何計(jì)算推薦鞏固題或拔高題？

(2)如何計(jì)算學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握情況？

對(duì)于問(wèn)題(1)，考慮將同一學(xué)習(xí)者在同一個(gè)知識(shí)點(diǎn)下，嘗試提交次數(shù)超過(guò)給定閾值時(shí)同時(shí)做錯(cuò)、同時(shí)做對(duì)的題目組成交易數(shù)據(jù)庫(kù)，根據(jù)知識(shí)點(diǎn)的順序關(guān)系，使用關(guān)聯(lián)規(guī)則算法挖掘出推薦規(guī)則，對(duì)于嘗試提交次數(shù)超過(guò)給定閾值的學(xué)習(xí)者推薦鞏固題，嘗試次數(shù)小于閾值時(shí)推薦拔高題，直到學(xué)習(xí)者掌握當(dāng)前知識(shí)點(diǎn)時(shí)，推薦下一知識(shí)點(diǎn)的題目，學(xué)習(xí)者不需要做完當(dāng)前知識(shí)點(diǎn)下的所有題目。

對(duì)于問(wèn)題(2)，考慮編程題目的特殊性與學(xué)習(xí)者遺忘規(guī)律，不能只是簡(jiǎn)單地從結(jié)果的“對(duì)”與“錯(cuò)”來(lái)評(píng)估學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握情況，雖然DKVMN模型可以通過(guò)記錄題目與各知識(shí)點(diǎn)的依賴(lài)關(guān)系，從而追蹤學(xué)習(xí)者對(duì)各知識(shí)點(diǎn)的掌握情況，然而沒(méi)有考慮到學(xué)習(xí)者的遺忘規(guī)律，也不適合編程題目的特殊性。在編程題目推薦算法時(shí)，先用DKVMN模型計(jì)算出學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握情況，再聯(lián)合使用判別分析模型，從編程題目的特殊性與學(xué)習(xí)者遺忘規(guī)律的維度評(píng)估學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握情況。

2.1 關(guān)聯(lián)規(guī)則挖掘

編程題目推薦時(shí)，可根據(jù)學(xué)生完成題目x的情況推薦題目集 {y1,y2,…,yn} (由n個(gè)鞏固題或拔高題組成的集合)，x與yi(1≤i≤n) 是二元的推薦關(guān)系，不考慮yi與yj之間是否有推薦關(guān)系 (i≠j, 1≤i≤n, 1≤j≤n)。 因此，用關(guān)聯(lián)規(guī)則挖掘題目之間滿(mǎn)足規(guī)則的二階大項(xiàng)集。

關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘中的研究熱點(diǎn)之一，用于挖掘數(shù)據(jù)間隱含的、未知的、有價(jià)值的關(guān)聯(lián)性[14]。Agrawal等提出了關(guān)聯(lián)規(guī)則挖掘的Apriori算法與AprioriTid算法[15]，使用上一次生成的大項(xiàng)集作為生成新候選項(xiàng)集的數(shù)據(jù)基礎(chǔ)，達(dá)到剪枝的目的，提高算法的執(zhí)行效率。其優(yōu)點(diǎn)是在首次計(jì)算大項(xiàng)集時(shí)掃描交易數(shù)據(jù)庫(kù)，以后每次用得到的候選項(xiàng)集構(gòu)造k階TID表，由k階TID表生成k+1階候選項(xiàng)集，除了在算法的開(kāi)始階段，所構(gòu)造的TID表都要比交易數(shù)據(jù)庫(kù)小，從而減少數(shù)據(jù)掃描次數(shù)。可其缺點(diǎn)是在開(kāi)始階段生成的TID表數(shù)據(jù)量有可能比交易數(shù)據(jù)庫(kù)大，存儲(chǔ)了k階TID表中下一次計(jì)算k+1階候選項(xiàng)集時(shí)不用的噪聲交易項(xiàng)，增加了掃描次數(shù)，造成了不必要的I/O操作。針對(duì)上述缺點(diǎn)，算法改進(jìn)的關(guān)鍵在于減少I(mǎi)/O操作與壓縮數(shù)據(jù)量[16]，因編程題目推薦時(shí)需要計(jì)算二階大項(xiàng)集，正處于AprioriTid算法的開(kāi)始階段，本文提出了一種AprioriTid的改進(jìn)算法，用于計(jì)算題目集的二階大項(xiàng)集。

性質(zhì)1 A、B為題目構(gòu)成的兩個(gè)交易集合，若A是B的子集，則A的范數(shù)不大于B的范數(shù)。反之，若A的范數(shù)大于B的范數(shù)，A必然不是B的子集。

性質(zhì)2 當(dāng)k>1時(shí)，k階候選項(xiàng)集一定是k-1階候選項(xiàng)集的子集，那么k階候選項(xiàng)集的元素一定取自于k-1階候選項(xiàng)集。

算法改進(jìn)的基本思想：由性質(zhì)1、性質(zhì)2可知，k+1階候選項(xiàng)集是k階候選項(xiàng)集的子集，它的生成依賴(lài)于k階TID表，在構(gòu)造k階TID表時(shí)，先計(jì)算k階大項(xiàng)集的冪集，再計(jì)算當(dāng)前交易項(xiàng)與k階大項(xiàng)集冪集的交集，如果交集的范數(shù)大于k，則將交集寫(xiě)入k階TID表中，可極大減少k階TID表的記錄數(shù)，故而減少計(jì)算k+1階候選項(xiàng)集時(shí)的數(shù)據(jù)掃描量與I/O操作，TID表記錄數(shù)不可能比交易數(shù)據(jù)庫(kù)大，可讓算法在執(zhí)行效率上得到明顯優(yōu)化。

用偽代碼描述改進(jìn)后的AprioriTid 算法如下：

(1)掃描題目構(gòu)成的交易數(shù)據(jù)庫(kù)D生成L[1];

(2)TID[1]=D;//1階TID表就是交易數(shù)據(jù)庫(kù)D

(3)for(k=2;L[k-1] !=null&&TID[k-1]!=null;k++){

(4)C[k]=Apriori_gen(L[k-1]);

(5) //使用Apriori_gen生成k階候選項(xiàng)集

(6) TID[k]=null;

(7) foreach(tin TID[k-1]){

(8) foreach(cinC[k])if(cint)c.Sup=c.Sup+1;

(9)L[k]=null;

(10) foreach(cinC[k])if(c.Sup≥Minsup)L[k]=L[k]+c;

(11)M=PowerSet(L[k]);//計(jì)算L[k]的冪集

(12)MT=t.item∩M;//交易項(xiàng)與候選項(xiàng)集冪集的交集

(13) if(MT!=null&&|MT|>k){//|MT|>k的項(xiàng)寫(xiě)入TID[k]

(14)p.id=t.id;

(15)p.item=MT;

(16) TID[k]=TID[k]+p;

(17) //加入k階TID表， 包含交易id與交易項(xiàng)

(18) }

(19) }

(20)}

表2給出了上述算法中所涉及的符號(hào)及描述。

表2 算法中的符號(hào)及描述

例：現(xiàn)有交易數(shù)據(jù)庫(kù)D，見(jiàn)表3，設(shè)最小支持?jǐn)?shù)為3，計(jì)算候選項(xiàng)集與大項(xiàng)集。

表3 交易數(shù)據(jù)庫(kù)D

C[1]={{A},{B},{C},{D},{E},{F},{G}}，L[1]={{A},{B},{C},{D},{E}}，L[1]的冪集M={A,B,C,D,E}， 求M與每個(gè)交易項(xiàng)的交集MT， |MT|>1時(shí)寫(xiě)入TID[1]中。由TID[1]生成C[2]={{A,B},{A,C},{A,D},{A,E},{B,C},{B,D},{B,E},{C,D},{C,E},{D,E}}，L[2]={{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},{D,E}}，L[2] 的冪集M={A,B,C,D,E}， 求M與每個(gè)交易項(xiàng)的交集MT， |MT|>2時(shí)寫(xiě)入TID[2]中。迭代算法直到TID為空時(shí)結(jié)束，算法過(guò)程如圖1所示。

圖1 改進(jìn)的AprioriTid算法過(guò)程

2.2 基于知識(shí)追蹤的知識(shí)點(diǎn)掌握分析模型

題目推薦的目的是為了讓學(xué)習(xí)者通過(guò)練習(xí)掌握知識(shí)，如果掌握了當(dāng)前知識(shí)點(diǎn)，就應(yīng)推薦下一知識(shí)點(diǎn)的題目。如果推薦時(shí)不考慮知識(shí)點(diǎn)掌握狀態(tài)，不斷為其推送當(dāng)前知識(shí)點(diǎn)的題目顯然是不合理的。對(duì)于編程題目，一道題目需要經(jīng)過(guò)若干次反復(fù)修改與提交才能完成，在計(jì)算學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握情況時(shí)需要滿(mǎn)足兩個(gè)方面的要求：一是能反應(yīng)學(xué)習(xí)者對(duì)當(dāng)前知識(shí)點(diǎn)的掌握情況，二是要考慮編程題需要經(jīng)過(guò)若干次反復(fù)修改與提交才能完成的特殊性，一般認(rèn)為學(xué)習(xí)者對(duì)一道編程題目嘗試提交次數(shù)越多，反應(yīng)出學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握越不好。因此，考慮在DKVMN模型的基礎(chǔ)上，加入學(xué)習(xí)者每次提交的狀態(tài)、所用知識(shí)點(diǎn)及提交次數(shù)、學(xué)習(xí)間隔時(shí)間、上次提交時(shí)所用知識(shí)點(diǎn)間隔時(shí)間等行為特征，運(yùn)用判別分析計(jì)算學(xué)習(xí)者學(xué)習(xí)行為對(duì)DKVMN模型預(yù)測(cè)結(jié)果的影響。

用GA表示掌握知識(shí)點(diǎn)，GB表示未掌握知識(shí)點(diǎn)。X(i) 表示學(xué)習(xí)者特征，X(1)表示嘗試提交次數(shù)，X(2)表示課程學(xué)習(xí)間隔時(shí)間，X(3)表示同一知識(shí)點(diǎn)學(xué)習(xí)間隔時(shí)間。X(2)、X(3)屬于學(xué)習(xí)者遺忘特征數(shù)據(jù)，根據(jù)德國(guó)心理學(xué)家艾賓浩斯遺忘曲線，學(xué)習(xí)間隔時(shí)間按間隔天數(shù)t分段計(jì)算，即

(1)

因此，學(xué)習(xí)者數(shù)據(jù)被分成兩組： {X1i(A),X2i(A),X3i(A)|i≤n1} 與 {X1j(B),X2j(B),X3j(B)|j≤n2}，n1+n2為學(xué)習(xí)者人數(shù)。

下面給出求判別指標(biāo)的過(guò)程[17]。

通過(guò)線性組合構(gòu)造一個(gè)判別函數(shù)，用于判斷學(xué)習(xí)者學(xué)習(xí)狀態(tài)，判別函數(shù)為

Y=L(X1,X2,X3)=C1X1+C2X2+C3X3

其中，C1、C2、C3為判別系數(shù)。

對(duì)于GA，n1個(gè)學(xué)生共有3*n1條數(shù)據(jù)，其觀測(cè)數(shù)據(jù)矩陣為

對(duì)于GB，n2個(gè)學(xué)生共有3*n2個(gè)數(shù)據(jù)，其觀測(cè)數(shù)據(jù)矩陣為

判別函數(shù)Y可最大限度區(qū)分GA與GB兩組狀態(tài)。GA有n1個(gè)樣本

i為1到n1的自然數(shù)。代入判別函數(shù)，可得

yi(A)=C1X1i(A)+C2X2i(A)+C3X3i(A)

GB有n2個(gè)樣本

i為1到n2的自然數(shù)。代入判別函數(shù)，可得

yi(B)=C1X1i(B)+C2X2i(B)+C3X3i(B)

在判斷學(xué)生是否掌握知識(shí)點(diǎn)時(shí)，將學(xué)習(xí)特征數(shù)據(jù) {X(1),X(2),X(3)} 代入判別函數(shù)Y，如果Y的值大于等于yAB時(shí)判別為未掌握該知識(shí)點(diǎn)，否則判別為已掌握該知識(shí)點(diǎn)。

2.3 編程題目推薦算法步驟

針對(duì)編程題目的特點(diǎn)，按學(xué)習(xí)者嘗試提交次數(shù)閾值把作答歷史記錄數(shù)據(jù)庫(kù)劃分為兩個(gè)庫(kù)，在提交次數(shù)小于等于閾值的數(shù)據(jù)庫(kù)中，將同一學(xué)習(xí)者在同一知識(shí)點(diǎn)下同時(shí)做對(duì)或做錯(cuò)的題目組成交易項(xiàng)，使用關(guān)聯(lián)規(guī)則挖掘出鞏固題推薦規(guī)則。解決一道編程題目需要多次修改與提交，熟練掌握了知識(shí)點(diǎn)的學(xué)生解決編程題目的提交次數(shù)相對(duì)較少，可用掌握了知識(shí)點(diǎn)的學(xué)生在完成編程作業(yè)時(shí)的平均提交次數(shù)作為劃分閾值。

同理，在提交次數(shù)大于閾值的數(shù)據(jù)庫(kù)中，將同一學(xué)習(xí)者在同一知識(shí)點(diǎn)下同時(shí)做對(duì)或做錯(cuò)的題目組成交易項(xiàng)，挖掘出拔高題目推薦規(guī)則。推薦時(shí)考慮題目提交次數(shù)與學(xué)習(xí)者遺忘特征，使用知識(shí)追蹤的DKVMN模型與判別分析模型計(jì)算學(xué)習(xí)者對(duì)當(dāng)前知識(shí)點(diǎn)的掌握狀態(tài)，決定推薦鞏固題、拔高題或下一知識(shí)點(diǎn)的題目。

本文算法具體步驟如下：

步驟1 根據(jù)學(xué)習(xí)者做題歷史記錄，使用改進(jìn)后的關(guān)聯(lián)規(guī)則挖掘算法生成推薦規(guī)則。

步驟2 生成DKVMN模型。

步驟3 生成各知識(shí)點(diǎn)的判別函數(shù)Y與yAB。

步驟4 輸入學(xué)生做題記錄，由DKVMN模型評(píng)估學(xué)生是否通過(guò)當(dāng)前知識(shí)點(diǎn)，未通過(guò)執(zhí)行步驟6，否則執(zhí)行步驟5。

步驟5 輸入學(xué)生學(xué)習(xí)特征數(shù)據(jù)：題目提交次數(shù)、同一知識(shí)點(diǎn)學(xué)習(xí)間隔時(shí)間、課程學(xué)習(xí)間隔時(shí)間，并代入與判別函數(shù)Y，如果函數(shù)值大于等于yAB執(zhí)行步驟6，否則執(zhí)行步驟7。

步驟6 嘗試提交次數(shù)超過(guò)給定閾值時(shí)推薦鞏固題，嘗試次數(shù)小于閾值時(shí)，推薦拔高題，執(zhí)行步驟4。

步驟7 推薦下一知識(shí)點(diǎn)的題目。

3 實(shí)驗(yàn)評(píng)估

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證本文提出的編程題目推薦算法的可行性與有效性，采用某高校在線編程教學(xué)平臺(tái)的實(shí)際生產(chǎn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，以C程序設(shè)計(jì)課程為對(duì)象，經(jīng)過(guò)專(zhuān)家標(biāo)注的知識(shí)點(diǎn)共124個(gè)，學(xué)生754人，程序提交1 358 973次，編程題目6230道。

算法實(shí)現(xiàn)采用Python語(yǔ)言編寫(xiě)，運(yùn)行的硬件環(huán)境為Intel(R) Core(TM)i7-8550U CPU @1.80 GHz(8 CPUs)，16 G內(nèi)存，操作系統(tǒng)為CentOS6。

3.2 評(píng)測(cè)指標(biāo)選擇

關(guān)聯(lián)規(guī)則的改進(jìn)算法評(píng)估從算法效率與精準(zhǔn)性2個(gè)方面進(jìn)行考量，算法效率從時(shí)間復(fù)雜度方面考量，精準(zhǔn)性反映算法的可靠程度與可行性，它們是推薦算法可靠可行的基礎(chǔ)保障。

題目推薦算法評(píng)價(jià)從題目推薦的覆蓋率(Coverage)和準(zhǔn)確率 (Precision)2個(gè)方面進(jìn)行考量，覆蓋率主要用于觀察算法推薦的題目集合Prc與實(shí)際可推薦的題目集合Preal交集中題目數(shù)量占實(shí)際可推薦的題目比率，計(jì)算公式如下

(2)

準(zhǔn)確率主要用于觀察題目推薦算法的正確性與可行性，其計(jì)算方式為所推薦的準(zhǔn)確題目所占推薦題目總數(shù)的百分比，值越大表示推薦算法的正確性越高，計(jì)算公式如下

(3)

3.3 實(shí)驗(yàn)結(jié)果與分析

3.3.1 改進(jìn)的AprioriTid算法分析

算法效率分析：選取最小支持?jǐn)?shù)為50，從1 358 973條提交記錄中隨機(jī)選擇0.5 w、1 w、1.5 w、2 w、2.5 w、3 w、3.5 w和4 w進(jìn)行對(duì)比測(cè)試，運(yùn)行結(jié)果如圖2所示。另外選取數(shù)據(jù)量為4.5 w，最小支持?jǐn)?shù)分別為60、80、100、120、140、160、180和200進(jìn)行對(duì)比測(cè)試，運(yùn)行結(jié)果如圖3所示。

圖2 最小支持?jǐn)?shù)為50時(shí)兩種算法的運(yùn)行時(shí)間

圖3 隨最小支持?jǐn)?shù)增大時(shí)執(zhí)行效率比較

從圖2、圖3中可以看出，在最小支持?jǐn)?shù)為50的情況下，改進(jìn)后的AprioriTid算法比AprioriTid算法在時(shí)間性能上平均提升了1826 MS，當(dāng)數(shù)據(jù)量增加到4 W時(shí)，改進(jìn)后比改進(jìn)前少用了2982 MS。在數(shù)據(jù)量不變的情況下，支持?jǐn)?shù)由60增加到120時(shí)，改進(jìn)后的AprioriTid算法在時(shí)間性能上平均提升了871 MS。

算法精準(zhǔn)性分析：分別設(shè)置支持?jǐn)?shù)為50、60、80、100、120、140、160、180和200，從1 358 973條提交記錄中隨機(jī)選擇了10組數(shù)據(jù)對(duì)算法的準(zhǔn)確率進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)量分別為2000、4000、6000、8000、10 000、12 000、14 000、16 000、18 000和20 000，用改進(jìn)前后的AprioriTid算法分別生成大項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，改進(jìn)前后算法生成的大項(xiàng)集是一致的，究其原因主要在于k階TID表是構(gòu)造k+1階候選項(xiàng)集的數(shù)據(jù)基礎(chǔ)，計(jì)算k階TID表時(shí)，先計(jì)算k階大項(xiàng)集的冪集，再計(jì)算出當(dāng)前交易項(xiàng)與k階大項(xiàng)集冪集的交集，如果交集的元素個(gè)數(shù)小于等于k，便不可能產(chǎn)生k+1階候選項(xiàng)集，并且k+1階候選項(xiàng)集只能產(chǎn)生于k階大項(xiàng)集中，通過(guò)計(jì)算交集可對(duì)不在k階大項(xiàng)集中元素進(jìn)行剪枝，并不影響計(jì)算k+1階候選項(xiàng)集，故改進(jìn)后的算法不會(huì)損耗原有算法的精準(zhǔn)性。

3.3.2 編程題目推薦算法分析

在實(shí)驗(yàn)數(shù)據(jù)集上，設(shè)置題目提交嘗試次數(shù)閾值為5，將實(shí)驗(yàn)數(shù)據(jù)集分為鞏固題數(shù)據(jù)集(提交嘗試次數(shù)小于等于5，共537 681條數(shù)據(jù))與拔高題數(shù)據(jù)集(提交嘗試次數(shù)大于5，共821 292條數(shù)據(jù))。選取400名學(xué)生的期末考試數(shù)據(jù)，將考試中每個(gè)知識(shí)點(diǎn)的得分率超過(guò)0.8的學(xué)生劃分到GA組，其他學(xué)生劃分到GB組，統(tǒng)計(jì)學(xué)生平時(shí)練習(xí)的程序提交次數(shù)、知識(shí)點(diǎn)學(xué)習(xí)間隔時(shí)間與課程學(xué)習(xí)間隔時(shí)間3項(xiàng)學(xué)習(xí)者特征數(shù)據(jù)，生成各知識(shí)點(diǎn)的判別指標(biāo)。設(shè)置關(guān)聯(lián)規(guī)則挖掘的支持?jǐn)?shù)為200，最多推薦題目數(shù)為20，在鞏固題數(shù)據(jù)集與拔高題數(shù)據(jù)集上分別設(shè)置訓(xùn)練集/實(shí)驗(yàn)數(shù)據(jù)集為60%、70%、80%與90%的情況下，將本文算法與基于用戶(hù)的協(xié)同過(guò)濾算法(UserCF)、kNN協(xié)同過(guò)濾算法[6]、BiUCF[7]進(jìn)行10次對(duì)比實(shí)驗(yàn)取平均值，實(shí)驗(yàn)結(jié)果見(jiàn)表4、表5。

表4 鞏固題推薦的覆蓋率與準(zhǔn)確率比較

在覆蓋率與準(zhǔn)確率2個(gè)指標(biāo)上，本文提出的推薦算法在推薦鞏固題與拔高題方面均優(yōu)于其它3種推薦算法，原因在于本文算法考慮了編程題目的特征、學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握狀態(tài)以及學(xué)習(xí)者遺忘特征。

4 結(jié)束語(yǔ)

本文提出了一種基于關(guān)聯(lián)規(guī)則與知識(shí)追蹤的編程題目推薦算法，算法根據(jù)編程題目的特點(diǎn)，使用關(guān)聯(lián)規(guī)則挖掘出同一知識(shí)點(diǎn)下同一學(xué)習(xí)者在嘗試提交一定次數(shù)后同時(shí)“做對(duì)”與“做錯(cuò)”的題目推薦規(guī)則，通過(guò)分析學(xué)習(xí)者的遺忘特征，使用知識(shí)追蹤模型與判別分析模型計(jì)算學(xué)習(xí)者對(duì)知識(shí)點(diǎn)的掌握狀態(tài)，決定推薦鞏固題或拔高題，或進(jìn)入下一知識(shí)點(diǎn)學(xué)習(xí)，從而優(yōu)化學(xué)習(xí)者學(xué)習(xí)效率。實(shí)驗(yàn)結(jié)果表明，本文提出的推薦算法具有較好的推薦效果，并已成功應(yīng)用于某高校的在線智慧教學(xué)平臺(tái)中。

表5 拔高題推薦的覆蓋率與準(zhǔn)確率比較