基于FC-KNN的C语言程序自动评分算法

李亭葳 刘 新 白王梓松 李梦磊

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

0 引 言

C语言是全国高等院校计算机专业和非计算机理工科专业的必修课，C语言程序题自动评分因此成为一个广泛应用的场景。现有的程序题自动评分方法可分为以下两类：

动态评分方法[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的程序自动评分算法

程序分类是指在给定评分等级体系下，根据程序流程控制结构自动确定程序分数类别的过程。自动评分的原理其实就是人工评分的模拟。现实中教师的评分方法通常如下：编程题的评分重点主要是考察考生对程序结构关系的掌握，比如冒泡排序，看两个循环结构的嵌套使用；再比如折半查找，主要考察考生对待查找空间的迭代管理。另外一辅助打分因素就是与别的已给分的程序(通常称为标杆)进行对比，综合本题的整体完成质量，给其一个合适的评分。

基于机器学习的程序自动评分技术以手工评判的诸多份程序的评分结果为基础，统计分析获得规律后作为机器学习的训练集，对待评分程序做分析，从而达到评估学生编程能力的目的。基本流程如下：首先把人工已经评分的程序，进行预处理、规范化、特征提取，比如将函数调用、赋值语句以及顺序关系等因素变成一个个流程控元；再给程序里的每一个流程控制元分成的小的元素加上标签与权值，以便计算机能够识别计算；最后利用某种分类算法进行分类。程序自动评分流程示意图如图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语言程序自动评分提供了新思路。

本文的算法存在的主要不足是：对于从来未评过分的新程序题，无法使用本文的算法自动评分，此问题还需要进一步的研究。可以将基于流程控制图作为中间形式，结合传统计算模板匹配相似度方法，算出新程序题的初始分值。待该题的已评分训练样本达到相应数量，再开始采用本文的FC-KNN自动评分算法，并在训练样本积累过程中，对前者与后者设定相应的分数权值分配。随着训练样本的递增，前者权值递减，后者权值呈递增趋势。待该题训练样本足够多(至少达到实验中的训练集数量)，再完全采用本文算法自动评分，这也是作者继续下一步研究的方向。