基于程序向量樹和聚類的學生程序算法識別方法

魏 敏，張麗萍，閆 盛

(內蒙古師范大學 計算機科學技術學院，內蒙古 呼和浩特 010022)

0 引 言

程序理解是對程序分析、抽象、推理從而獲取程序特征和知識的過程，它在軟件開發、復用和維護中占據重要作用[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)模型獲取程序表示并執行聚類，將使用相同算法的程序映射到向量空間中相近的位置，從而完成算法識別。該方法可以自動化識別程序算法，不僅能提高識別準確度，更能節省人工識別成本。

1 相關工作

在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款開源軟件上取得較好檢測效果。

對比以上研究，基于程序特征分類的方法主要關注程序的自身特性，能夠對任意程序算法提取特征進行分析，也不依賴代碼相關數據，使用深度學習模型提取代碼特征還能緩解人工壓力，提高識別準確率，因此具有良好的擴展性。

2 基于程序向量樹和聚類的學生程序算法識別方法

本節主要介紹提出的基于程序向量樹和聚類的學生程序算法識別方法，如圖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 實驗分析

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

從問卷調查的結果中可以看出，大部分的參與者對程序算法推薦方法持肯定態度，認為通過程序算法推薦的手段為學生提供“一題多解”的算法實現，能夠培養學生的算法思維與問題求解能力，并為算法教學提供指導作用。

4 結束語

本文提出了一種基于程序向量樹和k-means聚類的學生程序算法識別方法。利用程序向量樹融合程序單詞的詞法信息和程序的語法結構信息，提高了對學生程序算法識別的準確率。本文方法應用在程序算法推薦任務中，可以很好地為教師和學生提供多樣化的編程問題解決方案。

程序算法識別實現了程序算法的自動化理解，在教育教學和程序優化等方面具有廣闊的應用前景。將程序算法識別應用于編程學習領域，一方面可以協助教師對學生群體學習情況的監測，了解學生對編程方法的掌握情況，為科學施教提供良好的決策，另一方面從學生程序數據出發，挖掘算法知識和求解方法更符合學生的認知規律，能夠給予學生編程啟發。將程序算法識別應用于程序優化問題，可以為開發者尋找在語義上保持一致的程序優化方案，將性能較差的程序替換性能較好的程序，提升程序執行效率。

本文方法仍然存在諸多不足。其一識別的程序語言種類單一，主要針對Java編程語言的學生程序，優化樹結構的規則也只對Java程序有效，不能遷移到其它語言程序的識別任務中。其二，本文方法主要針對使用單個方法實現的編程問題，以函數為粒度提取程序特征，無法應用于多個方法組合調用的編程問題。在未來，可以進一步豐富識別的程序語言種類，同時對于調用多個方法的編程問題提取關鍵代碼語句形成組合程序用以提取重要特征。