史雪靜，吳 飛，荊曉遠(yuǎn),3

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

基于改進(jìn)MDS的軟件缺陷預(yù)測(cè)

史雪靜1，吳 飛2，荊曉遠(yuǎn)1,3

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

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

多維尺度分析；對(duì)稱不確定性；閾值相關(guān)性；軟件缺陷預(yù)測(cè)

0 引 言

軟件缺陷預(yù)測(cè)可以預(yù)測(cè)軟件出現(xiàn)的錯(cuò)誤[1]。從整體上，軟件缺陷預(yù)測(cè)可以分為動(dòng)態(tài)缺陷預(yù)測(cè)和靜態(tài)缺陷預(yù)測(cè)[2]。文中使用的是靜態(tài)缺陷預(yù)測(cè)。

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

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

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

1 多維尺度分析

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

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

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

(1)

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

(2)

MDS的目標(biāo)是給定D，構(gòu)造樣本Z={zi,li},i=1,2,…,n，使得‖zi-zj‖≈di,j,其中i,j∈1,2,…,n?？蓪DS的解決看作一個(gè)優(yōu)化問題，通過最小化下面的代價(jià)函數(shù)，可求得

(3)

(4)

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

(5)

2 基于閾值相關(guān)性的多維尺度分析

文中在MDS的基礎(chǔ)上進(jìn)行改進(jìn)，引入方法SU[15]。SU作為非線性的相關(guān)性度量，使用的理論來自信息論中的熵。該方法可以用來評(píng)估特征的質(zhì)量。對(duì)于兩個(gè)變量X和Y，SU的計(jì)算公式如下：

(6)

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

假設(shè)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意味著通過任意一個(gè)變量的取值能完全預(yù)測(cè)另一變量的值；SU(X,Y)=0則表明X和Y之間相互獨(dú)立。

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

由此，TC_MDS的實(shí)施步驟如下：

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

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

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

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

TC_MDS算法描述如下：

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

輸出：樣本集Z。

步驟1：計(jì)算各個(gè)樣本之間的距離，得到距離矩陣D；

步驟3：令i=1 tok，循環(huán)

計(jì)算Si=SU(Fi,L)；

步驟4：對(duì)Si按從大到小排序；

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

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

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

選用NASA數(shù)據(jù)庫，五個(gè)工程分別代表著NASA的軟件系統(tǒng)，它們具有不同的度量和對(duì)應(yīng)的缺陷標(biāo)記。表1匯總了這五個(gè)工程的詳細(xì)信息。

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

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

實(shí)驗(yàn)中使用四種評(píng)估指標(biāo)，分別是召回率(Recall，Pd)、誤檢率(Pf)、F-measure和ROC曲線下的面積(AUC)。預(yù)測(cè)結(jié)果見表2。

指標(biāo)定義為：

Pd=A/(A+B)

(9)

Pf=C/(C+D)

(10)

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

precision)

(11)

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

當(dāng)具有較高的Pd，F(xiàn)-measure，AUC和較低的Pf，一個(gè)預(yù)測(cè)模型才算是好的。且F-measure和AUC是綜合性評(píng)價(jià)指標(biāo)，更為重要。

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

實(shí)驗(yàn)使用MDS、PCA、LE作為對(duì)比方法，使用隨機(jī)森林作為分類器，在CM1、MW1、PC1、PC3、PC4庫中進(jìn)行實(shí)驗(yàn)，結(jié)果見表3。

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

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

4 結(jié)束語

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

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

[2] 王 青,伍書劍,李明樹.軟件缺陷預(yù)測(cè)技術(shù)[J].軟件學(xué)報(bào),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ī)器學(xué)習(xí)的軟件缺陷預(yù)測(cè)研究[J].計(jì)算機(jī)工程與應(yīng)用,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] 陳家強(qiáng).軟件缺陷預(yù)測(cè)中數(shù)據(jù)預(yù)處理技術(shù)研究[D].南京:南京大學(xué),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">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-09-27

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272273)

史雪靜(1991-)，女，碩士研究生，研究方向?yàn)檐浖毕蓊A(yù)測(cè)；吳 飛，講師，研究方向?yàn)闄C(jī)器學(xué)習(xí)、軟件工程；荊曉遠(yuǎn)，教授，博士生導(dǎo)師，研究方向?yàn)槟Ｊ阶R(shí)別、圖像與信號(hào)處理、信息安全、機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。

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