面向大規模在線開放課程的編程題多特征綜合自動評分方法

劉月霞,牛志堯,吳寧

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

?

面向大規模在線開放課程的編程題多特征綜合自動評分方法

劉月霞,牛志堯,吳寧

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

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

大規模在線開放課程;自動評閱;多特征分析;抽象語法樹;相似度計算

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

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

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

針對上述存在的問題,本文通過對人工評閱的思維過程進行分析,對C/C++編程題自動評分中的難點問題進行深入研究,融合動態測試與靜態分析方法的優點,提出了一種用于支撐MOOC教學的編程題多特征綜合分析自動評分方法。

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

1.1 多特征綜合評分模型

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

基于人工評閱思想的自動評分技術中,通過輸入測試用例、判斷運行結果的方法稱為動態測試;通過觀察程序編程思想、知識點、程序規模等特征的方法屬于靜態分析。人工評閱模式下的靜態分析依據人的判斷,而自動評分系統中的靜態分析則需要借助程序的中間表示形式或源程序代碼。

作為程序的一種中間表示形式,抽象語法樹(abstract syntax tree,AST)是源程序代碼的抽象語法結構的樹狀表現形式,樹上的每個節點都表示源代碼中的一種結構。之所以稱為“抽象”,是因為這里的語法并不表示出真實語法中出現的每個細節,而只反映其特征。通過將學生程序和標準模板程序轉換為以AST表示的中間形式,從中抽取各種特征并對比特征相似度,就可以確定學生程序的正確程度。

由于編譯失敗時生成的AST文本與程序實際語義存在較大不一致性,甚至無法生成AST,所以在此情況下,僅依賴于對AST所抽取特征的分析會影響評分精度。為此,需進一步分析程序源代碼,計算學生程序與標準模板程序的代碼相似度,結合對AST所抽取特征的分析結果進行綜合評分。

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

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

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

1.2 代碼預處理

目前的程序設計類課程教學基本上僅涉及控制臺程序,因此學生程序會涉及大量的控制臺輸入輸出語句。部分提示性語句、暫停性語句等會對程序的自動運行產生影響。對于初學者,學生程序中可能會缺乏提示性語句或輸出的提示性語句與標準模板程序輸出的提示性語句在空格、字符內容、大小寫等方面存在一定的不一致。另外,學生程序中若存在暫停性語句會導致其無法自動結束。這些因素都會影響動態測試的評分準確性。

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

1.3 用例運行結果相似度計算

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

表1 學生程序常見運行結果類型

根據學生程序運行結果類型,匹配用例運行結果相似度的算法如下。

輸入 學生程序的用例運行結果,標準模板程序的用例運行結果。

輸出 用例運行結果相似度。

步驟1 設置i=1,n,s=0,其中n為用例運行結果的組數;i為當前用例運行結果的組數編號,i=1,2,…,n;s為從第1組到第i組的用例運行結果相似度之和。

步驟2 判斷i是否小于等于n,如果是,判斷學生程序的第i組用例運行結果的類型;否則,轉到步驟10。

步驟3 若結果是整型數,直接匹配運行結果,如果相等,則相似度為1,否則為0。

步驟4 若結果是浮點數,設定誤差ε=0.000 01,匹配學生程序和標準模板程序運行結果,如果誤差≤ε,則相似度為1,否則為0。

步驟5 若結果是數值序列,則依次匹配每個數值。對整型數組,僅當所有數值都依序完全匹配時,相似度為1,否則為0;對于浮點型數組,則依照步驟4所述方法,計算每對數值的匹配度。

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

步驟7 若結果是字符串、字符串序列、混合序列等,先剔除不相關元素,例如空格、標點符等,然后進行字符匹配。

步驟8 若結果是算術表達式,將其轉換為逆波蘭表達式,再進行字符匹配。

步驟9 計算前i組用例運行結果相似度之和s,設置i=i+1,轉到步驟2。

步驟10 計算n組用例運行結果的平均相似度值,即s/n。

步驟11 結束。

1.4 源程序代碼相似度分析

利用有限自動機對預處理后的源程序進行詞法分析,可以生成屬性字序列。單詞的屬性,例如分界符、標識符、運算符、關鍵字等是單詞的特征。屬性字是單詞及其特性的二元組,可表示為<關鍵字,’if’>、<運算符,’+’>、<分界符,’;’>、<標識符,’book’>等。例如C程序代碼:while(i>=j)i--;經詞法分析后,可生成屬性字序列<關鍵字,’while’><分界符,’(’><標識符,’i’><運算符,’>=’><標識符,’j’><分界符,’)’><標識符,’i’><運算符,’-’><運算符,’-’><分界符,’;’>。可以看出,屬性字序列反映了程序實現的過程順序和包含的單詞及其特性。通過計算兩段程序屬性字序列的相似度,就可判斷兩段程序的相似程度。

最長公共子序列(longest common subsequence, LCS)是將兩個或多個給定字符串分別刪除任意多個字符后得到的順序不變且長度最長的相同字符序列。LCS越長,序列越相似。因此,通過計算學生程序和標準模板程序的屬性字序列的最長公共子序列,根據最長公共屬性字子序列的長度以及學生程序和標準模板程序的屬性字序列長度,就可以計算出屬性字序列的相似度,也就是兩段程序的相似度。基于動態規劃LCS算法的源程序代碼相似度S1的計算方法為

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

(1)

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

1.5 AST特征相似度分析

定義從AST中提取的能夠反映學生程序和標準模板程序相似性的各項特征如下。

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

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

定義3 類特征。可以最大程度衡量類的語義結構的特征向量,包括變量、調用、繼承、多態、方法個數等信息。

定義4 表達式特征。程序中運算符種類和個數所組成的序列。

定義5 結構特征。程序控制結構序列?？刂平Y構包括循環、選擇和順序結構。為便于處理,用關鍵字Loop統一標識循環結構(while,do-while,for),用Branch統一標識分支結構(if-else,switch),用每個關鍵字后邊緊跟的數字表示關鍵字的嵌套深度。

如果將特征視為一個文檔,將特征分量視為文檔中的詞項,那么計算學生程序和標準模板程序某項特征的相似度就相當于計算兩個文檔之間的相似度。因此,可以利用向量空間模型來計算AST特征的相似度。

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

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

(2)

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

(3)

式中:Si表示AST特征中特征i的相似度;Vi表示學生程度和標準模板程序中特征i的集合;d1i和d2i分別表示特征分量v在學生程序和標準模板程序中出現的頻數。

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

1.6 綜合評分策略

綜合各項特征的相似度分析結果,設計如下綜合評分模型

(4)

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

根據學生程序是否編譯通過,設計綜合評分策略如下。

(1)學生程序編譯通過。①如果全部測試用例運行結果正確且規模相似度達到設定閾值,輸出學生程序為滿分;②若部分測試用例運行正確,依據式(4)進行評分,此時結果特征和AST各項特征的權重均為1/6;③對全部測試用例運行結果正確但規模相似度小于設定閾值、全部測試用例運行均不正確、編譯成功但不可運行等3種情況,依據人工評分原則需扣除一定的錯誤分,修改評分模型為

%

(5)

由于此時運行結果對評分已經沒有意義,故設置用例運行結果特征的權重時將AST各項特征的權重值調整為1/5。

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

%

(6)

此時源程序代碼相似度和AST各項特征的權重值均為1/6;②如果AST生成失敗,即無法獲取AST特征,說明學生程序存在較為嚴重的語法錯誤,依據人工經驗取源程序代碼相似度和0.1之間的較小值進行評分。

2 實驗結果與分析

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

%

(7)

式中:P是評分準確率;n是考生答卷份數;M1是教師嚴格按照評分準則給出的分數;M2是指采用自動評分方法給出的分數;M0是指該題的滿分分值。

實驗在Visual Studio 2013環境下進行,每道題目提供1份模板程序和3個測試用例。

2.1 評分準確率分析

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

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

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

由圖2可以看出,MFA方法的平均評分準確率達94.48%,較動態測試方法和傳統靜態分析方法分別提高了18.48%和14.17%。

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

2.2 編譯失敗時的評分準確率分析

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

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

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

3 結 論

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

雖然實際測試結果已表明本文方法總體上優于僅依靠動態測試或傳統靜態分析的評分方法,但受各種因素限制,還無法做到對其他各類程序語言所編程序代碼的準確評判。另外,由于靜態分析依賴于標準模板程序,若能通過系統篩選將人工評分為滿分但程序等價性分析相似度較低的學生程序自動添加到標準程序庫,將會進一步提高評分的準確性。

[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] 馬培軍, 王甜甜, 蘇小紅. 基于程序理解的編程題自動評分方法 [J]. 計算機研究與發展, 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]王倩, 蘇小紅, 馬培軍. 有語法錯誤的編程題自動評分方法研究: 用局部語法分析和采分點匹配實現 [J]. 計算機工程與應用, 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]. 聲學技術, 2009, 28(4): 532-536. ZHANG Yu, LIU Yudong, JI Zhao. Vector similarity measurement method [J]. Technical Acoustics, 2009, 28(4): 532-536.

[本刊相關文獻鏈接]

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

楊迎輝,李建華,沈迪,等.多重邊融合復雜網絡動態演化模型.2016,50(9):132-139.[doi:10.7652/xjtuxb201609021]

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

魏倩,蔡遠利.一種基于神經網絡的中制導改進算法.2016,50(7):125-130.[doi:10.7652/xjtuxb201607019]

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

姜濤,黃偉,王安麟.多路閥閥芯節流槽拓撲結構組合的神經網絡模型.2016,50(6):36-41.[doi:10.7652/xjtuxb201606 006]

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

陳江城,張小棟.人體下肢行走關節連續運動表面肌電解碼方法.2016,50(6):61-67.[doi:10.7652/xjtuxb201606010]

劉兆麗,秦濤,管曉宏,等.采用用戶名相似度傳播模型的線上用戶身份屬性關聯方法.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—),女,碩士生;吳寧(通信作者),女,教授。

陜西省科技研究發展計劃資助項目(2013K06-05)。

時間: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