面向大規(guī)模在線開放課程的編程題多特征綜合自動(dòng)評分方法

劉月霞,牛志堯,吳寧

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

?

面向大規(guī)模在線開放課程的編程題多特征綜合自動(dòng)評分方法

劉月霞,牛志堯,吳寧

(西安交通大學(xué)電子與信息工程學(xué)院,710049,西安)

針對大規(guī)模在線開放課程環(huán)境下C/C++語言學(xué)習(xí)者人數(shù)眾多、自動(dòng)評閱準(zhǔn)確率低的問題,提出一種基于多特征綜合分析的編程題自動(dòng)評分方法。通過對源程序編譯預(yù)處理剔除提示性信息,用詞法分析和抽象語法樹(AST)分別抽取學(xué)生程序和標(biāo)準(zhǔn)模板程序的多種特征并計(jì)算特征相似度,再根據(jù)程序編譯是否通過,采用不同策略綜合分析多種特征相似度進(jìn)行自動(dòng)評分。特征相似度包括多項(xiàng)測試用例運(yùn)行結(jié)果的相似度、AST抽取的各項(xiàng)特征的相似度和源程序代碼相似度。如果學(xué)生程序編譯失敗,在計(jì)算AST特征相似度的同時(shí)需進(jìn)行源程序代碼相似度分析。實(shí)驗(yàn)結(jié)果表明:相對于僅基于測試用例運(yùn)行結(jié)果的動(dòng)態(tài)測試方法和傳統(tǒng)靜態(tài)分析方法,所提方法的平均準(zhǔn)確率分別提高了18.48%和14.17%,評價(jià)結(jié)果與人工評分高度相關(guān)且無需借助人工輔助分析。該方法適用于大規(guī)模在線開放課程教學(xué)。

大規(guī)模在線開放課程;自動(dòng)評閱;多特征分析;抽象語法樹;相似度計(jì)算

自2012年起,大規(guī)模在線開放課程(massive open online courses,MOOC)開始在全球興起。對計(jì)算機(jī)程序設(shè)計(jì)類MOOC,編程練習(xí)是重要的環(huán)節(jié)。由于MOOC環(huán)境下的學(xué)習(xí)者人數(shù)眾多,依靠教師人工評閱編程作業(yè)不現(xiàn)實(shí)。目前,MOOC平臺(tái)對編程題的評判大多采用學(xué)生互評方式,部分平臺(tái)通過將學(xué)生作業(yè)的運(yùn)行結(jié)果與給定答案進(jìn)行比對的方式評分,以上評分方式并不適合對學(xué)生作業(yè)和考試程序的評分,難以滿足教學(xué)需求[1-2]。

學(xué)生程序一般具有規(guī)模小(代碼行數(shù)通常在100行以內(nèi))、在正確或基本正確情況下其代碼規(guī)模與標(biāo)準(zhǔn)模板程序相差不大、同一道題目可能會(huì)有多種解答、易出現(xiàn)語法錯(cuò)誤且錯(cuò)誤類型較多等特點(diǎn),這些特點(diǎn)決定了編程題自動(dòng)評分若要滿足教學(xué)需求必須解決以下幾個(gè)問題:①如何證明程序語義、知識(shí)的正確性;②如何衡量學(xué)生完成編程任務(wù)的正確程度;③如何處理有語法錯(cuò)誤的程序;④采用什么樣的評分模型才能獲得與人工閱卷相關(guān)性高的評分結(jié)果[3]。

近年來,已有多位學(xué)者針對學(xué)生編程作業(yè)特點(diǎn)開展自動(dòng)評分方法研究。目前的自動(dòng)評分方法主要分為兩大類:基于測試用例的動(dòng)態(tài)測試和基于程序中間表示形式的靜態(tài)分析。文獻(xiàn)[4-6]研究了動(dòng)態(tài)測試方法,通過隨機(jī)生成測試用例,然后比對學(xué)生程序與標(biāo)準(zhǔn)模板程序的運(yùn)行結(jié)果進(jìn)行評分。這是評判程序正確性最直接的方法,也是目前使用較多的編程題自動(dòng)評分方法,例如全國計(jì)算機(jī)等級考試中的編程題評閱系統(tǒng)等。這種評測方法的前提是程序必須能夠運(yùn)行,其不足是:①當(dāng)學(xué)生程序輸出與標(biāo)準(zhǔn)模板程序輸出格式不完全相符時(shí)會(huì)影響評分精度;②如果學(xué)生通過數(shù)學(xué)計(jì)算或其他方式直接輸出結(jié)果會(huì)獲得滿分,這顯然與實(shí)際情況不符;③若程序編譯失敗,只會(huì)給出零分。這些不足使其難以滿足程序設(shè)計(jì)課程教學(xué)的實(shí)際需求。國內(nèi)外眾多學(xué)者也研究了編程題的靜態(tài)分析方法。靜態(tài)分析通常是將源程序轉(zhuǎn)換為抽象語法樹或系統(tǒng)依賴圖等中間表示形式,從中間形式抽取出程序的各項(xiàng)特征,再根據(jù)特征信息的匹配度給出分值[7]。文獻(xiàn)[8]通過計(jì)算控制流圖節(jié)點(diǎn)的相似度進(jìn)行評分;文獻(xiàn)[9]通過匹配系統(tǒng)依賴圖抽取的程序特征進(jìn)行評分;文獻(xiàn)[10-11]通過分析抽象語法樹進(jìn)行評分。靜態(tài)分析方法能夠在一定程度上反映學(xué)生程序和標(biāo)準(zhǔn)模板程序的相似程度,較適合對學(xué)生程序的自動(dòng)評分,但完全依賴中間表示形式也存在不足,主要是當(dāng)程序因語法錯(cuò)誤導(dǎo)致編譯失敗時(shí),所生成的中間表示形式往往存在偏差,使提取的程序特征信息缺乏足夠的可信度,從而影響評分精度。

針對上述存在的問題,本文通過對人工評閱的思維過程進(jìn)行分析,對C/C++編程題自動(dòng)評分中的難點(diǎn)問題進(jìn)行深入研究,融合動(dòng)態(tài)測試與靜態(tài)分析方法的優(yōu)點(diǎn),提出了一種用于支撐MOOC教學(xué)的編程題多特征綜合分析自動(dòng)評分方法。

1 編程題多特征綜合評分方法

1.1 多特征綜合評分模型

人工評閱編程題的一般過程如下。①首先編譯學(xué)生程序,若編譯通過,直接觀察運(yùn)行結(jié)果。如果結(jié)果正確,再觀察程序規(guī)模以判斷是否是直接輸出結(jié)果;如果運(yùn)行結(jié)果不正確,會(huì)考察其編程思想、關(guān)鍵知識(shí)點(diǎn)(例如程序控制結(jié)構(gòu)、表達(dá)式、類定義等)等是否符合題目要求,根據(jù)符合度進(jìn)行評分。②若學(xué)生程序因存在語法錯(cuò)誤導(dǎo)致編譯失敗,則在扣除一定語法分之后,再考察其編程思想、知識(shí)點(diǎn)等進(jìn)行綜合評分。

基于人工評閱思想的自動(dòng)評分技術(shù)中,通過輸入測試用例、判斷運(yùn)行結(jié)果的方法稱為動(dòng)態(tài)測試;通過觀察程序編程思想、知識(shí)點(diǎn)、程序規(guī)模等特征的方法屬于靜態(tài)分析。人工評閱模式下的靜態(tài)分析依據(jù)人的判斷,而自動(dòng)評分系統(tǒng)中的靜態(tài)分析則需要借助程序的中間表示形式或源程序代碼。

作為程序的一種中間表示形式,抽象語法樹(abstract syntax tree,AST)是源程序代碼的抽象語法結(jié)構(gòu)的樹狀表現(xiàn)形式,樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)。之所以稱為“抽象”,是因?yàn)檫@里的語法并不表示出真實(shí)語法中出現(xiàn)的每個(gè)細(xì)節(jié),而只反映其特征。通過將學(xué)生程序和標(biāo)準(zhǔn)模板程序轉(zhuǎn)換為以AST表示的中間形式,從中抽取各種特征并對比特征相似度,就可以確定學(xué)生程序的正確程度。

由于編譯失敗時(shí)生成的AST文本與程序?qū)嶋H語義存在較大不一致性,甚至無法生成AST,所以在此情況下,僅依賴于對AST所抽取特征的分析會(huì)影響評分精度。為此,需進(jìn)一步分析程序源代碼,計(jì)算學(xué)生程序與標(biāo)準(zhǔn)模板程序的代碼相似度,結(jié)合對AST所抽取特征的分析結(jié)果進(jìn)行綜合評分。

基于上述分析,本文提出一種多特征綜合評分模型,如圖1所示。

圖1 編程題多特征綜合評分模型

圖中用虛線框及相應(yīng)數(shù)字編號表示評分過程的3個(gè)主要階段。①預(yù)處理與編譯。首先對學(xué)生程序代碼進(jìn)行預(yù)處理,去除提示性語句等影響運(yùn)行和評分準(zhǔn)確性的因素。然后調(diào)用編譯器進(jìn)行編譯,根據(jù)編譯是否通過決定后續(xù)的特征抽取和評分策略。②相似度分析。包括對多項(xiàng)測試用例運(yùn)行結(jié)果的相似度計(jì)算(簡稱用例運(yùn)行結(jié)果)、對從AST抽取的各項(xiàng)特征(簡稱AST特征)的相似度計(jì)算以及源程序代碼的相似度計(jì)算。如果學(xué)生程序編譯通過,則匹配學(xué)生程序和標(biāo)準(zhǔn)模板程序用例運(yùn)行結(jié)果相似度,若完全匹配,再分析程序規(guī)模,否則進(jìn)一步分析AST特征的相似度;如果學(xué)生程序編譯失敗,在計(jì)算AST特征相似度的同時(shí),還需進(jìn)行源程序代碼相似度分析。③多特征綜合評分。綜合相似度分析結(jié)果,結(jié)合人工評分準(zhǔn)則,按照評分策略給出評判結(jié)果。

1.2 代碼預(yù)處理

目前的程序設(shè)計(jì)類課程教學(xué)基本上僅涉及控制臺(tái)程序,因此學(xué)生程序會(huì)涉及大量的控制臺(tái)輸入輸出語句。部分提示性語句、暫停性語句等會(huì)對程序的自動(dòng)運(yùn)行產(chǎn)生影響。對于初學(xué)者,學(xué)生程序中可能會(huì)缺乏提示性語句或輸出的提示性語句與標(biāo)準(zhǔn)模板程序輸出的提示性語句在空格、字符內(nèi)容、大小寫等方面存在一定的不一致。另外,學(xué)生程序中若存在暫停性語句會(huì)導(dǎo)致其無法自動(dòng)結(jié)束。這些因素都會(huì)影響動(dòng)態(tài)測試的評分準(zhǔn)確性。

為了有效地進(jìn)行動(dòng)態(tài)測試,在編譯之前需對學(xué)生程序進(jìn)行以下預(yù)處理:①去掉程序中所有提示性信息,防止輸入輸出語句中的提示性信息對運(yùn)行結(jié)果匹配造成干擾;②去掉程序中的空行,避免空行對程序規(guī)模特征匹配的準(zhǔn)確度造成影響;③為防止因輸入格式問題而導(dǎo)致程序無法正常運(yùn)行,在不影響正常輸入的情況下去掉輸入中的各種符號,包括空格、換行符、分號等;④在不改變程序語義的情況下,去掉程序中的暫停性語句,例如system(“pause”)語句,主函數(shù)中位于輸出語句和return語句之間且靠近return語句的getchar()語句等。

1.3 用例運(yùn)行結(jié)果相似度計(jì)算

判斷程序是否正確的最直接方法就是運(yùn)行程序、觀察結(jié)果。如果結(jié)果正確,則完全匹配,相似度為1,否則相似度為0。一般情況下,學(xué)生程序的運(yùn)行結(jié)果通常包含的幾種形式見表1。

表1 學(xué)生程序常見運(yùn)行結(jié)果類型

根據(jù)學(xué)生程序運(yùn)行結(jié)果類型,匹配用例運(yùn)行結(jié)果相似度的算法如下。

輸入 學(xué)生程序的用例運(yùn)行結(jié)果,標(biāo)準(zhǔn)模板程序的用例運(yùn)行結(jié)果。

輸出 用例運(yùn)行結(jié)果相似度。

步驟1 設(shè)置i=1,n,s=0,其中n為用例運(yùn)行結(jié)果的組數(shù);i為當(dāng)前用例運(yùn)行結(jié)果的組數(shù)編號,i=1,2,…,n;s為從第1組到第i組的用例運(yùn)行結(jié)果相似度之和。

步驟2 判斷i是否小于等于n,如果是,判斷學(xué)生程序的第i組用例運(yùn)行結(jié)果的類型;否則,轉(zhuǎn)到步驟10。

步驟3 若結(jié)果是整型數(shù),直接匹配運(yùn)行結(jié)果,如果相等,則相似度為1,否則為0。

步驟4 若結(jié)果是浮點(diǎn)數(shù),設(shè)定誤差ε=0.000 01,匹配學(xué)生程序和標(biāo)準(zhǔn)模板程序運(yùn)行結(jié)果,如果誤差≤ε,則相似度為1,否則為0。

步驟5 若結(jié)果是數(shù)值序列,則依次匹配每個(gè)數(shù)值。對整型數(shù)組,僅當(dāng)所有數(shù)值都依序完全匹配時(shí),相似度為1,否則為0;對于浮點(diǎn)型數(shù)組,則依照步驟4所述方法,計(jì)算每對數(shù)值的匹配度。

步驟6 若結(jié)果是字符,利用ASCII碼進(jìn)行匹配。若完全匹配,則相似度為1,否則為0。

步驟7 若結(jié)果是字符串、字符串序列、混合序列等,先剔除不相關(guān)元素,例如空格、標(biāo)點(diǎn)符等,然后進(jìn)行字符匹配。

步驟8 若結(jié)果是算術(shù)表達(dá)式,將其轉(zhuǎn)換為逆波蘭表達(dá)式,再進(jìn)行字符匹配。

步驟9 計(jì)算前i組用例運(yùn)行結(jié)果相似度之和s,設(shè)置i=i+1,轉(zhuǎn)到步驟2。

步驟10 計(jì)算n組用例運(yùn)行結(jié)果的平均相似度值,即s/n。

步驟11 結(jié)束。

1.4 源程序代碼相似度分析

利用有限自動(dòng)機(jī)對預(yù)處理后的源程序進(jìn)行詞法分析,可以生成屬性字序列。單詞的屬性,例如分界符、標(biāo)識(shí)符、運(yùn)算符、關(guān)鍵字等是單詞的特征。屬性字是單詞及其特性的二元組,可表示為<關(guān)鍵字,’if’>、<運(yùn)算符,’+’>、<分界符,’;’>、<標(biāo)識(shí)符,’book’>等。例如C程序代碼:while(i>=j)i--;經(jīng)詞法分析后,可生成屬性字序列<關(guān)鍵字,’while’><分界符,’(’><標(biāo)識(shí)符,’i’><運(yùn)算符,’>=’><標(biāo)識(shí)符,’j’><分界符,’)’><標(biāo)識(shí)符,’i’><運(yùn)算符,’-’><運(yùn)算符,’-’><分界符,’;’>?？梢钥闯?屬性字序列反映了程序?qū)崿F(xiàn)的過程順序和包含的單詞及其特性。通過計(jì)算兩段程序?qū)傩宰中蛄械南嗨贫?就可判斷兩段程序的相似程度。

最長公共子序列(longest common subsequence, LCS)是將兩個(gè)或多個(gè)給定字符串分別刪除任意多個(gè)字符后得到的順序不變且長度最長的相同字符序列。LCS越長,序列越相似。因此,通過計(jì)算學(xué)生程序和標(biāo)準(zhǔn)模板程序的屬性字序列的最長公共子序列,根據(jù)最長公共屬性字子序列的長度以及學(xué)生程序和標(biāo)準(zhǔn)模板程序的屬性字序列長度,就可以計(jì)算出屬性字序列的相似度,也就是兩段程序的相似度?；趧?dòng)態(tài)規(guī)劃LCS算法的源程序代碼相似度S1的計(jì)算方法為

S1=2L(T1,T2)/(t1+t2)

(1)

式中:T1和T2分別表示學(xué)生程序和標(biāo)準(zhǔn)模板程序的屬性字序列;t1、t2表示T1和T2的長度;L(T1,T2)為T1和T2最長公共子序列的長度。

1.5 AST特征相似度分析

定義從AST中提取的能夠反映學(xué)生程序和標(biāo)準(zhǔn)模板程序相似性的各項(xiàng)特征如下。

定義1 規(guī)模特征。程序長度、程序詞匯量所組成的單元。程序長度為程序中的所有操作符和操作數(shù)的數(shù)量之和;程序詞匯量為程序中的所有操作符及操作數(shù)的種類數(shù)量之和。

定義2 變量特征。程序中全局變量和局部變量的類型和個(gè)數(shù)所組成的序列。

定義3 類特征?？梢宰畲蟪潭群饬款惖恼Z義結(jié)構(gòu)的特征向量,包括變量、調(diào)用、繼承、多態(tài)、方法個(gè)數(shù)等信息。

定義4 表達(dá)式特征。程序中運(yùn)算符種類和個(gè)數(shù)所組成的序列。

定義5 結(jié)構(gòu)特征。程序控制結(jié)構(gòu)序列?？刂平Y(jié)構(gòu)包括循環(huán)、選擇和順序結(jié)構(gòu)。為便于處理,用關(guān)鍵字Loop統(tǒng)一標(biāo)識(shí)循環(huán)結(jié)構(gòu)(while,do-while,for),用Branch統(tǒng)一標(biāo)識(shí)分支結(jié)構(gòu)(if-else,switch),用每個(gè)關(guān)鍵字后邊緊跟的數(shù)字表示關(guān)鍵字的嵌套深度。

如果將特征視為一個(gè)文檔,將特征分量視為文檔中的詞項(xiàng),那么計(jì)算學(xué)生程序和標(biāo)準(zhǔn)模板程序某項(xiàng)特征的相似度就相當(dāng)于計(jì)算兩個(gè)文檔之間的相似度。因此,可以利用向量空間模型來計(jì)算AST特征的相似度。

向量相似度[12]計(jì)算方法很多,例如夾角余弦法、廣義Jaccard系數(shù)法等。廣義Jaccard系數(shù)采用乘積方式,分母中減去兩個(gè)向量相同的部分,放大了向量的差異,增大了向量相似度的辨識(shí)度,常用來計(jì)算不完全相同的兩個(gè)向量的相似度,適用于如AST特征這樣的離散型數(shù)據(jù)。設(shè)向量u、v,這兩個(gè)向量的相似度使用廣義Jaccard系數(shù)計(jì)算的公式為

J(u,v)=uv/(‖u‖2+‖v‖2-uv)

(2)

其中J(u,v)表示了向量u和向量v共同具有的特征項(xiàng)在兩向量全部特征項(xiàng)中的比重。在不考慮特征項(xiàng)順序的情況下,式(2)反映了兩個(gè)向量的相似程度,可以利用向量空間模型計(jì)算從AST抽取的變量特征、表達(dá)式特征、類特征和規(guī)模特征。若用下標(biāo)1表示學(xué)生程序,下標(biāo)2表示標(biāo)準(zhǔn)模板程序,各特征的相似度計(jì)算方法為

(3)

式中:Si表示AST特征中特征i的相似度;Vi表示學(xué)生程度和標(biāo)準(zhǔn)模板程序中特征i的集合;d1i和d2i分別表示特征分量v在學(xué)生程序和標(biāo)準(zhǔn)模板程序中出現(xiàn)的頻數(shù)。

利用向量空間模型計(jì)算文檔相似度時(shí),并沒有考慮檢索詞出現(xiàn)的順序。由于結(jié)構(gòu)特征是程序控制流程的反映,具有一定的上下位順序關(guān)系,因此,對結(jié)構(gòu)特征的相似度計(jì)算采取與1.4節(jié)所述源程序代碼同樣的處理方法。

1.6 綜合評分策略

綜合各項(xiàng)特征的相似度分析結(jié)果,設(shè)計(jì)如下綜合評分模型

(4)

式中:F∈[0,100]為學(xué)生程序得分;N為特征個(gè)數(shù),由圖1可知,用于評判學(xué)生程序的特征信息總體包括用例運(yùn)行結(jié)果、AST抽取的5項(xiàng)特征和源程序代碼共7個(gè)特征,即N=7;Si∈[0,1]為特征i的相似度,Si為1表示學(xué)生程序與標(biāo)準(zhǔn)模板程序的特征i完全匹配;wi為特征i的權(quán)重值,取值范圍為[0,1]。不同情況下各特征的wi值設(shè)置不同。按照圖1所示評分模型,當(dāng)學(xué)生程序編譯通過時(shí),源程序代碼特征的權(quán)重為0;當(dāng)學(xué)生程序編譯失敗時(shí),用例運(yùn)行結(jié)果特征的權(quán)重為0。

根據(jù)學(xué)生程序是否編譯通過,設(shè)計(jì)綜合評分策略如下。

(1)學(xué)生程序編譯通過。①如果全部測試用例運(yùn)行結(jié)果正確且規(guī)模相似度達(dá)到設(shè)定閾值,輸出學(xué)生程序?yàn)闈M分;②若部分測試用例運(yùn)行正確,依據(jù)式(4)進(jìn)行評分,此時(shí)結(jié)果特征和AST各項(xiàng)特征的權(quán)重均為1/6;③對全部測試用例運(yùn)行結(jié)果正確但規(guī)模相似度小于設(shè)定閾值、全部測試用例運(yùn)行均不正確、編譯成功但不可運(yùn)行等3種情況,依據(jù)人工評分原則需扣除一定的錯(cuò)誤分,修改評分模型為

%

(5)

由于此時(shí)運(yùn)行結(jié)果對評分已經(jīng)沒有意義,故設(shè)置用例運(yùn)行結(jié)果特征的權(quán)重時(shí)將AST各項(xiàng)特征的權(quán)重值調(diào)整為1/5。

(2)學(xué)生程序編譯失敗。①如果AST生成成功,依據(jù)人工評分原則編譯失敗需扣除一定語法分,然后再綜合考慮AST特征和源程序代碼相似度進(jìn)行評分,修改評分模型為

%

(6)

此時(shí)源程序代碼相似度和AST各項(xiàng)特征的權(quán)重值均為1/6;②如果AST生成失敗,即無法獲取AST特征,說明學(xué)生程序存在較為嚴(yán)重的語法錯(cuò)誤,依據(jù)人工經(jīng)驗(yàn)取源程序代碼相似度和0.1之間的較小值進(jìn)行評分。

2 實(shí)驗(yàn)結(jié)果與分析

2015年,我們將多特征綜合分析自動(dòng)評分方法(multi-feature analysis,MFA)應(yīng)用于“大學(xué)計(jì)算機(jī)”MOOC在線編程作業(yè)和期末考試的自動(dòng)評判中,并以人工評分為標(biāo)準(zhǔn),對期末考試的367份答卷、10道編程題進(jìn)行了評分準(zhǔn)確率測試。評分準(zhǔn)確率的計(jì)算公式為

%

(7)

式中:P是評分準(zhǔn)確率;n是考生答卷份數(shù);M1是教師嚴(yán)格按照評分準(zhǔn)則給出的分?jǐn)?shù);M2是指采用自動(dòng)評分方法給出的分?jǐn)?shù);M0是指該題的滿分分值。

實(shí)驗(yàn)在Visual Studio 2013環(huán)境下進(jìn)行,每道題目提供1份模板程序和3個(gè)測試用例。

2.1 評分準(zhǔn)確率分析

我們對學(xué)生答卷中的題目分別用3種方法進(jìn)行評分測試:①動(dòng)態(tài)測試,采用1.3節(jié)所述的直接匹配用例運(yùn)行結(jié)果的方法;②傳統(tǒng)靜態(tài)測試,僅依據(jù)對程序中間表示形式抽取的各項(xiàng)特征的相似度分析結(jié)果;③本文提出的MFA方法,按照式(7)分別計(jì)算3種方法的評分準(zhǔn)確率,圖2給出了10道題目3種方法評分準(zhǔn)確率的對比。

(a)10道題目的平均評分準(zhǔn)確率比較

(b)平均評分準(zhǔn)確率比較圖2 3種方法評分準(zhǔn)確率比較

由圖2可以看出,MFA方法的平均評分準(zhǔn)確率達(dá)94.48%,較動(dòng)態(tài)測試方法和傳統(tǒng)靜態(tài)分析方法分別提高了18.48%和14.17%。

雖然MFA方法的最高評分準(zhǔn)確率可以達(dá)到98.58%,但從圖2也可以看出,第3題和第5題的評分準(zhǔn)確率未能達(dá)到90%(分別為86.16%和88.86%)。主要原因是:①在用例運(yùn)行結(jié)果全部錯(cuò)誤、AST各項(xiàng)特征相似性在50%以上時(shí),MFA方法的評分會(huì)高于人工評分(如第3題);②MFA方法采用了平均權(quán)重設(shè)計(jì),各項(xiàng)特征的權(quán)重相同,而人工評分會(huì)針對具體題目人為提高某項(xiàng)特征的權(quán)重,如在第5題中部分學(xué)生程序的類特征相似度在50%左右,但其他特征相似度在20%以下,教師對該題更關(guān)注類知識(shí)點(diǎn),由此導(dǎo)致人工評分高于MFA評分。圖2中,第6和第10題的動(dòng)態(tài)評分準(zhǔn)確率較低,是因?yàn)橛?0%的學(xué)生程序的測試用例僅部分通過或全部不通過,這說明了僅使用動(dòng)態(tài)測試方法會(huì)有很大局限性。第4題的傳統(tǒng)靜態(tài)方法評分效果明顯低于其他兩種方法,是因?yàn)橥坏谰幊填}目可能會(huì)存在不同的解答,例如,學(xué)生程序中定義的變量類型、使用的表達(dá)式等可能和標(biāo)準(zhǔn)模板程序不完全一致,雖然并不影響輸出結(jié)果的正確性,但卻會(huì)影響AST特征相似度的計(jì)算結(jié)果,使得僅依賴中間形式進(jìn)行評分的效果不佳。

2.2 編譯失敗時(shí)的評分準(zhǔn)確率分析

(a)10道題目的平均評分準(zhǔn)確率比較

(b)平均評分準(zhǔn)確率比較圖3 編譯失敗時(shí)的3種方法評分準(zhǔn)確率比較

專門針對學(xué)生程序編譯失敗情況下MFA方法的評分準(zhǔn)確率進(jìn)行了分析,結(jié)果如圖3所示。可以看出,此時(shí)MFA方法的平均準(zhǔn)確率達(dá)92.15%以上,明顯高于動(dòng)態(tài)測試方法67.62%和僅基于AST的傳統(tǒng)靜態(tài)評分方法76.80%的平均準(zhǔn)確率。但是第1題和第2題使用MFA方法評分的準(zhǔn)確率低于動(dòng)態(tài)測試的準(zhǔn)確率,導(dǎo)致這一點(diǎn)的主要原因是學(xué)生程序的多個(gè)特征與標(biāo)準(zhǔn)模板程序具有20%以上的相似度,尤其變量相似度高達(dá)90%,但程序不符合編程思想且有較多錯(cuò)誤語句(例如cin?”N”;),人工評分幾乎為0分。MFA方法因考慮了源程序代碼相似度和AST各項(xiàng)特征的相似度,沒有給出0分的評價(jià),而動(dòng)態(tài)測試方法在程序編譯失敗時(shí)評分為0分,因此其結(jié)果表現(xiàn)得更接近人工評分。另外,在圖3a中MFA方法的準(zhǔn)確率均高于傳統(tǒng)靜態(tài)評分方法的準(zhǔn)確率,這也說明MFA方法在編譯失敗時(shí)考慮源程序代碼相似度的做法是比較合理的。

3 結(jié) 論

隨著MOOC在全球的興起,對編程題的在線自動(dòng)評判方法及其準(zhǔn)確率的研究成為了新的熱點(diǎn)。與現(xiàn)有研究相比,本文提出的MFA方法分別考慮了編譯成功和編譯失敗兩種不同情況。對編譯成功且運(yùn)行結(jié)果全部正確的程序引入規(guī)模特征相似度計(jì)算,防止了因直接輸出結(jié)果對評分準(zhǔn)確率產(chǎn)生的影響。對編譯成功但運(yùn)行結(jié)果不正確的程序,借助了AST特征相似度分析;在編譯失敗時(shí),綜合考慮了AST特征相似度和源程序代碼相似度,有效防止了編譯失敗情況下AST文本與程序?qū)嶋H語義存在較大差異,甚至無法生成AST的情況。實(shí)驗(yàn)結(jié)果表明,相對于僅依靠動(dòng)態(tài)測試或傳統(tǒng)靜態(tài)分析的評分方法,本文方法表現(xiàn)出更好的健壯性。

雖然實(shí)際測試結(jié)果已表明本文方法總體上優(yōu)于僅依靠動(dòng)態(tài)測試或傳統(tǒng)靜態(tài)分析的評分方法,但受各種因素限制,還無法做到對其他各類程序語言所編程序代碼的準(zhǔn)確評判。另外,由于靜態(tài)分析依賴于標(biāo)準(zhǔn)模板程序,若能通過系統(tǒng)篩選將人工評分為滿分但程序等價(jià)性分析相似度較低的學(xué)生程序自動(dòng)添加到標(biāo)準(zhǔn)程序庫,將會(huì)進(jìn)一步提高評分的準(zhǔn)確性。

[1] STAUBITZ T, KLEMENT H, RENZ J, et al. Towards practical programming exercises and automated assessment in massive open online courses [C]∥Proceedings of the 2015 IEEE International Conference on Teaching, Assessment, and Learning for Engineering. Piscataway, NJ, USA: IEEE, 2015: 23-30.

[2] ALBER S, DEBIASI L. Automated assessment in massive open online courses [EB/OL]. (2013-07-16) [2015-12-12]. http:∥uni-salzburg.at/fileadmin/multimedia/SRC/docs/teaching/SS13/SaI/Paper_Alber_Debiasi.pdf.

[3] PIETERSE V. Automated assessment of programming assignments [C]∥Proceedings of the 3rd Computer Science Education Research Conference on Computer Science Education Research. New York, USA: ACM, 2013: 45-56.

[4] ALA M, KIRSTI M. A survey of automated assessment approaches for programming assignments [J]. Computer Science Education, 2005, 15(2): 83-102.

[5] POZENEL M, FURST L, MAHNICC V. Introduction of the automated assessment of homework assignments in a university-level programming course [C]∥Proceedings of the 2015 38th International Convention on Information and Communication Technology, Electronics and Microelectronics. Piscataway, NJ, USA: IEEE, 2015: 761-766.

[6] RUBIO M, KINNUNEN P, PAREJA C, et al. Student perception and usage of an automated programming assessment tool [J]. Computers in Human Behavior, 2014, 31(2): 453-460.

[7] GUPTA S, DUBEY S K. Automatic assessment of programming assignment [J]. Computer Science & Engineering, 2012, 2(1): 67-74.

[8] VUJOSEVIC M, NIKOLIC M, TOSIC D, et al. Software verification and graph similarity for automated evaluation of students’ assignments [J]. Information & Software Technology, 2013, 55(6): 1004-1016.

[9] 馬培軍, 王甜甜, 蘇小紅. 基于程序理解的編程題自動(dòng)評分方法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2009, 46(7): 1136-1142. MA Peijun, WANG Tiantian, SU Xiaohong. Automatic grading of student programs based on program understanding [J]. Journal of Computer Research and

Development, 2009, 46(7): 1136-1142.

[10]王倩, 蘇小紅, 馬培軍. 有語法錯(cuò)誤的編程題自動(dòng)評分方法研究: 用局部語法分析和采分點(diǎn)匹配實(shí)現(xiàn) [J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(17): 239-242. WANG Qian, SU Xiaohong, MA Peijun. Automatic grading method for programs with syntax error: via local syntax analysis and key point matching [J]. Computer Engineering and Applications, 2010, 46(17): 239-242.

[11]CUI B, LI J, GUO T, et al. Code comparison system based on abstract syntax tree [C]∥Proceedings of the 2010 3rd IEEE International Conference on Broadband Network and Multimedia Technology. Piscataway, NJ, USA: IEEE, 2010: 668-673.

[12]張宇, 劉雨東, 計(jì)釗. 向量相似度測度方法 [J]. 聲學(xué)技術(shù), 2009, 28(4): 532-536. ZHANG Yu, LIU Yudong, JI Zhao. Vector similarity measurement method [J]. Technical Acoustics, 2009, 28(4): 532-536.

[本刊相關(guān)文獻(xiàn)鏈接]

李揚(yáng),潘泉,楊濤.基于短文本情感分析的敏感信息識(shí)別.2016,50(9):80-84.[doi:10.7652/xjtuxb201609013]

楊迎輝,李建華,沈迪,等.多重邊融合復(fù)雜網(wǎng)絡(luò)動(dòng)態(tài)演化模型.2016,50(9):132-139.[doi:10.7652/xjtuxb201609021]

戴啟華,劉勤讓,沈劍良,等.采用集簇方法的片上網(wǎng)絡(luò)動(dòng)態(tài)映射算法.2016,50(8):52-58.[doi:10.7652/xjtuxb201608 009]

魏倩,蔡遠(yuǎn)利.一種基于神經(jīng)網(wǎng)絡(luò)的中制導(dǎo)改進(jìn)算法.2016,50(7):125-130.[doi:10.7652/xjtuxb201607019]

張小棟,郭晉,李睿,等.表情驅(qū)動(dòng)下腦電信號的建模仿真及分類識(shí)別.2016,50(6):1-8.[doi:10.7652/xjtuxb201606001]

姜濤,黃偉,王安麟.多路閥閥芯節(jié)流槽拓?fù)浣Y(jié)構(gòu)組合的神經(jīng)網(wǎng)絡(luò)模型.2016,50(6):36-41.[doi:10.7652/xjtuxb201606 006]

宋青松,田正鑫,孫文磊,等.用于孤立數(shù)字語音識(shí)別的一種組合降維方法.2016,50(6):42-46.[doi:10.7652/xjtuxb 201606007]

陳江城,張小棟.人體下肢行走關(guān)節(jié)連續(xù)運(yùn)動(dòng)表面肌電解碼方法.2016,50(6):61-67.[doi:10.7652/xjtuxb201606010]

劉兆麗,秦濤,管曉宏,等.采用用戶名相似度傳播模型的線上用戶身份屬性關(guān)聯(lián)方法.2016,50(4):1-6.[doi:10.7652/xjtuxb201604001]

(編輯 武紅江 苗凌)

An Automatic Scoring Method of Student Programs Using Multi-Feature Analysis for Massive Open Online Courses

LIU Yuexia,NIU Zhiyao,WU Ning

(School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

A new automatic scoring method based on multi-feature analysis is proposed to focus the problem that there are a great number of C/C++ programming learners on massive open online courses environment, while the existing automatic scoring techniques possess low accuracy. The prompt information in a submitted program is eliminated with a preprocessing compiler. The lexical analysis and abstract syntax tree (AST) methods are used to extract the features of the submitted program and the standard template one, respectively. Then similarities of these features are calculated. According to whether or not the program is compiled successfully, two different strategies are applied to comprehensively analyze the multi-feature similarities and the program is automatically evaluated finally. The multi-feature similarities include the running result similarity of test cases, the AST feature similarity, and the source code similarity. If the program fails to be compiled, both the source code similarity and the AST features similarity need to be analyzed. Experimental results and comparisons with the dynamic test method and the static analysis method show that the average accuracy of the proposed method increases by 18.38 % and 14.17 %, respectively. The automatically generated scores are highly correlated with manually determined scores and there is no manual assistant to ensure the accuracy of the scoring results. The proposed method can be applied in massive open online courses.

massive open online courses; automatic evaluation; multi-feature analysis; abstract syntax tree; similarity computation

2016-05-19。

劉月霞(1991—),女,碩士生;吳寧(通信作者),女,教授。

陜西省科技研究發(fā)展計(jì)劃資助項(xiàng)目(2013K06-05)。

時(shí)間:2016-09-02

http:∥www.cnki.net/kcms/detail/61.1069.T.20160902.1630.004.html

10.7652/xjtuxb201610010

TP311

A

0253-987X(2016)10-0064-07