基于決策樹(shù)的軟件可維護(hù)性預(yù)測(cè)方法研究

朱佳俊，王 煒,2，李 彤,2，唐 季

(1.云南大學(xué) 軟件學(xué)院，云南 昆明 650091；2.云南省軟件工程重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650091)

0 引 言

軟件維護(hù)是軟件全生命周期中一項(xiàng)高難度、高成本、長(zhǎng)周期的活動(dòng)，將花費(fèi)軟件總資源的60%～80%[1]。預(yù)測(cè)軟件產(chǎn)品的可維護(hù)性，能有效支持軟件維護(hù)工作，例如決策支持、資源分配、成本控制等。預(yù)測(cè)軟件可維護(hù)性對(duì)降低軟件維護(hù)成本、提高軟件可用性具有重要意義。

1993年Li和Henry[2]定義了用軟件維護(hù)期間每個(gè)類(lèi)的代碼修改行數(shù)來(lái)表示面向?qū)ο筌浖目删S護(hù)性，用CHANGE變量表示。近年來(lái)，隨著機(jī)器學(xué)習(xí)的發(fā)展，陸續(xù)提出了一些使用機(jī)器學(xué)習(xí)的方法來(lái)預(yù)測(cè)面向?qū)ο筌浖目删S護(hù)性。基于機(jī)器學(xué)習(xí)的方法通常希望構(gòu)建一個(gè)較好的模型，以更好地刻畫(huà)可維護(hù)性數(shù)據(jù)，從而提高軟件可維護(hù)性的預(yù)測(cè)準(zhǔn)確率。已有模型包括神經(jīng)網(wǎng)絡(luò)模型[3-5]、貝葉斯模型[6]、向后消除[6]、逐步選擇[6]、MARS[7]、SVM[7-8]、GMDH[9]、GA[9]、PNN[9]等。但是，軟件可維護(hù)性預(yù)測(cè)研究經(jīng)過(guò)20多年的發(fā)展，其預(yù)測(cè)精度始終不高，較好的平均預(yù)測(cè)誤差僅能達(dá)到0.210[9]。

軟件可維護(hù)性預(yù)測(cè)精度涉及兩個(gè)核心問(wèn)題：訓(xùn)練數(shù)據(jù)好壞和預(yù)測(cè)模型。針對(duì)這兩個(gè)問(wèn)題，文中基于抽樣方法采用決策樹(shù)對(duì)面向?qū)ο筌浖删S護(hù)性進(jìn)行研究，構(gòu)建了相應(yīng)的預(yù)測(cè)模型，并利用可維護(hù)性數(shù)據(jù)集對(duì)構(gòu)建的模型進(jìn)行實(shí)驗(yàn)驗(yàn)證。

1 文中方法

文中方法的框架如圖1所示，包含三部分：數(shù)據(jù)集獲取與預(yù)處理、決策樹(shù)建模和可維護(hù)性預(yù)測(cè)。決策樹(shù)建模是主要部分，文中按模型的要求將獲取的數(shù)據(jù)集進(jìn)行預(yù)處理形成輸入，經(jīng)過(guò)訓(xùn)練數(shù)據(jù)生成預(yù)測(cè)模型，最后使用驗(yàn)證集對(duì)生成的模型進(jìn)行驗(yàn)證，完成面向?qū)ο筌浖删S護(hù)性預(yù)測(cè)過(guò)程。

圖1 文中方法框架

1.1 數(shù)據(jù)集獲取與預(yù)處理

(1)數(shù)據(jù)集獲取。

數(shù)據(jù)集獲取是所有工作的基礎(chǔ)。為了保證文中方法的客觀性，采用該領(lǐng)域比較流行的兩個(gè)面向?qū)ο笙到y(tǒng)數(shù)據(jù)集：UIMS(user interface system)和QUES(quality evaluation system)[2]。這兩個(gè)數(shù)據(jù)集采用Ada語(yǔ)言編碼實(shí)現(xiàn)以類(lèi)為單位，一個(gè)類(lèi)代表一個(gè)實(shí)例，其中UIMS系統(tǒng)有39個(gè)類(lèi)，QUES系統(tǒng)有71個(gè)類(lèi)，共110個(gè)類(lèi)。

(2)度量因子選擇。

度量因子定義了如何描述軟件可維護(hù)性，表1給出了各度量標(biāo)準(zhǔn)的詳細(xì)描述。文中采用11個(gè)度量因子，其中五個(gè)C&K[10]度量因子：DIT、NOC、RFC、LCOM、WMC，四個(gè)L&H[2]度量因子：MPC、DAC、NOM、SIZE2，以及一個(gè)傳統(tǒng)代碼行數(shù)度量因子SIZE1。目標(biāo)變量可維護(hù)性度量因子用CHANGE表示，代表了每個(gè)類(lèi)在維護(hù)期間代碼更改(增加或刪除)行數(shù)。UIMS數(shù)據(jù)集和QUES數(shù)據(jù)集都采用了上述11個(gè)度量因子進(jìn)行描述。

表1 度量準(zhǔn)則

(3)預(yù)處理。

數(shù)據(jù)預(yù)處理的目的是把原始數(shù)據(jù)按照模型要求經(jīng)過(guò)歸一化和數(shù)據(jù)集劃分，將其形成模型的特定輸入。經(jīng)過(guò)分析原始數(shù)據(jù)，發(fā)現(xiàn)存在同一度量因子的不同樣本值或同一樣本的不同度量因子值相差很大的情況。為了縮小數(shù)據(jù)樣本各度量因子間的數(shù)值差異性，采用歸一化方法將所有有用數(shù)據(jù)映射到[0,1]區(qū)間。

(1)

1.2 決策樹(shù)建模

(1)訓(xùn)練數(shù)據(jù)采樣。

可維護(hù)性訓(xùn)練集的劃分能直接影響所構(gòu)建預(yù)測(cè)模型的精度和性能，好的訓(xùn)練集能覆蓋所有樣本空間，訓(xùn)練出的預(yù)測(cè)模型更符合問(wèn)題域，也能得到更符合實(shí)際的預(yù)測(cè)結(jié)果。但是軟件可維護(hù)性數(shù)據(jù)集中普遍存在數(shù)據(jù)分布不平衡問(wèn)題，在可維護(hù)性數(shù)據(jù)集中，無(wú)需演化的模塊數(shù)量遠(yuǎn)比需要演化的模塊數(shù)量多，因此隨機(jī)劃分訓(xùn)練集和測(cè)試集存在劃分不均衡的情況，導(dǎo)致建立的預(yù)測(cè)模型在預(yù)測(cè)可維護(hù)性行為時(shí)偏向數(shù)量多的模塊，而對(duì)數(shù)量少的模塊預(yù)測(cè)精度偏低。然而這并不符合軟件演化的實(shí)際情況，而且對(duì)可維護(hù)性的錯(cuò)誤預(yù)測(cè)代價(jià)較高。為了緩解可維護(hù)性數(shù)據(jù)的分布不平衡問(wèn)題，提高所建立模型的預(yù)測(cè)準(zhǔn)確率，采用聚簇再劃分的方式，利用K-means算法把數(shù)據(jù)集樣本先聚成K簇，再分別從K簇中提取相應(yīng)比例的樣本構(gòu)成訓(xùn)練集和測(cè)試集。算法偽代碼描述如下：

輸出：訓(xùn)練數(shù)據(jù)集。

過(guò)程：

ForD中每個(gè)數(shù)據(jù)

K-means聚成K類(lèi)

End For

For 每個(gè)類(lèi)簇

按比例P抽取訓(xùn)練集

End For

(2)訓(xùn)練預(yù)測(cè)模型。

決策樹(shù)(decision tree，DT)[11]是一個(gè)樹(shù)結(jié)構(gòu)(可以是二叉樹(shù)或非二叉樹(shù))，表示了對(duì)象屬性和對(duì)象值之間的一種映射，該結(jié)構(gòu)由樹(shù)的分支來(lái)對(duì)對(duì)象的屬性進(jìn)行分類(lèi)和預(yù)測(cè)[12]。決策樹(shù)相比其他機(jī)器學(xué)習(xí)算法不僅易于理解和實(shí)現(xiàn)，可讀性好，效率高，而且在進(jìn)行學(xué)習(xí)任務(wù)時(shí)也表現(xiàn)出了強(qiáng)大的性能，因而在各領(lǐng)域應(yīng)用廣泛。

一棵決策樹(shù)的生成過(guò)程主要分為3個(gè)部分：

①特征選擇：指從訓(xùn)練數(shù)據(jù)的眾多特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的分裂標(biāo)準(zhǔn)，根據(jù)選擇不同特征量化評(píng)估標(biāo)準(zhǔn)，衍生出不同的決策樹(shù)算法。

②決策樹(shù)生成：根據(jù)選擇的特征評(píng)估標(biāo)準(zhǔn)，從上至下遞歸地生成子節(jié)點(diǎn)，直到數(shù)據(jù)集不可分則決策樹(shù)停止生長(zhǎng)。顯然，決策樹(shù)的生成過(guò)程是一個(gè)遞歸過(guò)程。

③剪枝[13]：決策樹(shù)容易過(guò)擬合，一般需要剪枝縮小樹(shù)結(jié)構(gòu)規(guī)模，緩解過(guò)擬合。剪枝技術(shù)有預(yù)剪枝和后剪枝兩種。剪枝遵循的準(zhǔn)則是在殘留誤差與模型復(fù)雜度之間進(jìn)行平衡。

然而在實(shí)際應(yīng)用中通常會(huì)先構(gòu)建一棵較大的樹(shù)，使用與葉節(jié)點(diǎn)關(guān)聯(lián)的數(shù)據(jù)點(diǎn)數(shù)量的停止準(zhǔn)則，然后再剪枝，生成最終的決策樹(shù)。因此，生成決策樹(shù)最重要的過(guò)程變成了剪枝。假設(shè)T0代表剪枝開(kāi)始的樹(shù)，對(duì)于Ti∈T0，如果Ti能夠從T0剪枝(即通過(guò)合并對(duì)應(yīng)區(qū)域來(lái)收縮內(nèi)部節(jié)點(diǎn))得到，那么它就被定義為T(mén)0的一棵子樹(shù)。假設(shè)葉節(jié)點(diǎn)為L(zhǎng)i(i=1,2,…,m)，Li表示具有Ni個(gè)數(shù)據(jù)點(diǎn)的區(qū)域Ri。那么區(qū)域Ri給出的最優(yōu)預(yù)測(cè)為：

(2)

(3)

因此，剪枝標(biāo)準(zhǔn)為：

(4)

正則化參數(shù)λ確定了整體的殘留平方和誤差與模型復(fù)雜度的折中，模型復(fù)雜度用葉節(jié)點(diǎn)的數(shù)量m表示，它的值通過(guò)交叉驗(yàn)證的方式確定。通過(guò)使用上述方法構(gòu)建的決策樹(shù)，可以高效地對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)，決策樹(shù)生成偽代碼如下：

輸出：預(yù)測(cè)結(jié)果。

過(guò)程：

特征選擇:

For 每個(gè)特征

For 每個(gè)特征值

將數(shù)據(jù)集切分為兩部分

計(jì)算切分誤差

If當(dāng)前誤差<當(dāng)前最小誤差

將當(dāng)前切分設(shè)定為最佳切分并更新最小誤差

End for

End for

返回最佳切分的特征和閾值αi

構(gòu)建決策樹(shù):

For 數(shù)據(jù)集中每個(gè)樣本

If 該節(jié)點(diǎn)不能再分

則把當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)均值作為葉節(jié)點(diǎn)

Else

尋找當(dāng)前最佳待切特征和特征值并返回

IfXi>αi

在左子樹(shù)調(diào)用構(gòu)建決策樹(shù)方法

Else ifXi≤αi

在右子樹(shù)調(diào)用構(gòu)建決策樹(shù)方法

End for

剪枝：

For 所構(gòu)建決策樹(shù)中的每個(gè)節(jié)點(diǎn)

IfTi是一棵樹(shù)

計(jì)算將當(dāng)前兩個(gè)葉節(jié)點(diǎn)合并后的誤差

計(jì)算不合并的誤差

If 合并誤差<不合并誤差

將葉節(jié)點(diǎn)合并

End for

1.3 可維護(hù)性預(yù)測(cè)

利用1.2生成的模型進(jìn)行可維護(hù)性預(yù)測(cè)是一個(gè)回歸過(guò)程，具體為將可維護(hù)性數(shù)據(jù)按度量因子方法進(jìn)行度量，然后按相同預(yù)處理方法進(jìn)行處理，形成可維護(hù)性預(yù)測(cè)模型的輸入數(shù)據(jù)，通過(guò)模型預(yù)測(cè)出對(duì)應(yīng)的代碼更改行數(shù)CHANGE值，完成可維護(hù)性預(yù)測(cè)過(guò)程。

2 實(shí)驗(yàn)驗(yàn)證

2.1 評(píng)價(jià)方法

為了驗(yàn)證該方法的有效性和客觀性，采用該領(lǐng)域常用的評(píng)價(jià)標(biāo)準(zhǔn)絕對(duì)殘差、相對(duì)誤差率和Pred(q)對(duì)實(shí)驗(yàn)預(yù)測(cè)結(jié)果進(jìn)行度量和評(píng)價(jià)。

(1)絕對(duì)殘差(Ab.Res.)[6]：表示可維護(hù)性預(yù)測(cè)值和實(shí)際值差的絕對(duì)值。文中用絕對(duì)殘差的中位數(shù)來(lái)度量殘差分布的集中趨勢(shì)，表示為Med.Ab.Res.。Med.Ab.Res.值越小，說(shuō)明預(yù)測(cè)值和實(shí)際值的差異越小，預(yù)測(cè)越準(zhǔn)確。

Ab.Res.=|實(shí)際值-預(yù)測(cè)值|

(5)

Med.Ab.Res.=Ab.Res.0.5

(6)

(2)相對(duì)誤差率(MRE)[4,6-7,9,14-15]：表示實(shí)際值和預(yù)測(cè)值間的歸一化程度。文中用MRE的最大值Max.MRE和平均值MMRE來(lái)度量可維護(hù)性預(yù)測(cè)精度。MMRE用來(lái)度量實(shí)際值和預(yù)測(cè)值之間的平均差異，MMRE是主要評(píng)價(jià)標(biāo)準(zhǔn)；Max.MRE用來(lái)度量實(shí)際值和預(yù)測(cè)值之間的最大差異。

(7)

(8)

Max.MRE=MREmax

(9)

MMRE值越小，說(shuō)明實(shí)際值和預(yù)測(cè)值之間平均差異越小，預(yù)測(cè)準(zhǔn)確率越高；Max.MRE值越小，說(shuō)明實(shí)際值和預(yù)測(cè)值之間最大差異越小，預(yù)測(cè)準(zhǔn)確率越高。

(3)Pred(q)[4,6-7,9,14-15]：度量所有預(yù)測(cè)值中MRE值小于或等于特定值的比例[16]，值在[0,1]區(qū)間。

(10)

其中，q為特定值；K為預(yù)測(cè)值中MRE值小于或等于q的數(shù)量；N為預(yù)測(cè)數(shù)據(jù)集總個(gè)數(shù)。Pred(q)值越小，說(shuō)明預(yù)測(cè)準(zhǔn)確的比例越大。文中用Pred(0.25)來(lái)度量。

2.2 實(shí)驗(yàn)過(guò)程

數(shù)據(jù)是實(shí)驗(yàn)的基礎(chǔ)，文中使用UIMS數(shù)據(jù)集的39個(gè)類(lèi)和QUES數(shù)據(jù)集的71個(gè)類(lèi)進(jìn)行實(shí)驗(yàn)。根據(jù)數(shù)據(jù)集的數(shù)據(jù)分布情況，分別將UIMS數(shù)據(jù)集和QUES數(shù)據(jù)集聚成3簇和4簇，然后采用隨機(jī)抽樣的方式，分別從每個(gè)簇中抽取了80%的數(shù)據(jù)樣本構(gòu)成訓(xùn)練集，剩下20%的數(shù)據(jù)樣本作為測(cè)試集。

實(shí)驗(yàn)使用Python3.5實(shí)現(xiàn)，并采用Scikit-learn 0.18.1的Tree包創(chuàng)建決策樹(shù)模型。模型的好壞一方面與劃分訓(xùn)練集的合理性有關(guān)，另外還與模型參數(shù)設(shè)置的值有關(guān)，模型參數(shù)設(shè)置的合理與否能影響預(yù)測(cè)結(jié)果的精確度。文中實(shí)驗(yàn)將所有的參數(shù)設(shè)置為默認(rèn)值。

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

2.3.1 基線方法選擇

為了驗(yàn)證文中方法的準(zhǔn)確性，實(shí)驗(yàn)需選擇基線方法進(jìn)行對(duì)比。文獻(xiàn)[6]建立了貝葉斯模型、回歸樹(shù)模型、向后消除和逐步選擇模型，通過(guò)實(shí)驗(yàn)得出貝葉斯模型的預(yù)測(cè)準(zhǔn)確率優(yōu)于另外三個(gè)模型。文獻(xiàn)[4]采用人工神經(jīng)網(wǎng)絡(luò)(ANN)進(jìn)行研究，得出ANN模型能夠用于軟件可維護(hù)性預(yù)測(cè)。文獻(xiàn)[9]采用數(shù)據(jù)分組處理(GMDH)方法、遺傳算法、概率神經(jīng)網(wǎng)絡(luò)進(jìn)行研究。文獻(xiàn)[14]采用多層感知機(jī)、支持向量機(jī)、徑向基網(wǎng)絡(luò)及異構(gòu)集成方法進(jìn)行研究，發(fā)現(xiàn)基于最好訓(xùn)練(BT)集成方法的預(yù)測(cè)準(zhǔn)確率優(yōu)于單模型方法。

由于文獻(xiàn)[4]和文獻(xiàn)[9]未給出具體UIMS和QUES數(shù)據(jù)集的實(shí)驗(yàn)結(jié)論，因此文中選擇文獻(xiàn)[6]和文獻(xiàn)[14]的實(shí)驗(yàn)結(jié)果作為基準(zhǔn)方法進(jìn)行側(cè)面比對(duì)。另外，為了使實(shí)驗(yàn)更公平客觀，設(shè)置了一組對(duì)照實(shí)驗(yàn)，采用當(dāng)前取得較好預(yù)測(cè)精度的GMDH模型作為基線方法，在同等環(huán)境下對(duì)相同數(shù)據(jù)集進(jìn)行測(cè)試。

2.3.2 預(yù)測(cè)結(jié)果分析

(1)UIMS數(shù)據(jù)集。

表2為采用UIMS數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對(duì)比，圖2為UIMS數(shù)據(jù)集的MMRE和Pred(0.25)實(shí)驗(yàn)結(jié)果對(duì)比。

表2 UIMS數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖2 UIMS數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

根據(jù)UIMS實(shí)驗(yàn)結(jié)果可以得出：文中方法得到的MMRE和Max.MRE最小，Pred(0.25)達(dá)到最優(yōu)值1；對(duì)比基線方法，文中方法的預(yù)測(cè)結(jié)果其MMRE、Max.MRE和Pred(0.25)分別提高了84%、83%和75%；對(duì)比文獻(xiàn)[6]和文獻(xiàn)[14]，文中方法得到的MMRE提高了95%，Pred(0.3)分別提高了113%和56%；Med.Ab.Res.為0，對(duì)比基線方法和文獻(xiàn)[6]，文中方法在該指標(biāo)上提高了100%；通過(guò)對(duì)UIMS數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析，可以得出文中方法的預(yù)測(cè)性能更好，預(yù)測(cè)準(zhǔn)確率更高(MMRE為0.045)。

(2)QUES數(shù)據(jù)集。

表3為采用QUES數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對(duì)比，圖3為QUES數(shù)據(jù)集的MMRE和Pred(0.25)實(shí)驗(yàn)結(jié)果對(duì)比。

根據(jù)QUES實(shí)驗(yàn)結(jié)果可以得出：文中方法得到的MMRE和Max.MRE最小，Pred(0.25)達(dá)到最優(yōu)值1；對(duì)比基線方法，文中方法的預(yù)測(cè)結(jié)果其MMRE、Max.MRE和Pred(0.25)分別提高了61%、73%和30%；對(duì)比文獻(xiàn)[6]和文獻(xiàn)[14]，文中方法得到的MMRE分別提高了81%和79%，Pred(0.3)分別提高了132%和18%；Med.Ab.Res.為0，對(duì)比基線方法和文獻(xiàn)[6]，文中方法在該指標(biāo)上提高了100%；通過(guò)對(duì)QUES數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果分析，可以得出文中方法的預(yù)測(cè)性能更好，預(yù)測(cè)準(zhǔn)確率更高(MMRE為0.084)。

表3 QUES數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖3 QUES數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

綜上可得，在面向?qū)ο笙到y(tǒng)可維護(hù)性預(yù)測(cè)上，文中方法的性能和準(zhǔn)確率更高，而且Pred(0.25)都達(dá)到了該評(píng)價(jià)標(biāo)準(zhǔn)的最優(yōu)值，表明該模型所有預(yù)測(cè)結(jié)果的誤差率都小于0.25，達(dá)到了最優(yōu)狀態(tài)，驗(yàn)證了該方法能夠顯著提高軟件可維護(hù)性預(yù)測(cè)能力。

3 結(jié)束語(yǔ)

基于采樣方法利用決策樹(shù)算法對(duì)UIMS數(shù)據(jù)集和QUES數(shù)據(jù)集分別構(gòu)建了面向?qū)ο筌浖删S護(hù)性預(yù)測(cè)模型，并通過(guò)測(cè)試集對(duì)構(gòu)建的預(yù)測(cè)模型進(jìn)行了驗(yàn)證。通過(guò)設(shè)定基線方法進(jìn)行對(duì)照實(shí)驗(yàn)，同時(shí)與文獻(xiàn)[6]和文獻(xiàn)[14]的研究結(jié)果進(jìn)行側(cè)面比對(duì)，并采用該領(lǐng)域常用的評(píng)價(jià)標(biāo)準(zhǔn)-絕對(duì)殘差、平均誤差率和Pred(0.25)對(duì)實(shí)驗(yàn)預(yù)測(cè)結(jié)果進(jìn)行度量和評(píng)價(jià)。結(jié)果表明，該方法的預(yù)測(cè)性能更好，準(zhǔn)確率更高。另外，該方法對(duì)兩個(gè)數(shù)據(jù)集預(yù)測(cè)結(jié)果的Pred(0.25)指標(biāo)都達(dá)到了該評(píng)價(jià)標(biāo)準(zhǔn)的最優(yōu)值1，表明該模型所有預(yù)測(cè)結(jié)果的誤差率都小于0.25，達(dá)到了最優(yōu)狀態(tài)。

但是該方法也存在一些問(wèn)題：模型的參數(shù)設(shè)置為默認(rèn)值，有一定局限性，參數(shù)設(shè)置的好壞與模型的性能有很大關(guān)系，未來(lái)將針對(duì)參數(shù)的設(shè)置問(wèn)題進(jìn)行探討；另外，采用的UIMS和QUES數(shù)據(jù)集發(fā)布時(shí)間較早且數(shù)據(jù)實(shí)例少，未來(lái)研究中，可以探索更有利于該領(lǐng)域研究的數(shù)據(jù)集。