類不平衡稀疏重構度量學習軟件缺陷預測

史作婷，吳 迪，荊曉遠,，吳 飛

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.武漢大學 計算機學院 軟件工程國家重點實驗室，湖北 武漢 430072；3.南京郵電大學 自動化學院，江蘇 南京 210003)

0 引 言

軟件缺陷預測是軟件工程領域的一個重要研究方向，對于發現程序錯誤、保障軟件質量有重要的意義。已有的軟件缺陷預測技術借助于機器學習等方法，通過分析軟件代碼，提取與軟件缺陷相關的度量元，構建模型，找出項目中潛在的缺陷程序模塊[1]。

研究表明，軟件系統中只有極少數的模塊是有缺陷的，這說明數據集的類別分布不平衡。常用的機器學習算法直接用于不平衡數據集分類時會傾向于把有缺陷樣本錯分到無缺陷類中。但是，將有缺陷樣本錯誤預測與將無缺陷樣本錯誤預測的代價是不同的[2]。為了解決軟件缺陷預測中數據不平衡的問題，目前常用的方法是采樣法(包括上采樣、下采樣等)、代價敏感學習方法以及集成學習方法。

現在已經有很多典型的分類方法運用在軟件缺陷預測領域中，比如SVM[3]、樸素貝葉斯[4]、決策樹[5]、神經網絡[6]等算法。最近，一些機器學習領域最新的研究成果，例如字典學習、稀疏表示[7]等也引入到軟件缺陷預測中，并且取得了良好的預測效果。代價敏感鑒別字典學習(cost-sensitive discriminative dictionary learning,CDDL)[8]結合稀疏表示字典學習以及代價敏感因子，在提升預測性能的同時也解決了類不平衡問題。代價敏感局部協同表示(cost-sensitive local collaborative representation,CLCR)[9]利用協同表示為給定的一個測試模塊找出訓練集中的鄰居模塊，然后使用這些鄰居模塊的線性組合表示測試模塊。

文獻[10]提出了基于局部稀疏重構的度量學習方法(local sparse reconstruction based metric learning,LSRML)，首次將距離度量學習方法運用到軟件缺陷預測中，在稀疏表示的基礎上引入距離度量學習技術。但是該方法并沒有針對樣本集類別不平衡的問題進行處理，影響了算法性能。因此文中提出一種類不平衡稀疏重構度量學習軟件缺陷預測方法(class-imbalance sparse reconstruction metric learning software defect prediction,CSRML)，在學習特征矩陣的階段融入代價敏感因子，同時加入類別權重提高小類樣本距離度量學習的準確性，并在分類預測階段使用改進加權KNN(improved weighted KNN,IWKNN)算法預測標簽。最后在NASA數據集上驗證該方法的有效性。

1 相關工作

1.1 代價敏感學習方法

軟件缺陷領域中樣本錯誤分類的代價是不同的，通常將無缺陷樣本預測為有缺陷樣本的情況稱為Ⅰ類錯分，將有缺陷樣本預測為無缺陷樣本的情況稱為Ⅱ類錯分，而Ⅱ類錯分的代價遠大于Ⅰ類錯分。代價敏感學習提高Ⅱ類錯分的懲罰，可以生成分類模型來使錯誤分類的代價最小。例如代價敏感多層感知機(CSMLP)[11]在目標函數中加入一個代價參數來區分不同類錯誤帶來的代價。

1.2 稀疏表示

給定訓練樣本集X=[X1,X2,…,Xc]∈Rm×n，其中c表示類別數，第i類訓練樣本集為Xi=[xi,1,xi,2,…,xi,Ni]，Ni表示第i類樣本的樣本數。對于一個測試樣本y，可以看作是訓練樣本的聯合稀疏表示[7]，公式表示為：

(1)

其中，α=[α1,α2,…,αc]T表示稀疏系數向量；μ為使α保持稀疏性的正則化系數。

1.3 基于局部稀疏重構的距離度量學習

(2)

局部權重定義為：

(3)

(4)

其中，r1>r2。

最終得到的稀疏重構項為：

R(xi,A)=(xi-Aβ)TM(xi-Aβ)+σ‖Diβ‖1=

(5)

(6)

其中，β表示xi關于樣本集A的稀疏表示系數；γ表示xi關于樣本集B的稀疏表示系數。

雖然LSRML方法可以學習到鑒別性更好的度量矩陣，但是該方法沒有考慮到軟件缺陷預測中數據不平衡的問題與代價敏感問題。因此文中在度量矩陣學習階段引入代價敏感因子來減小樣本錯分代價，同時更加注重小類樣本距離度量學習的準確性，并在測試樣本分類階段使用改進加權KNN算法。

2 類不平衡稀疏重構度量學習軟件缺陷預測

文中提出的CSRML方法分為兩個階段：距離度量矩陣學習階段與使用IWKNN算法分類階段。第一個階段可以學習到距離度量矩陣M。在這一階段中引入代價敏感因子，并為不同類別的樣本賦予不同的權重，提高小類樣本計算的準確性，目的是使學習到的矩陣能更適用于類別不平衡的數據集。第二個階段使用IWKNN分類算法進行樣本標簽預測，使用該算法的目的是在進行分類任務時也考慮樣本類別不平衡的問題。

2.1 距離度量矩陣學習

為了解決軟件缺陷預測中的數據不平衡問題與樣本錯分代價不同的問題，在類間稀疏重構項中加入代價敏感因子，得到新的類間稀疏重構項公式：

(7)

其中，cost(i,j)表示樣本錯分的懲罰值，將有缺陷樣本預測為無缺陷樣本時懲罰值更大。cost(i,j)的取值為表1中的代價矩陣。

表1 代價矩陣

對于軟件缺陷預測來說，少數的存在缺陷的樣本需要被檢測出來。所以在學習過程中除了增加對錯分的懲罰之外，也應該提高小類樣本距離度量學習的準確性，可以為不同類別的樣本賦予不同的權值，使小類樣本之間距離更近。權重計算公式為：

(8)

其中，N表示樣本總數；Ni表示第i類樣本個數；c表示樣本類別數，文中c取值為2。

因此可以得到CSRML算法的目標函數：

(9)

式9可以分成兩個子問題來求解：固定M更新β與γ；固定β與γ更新M。目標函數的優化過程就是迭代更新M與β、γ的過程。

2.2 改進加權KNN算法

K近鄰算法是一種經典的分類算法，其基本思想是將測試樣本標記為其K個近鄰樣本中類別數最多的那一類[13]。文中在度量矩陣學習階段沒有改變原始樣本中數據不平衡分布的情況，因此，在后續的分類任務中還需要考慮不同類別間樣本數目差別較大對算法分類性能的影響。

文中引入了IWKNN，為訓練樣本賦予不同權重，在分類階段統計測試樣本與近鄰樣本的相似度之和，以此作為樣本分類的判決準則。IWKNN算法的步驟如下：

(1)為有缺陷與無缺陷的訓練樣本賦予不同的權重，使得有缺陷樣本具有更大的權重，同一類樣本權重相同,如式8所示。

(2)計算測試樣本與所有訓練樣本的馬氏距離，公式為：

(10)

(3)找出式10中求出的K個距離測試樣本最近的訓練樣本。

(4)分別計算測試樣本與K個近鄰樣本的相似度，距離越近，相似度越大,計算公式為：

(11)

(5)計算測試樣本與K個近鄰樣本中每類樣本的加權相似度之和,計算公式為：

(12)

(6)測試樣本類別指定為與其加權相似度最大的類，計算公式為：

(13)

結合距離度量矩陣學習階段以及IWKNN算法分類階段，可得到CSRML算法的具體步驟：

(1)初始化鑒別矩陣M。初始化矩陣M為歐氏度量矩陣M=I。

(2)更新稀疏系數β與γ。固定矩陣M，依次求得β與γ。

(3)更新半正定矩陣M。固定稀疏系數β與γ，更新矩陣M。

(4)分解半正定矩陣。M=WWT，更新訓練樣本xi=WTxi。

(5)輸出矩陣M。返回步驟2，直到連續兩次迭代求得的目標函數值J(M,β,γ)足夠接近或者達到最大的迭代次數。

(6)利用IWKNN算法求出測試樣本的標簽。

3 實 驗

3.1 數據庫

使用NASA數據庫[14-15]中的五個項目作為實驗數據，每個項目代表一個NASA的軟件系統或子系統，由靜態代碼度量指標和樣本缺陷標簽組成。表2列出了數據集的詳細信息。從表中可以看出，這五個數據集中有缺陷樣本數所占比例都低于13%，有缺陷樣本與無缺陷樣本這兩類樣本的數目之間差別較大。

表2 NASA數據集詳細信息

3.2 評價指標

采用四個常用的度量指標來評價該算法的實驗效果，四個度量指標包括召回率(recall (pd))、假陽率(false positive rate (pf))、F-measure和曲線下面積(area under curve (AUC))。這些度量指標由表3所示的四種預測結果定義。

表3 四種預測結果

其中,pd表示被正確分類的缺陷樣本占所有缺陷樣本的比例，pf表示被錯分的無缺陷樣本占所有無缺陷樣本的比例。計算公式為：

pd=A/(A+B)

(14)

pf=C/(C+D)

(15)

精準度(precision)用來評價預測模型的準確度，公式為:

precision=A/(A+C)

(16)

F-measure指標用于平衡precision和recall，計算公式為：

(17)

AUC表示ROC曲線下的面積，ROC曲線是由一列pf、pd數據對得到的一條曲線。

3.3 實驗結果

CSRML算法主要與軟件缺陷預測中的幾種典型方法作對比，包括SVM、CC4.5、NB。此外，文中算法是對LSRML算法做的改進，因此也要將其作為對比算法。

CSRML算法與其他方法的對比結果如表4所示。

表4 實驗結果

從表中可以看出，與傳統的算法相比，文中算法有比較明顯的優勢。而與LSRML算法相比，CSRML方法獲得了較高的pd值與F-measure值。通過進一步分析可以得出，CSRML算法的pd平均值比LSRML高0.026，F-measure的平均值比LSRML算法的高0.058。這說明了在度量學習軟件缺陷預測中考慮數據集不平衡問題的必要性。

4 結束語

在稀疏重構度量學習的基礎上，為度量矩陣學習階段引入代價敏感因子來減小樣本錯分代價，同時加入權重來提高小類樣本距離度量學習的準確性，并在測試樣本分類階段使用IWKNN算法。在NASA上5個項目的實驗結果證明了文中算法的有效性。

參考文獻：

[1] 陳 翔,賀 成,王 宇,等.HFS:一種面向軟件缺陷預測的混合特征選擇方法[J].計算機應用研究,2016,33(6):1758-1761.

[2] 繆林松.基于代價敏感神經網絡算法的軟件缺陷預測[J].電子科技,2012,25(6):75-78.

[3] ELISH K O,ELISH M O.Predicting defect-prone software modules using support vector machines[J].Journal of Systems & Software,2008,81(5):649-660.

[4] WANG Tao,LI Weihua.Naive Bayes software defect prediction model[C]//International conference on computational intelligence and software engineering.Wuhan,China:IEEE,2010:1-4.

[5] WANG Jun,SHEN Beijun,CHEN Yuting.Compressed C4.5 models for software defect prediction[C]//International conference on quality software. Xi’an, Shaanxi,China:IEEE,2012:13-16.

[6] ZHENG Jun. Cost-sensitive boosting neural networks for software defect prediction[J].Expert Systems with Applications,2010,37(6):4537-4543.

[7] WRIGHT J, YANG A Y, GANESH A, et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2008,31(2):210-227.

[8] JING Xiaoyuan,YING Shi,ZHANG Zhiwu,et al.Dictionary learning based software defect prediction[C]//International conference on software engineering.[s.l.]:IEEE,2014:414-423.

[9] WU Fei,JING Xiaoyuan,DONG Xiwei,et al.Cost-sensitive local collaborative representation for software defect prediction[C]//International conference on software analysis,testing and evolution.Kunming,China:IEEE,2016:102-107.

[10] 王 晴,荊曉遠,朱陽平,等.基于局部稀疏重構度量學習的軟件缺陷預測[J].計算機技術與發展,2016,26(11):54-57.

[11] CASTRO C L,BRAGA A P.Novel cost-sensitive approach to improve the multilayer perceptron performance on imbalanced data[J].IEEE Transactions on Neural Networks and Learning Systems,2013,24(6):888-899.

[12] 劉江濤.距離度量學習中的類別不平衡問題研究[D].南京:東南大學,2016.

[13] 王超學,潘正茂,馬春森,等.改進型加權KNN算法的不平衡數據集分類[J].計算機工程,2012,38(20):160-163.

[14] SHEPPERD M,SONG Qinbao,SUN Zhongbin,et al.Data quality:some comments on the NASA software defect datasets[J].IEEE Transactions on Software Engineering,2013,39(9):1208-1215.

[15] MENZIES T,GREENWALD J,FRANK A.Data mining static code attributes to learn defect predictors[J].IEEE Transactions on Software Engineering,2006,33(1):2-13.