基于源碼模式挖掘的軟件輔助開發(fā)技術(shù)研究

付 鵬，沈莉莉

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

基于源碼模式挖掘的軟件輔助開發(fā)技術(shù)研究

付 鵬，沈莉莉

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院，上海 200093)

由于軟件代碼的復(fù)雜性，對于不了解框架的新手，很難利用開源社區(qū)中的代碼來開發(fā)軟件。因此，利用數(shù)據(jù)挖掘技術(shù)挖掘現(xiàn)有代碼中的編程模式成為研究熱點。文中介紹了頻繁項挖掘Apriori算法，并提出了基于源碼模式的軟件輔助開發(fā)方法。它能夠根據(jù)用戶輸入的關(guān)鍵字來智能匹配類庫中的特定父類，挖掘基于此父類的編程模式，給出優(yōu)先要重寫的方法以及關(guān)聯(lián)規(guī)則。實驗結(jié)果表明，新手可以利用這些編碼建議，快速學(xué)習(xí)一個新的框架，提高開發(fā)效率。

源碼;數(shù)據(jù)挖掘;編程模式;軟件輔助開發(fā)

如今開源社區(qū)受到越來越多人的關(guān)注，人們可以輕松從網(wǎng)絡(luò)上獲取各種軟件源代碼，軟件重用[1]是軟件工程的一個熱點研究方向，它可以為開發(fā)新手帶來很多好處，例如提高工作效率、減小開發(fā)成本、獲取更好的產(chǎn)品質(zhì)量以及更快的投入市場。但新手很難理解基于同一種框架而編寫的代碼，首要的問題是不知道編寫第一行代碼。

框架作為目前軟件開發(fā)的一個重要組成部分，扮演著重要角色，然而對框架不了解的新手，要重用框架并不容易?？蚣鼙緛砭褪菫榱遂`活性而設(shè)計的，因此引入了很多抽象類，這使理解框架變的更加復(fù)雜。而且，開發(fā)者單單理解一個類無法使用框架，還需要理解框架的整體架構(gòu)。盡管如此，目前還是有很多方法來解決這個問題，但存在一些弊端。例如，一些框架教程以及相應(yīng)的API[2]文檔，可以幫助開發(fā)人員學(xué)習(xí)框架，但框架開發(fā)人員編寫文檔的水平參差不齊，有些框架開發(fā)者編寫的文檔質(zhì)量不高；另外有的框架版本已更新，但文檔并沒有及時更新。文獻(xiàn)[3]提出了一種挖掘用戶類庫的重用模式的方法，可以根據(jù)用戶選擇的應(yīng)用，挖掘其中的類庫重用模式，這樣在使用特定框架時，只需已知其他開發(fā)者如何使用框架，就能以同樣的方式使用框架，這對構(gòu)建應(yīng)用有一定的幫助，但用戶首先需要挑選那些使用框架與其一致的應(yīng)用，此方法挖掘出來的關(guān)聯(lián)規(guī)則[4- 6]，對于框架初學(xué)者來說，要理解這些關(guān)聯(lián)規(guī)則并應(yīng)用到自己的應(yīng)用中難度較大。文獻(xiàn)[7]提出了一種幫助開發(fā)人員理解框架的方法，這種方法可以在用戶實例化一個對象之后，挖掘現(xiàn)有代碼庫，按照置信度給出下一步應(yīng)該進(jìn)行操作的提示，這樣用戶在編寫代碼的時候就有了一定的參考，但初學(xué)者并不知道首先要實例化哪個對象。針對上述問題，文中提出了一種新的輔助開發(fā)方法CodeMining，它根據(jù)現(xiàn)有框架源碼庫，挖掘其中的編程模式，為不了解框架的新手提供編碼建議，輔助開發(fā)。

1 Apriori算法

基本概念：規(guī)則A->B在事務(wù)集D中成立。

(1)支持度：P(A∩B)，既A發(fā)生時B也發(fā)生的概率；

(2)置信度：P(B|A)，即在A發(fā)生的事件中同時發(fā)生B的概率P(AB)/P(A)。

例如購物籃[8]分析：泡面?火腿腸

例：[支持度：2%，置信度：50%]

支持度2%：意味著2%顧客同時購買泡面和火腿腸。

置信度50%：意味著購買泡面的顧客50%也購買火腿腸；

(3)如果事件A中包含k個元素，那么稱這個事件A為k項集事件A滿足最小支持度閾值的事件為頻繁k項集；

(4)同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則。

Apriori算法[9-10]的主要作用是尋找所有支持度不小于最小支持度(minsup)的項集。項集的支持度是指包含該項集的事務(wù)所占所有事務(wù)的比例。頻繁項集[11-12]就是指滿足給定的最小支持度的項集。該算法會對數(shù)據(jù)集進(jìn)行多次遍歷：第一次遍歷，對所有單項集的支持度進(jìn)行計數(shù)并確定頻繁項；在后續(xù)的每次遍歷中，利用上一次遍歷所得頻繁項集作為種子項集，產(chǎn)生新的潛在頻繁項集(即候選項集)，接下來就是對候選項集的支持度進(jìn)行計數(shù)，在本次遍歷結(jié)束時統(tǒng)計滿足最小支持度的候選項集，則本次遍歷對應(yīng)的頻繁項集就確定了，這些頻繁項集又作為下一趟遍歷的種子。重復(fù)此遍歷過程，直到再不能發(fā)現(xiàn)新的頻繁項集，算法結(jié)束。

其中，Apriori算法有兩個核心步驟:(1)連接步：假設(shè)Apriori算法對事務(wù)集中的項按字典順序排序，前面所說的由種子項集生成新的頻繁K項集就是通過保證事務(wù)集中不同項前K-1項相同，而第K項不同，則認(rèn)為這兩項是可連接的；(2)剪枝步：如果一個項集是非頻繁的，那么其所有超集也是非頻繁的，所以它的所有超集就沒有必要再進(jìn)行搜索了，就是把那些不滿足minsup的項集從生成的新的頻繁K項集中刪除。

下面介紹Apriori算法的實現(xiàn)，算法1給出了Apriori算法偽代碼。Apriori假設(shè)事務(wù)或項集里的各項已經(jīng)預(yù)先按詞典序進(jìn)行排列。項集里項的數(shù)量被稱為項集的大小，大小為k的項集被稱為k項集。用Fk表示大小為k的頻繁項集的集合，用Ck表示相應(yīng)候選項集的集合，F(xiàn)k和Ck都包含一個存儲支持度的字段。第一次遍歷只對每個單項的出現(xiàn)次數(shù)計數(shù)并確定頻繁1-項集。隨后的遍歷包含兩個階段，第一階段調(diào)用Apriori-gen函數(shù)從第k-1次遍歷產(chǎn)生的頻繁項集Fk-1中獲得Ck；第二階段掃描事務(wù)集D，用函數(shù)Subset對Ck中每個候選項集的支持度進(jìn)行計數(shù)，將不滿足最小支持度的項集從候選項集中刪除。

算法1 Apriori算法

∥頻繁1項集

F1= {frequent 1-itemsets}；

for(k=2；Fk-1≠□) do begin

∥新的候選

Ck=apriori-gen(Fk-1)；

∥掃描D，對候選項集進(jìn)行統(tǒng)計計數(shù)foreach transactiont∈Ddo begin

Ct=subset(Ck，t)；

foreach candidate c∈ do begin

c.count++；

end

Fk= {c∈Ck∣c.count≥minsup}

end

returnFk=最大頻繁項集；

Apriori算法通過剪枝來減少候選集大小來獲得良好的性能。然而，在頻繁項集很多或者最小支持度很低的情況下，算法必然產(chǎn)生數(shù)量龐大的候選項集，并且需要反復(fù)掃描事務(wù)集D來檢查數(shù)量龐大的候選項集，代價仍然較高，但是它作為經(jīng)典的數(shù)據(jù)挖掘[13-14]算法，簡單實用，能夠解決文中的問題。

2 基于源碼的模式挖掘

本文主要研究Jenkins插件，利用Apriori算法挖掘其中的編程模式，生成編碼建議給用戶。生成的編碼建議主要分為兩個部分：一是在用戶選擇了一個父類之后，優(yōu)先要重寫的方法頻繁項；二是這些重寫方法之間的關(guān)聯(lián)規(guī)則，例如：類A要重寫父類方法a(·)和方法b(·)之后，還要重寫方法c(·)的概率，此處的概率即置信度。

圖1 本文工作概述

如圖1所示，本文主要工作包括以下4個階段：第一階段：預(yù)處理階段，把相關(guān)有用的信息保存到數(shù)據(jù)庫中，減少后期代碼頻繁項挖掘[15]的時間開銷；第二階段：挖掘Jenkins插件類庫中類與類之間的繼承關(guān)系，生成樹形結(jié)構(gòu)圖；第三階段：根據(jù)用戶輸入關(guān)鍵字智能匹配樹形結(jié)構(gòu)中對應(yīng)節(jié)點；第四階段：從上一步匹配的節(jié)點為切入點，挖掘代碼中需要重寫的方法，為用戶提示要優(yōu)先重寫的方法，以及關(guān)聯(lián)規(guī)則和對應(yīng)的置信度。

第一階段：把插件的插件名、子類名、繼承的父類名以及子類中重寫的method等信息存儲到數(shù)據(jù)庫中，方便后面挖掘插件重用的父類信息。另外還要把繼承Jenkins類庫父類的子類的類名進(jìn)行分詞，便于通過關(guān)鍵字進(jìn)行節(jié)點匹配；

第二階段：為了從這些代碼中挖掘出相應(yīng)的父類繼承關(guān)系樹形結(jié)構(gòu)圖，通過分析Jenkins插件中繼承Jenkins類庫中父類的代碼，它們的import信息都是以import hudson開頭，或包含husdon的，先解析插件源碼中的import信息。但是并不是所有的import信息都是有用的信息，有些類不是插件繼承的父類，這部分類要剔除掉；還有些類雖然被插件中的子類繼承了，但是只有一個插件繼承過，這種父類也要剔除掉，因為挖掘頻繁項至少要有兩個事務(wù)，只有一個插件繼承的父類，事務(wù)集中只有一個事務(wù)。例如圖2中所示的import信息,org.jvnet.hudson.t- est.HudsonTestCase類HudsonTestCase是Jenkins插件類庫中的一個父類，用戶在寫插件的時候可以直接繼承父類。這些代碼中的import信息就是要利用的信息，在這個階段的主要任務(wù)是生成Jenkins插件中類似的類與類之間的繼承結(jié)構(gòu)關(guān)系圖，為下一個階段中匹配對應(yīng)節(jié)點做準(zhǔn)備；

圖2 源碼import信息

第三階段：這個階段就是為了獲取用戶想要了解的信息，然后有針對性的挖掘，并返回給用戶有價值的信息。首先用戶輸入最能代表他想實現(xiàn)功能的關(guān)鍵字，CodeMining根據(jù)用戶的輸入的關(guān)鍵字智能匹配相應(yīng)的節(jié)點，并給出評分，分?jǐn)?shù)越高，代表關(guān)聯(lián)性越大，用戶可以很輕松的做出自己的選擇，作為編寫代碼的切入點；

第四階段：這個階段就是利用Apriori算法進(jìn)行頻繁項挖掘，也是本文所提方法最重要的一個部分。編寫一個類繼承Jenkins插件中的一個父類，需要重寫一些方法，這里所說的頻繁項就是這些要優(yōu)先重寫的方法，設(shè)置不同的支持度和置信度參數(shù)值，會返回不同的頻繁項結(jié)果，同時給出相應(yīng)的關(guān)聯(lián)規(guī)則和對應(yīng)的置信度。用戶可以有針對性的參考這些規(guī)則，在沒有任何經(jīng)驗的情況下開始編寫Jenkins插件的第一行代碼。

3 實驗結(jié)果與分析

為評價本文方法，挖掘了從Github[16]上下載的1 523個Jenkins插件的代碼信息，為了減少挖掘時間，從1 523個插件代碼中隨機(jī)挑選了500個插件，這些代碼均采用Java語言編寫。本文試驗環(huán)境為：操作系統(tǒng)： Windows 7 64位專業(yè)版、CPU：Intel(R)Core(TM)i3-2330 M @ 2.20 GHz、內(nèi)存8 GB。

為展現(xiàn)本文所提方法的效果，列舉了一個以James為開發(fā)者的應(yīng)用案例，分析挖掘出來的頻繁項集以及關(guān)聯(lián)規(guī)則，以驗證本文提出的方法的可行性。

例1 HudsonTestCase

James想寫一個關(guān)于Hudson的測試用例，他并不知道應(yīng)該繼承哪一個類，以及從哪里入手開始寫代碼，于是他輸入了關(guān)鍵字hudson, CodeMining開始搜索之前預(yù)處理階段存儲在數(shù)據(jù)庫中的數(shù)據(jù)，返回如表1數(shù)據(jù)，代碼運行的時間為0.143 s。

表1 基于關(guān)鍵字CodeMining返回的父類列表

Count為關(guān)鍵字在所有繼承此父類的子類名中出現(xiàn)的次數(shù)，F(xiàn)requency為此關(guān)鍵字在類名分詞結(jié)果中所占比例，Score為關(guān)鍵字匹配的得分，得分最高者為最匹配的那個父類。

于是James就編寫一個類文件來繼承這個父類，在CodeMining中選擇HudsonTestCase這個父類，設(shè)置頻繁項挖掘的一些參數(shù)，例如：支持度、置信度。CodeMining就可以進(jìn)行頻繁項挖掘，這里分別將支持度設(shè)置為2、3和4，置信度都設(shè)置為0.5，挖掘出的頻繁K項集K的最大值Kmax、Kmax項集對應(yīng)的支持度、關(guān)聯(lián)規(guī)則數(shù)量以及運行時間如表2所示。

表2 置信度為0.5不同支持度下的實驗結(jié)果

如表2所示，支持度設(shè)置過低的話，會挖掘出很多關(guān)聯(lián)規(guī)則，James可有側(cè)重性的選擇其中有價值的信息來使用，另外本文實驗運行時間很短得益于預(yù)處理階段將有用的數(shù)據(jù)存儲在數(shù)據(jù)庫中。本文限于篇幅，僅分析當(dāng)支持度為4時的實驗結(jié)果。當(dāng)支持度設(shè)置為4，置信度設(shè)置為0.5時，返回的頻繁項集如圖3所示，關(guān)聯(lián)規(guī)則如圖4所示。實驗結(jié)果簡單明了，如@Before:setup在單元測試[17]里很常見，原因是為了方便演示，但對于那些不常見的關(guān)聯(lián)規(guī)則，CodeMining也可以像挖掘那些熟悉的關(guān)聯(lián)規(guī)則一樣，將其挖掘出來。

圖3 支持度為4的頻繁項集

圖4 支持度為4的關(guān)聯(lián)規(guī)則

圖3和圖4中@Override:setup表示要重寫setUp方法，@Before:setUp表示注解為@Before的setUp方法。

圖3中頻繁1項集@Override:setup在62個插件中出現(xiàn)了，出現(xiàn)次數(shù)最多，James會優(yōu)先重寫這個方法，而@Before:

setUp這個方法在21個插件中出現(xiàn)了，James已知這個方法也是要優(yōu)先重寫的方法，但并不像@Override:setup這個方法那么重要，有時也可以不重寫這個方法。圖3中2項集@Before:setUp; @Override:setup在12個插件中出現(xiàn)了，James會猜想這兩個方法應(yīng)該是存在某種關(guān)聯(lián)，即重寫了第一個方法，有較大概率要重寫第二個方法。頻繁3項集的支持度為6，說明在6個插件中這3個方法都同時出現(xiàn)了，James重寫了3項集中任意一個方法時其他兩個方法就是優(yōu)先重寫的方法。

圖4中由@Before:setup-> @Override: setup的置信度為0.571，這也驗證了由圖3得出的猜想，在重寫了@Before:setup這個方法后，是有很大概率要重寫@Override:setUp這個方法的。從圖4還可以發(fā)現(xiàn)由@Before:setUp;@Test:

testBadConfig;->@Override:setUp;置信度為1.0，由@Before:setUp;@Test: testGoodConfig;->@Override:setUp;置信度也為1.0，James重寫了@Before: setUp方法之后，只要也重寫了@Test: testBadConfig這個測試或者@Test: testGoodConfig這個測試，他就有100%的概率還要再重寫@Override: setUp這個方法。

通過James的案例分析，驗證了可以通過文中提出的CodeMining方法，根據(jù)挖掘出來的頻繁項以及關(guān)聯(lián)規(guī)則，快速的學(xué)習(xí)框架的開發(fā)，寫出軟件開發(fā)的第一行代碼。

4 結(jié)束語

本文提出了一種挖掘源碼模式的輔助開發(fā)方法，通過實驗證明，可以挖掘出代碼中的編程模式，并有效輔助新手進(jìn)行軟件開發(fā)。但本文挖掘出的是粗粒度編程模式，沒有進(jìn)一步深入到方法中去挖掘相關(guān)的編程模式，也沒有挖掘代碼中一些其他有用的信息。下一步工作是進(jìn)一步挖掘代碼方法中的具體內(nèi)容，挖掘出更細(xì)粒度的編程模式，并加入更多維度。

[1] 王少鋒,何志均,王克宏.軟件重用技術(shù)研究[J].計算機(jī)工程與設(shè)計,2000,21(5):10-14.

[2] Robillard M P,Chhetri Y B. Recommendi -ng reference API documentation [J]. Empirical Software Engineering,2015,20(6):1558-1586.

[3] Michail A.Data mining library reuse patterns in user-selected applications[C]. Hangzhou:Automated Software Engineering,14th IEEE International Conference,2000.

[4] 趙洪英,蔡樂才,李先杰.關(guān)聯(lián)規(guī)則挖掘的Apriori算法綜述[J].四川理工學(xué)院學(xué)報:自然科學(xué)版,2011,24(1):66-70.

[5] 崔貫勛,李梁,王柯柯,等.關(guān)聯(lián)規(guī)則挖掘中Apriori研究與改進(jìn)[J].計算機(jī)應(yīng)用,2010,30(11):2952-2955.

[6] 劉華婷,郭仁祥,姜浩.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)[J].計算機(jī)應(yīng)用與軟件,2009,26(1):146-149.

[7] Bruch M, Sch?fer T, Mezini M. FrUiT: IDE support for framework understanding[C]. Portland, Oregon, USA：OOPSLA Workshop on Eclipse Technology Exchange, ETX 2006.

[8] 吳信東,Vipin Kumar.數(shù)據(jù)挖掘十大算法[M].北京:清華大學(xué)出版社,2013.

[9] Jiang C, Coenen F,Zito M.Frequent sub -graph mining on edge weighted graphs[M].Berlin:Springer Berlin Heidelberg,2010.

[10] 陸麗娜,陳亞萍,魏恒義,等.挖掘關(guān)聯(lián)規(guī)則中的Apriori算法的研究[J].小型微型計算機(jī)系統(tǒng),2000,21(9):940-943.

[11] 顏躍進(jìn),李舟軍,陳火旺.基于FP-Tree有效挖掘最大頻繁項集[J].軟件學(xué)報,2005,16(2):215-222.

[12] 高宏賓,潘谷,黃義明.基于頻繁項集特性的Apriori算法的改進(jìn)[J].計算機(jī)工程與設(shè)計,2007,28(10):2273-2275.

[13] 賀玲,吳玲達(dá),蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計算機(jī)應(yīng)用研究,2007,24(1):10-13.

[14] 劉紅巖,陳劍,陳國青.數(shù)據(jù)挖掘中的數(shù)據(jù)分類算法綜述[J].清華大學(xué)學(xué)報:自然科學(xué)版,2002,42(6):727-730.

[15] 祝然威,王鵬,劉馬金.基于計數(shù)的數(shù)據(jù)流頻繁項挖掘算法[J].計算機(jī)研究與發(fā)展,2011,48(10):1803-1811.

[16] 張智,鄭卉,蔣依伶,等.使用Github實現(xiàn)高效的團(tuán)隊協(xié)作開發(fā)[J].電腦知識與技術(shù),2015,11(7):206-208.

[17] 白凱,崔冬華.基于JUnit自動化單元測試的研究[J].計算機(jī)與數(shù)字工程,2010,38(2):52-54.

Based on the Source Code Pattern Mining Software Assist Development Technology Research

FU Peng，SHEN Lili

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology, Shanghai 200093,China)

With the explosive growth of the open source community software code, software reuse is being more and more attention. Because of the complexity of the software code. To the novice that do not understand the framework, it is difficult to use the code from the open source community to develop software. As a result, using data mining technology to dig programming patterns from the existing code become a research hotspot. This paper mainly introduces the frequent items mining Apriori algorithm, and put forward the based on the source code pattern mining software assist development method. It can be based on user input keywords to intelligent matching to the super class, mining programming patterns based on the super class, give the methods that priority to override as well as the association rules. The experimental results show that the novice can use these coding suggestions, fast learning a new framework and improve the development efficiency.

source code; data mining; programming patterns; software assist development

2016- 05- 30

沈莉莉(1992-)，女，碩士研究生。研究方向：數(shù)據(jù)挖掘。

10.16180/j.cnki.issn1007-7820.2017.04.035

TP312

A

1007-7820(2017)04-140-05