代價敏感的Boosting 軟件缺陷預測方法

李 莉，任振康，石可欣

（東北林業大學 信息與計算機工程學院，哈爾濱 150040）

0 概述

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

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

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

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

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

1 常規Boosting 方法

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

1）給出N個數據，初始化每個數據的權重并取值相同：

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

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

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

計算Gm(x)的系數，即該基分類器的權重：

3）根據模型權重更新數據的權重：

其中：Zm是正規化系數，用來確保所有的數據權重總和為1。

指數內部為：

若弱分類器m的分類結果和真實結果相同，則θm小于1，該數據集的樣本權重降低；若弱分類器m的分類結果和真實結果不一致，即θm大于1，則該數據集樣本權重增加。

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

2 代價敏感的Boosting 方法

2.1 方法步驟

在軟件缺陷預測領域對于誤報與漏報的懲罰因子實際不相同，誤報率較高易導致開發和測試資源的浪費，漏報率較高易導致含有缺陷模塊的軟件被交付到用戶手中［18］。軟件開發后期對缺陷的修復代價是前期的指數倍，交付后存在的軟件缺陷甚至會威脅客戶的生命財產安全，因此，軟件缺陷預測過程中對漏報的懲罰應大于誤報［19-20］。CSBst 方法在更新樣本權重時，增加產生第一類錯誤樣本的權重，使產生第一類錯誤的樣本權重高于無缺陷類樣本權重和產生第二類錯誤的樣本權重［21-22］，由此可大幅提高預測結果的準確率。CSBst 方法流程如圖1 所示，其中，加粗標注為相對常規Boosting 的改進部分。

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

CSBst 方法具體步驟如下：

1）第一步同常規Boosting 方法。

2）第二步同常規Boosting 方法。

3）根據模型權重更新數據的權重：

其中：Zm是正規化系數，用來確保所有的數據權重總和為1。

指數內部為：

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

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

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

2.2 CSBst 方法實現

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

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

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

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

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

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

表1 混淆矩陣Table 1 Confusion matrix

由混淆矩陣可知，TPR 值升高，FPR 值隨之升高。選取BAL 來平衡TPR 和FPR，最優閾值和權重的選擇以BAL 取得最大值為標準。

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

2.3 CSBst 偽代碼

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

算法1代價敏感的軟件缺陷預測算法

3 實驗結果與分析

3.1 實驗環境

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

表2 數據集及其特征Table 2 Datasets and their characteristics

3.2 方法時間復雜度分析

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

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

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

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

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

3.3 結果分析

3.3.1 實驗結果

本文選用4 個NASA 缺陷預測數據集作為測試數據集，實驗結果如表3 所示。

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

從表3 可以看出：

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

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

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

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

表4 CSBst 與CSCE 的F1 指標結果對比Table 4 Comparison of F1 index results between CSBst and CSCE

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

相較CSBKNN 方法，在4 個NASA 實驗數據集中，CSBst 方法的BAL 提高7%，TPR 提高13.6%，FPR提高5.8%。相較CSCE 方法，在4 個實驗數據集中，CSBst 方法的BAL 平均提高3%，TPR 降低0.22%，FPR 降低4.4%，總體性能接近。在F1 指標上，CSBst性能優于CSCE，且CSBst 具有更低的時間復雜度，因此，CSBst 方法性能優于CSCE。與常規Boosting方法進行如上的比較分析，能夠得出同樣的結論。

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

3.3.2a取值對實驗結果的影響

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

從圖2 可以看出：

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

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

2）隨著a值的逐漸增大，誤報率FPR 和預測率TPR 都逐漸上升，當a=1.6 時，綜合性能指標BAL 最高，可以認為a=1.6 為CSBst 在PC1 數據集上的最優解。

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

4）當a>2.4 時，TPR>95%，隨著a值的繼續增大，TPR 呈穩定趨勢，FPR 不斷增長，因此，BAL 不斷減小。綜上，1.6 為a的最佳取值。

4 結束語

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