基于自適應決策支持技術的研究生 在線考試系統的設計與實現

(曲阜師范大學 計算機科學學院， 山東 日照276826)



摘 要：

設計并實現的研究生在線考試系統以遺傳算法和ID3經典算法為基礎，采用四層體系架構，除包括考試系統的基本功能外，還具有自動組卷、試題難度系數自適應學習和面試決策支持功能，同時實現了數據倉庫數據的來源處理過程和應用處理過程，充分體現了自適應決策支持技術的優越性。

關鍵詞：自適應學習； 決策支持； 難度系數； 遺傳算法； ID3算法

中圖分類號：TP273 文獻標志碼：A

文章編號：1001-3695(2009)02-0637-04



Design and implementation of postgraduate online exam system based on self-adaptive decision-making supported technology



YAN Wei， CAO Bao-xiang， XIA Xiao-na

（College of Computer Science， Qufu Normal University， Rizhao Shandong 276826， China）



Abstract:This paper designed and implemented the postgraduate online exam system designed and implemented which was on the basis of the genetic algorithm and ID3 algorithm， adopted the four-tier architecture， and includeed generating examination paper automatically， studying the difficult coefficient self-adaptively and interview decision supporting except for the basic functions of the exam system. It carried out the process of source’s disposition and application’s disposition and embodies sufficiently the advantages of the self-adaptive decision-making supported technology.

Key words：self-adaptive study; decision-making support; difficult coefficient; genetic algorithm(GA); ID3 algorithm



人類已經進入21世紀，科學技術突飛猛進，知識經濟和信息產業初見端倪，特別是信息技術與網絡技術迅速發展和廣泛應用，對社會政治、經濟、軍事和文化等領域產生越來越深刻的影響。作為計算機應用的一部分，使用計算機對研究生招生進行管理，有著手工管理所無法比擬的優點，如檢索迅速、查找方便、可靠性高和存儲量大等。

一個比較完善的研究生在線考試系統可以允許根據需要自動從題庫抽取試題，進行動態組卷，保證筆試和面試能夠公平、公開地進行，從而使考試結果更符合實際情況。

1 基于自適應決策支持技術的研究生在線考試系統的設計與實現

1. 1 背景

目前，已經有不同類型的在線考試系統，但這些考試系統在一定程度上還存在這樣或那樣的問題，主要可以歸納為如下幾個方面：

a)雖然試題的難度系數可以由經驗豐富的教師預先設定，但靠經驗指定必定有誤差，由于受主觀和客觀因素的影響，不可避免地會帶來估計的偏差；

b)多次進行的考試之間是完全孤立的，沒有進行比較的標準，不利于出題人員進行統計分析以調整試題難度；

c)不具備面試模塊，或者是其設計沒有充分考慮實際情況，從而使整個考試難以公平、公正地進行；

d)無法保證筆試過程的安全性和保密性。

本文所設計的研究生在線考試系統，應用當前流行的自適應學習、決策支持和數據倉庫技術，實現了基于題庫的試題難度系數自適應學習和基于數據挖掘的面試決策支持功能。

1. 2 試題難度系數自適應學習

試題的難度系數是比較各套試題庫難易程度的重要標準，但它會因考試群體的不同而不同，因此很難通過經驗得出。本文提出的研究生在線考試系統，根據Bernoulli大數定律和機器學習思想，充分利用網絡的高速性，自適應學習并計算出試題庫的難度系數。該難度系數具有考試群體規模越大，結果越接近現實的統計特性。

1.2.1 Bernoulli大數定律

Bernoulli大數定律：設nA是n次獨立重復實驗中事件A發生的次數，P是事件A在每次實驗中發生的概率，則對于ε＞0，有limn→∞P{|nA/n-p|＜ε}=1。

Bernoulli大數定律表明，事件發生的頻率nA/n依概率收斂于事件的概率P，即當n很大時，事件發生的頻率與概率有較大偏差的可能性很小。由實際推斷原理，在實際應用中，當實驗次數很大時，便可以用事件發生的頻率代替事件的概率。

1.2.2 難度系數自適應學習

對于研究生在線考試系統而言，考生是相互獨立的，并且獨立地做出答案。每道試題只有一個考核點，采用答對得分答錯不得分的閱卷模式。設某試題累計得分次數為Ns，該試題被選中的次數為N，則該試題到目前為止得分率為qk=Ns/N。

根據Bernoulli大數定律，當考試次數N趨于無窮時，qk將以概率1接近得分概率q。

在系統中，以課程為單位來統計難度系數。一般情況下，每門課程試題庫有多于一道的試題，則該課程的得分概率就是所包含試題的得分概率的期望概率，即q=1/M∑Mi=1qi。其中，M為該課程的試題數量，各試題之間是線性無關的，即是獨立的。

該課程試題庫的難度系數d可由其得分概率q得到，即d=1-q。

在研究生在線考試系統中，每當考生答卷和提交答案時，系統會對考生提交的考試結果進行自學，即重新計算難度系數，并修改對應試題的難度系數因子，以適應當前考生的實際解題能力。隨著考生人數和考試次數的增加，難度系數逐步逼近實際情況。

自適應學習各門考試課程的難度系數，一方面為出題人員調整試題庫提供標準；另一方面，將每次考試統計分析得到的難度系數作為數據倉庫的數據來源，利用數據挖掘技術，對研究生在線考試的課程調整、篩選等方面發揮積極的指導作用。

難度系數自適應處理過程如圖1所示。本系統實現的難度系數自適應學習的處理界面如圖2所示。

1. 3 面試決策支持

研究生在線考試系統的主要功能模塊是筆試和面試。筆試由于設計成系統自動處理，能夠保證這一模塊的公平性和安全性；而面試加入了面試考官的主觀因素，如何能夠使面試過程更為順利、公正地進行，是很多考試系統主要面臨的問題。

針對以上問題，本文考試系統提出了考生評價模型，并基于該模型和數據挖掘技術設計并實現了面試功能模塊。

1.3.1 考生評價模型

在考生評價模型中，不同級別的面試考官對決定考生面試成功的各因素，即影響因子進行分別評價，將各因素評價值加權求和[1]。具體步驟包括：首先求出每個面試考官對某考生的評價值；再求出各級別面試考官對某考生的評價值均值；然后將各級別面試考官對考生評價均值加權求和，得出考生的最終評價值。

考生評價模型的符號表示如下：設影響因子ai的權重為bi(i=1，2，…，I)，面試考官分為J個級別，第j級別的面試考官對考生評價結果的影響權重為cj(j=1，2，…，J， cj≤0.5)，有dj個第j級別的面試考官對考生作出評價，ejk為其中的第k(k=1，2，…，dj)個，ejk對考生影響因子ai的評價值是fjki，考生的最終評價值為L，且有L=∑Jj=1cj[1/dj∑djk=1(∑Ii=1bifjki)]。

1.3.2 影響因子判定自適應

面試過程中影響因子的選擇是面試功能模塊中最為重要的環節之一。本文所設計的研究生在線考試系統將以歸納學習策略中ID3經典算法[2]為核心，實現數據挖掘技術，并完成影響因子判定問題。

由Quinlan提出的著名的ID3算法，是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現對數據的歸納分類。經典ID3算法的主要步驟是：

a)對數據進行規范化處理;

b)選取訓練實例集;

c)利用信息增益度選取最能區別訓練集中實例的屬性;

d)創建一個樹節點，并創建該節點的子鏈，每個子鏈代表所選屬性的一個惟一值，使用子鏈的值進一步細化子類，當出現以下兩種情形之一時可以停止分類：

(a)一個節點上的數據都是屬于同一類別；

(b)沒有屬性可以再對屬性進行分割。

研究生在線考試系統中，需要在大量統計數據的基礎上通過ID3算法，實現對影響因子的選擇。因此，首先選擇非類別屬性，本系統以四個屬性(A，B，C，D)為例，它們分別是：A表示考生專業知識是否合格；B表示考生動手能力是否合格；C表示考生應變能力是否合格；D表示考生非專業知識是否合格。

首先選取影響因子選擇的訓練實例集，對數據進行規范化，這里0表示不合格，1表示合格，然后通過分析大量的考生關于影響因子面試結果的訓練實例，利用信息增益度選取最能區別影響因子訓練集中實例的屬性。這里根據考試人群的不同而不同，可能是A、B、C、D中的一個。將選擇的影響因子的非類別屬性作為決策樹的樹節點，開始創建該節點的子鏈，每個子鏈代表所選屬性的一個惟一值[3]。當出現以下情形之一時即可停止：

a)一個節點上的數據都屬于同一類別，例如，如果考生動手能力合格，則考生專業知識合格的準確率高達98％；

b)沒有屬性可以再對屬性進行分割[3]。

以上分析過程形成了如圖3所示的決策樹。其中，0/1表示分支條件。

通過以上對大量面試結果中影響因子選擇的訓練實例的分析，能夠得到一系列的結構和規則，

進而能判定各影響因子。例如，統計數據顯示，在120個進行面試的考生中，有100個動手能力合格，并且在這100個考生中，有95個反應能力也合格。因此，可以得出規則“if動手能力合格then反應能力也合格”，準確度為95％，覆蓋率＝100/120＝83％。以上規則說明，對于大部分考生，考察動手能力和反應能力存在重復，所以有必要取消其中對反應能力的考察。

對研究生在線考試系統進行初始化時，可以設置遠遠大于實際個數的影響因子，然后通過執行ID3算法，產生一個根據區別能力依次排列的影響因子列表和一系列關于各影響因子的規則；根據規則，首先淘汰具有重復作用的影響因子，然后按照影響因子列表順序依次保留最有能力區別考生的強影響因子。這樣，保證了經過ID3算法產生的各影響因子相互間的聯系最小，并且每個影響因子能夠在最大程度上區別不同的考生，同時將面試結果的統計數據重新應用于面試影響因子的判定，完成了影響因子的自適應判定。

1.3.3 面試評判標準自適應學習

與面試影響因子判定相似，面試評判標準也需要經過長期統計和實驗得出。在本系統的設計過程中，使用遺傳算法（GA）作為數據挖掘技術的核心算法，將大量對應于各種標準所得出的統計數據通過數據挖掘技術產生能夠指導面試過程的最優評判標準，進而使面試根據最優評判標準更合理地進行。

遺傳算法是由美國Michigan大學J.Holland教授于1975年提出，它是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型[4]，是一種通過模擬自然進化過程搜索最優解的方法。

遺傳算法把問題的解表示成染色體，在算法中也即是以二進制編碼的串。在執行遺傳算法之前，給出一群染色體，即假設解；然后，把這些假設解置于問題的環境中，并按照適者生存的原則，從中選擇出較適應環境的染色體進行復制，再通過交叉、變異過程產生更適應環境的新一代染色體群。這樣，一代一代地進化，最后就會收斂到最適應環境的一個染色體上，它就是問題的最優解[5]。

根據GA的算法思想和步驟，面試評判標準的自適應學習過程如下：首先，將各評判標準轉換為二進制串表示形式，即染色體表示，如評判標準0.64對應二進制串1000000，根據實際情況，這里選擇七位二進制串就可以完全表示所有評判標準，同時隨機選擇問題的假設解集合ai（i=1，2，…，n），一般n取30~160；然后，根據適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則，適應度準則體現了適者生存，不適者淘汰的自然法則。結合本系統的實際情況，設計適應值函數f(ai)=M/|M-N|。

其中：M為面試擬定錄取人數；N為評判標準ai所對應的統計合格人數。以P(ai)表示選中ai為下一代個體的次數，并且滿足：

P(ai)=f(ai)/∑nj=1f(aj)×n



其中：n為假設解集合的規模。顯然，從上式可以得出：

a)適應度較高的個體，繁殖下一代的數目越多，即在本系統中，面試評判標準對應的合格人數越接近實際擬定的錄取人數，這種評判標準越接近于最優；

b)適應度較低的個體，繁殖下一代的數目較少，甚至被淘汰，即如果由面試評判標準產生的合格人數與實際擬定人數相差很大，則該評判標準可能被淘汰。

這樣，就產生了對面試環境適應能力較強的后代，即產生符合面試擬定人數的評判標準。

接下來，對選出的下一代評判標準要應用交叉算子(crossover)和變異算子(mutation)，確保能夠在更大規模上窮盡所有可能的解方案，實現真正意義上的全局最優解。在具體實現時，各算子操作對象均為二進制串，該過程有利于將問題離散化。其中，交叉算子將被選中的兩個個體的基因鏈按概率Pc進行交叉，生成兩個新的個體，交叉位置是隨機的，Pc一般取0.25~0.75；變異算子(mutation)將新個體的基因鏈的各位按概率Pm進行變異，對二值基因鏈(0，1編碼)來說即是取反，Pm一般取0.01~0.2。經過交叉和變異過程，解集合中會出現新的評判標準供以后選擇。最后，當最優評判標準的適應度達到給定的閾值，或者最優評判標準的適應度和群體適應度不再上升時，則迭代過程收斂，遺傳算法結束；否則，用經過選擇、交叉、變異所得到的新一代評判標準群體取代上一代群體，并返回到選擇操作處繼續循環執行。

現以由四個隨機產生的評判標準組成的初始種群為例，實現算法步驟如下：

a)初始化。初始種群如表1所示。

表1 初始種群

編號染色體表示aif(ai)P(ai)編號染色體表示aif(ai)P(ai)

101000000.322.51.0310000100.661.61.0

210000000.645.02.0410001000.681.20.0

并有max f(ai)=5.0， E(f(ai))=∑f(ai)/4=2.6。

b)選擇。根據P(ai)得到新的群體為{1000000，0100000，1000010，1000000}。

c)交叉。設交叉率為0.5，平均每代有兩個染色體參與交叉，不妨設1和3被選中交叉，并且隨機產生的交叉位置為5，則新產生的染色體如表2所示。

表2 交叉后新產生的染色體

染色體表示aif(ai)染色體表示aif(ai)

01000100.343.310000000.645.0

d)變異。設由評判標準所組成的群體中每代只有一位發生變異，且染色體為0100010的第三位被選中，則新種群如表3所示。

表3 新種群

編號染色體表示aif(ai)編號染色體表示aif(ai)

101100100.5010310000000.645.0

210000000.645.0410000000.645.0

并有max f(ai)=10，E(f(ai))=∑f(ai)/4＝6.3。

對比新舊兩個種群可以看出，經過了一代遺傳，第二代評判標準適應函數值的平均值及最大值比第一代都有了提高，這說明評判標準種群正朝優化的方向前進，而按此步驟進行下去，最后產生的解將是符合面試要求的最優評判標準。

1.3.4 小結

在研究生在線考試系統的設計過程中，經過大量的統計分析，利用數據挖掘中的ID3經典算法和遺傳算法，生成面試功能模塊中的影響因子[6]和面試成績合格評判標準，利用這些數據信息，借助于考生評價模型，產生考生最終評價及錄取信息，以上過程均在系統管理后臺自動完成[7]，只將所有考生最終錄取信息反饋給系統用戶。面試結果處理頁面如圖4所示。

1. 4 研究生在線考試系統的設計與實現

本文所設計的研究生在線考試系統，按照角色劃分主要包括以下用戶：教學主管、專業教師、面試考官和考生。其中，教學主管具有系統最高權限，可以進行管理賬戶、試題、組卷、面試等多個功能的操作；專業教師主要完成各專業試題的輸入工作；面試考官則負責面試以及成績的錄入；考生需要完成網上的筆試部分答題。

考慮到系統的安全性，本系統分為兩個界面：a)用于教學主管、專業教師以及面試考官登錄，主要負責管理基本資料、題庫、試卷、筆試和面試成績等；b)用于考生登錄，主要進行在線考試。

從總體上考慮，系統主要實現以下功能，且各功能模塊間關系如圖5所示。

1）基本信息管理功能 主要包括賬戶管理、考生密碼查詢、考試科目信息管理和成績查詢等；

2）試題庫管理功能 主要包括對各科試題的增、刪、修改管理；

3）組卷功能 能夠實現動態組卷；

4）面試成績管理功能 通過對各面試考官輸入的面試成績處理，得到所有考生的錄取結果；

5）試題庫難度系數管理 根據考試情況，對不同時期、不同階段的各科試題庫難度系數進行自適應學習；

6）筆試功能 考生可登錄筆試首頁，選擇考試科目進行在線答題。

本系統在實現時，為了充分考慮考試系統的安全性和保密性，筆試部分采取了一些安全防范措施。例如：考試過程中，禁止離開答題窗口；考試結束自動提交試卷；不能重復進行同一專業的考試等。筆試答題頁面如圖6所示。

本系統采用四層體系架構，包括客戶端表示層、服務器端表示層、業務邏輯層和數據信息層[8，9]。其中，客戶端表示層用HTML、JavaScript實現，如登錄界面等；服務器端表示層用JSP實現，如考生信息查詢頁面；業務邏輯層用Servlet實現，如動態組卷、難度系數自適應學習、面試結果處理等；數據信息層則由JavaBean完成，主要包括數據庫操作。

2 結束語

本文所設計并實現的研究生在線考試系統，具有自動組卷、試題難度系數自適應學習和面試決策支持功能，實現了數據倉庫數據的來源處理過程和應用處理過程，充分體現了自適應決策支持的優越性。本系統采用四層體系架構，從理論到實際，詳細地闡述了系統的設計和實現過程，為實現高效、公平、公正和公開的研究生在線考試提供了一個可靠的平臺。

參考文獻：

[1]ELBER G. Curve evaluation and intenogation on surfaces[J].Graphical Models，2001，63(3):197-210.

[2]QUINLAN J R.Induction of decision tree[J]. Machine Learning，1986，1(1):81-106.

[3]QUINLAN J R.Simplifying decision tree[J].Internet Journal of Man-Machine Studies，1987，27(3):221-234.

[4]FOGEL D B.An introduction to simulated evolutionary optimization[J].IEEE Trans on Neural-Networks， 1994，5(1):3-14.

[5]SRINIVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithm[J]. IEEE Trans on S M C，1994，24(4):656-666.

[6]楊選留，張朋柱.基于神經網絡的高級行政管理人才選拔方案群體決策支持系統研究[J].統計研究，2005(7):66-68.

[7]陳鄭漢，周經野.自然語言與機器學習[J].計算機技術與自動化，2000，19(3)：3-7.

[8]張峻，鐘華.基于J2EE技術的圖書出版領域應用框架研究[J].計算機應用與軟件，2007，24(5):102-104.

[9]程洪，錢樂秋，馬舜雄.基于J2EE體系的Web應用框架整合[J].計算機工程，2005，31(20):96-98.