于安雷，皮德常

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

于安雷，皮德常

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

其中，n為樣本的數(shù)量，Ei由式計算，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（）為隨機產(chǎn)生整數(shù)，pid為粒子i的當(dāng)前最優(yōu)位置的第d維分量，pgd為當(dāng)前種群最優(yōu)位置的第d維分量，為第t次迭代時，粒子i位置向量的第d維分量，為第t+1次迭代時，粒子i速度向量的第d維分量。

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

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

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

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

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

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

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

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

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

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

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

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

（1）初始化粒子群。

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

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

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

（2）將粒子的速度和位置分量映射給BP神經(jīng)網(wǎng)絡(luò)，按照公式計算每個粒子的適應(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是粒子的個體最優(yōu)值，gbestfit是種群全局最優(yōu)適應(yīng)值，pbest是粒子個體最優(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 實驗分析

4.1 實驗數(shù)據(jù)

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

表1 實驗數(shù)據(jù)

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

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

4.2 實驗評價標(biāo)準(zhǔn)

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

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

表2 二值分類交叉矩陣

評價標(biāo)準(zhǔn)指標(biāo)定義如下：

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

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

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

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

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

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

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

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

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

5 結(jié)論

本文的貢獻(xiàn)是針對軟件缺陷預(yù)測問題提出了一種新穎的基于PSO-BP的軟件缺陷預(yù)測模模型。在數(shù)據(jù)集PC1、KC3、CM1、JM1上分別進(jìn)行實驗，并與J48和人工神經(jīng)網(wǎng)絡(luò)進(jìn)行比較。實驗結(jié)果表明，該模型比傳統(tǒng)方法具有更好的預(yù)測效果，說明了模型的可行性。但是本文方法在優(yōu)化權(quán)值和閾值過程中需要較長的時間，在今后的研究中將進(jìn)一步降低模型的運行時間，提高模型的預(yù)測準(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].北京：國防工業(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ù)測模型的研究[J].計算機學(xué)報，2011，34（6）：1148-1154.

[5]馮少榮，尚文俊.基于樣本選取的決策樹改進(jìn)算法[J].西南交通大學(xué)學(xué)報，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ù)測技術(shù)[J].軟件學(xué)報，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é) 計算機科學(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ù)庫的研究。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