基于PSO-BP的軟件缺陷預測模型

于安雷，皮德常

基于PSO-BP的軟件缺陷預測模型

于安雷，皮德常

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

軟件缺陷預測；神經網絡；粒子群優化

1 引言

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

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

J48是一種決策樹算法，嚴格意義上說是一種對ID3算法的改進[5]。通過信息增益率選擇屬性避免了偏向屬性值高的弊端；在建樹的過程中不斷剪枝；能夠對不完整數據進行處理以及連續屬性值的離散化處理；但是在構造樹的過程中需要對數據集進行多次的順序掃描和排序，導致算法低效。

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

為了提高軟件模塊缺陷預測模型的準確性，本文提出了基于PSO-BP的軟件缺陷預測模型，即運用粒子群優化算法優化BP神經網絡的權值和閾值，建立軟件缺陷預測模型，最后用于實驗預測軟件模塊是否為缺陷模塊。

2 相關工作

2.1 神經網絡

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

其中，m為輸出向量的維數，Yi，k是樣本i的第k維期望輸出值，Oi，k是樣本i的第k維實際輸出值，Ei為樣本i網絡誤差的平方。

2.2 粒子群優化算法

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

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

其中，n為樣本的數量，Ei由式計算，Fpindex為粒子的適應度，pindex的取值為 pindex=1，2，…，size，size為粒子群規模。

在粒子群優化過程中，粒子的速度和位置按如下公式（3）、（4）進行調整：

其中，D為粒子的速度與位置的向量維數，t為當前的迭代次數，w為慣性權重，c1和c2為加速常數，rand（）為隨機產生整數，pid為粒子i的當前最優位置的第d維分量，pgd為當前種群最優位置的第d維分量，為第t次迭代時，粒子i位置向量的第d維分量，為第t+1次迭代時，粒子i速度向量的第d維分量。

3 軟件缺陷預測模型的建立

3.1 軟件缺陷預測模型

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

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

（1）獲取軟件缺陷數據集。

（2）基于訓練樣本建立BP神經網絡的軟件缺陷預測模型，選擇sigmoid轉移函數，采用三層網絡結構。

（3）利用PSO算法優化BP網絡的權值和閾值。

（4）用測試樣例對模型進行分類預測。如果預測結果滿足終止條件，則停止優化得到優化的軟件預測模型；否則返回步驟3，繼續優化模型。

其中，終止條件為模型的預測準確率達到事先設定的閾值或者循環次數達到事先設定的最大值。

圖1 軟件缺陷預測模型圖

3.2 PSO優化BP神經網絡

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

（1）初始化粒子群。

（1.1）設定粒子群規模大小，粒子速度和位置以及向量的維數，其中，本文粒子規模為30，向量的維數與BP神經網絡的權值和閾值的個數之和相等；

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

（1.3）根據經驗，設定慣性權重w為0.3，加速常數c1和c2為2，設定最大進化代數Tmax。

（2）將粒子的速度和位置分量映射給BP神經網絡，按照公式計算每個粒子的適應度。

（3）按照如下式進行適應度的比較：

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

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

其中，current是粒子的當前適應值，pbestfit是粒子的個體最優值，gbestfit是種群全局最優適應值，pbest是粒子個體最優值，gbest是種群全局最優值，xi為粒子當前位置。

（4）根據式（3）和式（4）更新粒子的速度和位置，通常為讓粒子達到最佳全局尋優能力，設置速度閾值Vmax，做如下限制：

（5）將迭代次數與Tmax進行比較，如果大于Tmax，則終止算法，且當前的gbest為BP神經網絡優化的權值和閾值；否則跳至步驟2，繼續下一次迭代。

4 實驗分析

4.1 實驗數據

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

表1 實驗數據

本文根據數據集屬性Error_Count，對軟件模塊是否缺陷進行分類。設定Error_Count≥1的數據集認為是有缺陷的模塊，否則為無缺陷的。并將數據集中每個屬性值運用公式（5）進行標準化：

其中，x為屬性值A的原始值，x′為屬性A標準化后的值，minA是屬性A的最小值，maxA是屬性A的最大值。

4.2 實驗評價標準

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

為了與傳統機器學習方法預測能力上作比較，本文采用準確度、查全率、查準率以及F1值來比較模型的預測能力。這些度量值首先要用到表2的交叉矩陣。

表2 二值分類交叉矩陣

評價標準指標定義如下：

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

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

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

F1表示查全率和查準率的調和平均。計算公式如式（9）：

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

4.3 實驗結果與分析

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

從圖2中可以看出：BP神經網絡的預測總體較差，因為BP網絡尚無一個有效的網絡結構選擇方法，網絡結構和學習參數選擇過分要求設計人員的經驗，且泛化能力較差。基于決策樹J48算法的預測模型的總體結果較好，但它受限于樣本容量限制，需要對數據集進行多次的順序掃描和排序，當訓練集大得無法在內存容納時程序無法運行。本文利用粒子群優化算法在全局的尋優能力，使之用于優化神經網絡的權值和閾值，使得預測的各項指標優于BP神經網絡和決策樹J48算法，但每一粒子在給出位置及速度值，都要計算一次網絡，故本文方法的計算成本需要進一步減少。

圖2 PSO-BP方法與傳統方法的比較

5 結論

本文的貢獻是針對軟件缺陷預測問題提出了一種新穎的基于PSO-BP的軟件缺陷預測模模型。在數據集PC1、KC3、CM1、JM1上分別進行實驗，并與J48和人工神經網絡進行比較。實驗結果表明，該模型比傳統方法具有更好的預測效果，說明了模型的可行性。但是本文方法在優化權值和閾值過程中需要較長的時間，在今后的研究中將進一步降低模型的運行時間，提高模型的預測準確率。

[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].北京：國防工業出版社，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的軟件缺陷預測模型的研究[J].計算機學報，2011，34（6）：1148-1154.

[5]馮少榮，尚文俊.基于樣本選取的決策樹改進算法[J].西南交通大學學報，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]王青，伍書劍，李明樹.軟件缺陷預測技術[J].軟件學報，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

南京航空航天大學 計算機科學與技術學院，南京 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.

江蘇省高校“青藍工程”；江蘇省“333高層次人才培養工程”；航空科學基金（No.20111052010）。

于安雷（1988—），男，碩士研究生，主要從事數據挖掘的研究；皮德常（1971—），男，博士，教授，博導，主要從事數據挖掘與數據庫的研究。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