折蓉蓉，張麗萍，侯 敏，閆 盛

(內(nèi)蒙古師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，呼和浩特 010022)(*通信作者電子郵箱cieczlp@imnu.edu.cn)

0 引言

近年來軟件開發(fā)環(huán)境、操作系統(tǒng)及軟件相關(guān)領(lǐng)域的不斷發(fā)展，導(dǎo)致軟件復(fù)用的規(guī)模越來越大，軟件開發(fā)的成果被越來越多的人們直接復(fù)用。為了提高軟件的開發(fā)效率，開發(fā)人員會復(fù)用大量的代碼，被復(fù)用的代碼稱為克隆代碼[1]，據(jù)統(tǒng)計(jì)一個(gè)軟件系統(tǒng)中的克隆代碼達(dá)到9%～17%，有的甚至達(dá)到50%以上[2]。

克隆代碼的大量使用導(dǎo)致了軟件復(fù)雜性的增加，僅僅檢測出克隆代碼并不能降低軟件維護(hù)成本?，F(xiàn)有研究表明，重構(gòu)與軟件的質(zhì)量(如可維護(hù)性和穩(wěn)定性)有著密切的聯(lián)系，經(jīng)過重構(gòu)的克隆代碼往往比未經(jīng)過重構(gòu)的克隆代碼具有更高的質(zhì)量，所以重構(gòu)對于軟件的進(jìn)化具有積極的意義。

重構(gòu)軟件系統(tǒng)中克隆所有代碼是不切實(shí)際的，也不是所有克隆代碼都需要重構(gòu)，雖然預(yù)測克隆重構(gòu)代碼的方法相繼提出，然而國內(nèi)外針對機(jī)器學(xué)習(xí)預(yù)測出需要重構(gòu)的克隆代碼的方法極少，因此本文將重構(gòu)作為一個(gè)機(jī)器學(xué)習(xí)問題，預(yù)測需要重構(gòu)的克隆代碼，以降低軟件的復(fù)雜性和維護(hù)成本。

1 相關(guān)工作

1.1 克隆代碼定義及分類

當(dāng)前，人們廣泛采用的克隆代碼的概念是將具有相似語法及語義特征的代碼段稱為克隆代碼[3]?；趯Υa質(zhì)量造成重要影響的是克隆代碼的大量使用，近年來代碼分析領(lǐng)域中比較活躍的分支為克隆代碼的相關(guān)研究?？寺〈a的類型從不同的角度進(jìn)行劃分，當(dāng)前進(jìn)行分類的角度主要分為兩種。一種角度是根據(jù)代碼相似度，將其分成Type- 1、Type- 2、Type- 3及Type- 4四類[4](定義如表1)；另一種角度是根據(jù)檢測粒度，將其分成文件克隆、類克隆、函數(shù)克隆、塊克隆以及語句克隆等五種類型[5]。

表1 克隆類型的定義

1.2 克隆檢測

克隆檢測是指查找源代碼中的克隆代碼，并以克隆對(Clone Pair)或克隆群(Clone Group)的形式反饋。其中，克隆對是指相互之間存在克隆關(guān)系的代碼段；克隆群是一些克隆代碼段的集合，其中任意兩個(gè)代碼段都是克隆對。目前，克隆檢測領(lǐng)域的研究已較為成熟，許多檢測方法及技術(shù)被提出，主要包括：基于文本的克隆檢測方法[6]、基于Token的克隆檢測方法[7]、基于抽象語法樹(Abstract Syntax Tree， AST)的檢測方法[8]、程序依賴圖(Program Dependence Graph， PDG)[9]、基于低級語言[10]的檢測方法、基于Metrics[11]的檢測方法等。

本團(tuán)隊(duì)在克隆檢測方面也進(jìn)行了大量研究：史慶慶等[12]使用優(yōu)化后綴數(shù)組的方法進(jìn)行克隆代碼檢測，并實(shí)現(xiàn)了一款檢測軟件源代碼中克隆群的工具——FCD(Function Clone Detector)。FCD能夠把軟件系統(tǒng)中的Type- 1和Type- 2函數(shù)克隆高效地檢測出來；張久杰等[13]實(shí)現(xiàn)了基于Token編輯距離的檢測方法，能有效檢測Type- 3克隆代碼，解決了克隆檢測中Type- 3類型克隆檢測的難題，解決了以往對克隆代碼分析的研究對象大多局限于Type- 1和Type- 2類型的問題，并為后續(xù)研究克隆代碼的演化、克隆代碼性能分析提供更加全面、準(zhǔn)確的數(shù)據(jù)來源。

1.3 克隆重構(gòu)

重構(gòu)的概念由Opdyke[14]提出，重構(gòu)就是通過改變程序代碼的內(nèi)部結(jié)構(gòu)而不改變程序代碼的外部行為來提高代碼的質(zhì)量，尤其是代碼的可擴(kuò)展性與可維護(hù)性。多年來軟件重構(gòu)作為提高代碼質(zhì)量的有效途徑，已成為軟件工程領(lǐng)域的熱點(diǎn)問題。出現(xiàn)了許多針對不同類型的克隆代碼的重構(gòu)方法和技術(shù)，主要包括：Bakota[15]采用進(jìn)化分析方法提取可重構(gòu)的克隆代碼；Rahman等[16]用度量提取可重構(gòu)的克隆代碼。Fowler[17]提出兩種重構(gòu)方法：提煉函數(shù)(Extract Method)和函數(shù)上移(Pull Up Method)，這兩種方法是重構(gòu)克隆代碼常用的技術(shù)，通常重構(gòu)克隆代碼需要結(jié)合使用這兩種方法，首先執(zhí)行“提煉函數(shù)”，然后執(zhí)行“函數(shù)上移”?？寺〈a重構(gòu)可以提高代碼的可維護(hù)性。

以Apache Ant中的一小段代碼為例來理解克隆重構(gòu)。Apache Ant的r436724中的克隆代碼重構(gòu)細(xì)節(jié)如圖1所示，開發(fā)人員在維護(hù)日志提交內(nèi)容中有如下表述：“重構(gòu)DirectoryScanner來減少重復(fù)的代碼，測試全部通過”。源代碼的更改確認(rèn)了重構(gòu)DirectoryScanner中的克隆兄弟姐妹：分散在兩個(gè)方法中的克隆兄弟姐妹被提取到一個(gè)名為processIncluded的新方法中，并且這兩個(gè)方法調(diào)用新的方法來保存程序的外部行為。這就是重構(gòu)克隆代碼的一個(gè)實(shí)例。

圖1 克隆重構(gòu)實(shí)例

1.4 決策樹

決策樹又稱判定樹，是一種運(yùn)用于分類的樹形結(jié)構(gòu)，構(gòu)造決策樹采用的是一種自上而下的遞歸方法。將一組帶有類別標(biāo)記的訓(xùn)練數(shù)據(jù)作為決策樹的輸入，一棵二叉樹或者多叉樹作為輸出，以下兩步主要是決策樹的分類過程。

第1步 構(gòu)建決策樹模型，此過程就是進(jìn)行機(jī)器學(xué)習(xí)的過程。從數(shù)據(jù)中獲取知識，使用訓(xùn)練集建立模型同時(shí)優(yōu)化。

第2步 進(jìn)行分類，使用生成的決策樹對輸入數(shù)據(jù)進(jìn)行分類。對輸入的記錄，從根節(jié)點(diǎn)依次測試記錄的屬性值，直到到達(dá)某個(gè)葉節(jié)點(diǎn)，從而找到該記錄所在的類。

尤為關(guān)鍵的是構(gòu)造一棵決策樹，構(gòu)造決策樹的過程分為三步：1)特征選擇；2)生成決策樹；3)剪枝。

具體原理如下：

InfoGain(D,A)=H(D)-H(D|A)

(1)

(2)

(3)

其中：D代表整個(gè)訓(xùn)練樣本；訓(xùn)練樣本有k類；A代表特征，A將訓(xùn)練樣本分為n類；Pi為數(shù)據(jù)集中第i個(gè)類別占樣本總數(shù)的比例，Pji為j個(gè)剪枝數(shù)目中第i個(gè)類別所占比例。

決策樹相對于其他分類器而言有如下優(yōu)點(diǎn)。

1)速度快：不僅計(jì)算量小，而且分類規(guī)則轉(zhuǎn)化較容易。

2)準(zhǔn)確性高：挖掘出的內(nèi)容不僅可以清晰地反映出哪些字段比較重要，而且分類規(guī)則精準(zhǔn)性較高、便于理解。

2 基于決策樹推薦克隆重構(gòu)的方法

本文提出的基于分類器推薦克隆代碼重構(gòu)的方法共分為5個(gè)步驟，如圖2所示。

圖2 整體工作流程

2.1 克隆檢測

如果不知道哪些代碼片段是克隆代碼、克隆代碼所在的位置，也無法識別重構(gòu)代碼，解決克隆代碼引起的問題，克隆代碼檢測是研究克隆重構(gòu)的基礎(chǔ)，因此本研究使用目前比較成熟的克隆檢測工具——NiCad進(jìn)行克隆檢測。NiCad檢測工具是由加拿大皇后大學(xué)Roy等[6]開發(fā)的克隆檢測工具，當(dāng)前最新版本為NiCad 4.0，適用于C、Java、Python等主流開發(fā)語言，能夠檢測Type- 1、Type- 2、Type- 3的克隆代碼。由于它能有效檢測Type- 3克隆代碼，解決了以往對克隆代碼分析的研究對象大多局限于Type- 1和Type- 2類型的難題，并為后續(xù)研究克隆代碼的重構(gòu)、克隆代碼性能分析提供更加全面、準(zhǔn)確的數(shù)據(jù)來源。

本研究使用subversion從版本管理器中獲取某次提交之后的結(jié)果作為一個(gè)版本的源碼，然后使用NiCad進(jìn)行克隆檢測，該工具可以檢測Java語言的Type- 1、Type- 2與Type- 3函數(shù)克隆,并具有很高的精度值和召回率。檢測結(jié)果以克隆對、克隆群和克隆函數(shù)的形式反饋出來，本研究只用克隆函數(shù)、克隆群形式的檢測結(jié)果，檢測結(jié)果存儲到XML文件中。下面以Tomcat軟件為例，介紹克隆檢測結(jié)果。圖3呈現(xiàn)了以克隆函數(shù)形式反饋出來的部分內(nèi)容檢測結(jié)果，它顯示的是一個(gè)代碼片段的文件，提供每一個(gè)代碼片段的文件路徑、起始行號、結(jié)束行號、片段源碼等信息。圖4呈現(xiàn)了以克隆群形式反饋出來的部分檢測結(jié)果，它是克隆群文件，克隆群包含的克隆片段、檢測出來的克隆群信息都包含在里面。

2.2 識別重構(gòu)的克隆代碼

近年來隨著克隆代碼檢測技術(shù)日益成熟，克隆代碼的重構(gòu)也逐漸成為了熱門，在對軟件系統(tǒng)中克隆代碼重構(gòu)之前，識別出需要重構(gòu)的集合是非常重要的。本文識別克隆代碼重構(gòu)實(shí)例具體過程分為如下3個(gè)步驟。

圖3 部分檢測結(jié)果(克隆函數(shù))

圖4 部分檢測結(jié)果(克隆群)

步驟1 通過相鄰版本間定義重構(gòu)實(shí)例?？寺≈貥?gòu)簡單來說就是代碼的更改，即定義克隆類C為由兩個(gè)或更多個(gè)克隆片段組成的集合。一個(gè)克隆類C至少有兩個(gè)克隆片段被合并，并且保留原始代碼段的外部行為，超過兩個(gè)克隆片段的克隆類C，則C被認(rèn)為是克隆重構(gòu)，如果任何兩個(gè)克隆片段被重構(gòu)，則為重構(gòu)實(shí)例。

步驟2 生成重構(gòu)候選集。本實(shí)驗(yàn)選擇了5個(gè)著名的開源系統(tǒng)，Tomcat、ArgoUML、PostgreSQL、Lucene、Apache Ant，收集了這些系統(tǒng)的所有公開版本，要在所選目標(biāo)系統(tǒng)中識別克隆重構(gòu)實(shí)例，用Demeyer等[18]開發(fā)的度量工具M(jìn)oose Metrics從源代碼中提取類、方法、屬性、計(jì)算必要的度量來生產(chǎn)重構(gòu)候選集。

步驟3 優(yōu)化重構(gòu)候選集。生成重構(gòu)候選集之后，依據(jù)以下3個(gè)條件對重構(gòu)候選集進(jìn)一步篩選和優(yōu)化：

1)相鄰版本間克隆類的兩個(gè)兄妹消失；

2)對于克隆代碼片段內(nèi)的方法，源代碼行數(shù)減少，并且至少一種方法被添加進(jìn)此方法中；

3)一個(gè)原始克隆代碼中新的源類被創(chuàng)建并作為父類。

選擇這3個(gè)條件是因?yàn)樗鼈儼怂信c克隆重構(gòu)有關(guān)的重構(gòu)模式。通過使用這種基于度量值的方法，手動(dòng)檢查克隆克隆重構(gòu)候選者，據(jù)Demeyer等[18]使用發(fā)現(xiàn)，這種方法可以檢測到適用于克隆重構(gòu)的所有Fowler重構(gòu)模式，包括“Extract Method”“Extract Superclass”“Pull-Up Method”“Replace Method with Method Object”“Template Method”等方法。

若滿足其中任意一個(gè)條件則一個(gè)克隆類C被當(dāng)作候選，重構(gòu)實(shí)例如表2所示。

表2 識別克隆重構(gòu)實(shí)例

為了構(gòu)成完整的分類器訓(xùn)練數(shù)據(jù)集合，還需要收集非克隆重構(gòu)實(shí)例。非克隆重構(gòu)實(shí)例的收集則比較簡單，只需觀察從克隆開始版本到本研究中的最后一個(gè)版本，選擇沒有任何重構(gòu)的克隆代碼(包括重命名標(biāo)識符)，則為非克隆重構(gòu)實(shí)例。

2.3 特征提取

特征提取是機(jī)器學(xué)習(xí)和模式識別領(lǐng)域常用的數(shù)據(jù)預(yù)處理方式，是訓(xùn)練機(jī)器學(xué)習(xí)模型的必要步驟，Wang[19]提出了使用克隆代碼的危害性可能與克隆代碼段的特征以及克隆內(nèi)容的特征有關(guān)，并在兩個(gè)大型工業(yè)軟件上進(jìn)行了評估。Steidl等[20]用克隆代碼段、克隆關(guān)系的特征來自動(dòng)識別克隆代碼的bugfixes，并進(jìn)行了驗(yàn)證。本團(tuán)隊(duì)王歡等[21]針對克隆代碼有害性特征數(shù)量多且不容易提取、質(zhì)量粗糙的情況，提出了一種有害性特征選取的組合模型?；谝陨涎芯康贸鯰ype- 3的克隆、克隆代碼的圈復(fù)雜度、克隆代碼段的行數(shù)、分支語句的比例等特征與克隆代碼的有害性和重構(gòu)相關(guān)，因此本文從克隆關(guān)系、克隆代碼段及克隆內(nèi)容這3個(gè)維度中提取特征，詳細(xì)特征信息如表3所示。

特征的提取是建立在克隆代碼檢測和重構(gòu)標(biāo)注的基礎(chǔ)上，通過分析克隆檢測結(jié)果可以為本文研究基礎(chǔ)性的克隆代碼數(shù)據(jù)，包括克隆代碼的數(shù)量、位置等數(shù)據(jù)?？寺∪菏遣皇荰ype- 3的克隆、克隆代碼段的Token大小這兩個(gè)特征直接從NiCad克隆檢測結(jié)果中提取，對于其他特征本文使用代碼工具SourceMonitor提取。SourceMonitor是一款可對多種語言(C++、C、C#、VB.net、Java、Visual、Basic和HTML)編寫的代碼進(jìn)行度量的工具，并且針對不同的語言，輸出不同的代碼度量值。將克隆代碼作為輸入，SourceMonitor便會輸出相應(yīng)克隆代碼的靜態(tài)特征值。圖5是SourceMonitor對部分克隆代碼進(jìn)行度量的結(jié)果。代碼行數(shù)是從SourceMonitor工具的標(biāo)簽獲取，圈復(fù)雜度是從SourceMonitor工具的標(biāo)簽獲取，注釋比例從SourceMonitor工具的<%Comments>標(biāo)簽獲取，其他特征都是從SourceMonitor工具中的標(biāo)簽獲取；但是對于特征11(一個(gè)克隆代碼段是否包含完整的控制塊)需要手動(dòng)提取。

2.4 訓(xùn)練決策樹分類器

決策樹方法在分類、預(yù)測等領(lǐng)域有著廣泛的應(yīng)用，C4.5是比較成熟的決策樹算法，C4.5算法是決策樹分類問題中必不可少的挖掘工具。之所以選擇C4.5是因?yàn)樗a(chǎn)生的預(yù)測準(zhǔn)確性不低于其他的分類方法。哈爾濱工業(yè)大學(xué)袁悅[22]使用機(jī)器多種學(xué)習(xí)的方法來預(yù)測克隆代碼的一致性維護(hù)需求模型，經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)決策樹的預(yù)測模型最佳，Wang等[23]用決策樹預(yù)測克隆代碼的質(zhì)量且取得良好的效果。受此啟發(fā)本研究選用決策樹來預(yù)測需要重構(gòu)的克隆代碼。

表3 特征選擇

構(gòu)造一棵決策樹的步驟如下。

1)數(shù)據(jù)預(yù)處理：將屬性變量處理形成決策樹的訓(xùn)練集，這里只需處理連續(xù)型的屬性變量，若沒有連續(xù)型的屬性變量則忽略。

2)計(jì)算屬性的信息增益率。

3)生成決策樹：每一個(gè)根節(jié)點(diǎn)屬性的取值對應(yīng)一個(gè)子集，對樣本子集遞歸執(zhí)行步驟2)，直到分類屬性上取值都相同時(shí)生成決策樹。

4)對新數(shù)據(jù)集進(jìn)行分類：根據(jù)構(gòu)造的決策樹，提取分類規(guī)則且進(jìn)行分類。

算法描述如下。

輸入：訓(xùn)練樣本samples，候選屬性的集合attributelist。

輸出：一棵決策樹。

創(chuàng)建節(jié)點(diǎn)N

ifsamples都在同一個(gè)類Cthen

returnN作為葉節(jié)點(diǎn)，以類C標(biāo)記

ifattribute_list為空then

returnN作為葉節(jié)點(diǎn)，標(biāo)記為samples中最普通的類

選擇attribute_list中具有最高信息增益的屬性best_attribute

標(biāo)記節(jié)點(diǎn)N為best_attribute

for eachbest_attribute中的未知值ai

由節(jié)點(diǎn)N長出一個(gè)條件為best_attribute=ai的分枝

設(shè)si是samples中best_attribute=ai的樣本的集合

ifsi為空then

加入一個(gè)樹葉，標(biāo)記為samples中最普通的類

else 加上一個(gè)由Generate_decision_tree返回的節(jié)點(diǎn)

圖5 部分克隆代碼度量結(jié)果

訓(xùn)練分類器，需要一個(gè)包含克隆重構(gòu)實(shí)例和非克隆重構(gòu)實(shí)例的樣本數(shù)據(jù)庫，然而未經(jīng)重構(gòu)的克隆實(shí)例通常比重構(gòu)實(shí)例多出幾倍，訓(xùn)練所有克隆實(shí)例將會在構(gòu)造分類器時(shí)引入對未克隆重構(gòu)的偏奇。為了解決這個(gè)問題，使用隨機(jī)欠采樣來減小未重構(gòu)克隆的大小。隨機(jī)欠采樣簡單來說就是從原始數(shù)據(jù)集中刪除數(shù)據(jù)，從而提供相同比例的數(shù)據(jù)。具體來說，本文隨機(jī)選擇一組Dmaj中的多數(shù)類實(shí)例，并從D中刪除這些樣本，計(jì)算過程如下：

|D|=|Dmin|+|Dmaj|-|E|

(4)

其中：D是數(shù)據(jù)集；Dmin表示少數(shù)類數(shù)據(jù)的集合，在本實(shí)驗(yàn)中就是克隆重構(gòu)實(shí)例；Dmaj表示多數(shù)類數(shù)據(jù)的集合，在本實(shí)驗(yàn)中就是非克隆重構(gòu)實(shí)例；E表示D上采樣過程中產(chǎn)生的任何集合。

2.5 評估分類結(jié)果

在對未知數(shù)據(jù)樣本進(jìn)行預(yù)測時(shí)，部分被正確分類，部分被錯(cuò)誤分類，因此，為了評價(jià)克隆代碼重構(gòu)預(yù)測模型，本研究選用常用的召回率、精度值、F值來評價(jià)分類器的性能，對應(yīng)的混合矩陣如表4所示。表4中：正確的正例(True Positive， TP)用TP來表示；錯(cuò)誤的反例(False Negative， FN)用FN來表示；錯(cuò)誤的正例(False Positive， FP)用FP來表示；正確的反例(True Negative， TN)用TN來表示。

表4 混合矩陣

精度值(Precision)的定義如式(5)所示、召回率(Recall)的定義如式(6)所示、F值的定義如式(7)所示：

Precision=TP/(TP+FP)

(5)

Recall=TP/(TP+FN)

(6)

F=(2*Precision*Recall)/(Precision+Recall)

(7)

其中：精度值是分類問題中常用的指標(biāo)，它反映分類器對數(shù)據(jù)集的整體分類性能；召回率度量分類器正確預(yù)測克隆重構(gòu)的比例。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)?zāi)繕?biāo)軟件

本實(shí)驗(yàn)選取5款開源軟件分別是:Tomcat 7.0、Apache Ant、ArgoUML、Lucene、PostgreSQL，基本信息如表5所示。本研究之所以選擇這些系統(tǒng)不僅僅是這些系統(tǒng)比較龐大，而且這幾個(gè)系統(tǒng)已經(jīng)通過趙玉武等[24]在克隆代碼Bugs的研究中進(jìn)行了實(shí)驗(yàn)。

表5 實(shí)驗(yàn)軟件基本信息

3.2 實(shí)驗(yàn)結(jié)果

由于位于決策樹根部附近的特征不能代表其預(yù)測能力，因此選擇不同的特征子集，并使用每個(gè)子集來訓(xùn)練一個(gè)新的分類器。本實(shí)驗(yàn)選擇三個(gè)子集的特征。這三個(gè)子集分別是克隆關(guān)系、克隆內(nèi)容以及克隆代碼段。

實(shí)驗(yàn)結(jié)果如表6所示(使用子集對克隆重構(gòu)組、非重構(gòu)組進(jìn)行分類訓(xùn)練的性能)，從表6中可以得出如下結(jié)論。

1)在5個(gè)目標(biāo)系統(tǒng)中，沒有一個(gè)特征子集的性能始終優(yōu)于其他子集。

2)和所有特征訓(xùn)練的分類器相比，克隆代碼片段的特征可以產(chǎn)生最接近的結(jié)果。如重構(gòu)組ArgoUML目標(biāo)系統(tǒng)中所有特征訓(xùn)練分類器的精度值為0.813、召回率為0.785，與此最相近的是受過克隆上下文訓(xùn)練分類器的精度值為0.798、召回率為0.779。其他目標(biāo)系統(tǒng)也是如此。

3)與克隆上下文相關(guān)的特征產(chǎn)生的結(jié)果略低于受過所有特征訓(xùn)練的分類器。如重構(gòu)組ArgoUML目標(biāo)系統(tǒng)中所有特征訓(xùn)練分類器的精度值為0.813、召回率為0.785。受過克隆上下文訓(xùn)練分類器的精度值為0.751、召回率為0.732，略低于所有特征訓(xùn)練的分類器。其他目標(biāo)系統(tǒng)也是如此。

4)通過學(xué)習(xí)克隆關(guān)系的特征，例如特征3(克隆類是否是一個(gè)Type- 3克隆)，或者特征4(克隆片段是否在同一個(gè)文件中，或者是兄妹姐妹)，分類器的性能獲得一小部分的改進(jìn)。如重構(gòu)組ArgoUML目標(biāo)系統(tǒng)中所有特征訓(xùn)練分類器的精度值為0.813、召回率為0.785，受過克隆關(guān)系訓(xùn)練分類器的精度值為0.635、召回率為0.801，略低于所有特征訓(xùn)練的分類器。其他目標(biāo)系統(tǒng)也是如此。

基于以上結(jié)論，得出克隆代碼段的特性獨(dú)立于克隆關(guān)系及克隆內(nèi)容，產(chǎn)生的結(jié)果可用于推薦重構(gòu)的克隆代碼。

表6 使用子集對不同組進(jìn)行分類訓(xùn)練的性能對比

本實(shí)驗(yàn)選取K折交叉驗(yàn)證來評估驗(yàn)證，此方法的基本思想是將輸入數(shù)據(jù)集劃分為訓(xùn)練集和測試集，因?yàn)闇y試集和訓(xùn)練集中測試集對分類器是不可見的，所以進(jìn)行交叉驗(yàn)證的對象是訓(xùn)練集輸出的結(jié)果。

第1步 將數(shù)據(jù)集D劃分為k個(gè)大小相似的互斥子集，即D=D1∩D2∩D3∩…∩Dk，每個(gè)子集之間沒有交集。

第2步 然后每次用k-1個(gè)子集的并集作為訓(xùn)練集，余下的那個(gè)作為測試集，這樣得到k組訓(xùn)練/測試集。

第3步 可以進(jìn)行k次訓(xùn)練和測試，最終返回的是這k個(gè)結(jié)果的均值。

第4步 可以隨機(jī)使用不同的劃分次數(shù)。

本實(shí)驗(yàn)選取K=10，即K折交叉驗(yàn)證來評估分類器預(yù)測模型，通過利用大量數(shù)據(jù)集以及使用不同技術(shù)進(jìn)行大量實(shí)驗(yàn)發(fā)現(xiàn)10折獲得的誤差最小，因此本實(shí)驗(yàn)將數(shù)據(jù)集分為10份。驗(yàn)證結(jié)果如表7所示，分別顯示了重構(gòu)組和非重構(gòu)組的精度值、召回度、F度量。

表7 對不同組的測試結(jié)果對比

從表7的重構(gòu)組對比可以得出，重構(gòu)組10倍交叉驗(yàn)證的精度值從78.3%提高到了87.9%，提高了9.6個(gè)百分點(diǎn)；召回率從74.7%提高到了91.3%，提高了16.6個(gè)百分點(diǎn)；F值從76.5%提高到了89.6%，提高了13.1個(gè)百分點(diǎn)。從表7的非重構(gòu)組對比中可以得出，非重構(gòu)組10倍交叉驗(yàn)證的精度值從77.3%提高到了90.3%，提高了13個(gè)百分點(diǎn)；召回率從81.2%提高到了87.1%，提高了5.9個(gè)百分點(diǎn)；F值從78.9%提高到了88.9%，提高了10個(gè)百分點(diǎn)：因此得出本文所構(gòu)造的分類器比隨機(jī)選擇執(zhí)行來的效果更佳。

3.3 同類實(shí)驗(yàn)對比分析

當(dāng)前國內(nèi)外使用機(jī)器學(xué)習(xí)的方法預(yù)測出需要重構(gòu)的克隆代碼方法較少，本團(tuán)隊(duì)的劉冬瑞等[25]也曾使用機(jī)器學(xué)習(xí)方法預(yù)測需重構(gòu)的克隆代碼，然而其度量值的選取是根據(jù)ISO軟件質(zhì)量標(biāo)準(zhǔn)選取的，不能很好地體現(xiàn)需重構(gòu)克隆代碼的特征，而本研究度量值的選取是從重構(gòu)實(shí)例中提取的，相對而言，可信度更好，可行性更強(qiáng)。使用機(jī)器學(xué)習(xí)方法預(yù)測出需要重構(gòu)的克隆代碼具有代表性的是文獻(xiàn)[26]所提出的方法，鑒于文獻(xiàn)[26]直接從公司收集的克隆代碼，而本研究使用NiCad來檢測克隆代碼，同時(shí)本研究與文獻(xiàn)[26]提取的特征也不完全一致，因此僅對推薦克隆重構(gòu)做對比實(shí)驗(yàn)。其中本文研究與文獻(xiàn)[26]所使用的項(xiàng)目均為Java項(xiàng)目，實(shí)驗(yàn)平臺同為操作系統(tǒng)：Ubuntu14.04 64位、8 GB內(nèi)存、2核CPU。版本信息如表8所示。

表8 推薦克隆重構(gòu)對比實(shí)驗(yàn)軟件信息

通過對比實(shí)驗(yàn)，結(jié)果如表9所示。

表9 推薦克隆重構(gòu)同類實(shí)驗(yàn)結(jié)果對比

從推薦克隆重構(gòu)結(jié)果中分析軟件ArgoUML的精度值、召回率和F值,與文獻(xiàn)[26]的方法相比，本文方法的精度值提高了10個(gè)百分點(diǎn)、召回率提高了10個(gè)百分點(diǎn)、F值提高了9.8個(gè)百分點(diǎn)。從推薦克隆重構(gòu)結(jié)果中分析軟件Apache Ant的精度值、召回率和F值,與文獻(xiàn)[26]的方法相比，本文方法的精度值提高了10個(gè)百分點(diǎn)、召回率提高了6個(gè)百分點(diǎn)、F值提高了3.3個(gè)百分點(diǎn)。從推薦克隆重構(gòu)結(jié)果中分析軟件Lucene的精度值、召回率和F值,與文獻(xiàn)[26]的方法相比，本文方法的精度值提高了4.5個(gè)百分點(diǎn)、召回率提高了9.6個(gè)百分點(diǎn)、F值提高了2.4個(gè)百分點(diǎn)。綜上本文推薦克隆代碼重構(gòu)方法的召回率、精度值、F值均高于文獻(xiàn)[26]方法。

4 結(jié)語

針對克隆代碼的大量使用會導(dǎo)致長期軟件維護(hù)問題甚至引入錯(cuò)誤的問題，本文提出了一種基于決策樹的分類器來推薦克隆進(jìn)行重構(gòu)的方法，通過Nicad檢測出源代碼中的克隆代碼，使用基于度量值的方法將重構(gòu)實(shí)例標(biāo)注出來，同時(shí)使用SourceMonitor提取出特征并構(gòu)建樣本數(shù)據(jù)集。最后對600多個(gè)克隆實(shí)例使用10折交叉來驗(yàn)證，發(fā)現(xiàn)本文提出的基于決策樹的分類器來推薦克隆重構(gòu)方法的精確度、召回率及F值都能達(dá)到80%以上，驗(yàn)證了本文方法的有效性。本研究可以為克隆重構(gòu)提供更好的資源分配，從而改進(jìn)克隆管理。

本文的研究內(nèi)容與實(shí)驗(yàn)仍然存在一些不足之處，例如目前只能推薦用Java開發(fā)項(xiàng)目的克隆重構(gòu)、推薦克隆重構(gòu)精度有待提高，在后續(xù)研究中將繼續(xù)改進(jìn)，嘗試使用深度學(xué)習(xí)、半監(jiān)督學(xué)習(xí)來推薦克隆重構(gòu)。