王 帆,吳海濤,高建華
(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)
在軟件生命周期階段,代碼異味導(dǎo)致軟件質(zhì)量逐漸衰退,降低軟件理解性和維護(hù)性[1]。代碼異味檢測(cè)已經(jīng)成為發(fā)現(xiàn)軟件源碼或設(shè)計(jì)問題的方法,過去幾十年中,大量研究者研究出不同的代碼異味檢測(cè)技術(shù)。Baydaa等[2]在基于相似性度量基礎(chǔ)上提出兩種新的度量檢測(cè)Refused Bequest代碼異味。Palomba等[3]提出一種“HIST”檢測(cè)技術(shù),通過挖掘系統(tǒng)版本變更歷史來檢測(cè)代碼異味,解決單個(gè)版本容易丟失重要信息的缺點(diǎn)。近些年來,越來越多的研究者使用機(jī)器學(xué)習(xí)方法檢測(cè)代碼異味。Wang等[4]使用代碼變更信息來提升代碼異味數(shù)據(jù)集中的標(biāo)簽質(zhì)量,得到更可靠的訓(xùn)練集,提高代碼異味檢測(cè)準(zhǔn)確率。Amorim等[5]將C5.0算法和遺傳算法相結(jié)合進(jìn)行代碼異味檢測(cè)。Fontana等[6]使用16種機(jī)器學(xué)習(xí)算法對(duì)4種代碼異味進(jìn)行檢測(cè),其目的是評(píng)估哪種機(jī)器學(xué)習(xí)算法在檢測(cè)代碼異味上準(zhǔn)確率更高。
為了提高代碼異味檢測(cè)精確度并使開發(fā)人員便于理解代碼異味檢測(cè)過程,提高開發(fā)人員識(shí)別代碼異味的信心,本文使用機(jī)器學(xué)習(xí)中的C4.5算法對(duì)其進(jìn)行檢測(cè)。在屬性選擇階段,本文提出使用ReliefF算法計(jì)算條件屬性和目標(biāo)屬性相關(guān)性,使用互信息計(jì)算條件屬性間的冗余度,選擇出相關(guān)性大而冗余度小的條件屬性集,通過劃分子集并依據(jù)機(jī)器學(xué)習(xí)算法求得F值最大的條件屬性子集,減少生成決策樹的計(jì)算開銷。同時(shí)提出在C4.5算法中加入對(duì)稱不確定性(SU),選擇信息增益率高且與條件屬性間相關(guān)度低的條件屬性作為分裂屬性,建立新的算法模型。對(duì)比實(shí)驗(yàn)結(jié)果得出,該模型在檢測(cè)代碼異味的精確度和召回率方面均有所提高。
代碼異味是軟件結(jié)構(gòu)中的一種設(shè)計(jì)缺陷,阻礙代碼理解,影響軟件質(zhì)量和維護(hù)。代碼異味在軟件版本中生存周期長(zhǎng)[7],研究者給出22種代碼異味的定義,并列出特定的重構(gòu)方法來分別移除每種代碼異味。但是研究者只是在單一平面上給出22種代碼異味的定義,并沒有進(jìn)一步對(duì)其進(jìn)行分類。文獻(xiàn)[8]根據(jù)每種代碼異味的特點(diǎn)將Fow-ler定義的代碼異味分為7種類別,以便更好理解代碼異味,并認(rèn)識(shí)到代碼異味之間的關(guān)系,表1列出代碼異味的分類類別。
表1 代碼異味分類
C4.5算法是決策樹算法中的一種算法,可以用于解決分類和回歸問題,本文用于對(duì)代碼異味進(jìn)行分類。
假設(shè)D是一組帶有目標(biāo)屬性的數(shù)據(jù)集,|D|為數(shù)據(jù)集的樣本總數(shù)。本文涉及二分類,即目標(biāo)屬性C有兩個(gè)不同的取值{P,N},|P|, |N|分別為D中目標(biāo)屬性值為P,N的樣本總數(shù),這里|P|+|N|=|D|。對(duì)D中的樣本分類所需的信息熵為
(1)
假定選擇條件屬性A劃分?jǐn)?shù)據(jù)集D中樣本,若A有m種不同的取值{a1,a2,…,ai,…,am},則屬性A按照m種取值將D劃分為m個(gè)子集{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對(duì)數(shù)據(jù)集D的分裂信息為
(4)
條件屬性A對(duì)數(shù)據(jù)集D的信息增益率為
(5)
C4.5算法選擇信息增益率大的條件屬性,即能夠最大減少目標(biāo)屬性不確定程度的屬性,作為當(dāng)前節(jié)點(diǎn)的分裂屬性。
本文研究一種基于改進(jìn)的C4.5算法的代碼異味檢測(cè)技術(shù),提出增加條件屬性間的相關(guān)度,更新信息增益率的方法,并在屬性選擇過程中,提出將ReliefF算法和互信息結(jié)合,選擇出最優(yōu)條件屬性集。圖1總結(jié)了本文代碼異味檢測(cè)技術(shù)的主要過程。
圖1 代碼異味檢測(cè)過程
屬性選擇是數(shù)據(jù)挖掘數(shù)據(jù)預(yù)處理中的重要和常用技術(shù)之一[9],在有限的樣本數(shù)據(jù)中,冗余的、不相關(guān)的條件屬性只會(huì)使分類器計(jì)算開銷大并且分類性能差。本文每種代碼異味有61種軟件度量即條件屬性,并不是每種條件屬性對(duì)于檢測(cè)代碼異味都是相關(guān)的,通過屬性選擇可以刪除冗余的無關(guān)的條件屬性,提高分類器效率。
ReliefF算法由Kononenko在Kira等的研究成果基礎(chǔ)上提出,用于解決多類問題[10],是一種屬性權(quán)重算法。ReliefF算法的主要思想是從訓(xùn)練集中隨機(jī)選擇一個(gè)樣本S,依次從與S相同類別和不同類別的訓(xùn)練集中選擇M個(gè)最近鄰樣本,然后根據(jù)權(quán)重公式計(jì)算條件屬性的權(quán)重值并更新排名。上述過程不斷重復(fù),直到每個(gè)條件屬性與目標(biāo)屬性的權(quán)重都被計(jì)算,最終得到按照權(quán)重降序的條件屬性排名。權(quán)重越大,代表該條件屬性對(duì)分類作用越大,即該條件屬性和目標(biāo)屬性相關(guān)度越大,反之,表示該條件屬性對(duì)分類作用越小。通過設(shè)定閾值選擇相關(guān)度大的條件屬性子集,剔除無效、不相關(guān)的條件屬性。
雖然ReliefF算法可以對(duì)屬性進(jìn)行選擇,但是不能解決屬性冗余的缺點(diǎn),即得到的屬性子集中仍然存在冗余項(xiàng)??梢酝ㄟ^互信息(mutual information)[11]計(jì)算條件屬性間的冗余度,也表示兩個(gè)條件屬性間的依賴程度。互信息的計(jì)算公式為
(6)
其中,P(x,y)是X和Y的聯(lián)合概率分布函數(shù),而P(x)和P(y)分別是X和Y的邊緣概率分布函數(shù)?;バ畔⒍攘康氖莾蓚€(gè)條件屬性間,一個(gè)條件屬性對(duì)另一個(gè)不確定減少的程度,依賴性越強(qiáng),I(X;Y)的值越大。
通過ReliefF算法計(jì)算條件屬性和目標(biāo)屬性間的相關(guān)度,使用互信息計(jì)算條件屬性間的冗余度,選擇出與目標(biāo)屬性相關(guān)度大而與其它條件屬性冗余度小的條件屬性,所以把該算法稱為RMIO屬性選擇算法,偽代碼如算法1所示。
算法1:RMIO屬性選擇算法
輸入:數(shù)據(jù)集D,包含條件屬性集X
輸出:最優(yōu)條件屬性集S
(1)For X中的每個(gè)條件屬性xi
(2)使用ReliefF算法計(jì)算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
數(shù)據(jù)集合中的條件屬性并非都對(duì)模型的分類包含相同的期望信息,有些條件屬性對(duì)分類起到一定的正作用,有些則相反。例如對(duì)Long Method代碼異味進(jìn)行分類,條件屬性“LOC”(代碼量)包含更多的期望信息,對(duì)其分類有更多作用,而條件屬性“DIT”(類的繼承深度)只包含少量期望信息。同樣,利用C4.5算法構(gòu)造決策樹時(shí),在數(shù)據(jù)集合中先選擇一個(gè)條件屬性作為分裂屬性,剩下的條件屬性集中,有的條件屬性對(duì)分裂屬性影響較大,有的則相反。例如天氣的兩個(gè)條件屬性溫度和季節(jié),季節(jié)的變化會(huì)影響溫度的高低,這兩個(gè)條件屬性將有一定的影響,具有一定的關(guān)聯(lián)關(guān)系。
本文認(rèn)為任意兩個(gè)屬性都有一定的關(guān)聯(lián)關(guān)系,并且定義這種關(guān)聯(lián)關(guān)系為相關(guān)度。C4.5算法在構(gòu)造決策樹時(shí),只考慮條件屬性與目標(biāo)屬性的相關(guān)度,忽略條件屬性間的相關(guān)度。改進(jìn)的C4.5算法通過計(jì)算對(duì)稱不確定性來確定兩個(gè)條件屬性間的相關(guān)度。
對(duì)稱不確定性(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時(shí),表示X與Y為兩個(gè)相互獨(dú)立的條件屬性,當(dāng)SU(X,Y)=1時(shí),表示X與Y為兩個(gè)完全相關(guān)的條件屬性。則條件屬性A與其它所有條件屬性的平均相關(guān)度公式為
(8)
式(8)中E為不包含條件屬性A的屬性子集,|E|為集合E的屬性總數(shù)。
C4.5算法構(gòu)造決策樹選擇分裂屬性時(shí)需要考慮該條件屬性與目標(biāo)屬性有最大相關(guān)度,同時(shí)在該條件屬性與其它條件屬性間需要有最小相關(guān)度,即該條件屬性與其它條件屬性有最小的平均相關(guān)度。改進(jìn)后的算法公式如式(9)所示
(9)
如果條件屬性A與其它條件屬性的相關(guān)度越小,平均相關(guān)度就越小,信息增益率就越大。本文將對(duì)稱不確定性(SU)加入C4.5算法中,更新信息增益率的計(jì)算,所以把該改進(jìn)算法稱為SU_C4.5算法,偽代碼如算法2所示。
算法2:SU_C4.5算法
輸入:數(shù)據(jù)集D(有n個(gè)屬性,其中n-1個(gè)是條件屬性,第n個(gè)是目標(biāo)屬性)
輸出:一棵決策樹
(1)創(chuàng)建根節(jié)點(diǎn)N
(2)If 所有樣本都屬于同一類別C,then
(3)Return N為葉子結(jié)點(diǎn),標(biāo)記為類C
(4)For D中的每個(gè)條件屬性A
(5) 計(jì)算條件屬性間的相關(guān)度和信息增益率
(6)End for
(7)選擇使GainRatio(D,A)(信息增益率)最大的條件屬性作為分裂屬性
(8)將數(shù)據(jù)集D按照選擇的分裂屬性進(jìn)行劃分
(9)對(duì)于分裂后的每部分?jǐn)?shù)據(jù)集,循環(huán)執(zhí)行以上算法過程
在傳統(tǒng)的C4.5算法中,計(jì)算信息增益率的時(shí)間復(fù)雜度是O(m*n),其中m是屬性的個(gè)數(shù),n是樣本的個(gè)數(shù)[13]。在SU_C4.5算法中,計(jì)算信息增益率之前,需要先計(jì)算條件屬性間的相關(guān)度,需要掃描為整個(gè)區(qū)間去計(jì)算每個(gè)條件屬性間的相關(guān)度,其時(shí)間復(fù)雜度為O(m*n)。所以在使用SU_C4.5算法計(jì)算信息增益率最壞情況下的時(shí)間復(fù)雜度仍然為O(m*n)。
為了驗(yàn)證本文提出的SU_C4.5算法的有效性,在4個(gè)開源軟件Eclipse 3.3.1,Mylyn 3.1.1,ArgoUML 0.26和Rhino 1.6上進(jìn)行了實(shí)證性研究。本實(shí)驗(yàn)主要關(guān)注以下3個(gè)問題:
Q1: C4.5算法在屬性選擇后的數(shù)據(jù)集上的分類準(zhǔn)確率是否有提高?
Q2: SU_C4.5算法相對(duì)于傳統(tǒng)C4.5算法的分類準(zhǔn)確率是否有提高?
Q3: SU_C4.5算法相對(duì)于其它機(jī)器學(xué)習(xí)算法的分類準(zhǔn)確率是否有提高?
實(shí)驗(yàn)中使用的數(shù)據(jù)集來自于Lucas Amorim等[6]的論文中的數(shù)據(jù)集,數(shù)據(jù)集D={(Ni,Ai,Ci)|i=1,2,3,…,n}, Ni表示代碼類實(shí)體的ID,Ai表示代碼實(shí)體的屬性(本文指度量,如LOC、WMC等),Ci表示該實(shí)體是否是代碼異味。數(shù)據(jù)集D來自4個(gè)java開源軟件Eclipse 3.3.1、Mylyn 3.1.1、ArgoUML 0.26 和Rhino 1.6,總共有7952個(gè)樣本,61個(gè)條件屬性,9種代碼異味。本文實(shí)驗(yàn)采用十折交叉驗(yàn)證來測(cè)試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。對(duì)于這9種代碼異味,在文獻(xiàn)[14]中有詳細(xì)的定義。
(1)Antisingleton(AS):該類的對(duì)象只有一個(gè)實(shí)例,承擔(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):類中至少包含一個(gè)大而復(fù)雜的方法,可以用圈復(fù)雜度和代碼行數(shù)度量。
(5)Large Class(LC):類中至少包含一個(gè)大的方法。
(6)Long Method(LM):類中有過長(zhǎng)方法。
(7)Long Parameter List(LPL):類中至少包含一個(gè)方法,該方法相對(duì)系統(tǒng)中每個(gè)方法的平均參數(shù)數(shù)量的長(zhǎng)參數(shù)列表。
(8)Message Chains(MC):一個(gè)使用長(zhǎng)鏈方法調(diào)用來實(shí)現(xiàn)(至少)其功能之一的類。
(9)Swiss Army Knife(SK):類中某方法可以分為多種方法的分離集,從而提供許多不同的不相關(guān)的功能。
本文使用信息檢索中最基本指標(biāo)召回率和精確度來評(píng)估模型的好壞,其中召回率和精確度的計(jì)算方法如下
(10)
(11)
這里TP(true positive)指正確檢測(cè)出的代碼異味數(shù),F(xiàn)P(false positive)指將非代碼異味檢測(cè)為代碼異味的數(shù)量,F(xiàn)N(false negative)指將代碼異味檢測(cè)為非代碼異味的數(shù)量。由于精確度和召回率是兩個(gè)值,無法根據(jù)兩個(gè)值來比較模型的好壞,需要F值來綜合精確度和召回率,計(jì)算方法如下
(12)
實(shí)驗(yàn)環(huán)境如下:操作系統(tǒng)是windows 10,處理器是inter(R) Core(TM)i5-8250U @1.6 GHz,內(nèi)存是8 GB,實(shí)驗(yàn)是在Weka3.8和eclipse中完成,開發(fā)語言是java。
實(shí)驗(yàn)一:本文每種代碼異味數(shù)據(jù)集的樣本總數(shù)和條件屬性總數(shù)見表2。使用RMIO算法對(duì)9種代碼異味數(shù)據(jù)集進(jìn)行屬性選擇。RMIO算法最后一步之前會(huì)給出按照值大小的一份條件屬性排序,此處的值代表?xiàng)l件屬性的相關(guān)度及冗余度,值最大即相關(guān)度最大且冗余度最小的條件屬性排在首位,值最小即相關(guān)度最低且冗余度最低的排在末尾。每種代碼異味數(shù)據(jù)集的條件屬性都有61種,為了得到更優(yōu)的條件屬性子集,本文首先將61種條件屬性按照排序結(jié)果分成6份,第1份包含前10個(gè)條件屬性,第2份包含前20個(gè)條件屬性,依次類推,第5份包含前50個(gè)屬性,第6份包含所有屬性。使用C4.5算法在不同數(shù)量的條件屬性的代碼異味數(shù)據(jù)集上進(jìn)行分類,F(xiàn)值最大的條件屬性集再依次左右±1,2,3個(gè)條件屬性,再使用C4.5算法在不同的數(shù)據(jù)集上進(jìn)行分類,此時(shí)F值最大的條件屬性集為最優(yōu)條件屬性集。
表2 代碼異味數(shù)據(jù)集樣本總數(shù)和條件屬性總數(shù)
實(shí)驗(yàn)二:分別使用SU_C4.5算法和傳統(tǒng)C4.5算法在RMIO屬性選擇后的9種代碼異味數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。通過十折交叉驗(yàn)證法計(jì)算代碼異味分類準(zhǔn)確率,最后比較兩個(gè)算法的精確度、召回率及F值。
實(shí)驗(yàn)三:分別使用SU_C4.5算法和JRip算法及樸素貝葉斯算法在RMIO屬性選擇后的9種代碼異味數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。通過十折交叉驗(yàn)證法計(jì)算代碼異味分類準(zhǔn)確率,最后比較SU_C4.5算法和JRip算法及樸素貝葉斯算法的精確度、召回率及F值。
通過上述3組實(shí)驗(yàn)的設(shè)計(jì),得到3組實(shí)驗(yàn)結(jié)果,根據(jù)實(shí)驗(yàn)結(jié)果,逐一回答前文提到的Q1-Q3問題。
Q1:對(duì)9種代碼異味數(shù)據(jù)集使用RMIO算法進(jìn)行屬性選擇,使用C4.5算法做為基準(zhǔn)分類算法,得到最優(yōu)的條件屬性子集,并與選擇之前的條件屬性集進(jìn)行比較,得到的結(jié)果見表3。其中“Δ”表示使用RMIO算法得到的條件屬性子集和未進(jìn)行選擇的條件屬性集構(gòu)造的模型比較,“+”表示使用RMIO算法進(jìn)行屬性選擇后構(gòu)造的模型結(jié)果更好,“-”表示不進(jìn)行屬性選擇的條件屬性集構(gòu)造的模型結(jié)果更好。從表3中可以看出Message Chains數(shù)據(jù)集中的條件屬性總數(shù)減到10,Blob和CDSBP數(shù)據(jù)集的條件屬性總數(shù)減得少些,減到30。從表3能夠看出,C4.5算法在使用RIMO算法進(jìn)行屬性選擇的數(shù)據(jù)集上構(gòu)造的模型的分類準(zhǔn)確率有明顯提高,其中分類精確度最高提高5.9%,召回率提高3.7%,F(xiàn)值提高4.1%。通過圖2能夠直觀看出,C4.5算法在RIMO屬性選擇后的數(shù)據(jù)集上的分類F值有所提高,結(jié)果表明在預(yù)處理階段對(duì)數(shù)據(jù)集進(jìn)行RMIO屬性選擇能夠提高分類器性能。
表3 RMIO算法與未屬性選擇的比較結(jié)果
圖2 屬性選擇前后F值對(duì)比
Q2:根據(jù)表4的實(shí)驗(yàn)結(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算法檢測(cè)代碼異味時(shí),Blob的F值近似50%,而其它代碼異味的F值都在68.5%以上,其中Long Parameter List的F值為97.4%。這是因?yàn)榇a異味沒有統(tǒng)一正式的定義,用來作為條件屬性的度量值也不一樣,使用現(xiàn)有的度量值并不適合用來檢測(cè)Blob異味。表4和圖3結(jié)果表明,SU_C4.5算法在構(gòu)造決策樹時(shí),將條件屬性間的相關(guān)度考慮進(jìn)來,能夠有效提高分類準(zhǔn)確率。
表4 SU_C4.5算法與C4.5算法的比較結(jié)果
圖3 C4.5算法改進(jìn)前后F值對(duì)比
Q3:根據(jù)表5和表6的實(shí)驗(yàn)結(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]論文中指出,在代碼異味檢測(cè)中,C4.5算法和隨機(jī)森林算法分類準(zhǔn)確率最高,其次是JRip算法,而樸素貝葉斯算法相比于前面幾種算法分類準(zhǔn)確率要低。
表5 SU_C4.5算法與JRip算法的比較結(jié)果
表6 SU_C4.5算法與樸素貝葉斯算法的比較結(jié)果
本文針對(duì)傳統(tǒng)C4.5算法未考慮條件屬性間相關(guān)度提出一種改進(jìn)方法,將對(duì)稱不確定性(SU)加入C4.5算法中,選擇信息增益率高且與條件屬性間相關(guān)度低的條件屬性作為分裂屬性。并且在數(shù)據(jù)預(yù)處理階段,使用ReliefF算法和互信息對(duì)條件屬性進(jìn)行選擇,得到最優(yōu)條件屬性子集。本文在9種代碼異味數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,SU_C4.5算法以及RMIO屬性選擇算法有更好的精確度、召回率以及F值。本文介紹了9種代碼異味的檢測(cè),后續(xù)也會(huì)對(duì)更多類型的代碼異味進(jìn)行檢測(cè)。