基于PSO-BP的軟件缺陷預(yù)測(cè)模型

于安雷，皮德常

基于PSO-BP的軟件缺陷預(yù)測(cè)模型

于安雷，皮德常

軟件缺陷檢測(cè)旨在自動(dòng)檢測(cè)程序模塊中是否包含缺陷，從而加速軟件測(cè)試過程，提高軟件系統(tǒng)的質(zhì)量。針對(duì)傳統(tǒng)軟件缺陷預(yù)測(cè)模型被限制在一定的應(yīng)用范圍而影響其預(yù)測(cè)的準(zhǔn)確性和適用性，提出了一種基于PSO-BP軟件缺陷預(yù)測(cè)模型。該模型運(yùn)用粒子群優(yōu)化算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值，采用交叉驗(yàn)證的方式進(jìn)行實(shí)驗(yàn)，并與傳統(tǒng)的機(jī)器學(xué)習(xí)方法J48和BP神經(jīng)網(wǎng)絡(luò)等方法進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明提出的方法具有較高的預(yù)測(cè)準(zhǔn)確性。

軟件缺陷預(yù)測(cè)；神經(jīng)網(wǎng)絡(luò)；粒子群優(yōu)化

1 引言

隨著軟件系統(tǒng)在工程應(yīng)用中不斷擴(kuò)大，軟件缺陷[1]的危害越來越受到人們的關(guān)注。例如，1962年，因Fortran語言少寫一個(gè)連字符，美國(guó)國(guó)家航天局（NASA）不得不銷毀價(jià)值8 000萬美元的馬里納1號(hào)探測(cè)器[2]。軟件缺陷預(yù)測(cè)能夠在軟件開發(fā)的早期預(yù)測(cè)出哪些模塊有出錯(cuò)的傾向從而盡早改正缺陷模塊，對(duì)于提高軟件可靠性有著重要的意義。本文提出的預(yù)測(cè)技術(shù)是一種靜態(tài)預(yù)測(cè)技術(shù)，即基于缺陷相關(guān)的度量數(shù)據(jù)，對(duì)缺陷分布進(jìn)行預(yù)測(cè)的技術(shù)。

目前，軟件缺陷預(yù)測(cè)模型主要包括Bayesian模型[3]、線性判別模型（Linear Discriminant Analysis，LDA）、支持向量機(jī)模型（Support Vector Machine，SVM）[4]、分類回歸樹模型（Classification and Regression Tree，CART）、馬爾可夫模型等。但這些方法尚存在一些問題，例如，Bayesian模型在因子過多，模型結(jié)構(gòu)較為復(fù)雜的情況下，計(jì)算效率和推理過程緩慢不易被人接受；分類回歸模型泛化能力比較差；支持向量機(jī)參數(shù)選擇缺乏有效的方法；馬爾可夫模型需要提出很多假設(shè)，在實(shí)際應(yīng)用中受到許多限制。

J48是一種決策樹算法，嚴(yán)格意義上說是一種對(duì)ID3算法的改進(jìn)[5]。通過信息增益率選擇屬性避免了偏向?qū)傩灾蹈叩谋锥?；在建樹的過程中不斷剪枝；能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理以及連續(xù)屬性值的離散化處理；但是在構(gòu)造樹的過程中需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，導(dǎo)致算法低效。

人工神經(jīng)網(wǎng)絡(luò)模型[6]（ANN）起源于對(duì)生物系統(tǒng)的研究和模仿，目前，在軟件缺陷預(yù)測(cè)中主要應(yīng)用的神經(jīng)網(wǎng)絡(luò)是BP神經(jīng)網(wǎng)絡(luò)。但神經(jīng)網(wǎng)絡(luò)容易陷入局部極小值點(diǎn)，收斂速度慢等缺點(diǎn)。粒子群優(yōu)化算法[7]（PSO）由Kennedy和Eberhart于1995年共同提出，具有算法簡(jiǎn)單，不需要設(shè)置參數(shù)，以及不要求目標(biāo)函數(shù)可導(dǎo)、可微，甚至不要求有明顯的表達(dá)式等優(yōu)點(diǎn)。

為了提高軟件模塊缺陷預(yù)測(cè)模型的準(zhǔn)確性，本文提出了基于PSO-BP的軟件缺陷預(yù)測(cè)模型，即運(yùn)用粒子群優(yōu)化算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值，建立軟件缺陷預(yù)測(cè)模型，最后用于實(shí)驗(yàn)預(yù)測(cè)軟件模塊是否為缺陷模塊。

2 相關(guān)工作

2.1 神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)以數(shù)學(xué)和物理方法以及從信息處理的角度對(duì)人腦神經(jīng)進(jìn)行抽象，并建立簡(jiǎn)化模型，模擬人腦的智能處理行為[6]。BP神經(jīng)網(wǎng)絡(luò)是一種誤差反傳神經(jīng)網(wǎng)絡(luò)，是一種有監(jiān)督的學(xué)習(xí)方法。其基本思想是：神經(jīng)網(wǎng)絡(luò)在外界樣本的刺激下反向傳播算法不斷地動(dòng)態(tài)修整網(wǎng)絡(luò)的連接權(quán)值和閾值，以使網(wǎng)絡(luò)的輸出等同期望或者以設(shè)定的誤差接近期望輸出[8]。曾有研究表明三層網(wǎng)絡(luò)可較好地解決非線性映射、優(yōu)化設(shè)計(jì)等問題[9]。因此本文基于這一成果，選用三層神經(jīng)網(wǎng)絡(luò)，即包括輸入層、隱藏層、輸出層。本文定義的誤差平方計(jì)算如公式（1）：

其中，m為輸出向量的維數(shù)，Yi，k是樣本i的第k維期望輸出值，Oi，k是樣本i的第k維實(shí)際輸出值，Ei為樣本i網(wǎng)絡(luò)誤差的平方。

2.2 粒子群優(yōu)化算法

粒子群優(yōu)化算法思想起源于對(duì)鳥群覓食和人類作決策時(shí)的行為模型的研究，它是一種基于群智能的隨機(jī)全局優(yōu)化算法[10]。與遺傳算法相比，它避開了遺傳算法固有的選擇、交叉及變異等操作，根據(jù)自己速度進(jìn)行搜索，縮短了神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時(shí)間，加快了收斂速度。因此本文采用粒子群優(yōu)化神經(jīng)網(wǎng)絡(luò)，達(dá)到提高神經(jīng)網(wǎng)絡(luò)的泛化能力。

粒子群優(yōu)化算法首先在目標(biāo)函數(shù)空間中生成初始種群，即隨機(jī)初始化粒子的位置及速度，每一個(gè)粒子的位置都是目標(biāo)函數(shù)的一個(gè)可行解，并有目標(biāo)函數(shù)確定其適應(yīng)值。本文的適應(yīng)值由式（2）確定：

其中，n為樣本的數(shù)量，Ei由式計(jì)算，F(xiàn)pindex為粒子的適應(yīng)度，pindex的取值為 pindex=1，2，…，size，size為粒子群規(guī)模。

在粒子群優(yōu)化過程中，粒子的速度和位置按如下公式（3）、（4）進(jìn)行調(diào)整：

其中，D為粒子的速度與位置的向量維數(shù)，t為當(dāng)前的迭代次數(shù)，w為慣性權(quán)重，c1和c2為加速常數(shù)，rand（）為隨機(jī)產(chǎn)生整數(shù)，pid為粒子i的當(dāng)前最優(yōu)位置的第d維分量，pgd為當(dāng)前種群最優(yōu)位置的第d維分量，為第t次迭代時(shí)，粒子i位置向量的第d維分量，為第t+1次迭代時(shí)，粒子i速度向量的第d維分量。

3 軟件缺陷預(yù)測(cè)模型的建立

3.1 軟件缺陷預(yù)測(cè)模型

基于PSO-BP方法的軟件缺陷預(yù)測(cè)模型主要包括如下幾個(gè)步驟，如圖1所示。

建立軟件缺陷預(yù)測(cè)模型主要步驟如下：

（1）獲取軟件缺陷數(shù)據(jù)集。

（2）基于訓(xùn)練樣本建立BP神經(jīng)網(wǎng)絡(luò)的軟件缺陷預(yù)測(cè)模型，選擇sigmoid轉(zhuǎn)移函數(shù)，采用三層網(wǎng)絡(luò)結(jié)構(gòu)。

（3）利用PSO算法優(yōu)化BP網(wǎng)絡(luò)的權(quán)值和閾值。

（4）用測(cè)試樣例對(duì)模型進(jìn)行分類預(yù)測(cè)。如果預(yù)測(cè)結(jié)果滿足終止條件，則停止優(yōu)化得到優(yōu)化的軟件預(yù)測(cè)模型；否則返回步驟3，繼續(xù)優(yōu)化模型。

其中，終止條件為模型的預(yù)測(cè)準(zhǔn)確率達(dá)到事先設(shè)定的閾值或者循環(huán)次數(shù)達(dá)到事先設(shè)定的最大值。

圖1 軟件缺陷預(yù)測(cè)模型圖

3.2 PSO優(yōu)化BP神經(jīng)網(wǎng)絡(luò)

因?yàn)锽P神經(jīng)網(wǎng)絡(luò)中的誤差梯度下降法，要求其函數(shù)可微、可導(dǎo)，本文采用PSO優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值，以達(dá)到改進(jìn)BP算法的缺陷和提高泛化性能的目的。即運(yùn)用粒子群優(yōu)化算法計(jì)算出每個(gè)粒子在每個(gè)方向上的速度和位置映射到BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值。每個(gè)粒子在個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)指導(dǎo)下尋找自身最優(yōu)解和群體最優(yōu)解的步驟如下：

（1）初始化粒子群。

（1.1）設(shè)定粒子群規(guī)模大小，粒子速度和位置以及向量的維數(shù)，其中，本文粒子規(guī)模為30，向量的維數(shù)與BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值的個(gè)數(shù)之和相等；

（1.2）隨機(jī)初始化每個(gè)粒子的位置及速度以及個(gè)體最優(yōu)解和群體最優(yōu)解；

（1.3）根據(jù)經(jīng)驗(yàn)，設(shè)定慣性權(quán)重w為0.3，加速常數(shù)c1和c2為2，設(shè)定最大進(jìn)化代數(shù)Tmax。

（2）將粒子的速度和位置分量映射給BP神經(jīng)網(wǎng)絡(luò)，按照公式計(jì)算每個(gè)粒子的適應(yīng)度。

（3）按照如下式進(jìn)行適應(yīng)度的比較：

如果current＜pbestfit，則pbestfit=current，pbest=xi；否則gbest和pbestfit不變。

如果current＜gbestfit，則gbestfit=current，gbest=xi；否則gbest和gbestfit不變。

其中，current是粒子的當(dāng)前適應(yīng)值，pbestfit是粒子的個(gè)體最優(yōu)值，gbestfit是種群全局最優(yōu)適應(yīng)值，pbest是粒子個(gè)體最優(yōu)值，gbest是種群全局最優(yōu)值，xi為粒子當(dāng)前位置。

（4）根據(jù)式（3）和式（4）更新粒子的速度和位置，通常為讓粒子達(dá)到最佳全局尋優(yōu)能力，設(shè)置速度閾值Vmax，做如下限制：

（5）將迭代次數(shù)與Tmax進(jìn)行比較，如果大于Tmax，則終止算法，且當(dāng)前的gbest為BP神經(jīng)網(wǎng)絡(luò)優(yōu)化的權(quán)值和閾值；否則跳至步驟2，繼續(xù)下一次迭代。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

本文采用的實(shí)驗(yàn)數(shù)據(jù)是由NASA提供的數(shù)據(jù)包[11]，其中含有13個(gè)數(shù)據(jù)集，如表1所示。這些數(shù)據(jù)集都是NASA的真實(shí)軟件項(xiàng)目，由常見的開發(fā)語言編寫。

表1 實(shí)驗(yàn)數(shù)據(jù)

本文根據(jù)數(shù)據(jù)集屬性Error_Count，對(duì)軟件模塊是否缺陷進(jìn)行分類。設(shè)定Error_Count≥1的數(shù)據(jù)集認(rèn)為是有缺陷的模塊，否則為無缺陷的。并將數(shù)據(jù)集中每個(gè)屬性值運(yùn)用公式（5）進(jìn)行標(biāo)準(zhǔn)化：

其中，x為屬性值A(chǔ)的原始值，x′為屬性A標(biāo)準(zhǔn)化后的值，minA是屬性A的最小值，maxA是屬性A的最大值。

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

為了驗(yàn)證本文模型的預(yù)測(cè)能力，實(shí)驗(yàn)采用數(shù)據(jù)集[11]PC1、CM1、JM1、KC3，從數(shù)據(jù)集中分別隨機(jī)抽取300、200、500、200個(gè)實(shí)驗(yàn)?zāi)K，采用十折交叉驗(yàn)證（10-fold CV）方法進(jìn)行實(shí)驗(yàn)，即將數(shù)據(jù)集隨機(jī)均分為10份，輪流將其中9份做訓(xùn)練，剩余的1份做預(yù)測(cè)，取10次實(shí)驗(yàn)度量值的平均值作為算法的運(yùn)行結(jié)果。

為了與傳統(tǒng)機(jī)器學(xué)習(xí)方法預(yù)測(cè)能力上作比較，本文采用準(zhǔn)確度、查全率、查準(zhǔn)率以及F1值來比較模型的預(yù)測(cè)能力。這些度量值首先要用到表2的交叉矩陣。

表2 二值分類交叉矩陣

評(píng)價(jià)標(biāo)準(zhǔn)指標(biāo)定義如下：

準(zhǔn)確度（accuracy）表示正確分類測(cè)試實(shí)例的個(gè)數(shù)占測(cè)試總實(shí)例個(gè)數(shù)的比例。計(jì)算公式如式（6）：

查準(zhǔn)率（precision）表示正確分類的正例數(shù)占分類為正例的實(shí)例個(gè)數(shù)的比例。計(jì)算公式如式（7）：

查全率（recall）表示正確分類的正例個(gè)數(shù)占實(shí)際正例個(gè)數(shù)的比例。計(jì)算公式如式（8）：

F1表示查全率和查準(zhǔn)率的調(diào)和平均。計(jì)算公式如式（9）：

其中，P為實(shí)際正例個(gè)數(shù)P=TP+FN,N為實(shí)際負(fù)例個(gè)數(shù)N=FP+TN,C為實(shí)驗(yàn)實(shí)例總數(shù)C=P+N。

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

圖2（a）～（d）分別為本文所提出的算法與BP神經(jīng)網(wǎng)絡(luò)和決策樹算法J48，在數(shù)據(jù)集JM1、CM1、KC3、PC1上運(yùn)行10次的平均值，這里分別從準(zhǔn)確度、查準(zhǔn)率、查全率和F1值的角度給出對(duì)比。

從圖2中可以看出：BP神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)總體較差，因?yàn)锽P網(wǎng)絡(luò)尚無一個(gè)有效的網(wǎng)絡(luò)結(jié)構(gòu)選擇方法，網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)參數(shù)選擇過分要求設(shè)計(jì)人員的經(jīng)驗(yàn)，且泛化能力較差?；跊Q策樹J48算法的預(yù)測(cè)模型的總體結(jié)果較好，但它受限于樣本容量限制，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)程序無法運(yùn)行。本文利用粒子群優(yōu)化算法在全局的尋優(yōu)能力，使之用于優(yōu)化神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值，使得預(yù)測(cè)的各項(xiàng)指標(biāo)優(yōu)于BP神經(jīng)網(wǎng)絡(luò)和決策樹J48算法，但每一粒子在給出位置及速度值，都要計(jì)算一次網(wǎng)絡(luò)，故本文方法的計(jì)算成本需要進(jìn)一步減少。

圖2 PSO-BP方法與傳統(tǒng)方法的比較

5 結(jié)論

本文的貢獻(xiàn)是針對(duì)軟件缺陷預(yù)測(cè)問題提出了一種新穎的基于PSO-BP的軟件缺陷預(yù)測(cè)模模型。在數(shù)據(jù)集PC1、KC3、CM1、JM1上分別進(jìn)行實(shí)驗(yàn)，并與J48和人工神經(jīng)網(wǎng)絡(luò)進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，該模型比傳統(tǒng)方法具有更好的預(yù)測(cè)效果，說明了模型的可行性。但是本文方法在優(yōu)化權(quán)值和閾值過程中需要較長(zhǎng)的時(shí)間，在今后的研究中將進(jìn)一步降低模型的運(yùn)行時(shí)間，提高模型的預(yù)測(cè)準(zhǔn)確率。

[1]Challagulla V U B，Bastani F B，Yen I L，et al.Empirical assessment of machine learning based software defect prediction techniques[C]//Proceedings of the 10th IEEE International Workshop on Object-Oriented Real Time Dependable Systems，Washington，DC，USA，2005：263-270.

[2]陸民燕.軟件可靠性工程[M].北京：國(guó)防工業(yè)出版社，2011.

[3]Feton N E，Martain N，William M，et al.Predicting software defects in varying development lifecycles using Bayesian nets[J]. Information and Software Technology，2007，49（1）：32-43.

[4]姜慧研，宗茂，劉相瑩.基于ACO-SVM的軟件缺陷預(yù)測(cè)模型的研究[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（6）：1148-1154.

[5]馮少榮，尚文俊.基于樣本選取的決策樹改進(jìn)算法[J].西南交通大學(xué)學(xué)報(bào)，2009，44（5）：643-647.

[6]Fast M，Assadi M，De S.Development and multi-utility of an ANN model for an industrial gas turbine[J].Applied Energy，2009，86（1）：9-17.

[7]Andreas W，Stefan W，Joachim W.Applying particle swarm optimization to software testing[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation，New York，NY，USA，2007：1121-1128.

[8]王青，伍書劍，李明樹.軟件缺陷預(yù)測(cè)技術(shù)[J].軟件學(xué)報(bào)，2008，19（7）：1565-1580.

[9]Wu W，Wang J，Cheng M.Convergence analysis of online gradient method for BP neural networks[J].Neural Networks，2011，24（1）：91-98.

[10]Lu X，Li H，Yuan X.PSO-based intelligent integration of design an control for one kind of curing process[J].Journal of Process Control，2010，20（10）：1116-1125.

[11]Chapman M，Callis P，Jackson W.Metrics data program[EB/OL]. NASAIV and V Facility（2004）.http：//mdp.ivv.nasa.gov.

YU Anlei,PI Dechang

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016

College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China

Software defect detection aims to automatically identify defective software modules that accelerates efficiently software test and improves the quality of a software system.Due to the application of traditional software prediction model being limited for its low accuracy and applicability,this paper puts forward a software prediction model based on PSO-BP,which employs Particle Swarm Optimization（PSO）to optimize weight and threshold value of BP.It uses cross-validation method as experiment method,and compares the results with other machine learning methods-BP and J48.The results show that PSO-BP has higher prediction accuracy.

software defect prediction;Artificial Neural Network（ANN）;Particle Swarm Optimization（PSO）

A

TP311

10.3778/j.issn.1002-8331.1208-0533

YU Anlei,PI Dechang.Software defect prediction model based on PSO-BP.Computer Engineering and Applications, 2013,49（7）：64-67.

江蘇省高?！扒嗨{(lán)工程”；江蘇省“333高層次人才培養(yǎng)工程”；航空科學(xué)基金（No.20111052010）。

于安雷（1988—），男，碩士研究生，主要從事數(shù)據(jù)挖掘的研究；皮德常（1971—），男，博士，教授，博導(dǎo)，主要從事數(shù)據(jù)挖掘與數(shù)據(jù)庫(kù)的研究。E-mail：anleiyu@yahoo.cn

2012-09-07

2012-10-30

1002-8331（2013）07-0064-04

CNKI出版日期：2012-11-13 http://www.cnki.net/kcms/detail/11.2127.TP.20121113.1525.002.html