基于知識點(diǎn)與難度的組卷算法及應(yīng)用

董曉璇， 葉建芳， 孫一萍

(東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 上海 201620)

0 引言

作業(yè)訓(xùn)練與考試作為評測手段是教學(xué)過程中不可或缺的一環(huán)，而信息技術(shù)的快速發(fā)展使得基于Web在線作業(yè)與試卷生成系統(tǒng)成為計算機(jī)輔助教學(xué)中重要的組成部分[1]。該系統(tǒng)在一定程度上避免傳統(tǒng)作業(yè)模式下普遍存在的作業(yè)抄襲現(xiàn)象；另一方面，克服任課老師命題的主觀性。系統(tǒng)根據(jù)教學(xué)大綱要求，能夠選擇一個高效、科學(xué)、強(qiáng)壯的算法組卷是關(guān)鍵[2]。

目前常用的組卷算法有隨機(jī)抽取法、回溯試探法與遺傳算法。遺傳算法具有全局尋優(yōu)和收斂速度快的特點(diǎn)，但算法復(fù)雜、容易“早熟”[3]，而且當(dāng)試題庫比較大時，容易導(dǎo)致染色體編碼過長，所花費(fèi)的時間開銷呈線性增長，同時對于小規(guī)模的試題庫而言，有可能導(dǎo)致兩次產(chǎn)生的試卷具有較高的試題重復(fù)率。

隨機(jī)抽取法盡管結(jié)構(gòu)簡單，易于理解與實(shí)現(xiàn)，適合于小型的題庫系統(tǒng)，在現(xiàn)有的大量考試系統(tǒng)中也有廣泛應(yīng)用，但是傳統(tǒng)的隨機(jī)抽取法是根據(jù)組卷狀態(tài)空間的控制指標(biāo)，隨機(jī)抽取一道符合指標(biāo)的試題，不斷重復(fù)此過程。不難發(fā)現(xiàn)，該算法可能在證明已無法抽取合適試題的區(qū)域反復(fù)選題，進(jìn)行大量無效操作，導(dǎo)致訪問數(shù)據(jù)庫過于頻繁，從而增加組卷時間，甚至進(jìn)入死循壞導(dǎo)致組卷失敗[4]。在文獻(xiàn)[5]中提出集合隨機(jī)組卷算法，采用集合和題號預(yù)存的方法解決了反復(fù)回溯匹配問題，但是預(yù)存題號加大了空間的占用，對試題難度的控制較為粗略。文獻(xiàn)[6]提出了試題難度和知識點(diǎn)覆蓋控制算法，組卷效果較好，但在題量較小時試題重復(fù)率較高。文獻(xiàn)[7]提出基于洗牌策略的隨機(jī)抽取算法，不依賴于題型數(shù)量，即使題庫數(shù)量增長，仍然可以達(dá)到很快的生成速度，但是對于試卷難度控制力不強(qiáng)。

基于上述問題，本文結(jié)合通信電路電子電路課程，采用php+MySQL開發(fā)設(shè)計了基于B/S的在線作業(yè)與試卷生成系統(tǒng)，并且提出了一種基于難度和知識點(diǎn)改進(jìn)的隨機(jī)組卷方法，實(shí)現(xiàn)快速、有效的組卷目標(biāo)。

1 設(shè)計思想

自動組卷需要兼顧多方面的因素，以滿足實(shí)際教學(xué)需求。一份好的作業(yè)能涵蓋的知識點(diǎn)全、難度中等，而且盡量避免每位學(xué)生作業(yè)題目的重復(fù)性，有效抑制學(xué)生之間相互抄襲現(xiàn)象。考試組卷不僅要求考察內(nèi)容全面，更注重難度合理，使學(xué)生的成績接近于正態(tài)分布[8]。

為了解決傳統(tǒng)隨機(jī)算法存在的問題，考慮采用縮小搜尋的范圍和生成不重復(fù)隨機(jī)數(shù)序列的方法來解決。此外，在線作業(yè)與試卷生成系統(tǒng)具有學(xué)生根據(jù)教師要求生成作業(yè)的功能，為了防止作業(yè)的抄襲現(xiàn)象，引入洗牌策略在一定程度上避免不同學(xué)生之間作業(yè)重復(fù)的現(xiàn)象。在組卷時運(yùn)用此策略可使試卷題目的排列順序不同，從而降低作弊的可能性。

將題目的知識點(diǎn)和難易程度作為組卷過程中兩個最為重要的因素，同時用洗牌策略控制試題出現(xiàn)頻度，將試卷作為整體研究對象，組卷過程可表示為式(1)。

Pa=Q(z1(D，K，P，T)，z2(D，K，P，T)，…，zN(D，K，P，T)，Q2(D,K))

(1)

式(1)中，Pa表示組卷，Q表示成功組卷的所有動作，z1、z2等表示只考慮難度(D)、知識點(diǎn)(K)、頻度(P)、題型(T)因素的組卷過程，Q2表示對某一題型的組卷進(jìn)行知識點(diǎn)和難易的平衡，下標(biāo)N表示章節(jié)數(shù)量或者章節(jié)中的小節(jié)數(shù)量。

1.1 題庫參數(shù)設(shè)計

題庫是選擇組卷算法及能否實(shí)現(xiàn)高效組卷的關(guān)鍵因素，一個好的題庫結(jié)構(gòu)在一定程度上可以提高算法的執(zhí)行效率。將整個題庫按照不同的題型分為4個試題庫表，分別為選擇題、填空題、簡答題、計算題，這樣既可以縮小算法的搜索范圍，也更加便于數(shù)據(jù)庫的管理。

一份作業(yè)、試卷中包含了不同知識點(diǎn)、不同題型的若干試題，因此每個試題庫包含了不同章節(jié)、難度的試題，按照“卷內(nèi)分塊”的思想[9]，每個試題庫表S可表示為式(2)。

S=(s1,s2,…,sn)n=1,2，…

(2)

式(2)中，s1,…，sn表示試題，n表示試題數(shù)量。

試題庫中的每個試題除了本身的題干、答案，還根據(jù)自動組卷的要求定義多種屬性，每道試題sj屬性可表示為式(3)。

sj=(IDj,Cj,Kj,Dj,mj,fj)

(3)

IDj表示試題的編號，是每個試題的唯一標(biāo)示，Cj表示試題所屬的章節(jié)，Kj表示這個試題所屬的小節(jié)，Dj表示該試題的難度系數(shù)，mj表示難度等級，fj表示該試題的分值。其中試題的難度系數(shù)與難度等級關(guān)系，如圖1所示。

難度等級12345難度系數(shù)0～0.20.2～0.40.4～0.60.6～0.80.8～1難度描述易較易中等較難難

1.2 知識點(diǎn)劃分

考試是對課程涵蓋所有知識點(diǎn)的考察，考卷中可依據(jù)章節(jié)區(qū)分知識點(diǎn)，作業(yè)是對一個章節(jié)知識點(diǎn)的檢測，因此依據(jù)章節(jié)中每個小節(jié)區(qū)分具體的知識點(diǎn)。因為知識點(diǎn)是按照章節(jié)或者小節(jié)進(jìn)行區(qū)分，所以知識點(diǎn)的優(yōu)先級是相等的，不加以區(qū)分。

1.3 難度判斷

該系統(tǒng)具有作業(yè)生成和組卷兩大功能，作業(yè)生成的主要目標(biāo)是檢測學(xué)生知識掌握情況，對難度系數(shù)沒有苛刻的要求，只要保持在某一范圍內(nèi)即可，作業(yè)的平均難度系數(shù)G表示為公式(4)。

(4)

考試的目的是衡量大多數(shù)學(xué)生的學(xué)習(xí)情況，對難度系數(shù)的要求較高，所以按照正態(tài)概率分布的思想來計算難度系數(shù)。不同難易等級將正態(tài)分布分隔成5塊，其中“容易”和“難”所占的面積約為2.5%，“較易”與“較難”各占13.5%，“中等”占68%[10]，概率分布，如圖2所示。

圖2 難度等級概率分布圖

在估計難易程度時按照統(tǒng)計學(xué)的均值思想，分別為5個等級賦予不同的估計系數(shù)，其系數(shù)如式(5)。

(5)

式(5)中，Ym表示第m等級的估計系數(shù)，Xk表示第k等級所占面積比例。計算得到圖中從右往左估計系數(shù)為0.987，0.917，0.51，0.0925，0.012，難度系數(shù)計算如式(6)。

(6)

1.4 不重復(fù)隨機(jī)數(shù)的產(chǎn)生

針對傳統(tǒng)隨機(jī)抽取法存在反復(fù)選取無效試題的問題，采用不重復(fù)隨機(jī)序列產(chǎn)生算法，即將已被選中的試題號用最后一個有效的試題號覆蓋，使得選題過程一直在能夠抽取合適試題的范圍內(nèi)選擇，具體步驟，如圖3所示。

圖3 不重復(fù)隨機(jī)序列生成圖

第一步，將根據(jù)條件遍歷數(shù)據(jù)庫后得到題號1-5存入數(shù)組，并使用洗牌算法打亂題號順序如圖3(a)、(b)；第二步，產(chǎn)生一個隨機(jī)數(shù)2作為數(shù)組的下標(biāo)，選取圖3(b)中的試題號1，將該題號存入題號數(shù)組后，用數(shù)組中最后一個有效的題號4覆蓋已選中的數(shù)組元素1，并且將產(chǎn)生隨機(jī)數(shù)的范圍減小1；第三步，重復(fù)第二步，直到產(chǎn)生的題號數(shù)量達(dá)到要求。這個算法的優(yōu)點(diǎn)是不需要反復(fù)判斷，也不會因為刪除數(shù)組元素而執(zhí)行大量移動操作，只是進(jìn)行數(shù)組元素賦值操作，將算法的復(fù)雜度降低到O(n)。

2 算法實(shí)現(xiàn)

2.1 算法描述

本算法優(yōu)先考慮出卷人的要求，在滿足基本條件的情況下，通過式(4)、(5)分別對生成的作業(yè)和試卷進(jìn)行難度系數(shù)計算，如果滿足要求執(zhí)行下一個模塊的組題，否則進(jìn)行難度均衡。以選擇題為例，算法的具體步驟如下。

(1) 定義一個數(shù)組Y，存放出題人要求各題型的題量數(shù)，根據(jù)出卷人給出的要求獲得所需要的選擇題數(shù)量為Y[0]，選擇題題庫中題目所屬的章節(jié)數(shù)共為nc或者章節(jié)中的小節(jié)數(shù)為nc，則需要處理的子集數(shù)為nc。為了保證覆蓋所有的知識點(diǎn)，從每個集合中抽取的題目數(shù)N可以計算，如式(7)。

(7)

(2) 定義一個二維數(shù)組temp_i，用來存放經(jīng)過數(shù)據(jù)庫語句得到的每個知識點(diǎn)的試題題號與其對應(yīng)的難度等級。首先獲取各個章節(jié)的單選題數(shù)量，采用洗牌算法將順序的題號進(jìn)行打亂后存放到數(shù)組tihaolist_i。洗牌算法如下：

void Shuffle()

{

for(intm=length[temp_i];m>=1;m--)

{

DoSwap(tihaolist_i[i],tihaolist_i[rand()%(m+1)]);

}

}

(3) 題號重新排序后，采用不重復(fù)的隨機(jī)數(shù)序列產(chǎn)生算法，用rand()函數(shù)產(chǎn)生第一個隨機(jī)數(shù)，從tihaolist_i數(shù)組取出對應(yīng)隨機(jī)數(shù)下標(biāo)的題號，存放到finallist數(shù)組，并將temp數(shù)組中被選中的題號與數(shù)組最后有效題號進(jìn)行交換，然后將隨機(jī)數(shù)產(chǎn)生范圍減1，同時將所需的題目數(shù)減1，直到選到等數(shù)量的題。核心代碼如下：

k=0;

for(j=n;j

{

finalist[k]=tihaolist_i[rand()%j];

k=k+1;

}

(4) 在finallist數(shù)組中選取選擇題所需的題量Y[0]，同樣采用不重復(fù)隨機(jī)序列的產(chǎn)生方法，將最終結(jié)果存入exam數(shù)組。

(5) 在獲取選擇題所有的題號后，根據(jù)不同的情況，作業(yè)的組成采用式(4)進(jìn)行難度系數(shù)計算，因為作業(yè)不需要精確地控制難度，所以只要難度系數(shù)維持在0.3-0.7之間即可；而試卷對于難度的要求較高，采用式(6)進(jìn)行難度評測，如果難度系數(shù)與難度閾值之差的絕對值在0.05之間則跳轉(zhuǎn)至步驟(8)，否則進(jìn)行難度均衡。

(6) 如果難度系數(shù)低(高)于難度閾值，從與其相同知識點(diǎn)的temp_i數(shù)組中選擇難度系數(shù)高(低)于難度閾值的題目，轉(zhuǎn)至步驟(5)重新進(jìn)行難度評測，直到難度符合用戶要求，并將其題目存入exam數(shù)組，跳轉(zhuǎn)至步驟(8)，如果執(zhí)行3次難度均衡后仍達(dá)不到要求跳轉(zhuǎn)到(7)。

(7) 輸出提示，組卷失敗。

(8) 將exam數(shù)組中試題號對應(yīng)的題目顯示到網(wǎng)頁上，完成組卷，結(jié)束。

2.2 算法流程圖

算法流程，如圖4所示。

圖4 算法流程圖

3 算法應(yīng)用及結(jié)果分析

3.1 實(shí)驗條件

該系統(tǒng)基于《通信電子電路》課程采用PHP+Mysql進(jìn)行開發(fā)，題庫系統(tǒng)所包含的總題量約為500道。按照題型分為4張表，分別是選擇題表、填空題表、簡答題表以及計算題表4個表，共約500道題，在此題庫下對算法生成作業(yè)和試卷兩方面性能進(jìn)行測試。

實(shí)驗1：生成作業(yè)的要求為第七章節(jié)選擇題2題，填空題2題，簡答題1題，計算題2題，如圖5所示。

實(shí)驗2：組卷的要求選擇題8題，填空題7題，簡答題4題，計算題5題，難度系數(shù)為0.5，如圖6所示。

根據(jù)出題人要求，在操作系統(tǒng)Windows 10，CPU為intel core i5，2G內(nèi)存環(huán)境下測試，經(jīng)過20次的實(shí)驗，得到結(jié)果如表1、表2所示。

表1 組卷成功次數(shù)對比

表2 組卷耗時對比 (單位：s)

比較改進(jìn)隨機(jī)算法與傳統(tǒng)隨機(jī)算法下得到的作業(yè)生成結(jié)果，試題重復(fù)率結(jié)果，如表3所示。

圖5 生成作業(yè)結(jié)果圖

表3 試題重復(fù)率

3.2 結(jié)果與分析

1) 算法的組卷效率

從表1可以看到，改進(jìn)隨機(jī)組卷算法的組卷成功率較高。表2的數(shù)據(jù)表明，改進(jìn)的隨機(jī)算法組卷速度明顯比傳統(tǒng)的隨機(jī)法組卷的速度快，對比作業(yè)生成與考卷，明顯可以看到在題庫較大的情況下，改進(jìn)隨機(jī)組卷算法的優(yōu)勢更加明顯。所以采用不重復(fù)隨機(jī)序列算法不僅組卷效率有很大的提高，并且組卷成功率也有所提升

2) 算法的有效性

從圖5可以看到，根據(jù)出題人要求生成作業(yè)，其涵蓋了第七章的知識點(diǎn)，沒有重復(fù)的知識點(diǎn)，而且分布也較為合理。由表3可見，運(yùn)用洗牌算法后，試題的重復(fù)率有所降低，使不同學(xué)生的作業(yè)有所區(qū)別。此外，在組卷時運(yùn)用洗牌算法，可以達(dá)到試卷試題順序不同的效果，從而在一定程度上避免學(xué)生作弊。

3) 算法復(fù)雜度分析

改進(jìn)的隨機(jī)組卷算法采用了洗牌算法和不重復(fù)隨機(jī)序列生成算法，洗牌算法的復(fù)雜度為O(n)，雖然相對傳統(tǒng)算法而言增加了復(fù)雜度，但是從一定程度上進(jìn)行了試題頻度控制。不重復(fù)隨機(jī)序列生成算法的復(fù)雜度僅為O(n)，相對于一般的隨機(jī)序列生成法，不用反復(fù)在無效的試題選取范圍內(nèi)選擇，并且相對于采用刪除試題號來避免的方式，大大減少了執(zhí)行時間，而且復(fù)雜度上由O()降低到O(n)。

圖6 部分組卷結(jié)果圖

4 總結(jié)

在線作業(yè)與試卷生成系統(tǒng)的性能主要取決于組卷算法，性能優(yōu)良的組卷算法不僅要確保成功組題，同時需要兼顧數(shù)據(jù)運(yùn)算速度，即組題效率。傳統(tǒng)隨機(jī)算法，組題的成功率較低，而且在時間和空間上開銷較大，更適合小型題庫。本文針對傳統(tǒng)隨機(jī)算法的不足，采用不重復(fù)隨機(jī)序列大大提高了組題的效率與成功率的同時，全面考慮知識點(diǎn)、難度控制，組題結(jié)果更加符合教學(xué)實(shí)際。此外，在改善了隨機(jī)算法在較大題庫情況下的性能。