基于知識體系結構的組卷方法研究與應用

喬亞男， 程 航， 薄鈞戈

(西安交通大學 計算機科學與技術學院，陜西 西安 710049)

0 引言

大學計算機類課程是非常重要的高校公共基礎必修課程，該類課程以計算思維培養為目標，在教學內容中滲透計算思維的基本理念，為學生展示計算機學科的輪廓和相關技術，提升學生利用計算機解決本專業應用問題的能力，同時為未來可能的學科交叉研究打下基礎?；谟嬎銠C學科的自身特點，在培養高素質專門人才和拔尖創新型人才的大背景下，推動教學評價改革成為計算機基礎課程教學改革的重中之重。隨著高校校園網建設的不斷完善，考試的方式、載體發生了比較大的變化，由傳統的線下考試轉變為無紙化線上考試，經過長時間的考試在電子化試題庫中積累了相當量的試題，傳統人工組卷方式不僅耗時耗力、效率低下，并且不能保證所組試卷科學合理[1～2]。

自動組卷是指根據出題人所指定的約束條件，從題庫中自動篩選滿足條件的試題，從而代替人工選題的過程[3]。大學計算機類課程包含數門課程，涉及軟硬件系統、網絡、數據庫、程序設計、多媒體技術等眾多知識點，不同課程的考核范圍既不同又有一定交叉。并且正常教學活動中，組織一門課程的考試通常要準備數份甚至數十份試卷。這些特點決定了計算機自動組卷若要滿足教學需求必須解決以下幾個問題：①如何保證多份試卷在難度、結構、考核范圍等方面一致；②如何提高算法性能。

近年來，已有多位學者針對組卷問題開展自動組卷方法研究。目前的自動組卷方法主要分為三大類：第一類為借助于某種隨機算法進行組卷,如Marzukhi和Kiran對傳統隨機抽題算法進行了改進，利用洗牌算法避免了重復性抽題[4～5]。第二類是基于深度優先搜索算法DFS(Depth-first Search)或者廣度優先搜索算法BFS(Breadth-first Search)進行組卷，如陳雷等人[6]針對回溯抽題算法時間復雜度和空間復雜度較大的問題進行了改進，提出了“目標終止回溯試探法”和“縮減深度回溯試探法”，在實驗中證明了兩種算法在特定試題庫中提高了組卷效率，但所組試卷中仍有部分重復試題，并且算法適應情況較窄。最后一類則是借助于智能啟發式搜索算法進行組卷,如Zhang等人[7]在試題庫建設中使每種題型在數據庫中對應一張表，并在原始仿生學遺傳算法中對初始種群的生成采取了約束，采用實數編碼代替了傳統的二進制編碼，提高了算法的收斂度。Hu等人[8]將遺傳算法與粒子群算法兩種算法相結合，通過實驗數據分析了影響組卷的因素。此外，基于遺傳算法和蟻群算法，國內多位研究者在智能考試和組卷算法上也進行了深入的研究[9～11]。

針對上述存在的問題，本文通過對組卷問題建模，對自動組卷中的難點問題進行深入研究，對傳統隨機抽取算法進行了改進，提出了一種針對大學計算機類課程知識體系結構的自動組卷方法。

1 設計思想

1.1 題庫參數設計

題庫是選擇組卷算法及能否實現組卷的關鍵因素，一個好的題庫設計在一定程度上可以提高算法的執行效率。

在試題表中，每道試題題干、答案以XML格式儲存，特別地，當題型為編程題時，額外擁有測試用例字段，該字段也以XML格式存儲。根據組卷要求，每道試題Qi擁有多個約束屬性，包括難度、題型、知識點、章節等，具體可表示為式(1)。

Qi= (QIDi,CIDi,Ti,Si,Pi,Di,...)

(1)

QIDi作為主鍵表示當前的試題編號，是每個試題的唯一標識，CIDi表示此試題對應的課程編號，作為外鍵與課程表相關聯，Ti表示該試題的題型，Si表示該試題在相應課程編號下對應的章節，Pi表示該試題在對應課程對應章節下的所屬知識點，Di表示該試題的難度等級。其中試題的難度系數與難度等級對應關系，如表1所示。

表1 難度等級與難度系數對應關系

在數據庫中，將試題的題型以int類型存儲，以提高檢索效率。試題的題型表示與題型描述對應關系如表2所示。

表2 題型對應關系

在知識點標注時，采用分段實數編碼的方式，具體可表示為式(2)。

Pi=CIDiSiKi

(2)

其中，CIDi表示該知識點對應的課程編號，Si表示該知識點對應的章節，Ki表示為該知識點的序號。例如：450102,45則為編號為45的課程，01代表該課程的第一章，02代表該課程第一章的第二個知識點。

1.2 候選試題數據結構

組卷時，系統根據用戶所設定組卷需求預先將數據庫中的試題信息自動讀入內存中，生成供隨機選題用的候選試題數據結構。

抽題算法主要數據結構包括兩個部分，第一部分為章數組字典IDAndChapter，數組下標代表題型，每個字典中的鍵值對代表試題編號與章的對應；第二部分為知識點數組字典IDAndKP，數組下標代表題型，每個字典中的鍵值對代表試題編號與知識點的對應。

2 組卷算法描述

采用此方法組卷的一般過程如下：

(1)根據組卷條件，判斷當前題庫情況是否滿足組卷要求，若滿足條件則開始組卷；否則重新設置組卷參數；

(2)采用一種基于知識體系結構的改進型隨機抽取算法，依次循環為各試卷抽取指定題型中之前未被抽取過的題目，直到抽取完條件要求的全部題目；

(3)題目抽取完成后，計算各試卷中每類題型的平均難度值，確定是否符合設定要求。如果不符合，則采用一種循環替換算法進行難度值調整，直到滿足設定要求。整體流程如圖1所示。

圖1 組卷整體流程圖

2.1 條件判斷及預處理

根據用戶所設置組卷條件，判斷當前題庫試題是否滿足組卷要求，若滿足條件則進入下一步開始組卷，否則重新設置組卷參數。這里的組卷條件可通過瀏覽器登錄組卷系統設置。包括的參數有：

(1)課程(Course)：本次組卷針對的具體課程；

(2)試卷數量(PaperNum)：需要同時組成的試卷套數；

(3)考核范圍(Scope)：試題涉及的章范圍；

(4)題型(QType)：各試卷所包含的題目類型。題型包括：單選、多選、判斷、填空、問答、編程、綜合。

(5)每種類型題目數量(QTNum)：每套試卷中單種題型的題目數量。

(6)題目分值(Score)：每種題型的單道題目分值。不同題型的單道題目分值可以不同。

(7)題型難度值(QDegree)：試卷中每種類型題目的平均難度值。不同題型的QDegree可以不同。

其中，“試卷數量”是指同時組成的試卷數，該數量與實際需要及題庫容量有關。在Scope設定的前提下，若用Sumf表示用戶所設置的試卷總分值，SumS表示題庫中設定考核范圍的總題量，Sumt表示題庫中考核范圍內任意一種題型的題目數量，n表示要求的題型種類數，對同時組成的每套試卷，其n值相同。則允許同時組成的試卷數量應同時滿足公式(3)、公式(4)和公式(5)，否則需要重新調整組卷參數。

(3)

(4)

Sumt≥PaperNum×QTNum

(5)

其中，公式(3)的含義是：每套試卷總分值應與用戶所設置試卷總分值相等；公式(4)的含義是：題庫中指定考核范圍的試題總量應大于等于所需試卷題目數量之和；公式(5)的含義是：題庫中每種題型的題目數量應大于等于所需試卷每種題型題目數量之和。

2.2 基于知識體系結構的抽題算法

這里的知識體系歸屬于計算機教學領域，其結構包含課程(Course)、章(Scope)、知識點(Point)及相互之間的對應關系，課程、章、知識點是特定領域約定俗成的術語，三者為包含關系，滿足如下表達式(6)。

Point?Scope?Course

(6)

按照公式(6)可得計算機領域知識體系拓撲結構圖，包含：課程(Course)、章(Scope)、知識點(Point)，它們之間滿足公式(6)所述關系。拓撲結構圖如圖2所示。

圖2 計算機領域知識體系拓撲結構圖

定義二維數組MIsChoosed和PIsChoosed，分別表示某類題型中某章是否已抽取，以及某章中某知識點是否已抽??；定義整型變量Count表示某題型已抽取的題目數量，初始化為0；定義Sum表示某類題型所需題目數量。具體流程為：

(1)選定準備抽取的題目類型；

(2)選擇已抽取章的下一章(初始時默認為第1章)作為當前抽取章，采用算法2依次為各試卷抽取一道題目。

(3)判斷各試卷該題型題目數量是否達到要求，如果沒有，則繼續(2)。否則進行過程(4)

(4)判斷是否所有題型題目均已抽取完畢，如果沒有，繼續(1)，選擇下一種題型；否則，表示各試卷所有題型題目都已抽取完畢。

所有試卷抽題流程算法偽代碼如下所示。

1)算法1

輸入：某課程下所有試題QIdList，組卷約束條件。

輸出：所組多份試卷paperList。

//i為當前題型

For each i [0,6] do

Define Count = 0

While (Count < Sumi) do

//chaps為用戶所選定章節

For each chap chaps

KSA();//算法2

End while

End for

Return paperList

其中，一次為每套試卷抽取一題的算法思想為：根據圖1所示領域知識體系，在已構建領域知識體系基礎上，按照章及章內知識點順序，遵循未被抽取過題目的知識點優先原則，依次循環為各試卷抽取指定題型中之前未被抽取過的題目，直到抽取完條件要求的全部題目，詳細步驟如下算法所示。

基于知識體系結構的改進型隨機抽取算法

輸入 某課程下所有試題QIdList，組卷約束條件。

輸出 符合出題人設定的多份試卷paperList。

步驟1：判斷當前抽取章curChap中當前題型i是否還有未被抽取過的題目，若全部題目均已被抽取，則進入步驟4；否則，基于知識體系結構，從該章中按順序選擇一個知識點curKP，執行步驟2；

步驟2：判斷該知識點是否有未被抽取過的該題型題目。若有，執行步驟3；否則，選擇該知識點所對應章節的下一個知識點，重新執行步驟2；

步驟3：從選定的知識點中隨機抽取一道未被抽取過的題目QId；

步驟4：選擇下一章作為當前抽取章(初始時默認抽取第一章)，若全部章被抽取完，則將所有章置為未抽取狀態，選擇第一章作為當前抽取章，重新返回步驟1；

步驟5：判斷各試卷是否均已抽取一道指定題型的題目，如果沒有，轉向步驟2；否則，將所抽取的題目及其知識點標記為“已抽取”，將包含該知識點的章設為已抽取章。完成為每套試卷抽取一道指定題型題目工作，偽代碼如算法2所示。

2)算法2

輸入：某課程下所有試題QIdList，組卷約束條件。

輸出：所組多份試卷paperList。

Define paper = 0 ;//當前試卷

If(!Mischoosed[chap]) do

//KPs為當前章下所有知識點

Define KPs getKPs(chap)

For each kp KPs do

If(!PisChoosed[i][kp]) do

While(paper

QId Random();

PisChoosed[i][chap] = True;

MisChoosed[chap] = True;

paperList[paper].add(QId);

End while

paper = 0;

End if

End for

End if

2.3 循環難度調整算法

對按照算法1所抽取的各試卷，分別計算各試卷中每類題型的平均難度值，并與用戶所設定的各題型難度值進行比較，判斷某試卷某題型的平均難度值與該題型對應難度值偏差是否處于允許范圍內。若不符合，則采用一種循環難度調整算法遵循知識點、章、其它章的搜尋順序進行試題難度調整，直到滿足設定要求。

設Dai為表示第i套試卷選定題型的平均難度值，Di為該題型設定難度值，f為允許誤差值，參照算法2，試卷難度調整的具體方法為：

輸入 基于上述抽題算法的所組試卷paperList

輸出 符合用戶所設定難度的試卷paperList`

依次處理paperList中的每套試卷，以第一份試卷為例，按序選定試卷題型，計算該試卷該題型的平均難度值Dai，并與該題型設定難度值Di進行比較，則有以下三種情況：

(1)如果|Dai-Di|

(2)如果|Dai-Di|≥f且Dai>Di，則刪除第i套試卷該題型中難度值最大的題目，重新抽取難度值較小、且在本次組卷中未被抽取過的同類型題目替換，直到滿足要求為止。

(3)如果|Dai-Di|≥f且Dai

所訴情況(2)的循環難度調整算法包括如下具體步驟：

步驟1：刪除該題型當前難度值最大的題目MaxQId，從題目屬性中獲取待替換題目關聯的知識點MaxQIdKP，查找題庫中同一知識點中是否有未被抽取過、難度值小于被刪除題的同類型題目。若有，則執行步驟5，否則繼續步驟2；

步驟2：從包含該知識點的章中查找是否有未被抽取過、難度值小于被刪除題的同類型題目。若有，則執行步驟5，否則繼續步驟3；

步驟3：從其它章中查找是否有未被抽取過、難度值小于被刪除題的同類型題目。若有，則執行步驟5，否則繼續步驟4；

步驟4：按照上述原則仍沒有找到符合條件的題目，則難度調整失敗，重新組卷。

步驟5：隨機抽取一道滿足條件的題目ranQId替換原題。計算當前題型的平均難度值，若符合難度范圍要求，則結束；否則繼續轉向步驟1。

所述情況(3)采用類似的循環難度調整算法，依次替換題型中難度值最小的題目，直到該題型難度值滿足要求。

當所有題型均滿足|Dai-Di|

3)算法3

輸入：基于前述改進型隨機抽題算法的所組試卷paperList。

輸出：經難度調整的paperList`。

Define f

For each curQType [0,6] do

//i為當前試卷

For i= 0;i

If(|Dai-Di|

Continue;

While(|Dai-Di|≥f&&Dai>Di)do

paperList[i].remove(MinQId)

ranQId Random();

paperList[i].add(ranQId);

End while

While(|Dai-Di|≥f&&Dai

paperList[i].remove(MaxQId)

ranQId Random();

paperList[i].add(ranQId);

End while

End for

End for

Return paperList`

3 實驗過程及分析

3.1 實驗條件

為了驗證本課題所提出的基于知識體系結構組卷算法KSA(knowledge structure algorithm)的有效性，采用“大學計算機基礎”這一課程題庫作為測試數據，題目數量共計803道，其中單選題318道，多選題32道，判斷題134道，填空題169道，程序題130道，綜合題20道。

測試環境：

1)軟件環境

操作系統：Windows 7 64bit

開發語言：C#+HTML+JavaScript

開發環境：Microsoft Visual Studio 2017

數據庫：Sql Server 2012

瀏覽器：Google Chrome

2)硬件環境

CPU：Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz

RAM：8G

3.2 試卷參數

(1)課程：大學計算機基礎。

(2)章范圍：第1-8章。

(3)試卷總分：100分。

(4)試卷題型及各題分值：單選題16題，每題2分，共計32分；判斷題10題，每題2分，共計20分；填空題2題，每題7分，共計14分；編程題3題，每題8分，共計24分；綜合題1題，每題10分，共計10分。各題型難度值設定除判斷題題型為2，其余題型均為3。

(5)組卷份數：5份。

3.3 實驗結果及分析

應用本文提出的KSA組卷算法與傳統遺傳算法GA(genetic algorithm)在組卷效果與執行效率上進行了對比實驗，每個算法實驗共進行5次，每次均以上述試卷參數為基準進行組卷。以實驗中試卷的難度值方差來衡量各試卷難度的離散程度，以限定題目數量下的知識點重復率衡量多套試卷知識點的重復情況，以各試卷間知識點走勢及擬合程度衡量知識點平衡情況，以算法執行時間衡量算法性能。對比實驗結果如下所示。

1)兩種算法難度值方差對比

每次實驗的難度值方差說明了各試卷之間難度的偏離程度，該方差數值越小，代表多份試卷難度基本持衡。兩種算法難度值方差對比實驗數據如表3所示。

表3 難度值方差對比實驗

從表中可以看出，KSA算法的方差值高于GA，主要原因是：GA算法中種群進化時會優先挑選適應度高的個體進入下一代，在不斷的雜交之后，種群多樣性銳減，導致個體相似度過高，即試卷中試題重復率過高，故所組試卷之間難度值方差極小。

2)兩種算法知識點重復率對比

在一份質量較高的試卷中，每道試題應有對應的知識點且互相不重復。這里題庫中的知識點標注以該題最想考察的知識點為主。取每次實驗中重復率最高的試卷作對比，對比結果如圖3所示：

從圖中可以看出，以KSA算法所組試卷的知識點重復率遠低于GA，最大差值為32%，提高了試卷的質量。

圖3 難度值方差對比實驗

3)知識點走勢及擬合程度

分別以KSA算法和GA算法為核心所組試卷中隨機抽樣一次實驗進行分析，圖4給出了32道題目同時組5份試卷的章、知識點分布情況。

(a)KSA知識點走勢及擬合程度

(b)GA知識點走勢及擬合程度圖4 知識點重復率對比實驗

由上圖可以看出，圖(a)較之于圖(b)，5份所組試卷的知識點曲線走勢更趨于擬合，這說明了KSA算法在組多份試卷的情況下能夠考慮到試卷之間的知識點平衡關系，為考試提供了一定的公平性。但從上圖也可以看出，在個別題目上曲線走勢分歧較大，如：1-3題、9-11題，主要原因是：該知識點下沒有足額未抽取的試題以供組卷。當組卷數目大于某知識點下題目總數時，KSA算法會優先抽取該知識點下試題，剩下的差額試題會自動從下一個知識點下抽取，當該章下所有知識點均標記為已抽取狀態，則從該章的下一章抽取。

4)算法性能對比

以組卷執行時間代表算法性能，由圖5可以看出兩種算法性能大致一般，組卷時間在2s內，滿足高校教師的需求。

圖5 知識點走勢對比實驗

由以上所有對比實驗可知，本文與傳統的遺傳算法相比，極大的降低了知識點的重復率，利用預定義的字典數組MIsChoosed和PIsChoosed實現了篩選試題無重復。實際運用中，組卷時間和體驗符合高校教師的基本組卷需求，基于知識體系結構的隨機抽取算法在組卷系統中得到了成功的運用。

4 結語

組卷是試題庫建設和在線考試系統的核心內容，設計一種高效、科學、魯棒的組卷算法則是重中之重。本文針對現有算法未考慮組多份難度一致、知識點均衡試卷的情況而提出基于知識體系結構的隨機抽取算法和循環難度調整算法，全面考慮知識點、難度控制，組卷結果更加符合正常的教學活動。在與傳統遺傳算法的對比實驗中，表現出了更好的組卷效果。

基于本文方法開發的題庫管理系統和考試系統已經在西安交通大學的教學環境中得到了實際應用，提升了教學體驗，得到了師生的一致好評，我?！按髮W計算機”系列課程，最近幾年相繼被評為國家級“一流課程”，和該部分的教學改革是分不開的。首先，按照知識點比例進行考試題目分布，對教師的教學和學生的學習都有了更高的要求，通過對平時習題和考前模擬的綜合分析，教師可以充分了解學生對知識點的掌握情況，對知識點進行有針對性的講解，達到提升教學質量的目標。而學生在反復練習的過程中，也可以查漏補缺，優化解題思路，鞏固知識點掌握。其次，通過對知識點的全面覆蓋，也可以確?？荚嚬?，避免學生復習的片面性，降低考前“押題”、“猜題”的收益率，提升學生學習水平和考試成績的相關性。

雖然實際測試結果已表明本文方法優于傳統遺傳算法，但還存在著一些欠考慮的情況，如：是否可以繼續降低知識點重復率，是否可以在大型題庫中快速組卷。這些還需要進一步的實驗以完善算法。