代價敏感的Boosting 軟件缺陷預(yù)測方法

李 莉，任振康，石可欣

（東北林業(yè)大學(xué) 信息與計算機工程學(xué)院，哈爾濱 150040）

0 概述

軟件的可靠性是軟件工程領(lǐng)域最重要的指標(biāo)之一［1-2］，軟件缺陷預(yù)測技術(shù)可以有效提高軟件可靠性，降低測試成本，合理進行軟件缺陷預(yù)測可以幫助測試團隊快速定位軟件缺陷，修復(fù)系統(tǒng)存在的漏洞。近年來的軟件缺陷預(yù)測研究結(jié)果表明［3］，絕大多數(shù)軟件缺陷集中在較小比例的軟件模塊中，即軟件缺陷預(yù)測領(lǐng)域存在嚴重的類不平衡問題?，F(xiàn)有軟件缺陷預(yù)測技術(shù)產(chǎn)生的錯誤分類主要分為2 種［4］：將有缺陷的模塊誤分為無缺陷的模塊；將無缺陷的模塊誤分為有缺陷的模塊。在軟件工程實踐中，第一類錯誤的代價遠高于第二類錯誤。隨著機器學(xué)習(xí)技術(shù)的發(fā)展，眾多研究人員將機器學(xué)習(xí)技術(shù)應(yīng)用于軟件缺陷預(yù)測領(lǐng)域。研究結(jié)果表明，代價敏感學(xué)習(xí)技術(shù)可較好地解決樣本中類不平衡問題［5］，能夠為軟件項目的決策提供支持［6-7］。

目前，軟件缺陷預(yù)測領(lǐng)域采用的主要方法包括神經(jīng)網(wǎng)絡(luò)［8］、邏輯回歸（Logistic Regression，LR）［9］、支持向量機（Support Vector Machine，SVM）［10］、貝葉斯模型［11］、集成學(xué)習(xí)方法［12］等。然而，上述方法在面對第一類和第二類錯誤分類代價不同的情況時，并未給出有效的解決方案。

YANG等使用以多個K最近鄰（K-Nearest Neighbor，KNN）為基分類器的Boosting算法進行軟件缺陷預(yù)測［13］，但使用KNN 算法時存在以下問題：KNN 算法復(fù)雜度較高，且在處理類不平衡問題時對于稀有類別的預(yù)測準(zhǔn)確率低。例如，在樣本不平衡時，即有缺陷類樣本容量很小、無缺陷類樣本容量很大，此時若輸入一個新的缺陷樣本，該樣本的K個鄰居中可能大容量類占大多數(shù)，從而導(dǎo)致分類結(jié)果誤差偏大。

相較KNN 算法，決策樹易于理解和實現(xiàn)，可以較直觀地體現(xiàn)數(shù)據(jù)特點，且其擅長處理二分類問題，但決策樹模型對多類別問題或連續(xù)型字段的分類效果不佳。在軟件缺陷預(yù)測領(lǐng)域，分類問題是一個二分類問題，即預(yù)測模塊是有缺陷模塊還是無缺陷模塊，因此，可以選取決策樹作為基分類器。李勇等使用以C4.5 決策樹作為基分類器的代價敏感Bagging算法進行軟件缺陷預(yù)測［14］，實驗結(jié)果表明，該算法具有較好的性能，但時間復(fù)雜度較高。

針對以上問題，本文提出一種代價敏感的Boosting 軟件缺陷預(yù)測方法CSBst，以提升Boosting方法在二分類問題中的預(yù)測性能［15-17］。針對不同的錯誤分類賦予其不同權(quán)重，采用閾值移動方法進行決策樹基分類器集成，從而解決類不平衡問題并在提高預(yù)測性能的同時降低算法的時間復(fù)雜度。

1 常規(guī)Boosting 方法

設(shè)訓(xùn)練數(shù)據(jù)集為{(x1，y1)，(x2，y2)，…，(xN，yN)}，其中：xi為一個含有d個元素的列向量，即xi∈X?R；yi為該訓(xùn)練數(shù)據(jù)集中的標(biāo)簽集，y∈{-1，+1}。Boosting 方法具體步驟如下：

1）給出N個數(shù)據(jù)，初始化每個數(shù)據(jù)的權(quán)重并取值相同：

2）對每一個弱分類器（1，2，…，m），按照樣本分布權(quán)重Dm訓(xùn)練數(shù)據(jù)，得到m個基學(xué)習(xí)器Gm(x)。Gm(x)的取值范圍為：

計算Gm(x)在加權(quán)訓(xùn)練集中的分類誤差：

式（3）表示模型的誤差等于每一個錯分的樣本權(quán)重之和。

計算Gm(x)的系數(shù)，即該基分類器的權(quán)重：

3）根據(jù)模型權(quán)重更新數(shù)據(jù)的權(quán)重：

其中：Zm是正規(guī)化系數(shù)，用來確保所有的數(shù)據(jù)權(quán)重總和為1。

指數(shù)內(nèi)部為：

若弱分類器m的分類結(jié)果和真實結(jié)果相同，則θm小于1，該數(shù)據(jù)集的樣本權(quán)重降低；若弱分類器m的分類結(jié)果和真實結(jié)果不一致，即θm大于1，則該數(shù)據(jù)集樣本權(quán)重增加。

4）通過迭代將多個弱分類器集成為一個強分類器：弱分類器i的權(quán)重為ai，弱分類器對于樣本i的分類結(jié)果為Gi(x)，集成之后的學(xué)習(xí)器為G(x)，sign（x）為符號函數(shù)，x>0 時輸出為1，x<0 時輸出為-1，集成學(xué)習(xí)的公式為：

2 代價敏感的Boosting 方法

2.1 方法步驟

在軟件缺陷預(yù)測領(lǐng)域?qū)τ谡`報與漏報的懲罰因子實際不相同，誤報率較高易導(dǎo)致開發(fā)和測試資源的浪費，漏報率較高易導(dǎo)致含有缺陷模塊的軟件被交付到用戶手中［18］。軟件開發(fā)后期對缺陷的修復(fù)代價是前期的指數(shù)倍，交付后存在的軟件缺陷甚至?xí){客戶的生命財產(chǎn)安全，因此，軟件缺陷預(yù)測過程中對漏報的懲罰應(yīng)大于誤報［19-20］。CSBst 方法在更新樣本權(quán)重時，增加產(chǎn)生第一類錯誤樣本的權(quán)重，使產(chǎn)生第一類錯誤的樣本權(quán)重高于無缺陷類樣本權(quán)重和產(chǎn)生第二類錯誤的樣本權(quán)重［21-22］，由此可大幅提高預(yù)測結(jié)果的準(zhǔn)確率。CSBst 方法流程如圖1 所示，其中，加粗標(biāo)注為相對常規(guī)Boosting 的改進部分。

圖1 CSBst 方法流程Fig.1 Procedure of CSBst method

CSBst 方法具體步驟如下：

1）第一步同常規(guī)Boosting 方法。

2）第二步同常規(guī)Boosting 方法。

3）根據(jù)模型權(quán)重更新數(shù)據(jù)的權(quán)重：

其中：Zm是正規(guī)化系數(shù)，用來確保所有的數(shù)據(jù)權(quán)重總和為1。

指數(shù)內(nèi)部為：

若弱分類器m的分類結(jié)果和真實結(jié)果相同，即分類正確，則Rresult<1，該數(shù)據(jù)集的樣本權(quán)重降低。若弱分類器m的分類結(jié)果和真實結(jié)果不同，即分類錯誤，則Rresult>1，該數(shù)據(jù)集的樣本權(quán)重增加。數(shù)據(jù)集的樣本權(quán)重由CL值決定。其中，CL的取值為：

4）通過迭代將多個弱基分類器集成為一個強分類器，集成學(xué)習(xí)的公式如下：

其中：弱分類器i的權(quán)重為ai；弱分類器對于樣本i的分類結(jié)果為Gi(x)；集成之后的學(xué)習(xí)器為G(x)；Tthreshold為調(diào)整閾值的參數(shù)；sign（x）為符號函數(shù)，x>0 時輸出為1，x<0 時輸出為-1。

2.2 CSBst 方法實現(xiàn)

CSBst 方法主要包括數(shù)據(jù)處理和閾值選擇2 個階段：

1）在數(shù)據(jù)處理階段，對數(shù)據(jù)集進行提取，將數(shù)據(jù)集分割為特征集和標(biāo)簽集，使用基分類器決策樹進行數(shù)據(jù)集分類。決策樹對第一個特征進行劃分，該特征最大值為FFEATURE_MAX，最小值為FFEATURE_MIN。對于該特征劃分的步長SStep為：

從FFEATURE_MIN開始，每次增加一個SStep進行特征劃分，計算方式如式（16）所示，劃分完成后計算該劃分下的錯誤率。每個特征計算20 次，依次計算每個特征直至遍歷特征集合，選出并存儲分類錯誤率最低的特征和特征閾值。

2）閾值選擇階段主要對上述數(shù)據(jù)進行進一步處理。基于CSBst 方法思想，對于已經(jīng)完成分類的第一個弱分類器，更新第一類錯誤、第二類錯誤和正確樣本的權(quán)重。依次處理每個弱分類器，最后根據(jù)基分類器的錯誤率更新其權(quán)重。

在CSBst 方法中，一直增加樣本權(quán)重雖會提高樣本的預(yù)測率，但也會在一定程度上使樣本過擬合，導(dǎo)致誤報率提高，無法有效解決類不平衡問題。為平衡預(yù)測率和誤報率，本文引入閾值移動的思想。在集成基分類器分類結(jié)果時，選擇合適值作為區(qū)分待預(yù)測模塊是否為缺陷模塊的閾值，集成加權(quán)結(jié)果小于該閾值的模塊并標(biāo)記為正常模塊，大于該閾值的模塊標(biāo)記為缺陷模塊。

在軟件缺陷預(yù)測領(lǐng)域，評價準(zhǔn)則TPR、誤報率FPR、預(yù)測率P、平衡值BAL、平衡值F1 分別如式（17）～式（21）所示，定義二值分類的混淆矩陣如表1 所示。

表1 混淆矩陣Table 1 Confusion matrix

由混淆矩陣可知，TPR 值升高，F(xiàn)PR 值隨之升高。選取BAL 來平衡TPR 和FPR，最優(yōu)閾值和權(quán)重的選擇以BAL 取得最大值為標(biāo)準(zhǔn)。

在CSBst 方法中，設(shè)置閾值為Threshold，初始值為0，權(quán)重為Weigh，初始值為1。遍歷Weigh 和Threshold，Weigh 為2.5 或Threshold 為1.5 時，TPR 值等于1，故設(shè)置Weigh 最大值為2.5，Threshold 最大值為1.5。每次遍歷步長為0.1，循環(huán)結(jié)束或TPR 值為1時遍歷停止。以BAL 取得最大值為模型的最優(yōu)解。

2.3 CSBst 偽代碼

CSBst 方法的偽代碼如算法1 所示。

算法1代價敏感的軟件缺陷預(yù)測算法

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

3.1 實驗環(huán)境

本文實驗采用公開的NASA 軟件缺陷預(yù)測數(shù)據(jù)集，包括CM1、PC1、KC1、PC3 數(shù)據(jù)集。所有結(jié)果采用10 次十折交叉驗證的平均值。實驗環(huán)境為Windows10 64 位操作系統(tǒng)，計算機內(nèi)存為8 GB，處理器為Core i5-8250u。實驗選取文獻［16］提出的CSBKNN 方 法、CSCE 方法和Boosting 方法進行對比。數(shù)據(jù)集特征如表2 所示。

表2 數(shù)據(jù)集及其特征Table 2 Datasets and their characteristics

3.2 方法時間復(fù)雜度分析

CSBst 與CSBKNN 集成方式相同，與CSCE 集成時間復(fù)雜度一致。因此，CSBst 的時間復(fù)雜度由基分類器的時間復(fù)雜度決定。

CSBst 方法使用的基分類器為一維決策樹，決策樹的訓(xùn)練時間復(fù)雜度為O(NMD)，其中：N為訓(xùn)練集中的樣本數(shù)；M為數(shù)據(jù)的維度；D是樹的深度。一維決策樹的深度為1，則時間復(fù)雜度為O(NM)。

CSBKNN 為KNN 集成的Boosting 方 法，KNN的時間復(fù)雜度為O(NM)。

CSCE 是C4.5 決策樹集成的代價敏感Bagging方法，決策樹的訓(xùn)練時間復(fù)雜度為O(NMD)。

綜上，CSBst 方法與CSBKNN 方法所采用的基分類器時間復(fù)雜度以及集成時間復(fù)雜度均相同，因此，CSBst 與CSBKNN 時間復(fù)雜度一致。CSBst 和CSCE 相比，前者的基分類器時間復(fù)雜度更低，兩者集成時間復(fù)雜度相同，因此，CSBst 方法的時間復(fù)雜度低于CSCE 方法。

3.3 結(jié)果分析

3.3.1 實驗結(jié)果

本文選用4 個NASA 缺陷預(yù)測數(shù)據(jù)集作為測試數(shù)據(jù)集，實驗結(jié)果如表3 所示。

表3 4 種方法實驗結(jié)果對比Table 3 Comparison of experimental results of four methods

從表3 可以看出：

1）與CSBKNN、CSCE 以及常規(guī)Boosting 方法相比，CSBst 方法在大部分數(shù)據(jù)集中均能取得較好的預(yù)測率。CSBst方法的平均TPR 值為76%，而CSBKNN、CSCE 以及常規(guī)Boosting 方法分別為62.4%、76.2%、18.56%，其中，常規(guī)Boosting 方法的預(yù)測率最低，主要是因為其沒有處理類不平衡問題，預(yù)測結(jié)果自然偏向多數(shù)類。

2）CSBst、CSCE、CSBKNN方法的平均誤報率分別為31.6%、36%、25.8%，而常規(guī)Boosting 方法的平均誤報率僅為3.76%。本文選取BAL 作為綜合指標(biāo)來評價預(yù)測性能，CSBst 方法具有較高的誤報率和預(yù)測率。

常規(guī)Boosting 與CSBKNN、CSCE 以及CSBst 方法相比，在方法流程中沒有考慮類不平衡問題的處理。CSBKNN、CSCE 以及CSBst 是專門為處理類不平衡問題而提出的代價敏感方法。本文選取的數(shù)據(jù)集取自真實的軟件項目，都存在類不平衡問題，因此，常規(guī)Boosting 方法性能較低。此外，為提高預(yù)測率，本文選取的性能評價標(biāo)準(zhǔn)為BAL=TPR-FPR。3 種代價敏感的方法通常都具有高預(yù)測率、高誤報率的特點，常規(guī)Boosting 方法具有低預(yù)測率和低誤報率的特點，預(yù)測率和誤報率等比增長，最后評價指標(biāo)BAL 也等比增長，因此，在本文所采用的評價指標(biāo)中常規(guī)Boosting 方法性能偏低。

綜上，常規(guī)Boosting 方法與CSBKNN、CSCE、CSBst 的性能差距主要是因為采用了特定的數(shù)據(jù)集與評價指標(biāo)。對于性能較為接近的CSBst 和CSCE方法，本文選用F1 指標(biāo)繼續(xù)進行深入分析，實驗結(jié)果如表4 所示。

表4 CSBst 與CSCE 的F1 指標(biāo)結(jié)果對比Table 4 Comparison of F1 index results between CSBst and CSCE

從表4 可以看出，對于綜合評價指標(biāo)F1，CSBst在4 個數(shù)據(jù)集中的性能均高于CSCE，分別高出0.41、0.33、0.25、0.31。CSBst 方法的F1 值較高，是由于其預(yù)測準(zhǔn)確率P和預(yù)測率TPR 均較高所致。

相較CSBKNN 方法，在4 個NASA 實驗數(shù)據(jù)集中，CSBst 方法的BAL 提高7%，TPR 提高13.6%，F(xiàn)PR提高5.8%。相較CSCE 方法，在4 個實驗數(shù)據(jù)集中，CSBst 方法的BAL 平均提高3%，TPR 降低0.22%，F(xiàn)PR 降低4.4%，總體性能接近。在F1 指標(biāo)上，CSBst性能優(yōu)于CSCE，且CSBst 具有更低的時間復(fù)雜度，因此，CSBst 方法性能優(yōu)于CSCE。與常規(guī)Boosting方法進行如上的比較分析，能夠得出同樣的結(jié)論。

綜上，CSBst 方法對軟件缺陷進行預(yù)測的整體性能明顯高于同類代價敏感的缺陷預(yù)測方法。

3.3.2a取值對實驗結(jié)果的影響

本節(jié)以PC1 數(shù)據(jù)集為例，給出實驗中代價因子a取值的選擇過程，為進行簡化，設(shè)置threshold 值為0。在采用CSBst 方法構(gòu)建預(yù)測模型時，代價因子a≥1。當(dāng)a>1 時，表示將有缺陷模塊預(yù)測為無缺陷模塊的代價較高；當(dāng)a=1 時，表示正確和錯誤分類具有相同的代價。較低的TPR 意味著沒有找全有缺陷模塊，較高的FPR 意味著要利用較多的人力資源來對沒有缺陷的模塊進行測試。

從圖2 可以看出：

圖2 a 取值對模型性能的影響Fig.2 Influence of a values on model performance

1）當(dāng)a=1 時，誤報率FPR 為3.1%，預(yù)測率TPR 為20%，預(yù)測率和誤報率均較低，但預(yù)測率FPR 低于60%，無法投入實際應(yīng)用。

2）隨著a值的逐漸增大，誤報率FPR 和預(yù)測率TPR 都逐漸上升，當(dāng)a=1.6 時，綜合性能指標(biāo)BAL 最高，可以認為a=1.6 為CSBst 在PC1 數(shù)據(jù)集上的最優(yōu)解。

3）當(dāng)a＞1.6 時，隨著a值的增大，綜合評價指標(biāo)BAL 下降，TPR 升高，適用于對系統(tǒng)要求較高或測試資源較充足的情況。

4）當(dāng)a>2.4 時，TPR>95%，隨著a值的繼續(xù)增大，TPR 呈穩(wěn)定趨勢，F(xiàn)PR 不斷增長，因此，BAL 不斷減小。綜上，1.6 為a的最佳取值。

4 結(jié)束語

為提升軟件缺陷預(yù)測精確度，本文提出一種代價敏感的Boosting 軟件缺陷預(yù)測方法CSBst。通過細化不同種類錯誤樣本的權(quán)重更新方式來篩選出存在第一類錯誤的模塊，采用移動閾值加權(quán)集成的方法解決軟件缺陷模塊中的類不平衡問題，并有效提高軟件缺陷的預(yù)測率。在NASA 軟件缺陷預(yù)測數(shù)據(jù)集上進行實驗，結(jié)果表明，與CSBKNN、CSCE 方法相比，在指標(biāo)相同的情況下，CSBst 方法的預(yù)測性能較高，時間復(fù)雜度較低，對于第一類錯誤分類樣本具有更好的查找效果。下一步將針對本文所設(shè)置的BAL 指標(biāo)調(diào)整TPR 和FTR 的比重，研究更加合理穩(wěn)定的比重設(shè)計方法，以保證算法的穩(wěn)定性。此外，將探究線性回歸、邏輯回歸等不同基分類器對算法預(yù)測性能的影響。