基于局部稀疏重構度量學習的軟件缺陷預測

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

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

基于局部稀疏重構度量學習的軟件缺陷預測

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

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

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

度量學習；軟件缺陷預測；稀疏表示；局部信息；鑒別性

0 引 言

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

目前，軟件缺陷預測技術主要分為動態缺陷預測技術和靜態缺陷預測技術兩種。動態缺陷預測技術是基于缺陷產生的時間，對軟件在生命周期或某些階段的時間關系的缺陷分布進行預測的技術；靜態缺陷預測技術是利用軟件中已經存在的缺陷以及能夠度量缺陷的度量元，結合一些機器學習模型，預測軟件中潛在的缺陷[4-5]。文中主要研究靜態缺陷預測技術。

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

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

1 大間隔最近鄰算法

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

(1)

其中，M為半正定矩陣。

結合上述兩個懲罰項得到如下損失函數(lossfunction)：

(2)

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

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

(3)

2 基于局部稀疏重構的度量學習方法(LS-RML)

(4)

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

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

(5)

(6)

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

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

(7)

(8)

其中，r1>r2。

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

根據上面定義的局部加權類內稀疏重構項和類間稀疏重構項，并借鑒LMNN中最大間隔的思想，則LSRML的目標函數定義為：

M≥0

(9)

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

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

(10)

(11)

其中，容錯誤差ε>0。

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

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

M≥0

(12)

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

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

輸出：距離度量矩陣M。

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

步驟2：令r=1,2,…，循環

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

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

(3)分解M=WWT。

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

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

3 實 驗

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

3.1 數據庫介紹

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

表1 NASA數據集

3.2 性能評價指標

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

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

表2 四種預測結果

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

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

3.3 實驗結果與分析

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

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

表3 所有方法在NASA MDP數據庫上的實驗結果

4 結束語

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

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

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

[3] 李 娟,陳 斌.一種基于JM模型的軟件安全性測試方法研究[J].計算機技術與發展,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

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

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

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