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

董曉璇， 葉建芳， 孫一萍

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

0 引言

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

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

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

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

1 設(shè)計(jì)思想

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

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

將題目的知識(shí)點(diǎn)和難易程度作為組卷過(guò)程中兩個(gè)最為重要的因素，同時(shí)用洗牌策略控制試題出現(xiàn)頻度，將試卷作為整體研究對(duì)象，組卷過(guò)程可表示為式(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表示成功組卷的所有動(dòng)作，z1、z2等表示只考慮難度(D)、知識(shí)點(diǎn)(K)、頻度(P)、題型(T)因素的組卷過(guò)程，Q2表示對(duì)某一題型的組卷進(jìn)行知識(shí)點(diǎn)和難易的平衡，下標(biāo)N表示章節(jié)數(shù)量或者章節(jié)中的小節(jié)數(shù)量。

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

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

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

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

(2)

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

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

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

(3)

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

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

1.2 知識(shí)點(diǎn)劃分

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

1.3 難度判斷

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

(4)

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

圖2 難度等級(jí)概率分布圖

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

(5)

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

(6)

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

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

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

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

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

2.1 算法描述

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

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

(7)

(2) 定義一個(gè)二維數(shù)組temp_i，用來(lái)存放經(jīng)過(guò)數(shù)據(jù)庫(kù)語(yǔ)句得到的每個(gè)知識(shí)點(diǎn)的試題題號(hào)與其對(duì)應(yīng)的難度等級(jí)。首先獲取各個(gè)章節(jié)的單選題數(shù)量，采用洗牌算法將順序的題號(hào)進(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) 題號(hào)重新排序后，采用不重復(fù)的隨機(jī)數(shù)序列產(chǎn)生算法，用rand()函數(shù)產(chǎn)生第一個(gè)隨機(jī)數(shù)，從tihaolist_i數(shù)組取出對(duì)應(yīng)隨機(jī)數(shù)下標(biāo)的題號(hào)，存放到finallist數(shù)組，并將temp數(shù)組中被選中的題號(hào)與數(shù)組最后有效題號(hào)進(jìn)行交換，然后將隨機(jī)數(shù)產(chǎn)生范圍減1，同時(shí)將所需的題目數(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) 在獲取選擇題所有的題號(hào)后，根據(jù)不同的情況，作業(yè)的組成采用式(4)進(jìn)行難度系數(shù)計(jì)算，因?yàn)樽鳂I(yè)不需要精確地控制難度，所以只要難度系數(shù)維持在0.3-0.7之間即可；而試卷對(duì)于難度的要求較高，采用式(6)進(jìn)行難度評(píng)測(cè)，如果難度系數(shù)與難度閾值之差的絕對(duì)值在0.05之間則跳轉(zhuǎn)至步驟(8)，否則進(jìn)行難度均衡。

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

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

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

2.2 算法流程圖

算法流程，如圖4所示。

圖4 算法流程圖

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

3.1 實(shí)驗(yàn)條件

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

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

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

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

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

表2 組卷耗時(shí)對(duì)比 (單位：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ī)法組卷的速度快，對(duì)比作業(yè)生成與考卷，明顯可以看到在題庫(kù)較大的情況下，改進(jìn)隨機(jī)組卷算法的優(yōu)勢(shì)更加明顯。所以采用不重復(fù)隨機(jī)序列算法不僅組卷效率有很大的提高，并且組卷成功率也有所提升

2) 算法的有效性

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

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

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

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

4 總結(jié)

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