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

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

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

0 引 言

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

動態評分方法[1-3]：預先備好特定的測試用例集，編譯并運行學生提交的程序，比較其運行結果是否符合測試集的輸出結果，并給定分數。

靜態評分方法[4-6]：將學生的源代碼與標準模板程序轉換成中間形式，比較兩種中間形式的語義相似度，再給出源代碼的評分結果。

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

隨著機器學習技術的迅速發展與普及，文本分類技術也成為機器學習中較為成熟的領域。C語言作為一種高級程序設計語言，以函數作為程序設計的基本單位，是一種半結構化的特殊文本。因此，我們考慮將C語言源代碼作為一種特殊文本來處理，以流程控制元作為源程序的基本特征；選擇KNN算法進行分類，不同的類別具有不同的分值，從而將程序評分問題轉化為分類問題。

1 KNN算法簡介

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

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

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

基于機器學習的程序自動評分技術以手工評判的諸多份程序的評分結果為基礎，統計分析獲得規律后作為機器學習的訓練集，對待評分程序做分析，從而達到評估學生編程能力的目的。基本流程如下：首先把人工已經評分的程序，進行預處理、規范化、特征提取，比如將函數調用、賦值語句以及順序關系等因素變成一個個流程控元；再給程序里的每一個流程控制元分成的小的元素加上標簽與權值，以便計算機能夠識別計算；最后利用某種分類算法進行分類。程序自動評分流程示意圖如圖1所示。

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

2.1 程序的預處理

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

2.1.1 程序規范化

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

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

2.1.2 程序流程分析

從程序流程角度分析，C語言程序由順序結構、選擇結構(分支結構)、循環結構這三大基本結構語句組成[2]。本文將這三大基本結構進一步細分為程序中常用的11種流程結構語句：常規賦值、系統函數調用賦值、自定義函數賦值、庫函數調用、自定義函數調用、函數跳轉、定長循環、變長循環、輔助控制語句、條件語句，k(k≥2)路分支語句。分析與標記程序的每個最小子句所屬的流程結構類型，并封裝成一個流程控制節點。流程控制節點類型表如表1所示。

表1 流程控制節點類型表

續表1

流程控制節點類型劃分細節說明：

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

2) 定長循環與變長循環：本文根據循環結構中循環體對循環判斷條件變量的改變與否，將循環分為變長循環與定長循環。若循環判斷條件在執行循環體的過程中被改變，則稱為變長循環，如：while(i++

3)k路分支:if分支結構中根據分支的數量來決定k的值。switch分支結構中則是根據case和default的數量決定分支k。

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

在確定每個最小子句的流程控制節點類型后，根據各節點的控制依賴和數據依賴關系，添加相應的邊表示各個節點之間的依賴關系。本文定義了6種常用的邊依賴關系，如表2所示。

表2 流程控制節點邊關系

續表2

2.1.3 控制流程結構圖

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

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

① int main()

{

int n;

② int i=2;

③ int fac=1;

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

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

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

⑦ fac=1;

⑧ else

⑨ while(i<=n)

{

⑩ fac=fac*i;

}

圖2 階乘流程控制結構圖

2.2 程序的表示模型

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

圖3 程序向量空間模型

2.3 KNN自動評分

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

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

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

(1)

式中：xi表示測試程序集待測的第i個程序向量，tj表示訓練程序集的第j個程序，k為通過多次試驗得出的最佳近鄰數。

3) 選擇與xi最近鄰的k個程序樣本，根據xi的k個最近鄰依次計算程序類別CA、CB、CC、CD、CE相應的權重，計算公式如下：

(2)

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

(3)

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

3 實驗及結果分析

3.1 實驗數據集

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

表3 評分等級對應分值

表4 訓練集評分等級分布

續表4

3.2 實驗結果分析與評價

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

表5 FC-KNN實驗結果

實驗數據中，題2與題4正確率相對較低，分析發現因其程序結構較其他略顯復雜，系統中收集的訓練集數量相對較少。從整體來看，A等級與B等級評分效果更好，因其訓練樣本集相對更豐富。由此可見，如果訓練樣本集進一步擴充，本算法的正確性還需進一步提升。

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

表6 自動評分算法實驗結果對比

實驗結果表明，本文提出的FC-KNN算法具有較好的評分效果。

4 結 語

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

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