網絡考試系統中自動評卷算法的應用研究

【摘要】隨著網絡化的發展，網絡教學近幾年逐漸興盛起來，是未來教育發展的一種趨勢，網絡考試系統是網絡教學的核心組成部分之一。本文針對當前已有考試系統的不足和學校的實際需求，設計和實現了一個新的網絡考試系統，其中就主觀題自動評卷技術作了分析與討論。

【關鍵詞】網絡教學；網絡考試；主觀題自動評卷

一、相關背景

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

本文根據作者所在的院系教學的需要，利用校園網強大的服務功能，要研究和設計的是一個完全無紙化考試系統，采用B/S結構，易于安裝使用。系統實現了從自動組卷、考試到自動評卷的全部功能。本文對其中主觀題的自動評卷技術進行重點研究。

二、自動評卷技術

網絡考試的主要優點之一就是可以快速、客觀地給出考試成績，有效地縮短了考試周期，這一優點主要得益于網絡考試的自動評卷[2]。

一般情況下，網絡考試系統對于客觀題可以進行自動評卷。客觀題一般有判斷題、單選題等。對于這類題，計算機可以采用字符串比較的方法，將考生的答案與標準答案進行精確的匹配評卷。

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

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

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

1.思路分析

分析教師的評卷過程，教師在人工評閱主觀題時一般是預先制定好一套評卷標準，然后將每道試題的總分劃分成若干部分，將分數分配到試題的求解過程中的一些關鍵的步驟或關鍵的詞語上，通常稱之為得分點，評閱時看學生的答案和標準答案的各個得分點的貼近度，貼近度高則得分高，最后查看一下學生答案的語句是否通順、是否有條理性等，綜合地給出一個適當的分數。

根據上述分析，可以發現，影響評卷的因素主要有兩個：一個是得分點，另一個是學生答案和標準答案的貼近度。可以將每個得分點轉化為每道題目的標準答案關鍵字，用這些關鍵字去匹配學生答案，根據匹配程度的高低，決定得分的高低。對學生答案和標準答案的貼近度的表示可采用模糊數學中貼近度的概念進行描述[7]，而對于語法結構則不做過多考慮，這樣，一方面可以避免對句子進行復雜的句法分析，另一方面也可增加系統的健壯性，如學生答案中出現無關大局的語法錯誤時，只要其概念表述正確，系統仍然可以給出相應的貼近度評價，這與教師的評卷過程是相符合的。最后，再根據關鍵字和貼近度在評卷時所占的權值比重，計算最終成績。

2.算法設計

（1）相關定義

為解決學生答案和標準答案的貼近度表示問題，可以把學生答案和標準答案均看成字符串，下面對單向貼近度的概念進行定義。

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

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

定義1：

設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：

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

（2）算法說明

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

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

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

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

3.自動評卷實現

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

（1-1）[7]

式中各符號的含義如下：

Sim1（A，B）：是學生答案與標準答案的相似度；

A：學生的實際答案。學生交卷后保存在學生答卷庫中；

B：試題的標準答案。出題時生成，從題庫中讀取；

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

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

n：關鍵詞的個數。根據題庫中的關鍵詞信息由程序計算得到；

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

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

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

其含義是：

當dki（Ki，A）

當dki（Ki，A）≥dk0（K，A）時，dki（Ki，A） =dki（Ki，A）。

da（A，B）：標準答案與學生答案的單向貼近度。由程序計算得到；

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

當da（A，B）

當da（A，B）≥da0（A，B）時，da（A，B）=da （A，B）。

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

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

1.思路分析

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

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

2.算法說明

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

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

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

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

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

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

（1-2）[9]

其中是一個可調節的參數。的含義是：當相似度為0.5時的詞語距離值。所以，假設詞語組成的樹的高度為H，那么兩個節點最遠距離為2H（根節點為0層），則可以等于樹高H。當兩個詞語在不同的樹中，那么它們的距離為∞。當然，的取值并不是唯一的。

本文主要是以知網的義原層次樹為基礎對詞語的相似度進行研究[10]。在知網中，它認為詞是由表達其意思的幾個義原組合的，這些義原可以根據其義原之間的上下位關系構成義原層次樹。在這棵樹中，每個節點就是一個義原。由于所有的概念都最終歸結于用義原來表示[11]，所以義原的相似度計算是概念相似度計算的基礎。

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

（1-3）[11]

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

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

3.算法實現

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

（1-4）[12]

其中義原項的權重：

（1-5）[12]

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

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

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

完整地表達一個句子的信息，不但依賴于組成句子的詞匯的信息，而且還依賴于詞匯之間的語義信息。本論文從句子結構信息和詞匯之間的語義信息進行研究，以便更準確地進行句子相似度計算。

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

因此可將前兩種方法相結合提出：

（1-6）

由于不同層次對句子相似度計算的貢獻不同，該方法對每個層次加了不同的權值，從而使相似度計算達到最優。其中兩個權值的設置規定為：

（1-7）

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

（1-8）

（四）自動評卷測試

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

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

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

三、工作總結

本系統在做了大量的研究和調查的基礎上，針對廣東私立華聯學院的實際情況進行開發建立了一個比較完善的網絡考試系統原型，該系統可適用于各類學校、成人教育，職業培訓和技術培訓等機構在遠程教育平臺上進行考試管理，其推廣使用對于教學管理的改革，使有限的師資發揮更大的作用等方面具有重要的意義。

參考文獻

[1]羅紅梅.基于J2EE架構的在線考試系統的設計與實現[D].碩士學位論文.

[2]孫衛.基于web的網絡考試系統的設計與實現[D].河海大學計算機及信息工程學院，2007.

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

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

[5]董英斌等.基于網絡的新型計算機考試系統[J].計算機工程，2001.

[6]龔漢明等.漢語分詞技術綜述[J].北京機械工業學院學報，2004.

[7]孟愛國等.一種網絡考試系統中主觀題自動評卷的算法設計與實現[J].計算機與數字工程，2005.

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

[9]汪泱.主觀文字試題評判相關技術研究[J].北京科技大學計算機學院，2006.

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

[11]董振東，董強.知網[OL].www.keenage.com.

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