基于PTA平台的编程能力评估算法

申晓倩，林晓霞，李环宇，徐燕妮

（山东科技大学智能装备学院，泰安 271000）

0 引言

PTA（programming test assessment）是由浙江大学主导，杭州百腾教育科技有限公司管理运营的程序设计类辅助教学平台［1］。当前，PTA平台被越来越多的高校和机构采用，截止目前，该平台注册用户近400 万，由1086 所高校共创，9100 多位优秀教师建设，近28 万道高质量题目供学习、练习。平台覆盖百余门课程，支持20万人同时在线，在平台上，教师可以创建自己的班级、创建自己的题目集、布置作业等。PTA 平台支持多种编程语言，如C、C++、Java等。它提供了丰富的题库，包括基础算法、数据结构、网络编程、操作系统等方面的题目，以及各种比赛和练习题目。学生可以通过PTA平台直接提交代码，进行在线编译、运行和评测。PTA 平台旨在提供一个高效、公平、准确的评测环境，评测结果会及时反馈给学生，帮助练习者及时发现问题、纠正错误，帮助学生提高编程能力和解决问题的能力。

数据挖掘技术是一种利用自动或半自动的手段挖掘出隐藏在海量数据中的对我们研究有用的信息的技术。数据挖掘技术包括分类、聚类、关联规则、异常检测等方法。其中，分类是将数据分成多个类别的过程，聚类是将数据分成多个相似的组的过程，关联规则是寻找数据之间的相关性，异常检测是检测与预期结果不符合的数据。

在数据挖掘技术的应用中，需要使用到各种算法和工具。这些算法可以用于关联、预测等，例如，决策树、神经网络、支持向量机等算法［2］通常用于分类和预测；K-means、DBSCAN等是常见的用于聚类的算法；可以用于关联规则挖掘的算法包括Apriori、FP-growth 等算法。同时，在进行数据挖掘的过程中，还需要熟悉经常使用到的各种数据挖掘工具，如RapidMiner、KNIME等。

本文采用数据挖掘的相关技术，借助PTA平台对高校学生的编程能力进行评估。

1 数据清洗

从PTA 平台采集完数据后，需要对采集到的学生学习记录数据进行处理，去除无效数据、异常数据，并对数据进行标准化，使得数据可以被后续的算法所使用。数据处理过程中需要注意数据的质量和准确性，以确保数据的可靠性和有效性，避免对后续的数据分析和模型构建产生干扰。

（1）处理异常数据。主要是对成绩单数据进行清洗，对缺失数据进行处理，在Navicat 中利用筛选功能处理数据，成绩单中“缺考”的学生记录直接删除，对于试题总分缺失的学生记录，用该套试题的学生得分平均值补充；练习试题通常分为选择题、判断题、函数题以及编程题，若某一类型题目得分数据缺失，不采取将该条数据删除的方法，而是用该条样本的其他题型的平均得分进行填补，本文使用均值插补法［3］，均值插补的原理是用待插补数据集的所有非缺失部分的均值替代每个缺失值，从而得到完整的数据集，避免大量数据的损失。

（2）进行数据规约［4］。主要是通过减少特征维数和数据规模的方式去掉一些不重要的信息，本文删除了用户组、姓名等与研究无关的变量，留下与编程能力相关度较高的特征作为评价指标，分别为耗时、总分、选择题得分、判断题得分、编程题得分和试题难度系数。

（3）数据标准化。是将数据进行无纲量化，使处理后的数据度量相同，将学生数据转换为统一的标准格式，以方便后续算法进行处理和分析，为了实现评估数据的集中和便于观察，对选择的数据进行归一化处理。本文用minmax 方法［5］归一化指标数据，将数据的取值范围规范到［0，1］，便于处理和计算，提高指标数据间的可比性。

2 定义和处理数据集

2.1 定义数据集

建立基础知识掌握情况集，确定基础知识掌握程度集，该程度集在面对不同的学生对象时，可以灵活掌握。本文为方便起见，将程度集分为三个等级，不掌握、半掌握和完全掌握，分别用［0，0.2］、［0.2，0.6］和［0.6，1］与这三个等级对应，具体见表1。编程实践能力评价等级分为强、较强、一般、弱、很弱五个等级，由于数据经过归一化处理后评价指标都介于［0，1］，所以评价等级也在［0，1］，规定区间［0.80，1.00］、（0.60，0.80］、（0.40，0.60］、（0.20，0.40］、（0，0.20］分别与上述评价等级一一对应［6］。规定编程实践能力评语集为V={}强,较强,一般,弱,很弱，见表2。在定义指标集之前，首先确定评价指标，根据规约后得到对学生学习状况评估有较重要影响的指标，即选择题得分、判断题得分、函数题得分、编程题得分、总分、耗时，及试题难度系数七个评价指标。以客观题得分情况来表示基础知识掌握情况，客观题有选择题和判断题，以函数题和编程题作为评估编程实践能力的评价指标。

表1 基础知识掌握程度评价等级

表2 编程实践能力评价等级

在研究规定评价指标集S={S1,S2,S3,S4,S5,S6,S7}其中S1是总分，S2是耗时，S3表示判断题得分，S4是选择题得分，S5是函数题得分，S6是编程题得分，S7是试题难度系数。规定指标权重集为Ws=[W1,W2,W3,W4,W5,W6,W7] 。定义指标权重集后，接下来就需要计算指标权重。

2.2 计算评价指标权重

指标权重的计算采用熵权法，这是根据某一指标的变异程度进行权重分配的方法。根据熵值进行指标权重计算时，如果指标的熵值较小，则表明其变异程度大，其权重也就越大。

2.2.1 求各个指标的信息熵

本文经过数据预处理后，有72个评价对象，7 个评价指标，设原始评价矩阵归一化后的评价指标矩阵其中xij表示第i个对象的第j个评价指标的值，bij是归一化后无量纲的第i个对象的第j个评级指标。根据信息熵的概念，可得公式（1）和公式（2）。

根据公式计算可得pij矩阵，局部矩阵展示如图1所示。

图1 局部矩阵示意

通过公式计算得到7个评价指标的信息熵为H1= 0.876，H2= 0.802，H3= 0.902，H4= 0.898，H5= 0.7591，H6= 0.7107，H7= 0.9034。

2.2.2 计算各个指标的权重

根据以上信息熵的公式，计算得到7个指标的信息熵值后，采用公式（3）计算可得到权重，公式（3）如下：

其中，j= 1,2,3,4,5,6,7并且

通过计算得到评估指标权重的具体值，见表3。

表3 评估指标权值

3 BP神经网络模型结构的确立

本文是通过训练BP 神经网络模型［7］来评估学生的编程能力，要确定BP 神经网络的结构，就需要确定三层的节点数。针对该系统，输入层有7 个神经元，输出层有2 个神经元，因此，确定隐含层的节点个数是明确BP 神经网络模型结构的关键，对于隐含层节点个数的计算通常采用经验公式（4）：

其中，l表示隐含层节点个数，n为输入层节点数，m为输出层节点数，α为［1，10］之间的常数。

通过公式（4）可得该隐含层节点个数取值范围为［4，14］，采用试凑法对不同数量的隐含层神经元个数进行测试，最终得到最佳隐含层神经元个数是9。即确定了该神经网络的结构为输入层节点数为7，隐含层节点数为9，输出层节点数为2，因此，确定7-9-2 型BP 神经网络。如图2所示，建立了BP神经网络模型［8］。

图2 BP神经网络结构

4 确定隐含层函数

本文采用tansig 函数和logsig 函数分别作隐含层的传输函数和输出层的转移函数，如式（5）和（6）所示：

输入层到隐含层函数如式（7）和（8）所示：

其中，xi表示输入层中第i个神经元的输入，wij表示输入层中第i个神经元和隐含层第j个神经元之间的连接权值，netj是指隐含层第j个神经元的输入，yj表示隐含层第j个神经元的输出。

隐含层到输出层函数如式（9）和（10）所示:

其中，vj表示隐含层第j个神经元与输出层神经元之间的连接权值，O1是输出层神经元的输出，net1表示输出层神经元的输入。

5 BP神经网络训练

该系统模型训练的流程［9］如下：首先，输入训练样本，本文选取了7 套题，共500 条记录，以400 条编程数据为训练样本，100 条数据作为测试样本。然后，设置网络参数，初始最大迭代次数设置为40000，目标误差为1e-004，训练样本数据进行学习，通过不断调整网络权值和阀值，使得评估模型达到一个稳定的状态，当神经网络达到目标误差或者达到最大迭代次数时训练可以结束。

在进行模型训练之前，首先要确定综合评价值，通过公式（11）计算综合评价值，将其作为期望输出。

采用绝对误差来测量神经网络输出的真实值与预期值之间的偏差，绝对误差是真实值与预期值之间差的绝对值，通过对比两者之间的绝对误差，编程实践能力测试结果和评价等级见表4。

表4 BP神经网络测试结果与误差

由表4 可知，该系统BP 神经网络的真实值与预期值的最大绝对误差为0.0072，最小值为0.0000，误差值十分接近，能够比较准确地对学生编程能力进行评估。因此，采用基于熵权的BP 神经网络模型对学生学习状况进行评估是可行的。

6 结语

本研究采用了BP 神经网络算法，神经网络结构为7-9-2 型，可以对学生的学习状况进行分类和预测，帮助教师和学生对学习状况准确评估，对教育信息化发展具有现实意义。即学生总得分、选择题得分、判断题得分、函数题得分、编程题得分被赋予权重后，可以得到准确的评估结果，这些与学习状况评估都有关系。该系统的评估结果可以为教师和学生提供有价值的参考信息。教师可以根据该评估系统准确了解学生的学习状况和问题，从而有针对性地为学生提供建设性建议，真正起到帮助学生提高学习效果和成绩的作用。当然学生也可以通过结果了解自己的编程能力，为下一步深入学习做好计划。