一种图形化编程作品的评测方法

摘要

本发明提供了一种基于图嵌入和程序复杂度的图形化编程作品的评测方法，包括针对作品的源代码文件，建立抽象语法树，并通过图嵌入得到语法树的图向量，将作品与参考作品的图向量相似度作为逻辑性特征；采用Halstead度量法计算工作量特征；采用McCabe度量法计算复杂度特征；通过静态匹配提取得到作品的关键变量与任务无关统计量；将以上特征以及老师作为特征输入下游分类器进行分类，计算得出作品的评分。本发明引入逻辑性特征，适用于答案不唯一的情况；兼顾逻辑性、工作量、复杂度、老师、关键变量和任务无关统计等多维度的特征，一定程序上解决了图形化编程中存在的创新性问题和鼓励性问题，使得评分能够准确反应学生的实际水平。

权利要求

1.一种图形化编程作品的评测方法，其特征在于，该方法包括：S1.获取图形化编程作品的特征；所述特征包括逻辑性特征、复杂度特征、关键变量特征和/或任务不相同统计量特征；

S2.对类别型特征进行处理；

S3.将非类别型特征和类别型特征的处理结果输入分类器，获取评测分数；

在所述步骤S1中，所述逻辑性特征的计算方法为：S11.获取作品的源代码；

S12.为所述源代码构造抽象语法树；

S13.对所述抽象语法树进行图嵌入获得图向量；

S14.逻辑性特征为作品的图向量与一个或多个参考作品的图向量的最大相似度；

所述复杂度特征的计算方法为：初始化复杂度为1；

遍历源代码，如果匹配到预置的操作码，则累加所述操作码对应的额外分支数；

所述任务不相同统计量特征的获取方法为：遍历作品源代码，对比作品任务要求，统计与任务要求不同的角色的数量和所述角色的代码块数量；

所述关键变量特征的获取方法为：遍历作品源代码，获取关键点处的内容；在所述步骤S2中，所述关键变量特征的处理方法为：

如果所述内容是数值型数据，无需特别处理；

若所述内容是有序的类别型数据，采取序号编码进行处理；

若所述内容是无序的类别型数据，采取独热编码进行处理。

2.根据权利要求1所述的评测方法，其特征在于，在步骤S12中，构建抽象语法树的规则为：(a)以舞台为根结点，属性为stage；(b)以角色作为舞台结点的子结点，属性为role；(c)以角色所实现的功能作为角色结点的子结点，功能表现为实现所述角色的代码块，代码块与代码块之间根据逻辑关系进行连接，属性为代码块的代码类型。

3.根据权利要求1所述的评测方法，其特征在于，所述步骤S1中，所述特征还包括工作量特征、老师偏好特征。

4.根据权利要求3所述的评测方法，其特征在于，所述工作量特征包括操作量O和时间开销T′，通过改造的Halstead方法计算。

5.根据权利要求1所述的评测方法，其特征在于，所述操作码为and、or、if、if‑else、repeat、repeat‑until、forever和stop。

6.根据权利要求3所述的评测方法，其特征在于，在所述步骤S2中，所述老师偏好的处理方法为：对批改老师进行独热编码。

7.根据权利要求1所述的评测方法，其特征在于，所述分类器为XGBoost，弱学习器采用gbtree，损失函数采用softmax。

说明书

一种图形化编程作品的评测方法

技术领域

[0001] 本发明涉及计算机技术领域，具体涉及一种图形化编程作品的评测方法。

背景技术

[0002] 面向图形化编程的项目式学习对于培养儿童的计算思维具有重要意义，图形化编程的学习旨在通过课程训练，培养和提升学生的创新思维，计算思维和编程思维，帮助他们
更好更正确地掌握科学世界的底层逻辑，从而更好地应对解决未来人生的各种问题。相比
传统的代码编程，图形化编程更加简单、易读、易上手，是适合所有少儿学员的入门平台。其
中，Scratch是一款由麻省理工学院(MIT)设计开发的一款面向少年的简易编程工具。MIT做
了相当深入研究和颇具针对性的设计开发。这个平台可以让低龄儿童编写属于自己的交互
动画、游戏、故事甚至是音乐和美术作品。Scratch学习过程中，除了编程本身的内容外，
Scratch可以将编程与学科内容以动画、游戏或者故事的形式表现出来，在加深编程理解的
同时，还能对于学校学习有明显的促进作用，这是知其然和知其所以然在的区别所在。提高
孩子的沟通力、领导力、计算思维、逻辑思维、批判性思维以及对生活的关注力和观察力。

[0003] 但是，由于以下问题，自动评测图形化编程作品的结果并不能令人满意：1、与传统的OJ系统相比，图形化编程不存在标准的输入输出。2、为了促进学生的积极性，对于与参考
答案相差较大和与任务无关的作品，老师也会尽可能地给予较高的评分。

[0004] 传统的解决方案是León等设计的Scratch作品计算思维评测工具Dr.Scratch[1]，该工具设计了7个维度、每个维度4个级别的计算思维评价表，根据匹配规则的情况给出得
分，但是在面对任务导向的学习中，受到任务本身局限性的影响，该方法仅有极少数规则有
效且作品之间的差距不大。抽象语法树是源代码语法结构的抽象表示，并不局限于编程语
言本身。以往的研究表明抽象语法树能比较好地表示图形化编程的作品，Jiang B等利用树
[2]
编辑抽象语法树表示图形化编程作品的编程轨迹 ，Davis R L利用抽象语法树表示作品，
继而将抽象语法树转化为四种类型(颜色+文本+缩进；颜色+缩进；文本；空白)的图片，使用
[3]
ResNet从图片分类的角度对图形化编程作品的评价进行了讨论 。该方法具有普适性，但
是这种方法也仅是从代码的逻辑角度进行考虑，缺乏对于儿童不受限于任务的自由发挥以
及儿童教育的鼓励的考量。此外，将图形化编程作品转化成图片的形式，在可拓展性上具有
一定局限性，只能够利用到有限的信息(该研究中证明，颜色+缩进形式的图片在ResNet‑18
上的表现最佳，这种形式图片只能够利用代码的逻辑结构和代码块的类型)。

[0005] 在专利文件CN201911230187中，提出一种图形化编程作品的在线评测方法，该方法包括利用Dr.Scratch设计的计算思维维度能力等级评价表评测计算思维，采用McCabe度
量法对圈复杂度进行评测，采用Halstead度量法对独立bug数、时间花费、工作量、难度、总
操作数进行评测。该方法中，McCabe度量法以及Halstead度量法都能够避免任务本身局限
性的影响。但是各个评测指标之间不存在联系，无法形成评测体系从整体上对作品进行评
级，并且没有考虑到原始McCabe度量法、Halstead度量法在图形化编程作品的适用性问题。

[0006] 常重利用McCabe度量法和Halstead度量法对Scratch作品进行分析，提出了McCabe度量法在Scratch语言中的使用规则，利用编程中的过程数据对Halstead方法在
[4]
Scratch语言的适用性进行了验证，并修正了部分度量指标 。该方法的指标适用于图形化
编程，但仅停留在单一指标的提出，并未形成完整的体系。

[0007] 另外，现有的研究和工具均是基于Scratch以往版本或其他图形化编程语言的，其共性是源代码文件直接内含抽象语法树。2019年Scratch正式发布3.0版本，其内部实现技
术与以往版本项目技术上差异较大，其源代码文件也不再直接内含抽象语法树，也无法根
据前期版本中抽象语法树的构造方法构建3.0版本的抽象语法树，因此前者的成果也不能
直接应用于后者。

[0008] 参考文献：

[0009] [1]Moreno‑León J,Robles G,Román‑González M.Dr.Scratch:Automatic analysis of scratch projects to assess and foster computational thinking[J]
.RED.Revista de Educación a Distancia,2015(46):1‑23.

[0010] [2]Jiang B,Zhao W,Zhang N,et al.Programming trajectories analytics in block‑based programming language learning[J].Interactive Learning 
Environments,2019:1‑14.

[0011] [3]Davis R L.Predicting Unit‑Test Scores for Graphic Representations of Simple Computer Programs[J].

[0012] [4]常重.Scratch作品评测系统的研究与实现[D].北京邮电大学,2019.

发明内容

[0013] 针对现有技术的不足，本发明的目的在于提供使用抽象语法树和图嵌入方法解决普适性问题，并从逻辑性、程序复杂度、创新性等多角度考虑的，偏向鼓励性质的图形化编
程的综合评价方法。

[0014] 为实现上述目的，本发明通过以下技术方案予以实现。

[0015] 一种图形化编程作品的评测方法，包括：

[0016] S1.获取图形化编程作品的特征；

[0017] S2.对类别型特征进行处理；

[0018] S3.将非类别型特征和类别型特征的处理结果输入分类器，获取评测分数。

[0019] 进一步的，所述步骤S1中，所述特征包括逻辑性特征，所述逻辑性特征的计算方法为：

[0020] S11.获取作品的源代码；

[0021] S12.为所述源代码构造抽象语法树；

[0022] S13.对所述抽象语法树进行图嵌入获得图向量R；

[0023] S14.逻辑性特征为作品的图向量R与一个或多个参考作品的图向量的最大相似度。

[0024] 进一步的，在步骤S12中，构建抽象语法树的规则为：(a)以舞台为根结点，属性为stage；(b)以角色作为舞台结点的子结点，属性为role；(c)以角色所实现的功能作为角色
结点的子结点，功能表现为实现所述角色的代码块，代码块与代码块之间根据逻辑关系进
行连接，属性为代码块的代码类型。

[0025] 进一步的，所述步骤S1中，所述特征还包括工作量特征、复杂度特征、老师偏好特征、关键变量特征和/或任务不相同统计量特征。

[0026] 进一步的，所述工作量特征包括操作量O和时间开销T'，通过改造的Halstead方法计算。

[0027] 进一步的，所述复杂度特征的计算方法为：

[0028] 初始化复杂度为1；

[0029] 遍历源代码，如果匹配到预置的操作码，则累加所述操作码对应的额外分支数；优选的，代码块为and、or、if、if‑else、repeat、repeat‑until、forever和stop。

[0030] 进一步的，在所述步骤S2中，所述老师偏好的处理方法为：对批改老师进行独热编码。

[0031] 进一步的，在所述步骤S1中，所述关键变量特征的获取方法为：

[0032] 遍历作品源代码，获取关键点处的内容；

[0033] 在所述步骤S2中，特征的处理方法为：

[0034] 如果所述内容是数值型数据，无需特别处理；

[0035] 若所述内容是有序的类别型数据，采取序号编码进行处理；

[0036] 若所述内容是无序的类别型数据，采取独热编码进行处理。

[0037] 进一步的，所述任务不相同统计量特征的获取方法为：遍历作品源代码，对比作品任务要求，统计与任务要求不同的角色的数量和所述角色的代码块数量。

[0038] 进一步的，所述分类器为XGBoost，弱学习器采用gbtree，损失函数采用softmax。

[0039] 本发明由于采用了以上技术方案，具有以下优点:

[0040] (1)将作品的抽象语法树视为图数据，而非转化为图片，大大增强了方法的可拓展性，可以为抽象语法树增加更多的语义信息，例如控制流和数据流。

[0041] (2)通过计算作品与多个参考作品的最大相似度来衡量逻辑性，在一定程度上解决了图形化编程评测中答案不唯一的问题。

[0042] (3)引入逻辑性、工作量、复杂度、任务不相关统计量以及老师等多维度的特征，在一定程序上解决了图形化编程评测中存在的创新性和鼓励性问题，使得图形化编程作品的
评价更加准确、可信。

附图说明

[0043] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明
的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据
这些附图获得其他的附图。

[0044] 图1为本发明一个实施例的评测方法的流程示意图；

[0045] 图2为本发明一个实施例的源代码的抽象语法树示意图；

[0046] 图3为本发明一个实施例的作品复杂度计算规则的示意图。

具体实施方式

[0047] 为使本发明实施例的目的、技术和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清查、完整的描述，显然，所描述的实施例是本发
明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没
有做出创造性方案劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0048] 为了实现上述目的，如图1所示，本发明采用下列技术方案：

[0049] S1.获取图形化编程作品的特征；

[0050] S2.对类别型特征进行处理；

[0051] S3.将非类别型特征和类别型特征的处理结果输入分类器，获取评测分数。

[0052] 在步骤S1中，特征可以包括非类别型特征和类别型特征，比如逻辑性特征属于非类别型特征。非类别型特征可以为数值型特征。具体包括：

[0053] S11、获取作品的源代码文件，如将作品的存盘文件sb3文件修改为压缩包文件，解压，提取其中的源代码文件(project.json文件)，并获得源代码；

[0054] S12、构造抽象语法树，即将作品源代码解析为包含结点、结点属性和边的抽象语法树；

[0055] S13、对抽象语法树的集合进行图嵌入得到图向量R；

[0056] S14、根据图向量R计算作品的逻辑性特征的向量表示；

[0057] 在步骤S12中，针对源代码文件，获取所有的角色和角色下面的代码块，并根据所有角色和代码块构建抽象语法树。在一个实施例中，以Scratch3.0编程语言为例，角色为
targets字段下的每个json对象，代码块为blocks字段下的每个json对象，构建抽象语法树
的规则为：(a)以舞台为根结点，属性为stage。(b)以角色作为舞台结点的子结点，属性为
role。(c)以角色所实现的功能作为角色结点的子结点，功能表现为一系列的代码块，代码
块与代码块之间根据逻辑关系进行连接，属性为代码块的代码类型。

[0058] 图2所示为源代码建立抽象语法树的示意图，其中，圆角矩形、椭圆、矩形分别代码舞台、角色、代码块三种类型的结点，结点上的文字代表结点的属性，结点之间的逻辑关系
体现为结点之间的父子关系，表现为从父结点指向子结点的边。

[0059] 在步骤S13中，可以采用Graph2Vec将抽象语法树转换为图向量R。采用图向量表示抽象语法树，意味着将抽象语法树认为是图数据，而不是通常意义上的图像数据(图数据
(graph data)是由结点及连接结点的边所构成的图形，这种图形通常用来描述某些事物之
间的某种特定关系，用结点代表事物，用连接两点的线表示相应两个事物间具有这种关系；
图像数据(image data)是指用数值表示的各像素的灰度值的集合；图数据中存在一种可以
表示图像数据的方式，被称为场景图，它将图像中的物体当作结点，物体之间的相互关系当
作边构成一场图，从而将关系复杂的图像简化为一个关系明确的语义图，而图像数据无法
表示图数据)。这种做法的优点是，能够非常容易地拓展抽象语法树(通过拓展结点、结点的
属性、边、边的属性)，将作品中的更多语义信息引入抽象语法树(例如数据流和控制流信
息)。这也是本发明优于上文文献3中利用图片方法进行评测之一处。

[0060] 在步骤S14中，逻辑性特征为作品图向量R与一个或多个参考作品的图向量的最大相似度。

[0061] 每一个作品都是针对一个任务，即学生根据老师布置的一个任务进行编程，编程结果就是作品，而参考作品是指老师为该任务提供的能够完成任务的程序代码，当然完成
任务的方法可能有多个，所以参考作品也可能有多个。

[0062] 在一个实施例中，特征还包括根据作品的源代码获取的作品的工作量特征、复杂度特征、老师偏好特征、关键变量特征和任务不相关统计量特征。

[0063] (1)工作量特征，通过改造的Halstead方法计算。工作量包括操作量O和时间开销T'，具体为：

[0064] 遍历作品源代码，统计源代码中唯一操作数的数量η1、唯一操作符的数量η2、操作数的总数N1和操作符的总数N2。例如，代码块是操作符，选项、字符串和数字是操作数。

[0065] 根据以下公式计算作品的操作量O和时间开销T。

[0066] η＝η1+η2

[0067] 程序长度N＝N1+N2

[0068] 容量V＝N+log2η

[0069] 难度

[0070] 工作量E＝D×V

[0071] 时间开销

[0072] 操作量O＝E×0.007+46

[0073] 时间开销修正T'＝T×1.42+1250

[0074] 其中，时间开销修正值T'和操作量O的计算公式是由常重利用Scratch编程过程数据对Halstead方法在Scratch语言下的适用性验证实验得出的，见上文中的文献4。

[0075] (2)复杂度特征，计算方法如下：

[0076] 任何只有一个进入点及结束点的结构化程序，其循环复杂度等于程序中决策点(if指令及条件循环)的个数加一，延伸到多个结束点的程序，循环复杂度如下：

[0077] 循环复杂度M＝π‑s+2

[0078] 其中，π是程序中决策点的个数，s是程序中结束点的个数。

[0079] 因此得到Scratch应用中的具体步骤如下：初始化复杂度为1；遍历源代码，如果匹配到操作码，则根据其对应的额外分支统计规则(代码块、操作码和额外分支数如图3所
示)，累加相应的额外分支数，当遍历完成时，得到最终的复杂度。

[0080] 在文献4中，常重在Scratch2.0中定义了and、or、if、if‑else、repeat、repeat_until六种代码块的额外分支数规则，而本发明增加forever、stop代码块的额外分支数规
则，stop代码块相当于程序中的退出点，使得计算出的复杂度更加准确。

[0081] (3)获取关键变量特征的方法是：遍历作品源代码，获取一个或多个关键点处的内容，该内容可能是代码块、条件或数值等。

[0082] 完成任务所必须要完成的关键步骤或关键条件称为关键点，例如，在一个实验的任务中(野兽需要抓到比尔，抓到之后停止)，最重要的事情是野兽运动的方向，结束动作和
触发结束动作的条件，分别对应于关键点是“towards”，“exit_action”和“condition”，每
个关键点对应一个关键变量特征。下面举例某一参考答案中的关键变量进行说明，
“condition”为“sening_touchingobject”，这是代码块的一种类型，该类型的代码块实现
的效果是判断是否碰到了某物。在图形化编程教育中，每个任务的一个或多个关键点是由
人工预先设置好的。

[0083] (4)任务不相关统计量，是指与任务要求不同的角色的数量和这些角色的代码块数量。对于角色而言，包括与任务要求不同的角色和与任务要求相同但数量不同两种情况。
在上面举例的实验的任务中，“num_bill”和“num_beast”被分为任务不相关统计量，是因为
任务要求仅包括一个比尔和一个野兽，超出的部分属于儿童自由发挥的范畴。

[0084] 每个任务所要求的角色(类型和数量)也由人工预先设置好。对于每个作品，获取其任务信息，然后遍历源代码，再根据预置的任务所要求的角色计算任务不相关统计量特
征。

[0085] (5)在一个实施例中，还可以引入老师偏好特征，因为任务作为导向的图形化编程，是没有一个标准答案的，老师批改是有主观因素的，但是大体上老师都是偏向鼓励的。

[0086] 在步骤S2中，需要处理的特征有老师偏好和关键变量特征。

[0087] (1)对应老师偏好特征，因为批改老师是无序的类别型数据(其变量值是定性的，表现为互不相容的类别或属性，且类别间不存在大小关系)，使用独热编码进行处理。

[0088] (2)对于关键变量特征，若关键点处的内容是数值型数据，无需特别处理；若关键点处的内容是有序的类别型数据(其变量值是定性的，表现为互不相容的类别或属性)，即
类别间存在大小关系，采取序号编码进行处理；若关键点处的内容是无序的类别型数据，即
类别间不存在大小关系，采取独热编码进行处理。

[0089] 工作量等特征的值为数值型，因此不需要进行处理。老师偏好和关键变量特征由于可能为类别型数据，因此要将其处理为数值型，以便与工作量等特征共同输入分类器。

[0090] 在步骤S3中，分类器的训练过程如下：

[0091] (1)数据集预处理，比如在小码王在线编程网站Scratch L0‑2随堂练习收集的20598份作品，每份作品都有评分(1～5分)。将完整的数据集根据步骤S1和S2提取并处理数
据集中作品的特征。

[0092] 其中，步骤S1中的Graph2Vec模型参数如表1所示。

[0093] 表格1：参数表1

[0094]

[0095] (2)划分数据集，将预处理过的数据集按8：2的比例划分为训练集和测试集。

[0096] (3)分类器可以有多种。在一个实施例中，采用XGBoost作为分类器，目标是多分类，弱学习器采用gbtree，损失参数采用softmax，具体参数(在本发明的实验中，一组最好
的参数)设置如表2所示。

[0097] 表格2：参数表2

[0098]

[0099] (4)在训练集上对分类器进行10折交叉验证训练，找到使得模型泛化性能最优的超参值。找到后，在全部训练集上重新训练模型，并使用测试集对模型性能做出最终评价。

[0100] 下面对本发明所用方法的性能进行了测试，具体结果如表3所示，表格中，DC代表文档分类(Document Classification)，IC代表图片分类(Image Classification)，GC代表
图分类(Graph Classification)，是三种考虑Scratch3.0存盘文件.sb3文件的不同角度，
其中IC角度由Davis R L(2017)提出，GC角度为首次。测试时采用了Precision、Recall、F1‑
score作为评价指标，这是三种广泛使用的指标。对比KimCNN和ResNet‑18 Baseline中的较
高值，Graph2Vec+XGBoost方法在Recall、F1‑micro、F1‑weighted分别有有7.2％、7.2％、
11.4％的明显提升，仅F1‑macro略有下降。在此基础上，所述方法对比Graph2Vec+XGBoost
方法在各项指标上均有5.5％、3.6％、3.6％、0.9％、5.0％的明显提升。

[0101] 表格3：小码王数据集评测结果

[0102]

[0103] 此外，基于数据不平衡的前提，为了更好地比较不同方法的性能，各个方法混淆矩阵中各个类别预测正确的准确率见表4(类别1、2由于样本数量较少不显示)。对比KimCNN方
法和ResNet‑18方法中的较高值，Graph2Vec+XGBoost方法在预测类别3的准确率有12％的
明显提升，类别4和类别5略有下降。对比前三种方法中的较高值，所属方法在类别3上的准
确率有43％显提升，类别4和类别5略有下降。

[0104] 表格4：各类别准确率

[0105]

[0106] 以上实施例仅用于说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施
例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或替
换，并不使相应的技术方案的本质脱离本发明各实施例技术方案的精神和范围。