一種軟件缺陷不平衡數據分類新方法

劉文英，林亞林，李克文，雷永秀

(中國石油大學(華東) 計算機科學與技術學院，山東 青島 266580)

對軟件缺陷預測的研究表明，80%的缺陷集中發生在20%的模塊中，這說明軟件系統中的數據分布是不平衡的，有缺陷模塊的數量遠遠少于無缺陷模塊的數量。雖然有缺陷類樣本的數量很少，但正確識別有缺陷樣本是軟件缺陷預測的關鍵，錯誤預測有缺陷樣本可能會導致遺漏關鍵錯誤從而增加軟件開發成本。因此，解決不平衡數據問題對于提高軟件質量、減少預測誤差和成功部署軟件具有重要意義。

不平衡數據處理[1]是機器學習研究中的熱點之一，更是軟件缺陷預測方向不可或缺的部分，已有不少學者專注于不平衡數據的研究。目前公認的解決不平衡數據問題的方法是從數據和算法兩個層面進行的。數據層面通過采樣方法進行處理，算法層面通過應用集成分類算法、代價敏感算法等處理數據。例如，Patel等[2]提出合并自適應K最近鄰和模糊K最近鄰的方法來提高不平衡數據的分類性能。Marwa等[3]提出一種多目標進化方法優化傾斜決策樹，并將其應用到不平衡數據分類。Liu等[4]提出了兩階段成本敏感學習方法，該方法將成本信息處理分為特征選擇和分類兩個階段。Rodriguez等[5]比較了成本敏感算法、采樣方法、混合技術和集成技術來處理不平衡數據集，結果表明，不平衡數據經過處理后提高了預測模型的性能。Ruchika等[6]提出一種新的過采樣算法SPIDER3，并將采樣算法與成本敏感分類器結合使用，解決缺陷數據集的不平衡問題，提高預測模型的性能。Siers等[7]提出成本敏感決策樹和成本敏感投票兩種技術來處理不平衡數據問題，還結合SMOTE過采樣方法來優化決策森林進行軟件缺陷預測。張忠林等[8]提出一種融合了閾值移動技術和Bagging算法的PT-Bagging集成算法，相較于Bagging算法，所提算法在處理不平衡數據時具有更好的性能。Yuan等[9]提出一種新的集成學習算法SE-gcForest，在gcForest算法基礎上結合SMOTE和EasyEnsemble來處理不平衡數據。

隨著實際軟件系統復雜度越來越高，相應的軟件缺陷預測面臨的數據不平衡問題也越來越突出，目前已出現了一些關于軟件缺陷預測與不平衡數據相結合的研究，但是采樣技術、特征降維、軟件缺陷預測模型等仍然存在很多問題值得去探索。由于混合采樣技術理論上同時具備欠采樣和過采樣的優點，本研究提出一種改進的RUS-RSMOTE混合采樣方法，克服SMOTE算法合成新樣本時隨機數取值不精確的缺點，引入影響因素posFac對隨機數進行約束，在此基礎上結合隨機欠采樣技術，對不平衡的軟件缺陷數據集進行處理，并利用F-value、AUC、G-mean對不平衡的軟件缺陷數據分類結果進行評價。

1 相關算法

1.1 隨機欠采樣(Random under-sampling, RUS)

欠采樣技術通過一定的規則或公式減少多數類樣本的數量，改變不平衡數據集的樣本分布，緩解數據集的不平衡程度，降低計算成本。隨機欠采樣、壓縮最近鄰[10]、Tomek links方法以及鄰域清理都是常用的欠采樣方法。

隨機欠采樣通過刪除數據集中的多數類樣本實現類分布均衡的目的，進而提高分類模型的效率，但是由于刪除多數類樣本的過程具有隨機性、偶然性，容易使重要信息丟失，降低學習器的分類效果。例如，NASA發布的軟件缺陷數據集PC2中有5 589個樣本，其中23個(缺陷率0.41%)為有缺陷樣本，5 566個為無缺陷樣本，不平衡率高達242，若使用隨機欠采樣技術實現1∶1(無缺陷樣本數∶有缺陷樣本數)的數據分布，那么經過隨機欠采樣處理后的新數據集只有46個樣本(23個無缺陷樣本和23個有缺陷樣本)。圖1是某一不平衡數據集經過隨機欠采樣前后的樣本分布圖。

圖1 隨機欠采樣前后樣本分布圖

1.2 SMOTE

SMOTE算法是最具代表性的過采樣算法，通過相鄰少數類樣本間線性插值生成新樣本[11]，從而改變不平衡數據集的類分布情況。SMOTE算法通過少數類樣本間線性插值的方式生成新樣本，克服了隨機過采樣由于單純復制少數類樣本而導致分類器過擬合的現象，但也存在兩個方面的問題，一是增加了數據集樣本量，從而增加了分類器訓練時間；二是函數rand(0,1)取值范圍過大，未進行精細控制，導致新合成樣本質量無法得到保證。

過采樣技術和欠采樣技術都是通過改變樣本數量來改變類分布，從而緩解不平衡數據集的樣本分布情況，降低不平衡率。這兩種采樣技術都有各自的優缺點，目前關于兩種技術的比較尚未形成統一的定論。而混合采樣技術[16]將欠采樣和過采樣結合起來，首先對不平衡數據集進行欠采樣，然后在此基礎上進行過采樣?；旌喜蓸涌梢允乔凡蓸雍瓦^采樣具體方法中任意兩種的組合體。

1.3 主成分分析

主成分分析(principal components analysis,PCA)實質是用一組正交向量對原始特征進行變換得到新特征，且新特征間互不相關。數據本身決定著數據從原來的坐標系轉換到新坐標系，第一個新坐標軸是由原始數據中方差最大的方向確定的，第二個新坐標軸是由和第一個新坐標軸正交并且方差最大的方向確定的，不斷重復該過程，使得重復次數等于原始數據中的特征數d，得到投影變化后的新坐標軸為{w1,w2,…,wd}。研究發現，大部分方差都包含在最開始的{w1,w2,w3，…，wd′}幾個坐標軸中，剩下的坐標軸可以忽略，將維度從d降低到d′實現特征降維，也可以設置一個重構閾值t，選擇占原始數據的方差中一定百分比的特征向量，t一般取95%。PCA適用于對數值型數據進行處理，優點是僅需識別最重要的多個特征來降低數據的復雜性，缺點是有可能損失重要信息。

1.4 Vote

集成分類器通過某種策略結合多個單分類器來完成學習任務，實際上是一種組合分類器的方法，集成分類器的結構如圖2所示。如果把單分類器看作是一位決策者，那么集成分類器相當于綜合多個決策者的智慧來解決問題。集成分類器可以根據分類器的類型分為同質集成和異質集成，同質集成是由類型相同的單分類器結合而成，例如“決策樹集成分類器”中的單分類器都是決策樹；異質集成是由類型不同的單分類器結合而成，例如同時包含決策樹和樸素貝葉斯的集成分類器。在不平衡的軟件缺陷數據集上應用集成分類器，可以使得集成分類器的泛化能力明顯高于單分類器，避免過擬合現象的發生，有效地降低了單分類器在不平衡數據分類時所產生的偏差[12]。

圖2 集成分類器結構

Vote是一種集成分類器結合策略，包括三種投票方法：相對多數投票法即少數服從多數，預測結果是得票最高的類；絕對多數投票法要求最終預測類別所得票數過半；加權投票法將每個類別的票數進行加權求和，結果最大的類別即為預測結果。投票策略既可以集成相同類型的分類器，又可以集成不同類型的分類器，因此可以使用投票策略構建異質集成分類器，綜合多個分類器的優勢構建預測模型。

本研究利用5種集成技術(如表1)來構建軟件缺陷預測模型。

2 基于RUS-RSMOTE-PCA-Vote的軟件缺陷不平衡數據分類方法

利用混合采樣技術可以同時具備欠采樣和過采樣的優點，提出一種改進的RUS-RSMOTE混合采樣方法。首先對原始缺陷數據集進行隨機欠采樣來減少無缺陷樣本的數量；然后使用SMOTE算法進行過采樣，同時考慮無缺陷樣本分布的影響作用，融入影響因素posFac約束隨機數rand(0,1)的取值。為解決不平衡數據集中的數據維度問題，將提出的RUS-RSMOTE與PCA相結合對軟件缺陷數據集進行處理。首先對不平衡數據集進行RUS-RSMOTE混合采樣，根據類別標記將樣本劃分為有缺陷樣本和無缺陷樣本，對無缺陷樣本進行隨機欠采樣，對有缺陷樣本進行RSMOTE過采樣；然后對經過RUS-RSMOTE混合采樣處理后的數據集進行PCA降維，將所有樣本進行中心化，計算樣本的協方差矩陣XXT并進行特征值分解，最后取前面最大的d′個特征值對應的特征向量進行降維。最后，應用Vote集成到的個體學習器，構建適合不平衡數據的軟件缺陷預測模型。

表1 本研究采用的五種分類器及相關文獻

2.1 改進的RSMOTE過采樣方法

針對SMOTE算法合成新樣本時隨機數取值不精確的缺點，引入影響因素posFac對隨機數進行約束[18]，使得新樣本合成過程中的隨機數取值更有針對性以更加合理地擴展少數類樣本，使新數據集趨于平衡，提高分類器對于少數類樣本的分類能力。影響因素posFac的計算如下：

1) 計算有缺陷樣本xi與其K個同類近鄰的平均歐幾里得距離

(1)

2) 計算所有有缺陷樣本xi與其K個同類近鄰的平均歐幾里得距離之和

(2)

其中，m表示有缺陷樣本的數量。

3) 計算m個有缺陷樣本與同類近鄰的平均歐幾里得距離和的均值

(3)

4) 計算有缺陷樣本xi與其K個無缺陷樣本近鄰的平均歐幾里得距離

(4)

5) 計算所有有缺陷樣本xi與其K個無缺陷樣本近鄰的平均歐幾里得距離之和

(5)

6) 計算有缺陷樣本與無缺陷樣本間的平均歐幾里得距離和的均值

(6)

7) 計算當前被選中的邊界樣本與其K個同類近鄰的平均歐幾里得距離

(7)

8) 計算當前被選中的邊界樣本與其K個無缺陷樣本近鄰的平均歐幾里得距離

(8)

9) 計算相對距離比

(7)

10) 得到影響因素

(8)

基于樣本分布的RSMOTE算法描述：計算任意一個少數類樣本xi到數據集中所有同類樣本的歐幾里得距離，接著尋找樣本xi的K最近鄰，根據采樣倍率N從xi的K最近鄰中隨機選擇N個樣本與xi進行線性插值合成新樣本xnew，假設xj為被選中的xi的K最近鄰樣本，新樣本合成公式為xnew=xi+posFac(xj-xi)。

2.2 基于RUS-RSMOTE-PCA-Vote的軟件缺陷不平衡數據分類方法

基于RUS-RSMOTE和PCA的特征降維框架如圖3所示，相應的算法具體過程如下：

圖3 基于RUS-RSMOTE和PCA的特征降維框架

輸入：DataSet-原不平衡數據集；

輸出：帶有標記的分類結果。

//RUS-RSMOTE混合采樣階段：

根據類別標記將DataSet劃分成DefectSet和NonDefectSet；

對數據集NonDefectSet按照預期達到的不平衡率進行隨機欠采樣，記為數據集newNonDefectSet；

有缺陷樣本數m=DefectSet.size( )；

對數據集DefectSet進行隨機化處理；

初始化隨機變量i=0；

WHILEi

i++；

END WHILE；

newDataSet=newDataSet+DefectSet+new NonDefectSet；

//PCA降維階段：

將所有樣本xi進行中心化；

計算樣本的協方差矩陣XXT并進行特征值分解；

對特征值按從大到小的順序進行排序；

取前面最大的d′個特征值對應的特征向量w1,w2,…,wd′；

利用特征向量實現數據降維得到新數據集；

//Vote構建集成分類器階段：

將經過前兩個階段處理后的數據集在樸素貝葉斯、決策樹、支持向量機、K最近鄰4種算法上進行分類；

分析所有數據集在樸素貝葉斯、決策樹、支持向量機、K最近鄰4種算法上的分類效果，確定最終用于集成的個體分類器，組合規則為“Average of Probabilities”。

3 實驗設計與分析

3.1 實驗對象

利用數據挖掘工具WEAK，使用NASA發布的軟件缺陷數據集進行實驗，實驗數據集的具體情況見表2。

表2 用于實驗的10個軟件缺陷數據集基本信息

3.2 實驗評價指標

通常情況下精準率(precision)和召回率(recall)是評價分類器性能的常用指標，但是對于軟件缺陷預測模型而言，由于面臨著數據不平衡問題，不適合使用上述兩個指標進行模型評價，本研究使用F-value、AUC、G-mean作為評價指標。

F-value是精準率和召回率的調和均值，是不平衡數據分類問題中常用的評價指標，當精準率和召回率的取值都大時，F-value值才大，且值越大代表預測模型性能越好。計算公式為：

(9)

AUC(Area Under the Curve)表示ROC曲線與坐標軸所圍成的面積，取值范圍是0～1，是不平衡數據分類問題中常用的評價指標，AUC值越大，則預測模型的性能越好。

G-mean是有缺陷樣本召回率和無缺陷樣本召回率的幾何均值，是衡量不平衡軟件缺陷數據集整體分類情況的性能評價指標，只有當有缺陷樣本和無缺陷樣本的召回率都較大時，G-mean值才大，同樣值越大代表預測模型性能越好。計算公式為：

(10)

表3 分類器情況統計

數據集中樣本的預測結果要么是“有缺陷”要么是“無缺陷”，是一個典型的二分類問題，樣本的預測類別與實際類別相比會產生4種結果(如表3)，TP表示正確分類的有缺陷樣本數，TN表示正確分類的無缺陷樣本數，FP表示實際為無缺陷類但被預測為有缺類的樣本數，FN表示實際為有缺陷類但被預測為無缺類的樣本數。

3.3 實驗設計與結果分析

實驗中的軟件缺陷數據集不平衡程度較高，MC1數據集的不平衡率最高，為138.21，KC1數據集的不平衡率最低，為5.48。為降低不平衡率且最大限度的保持原始數據分布，設置欠采樣后的不平衡率降為5，過采樣的鄰域值K取5。

為評估RUS-RSMOTE混合采樣方法在不平衡數據集處理方面的有效性，將其與RUS[19]、SMOTE[20]、RSMOTE[18]、RUS-SMOTE[21]進行對比，選用CM1、KC1、KC3、MC1、MW1、PC2作為實驗數據集，在經過采樣處理后的新數據集上使用決策樹(J48)構建軟件缺陷預測模型，為保證客觀性，所有實驗采用十折交叉驗證進行，選用F-value、AUC和G-mean作為驗證RUS-RSMOTE混合采樣方法在軟件缺陷預測中的有效性的評價指標。

圖4～6是6個軟件缺陷數據集經過5種采樣方法處理后的F-value、AUC、G-mean評價指標對應的柱狀圖。由圖4可見，所有數據集經過RUS-RSMOTE算法處理后的F-value值普遍高于其他采樣算法，在數據集KC3上尤為明顯。由圖5、6可見，除數據集CM1外，剩余5個數據集經過RUS-RSMOTE算法處理后的AUC、G-mean值的高于其他采樣算法。

圖4 不同算法上的F-value值對比

圖5 不同算法上的AUC值對比

圖6 不同算法上的G-mean值對比

綜合三個評價指標來看，經過隨機欠采樣處理的不平衡數據集的性能最差，評價指標取值最低。RUS-RSMOTE算法與其他采樣算法相比，在不平衡軟件缺陷數據集上的F-value、AUC、G-mean值更高，證實了RUS-RSMOTE算法對于處理不平衡的軟件缺陷數據集的有效性。

PC2數據集中某兩種屬性的數據分布如圖7所示，圖7(a)表示原始數據集分布，圖7(b)表示在RUS-RSMOTE混合采樣的基礎上進行PCA特征降維后的數據分布。其中，紅色標記表示無缺陷樣本，藍色標記表示有缺陷樣本，可以看出圖7(a)中的無缺陷樣本遠遠多于有缺陷樣本，樣本的不平衡程度非常高，無法找到合適的分割線對樣本進行分類，圖7(b)的樣本分布更適合分類器學習。

表4列出了經過RUS-RSMOTE混合采樣和PCA降維后的10種數據集在樸素貝葉斯、決策樹、支持向量機、K最近鄰4種機器學習算法上進行分類的F-value、AUC、G-mean指標對比，表格中加粗以及下劃線表示的數據代表值最高。F-value、G-mean值方面，K最近鄰算法在10個數據集上均取得最大值；AUC值方面，K最近鄰算法在除PC4之外的9個數據集上取得最大值。比較4種分類算法在F-value、AUC、G-mean 3個指標上的平均值發現，K最近鄰算法的最大，決策樹算法次之。綜上所述，K最近鄰算法在軟件缺陷數據集上的分類性能最好，決策樹算法次之，樸素貝葉斯和支持向量機的分類性能相對較差。而支持向量機算法的最終決策函數只由少數的支持向量所確定，魯棒性較強。因此，將K最近鄰、決策樹、支持向量機利用投票機制Vote進行異質集成。

圖7 PC2數據集的二維散點圖

表4 不同算法上的評價指標對比

為了驗證Vote集成分類器的性能，將其與Bagging、AdaBoostM1、RandomTree、RandomForest集成分類器進行對比，比較這些集成分類器在軟件缺陷預測性能方面的差異;為了更好地體現分類效果，同時與性能較好的單分類器K最近鄰(KNN)進行比較。其中，Bagging、AdaBoostM1為元分類器，使用K最近鄰作為基分類器。為保證客觀性，所有實驗采用十折交叉驗證進行，同樣選用F-value、G-mean和AUC作為驗證集成分類器在軟件缺陷預測中的性能評價指標。

表5是10種軟件缺陷數據集在6種分類算法上的F-value值對比。由表5可以看出：

1) 使用kNN作為基分類器的Bagging、AdaBoostM1在F-value值上幾乎沒有提高，應用Bagging、AdaBoostM1后的平均F-value值與kNN相等，甚至在應用Bagging后數據集KC1、MW1、PC1、PC3的F-value值反而略微降低。

2) Vote在9個數據集上具有最高的F-value值，平均F-value值為0.87；RandomForest次之，值為0.86。

表6是10種軟件缺陷數據集在6種分類算法上的AUC值對比。由表6可以看出：

1) 使用kNN作為基分類器的Bagging在AUC值上有顯著提升，而應用AdaBoostM1后數據集KC1、KC3、MC1、PC1、PC2、PC5的AUC值略微降低，平均AUC值也低于kNN。

2) RandomForest和Vote的AUC均值相等，值為0.94，相比其他分類器，在軟件缺陷預測方面具有明顯優勢。

表5 不同算法上的F-value值對比

表6 不同算法上的AUC值對比

表7是10種軟件缺陷數據集在6種分類算法上的G-mean值對比。通過觀察可以得到如下結論：

1) 對比Bagging、AdaBoostM1和kNN發現， Bagging、AdaBoostM1幾乎沒有貢獻，與單分類器的平均G-mean值相等。

2) 與AUC值情況一樣，RandomForest和Vote在G-mean上的均值相等，值為0.89，相比其他分類器，這兩種集成算法在軟件缺陷預測方面具有明顯優勢。

圖8～10是采用Vote、kNN算法在10個數據集上的F-value、AUC、G-mean對比。從圖8可以看出，采用Vote進行分類的數據集中除PC1外，其他9個數據集的F-value值普遍高于kNN，在數據集PC4上尤為明顯。從圖9可以看出，兩者在PC5數據集上的AUC值都是0.97，除此之外，采用Vote進行分類的AUC值明顯優于kNN。圖10的柱狀圖顯示兩者在3個數據集上的G-mean值相等，采用Vote進行分類的6個數據集的G-mean值高于kNN。綜上所述，采用Vote集成K最近鄰、決策樹、支持向量機的分類器性能遠遠超過個體分類器kNN。

表7 不同算法上的G-mean值對比

圖8 kNN和Vote的F-value值對比

圖9 kNN和Vote的AUC值對比

圖10 kNN和Vote的G-mean值對比

綜合6種分類算法在F-value、AUC、G-mean 3項指標的表現來看，將K最近鄰、決策樹、支持向量機利用投票機制Vote進行異質集成的分類器在軟件缺陷預測方面具有顯著的性能優勢。

4 總結與展望

為解決軟件缺陷預測中存在的數據不平衡、特征維度高以及預測精度低等問題，提出了一種基于RUS-RSMOTE-PCA-Vote的軟件缺陷不平衡數據分類方法，首先通過隨機欠采樣來減少無缺陷樣本的數量，然后進行SMOTE過采樣，在過采樣中綜合總體樣本的分布狀況引入影響因素posFac指導新樣本的合成，對經過RUS-RSMOTE混合采樣處理后的數據集進行PCA降維，最后應用Vote組合K最近鄰、決策樹、支持向量機構造集成分類器。實驗結果表明，所提方法可以有效地解決軟件缺陷預測中存在的數據不平衡、特征維度高以及預測精度低等問題。

由于綜合考慮了軟件缺陷數據存在的數據不平衡、特征維度高以及預測精度低等問題，因此本方法在時間復雜度上稍高于其他方法，接下來將探究不同運行參數對于軟件缺陷預測的分類性能影響并提高運行速度。同時結合機器學習、深度學習的新技術進行不平衡數據處理，例如探討生成對抗網絡(generative adversarial networks, GAN)在數據擴充方面的應用等。