基于程序向量树和聚类的学生程序算法识别方法

魏 敏，张丽萍，闫 盛

(内蒙古师范大学 计算机科学技术学院，内蒙古 呼和浩特 010022)

程序理解是对程序分析、抽象、推理从而获取程序特征和知识的过程，它在软件开发、复用和维护中占据重要作用[1]。程序算法识别是开发人员理解程序的重要步骤之一，是指针对程序代码识别出其所蕴含的程序算法[2]，例如给定一个程序代码，通过算法识别可以推断出该程序使用了冒泡排序算法。然而，实现相同算法的不同程序语法表示形式可能不同[3]，这使得人工分析无法满足复杂的程序算法识别需求。

本文以函数粒度作为基本单元，结合程序词法和语法结构特征，提出一种基于程序向量树和聚类的学生程序算法识别方法AR-PVTK(algorithm recognition based on program vector tree and k-means)。基本思路是：首先解析学生程序生成单词序列和抽象语法树，获取程序词法和语法结构信息；
其次针对单词序列训练word2vec模型得到程序单词的实数向量，结合抽象语法树构造程序向量树(program vector tree，PVT)，融合程序特征，并进一步优化树结构；
最后利用改进的递归自动编码器(improved recursive auto encoder，IRAE)模型获取程序表示并执行聚类，将使用相同算法的程序映射到向量空间中相近的位置，从而完成算法识别。该方法可以自动化识别程序算法，不仅能提高识别准确度，更能节省人工识别成本。

在20世纪80年代，程序算法识别研究兴起，目的是通过分析程序来评估一段代码中所包含的算法行为和功能，在程序优化、程序理解等方面具有重要意义。

早期时候，程序算法识别工作采用传统基于知识表示的方法。该类方法需要选择合理的表达方式对算法本质特征进行描述，然后基于算法表示建立模板库通过模式匹配完成算法识别，但是此方法在建立和维护模板库时费时费力。后来，基于信息检索技术的识别方法出现，主要利用非代码的文本信息，如程序代码中包含的函数名、注释以及对应的设计文档，辅助完成程序算法识别工作。该类方法不仅依赖注释、相关代码文档的支持，还对程序书写格式具有严格要求，因此识别准确度较低。

近年来，机器学习技术为PLP带来新途径，能够在更深层次挖掘源代码数据特征并获取程序的抽象表示[4,5]，因此这一阶段主要以程序特征分类的方法[6,7]进行程序识别。王甜甜等[8]提出了一种基于结构化度量向量的聚类方法，以从大量现有程序中快速识别结构相似的程序，为缺陷程序提供修复建议。Zhang等[9]提出了一种基于过程挖掘的源代码相似度检测方法，该方法充分考虑源代码运行时的动态特征，通过收集程序运行的日志，使用过程挖掘来获得这两段源代码的流程图，通过计算这两个流程图的相似度来衡量两段源代码的相似度。谭丁武等[10]重点关注源代码的数据流、控制流信息，并结合语法结构信息构造代码图，利用门控神经网络(gated graph attention neural network，GGANN)学习程序的分布式表示实现程序分类。此外，还有使用代码相似度检测[11]的方法，即认为使用相同算法的程序具有高度相似性。高蕾等[12]基于代码相似性设计一种聚类算法，该算法可以针对给定编程任务的所有正确解决方案自动生成聚类。实验结果表明，聚类算法可以成功获取数据集中的独特聚类。夏之阳等[13]首先对代码进行程序切片、变量替换等预处理，然后利用Bi-LSTM网络(bi-directional long short-term memory)对代码提取特征表示，计算漏洞模板和待测代码相似度判断漏洞。该类方法可以提取代码语义信息，能够检测更高级别的代码克隆，但同样具有构建PDG和比较子图同构时代价较大的问题。史志成等[14]提出一种基于卷积和双向循环神经网络的代码特征提取模型CVRNN，通过卷积神经网络提取代码的语法结构特征信息，通过双向循环神经网络提取代码的序列信息。该方法无需人工参与就可以很好地学习程序表示，应用在代码分类任务中，优于较多已有的用于代码特征提取的深度学习模型。本团队在代码克隆方面也展开过大量研究。王亚芳等[15]提出基于图像相似度的代码克隆检测方法，将处理好的源代码转化为图像，利用Jaccard 距离和感知哈希算法进行相似性识别，可以在6款开源软件上取得较好检测效果。

对比以上研究，基于程序特征分类的方法主要关注程序的自身特性，能够对任意程序算法提取特征进行分析，也不依赖代码相关数据，使用深度学习模型提取代码特征还能缓解人工压力，提高识别准确率，因此具有良好的扩展性。

本节主要介绍提出的基于程序向量树和聚类的学生程序算法识别方法，如图1所示，主要包括以下4个步骤。

(1)特征提取。从在线编程实践平台上针对不同类别的编程问题，收集与其相对应的正确的学生程序代码，构成学生程序集，然后将每个学生程序处理成单词序列和抽象语法树，以获取程序的词法和语法结构特征；

(2)程序向量树构造。针对所有程序的单词序列利用统计语言模型(statistical language model，SLM)学习单词的分布式嵌入表示得到单词向量，然后在抽象语法树的基础上，赋予叶子节点对应单词的向量表示，完成程序向量树的构造，再进一步去除无用节点，优化树结构；

(3)向量编码与聚类。结合程序向量树采用改进的递归自动编码器模型，由下至上逐层将非叶子节点编码成定长向量，以根节点的向量表示作为程序向量表示，再对程序向量执行k-means聚类，将使用相同算法的程序按照特征表示相近程度划分到同一类别；

(4)获取算法识别结果。通过以上步骤，相同编程问题的学生程序根据使用的算法不同被分别归类，至此完成程序算法识别工作。

2.1 程序特征提取

程序可以看作是单词和符号组成的文本序列，可以对程序单词进一步表示学习挖掘单词间的语义相似关系。本文首先将学生程序处理成单词序列，为了进一步降低数据稀疏性，对数值型和字符型常量分别抽象为同一记号，具体替换说明见表1。

此外，程序语言相比于自然语言还具有严格的强结构性、长依赖性和可执行性等特殊属性。AST[16]是对程序语义和语法分析后得到的一种树形表现形式，记录了程序的语法规则和执行顺序，在程序理解相关研究中起着重要的作用。AST包含了叶子节点和非叶子节点两种节点类型以及各节点之间的父子关系，其中叶子节点代表标识符，非叶子节点代表语法结构体，非叶子以及叶子节点共同描述了程序执行的数据流和控制流信息。本文使用Eclipse提供的软件开发工具包JDK(Java development kit)创建所有Java程序代码的抽象语法树，提取程序的语法结构和语义特征，用于后续向量编码工作。

2.2 程序向量树构造

程序向量树(PVT)是基于程序抽象语法树改造后的一种变体，由AST中各叶子节点被赋予对应的单词向量表示而得来，它可以为后续合成程序向量提供支持。PVT完整地保留了程序代码的语法结构信息，同时去除了个别无用节点，加入了具有语义信息的单词表示，可以有效规避语法形式的多样化。本文要解决的程序算法识别问题关键在于识别具有等价的语法结构形式的程序，因此针对程序代码的表示也使用程序向量树的方法，具体步骤如图2所示，包括词向量训练和程序向量树生成。

2.2.1 词向量训练

针对程序代码而言，词嵌入(word embedding)是一种将程序文本中的单词转换成数字向量的方法。与one-hot编码的表征方式相比，分布式表示能够较好地涵盖程序单词的语义信息，也不会产生高维度编码稀疏的问题，具有相似上下文的两个单词使用分布式表示可以被映射到向量空间中相近的位置。例如“for”和“while”，它们在单词使用上虽然有所不同但表达意思类似，因此在向量空间的位置也相近。

本文利用获取到的程序单词序列，使用最经典的word2vec词嵌入模型，在语料库上训练得到程序单词连续、稠密的向量表示。该模型由Mikolov等[17]提出，主要包括跳字模型(skip-gram)和连续词袋模型(continuous bag of words，CBOW)。本文选择skip-gram模型，该模型由输入、映射和输出3层网络模型构成，如图3所示，它利用中心词来推断上下文中一定窗口内其它单词出现的条件概率，并与已经存在的单词进行比对，最小化损失函数值来达到参数的优化，实现较好的训练效果。

最终，得到3370个长度不等的单词序列，词汇表中共有796个独特的单词，每个单词被表示为296维度的实数向量。

2.2.2 程序向量树生成

完成AST的提取，赋予AST叶子节点对应单词的向量表示就可以得到PVT。图4(a)、图4(b)和图4(c)分别是一个Java方法示例和其对应的抽象语法树以及PVT。

但是，通过分析AST发现，一些节点并不含有程序语义信息，它们对判断程序相似性的作用较小，因此应该被去除，来进一步减小树规模、统一树结构。完满二叉树是所有非叶子节点的度均是2的特殊二叉树，抽象语法树是多叉树结构，如果将无用节点去掉，将AST转化为完满二叉树，则能解决上述问题。本文将使用DLC[18]中提出的25种和曾杰等[19]补充的7种完满二叉树生成规则对AST进行转换，可以涵盖ArrayType、EnumDeclaration、AnnotationTypeDeclaration等32种节点类型的处理，处理后的抽象语法树具有相同的树结构，即非叶子节点都有0或者2棵子树。转化方法根据非叶子节点的度数分为3种。

(1)等于1：判断该节点与其孩子节点类型的重要性，将二者合并保留重要的节点类型。

(2)等于2：不作处理。

(3)大于2：按照设计的规则提取相关叶子节点，去除无用节点，添加人工定义的非叶子节点构建二叉树，对于再次出现的叶子节点数目是1的非叶子节点，继续执行(1)。

上述过程将AST转换为完满二叉树，相应的PVT也是完满二叉树的结构，这一结构保证每个非叶子节点都有相同的子树数量，为生成非叶子节点向量提供方便。

2.3 向量编码与聚类

本节在程序向量树的基础上，结合加权编码机制，利用递归自动编码器模型得到固定长度的向量表示，然后针对程序向量进行聚类分析，将使用相同程序算法的学生程序划分为同一类，完成学生程序算法识别任务，具体流程如图5所示。

2.3.1 向量编码

(1)

在非叶子节点向量编码过程中用到的加权编码机制，基本思路是：对于每一个非叶子节点，拥有的左右子树哪棵子树包含的叶子节点数目越多，它所承载的程序信息就越丰富，理所应当被赋予更高的权重系数。因此，对于任意一个非叶子节点，根据以上描述，定义一致的加权编码策略：非叶子节点以及它两个孩子节点的向量表示分别为qvector、vector1和vector2，通过遍历AST得到对应子树的叶子节点数量是n1和n2(当子树中只包含一个叶子节点则设置为1)，那么能够得到qvector的向量表示为式(2)

(2)

2.3.2 k均值聚类

向量聚类将使用相同算法的程序按照特征表示相近程度划分到同一类别。本文采用基于距离的k均值聚类算法(k-means clustering algorithm)实现上述操作，该算法具有计算速度快、鲁棒性强等优点。基本思想是：在给定k值和k个初始类簇中心点的情况下，通过迭代不断调整聚类中心或者达到设定的迭代次数，最终将数据集中的个体划分为k类，每个类称作一个“簇(cluster)”，同一簇中的个体更相互接近或相关，不同簇中的个体更远离或不同。以下是该算法的详细描述。

假设给定包含了n个数据样本的数据集X，X的每个样本点xi拥有d个维度的属性。k-means算法的目标是将n个样本依据样本间的相似性划分为k类组成集合，每个样本属于且仅属于离它自身距离最小的类簇，其中样本点xi到类簇ck的中心点pk的欧氏距离采用式(3)进行计算

(3)

k-means聚类的反复迭代过程描述为以下步骤。

(1)设定初始中心点的个数k，选取数据空间中的k个样本点作为初始聚类中心。

(2)将每个样本点根据它们与k个聚类中心的欧氏距离，将其划分到最近的聚类中心(最相似)所对应的类。

(3)更新聚类中心：将每个类别中所有样本点对应的均值作为该类别新的聚类中心，计算目标函数的值。

(4)判断聚类中心和目标函数的值是否发生改变，若不变，则输出结果，若改变，否则返回(2)。

本文将2.3.1节得到的程序向量表示输出到后缀名为.csv文件，文件每一行代表一条数据，即一个Java程序所对应的向量表示，共计3370条数据。

3.1 数据集与评价指标

3.1.1 数据集

为了准确而客观地评价本文方法，从在线编程实践平台筛选10类编程问题，每类收集200～500个学生程序，共计3370个正确程序，包含排序、递归、查找、哈希表和动态规划等算法知识。为了使实验数据集真实且有效，选择依据是：①按照学生作答人数选择数量较多的编程问题，这在一定程度上说明该类题型具有代表性，也保证了数据的真实性与多样性。②为保证每类编程任务收集的程序功能是相同的，选取通过OJ(online judge)平台测试的程序代码，即能够解决问题的正确程序。针对每类问题，以函数粒度作为研究对象进行实验，每类编程任务的问题名称、程序数量、总代码行数和功能描述等具体信息见表2。

表2 实验数据

3.1.2 评价指标

本文使用的实验数据采用人工的方法标记其所属类别，通过调整兰德系数(adjusted rand index，ARI)、调整互信息(adjusted mutual information，AMI)和Fowlkes-Mallows指数这3个指标来衡量程序算法识别的结果。

调整兰德系数ARI常被用来描述一个集合中的元素真实分类与预测分类的吻合程度，ARI的取值区间为[-1,1]，即ARI值越大，说明方法具有更强的区分能力，聚类效果越好，ARI的详细定义及计算公式请参见文献[20]。

互信息MI用来计算两个集合之间的相关性，调整互信息AMI用来衡量两个数据分布的吻合程度，AMI的取值范围是[-1,1]，AMI值的大小与聚类的准确性呈正相关，二者详细定义及计算公式请参见文献[21]。

FMI指数(fowlkes mallows index，FMI)是针对训练集和验证集数据之间求得的查全率和查准率的几何平均值，即式(4)。该指标同样也是数值越大，聚类的结果越准确

(4)

3.2 实验结果及分分析

3.2.1 4种程序向量生成方法聚类效果对比实验

由于业界缺少类似的方法，所以针对本文提出的基于程序向量树和聚类的学生程序算法识别方法AR-PVTK进行组内评估验证。本文将从调整兰德系数(ARI)、调整互信息(AMI)和FMI这3个指标进行验证，以检验AR-PVTK方法的有效性。

为验证本文提出的AR-PVTK方法在获取程序向量表示时的有效性，我们分别对比了未使用加权和使用不同权重计算方法后的聚类效果(即方法1～方法4)。通过实验得到各方法的分类性能对比见表3～表6。

方法1：利用所有节点向量的平均值作为程序向量表示。

方法2：利用TF-IDF[22]计算非叶子节点类型的词频，作为对应节点的权重系数，从而生成程序向量。

方法3：TF-IDF基础上加入非叶子节点的位置信息并进行归一化处理，从而生成程序向量。

方法4：利用子树的叶子节点数目的权重计算规则而生成的程序向量，即本文的AR-PVTK方法。

表3 基于均值节点向量方法的分类性能/%

表4 基于TF-IDF加权方法的分类性能/%

表5 TF-IDF加入节点位置信息方法的分类性能/%

表6 本文AR-PVTK方法的分类性能/%

表3～表6分别记录了10类编程问题使用方法1、方法2、方法3和方法4后，在ARI、AMI和FMI指标上的得分情况。从实验结果可以看出，本文方法AR-PVTK的分类性能优于均值节点向量方法和另外两种TF-IDF方法，表明利用子树的叶子节点数目的权重计算规则生成的程序向量可以更准确地获取到程序信息，因此可以得到较好的分类结果。

表7显示了数据集在使用了4种方法后，在ARI、AMI和FMI指标上的平均得分情况。从实验结果可以看出，方法2、方法3以及AR-PVTK方法分类性能均优于方法1，说明加入权重后，所有程序聚类的准确率均有提高，验证了树节点类型与所在位置的不同，它所涵盖的程序信息不同，贡献的信息量也存在一定差异。因此，针对一些重要节点需要通过加入权重值来适当调整特征向量来提高聚类的性能。此外，由表7还可以看出，本文方法AR-PVTK在ARI、AMI和FMI值较基于均值节点向量的方法提升幅度较大，较基于TF-IDF加权的方法分别提升22.24%、17.65%和13.52%，较TF-IDF加入节点位置信息的方法分别提升18.5%、17.1%和11.89%。通过比较4种方法分类性能评价的平均值可以看出，本文方法在ARI、AMI和FMI指标上均获得了最佳的效果，验证了本文方法在程序表示方面的有效性。

表7 4种不同方法的分类性能/%

3.2.2 聚类实验结果

图7给出了使用本文方法在不同编程任务上执行程序算法分类后的实验结果。以“最大子序和”编程问题为例，即Lab1，对其聚类结果进行详细分析。如聚类结果所示，该问题每个簇中分别有72、64、128个解决方案，通过人工对这些程序代码的分析，发现C1、C2和C3中解决方案的逻辑结构基本一致。首先初始化结果值，然后利用循环不断比较、更新子序列值，最后打印最大子序和。C1和C2中的解决方案主要使用“动态规划算法”进行问题求解，前者通过判断当前最大连续子序列和对结果是否存在增益影响进行子序列更新，后者通过寻找规律总结状态方程进行求解，C3中的解决方案则是使用“暴力法”利用双层循环累加选出最优解。

以上实验结果可以看出，本文方法能够针对相同编程问题的众多学生程序，通过程序词法和语法结构特征自动化识别出解决该问题的不同程序算法，继而进一步为学生和教师提供问题求解方案。

3.2.3 算法推荐实验及结果

本节将算法识别结果应用在程序算法推荐任务当中，向学生提供编程问题的多个解决方案，并对方法的有效性进行人工评估。

(1)程序算法推荐

本文使用Lucene全文检索技术，通过关键词匹配完成推荐。实现过程包括3部分：编程问题描述预处理，创建索引，以及基于关键词搜索。

首先，编程问题描述预处理。对于编程问题描述执行文本标准化和去除停用词等操作。主要包括去除文本中的标点符号，使用Lucene检索包中封装好的分词模块进行分词，以及删除停用词，如 “的”、“地”等词。其次，创建索引。以某一类编程问题作为一个搜索单位，并创建对应文档(Document)，Document主要包含两个域(Field)，分别是问题名称和描述。最后，基于关键词搜索。利用算法识别结果构建程序算法库，建立编程问题描述和多个解决方法的一对多关联关系。针对用户输入的自然语言形式的问题查询语句同样执行文本处理操作，然后通过关键词搜索的方法匹配到解决该类问题的程序算法。

(2)推荐结果

针对程序算法推荐方法的有效性，采用人工小组进行评估。协助本次实验的参与者是8名具备3年程序设计课程经验的助教以及15名在校学生，针对以上10类编程问题，参与者在阅读并比较每一类问题的算法推荐结果后完成评估问题。针对助教人员的问题如下，评估结果采用Likert scale五级量表，1(非常不同意)至5(非常同意)，以下记为A～ E，对应分值为1、0.5、0、-0.5和-1。

Q1：程序算法推荐方法是否有助于提高学生的算法应用能力和问题求解能力。

Q2：程序算法推荐方法是否可以辅助教师进行编程教学。

统计结果见表8，在Q1问题上，由P1=0.35>0可知，大约87.5%的参与者认为算法推荐方法有效。在Q2问题上，由P2=0.3>0可知，大约75%的参与者认为算法推荐方法可以促进编程教学，换言之，学生在不同类簇中的解决方案基本上可以代表编程问题的典型解决方案，并且可以在教学内容上为教师提供辅助性的教学资源。

表8 统计结果1

针对在校学生也调查了对算法推荐结果的反馈，这些学生都曾经完成过这10类问题。给学生的问题如下：

Q3：程序算法推荐方法是否有助于改善程序编写、提高算法思维。

Q4：通过编程问题的算法反馈结果是否可以得到其它求解方法的启发。

统计结果见表9，在Q3问题上，由P3=0.5>0可知，66.7%的学生认为算法推荐结果。在Q4问题上，由P4=0.7>0可知，80%的学生表示在阅读了问题的其它解决方案后可以获得新的灵感，20%的学生认为大多数解决方案除了处理输入数据的方式不同外，在解决问题的方法上没有明显的区别，受到启发的效果不强烈。

表9 统计结果2

从问卷调查的结果中可以看出，大部分的参与者对程序算法推荐方法持肯定态度，认为通过程序算法推荐的手段为学生提供“一题多解”的算法实现，能够培养学生的算法思维与问题求解能力，并为算法教学提供指导作用。

本文提出了一种基于程序向量树和k-means聚类的学生程序算法识别方法。利用程序向量树融合程序单词的词法信息和程序的语法结构信息，提高了对学生程序算法识别的准确率。本文方法应用在程序算法推荐任务中，可以很好地为教师和学生提供多样化的编程问题解决方案。

程序算法识别实现了程序算法的自动化理解，在教育教学和程序优化等方面具有广阔的应用前景。将程序算法识别应用于编程学习领域，一方面可以协助教师对学生群体学习情况的监测，了解学生对编程方法的掌握情况，为科学施教提供良好的决策，另一方面从学生程序数据出发，挖掘算法知识和求解方法更符合学生的认知规律，能够给予学生编程启发。将程序算法识别应用于程序优化问题，可以为开发者寻找在语义上保持一致的程序优化方案，将性能较差的程序替换性能较好的程序，提升程序执行效率。

本文方法仍然存在诸多不足。其一识别的程序语言种类单一，主要针对Java编程语言的学生程序，优化树结构的规则也只对Java程序有效，不能迁移到其它语言程序的识别任务中。其二，本文方法主要针对使用单个方法实现的编程问题，以函数为粒度提取程序特征，无法应用于多个方法组合调用的编程问题。在未来，可以进一步丰富识别的程序语言种类，同时对于调用多个方法的编程问题提取关键代码语句形成组合程序用以提取重要特征。

猜你喜欢 聚类编程向量 一种傅里叶域海量数据高速谱聚类方法北京航空航天大学学报(2022年8期)2022-08-31向量的分解新高考·高一数学(2022年3期)2022-04-28一种改进K-means聚类的近邻传播最大最小距离算法计算机应用与软件(2021年7期)2021-07-16编程，是一种态度少先队活动(2021年2期)2021-03-29聚焦“向量与三角”创新题中学生数理化(高中版.高考数学)(2021年1期)2021-03-19AR-Grams：一种应用于网络舆情热点发现的文本聚类方法中国传媒大学学报(自然科学版)(2021年5期)2021-02-24元征X-431实测：奔驰发动机编程汽车维修与保养(2021年8期)2021-02-16编程小能手学生天地(2020年17期)2020-08-25纺织机上诞生的编程数学大王·低年级(2020年3期)2020-03-12向量垂直在解析几何中的应用高中生学习·高三版(2016年9期)2016-05-14

推荐访问:程序 向量 算法