李紀(jì)扣，韓建宇，王 嫄

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

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

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

1 主觀題目閱卷原理

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

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

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

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

2.1 關(guān)鍵詞搜索匹配

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

typedef struct{

Py_ssize_hash；

PyObject * key；

PyObject * value

} PyDictEntry；

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

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

(1)初始化 root節(jié)點為根節(jié)點，并設(shè)置 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)移后均有空間進(jìn)行存儲．此時，設(shè)置當(dāng)前的base值為該begin值．

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

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

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

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

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

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

圖3 關(guān)鍵詞搜索匹配流程Fig. 3 Matching process of keywords

關(guān)鍵詞搜索匹配的具體步驟如下：

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

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

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

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

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

2.2 相似度求解

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

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

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

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

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

2.3 相似度融合

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

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

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

3 實 驗

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

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

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

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

實驗對比方法采用人工指定參數(shù)的相似度計算方法[9]．該方法在關(guān)鍵詞集合的基礎(chǔ)上通過計算關(guān)鍵詞相似度與集合貼近度，得到文本最終的相似度并將其作為題目得分權(quán)重．其中人工指定關(guān)鍵詞權(quán)重參數(shù) P＝0.7作為可信參數(shù)，語義貼近度閾值選取 0.15作為可信參數(shù)，ψ(A, B)表示關(guān)鍵詞相似度，δ(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%．不同答案的用詞差異導(dǎo)致關(guān)鍵詞匹配命中率較低，致使相似度差異較大；論述題中包含較多子句，句子整體相似度求解時子句權(quán)重平均分配導(dǎo)致差異增加；簡答題與名詞解釋題等短文本答案中的關(guān)鍵詞特征明顯，評閱效果較好；由于答案中的語序關(guān)系通過關(guān)鍵詞的相對距離系數(shù)得到了更準(zhǔn)確的描述，所以，對語序關(guān)系突出的題目評閱效果較好．評閱準(zhǔn)確率整體較高，說明該模型方法對于主觀試題有較好的評閱效果．

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

4 結(jié) 語

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