黨麗瓊 劉文輝

摘要： 主觀試題自動評閱系統(tǒng)涉及人工智能、模式識別以及計算機(jī)自然語言理解等復(fù)雜的系統(tǒng)知識，是無紙化考試中自動閱卷系統(tǒng)的設(shè)計難點。為此，仿照傳統(tǒng)考試過程中人工閱卷的基本思路，把主觀試題的自動評閱問題分解為知識庫的構(gòu)建、概念相似度的計算以及語句結(jié)構(gòu)的處理等三部分，并把一種改進(jìn)的多因素語義相似度算法引入到概念相似度計算，詳細(xì)設(shè)計了主觀試題的計算機(jī)自動評閱模型。實例運行結(jié)果表明，占總數(shù)70%的計算結(jié)果在可接受誤差范圍內(nèi)。

關(guān)鍵詞： 主觀試題； 多因素； 自動評閱； 語義相似度

中圖分類號：TP399 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2012）05-09-04

Study of automatic marking method of subjective questions based on semantic similarity

Dang Liqiong1，2, Liu Wenhui3

（1. Shan Xi Spaceflight Employee University School of Computer Science, Xian， Shanxi 710100, China;

2. Xian Shiyou University; 3. 95092 units）

Abstract： It is because of the automatic marking of the subjective questions involving artificial intelligence, pattern recognition and computer understanding of natural language that has become a difficulty of the automatic marking in the design of paperless examination. By simulating the basic train of thought of the manual marking in traditional test, automatic marking of the subjective questions is divided into three parts which are construction of knowledge, calculation of concept similarity and handle of sentence of structure, then a kind of improved multi-factor semantic similarity calculation is introduced to solve the concept similarity, finally a computer automatic marking model of subjective questions is designed in detail. Practical operation results show that seventy percent of the total results within the acceptable error range.

Key words： subjective questions； multi-factor； automatic marking； semantic similarity

0 引言

隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，無紙化考試逐漸成為一種新的發(fā)展方向。在無紙化考試系統(tǒng)的開發(fā)中，除一般試題庫的設(shè)計、試卷的組織管理以及考試過程的控制外，計算機(jī)自動閱卷模塊的設(shè)計是一個重要的內(nèi)容。對于完善的無紙化考試系統(tǒng)來說，自動閱卷模塊除了提供客觀試題自動評閱的功能，還必須能夠解決好主觀題自動閱卷問題。由于考生答案的靈活性和多樣性，主觀題評閱會涉及到人工智能、模式識別和計算機(jī)自然語言理解等多方面系統(tǒng)知識，這就使得主觀題的自動評閱成為自動閱卷設(shè)計中的技術(shù)難點。

1 主觀試題自動評閱

主觀試題的自動評閱可以理解為的計算機(jī)對自然語言的處理過程。漢語與英語等歐式語言相比，在結(jié)構(gòu)和組織方式上有很大的不同，計算機(jī)對漢語言的處理不僅要考慮詞與詞之間的關(guān)系，還應(yīng)考慮句子結(jié)構(gòu)之間的關(guān)系，因此計算機(jī)處理上相比歐式語言難度增加了很多。目前在這方面有代表性的算法有：李輝陽等根據(jù)有限概念領(lǐng)域中簡述文字的自動判讀過程提出的一種基于關(guān)系的帶權(quán)匹配技術(shù)[1]，文獻(xiàn)[2]提出的基于動態(tài)規(guī)劃的語句相似度算法，黃康等提出的基于帶權(quán)概念網(wǎng)絡(luò)進(jìn)行分層的語義相似度技術(shù)[3]，文獻(xiàn)[4]從漢語自然語言理解的語義分析角度提出的一種基于概念圖理論的模糊含權(quán)概念圖法，以及文獻(xiàn)[5]引入模糊理論中嚴(yán)格貼近度的概念來計算貼近程度得分等。

上述方法研究的重點主要集中在三方面：一是知識庫的構(gòu)建，如有限領(lǐng)域、概念圖、概念網(wǎng)等；二是句子結(jié)構(gòu)的處理，如動態(tài)規(guī)劃法、分層語義相似度技術(shù)等；三是相似度算法，如帶權(quán)匹配技術(shù)、模糊概念圖法、基于模糊理論的嚴(yán)格貼近度法等。一般來說，研究重點的不同，帶來的只是結(jié)果上的差異，而最有效的解決方案應(yīng)該是針對待處理的問題構(gòu)建最合適的知識庫、選擇最佳的句子結(jié)構(gòu)處理辦法、確定最有效的相似度算法。本文研究的對象是在線考試系統(tǒng)中簡單問答題的自動評閱技術(shù)；主要思路是從簡答題題型結(jié)構(gòu)出發(fā)，基于試題答案知識點構(gòu)建識庫，重點分析研究知識庫中概念節(jié)點的分布特點，最終采用由概念到句子的主觀試題自動評閱處理流程。

2 知識表示

實現(xiàn)主觀試題的自動評閱功能的一般方法是，通過訪問領(lǐng)域知識庫，使計算機(jī)獲得特定領(lǐng)域內(nèi)的專業(yè)知識，并在此基礎(chǔ)上計算標(biāo)準(zhǔn)答案和學(xué)生答案之間的相似度，由此可見，領(lǐng)域知識庫的創(chuàng)建對于自動評閱的實現(xiàn)是極其必要的，建立高效的領(lǐng)域知識庫是計算機(jī)自動閱卷的基礎(chǔ)。語義相似度的計算需要建立相應(yīng)領(lǐng)域的知識庫，實現(xiàn)起來不但工作量大、且需要耗大量的時間進(jìn)行比較和匹配，這樣對于在線考試系統(tǒng)的實時性來說不太現(xiàn)實。因此，對于特定領(lǐng)域問題的解決應(yīng)該具體問題具體分析，采用的特定的、符合實際的解決方法。目前，受限于自然語言理解領(lǐng)域的研究水平，直接讓計算機(jī)從自然文本中獲得專業(yè)領(lǐng)域知識還比較困難，所以一般采用計算機(jī)輔助的人工錄入方式來建立領(lǐng)域知識庫。

本文以計算機(jī)基礎(chǔ)課程為例，分析了大量的試題的結(jié)構(gòu)和特點，從試題答案組織結(jié)構(gòu)關(guān)系出發(fā)，對知識庫的構(gòu)建提出了以下原則。

⑴ 借鑒“知網(wǎng)”、“概念圖”等概念詞典，僅采用簡單的“包含”、“從屬”、“類同”等結(jié)構(gòu)來表示概念之間的關(guān)系。

⑵ 對于概念的描述盡可能詳細(xì)，且必須以試題答案所涉及到的知識點為基礎(chǔ)，進(jìn)行全面的擴(kuò)展，必要時包含同義詞描述等，以保證知識庫能涵蓋所有可能的概念組合，并能根據(jù)考生答案實際進(jìn)行擴(kuò)充。

⑶ 知識庫從上到下，概念表示應(yīng)該由抽象到具體，由簡單到詳細(xì)，以保證最底層的概念盡量達(dá)到“義元”級別，即概念的最小意義單位。

如圖1所示為本文基于以上原則建立的計算機(jī)基礎(chǔ)知識庫樹狀結(jié)構(gòu)局部圖。

圖1知識庫樹狀結(jié)構(gòu)局部圖

3 概念相似度計算

與概念相似度密切相關(guān)的一個概念是語義距離(semantic distance)，通常認(rèn)為它們是概念關(guān)系特征的不同表現(xiàn)形式?？梢越⒁环N簡單概念詞相似度用來描述概念樹中兩個節(jié)點之間的語義接近程度，對此，一般最常用的是劉群提出的以《知網(wǎng)》為基礎(chǔ)的相似度計算方法[6]：

⑴

式⑴中p1和p2表示兩個概念節(jié)點，是樹狀結(jié)構(gòu)中兩節(jié)點間的最短距離，α是一個調(diào)節(jié)參數(shù)，表示相似度為0.5時的路徑長度，一般取1。

Agirre和Rigau在利用WordNet計算英文詞匯相似度時，同時引入了層次樹深度和密度的因素[7]。他們認(rèn)為，在詞語層次樹中，路徑長度相同的兩對節(jié)點，深度越大(遠(yuǎn)離樹根)的節(jié)點對，語義距離越小。因為深度越大，語義網(wǎng)中的概念分類由小到大，由抽象逐漸到具體，也意味著分類越詳細(xì)。例如，對于路徑長度相同的2對節(jié)點來說，由于他們所處區(qū)域的節(jié)點密度較高，所以語義距離相對較小。因為概念密度越大，表明對概念的描述越詳細(xì)。如圖1中，同層節(jié)點“處理器”、“總線”、“系統(tǒng)軟件”和“應(yīng)用軟件”路徑距離相同，但“處理器”、“總線”所處的區(qū)域節(jié)點密度較高，從一般常識來看，“處理器”、“總線”之間的語義相似度要高于“系統(tǒng)軟件”和“應(yīng)用軟件”。因此，計算概念相似度，只考慮節(jié)點之間的路徑長度這個單一因素顯然不夠合理，應(yīng)同時考慮概念網(wǎng)中概念節(jié)點之間的縱向和橫向因素，以及他們之間的相互制約量，綜合考慮，才能取長補(bǔ)短，消除概念之間的相似度計算結(jié)果的影響因素。

本文采用文獻(xiàn)[8]提出的一種改進(jìn)的多因素語義相似度計算方法：

⑵

式中，調(diào)節(jié)參數(shù)，l(p1，p2)為分別遍歷概念網(wǎng)中節(jié)點p1，p2到達(dá)其最小公共父結(jié)點所歷經(jīng)的父結(jié)點（包括最小公共父結(jié)點）數(shù)的最大值。w(p1，p2)為p1，p2所在層概念數(shù)的最大值。在該調(diào)節(jié)參數(shù)的作用下，當(dāng)w(p1，p2)增大時，密度因素對相似度的貢獻(xiàn)值大；而當(dāng)p1，p2離最小公共父結(jié)點較遠(yuǎn)，深度因素對相似度的貢獻(xiàn)值較大。同時式中約定當(dāng)p1，p2的父結(jié)點和最小公共父結(jié)點相同，且同層只有p1，p2兩個節(jié)點時，調(diào)節(jié)參數(shù)為0.5。

4 句子相似度的處理

一般認(rèn)為句子相似度計算包括兩個步驟[9，10]：首先，經(jīng)過詞的結(jié)構(gòu)相似度計算，得到句子的結(jié)構(gòu)相似度，然后，在句子結(jié)構(gòu)相似的基礎(chǔ)上，再進(jìn)行句子語義相似度的計算。

設(shè)學(xué)生答案和標(biāo)準(zhǔn)答案分別表示為P和Q，P經(jīng)自動分詞處理后可表示為概念向量組P=(P1，P2，…，Pm)，Q包含的概念向量為Q=(Q1，Q2，…，Qm)。

則句子相似度的處理過程具體可分為以下兩個步驟：

⑴設(shè)MPQ為句子P，Q的相似度特征矩陣，則有：

⑶

式中，元素Sim(pi，qj)表示詞語pi和詞語qj間的語義相似度，通過前文講述的概念相似度公式計算獲得。矩陣中的每一行表示句子P中的某個詞語與句子Q中所有詞語的語義相似度。

⑵對矩陣中的每一行取最大值max(S(pi，qj))，即求句子P中的某個詞語和句子Q中的所有詞語的語義相似度的最大值，得到詞語最大組合序列，則句子P中所有詞語與Q句子之間的語義相似度可以表示為：

⑷

5 自動評閱模型的實現(xiàn)

前面我們分析了主觀試題的自動評閱問題的基本思路，按照一般教師的試卷評閱過程，把該過程分解為概念語義相似度的處理和句子語義相似度的處理兩個流程，對每一個流程給出了解決方案。下面將在上述基礎(chǔ)上給出主觀試題計算機(jī)自動評閱模型的流程。

Step1：初始條件

已知標(biāo)準(zhǔn)答案A，將其表示為關(guān)鍵詞序列：A=(a1，a2，…，an)；考生答案B，表示為關(guān)鍵詞序列：B=(b1，b2，…，bn)；標(biāo)準(zhǔn)分值S0。

除了上述的條件，模型還需要如下中間條件：

⑴ 考生答案中包含多少個符合條件的知識點；

⑵ 考生答案知識點與標(biāo)準(zhǔn)答案之間的相似度。

Step2：算法

⑴ 查找匹配符合條件的知識點

提取考生答案中每一個關(guān)鍵詞，對照先前創(chuàng)建好的知識庫，從底層開始遍歷搜索，當(dāng)找到對應(yīng)的概念節(jié)點時，提取該節(jié)點的高度、密度等屬性信息，并保存起來，搜索完成后即可進(jìn)行相似度的計算。

⑵ 求解概念相似度

概念相似度的計算采用語義相似度技術(shù)。設(shè)標(biāo)準(zhǔn)答案A可以表示為知識點的一個向量組A=(a1，a2，…，an)，則通過概念語義相似度算法可得到任意兩概念之間的相似度Sin(ai，bj)，其中i=1，2，…，m，j=1，2，…，n。

⑶ 求解語句相似度

把標(biāo)準(zhǔn)答案A與考生答案B之間的相似度表示為概念相似度矩陣，并把該矩陣處理為[0,1]區(qū)間上的一個歸一化相似度量。

Step3：確定最后評分結(jié)果

為了考慮不同知識點對得分的貢獻(xiàn)值，本文把不同知識點對得分的貢獻(xiàn)值以權(quán)值λj的形式分配到模型中。λj由出題老師在出題的時候根據(jù)不同重點的知識點直接給定，其中j=1,2，…，n。通過加入權(quán)值因素，本文最終確定的主觀試題自動評分結(jié)果如下：

⑸

式中。

圖2主觀題自動評閱模型流程圖

按照上述思路，本文確定的主觀試題自動評閱模型流程如圖2所示。

6 實例分析

下面我們以一個實例來介紹試題的評閱過程。設(shè)試題題干為：“計算機(jī)硬件由什么組成？”。

考生甲的答案是：“計算機(jī)硬件包括處理器、總線、存儲器、輸入輸出設(shè)備”。

考生乙的答案是：“計算機(jī)硬件包括CPU、總線、內(nèi)存、硬盤、鍵盤、顯示器”。

考生丙的答案是：“計算機(jī)硬件包括中文分詞技術(shù)和語義相似度技術(shù)”。

標(biāo)準(zhǔn)答案是：“計算機(jī)硬件包括處理器、總線、存儲器、輸入輸出設(shè)備”。標(biāo)準(zhǔn)答案關(guān)鍵詞序列為：“計算機(jī)；硬件；處理器；總線；存儲器；輸入輸出設(shè)備”。

考生甲的答案可表示為關(guān)鍵詞序列：“計算機(jī)；硬件；處理器；總線；存儲器；輸入輸出設(shè)備”。

考生乙的答案可表示為關(guān)鍵詞序列：“計算機(jī)；硬件；CPU；總線；內(nèi)存；硬盤；鍵盤；顯示器”。

考生丙的答案可表示為關(guān)鍵詞序列：“計算機(jī)；硬件；中文；分詞；技術(shù)；語義；相似度”。

設(shè)該題總分為10，對應(yīng)關(guān)鍵詞權(quán)值序列為：“0.3；0.3；0.2；0.2”。本文把考題中出現(xiàn)的關(guān)鍵詞如“計算機(jī)；硬件”按權(quán)值為0對待。最終計算結(jié)果如下：

考生甲=10*（1*0.3+1*0.3+1*0.2+1*0.2）=10。

考生乙=10*（0.919*0.3+1*0.3+0.524*0.2+ 0.512*0.2）=7.1729=7。

考生丙=10*（0.01*0.3+0.01*0.3+0.01*0.2 +0.01*0.2）=0.01=0。

從計算結(jié)果可以看出，考生甲得滿分，符合判斷結(jié)果；考生乙的答案與標(biāo)準(zhǔn)答案只有一個關(guān)鍵詞是相同的，而其他答案只能算是與標(biāo)準(zhǔn)答案相近或者相似，最終模型給出7分，其結(jié)果基本與人工評閱結(jié)果相近；至于考生丙的答案完全與標(biāo)準(zhǔn)答案無關(guān)，但模型給出了一個很小的分值，這是因為，對于完全不相關(guān)的概念，本文認(rèn)為它們之間的語義距離為無窮大，直接按照相似度為0.01處理。

為了進(jìn)一步驗證模型實際應(yīng)用效果，本文隨機(jī)抽取100道簡答題進(jìn)行在線測試，并與的人工閱卷結(jié)果作了對比。統(tǒng)計結(jié)果表明，其中完全符合的8例，不完全符合但準(zhǔn)確率90%以上的40例，準(zhǔn)確率在80%-90%之間的18例，完全不相關(guān)的8例，剩余26例。如果認(rèn)為準(zhǔn)確率在80%內(nèi)都算合格，則有66例符合評閱要求，占總數(shù)66%，不符合要求的34例，占總數(shù)34%。其中

相對誤差=[2]。

實際上對于與標(biāo)準(zhǔn)答案完全不相關(guān)的答案來說，經(jīng)過分詞處理后并沒有在知識樹網(wǎng)絡(luò)結(jié)構(gòu)中找到對應(yīng)的節(jié)點。本文把這些詞按照未登錄詞進(jìn)行處理，同時把這些詞錄入到未登錄詞數(shù)據(jù)表中，在后續(xù)的試題管理中，由老師根據(jù)知識樹網(wǎng)絡(luò)結(jié)構(gòu)需求進(jìn)行處理，對于符合要求的添加到知識庫中，不合要求的則拋棄，這樣當(dāng)下次考生給出相似答案的時候，系統(tǒng)會相應(yīng)給出更為準(zhǔn)確的計算結(jié)果。本文處理后剩余4道試題的評閱結(jié)果在相對誤差范圍內(nèi)，這樣符合要求評閱結(jié)果的比例上升為70%。

7 結(jié)束語

本文分析了目前在線考試系統(tǒng)自動評閱技術(shù)的現(xiàn)狀，從知識庫的構(gòu)建、概念相似度的處理、語句相似度三個方面給出了主觀試題自動評閱問題的詳細(xì)解決方案，并詳細(xì)介紹了計算機(jī)自動評閱模型的流程。在模型的設(shè)計和實現(xiàn)過程中以計算機(jī)基礎(chǔ)課程為研究對象，基于試題答案的組織結(jié)構(gòu)構(gòu)建了專業(yè)領(lǐng)域知識庫，并采用一種改進(jìn)的多因素語義相似度算法來解決概念級相似度求解問題。實例運算結(jié)果表明，模型基本實現(xiàn)了主觀試題的自動評閱功能。

參考文獻(xiàn)：

[1] 李輝陽,韓忠愿.有限領(lǐng)域簡述文字的自動判讀及其在CAI中的應(yīng)用[J].

計算機(jī)工程與應(yīng)用,2002.

[2] 高思丹,袁春風(fēng).語句相似度計算在主觀題自動批改技術(shù)中的初步應(yīng)

用[J].計算機(jī)工程與應(yīng)用,2004,14:132~135

[3] 黃康,袁春風(fēng).基于領(lǐng)域概念網(wǎng)絡(luò)的自動批改技術(shù)[J].計算機(jī)應(yīng)用研

究,2004.11:260~262

[4] 劉佩琦,李增智.基于模糊含權(quán)概念圖的主觀題自動方法研究[J].計

算機(jī)應(yīng)用研究,2009.26(12):4565~4567

[5] 李曉捷.基于Web的在線考試管理系統(tǒng)的設(shè)計與實現(xiàn)[D].(天津)天津

工業(yè)大學(xué),碩士學(xué)位論文,2005.12.

[6] 劉群,李素建.基于"知網(wǎng)"的詞匯語義相似度計算[C].第三屆漢語詞匯

語義學(xué)研討會論文集,2002:59~76

[7] AGIRREE, RIGAU G. A Proposal for Word Sense Disambiguation

Using Conceptual Distance[EB/OL].1995.12.11

[8] 蔣溢,丁優(yōu),熊安萍等.一種基于知網(wǎng)的詞匯語義相似度改進(jìn)計算方

法[J].重慶郵電大學(xué)(自然科學(xué)版),2009.21(4):533~537

[9] 黨麗瓊,劉文輝.一種改進(jìn)的多因素語義相似度計算方法[J].計算機(jī)

現(xiàn)代化,2011.10:24~26

[10] 穗志方.語句相似度研究中的骨架依存分析法及應(yīng)用[D].博士學(xué)位

論文,北京大學(xué),1998.5.

[11] Sergei Nirenburg,Constantine Donmashnew,Dean J Grannes.

Two Approaches to Matching in Example-based Machine Translation[C].In:Proceedings of the fifth International Conference on Theroretical and Methodological in Machine Translation of Natural Languages,1993:47~57