基于多因素語義相似度的主觀題自動(dòng)評(píng)閱方法研究

黨麗瓊 劉文輝

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

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

中圖分類號(hào)：TP399 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ì)算機(jī)網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，無紙化考試逐漸成為一種新的發(fā)展方向。在無紙化考試系統(tǒng)的開發(fā)中，除一般試題庫的設(shè)計(jì)、試卷的組織管理以及考試過程的控制外，計(jì)算機(jī)自動(dòng)閱卷模塊的設(shè)計(jì)是一個(gè)重要的內(nèi)容。對(duì)于完善的無紙化考試系統(tǒng)來說，自動(dòng)閱卷模塊除了提供客觀試題自動(dòng)評(píng)閱的功能，還必須能夠解決好主觀題自動(dòng)閱卷問題。由于考生答案的靈活性和多樣性，主觀題評(píng)閱會(huì)涉及到人工智能、模式識(shí)別和計(jì)算機(jī)自然語言理解等多方面系統(tǒng)知識(shí)，這就使得主觀題的自動(dòng)評(píng)閱成為自動(dòng)閱卷設(shè)計(jì)中的技術(shù)難點(diǎn)。

1 主觀試題自動(dòng)評(píng)閱

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

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

2 知識(shí)表示

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

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

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

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

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

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

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

3 概念相似度計(jì)算

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

⑴

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

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

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

⑵

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

4 句子相似度的處理

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

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

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

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

⑶

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

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

⑷

5 自動(dòng)評(píng)閱模型的實(shí)現(xiàn)

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

Step1：初始條件

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

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

⑴ 考生答案中包含多少個(gè)符合條件的知識(shí)點(diǎn)；

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

Step2：算法

⑴ 查找匹配符合條件的知識(shí)點(diǎn)

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

⑵ 求解概念相似度

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

⑶ 求解語句相似度

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

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

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

⑸

式中。

圖2主觀題自動(dòng)評(píng)閱模型流程圖

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

6 實(shí)例分析

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

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

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

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

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

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

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

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

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

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

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

相對(duì)誤差=[2]。

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

7 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

究,2004.11:260~262

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

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

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

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

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

語義學(xué)研討會(huì)論文集,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ì)算方

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

[9] 黨麗瓊,劉文輝.一種改進(jìn)的多因素語義相似度計(jì)算方法[J].計(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