基于相似度融合算法的主觀題自動閱卷機制

李紀扣，韓建宇，王 嫄

(天津科技大學計算機科學與信息工程學院，天津 300457)

主觀題目閱卷自動化是目前機考領域的前沿課題之一．主觀題目答案中不同種語言、字符、語言模式差異所導致相似度計算中的復雜性和準確性問題是研究的重點方向[1]．文本結(jié)構(gòu)差異、語義的不一致導致了相似度刻畫的多樣性，而且語義依存樹下的相似度、基于知網(wǎng)的語義相似度等算法均對應用環(huán)境有較嚴格的要求[2]．基于語義依存樹的相似度計算方法要先將語句的主干語義信息抽取成為語義表達式，再通過計算該語義表達式的相似度用以代替語句的相似度[3–4]；基于知網(wǎng)的相似度計算通過維護一個大規(guī)模語料庫來得到文本的相似度[5]．通過挖掘獨立詞對(word to word)之間潛在語義關系的方法的必要條件是能夠在語料庫中找到詞對的最優(yōu)搭配[6–7]．這些方法均從語言學角度去分析語法特征，從語法上解決相似度問題．而對于理工科教學中題目答案的正確性判定，答案文本的關鍵詞特征比其語法特征具有更高的重要度，并且基于關鍵詞特征的相似度計算不需要大量的語法分析，能夠降低相似度計算的復雜度[8]．在這種以文本結(jié)構(gòu)作為切入點的模式下，有人提出了一種基于人工指定參數(shù)的相似度計算方法，該方法將關鍵詞特征通過人為指定參數(shù)的方式組合得到文本的綜合相似度[9]．以上的分析研究表明，對文本結(jié)構(gòu)特征進行計算能夠得到文本相似度，但計算過程中很少考慮語序特征．

針對特定背景下的主觀題目自動閱卷，本文提出了一種基于相似度融合算法的相似度模型，在關鍵詞匹配的基礎上根據(jù)相對距離計算語序相似度，進而用統(tǒng)計回歸分析方法對關鍵詞相似度與詞序相似度特征進行融合，得到文本的綜合相似度，從而實現(xiàn)基于文本結(jié)構(gòu)特征的主觀題自動閱卷．

1 主觀題目閱卷原理

主觀題目閱卷采用基于文本結(jié)構(gòu)的相似度模型實現(xiàn)，模型結(jié)構(gòu)見圖 1．模型主要包含關鍵詞相似度計算方法、詞序相似度計算方法以及相似度融合方法．由于文本中關鍵詞同時代表著語義與結(jié)構(gòu)特性，所以文本的相似度通過文本關鍵詞特征來進行計算[10]．關鍵詞特征相似度通過關鍵詞相似度與詞序相似度兩維度分別進行計算，最后通過基于樣本數(shù)據(jù)的二元回歸分析實現(xiàn)不同維度的相似度融合，得到文本的綜合相似度．

圖1 基于文本結(jié)構(gòu)的相似度模型結(jié)構(gòu)Fig. 1 Similarity model structure based on text structure

在關鍵詞特征相似度計算過程中，通過將答案關鍵詞在標準答案關鍵詞序列空間中進行搜索匹配，得到關鍵詞的命中信息用于計算關鍵詞相似度，得到位置信息用于計算詞序相似度．其中，關鍵詞相似度通過求解關鍵詞序列的余弦向量夾角值得到[11]，詞序相似度通過計算關鍵詞在不同文本中的位置差的相對距離來得到．關鍵詞不同維度的相似度可以抽象為影響文本綜合相似度的因子，通過線性回歸分析得到不同因子對于因變量的權(quán)重關系，即得到不同維度的相似度對于文本綜合相似度的影響程度．將關鍵詞特征相似度與文本綜合相似度的二元線性回歸函數(shù)作為題目答案評分準則函數(shù)進行題目評分．

2 方法設計與實現(xiàn)

2.1 關鍵詞搜索匹配

在關鍵詞搜索匹配前，通過數(shù)組 Trie樹構(gòu)建標準答案序列空間．數(shù)組 Trie樹是將樹形節(jié)點狀態(tài)通過數(shù)組保存的一種字符前綴樹，Trie樹節(jié)點定義[12]為

typedef struct{

Py_ssize_hash；

PyObject * key；

PyObject * value

} PyDictEntry；

其中：key用于存儲節(jié)點字符；value用于存儲該節(jié)點的子節(jié)點以及當前節(jié)點的狀態(tài)、子節(jié)點相對于當前節(jié)點的偏移值(數(shù)組 base)、當前節(jié)點的父節(jié)點狀態(tài)(數(shù)組check)以及當前節(jié)點的位置標記值(index)．

基于 Trie樹的序列空間構(gòu)建過程包括初始狀態(tài)確定、字符編碼讀取、狀態(tài)轉(zhuǎn)移、結(jié)果存儲．在狀態(tài)轉(zhuǎn)移過程中，對于每一個關鍵詞，從狀態(tài) s到 t滿足base[s]＋code＝t、check[t]＝base[s]．字符編碼用 code表示，狀態(tài)轉(zhuǎn)移中選取字符的 GBK2312編碼集的十進制數(shù)取哈希映射后的值作為該值．序列空間構(gòu)建過程如下：

(1)初始化 root節(jié)點為根節(jié)點，并設置 base[root]＝1作為起始狀態(tài)．

(2)初始化base和check兩個狀態(tài)轉(zhuǎn)移記錄數(shù)組.

(3)找出root節(jié)點的子節(jié)點集合 root.childs，并修改 base數(shù)組和check數(shù)組，使得 check[root.childs]＝base[root]＝1成立．

(4)對于每一個子節(jié)點，找到一個初始值 begin，使得每一個子節(jié)點經(jīng)過狀態(tài)轉(zhuǎn)移后均有空間進行存儲．此時，設置當前的base值為該begin值．

(5)根據(jù)得到的 begin值與字符 code，通過狀態(tài)轉(zhuǎn)移方程對節(jié)點進行插入，同時修改字符的check值.

(6)對于每一個子節(jié)點，循環(huán)調(diào)用步驟(3)、步驟(4)，如果狀態(tài)i對應某一個關鍵詞，且base[i]＝0，那么令 base[i]＝(-1)*i；如果 base[i]?。?，那么令base[i]＝(-1)*base[i]．即使得關鍵詞詞尾(葉子節(jié)點)其base值為負值．通過狀態(tài)轉(zhuǎn)移插入得到的Trie樹如圖2所示．

(7)經(jīng)過逐個插入得到關鍵詞字符的 i、base、check以及index數(shù)組列表．

在進行關鍵詞搜索匹配時，首先對待評分答案進行分詞、去停用詞等操作，得到待評分答案的關鍵詞集合．然后讀取根據(jù)標準答案文本構(gòu)建好的序列空間，根據(jù)當前狀態(tài)與轉(zhuǎn)移規(guī)則，通過字符編碼進行狀態(tài)轉(zhuǎn)移，根據(jù)命中條件進行命中判定．

圖2 Trie樹示意圖Fig. 2 Diagram of Trie tree

命中條件：定義當前狀態(tài)為 p，如果 base[p]＝＝check[base[p]] && base[base[p]]＜0則查找命中．關鍵詞搜索匹配流程見圖3．

圖3 關鍵詞搜索匹配流程Fig. 3 Matching process of keywords

關鍵詞搜索匹配的具體步驟如下：

(1)讀取待匹配關鍵詞，并將其拆解成為單個字符.

(2)讀取構(gòu)建好的關鍵詞序列結(jié)果數(shù)組，并將root節(jié)點定義為起始狀態(tài)p．

(3)讀取第一個字符的編碼 code，根據(jù)轉(zhuǎn)移規(guī)則驗證是否滿足條件 base[p]＝＝check[base[p]] &&base[base[p]]＜0．如果滿足，則當前字符的查找命中，繼續(xù)讀取下一個字符進行驗證；如果不滿足，修改位置記錄數(shù)組值為0并退出查找過程．

(4)如果字符串中最后一個字符滿足步驟(3)，則該字符串查找命中，修改對應位置記錄數(shù)組的值為其index值并退出．

將待評分答案關鍵詞集合中的每一個關鍵詞都進行搜索匹配后，根據(jù)記錄關鍵詞位置情況的數(shù)組進行相似度特征計算．

2.2 相似度求解

相似度求解包括關鍵詞相似度求解與詞序相似度求解．在計算關鍵詞相似度時，首先通過詞袋模型對文本進行量化，將關鍵詞結(jié)構(gòu)特征轉(zhuǎn)化為向量特征．在向量空間模型中，文本被拆解成單字或者詞語組成的特征項集 D(T1，T2，…，Tn)，其中 Tk(1≤k≤n)是特征項，對應的是關鍵詞．兩個文本s1和s2之間的相似度可以用其特征項集對應的向量 V1，V2間夾角的余弦值表示．那么，標準答案文本與待評分答案文本的關鍵詞相似度 C可以通過式(1)進行求解．

詞序相似度通過相對距離進行計算．其中關鍵詞的位置標記為關鍵詞在文本特征項集中的序號；同一關鍵詞在不同文本特征項集中的位置差值定義為相對距離，用于刻畫其在語句內(nèi)部的位置差異，相對距離越小，相似程度越大．關鍵詞相對距離的計算方法見式(2)，其中dn2和dn1分別代表第n個關鍵詞在兩個不同文本s2、s1中的位置標記．

文本相對距離D的計算公式見式(3)．

將文本相對距離進行歸一化，得到表示文本詞序相似度的相對距離系數(shù)R，記為式(4)．

其中，Dmax為文本s1與文本s2間的最大相對距離．未命中關鍵詞的相對距離 d記為(n-1)，當 s2中關鍵詞全部缺失時，文本 s1與文本 s2間達到最大相對距離 Dmax＝(n-1)n．n為 s2中的元素個數(shù)，也就是集合長度．

2.3 相似度融合

在得到答案文本基于結(jié)構(gòu)的相似度特征后，采用統(tǒng)計回歸方法將不同維度的相似度以最優(yōu)的權(quán)重融合成為文本的綜合相似度．基于文本二維的結(jié)構(gòu)相似度特征，將關鍵詞相似度與詞序相似度定義為自變量，學生答案得分與題目滿分比值定義為因變量，定義二元線性回歸方程

式中：b0為常數(shù)項；b1、b2為回歸系數(shù)；C、R分別代表關鍵詞相似度與詞序相似度；y為答案得分與題目滿分的比值；μi為隨機誤差．

多子句文本的相似度選取各子句相似度的平均值作為其相似度，計算公式見式(6)．Si為文本第i個子句的綜合相似度．

3 實 驗

首先需要采集特定學科背景下的主觀題目人工閱卷結(jié)果作為樣本數(shù)據(jù)，通過統(tǒng)計分析方法獲得其相似度回歸函數(shù)．本次實驗采集“計算機體系結(jié)構(gòu)”課程的500道已閱試題作為樣本數(shù)據(jù)，數(shù)據(jù)來源為天津科技大學課程考試試題，試題類型包括簡答題、名詞解釋題和論述題，每條數(shù)據(jù)包含題目、標準答案、學生答案與得分四項內(nèi)容．

根據(jù)相似度算法求得學生答案與標準答案的關鍵詞相似度 C、相對距離系數(shù) R，并對得分與滿分比值進行二元回歸分析，得到回歸函數(shù)見式(7)(隨機誤差忽略不計)．

對回歸函數(shù)進行顯著性檢驗 F檢驗(顯著性水平取 α＝0.05)得 F0.05＝2.735＜F(2497)＝3.014，接受線性回歸顯著假設．T檢驗得 T＝2.003，查表得2.003＞ T0.025/497＝1.965，接受函數(shù)回歸參數(shù)顯著有效假設．即該回歸方程具有統(tǒng)計學意義，可以用來進行題目評分．

選取 200道“計算機體系結(jié)構(gòu)”主觀題目作為測試數(shù)據(jù)，其中包含 100道簡答題、50道名詞解釋題、50道論述題．將題目滿分標準化為 100分．對樣本數(shù)據(jù)進行閱卷，首先調(diào)用中科大分詞系統(tǒng)(NLPIR)進行分詞與去停用詞處理，將文本字符串處理成為關鍵詞序列集合．然后通過數(shù)組 Trie樹將關鍵詞集合構(gòu)建成為可供搜索的序列空間，在關鍵詞搜索匹配的基礎上計算關鍵詞相似度與詞序相似度作為文本不同維度的相似度，進而通過二元線性回歸進行融合，得到答案文本的綜合相似度．

實驗對比方法采用人工指定參數(shù)的相似度計算方法[9]．該方法在關鍵詞集合的基礎上通過計算關鍵詞相似度與集合貼近度，得到文本最終的相似度并將其作為題目得分權(quán)重．其中人工指定關鍵詞權(quán)重參數(shù) P＝0.7作為可信參數(shù)，語義貼近度閾值選取 0.15作為可信參數(shù)，ψ(A, B)表示關鍵詞相似度，δ(A, B)表示文本 A、B貼近度，S0為題目滿分．方法 2中的得分計算公式見式(8)．

本文方法、對比方法及人工評閱的結(jié)果見圖 4，分段統(tǒng)計結(jié)果見表1．

圖4 閱卷結(jié)果對比Fig. 4 Comparison of grading results

表1 分段統(tǒng)計結(jié)果Tab. 1 Results of section calculation

統(tǒng)計評分結(jié)果誤差在 10分以內(nèi)的題目數(shù)量，本文方法為 89.5%，對比方法為 86.5%．不同答案的用詞差異導致關鍵詞匹配命中率較低，致使相似度差異較大；論述題中包含較多子句，句子整體相似度求解時子句權(quán)重平均分配導致差異增加；簡答題與名詞解釋題等短文本答案中的關鍵詞特征明顯，評閱效果較好；由于答案中的語序關系通過關鍵詞的相對距離系數(shù)得到了更準確的描述，所以，對語序關系突出的題目評閱效果較好．評閱準確率整體較高，說明該模型方法對于主觀試題有較好的評閱效果．

雖然在個別題目上存在評分偏差較大的情況，但是整體來看，本文方法的閱卷結(jié)果更加貼近人工閱卷結(jié)果，與人工評閱結(jié)果的兩條評分曲線也更加吻合，閱卷結(jié)果基本一致．對于某些特定需求下的閱卷工作，該相似度模型可行有效．

4 結(jié) 語

對于學科背景下的主觀題閱卷，本文通過 Trie樹實現(xiàn)關鍵詞匹配下的二維相似度模型，有效地避免了傳統(tǒng)閱卷模式的句法樹分析與向圖分析的復雜性，節(jié)約了系統(tǒng)開銷．其方法對于主觀題目的快速閱卷具有一定的現(xiàn)實意義．