網(wǎng)絡(luò)考試系統(tǒng)中自動評卷算法的應(yīng)用研究

【摘要】隨著網(wǎng)絡(luò)化的發(fā)展，網(wǎng)絡(luò)教學(xué)近幾年逐漸興盛起來，是未來教育發(fā)展的一種趨勢，網(wǎng)絡(luò)考試系統(tǒng)是網(wǎng)絡(luò)教學(xué)的核心組成部分之一。本文針對當(dāng)前已有考試系統(tǒng)的不足和學(xué)校的實(shí)際需求，設(shè)計和實(shí)現(xiàn)了一個新的網(wǎng)絡(luò)考試系統(tǒng)，其中就主觀題自動評卷技術(shù)作了分析與討論。

【關(guān)鍵詞】網(wǎng)絡(luò)教學(xué)；網(wǎng)絡(luò)考試；主觀題自動評卷

一、相關(guān)背景

隨著計算機(jī)技術(shù)的不斷發(fā)展和網(wǎng)絡(luò)技術(shù)的日益普及，如何能最大限度的利用各類資源，快速提高技術(shù)人員的知識和能力水平成為社會的強(qiáng)烈需求。不管是在目前的高等學(xué)校，還是各類異地教育和培訓(xùn)機(jī)構(gòu)，考試都是教學(xué)活動的一個重要環(huán)節(jié)[1]，用來檢測學(xué)習(xí)成效。隨著考試類型的增多和考試要求的不斷提高，特別是考生數(shù)量比較大時，教師的工作量也越來越大，組織一次完整的考試至少包括以下幾個步驟：考生報名、人工出卷、試卷印刷、考生考試、人工評卷和成績統(tǒng)計分析等，在整個工作過程中，由于接觸的人員較多，通常還要考慮保密性方面的問題，例如教師需要找大量試題出多份試卷，再由選擇其中一份或者兩份作為考試用卷，試卷選擇隨意性大，憑教師的主觀意愿來評定一張試卷的難易程度；還要聯(lián)系印刷和送試卷等，花費(fèi)教師們大量的時間和精力，通常效率低下，可以說傳統(tǒng)的考試方式己經(jīng)不能適應(yīng)現(xiàn)代考試的需要。

本文根據(jù)作者所在的院系教學(xué)的需要，利用校園網(wǎng)強(qiáng)大的服務(wù)功能，要研究和設(shè)計的是一個完全無紙化考試系統(tǒng)，采用B/S結(jié)構(gòu)，易于安裝使用。系統(tǒng)實(shí)現(xiàn)了從自動組卷、考試到自動評卷的全部功能。本文對其中主觀題的自動評卷技術(shù)進(jìn)行重點(diǎn)研究。

二、自動評卷技術(shù)

網(wǎng)絡(luò)考試的主要優(yōu)點(diǎn)之一就是可以快速、客觀地給出考試成績，有效地縮短了考試周期，這一優(yōu)點(diǎn)主要得益于網(wǎng)絡(luò)考試的自動評卷[2]。

一般情況下，網(wǎng)絡(luò)考試系統(tǒng)對于客觀題可以進(jìn)行自動評卷?？陀^題一般有判斷題、單選題等。對于這類題，計算機(jī)可以采用字符串比較的方法，將考生的答案與標(biāo)準(zhǔn)答案進(jìn)行精確的匹配評卷。

如果一個考試系統(tǒng)中的考題都是客觀題，這樣的試卷不是一份好的試卷，僅有這類題型的試卷對測試考生的能力還存在欠缺。因此，理想的試卷針對不同的學(xué)科還應(yīng)該包括有主觀題（問答、證明、計算、設(shè)計題）等多種題型。但是對于主觀題，如論述題、簡答題等沒有統(tǒng)一答案的試題，目前還沒有一種考試系統(tǒng)能很好地完成其自動評卷。對此我們進(jìn)行了一些嘗試，對自動評卷技術(shù)做一些詳細(xì)的介紹。

主觀題自動評卷涉及到人工智能、模式識別和自然語言處理等方面的理論[3-4]，面臨許多技術(shù)上的問題，從而成為網(wǎng)絡(luò)考試系統(tǒng)中的一個技術(shù)難點(diǎn)[5]。主觀題自動評卷技術(shù)主要由自然語言處理，中文分詞技術(shù)[6]，語句相似度計算三方面構(gòu)成。其中自然語言處理技術(shù)和中文分詞技術(shù)到目前為止還沒有得到廣泛的應(yīng)用，原因在于對自然語言處理技術(shù)的研究還處在一個初級階段，無法實(shí)現(xiàn)計算機(jī)能夠百分之百地“讀懂”人類的語言，同時由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機(jī)器可直接讀取的形式，目前基于理解的分詞系統(tǒng)也還處在試驗階段。所以基于語句相似度的主觀題自動批改系統(tǒng)的實(shí)現(xiàn)成為本文研究的重點(diǎn)。在本系統(tǒng)中，由于開發(fā)時間短促以及各項條件尚不成熟，因而沒有全面地實(shí)現(xiàn)主觀題自動評卷模塊的設(shè)計，但在本文先分析了目前使用主觀題自動評卷技術(shù)中的一些算法，以期能拋磚引玉。

（一）基于詞語匹配的相似度法

1.思路分析

分析教師的評卷過程，教師在人工評閱主觀題時一般是預(yù)先制定好一套評卷標(biāo)準(zhǔn)，然后將每道試題的總分劃分成若干部分，將分?jǐn)?shù)分配到試題的求解過程中的一些關(guān)鍵的步驟或關(guān)鍵的詞語上，通常稱之為得分點(diǎn)，評閱時看學(xué)生的答案和標(biāo)準(zhǔn)答案的各個得分點(diǎn)的貼近度，貼近度高則得分高，最后查看一下學(xué)生答案的語句是否通順、是否有條理性等，綜合地給出一個適當(dāng)?shù)姆謹(jǐn)?shù)。

根據(jù)上述分析，可以發(fā)現(xiàn)，影響評卷的因素主要有兩個：一個是得分點(diǎn)，另一個是學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度?？梢詫⒚總€得分點(diǎn)轉(zhuǎn)化為每道題目的標(biāo)準(zhǔn)答案關(guān)鍵字，用這些關(guān)鍵字去匹配學(xué)生答案，根據(jù)匹配程度的高低，決定得分的高低。對學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度的表示可采用模糊數(shù)學(xué)中貼近度的概念進(jìn)行描述[7]，而對于語法結(jié)構(gòu)則不做過多考慮，這樣，一方面可以避免對句子進(jìn)行復(fù)雜的句法分析，另一方面也可增加系統(tǒng)的健壯性，如學(xué)生答案中出現(xiàn)無關(guān)大局的語法錯誤時，只要其概念表述正確，系統(tǒng)仍然可以給出相應(yīng)的貼近度評價，這與教師的評卷過程是相符合的。最后，再根據(jù)關(guān)鍵字和貼近度在評卷時所占的權(quán)值比重，計算最終成績。

2.算法設(shè)計

（1）相關(guān)定義

為解決學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度表示問題，可以把學(xué)生答案和標(biāo)準(zhǔn)答案均看成字符串，下面對單向貼近度的概念進(jìn)行定義。

把一個字符串分解為單個字符，并把它們構(gòu)成的有序集合稱為一個模糊集，U={u1， u2，……，un}稱為論域，論域u上的全體模糊子集所組成的集合記作F（U）（也叫模糊冪集）[7]。

為度量兩模糊集的接近程度，引入單向貼近度的概念。

定義1：

設(shè)U={u1，u2.......，un}，A，B∈F（U）。若映射d：F（U）×F（U）→[0，l]，滿足條件：

d（A，A）=l；d（B，B）=1；

若A包含于B，而B包含于C或A包含B，而B包含C，則d（A，B）≥d（A，C）稱d（A，B）為A貼近于B的單向貼近度。

定義2：

設(shè)A、B是字符串，A中包含n個字符，d（A，B）表示A貼近于B的單向貼近度，按照從左到右的順序，集合A中的每個元素在集合中出現(xiàn)的有效次數(shù)之和記為m，則d（A，B）=m/n，容易驗證，它滿足單向貼近度的定義。

（2）算法說明

為說明方便，以字符串A和B為例介紹計算字符串A貼近于字符串B的單向貼近度d（A，B），步驟如下：

把查找字符串A分解為單個有效字符。在分解前，首先判斷左邊第一個字符是雙字節(jié)字符還是單字節(jié)字符，如果是雙字節(jié)字符就按2個字節(jié)截取，如果是單字節(jié)字符則按l個字節(jié)截取。把字符串A分解為若干個有效字符u1，u2，……，un。

判斷A分解后的單字符是否包含在被查詢的字符串中。這里假定所要查找的字符串分解前和分解后是有順序的，所以不能簡單地使用是否包含來判斷。本文的做法是：判斷第一個字符u1是否包含在字符串B中，如果不包含則標(biāo)記為0，否則標(biāo)記為l，并從B2中去掉包含u1的字符，對B進(jìn)行第二個字符u2的相同處理，一直把u1，u2，……，un。判斷完畢。

計算單向貼近度d（A，B）。計算A分解后的單字符u1，u2，……，un在B中出現(xiàn)的次數(shù)之和m占A總有效字符數(shù)n的比值，并記為d（A，B）。

3.自動評卷實(shí)現(xiàn)

根據(jù)上述分析，可以得出主觀題的評卷公式。

（1-1）[7]

式中各符號的含義如下：

Sim1（A，B）：是學(xué)生答案與標(biāo)準(zhǔn)答案的相似度；

A：學(xué)生的實(shí)際答案。學(xué)生交卷后保存在學(xué)生答卷庫中；

B：試題的標(biāo)準(zhǔn)答案。出題時生成，從題庫中讀??；

P：關(guān)鍵詞在該題目中所占分值的比例，0≤P≤1。組卷時生成，也可評卷時修改，從試卷庫中讀??；

1-P：關(guān)鍵詞以外的因素在該題目中所占分值的比例；

n：關(guān)鍵詞的個數(shù)。根據(jù)題庫中的關(guān)鍵詞信息由程序計算得到；

Ki：第i個關(guān)鍵詞，1≤i≤n。根據(jù)題庫中的關(guān)鍵詞信息由程序拆分得到；

dki（Ki，A）：第i個關(guān)鍵詞與學(xué)生答案的單向貼近度，1≤i≤n。由程序計算得到；

dk0（K，A）：關(guān)鍵詞與學(xué)生答案的單向貼近度閥值。組卷時生成，也可評卷時修改，從試卷庫中取得。

其含義是：

當(dāng)dki（Ki，A）

當(dāng)dki（Ki，A）≥dk0（K，A）時，dki（Ki，A） =dki（Ki，A）。

da（A，B）：標(biāo)準(zhǔn)答案與學(xué)生答案的單向貼近度。由程序計算得到；

da0（A，B）：標(biāo)準(zhǔn)答案與學(xué)生答案的單向貼近度閥值。組卷時生成，也可評卷時修改，從試卷庫中讀取。其含義是：

當(dāng)da（A，B）

當(dāng)da（A，B）≥da0（A，B）時，da（A，B）=da （A，B）。

從公式中可以看出，主觀題的評卷受P，dk0（K，A），da0（A，B）三個參數(shù)影響，P增大，關(guān)鍵詞在評卷中占的比重就增大，反之則減??；一般來說，dk0（K，A），da0（A，B）增大，則表示評卷標(biāo)準(zhǔn)提高，反之，評卷標(biāo)準(zhǔn)降低。因此，通過調(diào)整這三個參數(shù)，即可實(shí)現(xiàn)對評卷標(biāo)準(zhǔn)的調(diào)整。這三個參數(shù)可在組卷時設(shè)定，保存在試卷信息中，也可在評卷時進(jìn)行調(diào)整。

（二）基于語義信息的相似度法

1.思路分析

基于關(guān)鍵詞信息的方法由于沒有考慮詞本身的詞義信息以及同義詞、近義詞等語義關(guān)系，實(shí)際應(yīng)用于自動該卷系統(tǒng)有一定的局限性，基于語義信息的方法可以部分地解決這一問題。基于語義信息的相似度也就是兩個詞語意思的相近程度，它是句子之間意思相似程度的基礎(chǔ)，也是答案比較研究的基礎(chǔ)。它的相似度比較的準(zhǔn)確性影響著答案比較的準(zhǔn)確性，從而也影響著整個考試系統(tǒng)判卷的正確性[8]。

語義信息相似度對于主觀試題評判非常重要，但是由于語義信息相似度是一個主觀性很強(qiáng)的概念，所以一直以來如何更準(zhǔn)確地計算兩個詞語之間的相似程度，都是國內(nèi)外研究的難點(diǎn)。它很難直接給出一個公式來衡量兩個詞的語義信息相似程度。大部分國內(nèi)外關(guān)于語義信息相似度的研究一般都是將所有的詞語按其意思所屬的類別組織成一棵或幾棵樹狀結(jié)構(gòu)，樹狀結(jié)構(gòu)中每個節(jié)點(diǎn)相對應(yīng)一個詞語，該詞語位于樹的層次結(jié)構(gòu)中所處的位置越高，表示它涵蓋其他概念的能力就越強(qiáng)。那么，由于在一棵樹形圖中任何兩個節(jié)點(diǎn)之間有且只有一條路徑，可以將詞語之間相似程度用樹的節(jié)點(diǎn)之間的距離來衡量[9]。

2.算法說明

一般而言，詞語距離是一個[0，∞]之間的實(shí)數(shù)。一個詞語與其本身的距離為0，詞距離與詞語相似度之間有著密切的關(guān)系。

兩個詞語的距離越大，其相似度越低；反之，兩個詞語的距離越小，其相似度越大。二者之間可以建立一種簡單的對應(yīng)關(guān)系。這種對應(yīng)關(guān)系需要滿足以下幾個條件[9]：

（1）兩個詞語距離為0時，其相似度為1。

（2）兩個詞語距離為無窮大時，其相似度為0。

（3）兩個詞語的距離越大，其相似度越小（單調(diào)下降）。

對于兩個詞語W1和W2，記其相似度為Sim （W1，W2），其詞語距離為Dis（W1，W2）那么可以定義一個滿足以上條件的簡單的轉(zhuǎn)換關(guān)系：

（1-2）[9]

其中是一個可調(diào)節(jié)的參數(shù)。的含義是：當(dāng)相似度為0.5時的詞語距離值。所以，假設(shè)詞語組成的樹的高度為H，那么兩個節(jié)點(diǎn)最遠(yuǎn)距離為2H（根節(jié)點(diǎn)為0層），則可以等于樹高H。當(dāng)兩個詞語在不同的樹中，那么它們的距離為∞。當(dāng)然，的取值并不是唯一的。

本文主要是以知網(wǎng)的義原層次樹為基礎(chǔ)對詞語的相似度進(jìn)行研究[10]。在知網(wǎng)中，它認(rèn)為詞是由表達(dá)其意思的幾個義原組合的，這些義原可以根據(jù)其義原之間的上下位關(guān)系構(gòu)成義原層次樹。在這棵樹中，每個節(jié)點(diǎn)就是一個義原。由于所有的概念都最終歸結(jié)于用義原來表示[11]，所以義原的相似度計算是概念相似度計算的基礎(chǔ)。

因為所有的義原根據(jù)上下位關(guān)系構(gòu)成了一個樹狀的義原層次體系，可以簡單地通過詞語距離來計算相似度。假設(shè)兩個義原在這個層次體系中的路徑距離為d，根據(jù)（公式1-2），我們可以得到這兩個義原之間的語義距離：

（1-3）[11]

其中p1和p2表示兩個義原，d是p1和p2在義原層次體系中的路徑長度，是一個正整數(shù)。如果兩個詞語處于不同的義原層次樹中，那么d為無窮大。是一個可調(diào)節(jié)的參數(shù)，本文中值為各義原層次樹的樹高。

本文所討論的方法是以義原層次樹為基礎(chǔ)的，而義原層次樹僅僅是按義原上下位關(guān)系組成的，因此用這種方法計算義原相似度的時候，并沒有考慮到義原的其他關(guān)系，如反義關(guān)系，對義關(guān)系等。盡管考慮其他義原關(guān)系會增加義原相似度計算的準(zhǔn)確性，但是基于對系統(tǒng)復(fù)雜程度的考慮，只利用了義原層次樹進(jìn)行義原相似度的比較也是可以接受的，因此本論文中采用的都是單純利用義原層次樹來計算義原距離和詞語相似度的方法，而沒有考慮其它義原關(guān)系對詞語相似度計算的影響。

3.算法實(shí)現(xiàn)

由于義原表達(dá)位置和詞語多義的情況，使得兩個詞語的相似度比較要分為兩個步驟：首先，在不考慮一詞多意的情況下，對兩個詞語的比較。假設(shè)詞語A（a1，a2，…，an）和詞語B（b1，b2，...，bm），其中ai，bi分別為詞語A，B的義原項。如果兩個詞語的第一個義原項相似度為0，說明這兩個義原肯定不在一棵義原層次樹中，由于第一義原對詞語的影響最大，決定了詞語的類型，因此，當(dāng)兩個第一義原相似度為0的時候，可以不用計算后面的其他義原相似度，直接認(rèn)為兩個詞語的相似度為0。如果第一義原比較不為0的話，那么詞語A與B的相似度就應(yīng)該是A的第i個義原與B的第i個義原相比較的加權(quán)平均和[12]。即：

（1-4）[12]

其中義原項的權(quán)重：

（1-5）[12]

如果n不等于m，也就是說A和B的義原數(shù)目不相等，假設(shè)A>B，那么在B的義原項m之后的AB義原項比較的相似度可以看作是0。

在出現(xiàn)一詞多義的情況下，假設(shè)詞W有z個意思，那么它就有z個義原組合情況Ai（i=1，2，……，z），那么W的第i個意思Ai又是由j個義原項組成Ai（a1，a2，……aj），因此，詞語W與詞V比較時，應(yīng)該把Ai分別與V的義原項進(jìn)行比較，取最大相似度為詞語W與V的相似度。

（三）基于融合的語句相似度法

完整地表達(dá)一個句子的信息，不但依賴于組成句子的詞匯的信息，而且還依賴于詞匯之間的語義信息。本論文從句子結(jié)構(gòu)信息和詞匯之間的語義信息進(jìn)行研究，以便更準(zhǔn)確地進(jìn)行句子相似度計算。

我們的目標(biāo)是將句子的詞形（詞語匹配技術(shù)）、詞義（詞語語義信息）組合起來，揚(yáng)長避短，互為補(bǔ)充，共同描述一個句子，從而根據(jù)這些特征計算學(xué)生答案和標(biāo)準(zhǔn)答案之間的相似度，獲得較高的準(zhǔn)確率。

因此可將前兩種方法相結(jié)合提出：

（1-6）

由于不同層次對句子相似度計算的貢獻(xiàn)不同，該方法對每個層次加了不同的權(quán)值，從而使相似度計算達(dá)到最優(yōu)。其中兩個權(quán)值的設(shè)置規(guī)定為：

（1-7）

由此得出如果一道題目的分值為S0，則最后得分S為：

（1-8）

（四）自動評卷測試

為了驗證用基于語句相似度的三種算法進(jìn)行自動評卷的可行性和有效性，我們抽取了07網(wǎng)絡(luò)1班的《數(shù)據(jù)結(jié)構(gòu)》試卷來進(jìn)行實(shí)驗，班上一共有20個學(xué)生參加了考試。每份考卷中都有1道簡答題，并且教師已經(jīng)對其人工評卷完畢，這樣能夠方便地計算出準(zhǔn)確率。

我們以考題“什么是算法”為例，標(biāo)準(zhǔn)答案為：“算法是問題求解規(guī)則的一種過程描述（即計算機(jī)解題的過程）。它具有5個基本性質(zhì)：確定性、有窮性、可行性、輸入和輸出?！痹O(shè)定好該題目的分值為10分，其中一個學(xué)生的答案是“算法是一種求解的過程，它具有邏輯性、可計算性和窮盡性”。分別通過三種相似度方法的計算得出最終分值進(jìn)行準(zhǔn)確率的比較。

通過實(shí)驗最后得出，基于融合的相似度計算方法把基于詞表面信息的相似度計算和基于語義信息的相似度計算很好地結(jié)合在一起，充分發(fā)揮了采用詞性和詞義方法的長處，最后得到了較高的準(zhǔn)確率。并且我們對測試錯誤的結(jié)果進(jìn)行了分析，發(fā)現(xiàn)錯誤的主要原因在于兩點(diǎn)，一個是在對基于詞語匹配相似度計算中我們所定義的關(guān)鍵詞拓展的不夠，也就是未登錄詞導(dǎo)致的問題；另一個原因是在基于語義信息相似度計算中利用語義詞典會給根本與題意無關(guān)的學(xué)生答案評了較高的分?jǐn)?shù)，從而帶來了錯誤的計算結(jié)果。

三、工作總結(jié)

本系統(tǒng)在做了大量的研究和調(diào)查的基礎(chǔ)上，針對廣東私立華聯(lián)學(xué)院的實(shí)際情況進(jìn)行開發(fā)建立了一個比較完善的網(wǎng)絡(luò)考試系統(tǒng)原型，該系統(tǒng)可適用于各類學(xué)校、成人教育，職業(yè)培訓(xùn)和技術(shù)培訓(xùn)等機(jī)構(gòu)在遠(yuǎn)程教育平臺上進(jìn)行考試管理，其推廣使用對于教學(xué)管理的改革，使有限的師資發(fā)揮更大的作用等方面具有重要的意義。

參考文獻(xiàn)

[1]羅紅梅.基于J2EE架構(gòu)的在線考試系統(tǒng)的設(shè)計與實(shí)現(xiàn)[D].碩士學(xué)位論文.

[2]孫衛(wèi).基于web的網(wǎng)絡(luò)考試系統(tǒng)的設(shè)計與實(shí)現(xiàn)[D].河海大學(xué)計算機(jī)及信息工程學(xué)院，2007.

[3]魏曉寧.人工智能在自然語言理解技術(shù)上的應(yīng)用[J].科技論壇，2005（10）.

[4]金博，史彥軍，騰弘飛.基于語義理解的文本相似度算法[J].大連理工大學(xué)學(xué)報，2005（3）.

[5]董英斌等.基于網(wǎng)絡(luò)的新型計算機(jī)考試系統(tǒng)[J].計算機(jī)工程，2001.

[6]龔漢明等.漢語分詞技術(shù)綜述[J].北京機(jī)械工業(yè)學(xué)院學(xué)報，2004.

[7]孟愛國等.一種網(wǎng)絡(luò)考試系統(tǒng)中主觀題自動評卷的算法設(shè)計與實(shí)現(xiàn)[J].計算機(jī)與數(shù)字工程，2005.

[8]高思丹，袁春鳳.語句相似度計算在主觀題自動批改技術(shù)中的初步應(yīng)用[J].計算機(jī)工程與應(yīng)用，2004.

[9]汪泱.主觀文字試題評判相關(guān)技術(shù)研究[J].北京科技大學(xué)計算機(jī)學(xué)院，2006.

[10]劉群，李素建.基于知網(wǎng)的詞匯語義相似度計算[Z].臺北：第三屆漢語詞匯語義學(xué)研討會，2002.

[11]董振東，董強(qiáng).知網(wǎng)[OL].www.keenage.com.

[12]許云，樊孝忠，張鋒.基于知網(wǎng)的語義相關(guān)度計算[J].北京理工大學(xué)學(xué)報，2005（25）：411-414.