基于FC-KNN的C語言程序自動評分算法

李亭葳 劉 新 白王梓松 李夢磊

(湘潭大學(xué)信息工程學(xué)院 湖南 湘潭 411105)

0 引 言

C語言是全國高等院校計(jì)算機(jī)專業(yè)和非計(jì)算機(jī)理工科專業(yè)的必修課，C語言程序題自動評分因此成為一個(gè)廣泛應(yīng)用的場景?，F(xiàn)有的程序題自動評分方法可分為以下兩類：

動態(tài)評分方法[1-3]：預(yù)先備好特定的測試用例集，編譯并運(yùn)行學(xué)生提交的程序，比較其運(yùn)行結(jié)果是否符合測試集的輸出結(jié)果，并給定分?jǐn)?shù)。

靜態(tài)評分方法[4-6]：將學(xué)生的源代碼與標(biāo)準(zhǔn)模板程序轉(zhuǎn)換成中間形式，比較兩種中間形式的語義相似度，再給出源代碼的評分結(jié)果。

動態(tài)測評方法是判定程序分?jǐn)?shù)最簡單、最直接的方法，在ACM這類編程競賽中經(jīng)常采用。但在實(shí)際場景中，學(xué)生程序可能因?yàn)楹芗?xì)微的邏輯錯(cuò)誤導(dǎo)致程序運(yùn)行結(jié)果出錯(cuò)，因此得零分。非計(jì)算機(jī)專業(yè)的C語言教學(xué)和考試要求完全不同于程序競賽的要求，它所針對的學(xué)生很少像ACM參賽選手那樣經(jīng)過大量的、反復(fù)的編程訓(xùn)練，程序中出現(xiàn)細(xì)微的邏輯錯(cuò)誤是大概率事件。在這類測試中主要考察學(xué)生對程序過程結(jié)構(gòu)以及知識點(diǎn)的掌握程度，因此對程序評判的方法與ACM并不相同。由于動態(tài)評分通常只能給出滿分或者零分，這并不符合平時(shí)教師閱卷的評分規(guī)則。靜態(tài)評分方法通常是將程序轉(zhuǎn)換為系統(tǒng)圖、語法樹等中間形式[7]，再與標(biāo)準(zhǔn)答案的模板進(jìn)行比較給出評分。相對來說，靜態(tài)評分不受細(xì)微邏輯錯(cuò)誤的影響，可以給出部分分值，因此更接近教師人工閱卷的方式。但是，靜態(tài)評分算法在很大程度上依賴于模板程序的完整性[7]，而在實(shí)際應(yīng)用中很難集齊各個(gè)分?jǐn)?shù)段的完美模板，這會影響評分的準(zhǔn)確性。

隨著機(jī)器學(xué)習(xí)技術(shù)的迅速發(fā)展與普及，文本分類技術(shù)也成為機(jī)器學(xué)習(xí)中較為成熟的領(lǐng)域。C語言作為一種高級程序設(shè)計(jì)語言，以函數(shù)作為程序設(shè)計(jì)的基本單位，是一種半結(jié)構(gòu)化的特殊文本。因此，我們考慮將C語言源代碼作為一種特殊文本來處理，以流程控制元作為源程序的基本特征；選擇KNN算法進(jìn)行分類，不同的類別具有不同的分值，從而將程序評分問題轉(zhuǎn)化為分類問題。

1 KNN算法簡介

KNN算法，即K近鄰分類算法，是一種簡單、有效，且經(jīng)典成熟的有監(jiān)督學(xué)習(xí)文本分類算法。KNN算法以最鄰近者類別作為決策未知類別的依據(jù)，它的基本思想是：從訓(xùn)練樣本集選取最鄰近的K個(gè)樣本(特征空間中最鄰近)，根據(jù)這K個(gè)樣本中大多數(shù)所屬類別，從而將待測樣本也劃分到該類別[8]。KNN算法中，所選擇的有限鄰居均是已正確分類的對象，而不是依靠類別域判定類別[9]。因此，KNN適用于多分類、分類域交叉重疊多的情況。我們用此算法實(shí)現(xiàn)對C語言程序的評分。

2 基于KNN的程序自動評分算法

程序分類是指在給定評分等級體系下，根據(jù)程序流程控制結(jié)構(gòu)自動確定程序分?jǐn)?shù)類別的過程。自動評分的原理其實(shí)就是人工評分的模擬?，F(xiàn)實(shí)中教師的評分方法通常如下：編程題的評分重點(diǎn)主要是考察考生對程序結(jié)構(gòu)關(guān)系的掌握，比如冒泡排序，看兩個(gè)循環(huán)結(jié)構(gòu)的嵌套使用；再比如折半查找，主要考察考生對待查找空間的迭代管理。另外一輔助打分因素就是與別的已給分的程序(通常稱為標(biāo)桿)進(jìn)行對比，綜合本題的整體完成質(zhì)量，給其一個(gè)合適的評分。

基于機(jī)器學(xué)習(xí)的程序自動評分技術(shù)以手工評判的諸多份程序的評分結(jié)果為基礎(chǔ)，統(tǒng)計(jì)分析獲得規(guī)律后作為機(jī)器學(xué)習(xí)的訓(xùn)練集，對待評分程序做分析，從而達(dá)到評估學(xué)生編程能力的目的?；玖鞒倘缦拢菏紫劝讶斯ひ呀?jīng)評分的程序，進(jìn)行預(yù)處理、規(guī)范化、特征提取，比如將函數(shù)調(diào)用、賦值語句以及順序關(guān)系等因素變成一個(gè)個(gè)流程控元；再給程序里的每一個(gè)流程控制元分成的小的元素加上標(biāo)簽與權(quán)值，以便計(jì)算機(jī)能夠識別計(jì)算；最后利用某種分類算法進(jìn)行分類。程序自動評分流程示意圖如圖1所示。

圖1 程序自動評分流程示意圖

2.1 程序的預(yù)處理

C語言程序編寫時(shí)表達(dá)方式非常靈活，比如讓變量i的值加1，就有“i++”、“++i”、“i+=1”、“i=i+1”等多種寫法，這給自動評分帶來了很大的困難。為了減少不必要的計(jì)算，提高后續(xù)處理的準(zhǔn)確性，在不影響源代碼語義的情況下，本文對訓(xùn)練集與測試集程序源碼先做程序規(guī)范化與流程分析。

2.1.1 程序規(guī)范化

定義1最小子語句。最小子語句是程序源碼中不可分割的最簡形式語句。如“i=j=k;”，需拆分為兩個(gè)最小子句：“j=k;i=j;”。

程序規(guī)范化的主要任務(wù)是將源程序劃分成最小子語句。主要是拆分復(fù)合語句為等價(jià)的簡單語句，包括聲明語句的拆分、復(fù)雜運(yùn)算表達(dá)式的拆分。除此之外，還需要刪除函數(shù)聲明語句；過濾掉無用的變量、注釋、頭文件、空行等；替換宏定義；統(tǒng)一while、do-while、for循環(huán)結(jié)構(gòu)為while循環(huán)結(jié)構(gòu)的表達(dá)形式；將每行處理成僅有一條語句，且大括號單獨(dú)占一行。

2.1.2 程序流程分析

從程序流程角度分析，C語言程序由順序結(jié)構(gòu)、選擇結(jié)構(gòu)(分支結(jié)構(gòu))、循環(huán)結(jié)構(gòu)這三大基本結(jié)構(gòu)語句組成[2]。本文將這三大基本結(jié)構(gòu)進(jìn)一步細(xì)分為程序中常用的11種流程結(jié)構(gòu)語句：常規(guī)賦值、系統(tǒng)函數(shù)調(diào)用賦值、自定義函數(shù)賦值、庫函數(shù)調(diào)用、自定義函數(shù)調(diào)用、函數(shù)跳轉(zhuǎn)、定長循環(huán)、變長循環(huán)、輔助控制語句、條件語句，k(k≥2)路分支語句。分析與標(biāo)記程序的每個(gè)最小子句所屬的流程結(jié)構(gòu)類型，并封裝成一個(gè)流程控制節(jié)點(diǎn)。流程控制節(jié)點(diǎn)類型表如表1所示。

表1 流程控制節(jié)點(diǎn)類型表

續(xù)表1

流程控制節(jié)點(diǎn)類型劃分細(xì)節(jié)說明：

1) 庫函數(shù)調(diào)用：由于函數(shù)調(diào)用的類別諸多，在此我們根據(jù)C語言中最常用的標(biāo)準(zhǔn)頭文件所聲明的函數(shù)，建立了標(biāo)準(zhǔn)庫函數(shù)表。其中標(biāo)準(zhǔn)頭文件包括：stdio.h、stdlib.h、math.h、string.h、time.h、alloc.h、asset.h、errno.h、float.h、limits.h等。

2) 定長循環(huán)與變長循環(huán)：本文根據(jù)循環(huán)結(jié)構(gòu)中循環(huán)體對循環(huán)判斷條件變量的改變與否，將循環(huán)分為變長循環(huán)與定長循環(huán)。若循環(huán)判斷條件在執(zhí)行循環(huán)體的過程中被改變，則稱為變長循環(huán)，如：while(i++

3)k路分支:if分支結(jié)構(gòu)中根據(jù)分支的數(shù)量來決定k的值。switch分支結(jié)構(gòu)中則是根據(jù)case和default的數(shù)量決定分支k。

4) 考慮到變量申明后，還有后續(xù)賦值等操作，為了降低后續(xù)處理特征維度，因此不將僅有變量申明的語句(如 int n;)單獨(dú)劃分為一個(gè)流程控制節(jié)點(diǎn)類型。

在確定每個(gè)最小子句的流程控制節(jié)點(diǎn)類型后，根據(jù)各節(jié)點(diǎn)的控制依賴和數(shù)據(jù)依賴關(guān)系，添加相應(yīng)的邊表示各個(gè)節(jié)點(diǎn)之間的依賴關(guān)系。本文定義了6種常用的邊依賴關(guān)系，如表2所示。

表2 流程控制節(jié)點(diǎn)邊關(guān)系

續(xù)表2

2.1.3 控制流程結(jié)構(gòu)圖

定義2有流程控制元。流程控制元是流程控制結(jié)構(gòu)圖中，兩個(gè)流程控制節(jié)點(diǎn)及關(guān)系弧組成的有序三元組e=(vp,rk,vq)，其中vp∈V，vq∈V，rk表示vp到vq的關(guān)系弧，rk=∈E。

在上述的預(yù)處理操作的基礎(chǔ)上，可以構(gòu)畫出源程序的流程控制結(jié)構(gòu)關(guān)系圖。因C語言程序以函數(shù)為基本單位，主函數(shù)與自定義函數(shù)是調(diào)用關(guān)系。在構(gòu)畫程序流程控制結(jié)構(gòu)圖時(shí)，本文以函數(shù)為基本單位將程序分為若干個(gè)流程控制結(jié)構(gòu)圖。掃描預(yù)處理后的源程序，得到流程控制圖G=，V是流程控制節(jié)點(diǎn)集合，E是流程控制節(jié)點(diǎn)關(guān)系邊集合。進(jìn)一步將G劃分成若干個(gè)流程控制元e，即完成了程序的特征提取工作。以求階乘為例，預(yù)處理后的源代碼如下，流程控制結(jié)構(gòu)圖如圖2所示。

① int main()

{

int n;

② int i=2;

③ int fac=1;

④ printf(″請輸入一個(gè)大于0的整數(shù):″);

⑤ scanf(″%d″,&n);

⑥ if(n==0‖n==1)

⑦ fac=1;

⑧ else

⑨ while(i<=n)

{

⑩ fac=fac*i;

}

圖2 階乘流程控制結(jié)構(gòu)圖

2.2 程序的表示模型

對C語言程序評分之前，我們需要將程序源碼轉(zhuǎn)換成計(jì)算機(jī)能夠處理的一種理想的結(jié)構(gòu)化形式[11]。文本分類最廣泛使用的是向量空間模型VSM(Vector Space Model)[12],在此我們的程序也采用該模型表示。在向量空間模型中，特征項(xiàng)是不可分的基本單位[13]，本文中是流程控制元。每一個(gè)程序P可以視作由n個(gè)流程控制元組成的集合：P={e1,e2,…,en}。每個(gè)流程控制元ei按照權(quán)值分配表賦予相應(yīng)的權(quán)重wi，則一個(gè)程序P可以表示為P=P(e1:w1,e2:w2,…,en:wn)，即n維空間向量。程序的向量空間模型如圖3所示。

圖3 程序向量空間模型

2.3 KNN自動評分

程序向量化表示后，就能用KNN算法處理程序，實(shí)現(xiàn)程序分類(評分)。算法具體步驟如下：

1) 給定由a個(gè)已評分程序組成訓(xùn)練集，b個(gè)待評分程序組成的測試集。

2) 使用向量夾角余弦公式計(jì)算待評分程序和訓(xùn)練集樣本程序之間的距離(相似度)，計(jì)算公式如下：

(1)

式中：xi表示測試程序集待測的第i個(gè)程序向量，tj表示訓(xùn)練程序集的第j個(gè)程序，k為通過多次試驗(yàn)得出的最佳近鄰數(shù)。

3) 選擇與xi最近鄰的k個(gè)程序樣本，根據(jù)xi的k個(gè)最近鄰依次計(jì)算程序類別CA、CB、CC、CD、CE相應(yīng)的權(quán)重，計(jì)算公式如下：

(2)

式中：Sim(xi,tj)為xi與k個(gè)近鄰程序中tj的距離，判別函數(shù)如下：

(3)

4) 比較各類別評分等級的權(quán)重，將待評分程序xi歸入權(quán)重最大的類別。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

一直以來，應(yīng)用于程序自動評分研究的公開數(shù)據(jù)集較為匱乏。研究者多采用ACM平臺的數(shù)據(jù)集，但ACM題庫難度與平時(shí)作業(yè)考試有很大不同。因此，本文選用我們自行開發(fā)的系統(tǒng)“典課云教育平臺”中的“程序設(shè)計(jì)作業(yè)”系統(tǒng)，累積了近5年的C語言程序設(shè)計(jì)作業(yè)題。教師已將程序題評閱為A、B、C、D、E五個(gè)成績等級,表3為評分等級對應(yīng)分值表。選取5道C語言程序題作為實(shí)驗(yàn)數(shù)據(jù)源，每道題約500份作為訓(xùn)練集，約100份作為測試集。每道題訓(xùn)練集評分等級分布如表4所示。

表3 評分等級對應(yīng)分值

表4 訓(xùn)練集評分等級分布

續(xù)表4

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

實(shí)驗(yàn)中，統(tǒng)計(jì)各評分等級的平均正確率AP(Average Precision)。文獻(xiàn)[14]認(rèn)為最佳k值取20，文獻(xiàn)[15]驗(yàn)證k值取30能取得較好的分類效果。為了驗(yàn)證適合本程序庫的最佳k值，本文k值依次選取15～35分別做了對比試驗(yàn)。通過反復(fù)試驗(yàn)，發(fā)現(xiàn)最終k值取24，能取得最高的正確率。k=24所得實(shí)驗(yàn)結(jié)果如表5所示。

表5 FC-KNN實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)數(shù)據(jù)中，題2與題4正確率相對較低，分析發(fā)現(xiàn)因其程序結(jié)構(gòu)較其他略顯復(fù)雜，系統(tǒng)中收集的訓(xùn)練集數(shù)量相對較少。從整體來看，A等級與B等級評分效果更好，因其訓(xùn)練樣本集相對更豐富。由此可見，如果訓(xùn)練樣本集進(jìn)一步擴(kuò)充，本算法的正確性還需進(jìn)一步提升。

為了進(jìn)一步驗(yàn)證本文FC-KNN算法的性能，本文還將FC-KNN與其他計(jì)算程序相似度自動評分算法做了對比試驗(yàn)，如表6所示。其中FC是基于本文前期流程控制元提取，直接計(jì)算與模板程序流程控制元匹配的相似度。

表6 自動評分算法實(shí)驗(yàn)結(jié)果對比

實(shí)驗(yàn)結(jié)果表明，本文提出的FC-KNN算法具有較好的評分效果。

4 結(jié) 語

本文采用基于程序流程控制圖的方法，將程序轉(zhuǎn)換為空間向量流程控制元集合的表示，并以流程控制元作為程序的特征項(xiàng)，結(jié)合機(jī)器學(xué)習(xí)中的KNN算法，對C語言程序進(jìn)行評分。該特征提取方法更符合C語言程序設(shè)計(jì)特點(diǎn)，也與教師評閱程序習(xí)慣更貼切。實(shí)驗(yàn)證明，基于流程控制元與KNN結(jié)合的程序自動評分算法，與傳統(tǒng)的自動評分算法相比，具有更高的評分準(zhǔn)確率。采用這種方法，不僅能減少傳統(tǒng)自動評分方法單純地與答案模板程序?qū)Ρ扔?jì)算的片面性，還避免了KNN算法在特征項(xiàng)提取后面臨的高維度問題，為解決C語言程序自動評分提供了新思路。

本文的算法存在的主要不足是：對于從來未評過分的新程序題，無法使用本文的算法自動評分，此問題還需要進(jìn)一步的研究?？梢詫⒒诹鞒炭刂茍D作為中間形式，結(jié)合傳統(tǒng)計(jì)算模板匹配相似度方法，算出新程序題的初始分值。待該題的已評分訓(xùn)練樣本達(dá)到相應(yīng)數(shù)量，再開始采用本文的FC-KNN自動評分算法，并在訓(xùn)練樣本積累過程中，對前者與后者設(shè)定相應(yīng)的分?jǐn)?shù)權(quán)值分配。隨著訓(xùn)練樣本的遞增，前者權(quán)值遞減，后者權(quán)值呈遞增趨勢。待該題訓(xùn)練樣本足夠多(至少達(dá)到實(shí)驗(yàn)中的訓(xùn)練集數(shù)量)，再完全采用本文算法自動評分，這也是作者繼續(xù)下一步研究的方向。