史雪靜，吳 飛，荊曉遠,3

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

基于改進MDS的軟件缺陷預測

史雪靜1，吳 飛2，荊曉遠1,3

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

隨著計算機技術的發展，計算機軟件產品給個人和企業都帶來了很多方便，但很多軟件也會存在各種缺陷。為了找到并解決軟件中存在的缺陷，研究者將機器學習等方法應用到軟件缺陷預測之中，但這些方法在數據預處理方面還存在很多需要改善的地方。在之前的研究中，有研究者使用多維尺度分析(MDS)對數據樣本進行降維，但關于如何使用和改善MDS的方法卻很少。文中提出了基于閾值相關性的多維尺度分析(TC_MDS)方法，在使用MDS方法的基礎上，使用對稱不確定性(SU)方法提取具有高鑒別的特征，并使用閾值相關性去除冗余特征。該方法學習得到的數據具有高鑒別性，去除了冗余特征，從而提高了預測效率。在軟件工程NASA數據庫上的實驗結果表明，提出的方法具有較好的缺陷預測效果。

多維尺度分析；對稱不確定性；閾值相關性；軟件缺陷預測

0 引 言

軟件缺陷預測可以預測軟件出現的錯誤[1]。從整體上，軟件缺陷預測可以分為動態缺陷預測和靜態缺陷預測[2]。文中使用的是靜態缺陷預測。

至今已有很多文獻提出了靜態軟件缺陷預測算法，算法的核心有兩點，一是挖掘軟件度量，二是構建軟件缺陷預測模型。目前已經有很多研究者將機器學習方法運用到軟件缺陷預測中，例如K近鄰分類器(K-Nearest Neighbor，KNN)、壓縮C4.5模型(Compressed C4.5,CC4.5)[3]、樸素貝葉斯模型(Na?ve Bayes,NB)[4]、支持向量機模型(Support Vector Machine，SVM)[5-6]、神經網絡模型(Neural Networks，NN)[7-8]等。

軟件度量即是與軟件是否有缺陷密切相關的屬性，FENTON等[9]將軟件度量分為產品度量、過程度量、資源度量。這些度量能夠描述一個軟件模塊的各種屬性，預測模型就是在度量和缺陷類型上建立的關系，所以擁有高質量的軟件度量尤為重要。主成分分析(Principal Component Analysis，PCA)[10]、線性鑒別分析(Linear Discriminant Analysis，LDA)，拉普拉斯特征映射方法(Laplacian Eigenmaps，LE)[11]、多維尺度分析(Multi-Dimensional Scaling，MDS)[12-13]等都是針對軟件質量進行的研究。

在研究MDS方法的基礎上，文中使用對稱不確定性(Symmetrical Uncertainty，SU)方法選出高鑒別性的特征，并去除冗余特征，提出了一種新的數據預處理方法，即基于閾值相關性的多維尺度分析(Threshold Correlation on Multi-Dimensional Scaling，TC_MDS)。在NASA數據庫[14]上對該方法的有效性進行了驗證。

1 多維尺度分析

MDS是一種維度降低的方法，通過分析相似數據來挖掘數據中的隱藏結構信息。通常，相似度量使用歐氏距離表示。所以，MDS算法的目的是在盡可能保留數據樣本間距離的情況下，將數據樣本映射到一個低維空間，以此降低樣本的維度。

給定一組訓練樣本X={xi,li},i=1,2,…,n，其中訓練樣本xi∈Rd，d是樣本維數，li(li∈{1,2,…,c})是樣本類別標簽。兩個樣本之間距離由歐氏距離定義為：

d(xi,xj)=(xi-xj)T(xi-xj)

(1)

每對樣本間的距離組成的矩陣作為相似矩陣。

(2)

MDS的目標是給定D，構造樣本Z={zi,li},i=1,2,…,n，使得‖zi-zj‖≈di,j,其中i,j∈1,2,…,n。可將MDS的解決看作一個優化問題，通過最小化下面的代價函數，可求得

(3)

(4)

通過廣義特征值求解方法計算T的特征值和特征向量，取前m(m

(5)

2 基于閾值相關性的多維尺度分析

文中在MDS的基礎上進行改進，引入方法SU[15]。SU作為非線性的相關性度量，使用的理論來自信息論中的熵。該方法可以用來評估特征的質量。對于兩個變量X和Y，SU的計算公式如下：

(6)

其中，H(X)為變量X的熵。

假設p(x)是X取值的概率，則H(X)為：

(7)

IG(X|Y)為信息増益,定義為：

IG(X|Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)

(8)

SU(X,Y)=1意味著通過任意一個變量的取值能完全預測另一變量的值；SU(X,Y)=0則表明X和Y之間相互獨立。

雖然MDS方法獲得的新樣本在降低計算復雜度的同時包含了盡可能多的原樣本信息，但是該方法對分類效果改善很少，通過使用SU方法選取與類別相關性較高的特征可以提高新樣本的鑒別性。另外，MDS無法去除冗余特征，即降維后的樣本可能會含有冗余特征，這會降低算法的效率，所以文中使用閾值相關性方法去除冗余特征。

由此，TC_MDS的實施步驟如下：

(1)使用MDS對樣本集降維；

(2)使用SU方法計算每個特征與類別的相關度，提取具有高鑒別性的特征；

(3)使用閾值相關性方法去除冗余特征。

在實際軟件度量中，存在非線性的關系，所以文中依然選擇SU來計算一對特征間的相似度。文中的閾值相關性方法使用預設的β作為相關性的臨界值，在步驟(2)得到的特征下，從后向前對每個特征進行相關性分析，所有大于臨界值的一對特征就從樣本集中去除靠后的特征，然后以此類推。之所以從后向前進行相關性分析，是因為步驟(2)得到的特征從后往前其鑒別性越來越高，所以從后往前進行相關性分析，當遇到相關度大于β值的兩個特征時，就可以優先去掉鑒別性小的特征，從而保留鑒別性較大的特征。

TC_MDS算法描述如下：

輸入：訓練樣本集X=[X1,X2,…,Xc]，其中Xi=(F1,F2,…,Fm,L),i=1,2,…,c，相關性閾值β；

輸出：樣本集Z。

步驟1：計算各個樣本之間的距離，得到距離矩陣D；

步驟3：令i=1 tok，循環

計算Si=SU(Fi,L)；

步驟4：對Si按從大到小排序；

步驟6：對每對特征從后向前使用SU進行相關性分析，去除大于β的指定特征，得出最終樣本Ζ。

3 實 驗

3.1 數據庫

選用NASA數據庫，五個工程分別代表著NASA的軟件系統，它們具有不同的度量和對應的缺陷標記。表1匯總了這五個工程的詳細信息。

表1 NASA數據集

3.2 性能評價指標

實驗中使用四種評估指標，分別是召回率(Recall，Pd)、誤檢率(Pf)、F-measure和ROC曲線下的面積(AUC)。預測結果見表2。

指標定義為：

Pd=A/(A+B)

(9)

Pf=C/(C+D)

(10)

F-measure=2*recall*precision/(recall+

precision)

(11)

其中，precision=A/(A+C)。

當具有較高的Pd，F-measure，AUC和較低的Pf，一個預測模型才算是好的。且F-measure和AUC是綜合性評價指標，更為重要。

3.3 實驗結果與分析

實驗使用MDS、PCA、LE作為對比方法，使用隨機森林作為分類器，在CM1、MW1、PC1、PC3、PC4庫中進行實驗，結果見表3。

表3 實驗結果

分析表3可知，提出的方法TC_MDS在各個數據庫上的缺陷預測效果普遍好于其他方法，尤其是F-measure和AUC，對比PCA、LE以及MDS優勢明顯，說明了該方法在缺陷預測中的優勢。

4 結束語

在MDS的基礎上，使用SU方法提取有鑒別性的特征，并使用閾值相關性方法去除冗余特征，提出一種新的數據預處理方法(TC_MDS)。該方法學習得到的數據具有很好的鑒別性，并去除了冗余特征，提高了運算效率，降低了復雜度。在NASA數據庫上的實驗結果表明，TC_MDS與現有的代表性缺陷預測方法相比，明顯提高了缺陷預測的效率。

[1] 李 勇,黃志球,房丙午,等.代價敏感分類的軟件缺陷預測方法[J].計算機科學與探索,2014,8(12):1442-1451.

[2] 王 青,伍書劍,李明樹.軟件缺陷預測技術[J].軟件學報,2008,19(7):1565-1580.

[3] WANG J,SHEN B J,CHEN Y T.Compressed C4.5 models for software defect prediction[C]//International conferenceon quality software.[s.l.]:IEEE,2012.

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

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

[6] SHEPPERD M,BOWES D,HALL T.Researcher bias:the use of machine learning in software defect prediction[J].IEEE Transactions on Software Engineering,2014,40(6):603-616.

[7] QUAH T S,THWIN M M T.Application of neural networks for software quality prediction using object-oriented metrics[C]//International conference on software maintenance.[s.l.]:IEEE,2003:589-590.

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

[9] FENTON N E,NEIL M.Software metrics:roadmap[C]//Proceedings of conference on the future of software engineering.[s.l.]:[s.n.],2000:357-370.

[10] 劉 旸.基于機器學習的軟件缺陷預測研究[J].計算機工程與應用,2006,42(28):49-53.

[11] BELKIN M,NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2003,15(6):1373-1396.

[12] BRUCHER M,HEINRICH C,HEITZ F.A metric multidimensional scaling-based nonlinear manifold learning approach for unsupervised data reduction[J].Eurasip Journal on Advances in Signal Processing,2008(1):1-12.

[13] LU H,CUKIC B,CULP M.A semi-supervised approach to software defect prediction[C]//Computer software and applications conference.[s.l.]:IEEE,2014:416-425.

[14] 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.

[15] 陳家強.軟件缺陷預測中數據預處理技術研究[D].南京:南京大學,2014.

SoftwareDefectPredictionBasedonImprovedMDS

SHI Xue-jing1，WU Fei2，JING Xiao-yuan1,3

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

With the development of computer technology,computer software products have brought many convenience to individuals and businesses,but many software may have a variety of defects.In order to find and solve them,researchers have applied machine learning and other methods in software default prediction,but they need to be improved on data preprocessing.In previous studies,the researchers used Multi-Dimensional Scaling (MDS) to reduce the dimensionality of data samples.But the methods about how to use and improve MDS are few.A method of Threshold Correlation on MDS (TC_MDS) is proposed in this paper.Based on MDS,Symmetrical Uncertainty (SU) is used to extract the features with high discriminatory and threshold correlation to remove the redundancy.The method makes the data with high discriminatory,removing of redundancy,improvement of forecasting efficiency.The results on NASA database show it has very good defect prediction effect.

MDS；symmetrical uncertainty；threshold correlation；software defect prediction

TP31

A

1673-629X(2017)12-0020-03

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

2017-01-20

2017-05-25 < class="emphasis_bold">網絡出版時間

時間：2017-09-27

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

史雪靜(1991-)，女，碩士研究生，研究方向為軟件缺陷預測；吳 飛，講師，研究方向為機器學習、軟件工程；荊曉遠，教授，博士生導師，研究方向為模式識別、圖像與信號處理、信息安全、機器學習與數據挖掘。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170927.1000.072.html