一種基于特征提取的簡(jiǎn)答題閱卷算法

唐朝霞

(淮陰工學(xué)院計(jì)算機(jī)工程學(xué)院,淮安223003)

0 引 言

隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展,考試從筆試到計(jì)算機(jī)輔助考試再發(fā)展到基于Web的無紙化考試已成為現(xiàn)實(shí).考試系統(tǒng)試題的類型主要有兩大類:一類是客觀題,答案比較明確、具有唯一性;另一類就是主觀題,答案沒有唯一標(biāo)準(zhǔn).目前的考試系統(tǒng)基本己實(shí)現(xiàn)對(duì)客觀題的自動(dòng)評(píng)分,對(duì)主觀題的自動(dòng)評(píng)分的考試系統(tǒng)還很少.近年來,一些專家也提出一些較好的方法:采用自動(dòng)搜索匹配技術(shù)[1-2],自動(dòng)處理錯(cuò)位、多字、漏字、錯(cuò)字等問題,自動(dòng)跳過非匹配部分,按照正確匹配率進(jìn)行評(píng)分.使用基于模糊理論的匹配技術(shù)對(duì)填空、文字錄入、程序設(shè)計(jì)等題型具有一定的智能,大大提高了計(jì)算機(jī)智能化閱卷的速度和準(zhǔn)確率.但對(duì)簡(jiǎn)答題這樣完全主觀的試題閱卷方面還不完善,需要進(jìn)一步研究與探索.

1 簡(jiǎn)答題閱卷算法

簡(jiǎn)答題的答案具有不唯一性,即有一定的模糊性,因此閱卷有較高的復(fù)雜性.目前采用的方法主要有:

(1)動(dòng)態(tài)規(guī)劃策略

文本的匹配利用動(dòng)態(tài)規(guī)劃策略匹配字符,采用從整體到局部的匹配策略,動(dòng)態(tài)挑選可能的最佳解,大大減少了計(jì)算量.在文本匹配策略上核心是求兩序列(文本字符序列)的最長(zhǎng)公共子序列(生物信息學(xué)中常用算法)[3].

定義2:設(shè) X,Y是兩個(gè)序列,且有Z＜X和Z＜Y,則稱Z是X和Y的公共子序列.

定義3:若Z＜X,Z＜Y,且不存在比Z更長(zhǎng)的X和Y的公共子序列,則稱Z是X和Y的最長(zhǎng)公共子序列,記為Z∈LCS(X,Y).如何找出 X和Y的一個(gè)最長(zhǎng)公共子序列?考慮用動(dòng)態(tài)規(guī)劃法.引進(jìn)一個(gè)二維數(shù)組C,用C[i,j]記錄Xi與Yj的LCS的長(zhǎng)度.

如果是自底向上進(jìn)行遞推計(jì)算,那么在計(jì)算C[i,j]之前,C[i-1,j-1],C[i-1,j]與C[i,j-1]均已計(jì)算出來,再根據(jù)Xi=Yj還是Xi≠Yj,就可以計(jì)算出C[i,j].最終得到X和Y的一個(gè)最長(zhǎng)公共子序列C.就得到了學(xué)生答案與已有試題標(biāo)準(zhǔn)答案的相似程度.

動(dòng)態(tài)規(guī)劃策略克服“一一對(duì)應(yīng)”比較方法的弊病.然而很多的簡(jiǎn)答題,并不是答案中每個(gè)字符都可以得分,而且每個(gè)知識(shí)點(diǎn)的不同關(guān)鍵詞對(duì)應(yīng)不同的分值,所以該方法可以解決文本匹配的相似度問題,但不適合于簡(jiǎn)答題的閱卷評(píng)分.

(2)模糊數(shù)學(xué)中的單向貼近度

為解決學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度表示問題,把學(xué)生答案和標(biāo)準(zhǔn)答案均看成字符串,以字符串S1和S2為例介紹計(jì)算字符串S1貼近于字符串S2的單向貼近度,首先把S1分解為若干個(gè)有效字符Ul,U 2,…,Un.然后判斷第一個(gè)字符Ul是否包含在字符串S2中,如果不包含標(biāo)記為0,否則標(biāo)記為1,并從S2中去掉包含Ul的字符,對(duì)S2進(jìn)行第二個(gè)字符U2的相同處理,一直把Ul,U2,…,Un判斷完畢.計(jì)算Sl分解后的單字符Ul,U 2,…,Un在S2出現(xiàn)的次數(shù)之和m占S1總有效字符數(shù)n的比值,并記為單向貼近度[4].該種方法在一定程度上可以解決學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度問題,但存在需要把S1分解為若干個(gè)有效字符進(jìn)行比較的麻煩,降低了閱卷的速度.其次,由于不是答案中每個(gè)字符都可以得分,所以并不是學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度越大,試題的得分就越高.

(3)句子相似度

首先將答案分解為句子,將各語句再進(jìn)行分詞,根據(jù)該詞向量矩陣,構(gòu)造句子的相似矩陣,求得學(xué)生答案與標(biāo)準(zhǔn)答案的句子相似度[5].該算法能夠解決學(xué)生答案與標(biāo)準(zhǔn)答案的匹配問題,但同樣存在需要分詞的麻煩,且如果利用一些現(xiàn)有的分詞系統(tǒng),也不能完全正確分解出與知識(shí)點(diǎn)相關(guān)的關(guān)鍵詞,降低了閱卷的質(zhì)量和速度.

2 基于特征提取的簡(jiǎn)答題閱卷算法

分析教師的閱卷過程,教師在人工評(píng)閱簡(jiǎn)答題時(shí)一般先預(yù)先制定好一套評(píng)分標(biāo)準(zhǔn),然后將每道試題的總分劃分成若干部分,將分?jǐn)?shù)分配到試題的求解過程中的一些關(guān)鍵的步驟或關(guān)鍵的詞語上,稱之為得分點(diǎn).最后計(jì)算學(xué)生答案中的得分點(diǎn)的得分總和,即為最終得分.

根據(jù)對(duì)人工閱卷過程的分析可以發(fā)現(xiàn)簡(jiǎn)答題評(píng)分的因素主要有兩個(gè):一是標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn),另一個(gè)是學(xué)生得分點(diǎn)吻合的多少.因此,在簡(jiǎn)答題閱卷中,首先將標(biāo)準(zhǔn)答案分成若干個(gè)得分點(diǎn),而文本的近義詞問題導(dǎo)致每個(gè)得分點(diǎn)又可能有若干個(gè)特征值.系統(tǒng)將標(biāo)準(zhǔn)答案的基本特征存儲(chǔ)起來,構(gòu)造一個(gè)答案特征表[6],并為不同的答案特征配上權(quán)值(分值),改變上述完全匹配答案的模型,不再給出試題的完整答案,而是從答案特征表中為試題提取相關(guān)特征進(jìn)行評(píng)定其小分,最后累加答案中各特征值的得分即可.

例如簡(jiǎn)答題1:因特網(wǎng)為我們主要提供了哪些服務(wù),設(shè)總分為10分,構(gòu)造其答案特征表如圖1.

圖1 答案特征表

圖中答案特征表的頭結(jié)點(diǎn)值表示標(biāo)準(zhǔn)答案的特征值的分值,表結(jié)點(diǎn)的值表示標(biāo)準(zhǔn)答案中某得分點(diǎn)的特征值,由于文本存在的近義詞問題,所以標(biāo)準(zhǔn)答案的同一個(gè)得分點(diǎn)可能有不同的特征值.

閱卷時(shí),首先獲取學(xué)生的答案,從標(biāo)準(zhǔn)答案特征表中提取第一個(gè)得分點(diǎn)的特征值,然后與學(xué)生的答案進(jìn)行匹配.如果匹配成功,將該特征值的分值加入該簡(jiǎn)答題的得分,再進(jìn)行下一個(gè)得分點(diǎn)的匹配;如果匹配失敗,繼續(xù)提取該得分點(diǎn)的下一個(gè)特征值與學(xué)生的答案再進(jìn)行匹配,直到匹配完答案特征表中所有得分點(diǎn),最終得到該題的得分.簡(jiǎn)答題的閱卷算法如算法1.

算法1:For i=1 To n

/*n表示某簡(jiǎn)答題的答案特征表的得分點(diǎn)總數(shù)

從標(biāo)準(zhǔn)答案特征表中提取出第i個(gè)得分點(diǎn)的特征值Ti

Do

If Ti匹配學(xué)生的答案 Then

將特征值Ti的分值累加到該題總分sum

Exit Do

Else

If答案特征表第i個(gè)得分點(diǎn)還有下一個(gè)特征值Then

Ti=答案特征表第i個(gè)得分點(diǎn)的下一個(gè)特征值

Else

Exit Do

End If

End If

Loop

Next i

算法1將學(xué)生答案與答案特征表中提取的特征值進(jìn)行匹配,再根據(jù)該特征值的權(quán)值完成閱卷.其優(yōu)點(diǎn)為:

1)增加試題時(shí)只需輸入試題答案得分點(diǎn)的特征值,減輕了教師輸入標(biāo)準(zhǔn)答案的工作量.

2)閱卷按特征值進(jìn)行匹配屏蔽了一些與得分點(diǎn)無關(guān)的字符的比較,提高了閱卷的準(zhǔn)確性和速度.

但算法1將學(xué)生答案與答案特征表中提取的特征值進(jìn)行匹配時(shí),沒有任何的順序限制,所以只適合得分點(diǎn)順序無關(guān)的簡(jiǎn)答題.為了解決將學(xué)生答案與答案特征表中提取的特征值需要依次進(jìn)行匹配的問題,本文引入定位特征值的概念,簡(jiǎn)答題標(biāo)準(zhǔn)答案得分點(diǎn)的定位特征值定義為該得分點(diǎn)在標(biāo)準(zhǔn)答案中的順序.

例如簡(jiǎn)答題2:圖像是如何進(jìn)行數(shù)字化的?設(shè)總分為10分,構(gòu)造其答案特征表如圖2.

圖2 答案特征表

圖中答案特征表的頭結(jié)點(diǎn)值有兩項(xiàng),第一項(xiàng)表示某得分點(diǎn)的定位特征值,第二項(xiàng)表示標(biāo)準(zhǔn)答案的特征值的分值.表結(jié)點(diǎn)的值表示標(biāo)準(zhǔn)答案中同一得分點(diǎn)的特征值.

閱卷時(shí)首先獲取學(xué)生的答案,根據(jù)定位特征值順序從答案特征表中提取特征值信息,然后與學(xué)生的答案進(jìn)行匹配.如果匹配成功,將該特征值的分值加入簡(jiǎn)答題得分,并從學(xué)生答案匹配成功后的位置開始再進(jìn)行下一個(gè)得分點(diǎn)的匹配;

如果匹配失敗,繼續(xù)提取該得分點(diǎn)的下一個(gè)特征值與學(xué)生的答案進(jìn)行匹配,直到匹配完答案特征表中所有得分點(diǎn),最終得到該題的總分.簡(jiǎn)答題的閱卷算法如算法2.

算法2:For i=1 To n

/*n表示某簡(jiǎn)答題的答案特征表的得分點(diǎn)總數(shù)

從答案特征表中提取出定位特征值為i的特征值Ti

Do

If Ti匹配學(xué)生的答案Then

將特征值Ti的分值累加到該題總分sum

學(xué)生的答案=與特征值Ti匹配位置后的字符串

Exit Do

Else

If 答案特征表中定位特征值為i的特征值Ti還有下一個(gè)特征值Then

Ti=答案特征表中定位特征值為i的下一個(gè)特征值

Else

Exit Do

End If

End If

Loop

Next i

3 閱卷結(jié)果分析

為驗(yàn)證算法進(jìn)行閱卷的可行性和有效性,以簡(jiǎn)答題2為例,五位學(xué)生輸入的答案如下:

答案1:圖像數(shù)字化的過程為:1、掃描 2、取樣3、量化

答案2:圖像首先掃描得到若干取樣點(diǎn),在分色,最后數(shù)字化.

答案3:1)掃描2)分色3)取樣4)A/D

答案4:1、分色2、取樣3、掃描4、量化

答案5:圖象的數(shù)字化過程為取樣、分色和數(shù)字化.

采用算法2閱卷的結(jié)果如表1:

表1 閱卷結(jié)果表

4 結(jié)束語

目前人工智能技術(shù)中自然語言理解這一領(lǐng)域仍在研究之中,因而要實(shí)現(xiàn)計(jì)算機(jī)完全的理解閱卷有一定的難度.本文提出的基于特征提取的簡(jiǎn)答題閱卷算法,既減輕了教師輸入的工作量,又提高了簡(jiǎn)答題閱卷的準(zhǔn)確性和速度.并引入定位特征值的概念,解決了學(xué)生答案與特征值需要依次進(jìn)行匹配的問題.

[1]劉 琰,周 理.基于VLCA的關(guān)鍵字查詢匹配算法[J].科學(xué)技術(shù)與工程,2008,(2):420-423.

[2]李 明,王 麗.基于本體的信息檢索系統(tǒng)模型[J].蘭州理工大學(xué)學(xué)報(bào),2007,(2):90-93.

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