類不平衡稀疏重構(gòu)度量學(xué)習(xí)軟件缺陷預(yù)測(cè)

史作婷，吳 迪，荊曉遠(yuǎn),，吳 飛

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.武漢大學(xué) 計(jì)算機(jī)學(xué)院 軟件工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430072；3.南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210003)

0 引 言

軟件缺陷預(yù)測(cè)是軟件工程領(lǐng)域的一個(gè)重要研究方向，對(duì)于發(fā)現(xiàn)程序錯(cuò)誤、保障軟件質(zhì)量有重要的意義。已有的軟件缺陷預(yù)測(cè)技術(shù)借助于機(jī)器學(xué)習(xí)等方法，通過(guò)分析軟件代碼，提取與軟件缺陷相關(guān)的度量元，構(gòu)建模型，找出項(xiàng)目中潛在的缺陷程序模塊[1]。

研究表明，軟件系統(tǒng)中只有極少數(shù)的模塊是有缺陷的，這說(shuō)明數(shù)據(jù)集的類別分布不平衡。常用的機(jī)器學(xué)習(xí)算法直接用于不平衡數(shù)據(jù)集分類時(shí)會(huì)傾向于把有缺陷樣本錯(cuò)分到無(wú)缺陷類中。但是，將有缺陷樣本錯(cuò)誤預(yù)測(cè)與將無(wú)缺陷樣本錯(cuò)誤預(yù)測(cè)的代價(jià)是不同的[2]。為了解決軟件缺陷預(yù)測(cè)中數(shù)據(jù)不平衡的問(wèn)題，目前常用的方法是采樣法(包括上采樣、下采樣等)、代價(jià)敏感學(xué)習(xí)方法以及集成學(xué)習(xí)方法。

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

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

1 相關(guān)工作

1.1 代價(jià)敏感學(xué)習(xí)方法

軟件缺陷領(lǐng)域中樣本錯(cuò)誤分類的代價(jià)是不同的，通常將無(wú)缺陷樣本預(yù)測(cè)為有缺陷樣本的情況稱為Ⅰ類錯(cuò)分，將有缺陷樣本預(yù)測(cè)為無(wú)缺陷樣本的情況稱為Ⅱ類錯(cuò)分，而Ⅱ類錯(cuò)分的代價(jià)遠(yuǎn)大于Ⅰ類錯(cuò)分。代價(jià)敏感學(xué)習(xí)提高Ⅱ類錯(cuò)分的懲罰，可以生成分類模型來(lái)使錯(cuò)誤分類的代價(jià)最小。例如代價(jià)敏感多層感知機(jī)(CSMLP)[11]在目標(biāo)函數(shù)中加入一個(gè)代價(jià)參數(shù)來(lái)區(qū)分不同類錯(cuò)誤帶來(lái)的代價(jià)。

1.2 稀疏表示

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

(1)

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

1.3 基于局部稀疏重構(gòu)的距離度量學(xué)習(xí)

(2)

局部權(quán)重定義為：

(3)

(4)

其中，r1>r2。

最終得到的稀疏重構(gòu)項(xiàng)為：

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

(5)

(6)

其中，β表示xi關(guān)于樣本集A的稀疏表示系數(shù)；γ表示xi關(guān)于樣本集B的稀疏表示系數(shù)。

雖然LSRML方法可以學(xué)習(xí)到鑒別性更好的度量矩陣，但是該方法沒(méi)有考慮到軟件缺陷預(yù)測(cè)中數(shù)據(jù)不平衡的問(wèn)題與代價(jià)敏感問(wèn)題。因此文中在度量矩陣學(xué)習(xí)階段引入代價(jià)敏感因子來(lái)減小樣本錯(cuò)分代價(jià)，同時(shí)更加注重小類樣本距離度量學(xué)習(xí)的準(zhǔn)確性，并在測(cè)試樣本分類階段使用改進(jìn)加權(quán)KNN算法。

2 類不平衡稀疏重構(gòu)度量學(xué)習(xí)軟件缺陷預(yù)測(cè)

文中提出的CSRML方法分為兩個(gè)階段：距離度量矩陣學(xué)習(xí)階段與使用IWKNN算法分類階段。第一個(gè)階段可以學(xué)習(xí)到距離度量矩陣M。在這一階段中引入代價(jià)敏感因子，并為不同類別的樣本賦予不同的權(quán)重，提高小類樣本計(jì)算的準(zhǔn)確性，目的是使學(xué)習(xí)到的矩陣能更適用于類別不平衡的數(shù)據(jù)集。第二個(gè)階段使用IWKNN分類算法進(jìn)行樣本標(biāo)簽預(yù)測(cè)，使用該算法的目的是在進(jìn)行分類任務(wù)時(shí)也考慮樣本類別不平衡的問(wèn)題。

2.1 距離度量矩陣學(xué)習(xí)

為了解決軟件缺陷預(yù)測(cè)中的數(shù)據(jù)不平衡問(wèn)題與樣本錯(cuò)分代價(jià)不同的問(wèn)題，在類間稀疏重構(gòu)項(xiàng)中加入代價(jià)敏感因子，得到新的類間稀疏重構(gòu)項(xiàng)公式：

(7)

其中，cost(i,j)表示樣本錯(cuò)分的懲罰值，將有缺陷樣本預(yù)測(cè)為無(wú)缺陷樣本時(shí)懲罰值更大。cost(i,j)的取值為表1中的代價(jià)矩陣。

表1 代價(jià)矩陣

對(duì)于軟件缺陷預(yù)測(cè)來(lái)說(shuō)，少數(shù)的存在缺陷的樣本需要被檢測(cè)出來(lái)。所以在學(xué)習(xí)過(guò)程中除了增加對(duì)錯(cuò)分的懲罰之外，也應(yīng)該提高小類樣本距離度量學(xué)習(xí)的準(zhǔn)確性，可以為不同類別的樣本賦予不同的權(quán)值，使小類樣本之間距離更近。權(quán)重計(jì)算公式為：

(8)

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

因此可以得到CSRML算法的目標(biāo)函數(shù)：

(9)

式9可以分成兩個(gè)子問(wèn)題來(lái)求解：固定M更新β與γ；固定β與γ更新M。目標(biāo)函數(shù)的優(yōu)化過(guò)程就是迭代更新M與β、γ的過(guò)程。

2.2 改進(jìn)加權(quán)KNN算法

K近鄰算法是一種經(jīng)典的分類算法，其基本思想是將測(cè)試樣本標(biāo)記為其K個(gè)近鄰樣本中類別數(shù)最多的那一類[13]。文中在度量矩陣學(xué)習(xí)階段沒(méi)有改變?cè)紭颖局袛?shù)據(jù)不平衡分布的情況，因此，在后續(xù)的分類任務(wù)中還需要考慮不同類別間樣本數(shù)目差別較大對(duì)算法分類性能的影響。

文中引入了IWKNN，為訓(xùn)練樣本賦予不同權(quán)重，在分類階段統(tǒng)計(jì)測(cè)試樣本與近鄰樣本的相似度之和，以此作為樣本分類的判決準(zhǔn)則。IWKNN算法的步驟如下：

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

(2)計(jì)算測(cè)試樣本與所有訓(xùn)練樣本的馬氏距離，公式為：

(10)

(3)找出式10中求出的K個(gè)距離測(cè)試樣本最近的訓(xùn)練樣本。

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

(11)

(5)計(jì)算測(cè)試樣本與K個(gè)近鄰樣本中每類樣本的加權(quán)相似度之和,計(jì)算公式為：

(12)

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

(13)

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

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

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

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

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

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

(6)利用IWKNN算法求出測(cè)試樣本的標(biāo)簽。

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)庫(kù)

使用NASA數(shù)據(jù)庫(kù)[14-15]中的五個(gè)項(xiàng)目作為實(shí)驗(yàn)數(shù)據(jù)，每個(gè)項(xiàng)目代表一個(gè)NASA的軟件系統(tǒng)或子系統(tǒng)，由靜態(tài)代碼度量指標(biāo)和樣本缺陷標(biāo)簽組成。表2列出了數(shù)據(jù)集的詳細(xì)信息。從表中可以看出，這五個(gè)數(shù)據(jù)集中有缺陷樣本數(shù)所占比例都低于13%，有缺陷樣本與無(wú)缺陷樣本這兩類樣本的數(shù)目之間差別較大。

表2 NASA數(shù)據(jù)集詳細(xì)信息

3.2 評(píng)價(jià)指標(biāo)

采用四個(gè)常用的度量指標(biāo)來(lái)評(píng)價(jià)該算法的實(shí)驗(yàn)效果，四個(gè)度量指標(biāo)包括召回率(recall (pd))、假陽(yáng)率(false positive rate (pf))、F-measure和曲線下面積(area under curve (AUC))。這些度量指標(biāo)由表3所示的四種預(yù)測(cè)結(jié)果定義。

表3 四種預(yù)測(cè)結(jié)果

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

pd=A/(A+B)

(14)

pf=C/(C+D)

(15)

精準(zhǔn)度(precision)用來(lái)評(píng)價(jià)預(yù)測(cè)模型的準(zhǔn)確度，公式為:

precision=A/(A+C)

(16)

F-measure指標(biāo)用于平衡precision和recall，計(jì)算公式為：

(17)

AUC表示ROC曲線下的面積，ROC曲線是由一列pf、pd數(shù)據(jù)對(duì)得到的一條曲線。

3.3 實(shí)驗(yàn)結(jié)果

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

CSRML算法與其他方法的對(duì)比結(jié)果如表4所示。

表4 實(shí)驗(yàn)結(jié)果

從表中可以看出，與傳統(tǒng)的算法相比，文中算法有比較明顯的優(yōu)勢(shì)。而與LSRML算法相比，CSRML方法獲得了較高的pd值與F-measure值。通過(guò)進(jìn)一步分析可以得出，CSRML算法的pd平均值比LSRML高0.026，F(xiàn)-measure的平均值比LSRML算法的高0.058。這說(shuō)明了在度量學(xué)習(xí)軟件缺陷預(yù)測(cè)中考慮數(shù)據(jù)集不平衡問(wèn)題的必要性。

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

在稀疏重構(gòu)度量學(xué)習(xí)的基礎(chǔ)上，為度量矩陣學(xué)習(xí)階段引入代價(jià)敏感因子來(lái)減小樣本錯(cuò)分代價(jià)，同時(shí)加入權(quán)重來(lái)提高小類樣本距離度量學(xué)習(xí)的準(zhǔn)確性，并在測(cè)試樣本分類階段使用IWKNN算法。在NASA上5個(gè)項(xiàng)目的實(shí)驗(yàn)結(jié)果證明了文中算法的有效性。

參考文獻(xiàn)：

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

[2] 繆林松.基于代價(jià)敏感神經(jīng)網(wǎng)絡(luò)算法的軟件缺陷預(yù)測(cè)[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] 王 晴,荊曉遠(yuǎn),朱陽(yáng)平,等.基于局部稀疏重構(gòu)度量學(xué)習(xí)的軟件缺陷預(yù)測(cè)[J].計(jì)算機(jī)技術(shù)與發(fā)展,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] 劉江濤.距離度量學(xué)習(xí)中的類別不平衡問(wèn)題研究[D].南京:東南大學(xué),2016.

[13] 王超學(xué),潘正茂,馬春森,等.改進(jìn)型加權(quán)KNN算法的不平衡數(shù)據(jù)集分類[J].計(jì)算機(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.