改進的基于知識點均衡的智能組卷方案

周千明，朱欣娟

（西安工程大學 計算機科學學院，陜西 西安710048）

計算機輔助教學CAI(Computer Assistant Instruction)是當前高等教育的重點工程，在線考試已經成為CAI的一個重要研究課題。智能組卷是在線考試的核心目標之一。目前智能組卷算法主要有隨機抽取法、回溯試探法以及遺傳算法[1]。決定組卷效率和試卷質量的主要因素有兩個：一是試題庫的結構；二是組卷算法的設計是否合理[2]。隨著在線考試智能組卷需求的提升，人們提出了一些基于知識點的組卷方案，這些方案在實際應用中取得了一定的效果，但仍存在一些問題與不足，歸納起來主要有：(1)在知識點的劃分中沒有明確區分元知識點與復合知識點，組卷時僅從元知識點著手，對于綜合試卷的組卷，容易造成所選擇的多數試題來自所屬科目的同一章節的元知識點，不符合實際要求；(2)在建立試題庫結構時缺乏對實際問題中題干及答案多樣性的分析處理；(3)沒有涉及到知識點出題數量的平衡策略，如在實際按章節范圍組卷中，當要求的出題數目大于或幾倍于限制知識點的數目時的處理策略。基于此，本文將在知識點的劃分、試題庫結構與算法實現上作一些探討，以期對今后組卷方案的設計與優化起到一定的借鑒作用。

1 知識樹的構建

知識點是教學活動過程中傳遞教學信息的基本單元，包括理論、原理、概念、定義、范例和結論等[3]。知識點可以分為元知識點和復合知識點，元知識點是不能再被分割的知識點，復合知識點是由若干個元知識點或復合知識點組成的知識點。知識樹(Knowledge Tree)是知識點及其關系的集合，即知識樹={知識點集合，知識點關系集合}，其中知識點關系集合是指知識點之間的父子關系集合[4]。根據知識體系結構，知識點的劃分一般以教材為基礎，采用細化的思想進行。從提高組卷效率的實際出發，將知識點按照科目的章節和內容自上而下劃分為3個層次，構建一棵深度為4的知識樹，如圖1所示。

知識樹根結點為科目名稱，除根結點之外的所有結點為各級知識點，分為一、二、三級。對于不同的科目，各級知識點可以有不同的表征。一、二級知識點可分別表征為相應科目的章、節，三級知識點可表征為章節下的元知識點。一般地，一、二級知識點最多下轄20個左右下級知識點。因此，設定每個結點最多可以有26個孩子結點，用字母A到Z表示。為了便于處理，除根結點之外的所有結點統一采用4個字符編碼，編碼的最后一個字符為“*”。由于各級知識點的孩子結點數目存在差異，當葉子結點的層次不足3時，編碼時在后面追加字符“*”以補足編碼。例如，圖1中二級知識點C編碼為AC**，三級知識點 A編碼為 ACA*。

2 試題庫結構的設計

建立合理的試題庫結構是實現智能組卷的重要環節。為了客觀全面地反映試題固有的特征，試題庫結構的建立必須綜合考慮以下方面因素：

(1)各類題型格式的多樣性。題型格式的多樣性主要體現在：一部分試題只有1個問題，而另一部分試題則囊括2個或更多的子問題。前者如傳統的單項選擇題、只有1個空的填空題等；后者如英語試卷的閱讀理解題、含有多個空的填空題等。

(2)試題答案可能不唯一，并且答案出現位置可能具有不確定性。這種情況主要體現在填空題上。例如有以下試題：“數據庫的三級模式結構是指數據庫系統是由____、____和 ____三級構成?！贝鸢甘恰巴饽Ｊ?內模式;模式”，但各答案的位置不確定，具體有=6種情況。再如有以下試題：“面向對象的三大特征是 ____、____和 ____?！贝鸢缚梢允恰胺庋b性;繼承性;多態性”，也可以是“封裝;繼承;多態”，并且各答案位置也不確定。這就明顯為試題庫的建立增加了難度。

(3)便于智能組卷。建立試題庫是以智能組卷為出發點，必須為智能組卷提供便利。

綜合上述因素考慮，設計試題庫結構如圖2所示。

試題的屬性有試題 ID、題型 ID、試題內容、試題擴展、試題分值、難度等級、是否試題組、估計用時、曝光度、知識點ID及科目ID。其中，題型包括選擇題、填空題、判斷題與問答題。選擇題又包括單選題、多選題和不定項選擇題。計算題、分析題、設計題、敘述題等均可以歸到問答題中。試題內容和試題擴展共同體現整個試卷完整的試題內容。擴展內容、答案、答案擴展作為試題擴展的屬性存在。難度等級包括簡單、基本、中等、較難、難題 5個級別，分別用整型常數 1、2、3、4、5 表示。是否試題組標識該試題是否囊括兩個或兩個以上的子問題。曝光度反映了試題被選中使用的次數，曝光度越大說明在以往的試卷中該題被考的次數越多[5]。 曝光度設為整型常數-1、0、1、2、3、4。組卷時在曝光度為0到4的試題中選題，對選中的試題使其曝光度遞增。每次組卷結束后，修改試題庫中曝光度為-1與5的試題，曝光度為-1的增加為0，以進入下次組卷選題范圍；曝光度為5的重置為-1，避免其下次組卷時被選中。試題內容有文字內容和圖形內容，相應的試題答案也有文字內容答案和圖形內容答案[6]。在試題庫中以記錄的形式組織上述的數據結構。

3 組卷控制參數的確立

組卷控制參數表征組卷的要求，由系統界面人機交互的方式獲得。本文采用的組卷控制參數有考試科目、題型、題型的知識點(可選)、題型的題量、題型的分值分配、題型的時間分配、試卷平均難度等級以及試卷允許時間誤差。

其中，為了滿足實際中諸如單元試卷、期中試卷、期末試卷、專題試卷等不同形式的組卷需求，設定題型的知識點為可選的組卷控制參數。組卷人員可以根據實際需求靈活地指定考試科目相應知識樹中的一級知識點、二級知識點、三級知識點或它們的任意組合，也可以不指定任何知識點，系統在組卷時將根據下文所述的知識點均衡策略進行知識點均衡。

4 智能組卷方案的實現

4.1 知識點均衡策略

為了保證組卷最大限度地趨近真實效果，知識點均衡很關鍵。本文采用如下策略在組卷過程中對各題型進行知識點均衡，結合圖1所示，下面分兩種情況討論：

圖3 知識點均衡核心策略簡圖

(1)當組卷人員沒有指定知識點時，按圖3所示策略實施。首先遍歷考試科目對應的知識樹，檢索該科目中一級知識點的數目，然后再依次檢索隸屬于每級知識點的下一級知識點的數目，分別存入到數組中。然后根據題型的題量確定該題型的各級目標知識點及相應的目標題量，步驟如下：

①設考試科目的一級知識點數目為K1，題型的題量為 Q1， 首先求得 Q1相對于 K1的倍數 M1與余數 R1：M1=Q1/K1；R1=Q1%K1；然后進行相應的判斷。 若 M1=0，則在這K1個一級知識點中隨機選擇R1個作為目標一級知識點，再分別在以這R1個目標一級知識點為根結點的子樹的所有葉子結點中隨機選擇1個知識點作為目標三級知識點，各目標題量為1，知識點均衡結束；若M1>0，并且 R1=0，則這K1個一級知識點均作為目標一級知識點，各目標題量為 M1；若 M1>0，并且 R1>0，則這 K1個一級知識點仍均作為目標一級知識點，再在目標一級知識點中隨機選擇 R1個，各目標題量為 M1+1，剩下的目標一級知識點的目標題量均為M1。

②若步驟①中的“M1>0，并且 R1=0”或“M1>0，并且R1>0”成立，用步驟①中同樣的策略逐級進行知識點均衡。

(2)當組卷人員指定知識點時，按以下策略實施：

①若組卷人員指定的知識點既有知識樹中的葉子結點(設其數目為X)，又有非終端結點，則首先遍歷考試科目對應的知識樹，檢索以這些非終端結點為根結點的子樹對應的葉子結點的數目(設其總數目為Y)，設題型的題量為Q，然后求得Q相對于X+Y的倍數M：M=Q/(X+Y)。若M=0，則對于葉子結點構成的目標知識點，各目標題量為1，對于非終端結點，分配題量為 Q-X，再按(1)中策略進行均衡；若M>0，則對于葉子結點構成的目標知識點，各目標題量為M；對于非終端結點，分配題量為Q-M，再按(1)中策略進行均衡。

②若組卷人員指定的知識點全部為知識點樹中的葉子結點，仍按(1)中策略進行均衡。

4.2 算法描述

經過知識點均衡之后，組卷控制參數中的考試科目、題型、題型的知識點(可選)、題型的題量4項已滿足要求。為了最大限度地滿足所有組卷控制參數的要求，在組卷過程中，各題型的選擇順序應按平均分值從大到小的順序進行，優先選擇試題平均分值高的題型。組卷的具體算法如下：

定義general_d表示試卷當前實際難度等級，初值賦為0；question_d表示當前選擇的試題的難度等級；direct_d表示難度等級調節方向；定義general_s表示試卷當前的總分，初值賦為0；question_s表示當前選擇的試題的分值；direct_s表示分值調節方向；定義 question_t表示當前選擇的試題的估計用時；direct_t表示時間調節方向；各調節方向的調節規則均為：取1時表示向上調節，取0時表示向下調節，取-1時表示暫時不調節。

(1)對組卷人員提出的組卷要求進行合理性驗證。

(2)確定各題型的選擇順序。對各種題型，比較它們組卷控制參數中的平均分值 (題型的分值分配/題型的題量)的大小，確定其大小順序，該順序即為各題型的選擇順序。

(3)進行知識點均衡。采用上文所述的知識點均衡策略實施，確定最終的各目標知識點及目標題量。

(4)按照組卷控制參數與確定的目標知識點及目標題量，從試題庫未選擇的試題中隨機選題。定義各種題型的已選試題數組，每選擇一道題，將其試題ID存入相應題型的已選試題數組中，并按以下方法修改或調整相關定義的參數的值[6]：

①難度系數調節方向direct_d的調整：

②分值調節方向direct_s的調整：

③時間調節方向 direct_t的調整：

(5)所有題型的試題選擇完成之后，整體上對試卷的平均難度等級、總分和總時間進行核對及相應優化調整。通過反復地組卷試驗發現，試卷的平均難度等級基本得到滿足，需要進行微調的一般是總分及總時間。在保證試題其他屬性不變的情況下，可以采用試題庫中相應的試題替換試卷中個別試題的辦法進行試卷優化調整。

(6)算法結束。

本文針對現有的基于知識點組卷方案存在的問題與不足，提出了一種改進的基于知識點均衡的智能組卷方案。通過多次試驗，證明了該方案具有較高的有效性和魯棒性。將該方案分別應用到學校針對在校學生的在線考試系統與企事業單位的在線考試系統中，知識點覆蓋與分布合理，滿足試卷平均難度等級、分值分配、時間分配等要求，取得了比較理想的效果。

[1]王友仁，張砦，施玉霞，等.題庫系統智能成卷理論和組卷方法研究[J].電子科技大學學報，2006，35(3)：363-366.

[2]王雍鈞，黃毓瑜.基于知識點題型分布和分值的智能組卷算法研究[J].計算機應用與軟件，2004，21(8)：111-113.

[3]施岳定，張樹有，項春.網絡課程中知識點的表示與關聯技術研究[J].浙江大學學報(工學版)，2003，37(5)：508-511.

[4]黃萬艮.基于知識樹的多媒體課件[J].中國教育信息化，2009(7)：56-58.

[5]林雪明，張鈞良，蔣偉鋼.基于知識點的試題庫組卷算法的建立[J].微機發展，2001，11(2)：77-80.

[6]周文舉.一種基于知識點的遺傳算法組卷的改進應用[J].山東師范大學學報(自然科學版)，2006，21(3)：39-42.