自動組卷系統(tǒng)試題難度和知識點覆蓋控制算法

柳浪濤，谷 林

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

0 引 言

題庫管理系統(tǒng)的自動組卷功能在教學活動中可以減輕教師出卷的工作負擔，能夠科學、全面考核學生的學習成績，及時反饋學生對知識的掌握情況，提高教學質(zhì)量［1－4］.自動組卷通常需要按照組卷人對試卷的要求設(shè)置基本信息（題型，各題型對應(yīng)題目的數(shù)量，題型的難易等級，每道題目的分值），然后依照設(shè)置生成一套符合要求的試卷［5－6］.

題庫管理系統(tǒng)中能夠?qū)崿F(xiàn)自動組卷的核心是自動組卷的算法.目前已有不少學者對此類算法進行了研究，文獻［7］以分類的方法將試題庫全集劃分成若干個子集，并且把將要生成試卷的試題按一定的規(guī)則分解成不同的試題子集，然后針對不同的試題子集隨機抽取指定數(shù)量的試題，此算法縮小了隨機抽題的范圍，并且在一定條件下提高了組卷的效率，但是在約束條件變少，導(dǎo)致劃分的試題子集也減少的情況下，對試題的抽取難以實現(xiàn)精確控制；文獻［8］提出了基于線性遞減系數(shù)粒子群優(yōu)化算法策略，試圖避免粒子群優(yōu)化算法在組卷過程中陷入局部最優(yōu)的困局，但本質(zhì)上是調(diào)整了粒子群優(yōu)化算法的慣性系數(shù)，使得算法中的步長減小，這只會減小組卷過程中出現(xiàn)局部最優(yōu)問題的概率，但不能從根本上避免粒子群優(yōu)化算法中的局部最優(yōu)問題；文獻［9］在實現(xiàn)組卷的過程中依靠蟻群算法的快速和智能搜索能力，先對建立的數(shù)學模型進行求解，然后得到最優(yōu)組卷方案進行組卷.

文中研究的組卷算法綜合考慮了組卷人對試卷各指標（難度、章節(jié)、知識點）的設(shè)置，在組卷過程中系統(tǒng)依照“卷內(nèi)分塊、組塊分層”的機制將被組的試卷按照題目的類型分成若干個題型塊，并且在算法實現(xiàn)過程中將每一個塊分成數(shù)據(jù)層、處理層、存儲層.系統(tǒng)會在處理層完成每一個題型塊的所有組卷操作，每當一個題型塊的組卷動作完成，系統(tǒng)會將被組卷模塊的難易等級與設(shè)置的參數(shù)進行比較，如果分析的結(jié)果和設(shè)置的參數(shù)一樣則此模塊的組卷完成，進行下一個模塊的組卷動作，否則系統(tǒng)要不斷調(diào)整處理層數(shù)據(jù)的難易等級，向被設(shè)置的參數(shù)逐漸逼近直到相等為止.

1 設(shè)計思想

將題目的知識點和難易程度作為組卷過程的兩個因素，為了對其進行有效控制，所定義的題庫信息如表1所示.其中，知識點用于說明題目所屬章節(jié)信息，它是出卷時進行知識點覆蓋規(guī)則匹配的一個重要參數(shù).將試卷本身看成一個整體研究對象，其組卷過程如式（1）所示：

表1 題目信息表Table 1 Title information

式中，P表示一個對象的組卷，Q表示成功組成一套試卷的所有動作，F(xiàn)表示只考慮難易程度（H），知識點（K），題目類型（T）3因素的組卷動作，f1（H，K，T）表示對此模塊進行第一次有關(guān)難易程度（H）、知識點（K）、題目類型（T）的驗證操作，Qt表示對同種類型題目的知識點和難易程度進行平衡操作，其中fs（H，K，T）中s由其迭代的次數(shù)決定.依照此方法實現(xiàn)系統(tǒng)的組卷，由于要將題型、知識點、難易等級綜合考慮在內(nèi)，所以涉及的內(nèi)容廣，實現(xiàn)起來對程序員的要求高，并且由于程序的嵌套導(dǎo)致系統(tǒng)的效率不高.

按卷內(nèi)分塊和組塊分層的機制把一套完整的試卷按照題目類型分成若干個模塊，再將每一個模塊看成一個對象，其次再把每個對象分成3個層次：首先，處理層根據(jù)隨機函數(shù)從數(shù)據(jù)層取出對應(yīng)數(shù)量的題目（數(shù)量的大小在試卷的指標信息表里獲取，其中試卷的指標設(shè)置如表2所示），再將當前題型塊的難易等級（其中難易等級的計算如式（4）所示）與試卷指標里設(shè)置的難易等級進行比較，如果相等表示此模塊的組卷動作完成，并且將處理層數(shù)據(jù)存入到存儲層，否則執(zhí)行處理層的組卷均衡動作，如式（2）所示.

表2 試卷指標信息Table 2 Papers index information

式（2）所描繪的是單個對象在處理層的驗證過程，G表示此次組卷的所有動作，g1（H，U）表示對此模塊進行一次有關(guān)難易程度（H）、知識點（K）的驗證操作，gn（H，K）表示對當前模塊信息進行n次查詢?nèi)缓笈c組卷要求進行比較，如果不符合組卷要求則要剔除相應(yīng)題目，然后重新來組織此模塊，其中n的大小是由驗證次數(shù)決定.要想依照此設(shè)計思想完成組卷，關(guān)鍵點就在于對試卷難易等級的測量.

2 難易等級測量

為了衡量大多數(shù)人的學習情況，難易等級是按照正態(tài)概率分布思想來劃分的，各個等級的概率分布如圖1所示.圖1中不同難易等級的值是將標準正態(tài)分布在－2σ，－σ，σ，2σ處分割成5塊，分別取各塊所占面積的近似值，其中容易和難各占2.5%，較易和較難各占13.5%，中等占68%.同時，在估計某種題目類型的難易程度時依照統(tǒng)計學中均值的思想，以百分制為例，系統(tǒng)分別給這5個等級賦予一組不同的估計系數(shù)，其系數(shù)的估計公式如式（3）所示：

圖1 等級概率分布圖Fig.1 Level probability distribution

式中，Yn表示第n等級的估計系數(shù)，Xk表示第k等級在概率分布圖中所占的比重.圖1中從右往左5個等級的估計系數(shù)分別是0.987 5，0.917 5，0.51，0.092 5，0.012 5.系統(tǒng)通過計算所有題目的分數(shù)所對應(yīng)的均值來估計同一試卷的難易等級.其估計公式如式（4）所示：

式中，Xk表示第k個題目的分數(shù)，Yn表示當前題目的難易等級系數(shù)，Z是最終計算獲得的一個統(tǒng)計分值，通過查看Z值落在的等級區(qū)間即可獲得試卷的難易等級.其中試卷的等級區(qū)間是依靠難易程度所占的比重來計算的.以總分為百分制的試卷為例，易等級所占比重為2.5%，所以它的分值的區(qū)間就是［0，2.5］，其他等級依次類推.

3 算法實現(xiàn)

本算法優(yōu)先考慮組卷人對試卷的指標設(shè)置，在滿足試卷指標設(shè)置的情況下，通過難易等級分析公式對組成的試卷進行難易等級分析，如果分析的結(jié)果不滿足組卷要求則調(diào)用均衡難易等級的方法調(diào)整組成的試卷，否則執(zhí)行下一模塊的組卷.算法主要過程如下：

（1）初始化數(shù)組a［4］［4］用于存放組卷人對試卷的指標設(shè)置信息，初始化標簽i設(shè)置初始值0，用于訪問第i行指標a［i］［0］到a［i］［3］的數(shù)據(jù).初始化3個緩沖區(qū)tempor List、title List、examation List分別用于存儲組卷過程中數(shù)據(jù)層、處理層、存儲層數(shù)據(jù).

（2）從a［i］［0］到a［i］［3］中取出第i行的數(shù)據(jù)，按照取出數(shù)據(jù)的要求（試卷指標）從數(shù)據(jù)庫里面獲取對應(yīng)的題目（此題目類型中，不同知識點的不同難易等級題目各兩道）信息存入tempor List，然后從tempor List里隨機獲取指定數(shù)量（在存儲指標的數(shù)組中獲?。┑脑囶}存入title List.

（3）調(diào)用式（4）估算title List中試題的難易等級，如果比要求高（低）執(zhí)行步驟（4），否則執(zhí)行步驟（5）.

（4）從title List中剔除高于或等于（低于或等于）的一道試題，從tempor List里面找出難易等級為次高（次低）的且title List中沒有此知識點的試題.如果還高（低）跳轉(zhuǎn)到步驟（3）.如果出現(xiàn)低（高）跳轉(zhuǎn)到步驟（6），表示試題不足不能組卷.

（5）將title List數(shù)據(jù)存入examation List（就是存放整個試卷的試題），如果標簽i的值小于4（題目類型只有4種），標簽i的值加1，然后跳轉(zhuǎn)到步驟（1），否則跳轉(zhuǎn)到步驟（7）.

（6）輸出提示，試題不足不能完成組卷.

（7）將titleList中試卷打出組卷完成，結(jié)束.

3.1 算法的關(guān)鍵代碼

3.2 實驗結(jié)果與組卷結(jié)果分析

實驗針對一般隨機算法和文中描述算法，在同一難易等級的題目數(shù)量不變，組卷中分別取題目數(shù)量為15，19，20，21，25的條件下完成.實驗結(jié)果統(tǒng)計如圖2和圖3所示，根據(jù)數(shù)據(jù)表明，依靠一般隨機算法實現(xiàn)組卷成功與否只取決于題庫里試題的數(shù)量，但是組卷結(jié)果符合組卷要求的概率比較低.圖3中實驗五的成功率沒有達到100%，究其原因發(fā)現(xiàn)，在題庫中只有20道題目的難易等級為“容易”，不能組成具有25道題目且難易等級為“容易”的試卷，從而造成組卷失敗.但是在真實的組卷環(huán)境下，題庫中題目數(shù)量會遠遠大于要組試題的數(shù)量，所以不會出現(xiàn)類似于圖3中實驗五的情況.

圖2 一般隨機算法實驗結(jié)果圖Fig.2 General stochastic algorithm test results

圖3 文中描述算法實驗結(jié)果圖 Fig.3 Algorithmic test results

表3是使用一般隨機算法和文中所述算法實現(xiàn)要求難度為“較難”的組卷結(jié)果分析表.由表3看出，一般隨機算法的試卷難易等級為“中等”，不符合組卷中難度的等級要求，并且存在知識點重復(fù)（同一章節(jié)號的多道題目）的現(xiàn)象，而文中描述算法的組卷結(jié)果，難度等級為“較難”符合組卷要求，并且克服了知識點重復(fù)現(xiàn)象.因此綜合對以上2種算法的實驗結(jié)果與組卷結(jié)果可知，文中描述的組卷算法，組卷結(jié)果更加合理.

表3 結(jié)果分析Table 3 Result analysis

4 結(jié)束語

本文采用“卷內(nèi)分塊、組塊分層”的組卷機制，設(shè)計了一套完整的自動組卷算法.經(jīng)過實驗并與一般隨機算法對比分析，證明此算法在試卷難度和知識點覆蓋控制方面具有良好的改進效果，并且系統(tǒng)運行速度較快、組卷效率較高.

［1］ 李麗，陳未如，王翠青.通用職能題庫管理系統(tǒng)的研究與實現(xiàn)［J］.沈陽化學學院學報，2005，19（3）：236－240.LI Li，CHEN Weiru，WANG Cuiqing.Study and realization of general intelligentItem bank system［J］.Journal of Shenyang Institute of Chemical Technology，2005，19（3）：236－240.

［2］ 夏萬東，藏玉紅，齊曉旭，等.通用試庫管理系統(tǒng)的設(shè)計與實現(xiàn)［J］.承德石油高等?？茖W校學報，2014，16（3）：44－47.XIA Wandong，ZANG Yuhong，QI Xiaoxu，et al.Design and implementation of general test questions library managenebt system［J］.Journal of Chengde Petroleum College，2014，16（3）：44－47.

［3］ 龍草芳，肖衡.試題庫建設(shè)與組卷算法研究［J］.電腦知識與技術(shù)，2013，13（9）：2955－2959.LONG Caofang，XIAO Heng.Research on design of test database and algorithm of examination paper［J］.Journal of Computer Knowledge and Technology，2013，13（9）：2955－2959.

［4］ 楊勛.在線考試系統(tǒng)的組卷算法研究［J］.電腦知識與技術(shù)，2014，10（32）：7621－7623.YANG Xun.Research on the test paper composition algorithm of online examination system［J］.Computer Knowledge and Technology，2014，10（32）：：7621－7623.

［5］ 趙靜雅，高斐，高震宇.在線考試系統(tǒng)自動組卷算法研究［J］.電子制作，2014（8）：282－283.ZHAO Jingya，GAO Pei，GAO Zhenyu.Research of auto generating test paper algorithm of online examination system［J］.Electronic Production，2014（8）：282－283.

［6］ 陳曉敏，梁靜，葛宇.基于改進遺傳算法的智能組卷研究［J］.西南師范大學學報：自然科學版［J］.2012，37（5）：98－101.CHEN Xiaomin，LIANG Jing，GE Yu.On intelligent test paper auto－generation based on improved genetic algorithm［J］.Journal of Southwest China Normal University：Natural Science Edition，2012，37（5）：98－101.

［7］ 呂東哲，蘇烈華.基于分類隨機算法的試卷生成算法研究［J］.計算機光盤軟件與應(yīng)用，2014（8）：190－191.LYU Dongzhe，SU Liehua.Based on the papers random generation algorithm classification algorithm［J］.Computer CD Software and Applications，2014（8）：190－191.

［8］ 白雁.基于線性遞減系數(shù)粒子群優(yōu)化算法的組卷實現(xiàn)［J］.現(xiàn)代電子技術(shù)，2014，37（24）：41－44.BAI Yan.Implementation of test paper generation based on particle swarm optimization algorithm with linear decreasing inertia weight［J］.Modern Electronics Technique，2013，37（24）：41－44.

［9］ 劉毅.人工智能在自動組卷建模中應(yīng)用研究［J］.計算機仿真，2011，28（8）：385－388.LIU Yi.Auto－generating test paper based on artificial intelligence［J］.Computer Simulation，2011，28（8）：385－388.