王 晴，荊曉遠,，朱陽平，吳 飛，董西偉，程 立

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

基于局部稀疏重構(gòu)度量學(xué)習(xí)的軟件缺陷預(yù)測

王 晴1，荊曉遠1,2，朱陽平3，吳 飛3，董西偉1，程 立2

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

隨著計算機技術(shù)的不斷發(fā)展，如何準確地預(yù)測出軟件中潛在的缺陷顯得至關(guān)重要。近年來，研究者們嘗試把一些機器學(xué)習(xí)方法應(yīng)用到軟件缺陷預(yù)測領(lǐng)域中，但是這些方法在分類過程中大多使用了傳統(tǒng)的歐氏距離。距離度量學(xué)習(xí)方法通過挖掘訓(xùn)練樣本集的特征信息和標記信息，學(xué)習(xí)得到有效的距離度量，讓樣本在基于度量矩陣的新特征空間中具有更好的鑒別可分性。將距離度量學(xué)習(xí)方法引入到軟件缺陷預(yù)測中，同時融入了局部稀疏重構(gòu)信息，提出一種新的軟件缺陷預(yù)測方法，即局部稀疏重構(gòu)度量學(xué)習(xí)方法(LSRML)。該方法學(xué)習(xí)得到的距離度量具有很好的鑒別性，并有效地解決了噪聲敏感問題。在軟件工程NASA數(shù)據(jù)庫上的實驗結(jié)果表明，提出的方法具有較好的缺陷預(yù)測效果。

度量學(xué)習(xí)；軟件缺陷預(yù)測；稀疏表示；局部信息；鑒別性

0 引 言

隨著軟件在各個領(lǐng)域中的開發(fā)規(guī)模不斷增長，由于軟件故障導(dǎo)致巨大損失的事件頻有發(fā)生，因此如何準確地預(yù)測出軟件中是否存在潛在缺陷的問題變得十分重要[1-3]。軟件缺陷預(yù)測(Software Defect Prediction,SDP)技術(shù)可以根據(jù)軟件的基本屬性，以及軟件模塊中的歷史缺陷數(shù)據(jù)等信息，來預(yù)測開發(fā)的軟件模塊中是否存在缺陷。它對于提高軟件質(zhì)量、縮短開發(fā)周期和控制軟件開發(fā)成本方面有著重要的意義。

目前，軟件缺陷預(yù)測技術(shù)主要分為動態(tài)缺陷預(yù)測技術(shù)和靜態(tài)缺陷預(yù)測技術(shù)兩種。動態(tài)缺陷預(yù)測技術(shù)是基于缺陷產(chǎn)生的時間，對軟件在生命周期或某些階段的時間關(guān)系的缺陷分布進行預(yù)測的技術(shù)；靜態(tài)缺陷預(yù)測技術(shù)是利用軟件中已經(jīng)存在的缺陷以及能夠度量缺陷的度量元，結(jié)合一些機器學(xué)習(xí)模型，預(yù)測軟件中潛在的缺陷[4-5]。文中主要研究靜態(tài)缺陷預(yù)測技術(shù)。

靜態(tài)缺陷預(yù)測方法的關(guān)鍵在于如何充分挖掘已有的缺陷數(shù)據(jù)，構(gòu)造出更為精確有效的預(yù)測模型。目前，已有研究者將傳統(tǒng)的機器學(xué)習(xí)方法成功地應(yīng)用在軟件缺陷預(yù)測領(lǐng)域，例如，壓縮C4.5模型(Compressed C4.5,CC4.5)[6]、樸素貝葉斯模型(Na?ve Bayes,NB)[7]、支持向量機模型(Support Vector Machine，SVM)[8]、神經(jīng)網(wǎng)絡(luò)模型(Neural Networks，NN)[9-10]等。近年來，一些較新的機器學(xué)習(xí)方法，如稀疏表示、字典學(xué)習(xí)等，已經(jīng)被成功運用到軟件缺陷預(yù)測中。代價敏感字典學(xué)習(xí)(Cost-sensitive Discriminative Dictionary Learning，CDDL)[11]融合了字典學(xué)習(xí)和代價敏感技術(shù)，解決了缺陷預(yù)測中的類不平衡和錯誤分類代價問題。協(xié)同表示分類模型(Collaborative representation classification based SDP,CSDP)[12]使用協(xié)同表示技術(shù)代替了稀疏表示應(yīng)用在缺陷預(yù)測中，有效降低了計算復(fù)雜度，提高了分類器的性能。

盡管現(xiàn)有的軟件缺陷預(yù)測方法融入了一些機器學(xué)習(xí)算法的優(yōu)點，但是預(yù)測效果仍有較大的提升空間。現(xiàn)有相關(guān)方法在訓(xùn)練模型階段或預(yù)測階段中，往往使用歐氏距離來度量樣本之間的距離。然而，歐氏距離并不能很好地突顯樣本之間的鑒別信息。因此文中引入距離度量學(xué)習(xí)方法(Distance Metric Learning)，并融入了局部加權(quán)和稀疏重構(gòu)技術(shù)，提出了一種新的軟件缺陷預(yù)測方法，即基于局部稀疏重構(gòu)的度量學(xué)習(xí)方法(Local Sparse Reconstruction based Metric Learning, LSRML)。該方法既可以學(xué)習(xí)鑒別性很好地距離度量矩陣，又融入了稀疏表示中對噪聲魯棒的優(yōu)點。文中在NASA數(shù)據(jù)庫[13]上的實驗結(jié)果驗證了所提方法的有效性。

1 大間隔最近鄰算法

這一節(jié)簡要介紹距離度量學(xué)習(xí)中的代表方法，即大間隔最近鄰算法(Large Margin Nearest Neighbor，LMNN)[14]。該算法的目標是學(xué)習(xí)一個距離度量矩陣M，使目標樣本與訓(xùn)練集中的近鄰?fù)悩颖颈M量靠近，同時與近鄰異類樣本盡量遠離。

(1)

其中，M為半正定矩陣。

結(jié)合上述兩個懲罰項得到如下?lián)p失函數(shù)(lossfunction)：

(2)

s.t.(xi-xk)TM(xi-xk)-(xi-xj)TM(xi-

xj)≥1-ξijk，ξijk≥0,M≥0

(3)

2 基于局部稀疏重構(gòu)的度量學(xué)習(xí)方法(LS-RML)

(4)

其中,‖α‖1用來強制稀疏約束;σ用來平衡重構(gòu)誤差和重構(gòu)系數(shù)的稀疏性。

為了增強距離度量矩陣M的鑒別性，設(shè)計了類內(nèi)稀疏重構(gòu)項和類間稀疏重構(gòu)項。對于每個訓(xùn)練樣本xi，i=1,2,…,N，把剩余的訓(xùn)練樣本劃分為兩個樣本集A和B。其中，A=[ai1,ai2,…,aiN1]表示和xi標記一致的樣本；B=[bi1,bi2,…,biN2]表示和xi標記不一致的樣本。類內(nèi)稀疏重構(gòu)項和類間稀疏重構(gòu)項分別表示為：

(5)

(6)

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

為了突出樣本近鄰信息在稀疏表示時的重要性，在式(5)和式(6)的基礎(chǔ)上，讓與xi同類的近鄰樣本所對應(yīng)的稀疏系數(shù)更大，與xi異類的近鄰樣本所對應(yīng)的稀疏系數(shù)更小，即：

(7)

(8)

其中，r1>r2。

可以看出，在距離相同的情況下，同類近鄰樣本對應(yīng)的權(quán)重更小，放在最小化的目標函數(shù)中，求得的表示系數(shù)就越大，這樣近鄰樣本在稀疏表示時就更加重要。

根據(jù)上面定義的局部加權(quán)類內(nèi)稀疏重構(gòu)項和類間稀疏重構(gòu)項，并借鑒LMNN中最大間隔的思想，則LSRML的目標函數(shù)定義為：

M≥0

(9)

式(9)可以使用交替優(yōu)化(AlternatingOptimization)的方式來求解。目標函數(shù)中總共有三個未知參數(shù)M,β和γ，先固定M，求解β和γ；然后固定β和γ，求解M。

首先，初始化距離度量矩陣M為歐氏距離度量矩陣，即M=Id×d。此時目標函數(shù)轉(zhuǎn)化為：

(10)

(11)

其中，容錯誤差ε>0。

式(10)、(11)為標準的l1范數(shù)的最小化問題，這和稀疏表示中的目標函數(shù)類似，可以采用文獻[15-16]中的優(yōu)化算法求解。

得到β和γ后，目標函數(shù)(式(9))可以簡化為求解矩陣M的函數(shù)：

M≥0

(12)

這是一個典型的半正定規(guī)劃問題，可以通過一個標準的半正定規(guī)劃工具包進行求解。文中使用了cvx工具包。

由于M是半正定矩陣，可以將M寫成M=WWT，這里W是一個線性轉(zhuǎn)換：d→d。其中，xi通過學(xué)習(xí)到W不斷更新：xi=WTxi，同時通過求解式(10)～(12)不斷更新β，γ和M。綜上所述，LSRML算法流程可以總結(jié)為：

輸出：距離度量矩陣M。

步驟1：初始化矩陣M：M=Id×d。

步驟2：令r=1,2,…，循環(huán)

(1)根據(jù)式(10)和式(11)計算β和γ。

(2)根據(jù)式(12)求解得到矩陣M。

(3)分解M=WWT。

(4)更新訓(xùn)練樣本xi=WTxi。

步驟3：輸出度量矩陣M=Mr。

3 實 驗

本節(jié)首先介紹實驗所用的數(shù)據(jù)庫，以及缺陷預(yù)測的評價指標，然后報告并分析文中LSRML和對比方法的實驗結(jié)果。

3.1 數(shù)據(jù)庫介紹

實驗選用了NASA MDP數(shù)據(jù)庫[13]的5個工程，每個工程代表著美國宇航局(NASA)的軟件系統(tǒng)或者子系統(tǒng)，它們包含不同的靜態(tài)代碼度量和相應(yīng)的缺陷標記數(shù)據(jù)。這些數(shù)據(jù)庫通過一個bug跟蹤系統(tǒng)記錄每個模塊的缺陷數(shù)。NASA MDP數(shù)據(jù)庫的靜態(tài)代碼度量指標包括軟件代碼量、可讀性、復(fù)雜度等等。這些分別由代碼行數(shù)、操作數(shù)以及McCabe等度量計算得到。表1匯總了NASA MDP中5個工程的詳細信息。

表1 NASA數(shù)據(jù)集

3.2 性能評價指標

在實驗中，使用四種指標來評估方法的缺陷預(yù)測效果，即召回率(Recall，Pd)、FalsePositiveRate(Pf)、F-measure和AreaUnderrocCurve(AUC)。

假設(shè)A代表有缺陷樣本被預(yù)測為有缺陷的數(shù)量，B代表有缺陷樣本被預(yù)測為無缺陷的數(shù)量，C代表無缺陷樣本被預(yù)測為有缺陷的數(shù)量，D代表無缺陷樣本被預(yù)測為無缺陷的數(shù)量,如表2所示。

表2 四種預(yù)測結(jié)果

則以上四種指標定義為：Pd=A/(A+B)；Pf=C/(C+D)；F-measure=2*recall* precision/ (recall + precision)，其中precision=A/(A+C)；AUC為ROC曲線下面積。

這四種評價指標值都在0～1之間，一個好的缺陷預(yù)測模型應(yīng)該會有較高的Pd，F(xiàn)-measure和AUC值，以及較小的Pf值。而且F-measure和AUC是綜合性評價指標，更加重要。

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

文中選取了幾種代表性的缺陷預(yù)測方法作為對比方法，包括CC4.5[6]、NB[7]、SVM[8]和CBNN[10](cost-sensitive boosting neural networks)。此外，由于提出的LSRML方法融入了距離度量學(xué)習(xí)，所以也選取LMNN[14]作為對比方法之一。實驗結(jié)果見表3。

分析表3可知，文中提出的LSRML在各個數(shù)據(jù)庫上的缺陷預(yù)測效果普遍好于對比方法，尤其是F-measure和AUC評價指標。對于基于傳統(tǒng)機器學(xué)習(xí)方法的CC4.5、SVM、NB和CBNN，LSRML優(yōu)勢較明顯，說明了使用距離度量學(xué)習(xí)得到的度量矩陣M要優(yōu)于傳統(tǒng)的歐氏距離，距離度量學(xué)習(xí)技術(shù)在軟件缺陷預(yù)測領(lǐng)域是有效的；對于代表性的距離度量學(xué)習(xí)方法LMNN，LSRML方法的優(yōu)勢說明局部稀疏重構(gòu)項在缺陷預(yù)測時的有效性。

表3 所有方法在NASA MDP數(shù)據(jù)庫上的實驗結(jié)果

4 結(jié)束語

文中首次將距離度量學(xué)習(xí)方法引入到軟件缺陷預(yù)測中，并且融入了稀疏重構(gòu)項和樣本的局部近鄰信息，提出一種新的軟件缺陷預(yù)測方法，即LSRML。該方法學(xué)習(xí)得到的距離度量具有很好的鑒別性。NASA MDP上5工程的數(shù)據(jù)庫表明，LSRML與現(xiàn)有的代表性缺陷預(yù)測方法相比，提高了缺陷預(yù)測的效果。

[1] 劉英博,王建民.面向缺陷分析的軟件庫挖掘方法綜述[J].計算機科學(xué),2007,34(9):1-4.

[2] 劉義穎,江建慧.基于軟件失效鏈的軟件錯誤行為分類研究[J].計算機技術(shù)與發(fā)展,2015,25(4):1-5.

[3] 李 娟,陳 斌.一種基于JM模型的軟件安全性測試方法研究[J].計算機技術(shù)與發(fā)展,2012,22(9):246-249.

[4] Catal C,Diri B.A systematic review of software fault prediction studies[J].Expert Systems with Applications,2009,36:7346-7354.

[5] Hall T,Beecham S,Bowes D,et al.A systematic literature review on fault prediction performance in software engineering[J]. IEEE Transactions on Software Engineering,2011,38(6):1276-1304.

[6] Wang J,Shen B J,Chen Y T.Compressed C4.5 models for software defect prediction[C]//2012 12th international conference on quality software.[s.l.]:IEEE,2012:13-16.

[7] Wang T,Li W H.Na?ve Bayes software defect prediction model[C]//International conference on computational intelligence and software engineering.[s.l.]:IEEE,2010:1-4.

[8] Elish K,Elish M.Predicting defect-prone software modules using support vector machines[J].Journal Systems and Software,2008,81(5):649-660.

[9] Thwin M M T,Quah T S.Application of neural networks for software quality prediction using object-oriented metrics[J].Journal of Systems and Software,2005,76(2):147-156.

[10] Zheng J.Cost-sensitiveboosting neural networks for software defect prediction[J].Expert Systems with Applications,2010,37(6):4537-4543.

[11] Jing X Y,Ying S,Zhang Z W,et al.Dictionary learning based software defect prediction[C]//Proceedings of the 36th international conference on software engineering.[s.l.]:ACM,2014:414-423.

[12] Jing X Y,Zhang Z W,Ying S,et al.Software defect prediction based on collaborative representation classification[C]//Proceedings of the 36th international conference on software engineering.[s.l.]:ACM,2014:632-633.

[13] Menzies T,Greenwald J,Frank A.Data mining static code attributes to learn defect predictors[J].IEEE Transactions on Software Engineering,2007,33(1):2-13.

[14] Weinberger K Q,Saul L K.Distance metric learning for large margin nearest neighbor classification[J].Journal of Machine Learning Research,2009,10(1):207-244.

[15] Donoho D L,Tsaig Y.Fast solution ofl1-normminimizationproblemswhenthesolutionmaybesparse[J].IEEETransactionsonInformationTheory,2008,54(11):4789-4812.

[16]WrightJ,YangAY,GaneshA,etal.Robustfacerecognitionviasparserepresentation[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2009,31(2):210-227.

Software Defect Prediction of Metric Learning Based on Local Sparse Reconstruction

WANG Qing1,JING Xiao-yuan1,2,ZHU Yang-ping3,WU Fei3,DONG Xi-wei1,CHENG Li2

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.State Key Laboratory of Software Engineering,School of Computer,Wuhan University,Wuhan 430072,China;3.College of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

With the development of computer technology,how to predict the potential defects in software project preciously is an important topic.Recently,researchers have introduced some machine learning methods into the software defect prediction field.However,they usually utilize the traditional Euclidean metric in classification phase.Distance metric learning can learn an effective distance metric by exploiting the feature and label information of training sets,which makes the original samples hold better discriminability in the new feature space.The distance metric learning is introduced into the software defect prediction field,and a novel software defect prediction approach called Local Sparse Reconstruction based Metric Learning (LSRML) is proposed.It incorporates the local sparse reconstruction information into the distance metric learning scheme.The learned distance metric not only has favorable discriminability,but also effectively handles the noise problem.The experiment results on the NASA projects demonstrate the effectiveness of the proposed approach.

distancemetric learning;software defect prediction;sparse representation;local information;discriminability

2016-01-24

2016-05-11

時間：2016-10-24

國家自然科學(xué)基金資助項目(61272273)

王 晴(1993-)，女，研究生，研究方向為軟件工程、機器學(xué)習(xí)與數(shù)據(jù)挖掘；荊曉遠，教授，博士生導(dǎo)師，研究方向為模式識別、圖像與信號處理、信息安全、機器學(xué)習(xí)與數(shù)據(jù)挖掘。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1114.050.html

TP181

A

1673-629X(2016)11-0054-04

10.3969/j.issn.1673-629X.2016.11.012