基于粗糙集-支持向量機的軟件缺陷預測*

孟 倩，馬小平

(1.中國礦業大學信電學院，江蘇 徐州 221008；2.江蘇師范大學計算科學與技術學院,江蘇 徐州 221116)

基于粗糙集-支持向量機的軟件缺陷預測*

孟 倩1,2，馬小平1

(1.中國礦業大學信電學院，江蘇 徐州 221008；2.江蘇師范大學計算科學與技術學院,江蘇 徐州 221116)

軟件缺陷預測已成為軟件工程的重要研究課題，構造了一個基于粗糙集和支持向量機的軟件缺陷預測模型。該模型通過粗糙集對原樣本集進行屬性約減，去掉冗余的和與缺陷預測無關的屬性，利用粒子群對支持向量機的參數做選擇。實驗數據來源于NASA公共數據集，通過屬性約減，特征屬性由21個約減為5個。實驗表明，屬性約減后，Bayes分類器、CART樹、神經網絡和本文提出的粗糙集—支持向量機模型的預測性能均有所提高，本文提出的粗糙集支持向量機的預測性能好于其他三個模型。

粗糙集；支持向量機；軟件缺陷；預測；粒子群

1 引言

軟件已經成為影響國民經濟、軍事、社會生活的重要因素。高可靠性和復雜的軟件系統非常依賴于所采用軟件的可靠性。根據ISO 9000的定義，軟件缺陷(Defect)是指“未滿足與預期或者規定用途有關的要求”，是導致軟件系統出錯、失效、崩潰甚至機毀人亡的潛在根源[1]。軟件缺陷預測技術是根據歷史數據以及已經發現的缺陷等軟件度量數據，預測哪些模塊有出錯傾向，對軟件開發者合理配置資源，從而降低研發成本、縮短產品開發周期和提高軟件質量起到重要作用。

軟件缺陷預測本質上是一個模式識別的過程，它的核心是分類，目前用于軟件缺陷預測的方法有Bayes分類器[2]、分類回歸樹[3]、聚類分析[4]和神經網絡[5]等。由于軟件缺陷受到多種復雜度度量屬性的綜合作用， 至今尚沒有一種軟件缺陷預測的通用的分類模型。近年來，用支持向量機SVM(Support Vector Machine)來實現基于分類問題的預測已經成為研究熱點。SVM是一種通用的前饋神經網絡，其核心是經驗風險最小化原則，有效地解決了小樣本、高維數、非線性等學習問題，它由Vapnik V N在1992年首次提出[6]，可以用于模式分類和非線性回歸。近年來，各國學者開始用SVM進行軟件可靠性方面的預測。國際上，Gray D等人[7]利用支持向量機對軟件缺陷進行預測取得了不錯的效果；Mishra B等人[8]提出用于軟件可靠性預測的模糊支持向量機。國內崔正斌等人[9]提出了遺傳優化支持向量機軟件可靠性模型；張艷等人[10]將支持向量機回歸模型用于測控軟件故障預測。

作為一種新的學習機器，SVM也存在一些有待完善的地方，SVM的性能與其參數的選擇密切相關，而其參數選取沒有理論上的指導。本文應用粒子群PSO(Particle Swarm Optimization)來進行支持向量分類機參數選擇。SVM方法另一不足之處是，由于SVM在訓練中需要進行大量的矩陣運算，當處理的數據量過大時，SVM的訓練時間過長、速度變慢[11]。波蘭科學院院士Pawlak Z教授于1982 年提出的粗糙集理論RS(Rough Sets)是繼概率論、模糊集、證據理論之后的又一個刻畫不完整性和不確定性的數學工具，它不需要任何先驗知識，可分析出信息間相互關系，可以在保持分類能力不變的條件下進行屬性約簡,達到數據信息精煉化的目的[12]。

為了提高軟件缺陷預測能力，本文融合RS方法和SVM方法，建立一種基于粗糙集-支持向量機(RS-SVM)的軟件缺陷預測模型，在不改變樣本分類質量的條件下，運用粗糙集屬性約簡方法作為預處理器對樣本進行降維處理。通過屬性約簡，本文發現可以僅使用軟件度量的少量特征屬性(McCabe環路復雜度、McCabe設計復雜度、操作符種類、操作數種類和總代碼行數)來進行軟件缺陷預測，這樣不但可以減少樣本的維數，縮短SVM樣本訓練時間，還可以降低數據采集難度，并提高分類器性能。屬性約簡后利用PSO算法對SVM進行參數優化，并用SVM方法建立軟件缺陷預測模型。

2 原理與算法

2.1 粗糙集

屬性約簡是粗糙集理論的核心內容之一，屬性約簡就是在保持知識庫分類能力不變的條件下，刪除其中不相關或不重要的屬性。

2.2 支持向量機

SVM的基本思想是非線性映射將輸入向量映射到一個高維特征空間，在高維特征空間尋求最優劃分超平面，使得盡可能多地將2 類數據點正確分開，同時使分類間隔最大[6]。

對于給定樣本點：(xi,yi)，i=1,…,n，xi∈Rd，yi∈{+1,-1}。xi為輸入特征，yi為決策屬性。構造決策函數最終可以轉化為一個典型的二次規劃問題,即在約束條件:

(1)

之下,求下列函數最小值:

(2)

其中，w為分類面權系數向量；b為分類域值；C是懲罰系數,C>0；ξ是訓練樣本關于分離面的偏差。引入Lagrange乘子αi，得到其對偶形式：

(3)

其中，0≤αi≤C,i=1,…,l。

將輸入向量映射到一個高維特征空間,引入滿足Mercer條件的K(xi,x)核函數,最終得到決策函數為 ：

(4)

這就是支持向量機，式(4)中具有非0值的ai對應的向量支撐了最優分類面，因此成為支持向量。目前常用的核函數有線性核函數、多項式核函數、徑向基核函數和Sigmoid核函數。

2.3 粒子群算法

粒子群優化算法[13]中，優化問題的每個解對應搜索空間的一個粒子，記為:

pi=(pi1,pi2,…,pin),i=1,2,…,m

(5)

其中,m為粒子的個數，n為粒子的維數。每個粒子有一個速度vi=(vi1,vi2,…,vin)，決定它的方向和位置。粒子群優化算法首先初始化粒子群，計算出每個粒子的適應值，然后通過迭代搜索最優解。在每次迭代中，對于每個粒子，粒子通過追蹤兩個極值來更新自己：一個是粒子自己找到的最優解，稱為個體極值；另一個是整個粒子群目前找到的最優解，稱為全局極值。當找到個體極值和全局極值后,粒子按式(6) 和式(7) 來更新自己的速度和位置：

(6)

(7)

3 RS-SVM軟件缺陷預測建模

本文建立一種基于RS-SVM的軟件缺陷預測模型，如圖1所示。整個分類過程分成三個階段：首先, 采用粗糙集理論對樣本進行預處理，以去掉冗余屬性，并剔除無效數據。軟件缺陷特征屬性之間存在著一定的相關性，經過屬性約簡不僅可消除指標間的信息重疊，還起到降維的作用，提高了模型運行速度，也大大降低了缺陷數據采樣的工作量。然后，利用粒子群對支持向量機的參數進行優化，尋出最優參數。最后，利用最優參數建立SVM訓練模型，對經過預處理的樣本集進行分類訓練和預測。

Figure 1 Prediction model based on RS-SVM

4 RS-SVM的軟件缺陷預測實驗

4.1 實驗環境及實驗數據來源

根據前述思想，本文利用臺灣ChangChih-chung等人[14]開發的LIBSVM工具箱，在MatlabR2009b下編寫了粗糙集和粒子群PSO算法程序。

美國國家航空航天局NASA(NationalAeronautics&SpaceAdministration)較早就啟動了軟件缺陷預測技術的研究，并基于航空系統軟件開展了軟件模塊的度量數據庫項目MDP(MetricDataProgram)，為缺陷預測研究提供數據支撐,MDP原數據集可從網址http://mdp.ivv.nasa.gov下載。本實驗數據來源于MDP的JM1數據集,JM1數據集從一個用C++語言編寫的地面預測系統項目中得到，共有10 878個模塊，每個模塊的22個屬性中有21個特征屬性和1個目標屬性，21個特征屬性中5個屬性來源于代碼度量，3個來源于McCabe度量，12個來源于或派生于Halstead度量，1個屬性是模塊分支數。

4.2 不平衡數據和臟數據處理

軟件缺陷數據集是類不平衡的，在JM1數據集中，有缺陷的模塊有2 102個，無缺陷的模塊有8 776個。WeissG等人[15]研究了訓練數據集的類分布與分類器的分類性能之間的關系。結果顯示,相對平衡的類分布通常會得到較理想的結果。

NASA軟件度量數據集已經被廣泛應用于研究，數據集本身可能存在的問題近期引起了一些學者的注意，ShepperdM[16]指出,NASA的數據集中存在著大量的“重復數據”和“矛盾數據”這種臟數據，已經嚴重影響了軟件缺陷預測的結果。

基于以上原因，本文對JM1數據集進行了刪除臟數據的處理，并最終隨機提取1 200個數據作為實驗樣本，有缺陷樣本和無缺陷樣本各占50%。

4.3 粗糙集屬性約簡

在MatlabR2009b下實現粗糙集屬性信息熵約簡算法，得出屬性決策表的兩個約簡：R1={1,4,6,8,9,11,21}和R2={5,6,19,20,21}，其中的數字為原數據集中屬性序號。這樣，條件屬性由21個分別約簡為7個和5個，下文分別稱為屬性約簡1和屬性約簡2，將分別做實驗測試其性能。

4.4 評價指標

本文實驗用準確度(Accuracy)、精確度(Precision)、查全率(Recall)和F-度量(F-Measure)來評價和比較預測模型，這些度量都來源于混淆矩陣，如表1所示。

Table 1 Confusion matrix

Accuracy：預測結果和實際結果一致的模塊在整個測試集合中的比例。

Accuracy=(TP+TN)/(TP+FN+FP+TN)

(8)

Precision：預測為有缺陷模塊中實際為有缺陷模塊比例。

Precision=TP/(TP+FP)

(9)

Recall：有缺陷模塊被正確識別的比例。

Recall=TP/(TP+FN)

(10)

F-Measure：是Precision和Recall的調和平均數。

F-Measure=2/((1/precision)+(1/Recall))

(11)

4.5 基于PSO的SVM參數的選擇

基于2.3節介紹的粒子群優化算法及其在Matlab R2009b下的實現，進行SVM最優參數選擇，本文采用徑向基核函數，需要優化的參數有懲罰系數C和核參數γ。

以1-Accuracy的值作為粒子群的適應值的評價函數， 1-Accuracy的值越小越好。

設置粒子群參數：群體規模為20，粒子向量維數為3，加速因子C1=2，C2=2，最大迭代次數為300。對未經過屬性約簡的SVM模型，粗糙集屬性約簡1為特征屬性的RS-SVM1和約簡2為特征屬性的RS-SVM2模型分別經過PSO優化，最優參數見表2 。

Table 2 Optimization of PSO parameters

4.6 實驗結果及分析

將特征值歸一化到[-1，1]，消除了因量綱不同可能引發的影響。本文采用10折交叉驗證的方法，樣本集被隨機等分成10個子集，任取其中一個子集作為測試樣本集，其余9個子集作為訓練樣本集，實驗總做10次，以10次實驗的性能指標平均值來評價一個算法的性能。將未經過屬性約簡的SVM模型、RBF神經網絡、CART樹、Bayes分類器分別經過10折交叉驗證，實驗結果比較如表3所示。

Table 3 Experimental results of models with all attribute

把由粗糙集約簡R1為特征屬性的RBF神經網絡、CART樹、Bayes分類器分別稱為RS-RBF1、RS-CART1和RS-Bayes1，這三個模型連同RS-SVM1模型，分別經過10折交叉驗證，實驗結果比較如表4所示。

Table 4 Experimental results of models with attribute reduction 1

把由粗糙集約簡R2為特征屬性的RBF神經網絡、CART樹、Bayes分類器分別稱為RS-RBF2、RS-CART2和RS-Bayes2，這三個模型連同RS-SVM2分別經過10折交叉驗證，實驗結果比較如表5所示。

Table 5 Experiment results of models with attribute reduction 2

從表3～表5可以看出，不論粗糙集屬性約簡前還是約簡后，Bayes分類器預測效果都比較差，Bayes分類器假設特征向量的所有分量之間是獨立的，在缺陷預測中，特征屬性之間不是絕對獨立的，所以使用此模型得到的分類結果會比較差。基于CART樹和RBF神經網絡方法的預測性能都明顯好于Bayes方法，但當CART樹分類回歸樹劃分得太細時,會對噪聲數據產生過度擬合的問題。RBF神經網絡結構選擇無統一理論指導，預測效果都比SVM略差一點。SVM具有嚴格的理論和數學基礎，基于結構風險最小化原則，保證學習機器具有良好的泛化能力，需要設定的參數相對較少，引入PSO進行參數優化，提高了參數選擇的效率和模型預測性能。

粗糙集屬性約簡后，四種模型預測性能都有所提高，總的來看，屬性簡減2的預測性能更好。原樣本數據含有大量冗余特征屬性，21個特征屬性中某些屬性是由其他屬性通過數學運算計算出來的，如大部分Halstead度量屬性，有些屬性對缺陷預測是無關緊要的，如一些代碼度量屬性。

性能比較好的屬性約簡2中的屬性有5個，分別是McCabe環路復雜度(CYCLOMATIC_COMPLEXITY)、McCabe設計復雜度(DESIGN_COMPLEXITY)、操作符種類(NUM_UNIQUE_OPERANDS)、操作數種類(NUM_UNIQUE_OPERATORS)和總代碼行數(LOC_TOTAL)。根據軟件工程的知識可知，這5個屬性相互之間基本不相關，并且是影響軟件可靠性的重要屬性。實驗也表明，對原屬性集中21個特征屬性通過粗糙集約簡掉冗余特征后只保留5個特征屬性，四種模型缺陷預測性能不但沒有降低反而都有所提高。

5 結束語

本文將粗糙集屬性約簡方法引入到軟件缺陷預測中。原軟件度量特征屬性中含有大量冗余屬性，通過粗糙集屬性約簡，僅保留了少量特征屬性，不但提高了軟件缺陷預測性能，而且大大減少采樣工作量，提高了工作效率。本文利用PSO算法對SVM進行參數選擇并用SVM算法對處理過的樣本集進行軟件缺陷預測，通過實驗與其他軟件預測方法比較，表明本文提出的方法具有更好的預測效果。下一步工作將研究如何進一步提高軟件缺陷預測的準確度。

[1] Wang Qing,Wu Shu-jian,Li Ming-shu.Software defect prediction[J].Journal of Software,2008,19(7):1565-1580.(in Chinese)

[2] Muson J C,Khoshgoftaar T M. The detection of fault-prone programs[J]. IEEE Transactions on Software Engineering,1992,18(5):423-433.

[3] Briand L C, Basili V, Hetmanski C J. Developing interpretable models with optimized set reduction for identifying high-risk software components[J].IEEE Transactions on Software Engineering,1993,19(11):1028-1044.

[4] Zhong S,Khoshgoftaar T M,Seliya N.Analyzing software measurement data with clustering techniques[J]. IEEE Intelligent Systems,2004,19(2):20-27.

[5] Qiao Hui,Zhou Yan-zhou,Shao Nan,et al. Research of software reliability prediction model on AGA-LVQ[J]. Computer Science,2013,40(1):179-182. (in Chinese)

[6] Vapnik V N. The nature of statistical learning theory[M]. New York:Springer-Verlag, 1995.

[7] Gray D, Bowes D, Davey N, Neill D,et al. Using the support vector machine as a classification method for software defect prediction with static code metrics∥[C]Proc of the 11th International Conference on Engineering Applications of Neural Networks,2009:223-234.

[8] Mishra Bharavi,Shukla K K. Support vector machine based fuzzy classification model for software fault prediction[C]∥Proc of the 5th Indian International Conference on Artificial Intelligence(IICAI 2011),2011:693-708.

[9] Cu Zheng-bin,Tang Guang-ming,Yue Feng. Software reliability prediction model based on support vector machine optimized by genetic algorithm[J].Computer Engineering and Applications,2009,45(36):71-74. (in Chinese)

[10] Zhang Yan,Ren Zi-hui.SVM-based forecasting methods for software fault[J].Journal of Chinese Computer Systems,2010,31(7):1380-1384. (in Chinese)

[11] Sanchez V D. Advanced support vector machines and kernel method[J]. Neurocomputing,2003, 55(1-2):5-20.

[12] Pawlak Z. Rough Sets:Theoretical aspects of reasoning about data(theory and decision library D)[M].Boston:Kluwer Academic Publishers,1992.

[13] Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]∥Proc of the 6th International Symposium on Micro Machine and Human Science, 1995:39-43.

[14] Chang Chih-chung,Lin Chih-jen.LIBSVM:A library for support vector machines[EB/OL].[2009-10-09].http://www.csie.ntu.edu.tw/～cjlin/libsvm.

[15] Weiss G, Provost F. Learning when training data are costly: The effect of class distribution on tree induction[J]. Journal of Artificial Intelligence Research,2003,19(1):315-354.

[16] Shepperd M,Song Qin-bao,Sun Zhong-bin,et al.Data quality: Some comments on the NASA software defect data sets[J]. IEEE Transactions on Software Engineering,2013,39(9):1208-1215.

附中文參考文獻：

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

[5] 喬輝，周雁舟，邵楠，等. 基于AGA-LVQ神經網絡的軟件可靠性預測模型研究[J]. 計算機科學，2013,40(1):179-182.

[9] 崔正斌,湯光明,樂峰.遺傳優化支持向量機的軟件可靠性預測模型[J].計算機工程與應用,2009,45(36)：71-74.

[10] 張艷，任子暉.一類基于支持向量機的軟件故障預測方法[J].小型微型計算機系統，2010,31(7):1380-1384.

MENG Qian,born in 1970,PhD candidate,associate professor,her research interests include database technology, and software engineering.

馬小平(1961-),男,四川綿陽人，博士，教授，研究方向為控制理論及應用。E-mail:xpma@cumt.edu.cn

MA Xiao-ping,born in 1961,PhD,professor,his research interest includes control theory and applications.

高性能計算專欄約稿

一、刊物簡介

《計算機工程與科學》是由國防科技大學計算機學院主辦的中國計算機學會會刊，是國內外公開發行的計算機類綜合性學術刊物。本刊已先后被列為中文核心期刊、中國科技信息研究所中國科技論文統計分析源期刊(中國科技核心期刊)、中國科學引文數據庫來源期刊(CSCD核心期刊)、中國學術期刊(光盤版)全文入編期刊、中國期刊網全文入編期刊、中國學術期刊綜合評價數據庫來源期刊。

二、征稿范圍(但不限于)

目前，國內高性能計算的研究方興未艾，為更好地宣傳目前國內高性能計算領域的研究和應用現狀，我刊常年設有高能性能計算專欄，重點是面向國內高性能計算領域的研究和應用。包括：

(1)系統研制技術：體系結構、系統軟件、軟件并行化、多核編程、編譯技術、GPU計算、低功耗技術、系統優化技術。

(2)系統應用：EDA設計仿真、CAE、數值計算、計算化學、計算物理、材料設計、量子力學、分子動力學、流體力學、工業設計、圖像渲染、生物信息、生命科學、氣象、天文、金融、石油勘探、工程計算、地震資料處理、集群管理、并行應用軟件開發(MPI、OpenMP、CUDA)、Linpack測試研究、超算服務等。

三、投稿要求

(1)投稿方式：采用“計算機工程與科學在線投稿系統”(http://www.joces.org.cn)投稿。投稿時請在備注欄中注明“高能性能計算專欄”字樣。

(2)稿件格式：參照《計算機工程與科學》下載中心的排版規范(網站上提供了論文模版，可下載)。

(3)投稿文章未在正式出版物上發表過，也不在其他刊物或會議的審稿過程中，不存在一稿多投現象；保證投稿文章的合法性(無抄襲、剽竊、侵權等不良行為)。

(4)其他事項請參閱投稿須知： http://www.joces.org.cn/CN/column/column291.shtml

(5)專刊投稿文章按《計算機工程與科學》正常標準收取審稿費和版面費，但將會優先發表；發表之后，將按《計算機工程與科學》的標準支付稿酬，并贈送樣刊。

《計算機工程與科學》編輯部

Software defect prediction usingrough sets and support vector machine

MENG Qian1,2,MA Xiao-ping1

(1.School of Information and Electrical Engineering,China University of Mining and Technology,Xuzhou 221008;2. College of Computer Science and Technology,Jiangsu Normal University,Xuzhou 221116,China)

The prediction of software defects has been an important research topic in the field of software engineering. The paper focuses on the problem of defect prediction. A classification model for predicting software defects based on the integration of rough sets and support vector machine model (RS-SVM) is constructed. Rough sets work as a preprocessor in order to remove redundant information and reduce data dimensionality before the sample data are processed by support vector machine. As a solution to the difficulty of choosing parameters, the particle swarm optimization algorithm is used to choose the parameters of support vector machines. The experimental data are from the open source NASA datasets. The dimensions of the original data sets are reduced from 21 to 5 by rough sets. Experimental results indicate that the prediction performances of Bayes classifier, CART tree, RBF neural network and RS-SVM are all improved after the dimension of the original data sets are reduced from 21 to 5 by rough sets. Compared with the above three models, RS-SVM has a higher prediction performance.

rough sets;support vector machine;software defect;prediction;particle swarm optimization

1007-130X(2015)01-0093-06

2014-08-12;

2014-10-19基金項目：國家自然科學基金資助項目(61303183)；江蘇省自然科學基金資助項目(BK20130204);高等學校博士學科點專項科研基金資助項目(20120095120023)

TP311.5

A

10.3969/j.issn.1007-130X.2015.01.014

孟倩(1970-),女,江蘇徐州人，博士生，副教授，研究方向為數據庫技術和軟件工程。E-mail:mqzzy2000@126.com

通信地址：221116 江蘇省徐州市銅山新區上海路101號江蘇師范大學計算機學院

Address:College of Computer Science and Technology,Jiangsu Normal University,101 Shanghai Rd,Tongshan New District,Xuzhou 221116,Jiangsu,P.R.China