課程測評系統的試題智能組裝方法

鮑宇 王凱馨 張艷群

摘要：分析課程測試系統試題的題干和問題組成的基本特征，提出利用題干和問題的智能匹配策略，通過模塊化組裝的形式與調整試題可變參數來生成問題和題干并創建試題，最終依據題型與知識點章節的劃分來抽取和生成測評內容。

關鍵詞：測評系統；背包算法；智能組裝方法

0、引言

隨著互聯網和信息科學技術的迅猛發展，網絡技術的應用領域不斷拓寬，網絡自主學習與課堂教學的結合已成為當代教學手段改革的主要方式。其中，利用網絡信息技術協助完成自主學習過程成為該類教育技術革新的亮點之一。通過自主學習平臺中的自主測評來完成自主在線測評，以及系統自帶的自動閱卷功能，使得被評測者能夠隨時隨地地進行自我檢測，這無疑方便和促進了使用者的學習。

經研究發現，目前學習網站測評系統還存在尚未完善的地方。例如測評系統形成試卷的方式固定，采用的是從同一題庫中抽取現有試題組成試卷的方法。這種方法產生的試題類別與數量有限，不易解決試題抽取重復率高的問題。

1、選題與組卷算法沒汁

1.1組卷與背包問題

組卷就是根據要求從試題庫中選擇試題組成—份符合要求的試卷。通過研究試卷的結構，發現任何一份試卷都可以分成以下3個部分來描述：①試卷的總體結構，用來描述試卷的整體信息，包括總體難度、試卷題型、試題數目等信息；②試卷單元，用來表示試卷所包含的題型，即每一題型為一試卷單元，包括題型、試題數、知識點章節分布，分數等信息；③試卷單元所包含的若干小題，用來描述試卷單元中每個小題的詳細信息，包括每個小題的題型、分數、所屬知識點章節。這樣，組卷過程實際上就是根據一定的約束條件，從試題庫中抽取若干小題組成一個個試卷單元，再由這若干個試卷單元構成一張完整試卷。若將一個試卷單元作為一個背包，背包所能裝入的試題數為背包容量，試題小包中的試題為所有的物品，則該問題的求解就轉變為背包問題的求解。每一試卷單元依據所屬題型匹配不同試題小包，得到每個試卷單元后，再將整張試卷作為一個大的背包，將所得到的試卷單元裝入背包，直到裝滿為止，從而就得到了整個試卷的解。至此，組卷實際上就轉化為了背包問題。

背包問題是一個非常經典的優化問題背包問題約束如下：設有一個背包，可以放入重量為S。現有，n件物品，重量分別為Sl，S2…Sn且均為正數，從這n件物品中選擇若干物品放入此背包，使得放入總重量恰好為S。

與解決背包問題類似，可以利用“回溯”的設計思想來解決此組卷問題。針對一個試卷單元，設其所要求包含試題數為S，從試題庫中選取小題，然后將所選小題i放入試卷單元中，如果已經選取的試題數i小于s，則繼續選取第1+1道題放人試卷單元中，直到試卷單元中的試題數為S為止。如果剩余試題中找不到合適的小題放人試卷單元，則說明剛剛裝入試卷單元的小題“不合適”，應將它“棄置一邊”，繼續選擇“它之后”的小題。如此重復，直到求得滿足要求的解或者無解為止，這樣得到一個試卷單元。同理，將所得到的若干試卷單元依次裝入試卷，直到得到一張完整的符合要求的試卷。

1.2基于背包問題的組卷算法設計

將組卷問題轉化為背包問題后，則組卷問題就是依據一定的限制條件，合理地選擇試題“裝入”試卷中。對此，首先要劃分可裝入的試題。分析試卷結構可知，一張完整試卷由若干題型組成，而每一題型又包含若干不同知識點章節的小題。所以，先依據不同的題型，將一整張試卷劃分為i個試卷單元Item（i），再依據所屬不同知識點章節，將每個試卷單元劃分為i部分，即對于每個試卷單元i包含j（j>=0）道題，分別來自于j個知識點章節。在選取j道試題填充試卷單元Item（i）時，由于是采用隨機數發生器來隨機地選取知識點章節，就有可能出現某些知識點在同一或不同試卷中重復出現，造成試卷知識點章節橫向縱向分布不均勻的問題，所以這里為屬于同一知識點章節的任意類型的試題設置相同的頻率參數ε，ε在這里代表該知識點章節試題出現的頻率。在進行試題抽取前，所有題庫中試題的ε初始化為相同的值，如設置為l/μ，設某一知識點章節的試題被抽取次數為κ，則抽取κ次后該知識點章節的ε更新為：

εj=1+k/μ+k（1）

其余知識點章節的ε隨著更新為：

εm=1/μ+k（2）

隨抽取次數κ的增加，εj會最終大于εm，即k越大，εj大于εm的程度越大，在題庫中相對出現頻率越大。那么在隨后的抽取試題的過程中，會優先選擇ε小的知識點裝入試卷單元Item（i），這樣可以使試卷結構分布更均勻，避免同一或不同試卷知識點分布不均的現象。

綜上，將每道試題記為Item（i，j，εj），i表示題目類型，j表示所屬知識點章節，εj表示該知識點章節試題出現的頻率。則基于背包問題的組卷問題就可看做，從已有的試題小包中抽取試題Item（ij，εj），將試卷單元Item（i）裝滿，再由Item（i）組成一張完整試卷的過程，試卷填充結構如表l所示。

根據上述描述，設計基于背包問題的組卷算法如下：

算法l：基于背包問題的組卷算法

void getSolutions（試卷單元，試題小包）{

k-random（）xlOOOO%size； //size為試題小包中的物品個數

WHILE（試卷單元朱裝滿且有試題小包不空）{

IF（試題小包中的第κ個題可取）

將κ試題放入試卷單元內；

k=random（）×lOOOO%size；//繼續考察試題小包中的下一個題

}

IF（試卷背包恰好裝滿）{求得一組解；}

退出試卷單元中的最后一道題k；

κ=random（）×lOOOO%size；//繼續考察試題小包中的下一道題

}

2、試題組裝及智能組裝策略

2.1試題組裝

解決了組卷問題后，接下來我們要討論如何得到大量可選試題。若采用從固定題庫中抽題的方法，那么可以使用的試題數目非常有限，且容易重復，所以我們提出采用動態組裝試題形成試題的方法來解決這個問題。仔細觀察某些試題就會發現，一道試題從語法結構上能劃分為若干部分，可以看做是多個前提、問題約束及問題的集合，即{前提1，前提2，……}、{問題約束1，問題約束2，……}，{問題l，問題2，……}，也就是說每道題都由若干題干搭配組合而成。對于該類試題，通過幾個題干集合的排列組合，形成不同的試題，若將每一集合分別拓展開來，即由設計者預先定義好每一集合所包含的若干元素，按照一些組題策略，通過幾個子集中元素的組合搭配即可形成數量可觀的試題，很好地解決了傳統固定題庫抽題所帶來的問題。對于試題組裝，本文作如下設置：

設題干小包Bagi（i=0，1，2，3）：

Bagl中元素為（Prebagl，Prebag2，Prebag3....），為前提小包Prebag，每一Prebagi內容為一給定的大知識點范疇（如樹、圖、數組等），Prebagi中元素為ai；

Bag2中元素為（Tipbagl，Tipbag2，Tipbag3...），為問題約束小包Tipbag，內容涉及具體問題約束，如相關算法、所提供的某些具體條件等；每一Tipbag包含若干可與 Prebagi中某一元素搭配的元素bi；

Bag3中元素為（Quebagl，Quebag2，Quebag3....），為問題小包Qucbag，內容為所提出的問題，如“求解……A.B、C”等；每一Quebag包含若干可與Tipbag/中某一元素搭配的元素ci。

對于包含參數的試題來說，還可以通過使用隨機數發生器，對題干所包含參數進行隨機修改，形成新的題干元素，再按照試題組裝算法進行試題組裝。在預先設置題干小包Bagi時，對其中元素所包含的參數進行初始化，在形成試題過程中，再隨機生成數字，代替原有參數，這樣不僅增加了試題的數量，還可減少試題的重復性；也可將作為問題的題干位置設為參數，進行隨機化處理。

2.2組裝策略

依據題干的位置不同，可將組裝策略分為兩類：題干視為參數型組裝策略、題干位置固定型組裝策略。第一種類型中，將題于視為參數，并隨機選取問題題干的位置，如問題題干放到句末，或是將包含已知條件的題干作為問題（可作選擇題、填空題）；第二種類型為默認問題題干在最后給出。對于不同的類型，有不同的組裝策略，先給出兩類組裝策略的通用策略：

（1）題干組裝策略。在組題過程中，對每個上一層的題干小包中的元素，選取可搭配的題干小包。又每一元素有可能只與某些小包中的元素可搭配。所以，當上一層小包中元素為空，或找不到可搭配的下一層小包時，就要采用回溯法返回到上一步，開始新一輪的搜索匹配。

（2）參數隨機策略。如在選定Bagl中的Prebag后，Bag2中與其搭配的Tipbag不一定只有一個，這時就需要隨機選取一個Tipbag，對于接下來的小包或元素選取也采用同樣的隨機方法，以確保組題步驟的連續性和隨機性，特別是對于有參數題干中參數的隨機生成。這要求使用一個運算速度快，分布均勻的隨機數發生器。

（3）語法語義判斷策略。由于組題完全由系統進行，在組裝出的試題中有可能存在誤差，有些可組裝試題不一定符合語法規則，或在答案鏈表中搜索不到可匹配答案，這要求丟棄該類試題，繼續進行其他的試題組裝。

（4）題型選擇策略。生成一道完整試題后，若給出可選答案，即為選擇題；若無可選答案，則為綜合題；若題干中含有空缺部分，則為填空題。

以上策略對于兩種類型的組裝方法都適用，接下來給出僅適用于題干視為參數型的組裝策略：①題干參數化策略：在這種類型中，將題干的位置視為參數，即可以隨機生成題干位置，一個題干既可作為問題約束部分，也可作為提出問題部分。例如將來自3個小包中的題干元素ai，bi，ci視為參數，既可以由ai>bi>ci連接方式形成一道題，也可由ai>ci>bi的連接方式形成一道題。這里將題干的位置參數化，并設為隨機。②問題題干截取策略：由題干組裝形成一完整試題后，隨機截取題干所給已知條件，并將所挖部分作為試題答案，以此生成選擇或填空題。

最后給出僅適用題干位置固定型的組裝策略：題干選擇策略，即當Bagi題干小包的元素不為空，并且從中可找到與Bagi-l小包的元素搭配的元素時，則選取該元素；依照Prebag->Tipbag->Quebag的次序進行題干選取，直到得到足以組裝成一道完整試題的若干題干，將其依序連接成一道完整試題。

2.3算法實現

在組裝試題時，分別從不同的Bagi中隨機選取元素小包，在不同的元素小包中隨機選取題干元素，依次進行人棧。之后依次取出入棧的題干元素，按順序進行鏈接，形成一道完整試題，然后進行語義語法分析，看是否為可用試題。若經過檢驗，則將試題放入題庫，然后對所得題干元素進行排列組合，選出符合語法規則的試題放入題庫（不包括之前得到的依序組裝的試題），以此實現組裝策略中的題干視為參數型的試題組裝；若沒有經過檢驗，所得試題不符合語法規則，則將棧頂的題干元素出棧，選擇其他的題干元素入棧，如此反復，得到試題庫。具體算法實現步驟如下：

算法2：試題組裝算法

Stepl：從Bagl中隨機選擇任一Prebagx；若為空，則組題過程結束；

Stcp2：若Prebagx非空，則從Prebagx中隨機選取元素am，將am入棧；若為空，返回Stepl；

Step3：從Bag2中搜尋可與am搭配的Tipbag小包，從搜尋結果中隨機選擇一Tipbagy；若為空，am出棧，返回Stcp2；

Step4：從Tipbagy巾隨機選擇元素bn，將bn人棧，若為空，返回Step3；

Step5：從Bag3 ff I搜尋可與bn搭配的Quebag小包，從搜尋結果中隨機選擇一Quebagz；若為空，6n出棧，返回Step4；

Step6：從Quebagz中隨機選擇元素ci，將Ci入棧，若為空，返同Step5；

Step7：獲取棧中元素，根據入棧順序連接元素am->bn->ci，進行語義分析，若符合語法規則，則將該題目中所含參數進行隨機具體化，并將其作為綜合題存入題庫；

注：由于整個組裝試題過程由程序來完成，試題是由幾個題干元素搭配而成，在連接成句時或多或少會存在語句不通，語義不搭的情況，所以連接后進行語義語法分析是必要的。只有符合語法語義規則，且符合問題邏輯的試題才可以作為可用試題存入題庫。

Step8：再將所得題干元素am，bn，ci視為參數，進行隨機排列組合，對所得每一種結果（除Step7中所得試題）進行語義分析，若通過檢驗，則隨機挖取題干元素所給已知條件，并將所挖部分作為試題答案，以此生成選擇或填空題存入題庫；出棧ci，返同Step6。

3、應用舉例

以數據結構中圖及樹的有關知識點為例，進行題干小包劃分，并實現題干組裝。

首先設置題干小包Bag/（這里取/=3）：對于Bagl，選取一元素Prebagl小包，Prebagl中元素為以“圖”及“樹”為范疇的知識點，記為ai；對于Bag2，其中可選擇元素為Tipbagl. Tipbag2，Tipbag3，Tipbag4，每個Tipbagi中包含若干可選元素，每一Tipbag中元素記為bij；對于Bag3，可選元素為Quebagl，Quebag2，Quebag3，每一Quebag/中含有可選元素，每一 Quebag中元素記為cij。

依據以上設置進行一部分的題干小包初始化，部分題干小包排列組合結構如圖l所示。

下面是一道試題的具體生成過程：

（1）隨機在Bagl中選取Prebag小包，獲得Prebagl小包，隨機取其中的元素，得到a3，并將其入棧；

（2）隨機在Bag2中選取可與元素a3搭配的Tipbag小包，獲得Tipbag2小包，隨機取其中的元素，得到62，并將其入棧；

（3）隨機在Bag3中選取可與冗素62搭配的Quebag小包，獲得Quebag2小包，隨機取其中的元素，得到c2；

（4）將元素a3，b2，c2出棧，依據人棧順序，將所得元素依次連接，組成一道試題，然后進行試題語義語法分析，若符合語法規則，則使用隨機數發生器具體化其中的參數圖G（V.E）及結點vi；

（5）將試題作為綜合題存入題庫。至此，通過依次在Prcbagl，Tipbag2，Quebag2小包中分別選取題十元素a3，b2，c2，再將這些元素依次連接成句，并具體化其中的參數，進而形成“已知圖Gl=（V，E）的鄰接表，依據最短路徑算法，找出vl到其余各頂點的最短距離”這道試題。

對圖1中題干排列組合進行分析，可得題干組裝試題為：

al～a6->bll～b12->cl；

a1～a6->b2->c2：

al～a2->c31～c32：

al～a7->b31～b32->c4；

a6->b31～b32->c5：

a8->b41～b43->c4：

總共可組合形成試題數：N=6×2×1+6×1×1+2×2+7×2×1+1×2×1+1×3×1=41道。這里只給定了某些題干小包的一部分元素，并且組裝過程未包括題干視為參數的組裝過程。可以想象，如果完整地將數據結構的所有知識點進行題干劃分，按照本文所述題干組裝方法進行試題組裝，將會動態得到數量十分可觀的試題。并且，在這些試題中，抽取出現重復的概率很小；除此之外，由于產生的試題難度相差不會過大，可以同時提高評測的隨機性和公平性。

4、結語

智能出卷測評系統的實現打破了傳統從固定題庫中抽取試題組成試卷的出卷方式，在增加試題數量的同時，也使得試題重復的概率極小，使得測評系統出題更加智能化，試卷組成更加多樣化，服務學生更加個性化。我們提出的測評系統仍存在不完善的地方，比如設計者分析搭配關系需要很大的工作量；在組裝試題過程中會出現不符合語法語義的試題等。

總之，此種智能測評系統不僅可以極大地方便和豐富學生的試題訓練，還可將其應用在服務于其他群體的網站測評系統中，從而為大眾提供更高質量的在線測評服務。