基于改進的C4.5算法的代碼異味檢測方法

王 帆，吳海濤，高建華

(上海師范大學(xué) 信息與機電工程學(xué)院，上海 200234)

0 引 言

在軟件生命周期階段，代碼異味導(dǎo)致軟件質(zhì)量逐漸衰退，降低軟件理解性和維護性[1]。代碼異味檢測已經(jīng)成為發(fā)現(xiàn)軟件源碼或設(shè)計問題的方法，過去幾十年中，大量研究者研究出不同的代碼異味檢測技術(shù)。Baydaa等[2]在基于相似性度量基礎(chǔ)上提出兩種新的度量檢測Refused Bequest代碼異味。Palomba等[3]提出一種“HIST”檢測技術(shù)，通過挖掘系統(tǒng)版本變更歷史來檢測代碼異味，解決單個版本容易丟失重要信息的缺點。近些年來，越來越多的研究者使用機器學(xué)習(xí)方法檢測代碼異味。Wang等[4]使用代碼變更信息來提升代碼異味數(shù)據(jù)集中的標(biāo)簽質(zhì)量，得到更可靠的訓(xùn)練集，提高代碼異味檢測準(zhǔn)確率。Amorim等[5]將C5.0算法和遺傳算法相結(jié)合進行代碼異味檢測。Fontana等[6]使用16種機器學(xué)習(xí)算法對4種代碼異味進行檢測，其目的是評估哪種機器學(xué)習(xí)算法在檢測代碼異味上準(zhǔn)確率更高。

為了提高代碼異味檢測精確度并使開發(fā)人員便于理解代碼異味檢測過程，提高開發(fā)人員識別代碼異味的信心，本文使用機器學(xué)習(xí)中的C4.5算法對其進行檢測。在屬性選擇階段，本文提出使用ReliefF算法計算條件屬性和目標(biāo)屬性相關(guān)性，使用互信息計算條件屬性間的冗余度，選擇出相關(guān)性大而冗余度小的條件屬性集，通過劃分子集并依據(jù)機器學(xué)習(xí)算法求得F值最大的條件屬性子集，減少生成決策樹的計算開銷。同時提出在C4.5算法中加入對稱不確定性(SU)，選擇信息增益率高且與條件屬性間相關(guān)度低的條件屬性作為分裂屬性，建立新的算法模型。對比實驗結(jié)果得出，該模型在檢測代碼異味的精確度和召回率方面均有所提高。

1 背 景

1.1 代碼異味

代碼異味是軟件結(jié)構(gòu)中的一種設(shè)計缺陷，阻礙代碼理解，影響軟件質(zhì)量和維護。代碼異味在軟件版本中生存周期長[7]，研究者給出22種代碼異味的定義，并列出特定的重構(gòu)方法來分別移除每種代碼異味。但是研究者只是在單一平面上給出22種代碼異味的定義，并沒有進一步對其進行分類。文獻[8]根據(jù)每種代碼異味的特點將Fow-ler定義的代碼異味分為7種類別，以便更好理解代碼異味，并認(rèn)識到代碼異味之間的關(guān)系，表1列出代碼異味的分類類別。

表1 代碼異味分類

1.2 C4.5算法

C4.5算法是決策樹算法中的一種算法，可以用于解決分類和回歸問題，本文用于對代碼異味進行分類。

假設(shè)D是一組帶有目標(biāo)屬性的數(shù)據(jù)集，|D|為數(shù)據(jù)集的樣本總數(shù)。本文涉及二分類，即目標(biāo)屬性C有兩個不同的取值{P,N}，|P|, |N|分別為D中目標(biāo)屬性值為P,N的樣本總數(shù)，這里|P|+|N|=|D|。對D中的樣本分類所需的信息熵為

(1)

假定選擇條件屬性A劃分?jǐn)?shù)據(jù)集D中樣本,若A有m種不同的取值{a1,a2,…,ai,…,am},則屬性A按照m種取值將D劃分為m個子集{D1,D2,…,Di,…,Dm}, |Di|為D中屬性A取值為ai的子集Di的樣本總數(shù)。屬性A劃分?jǐn)?shù)據(jù)集D的信息熵為

(2)

通過條件屬性A劃分后的樣本集的信息增益為

InfoGain(D,A)=info(D)-infoA(D)

(3)

條件屬性A對數(shù)據(jù)集D的分裂信息為

(4)

條件屬性A對數(shù)據(jù)集D的信息增益率為

(5)

C4.5算法選擇信息增益率大的條件屬性，即能夠最大減少目標(biāo)屬性不確定程度的屬性，作為當(dāng)前節(jié)點的分裂屬性。

2 代碼異味檢測方法

本文研究一種基于改進的C4.5算法的代碼異味檢測技術(shù)，提出增加條件屬性間的相關(guān)度，更新信息增益率的方法，并在屬性選擇過程中，提出將ReliefF算法和互信息結(jié)合，選擇出最優(yōu)條件屬性集。圖1總結(jié)了本文代碼異味檢測技術(shù)的主要過程。

圖1 代碼異味檢測過程

2.1 RMIO屬性選擇算法

屬性選擇是數(shù)據(jù)挖掘數(shù)據(jù)預(yù)處理中的重要和常用技術(shù)之一[9]，在有限的樣本數(shù)據(jù)中，冗余的、不相關(guān)的條件屬性只會使分類器計算開銷大并且分類性能差。本文每種代碼異味有61種軟件度量即條件屬性，并不是每種條件屬性對于檢測代碼異味都是相關(guān)的，通過屬性選擇可以刪除冗余的無關(guān)的條件屬性，提高分類器效率。

ReliefF算法由Kononenko在Kira等的研究成果基礎(chǔ)上提出，用于解決多類問題[10]，是一種屬性權(quán)重算法。ReliefF算法的主要思想是從訓(xùn)練集中隨機選擇一個樣本S，依次從與S相同類別和不同類別的訓(xùn)練集中選擇M個最近鄰樣本，然后根據(jù)權(quán)重公式計算條件屬性的權(quán)重值并更新排名。上述過程不斷重復(fù)，直到每個條件屬性與目標(biāo)屬性的權(quán)重都被計算，最終得到按照權(quán)重降序的條件屬性排名。權(quán)重越大，代表該條件屬性對分類作用越大，即該條件屬性和目標(biāo)屬性相關(guān)度越大，反之，表示該條件屬性對分類作用越小。通過設(shè)定閾值選擇相關(guān)度大的條件屬性子集，剔除無效、不相關(guān)的條件屬性。

雖然ReliefF算法可以對屬性進行選擇，但是不能解決屬性冗余的缺點，即得到的屬性子集中仍然存在冗余項?？梢酝ㄟ^互信息(mutual information)[11]計算條件屬性間的冗余度，也表示兩個條件屬性間的依賴程度?；バ畔⒌挠嬎愎綖?/p>

(6)

其中，P(x,y)是X和Y的聯(lián)合概率分布函數(shù)，而P(x)和P(y)分別是X和Y的邊緣概率分布函數(shù)。互信息度量的是兩個條件屬性間，一個條件屬性對另一個不確定減少的程度，依賴性越強，I(X;Y)的值越大。

通過ReliefF算法計算條件屬性和目標(biāo)屬性間的相關(guān)度，使用互信息計算條件屬性間的冗余度，選擇出與目標(biāo)屬性相關(guān)度大而與其它條件屬性冗余度小的條件屬性，所以把該算法稱為RMIO屬性選擇算法，偽代碼如算法1所示。

算法1：RMIO屬性選擇算法

輸入：數(shù)據(jù)集D，包含條件屬性集X

輸出：最優(yōu)條件屬性集S

(1)For X中的每個條件屬性xi

(2)使用ReliefF算法計算xi和目標(biāo)屬性C之間的相關(guān)性W(xi,C)

(3)End For

(4)選擇相關(guān)度最大的條件屬性x=argmaxW(xi,C),其中xi∈X

(5)S=S∩x

(6)Fori=1 To |X|-|S| Do

(7)從X-S中選擇相關(guān)性最大冗余度最小的條件屬性

(8)S=S∩x

(9)End For

(10)將S中條件屬性劃分成n份,S1…Sn

(11)Fori=1 TonDo

(12)利用C4.5算法選出F值最大的條件屬性集

S=argmax(C4.5(Si))

(13)End For

(14)Return S

2.2 SU_C4.5算法

數(shù)據(jù)集合中的條件屬性并非都對模型的分類包含相同的期望信息，有些條件屬性對分類起到一定的正作用，有些則相反。例如對Long Method代碼異味進行分類，條件屬性“LOC”(代碼量)包含更多的期望信息，對其分類有更多作用，而條件屬性“DIT”(類的繼承深度)只包含少量期望信息。同樣，利用C4.5算法構(gòu)造決策樹時，在數(shù)據(jù)集合中先選擇一個條件屬性作為分裂屬性，剩下的條件屬性集中，有的條件屬性對分裂屬性影響較大，有的則相反。例如天氣的兩個條件屬性溫度和季節(jié)，季節(jié)的變化會影響溫度的高低，這兩個條件屬性將有一定的影響，具有一定的關(guān)聯(lián)關(guān)系。

本文認(rèn)為任意兩個屬性都有一定的關(guān)聯(lián)關(guān)系，并且定義這種關(guān)聯(lián)關(guān)系為相關(guān)度。C4.5算法在構(gòu)造決策樹時，只考慮條件屬性與目標(biāo)屬性的相關(guān)度，忽略條件屬性間的相關(guān)度。改進的C4.5算法通過計算對稱不確定性來確定兩個條件屬性間的相關(guān)度。

對稱不確定性(SU)[12]常用來判斷條件屬性與目標(biāo)屬性、條件屬性間的相關(guān)度。SU的公式可參考第1章的式(1)～式(3)，條件屬性X和條件屬性Y的相關(guān)度公式如下

(7)

SU(X,Y)取值范圍為[0,1]，當(dāng)SU(X,Y)=0時，表示X與Y為兩個相互獨立的條件屬性，當(dāng)SU(X,Y)=1時，表示X與Y為兩個完全相關(guān)的條件屬性。則條件屬性A與其它所有條件屬性的平均相關(guān)度公式為

(8)

式(8)中E為不包含條件屬性A的屬性子集，|E|為集合E的屬性總數(shù)。

C4.5算法構(gòu)造決策樹選擇分裂屬性時需要考慮該條件屬性與目標(biāo)屬性有最大相關(guān)度，同時在該條件屬性與其它條件屬性間需要有最小相關(guān)度，即該條件屬性與其它條件屬性有最小的平均相關(guān)度。改進后的算法公式如式(9)所示

(9)

如果條件屬性A與其它條件屬性的相關(guān)度越小，平均相關(guān)度就越小，信息增益率就越大。本文將對稱不確定性(SU)加入C4.5算法中，更新信息增益率的計算，所以把該改進算法稱為SU_C4.5算法，偽代碼如算法2所示。

算法2：SU_C4.5算法

輸入：數(shù)據(jù)集D(有n個屬性，其中n-1個是條件屬性，第n個是目標(biāo)屬性)

輸出：一棵決策樹

(1)創(chuàng)建根節(jié)點N

(2)If 所有樣本都屬于同一類別C，then

(3)Return N為葉子結(jié)點，標(biāo)記為類C

(4)For D中的每個條件屬性A

(5) 計算條件屬性間的相關(guān)度和信息增益率

(6)End for

(7)選擇使GainRatio(D,A)(信息增益率)最大的條件屬性作為分裂屬性

(8)將數(shù)據(jù)集D按照選擇的分裂屬性進行劃分

(9)對于分裂后的每部分?jǐn)?shù)據(jù)集，循環(huán)執(zhí)行以上算法過程

2.3 算法復(fù)雜度分析

在傳統(tǒng)的C4.5算法中，計算信息增益率的時間復(fù)雜度是O(m*n),其中m是屬性的個數(shù)，n是樣本的個數(shù)[13]。在SU_C4.5算法中，計算信息增益率之前，需要先計算條件屬性間的相關(guān)度，需要掃描為整個區(qū)間去計算每個條件屬性間的相關(guān)度，其時間復(fù)雜度為O(m*n)。所以在使用SU_C4.5算法計算信息增益率最壞情況下的時間復(fù)雜度仍然為O(m*n)。

3 實 驗

為了驗證本文提出的SU_C4.5算法的有效性，在4個開源軟件Eclipse 3.3.1,Mylyn 3.1.1,ArgoUML 0.26和Rhino 1.6上進行了實證性研究。本實驗主要關(guān)注以下3個問題：

Q1: C4.5算法在屬性選擇后的數(shù)據(jù)集上的分類準(zhǔn)確率是否有提高？

Q2: SU_C4.5算法相對于傳統(tǒng)C4.5算法的分類準(zhǔn)確率是否有提高？

Q3: SU_C4.5算法相對于其它機器學(xué)習(xí)算法的分類準(zhǔn)確率是否有提高？

3.1 實驗數(shù)據(jù)集

實驗中使用的數(shù)據(jù)集來自于Lucas Amorim等[6]的論文中的數(shù)據(jù)集，數(shù)據(jù)集D={(Ni,Ai,Ci)|i=1,2,3,…,n}， Ni表示代碼類實體的ID，Ai表示代碼實體的屬性(本文指度量，如LOC、WMC等)，Ci表示該實體是否是代碼異味。數(shù)據(jù)集D來自4個java開源軟件Eclipse 3.3.1、Mylyn 3.1.1、ArgoUML 0.26 和Rhino 1.6，總共有7952個樣本，61個條件屬性，9種代碼異味。本文實驗采用十折交叉驗證來測試C4.5算法的準(zhǔn)確性。

本文選擇9種代碼異味，Antisingleton、Blob、Class Data Should Be Private、Complex Class、Large Class、Long Method、Long Parameter List、Message Chains和 Swiss Army Knife。對于這9種代碼異味，在文獻[14]中有詳細(xì)的定義。

(1)Antisingleton(AS)：該類的對象只有一個實例，承擔(dān)很多責(zé)任，在一定程度上違背“單一職責(zé)原則”。

(2)Blob(Bb)：系統(tǒng)中類承擔(dān)很多的責(zé)任，有很多屬性、操作，并且依賴數(shù)據(jù)類。

(3)Class Data Should Be Private(CP)：暴露字段的類，違反封裝原則。

(4)Complex Class(CC)：類中至少包含一個大而復(fù)雜的方法，可以用圈復(fù)雜度和代碼行數(shù)度量。

(5)Large Class(LC)：類中至少包含一個大的方法。

(6)Long Method(LM)：類中有過長方法。

(7)Long Parameter List(LPL)：類中至少包含一個方法，該方法相對系統(tǒng)中每個方法的平均參數(shù)數(shù)量的長參數(shù)列表。

(8)Message Chains(MC)：一個使用長鏈方法調(diào)用來實現(xiàn)(至少)其功能之一的類。

(9)Swiss Army Knife(SK)：類中某方法可以分為多種方法的分離集，從而提供許多不同的不相關(guān)的功能。

3.2 模型評價指標(biāo)

本文使用信息檢索中最基本指標(biāo)召回率和精確度來評估模型的好壞，其中召回率和精確度的計算方法如下

(10)

(11)

這里TP(true positive)指正確檢測出的代碼異味數(shù)，F(xiàn)P(false positive)指將非代碼異味檢測為代碼異味的數(shù)量，F(xiàn)N(false negative)指將代碼異味檢測為非代碼異味的數(shù)量。由于精確度和召回率是兩個值，無法根據(jù)兩個值來比較模型的好壞，需要F值來綜合精確度和召回率，計算方法如下

(12)

3.3 實驗設(shè)計

實驗環(huán)境如下：操作系統(tǒng)是windows 10,處理器是inter(R) Core(TM)i5-8250U @1.6 GHz,內(nèi)存是8 GB，實驗是在Weka3.8和eclipse中完成,開發(fā)語言是java。

實驗一：本文每種代碼異味數(shù)據(jù)集的樣本總數(shù)和條件屬性總數(shù)見表2。使用RMIO算法對9種代碼異味數(shù)據(jù)集進行屬性選擇。RMIO算法最后一步之前會給出按照值大小的一份條件屬性排序，此處的值代表條件屬性的相關(guān)度及冗余度，值最大即相關(guān)度最大且冗余度最小的條件屬性排在首位，值最小即相關(guān)度最低且冗余度最低的排在末尾。每種代碼異味數(shù)據(jù)集的條件屬性都有61種，為了得到更優(yōu)的條件屬性子集，本文首先將61種條件屬性按照排序結(jié)果分成6份，第1份包含前10個條件屬性，第2份包含前20個條件屬性，依次類推，第5份包含前50個屬性，第6份包含所有屬性。使用C4.5算法在不同數(shù)量的條件屬性的代碼異味數(shù)據(jù)集上進行分類，F(xiàn)值最大的條件屬性集再依次左右±1，2，3個條件屬性，再使用C4.5算法在不同的數(shù)據(jù)集上進行分類，此時F值最大的條件屬性集為最優(yōu)條件屬性集。

表2 代碼異味數(shù)據(jù)集樣本總數(shù)和條件屬性總數(shù)

實驗二：分別使用SU_C4.5算法和傳統(tǒng)C4.5算法在RMIO屬性選擇后的9種代碼異味數(shù)據(jù)集上進行實驗。通過十折交叉驗證法計算代碼異味分類準(zhǔn)確率，最后比較兩個算法的精確度、召回率及F值。

實驗三：分別使用SU_C4.5算法和JRip算法及樸素貝葉斯算法在RMIO屬性選擇后的9種代碼異味數(shù)據(jù)集上進行實驗。通過十折交叉驗證法計算代碼異味分類準(zhǔn)確率，最后比較SU_C4.5算法和JRip算法及樸素貝葉斯算法的精確度、召回率及F值。

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

通過上述3組實驗的設(shè)計，得到3組實驗結(jié)果，根據(jù)實驗結(jié)果，逐一回答前文提到的Q1-Q3問題。

Q1：對9種代碼異味數(shù)據(jù)集使用RMIO算法進行屬性選擇，使用C4.5算法做為基準(zhǔn)分類算法，得到最優(yōu)的條件屬性子集，并與選擇之前的條件屬性集進行比較，得到的結(jié)果見表3。其中“Δ”表示使用RMIO算法得到的條件屬性子集和未進行選擇的條件屬性集構(gòu)造的模型比較，“+”表示使用RMIO算法進行屬性選擇后構(gòu)造的模型結(jié)果更好，“-”表示不進行屬性選擇的條件屬性集構(gòu)造的模型結(jié)果更好。從表3中可以看出Message Chains數(shù)據(jù)集中的條件屬性總數(shù)減到10，Blob和CDSBP數(shù)據(jù)集的條件屬性總數(shù)減得少些，減到30。從表3能夠看出，C4.5算法在使用RIMO算法進行屬性選擇的數(shù)據(jù)集上構(gòu)造的模型的分類準(zhǔn)確率有明顯提高，其中分類精確度最高提高5.9%，召回率提高3.7%，F(xiàn)值提高4.1%。通過圖2能夠直觀看出，C4.5算法在RIMO屬性選擇后的數(shù)據(jù)集上的分類F值有所提高，結(jié)果表明在預(yù)處理階段對數(shù)據(jù)集進行RMIO屬性選擇能夠提高分類器性能。

表3 RMIO算法與未屬性選擇的比較結(jié)果

圖2 屬性選擇前后F值對比

Q2：根據(jù)表4的實驗結(jié)果，可以看出SU_C4.5算法和傳統(tǒng)C4.5算法相比，代碼異味分類準(zhǔn)確率有明顯提升，其中分類精確度最高提高4.9%，召回率最高提高6.8%，F(xiàn)值最高提高4.7%，雖然Message Chains異味的召回率和F值有所下降，但是平均各指標(biāo)的值都有所提高。從圖4可以看出傳統(tǒng)C4.5算法檢測代碼異味時，Blob的F值近似50%，而其它代碼異味的F值都在68.5%以上，其中Long Parameter List的F值為97.4%。這是因為代碼異味沒有統(tǒng)一正式的定義，用來作為條件屬性的度量值也不一樣，使用現(xiàn)有的度量值并不適合用來檢測Blob異味。表4和圖3結(jié)果表明，SU_C4.5算法在構(gòu)造決策樹時，將條件屬性間的相關(guān)度考慮進來，能夠有效提高分類準(zhǔn)確率。

表4 SU_C4.5算法與C4.5算法的比較結(jié)果

圖3 C4.5算法改進前后F值對比

Q3：根據(jù)表5和表6的實驗結(jié)果，可以看出SU_C4.5算法同JRip算法和樸素貝葉斯算法相比，代碼異味分類準(zhǔn)確率均有所提高。同JRip算法相比，SU_C4.5算法分類精確度最高7.7%，召回率最高提高16.6%，F(xiàn)值最高提高11%；同樸素貝葉斯算法相比，SU_C4.5算法分類精確度最高62.5%，召回率最高提高63.1%，F(xiàn)值最高提高58.8%。產(chǎn)生差異的原因在Fontana等[6]論文中指出，在代碼異味檢測中，C4.5算法和隨機森林算法分類準(zhǔn)確率最高，其次是JRip算法，而樸素貝葉斯算法相比于前面幾種算法分類準(zhǔn)確率要低。

表5 SU_C4.5算法與JRip算法的比較結(jié)果

表6 SU_C4.5算法與樸素貝葉斯算法的比較結(jié)果

4 結(jié)束語

本文針對傳統(tǒng)C4.5算法未考慮條件屬性間相關(guān)度提出一種改進方法，將對稱不確定性(SU)加入C4.5算法中，選擇信息增益率高且與條件屬性間相關(guān)度低的條件屬性作為分裂屬性。并且在數(shù)據(jù)預(yù)處理階段，使用ReliefF算法和互信息對條件屬性進行選擇，得到最優(yōu)條件屬性子集。本文在9種代碼異味數(shù)據(jù)集上進行實驗，實驗結(jié)果表明，SU_C4.5算法以及RMIO屬性選擇算法有更好的精確度、召回率以及F值。本文介紹了9種代碼異味的檢測，后續(xù)也會對更多類型的代碼異味進行檢測。