一種基于Logicboost的軟件缺陷預(yù)測方法

摘 ?要： 針對軟件缺陷預(yù)測中對不平衡數(shù)據(jù)分類精度較低的問題，提出了一種新的基于LogitBoost集成分類預(yù)測算法，使用SMOTE方法對原始數(shù)據(jù)集進行平衡處理，然后使用隨機森林算法作為弱分類器算法進行分類預(yù)測，最后使用LogitBoost算法以加權(quán)方式集成各弱分類器的結(jié)果。通過在NASA MDP基礎(chǔ)數(shù)據(jù)集上驗證得出本文提出的分類預(yù)測算法比數(shù)據(jù)集均衡處理前準(zhǔn)確率高出0.1%-11%，同時在均衡處理后比KNN算法平均高出0.9%，比SVM算法平均高出0.4%，比隨機森林算法平均高出0.1%。

關(guān)鍵詞： 不平衡數(shù)據(jù);LogitBoost集成算法;隨機森林算法;軟件缺陷預(yù)測

中圖分類號： TP206+.3 ? ?文獻標(biāo)識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.08.019

本文著錄格式：張洋. 一種基于Logicboost的軟件缺陷預(yù)測方法[J]. 軟件，2019，40（8）：7983

【Abstract】： Aiming at the problem of low classification accuracy of unbalanced data in software defect prediction， a new integrated classification prediction algorithm based on LogitBoost is proposed. SMOTE method is used to balance the original data set， then random forest algorithm is used as weak classifier algorithm for classification prediction. Finally， the results of weak classifiers are integrated in a weighted way using LogitBoost algorithm. Through the verification on NASA MDP basic data sets， the classification prediction algorithm proposed in this paper is 0.1%-11% higher than that before data balancing， 0.9% higher than that of KNN algorithm， 0.4% higher than that of SVM algorithm and 0.1% higher than that of random forest algorithm.

【Key words】： Unbalanced data; Logitboost integration algorithms; Random forest algorithm; Software defect prediction

0 ?引言

軟件缺陷是指計算機軟件或程序中存在的某種破壞正常運行能力而導(dǎo)致的問題和錯誤或者其他隱藏的功能缺陷。2011年“甬溫線”列車因控制軟件設(shè)計缺陷導(dǎo)致列車追尾事故造成了大量人員傷亡、2012年美國騎士資本集團的交易軟件缺陷問題造成股票交易異常損失近4.4億美元、2019年波音737MAX因軟件缺陷導(dǎo)致多起墜機事件，大量的人員傷亡和財產(chǎn)損失無不在警示人們對軟件質(zhì)量的重視，也進一步促進了對軟件缺陷預(yù)測的研究。

因為軟件缺陷客觀存在，而且某些隱藏較深的缺陷不容易發(fā)現(xiàn)，而一個軟件缺陷如果在開發(fā)早期發(fā)現(xiàn)那么解決該問題的成本會比較小，而越往后解決缺陷問題的成本會逐漸增加，而開發(fā)完成后才發(fā)現(xiàn)的缺陷最嚴(yán)重的情況是有可能項目需要重新開發(fā)，所以研究軟件缺陷問題的關(guān)鍵就是如何最大程度的發(fā)現(xiàn)軟件或程序中的隱藏缺陷，而開發(fā)一款高質(zhì)量的算法讓其能判定軟件中的大部分缺陷是解決當(dāng)前問題的重中之重[1]。

1 ?相關(guān)研究

軟件缺陷預(yù)測方法分為靜態(tài)軟件缺陷預(yù)測方法和動態(tài)軟件缺陷預(yù)測方法[2]，本文研究內(nèi)容屬于靜態(tài)軟件預(yù)測方法。目前針對靜態(tài)軟件預(yù)測采用的方法有神經(jīng)網(wǎng)絡(luò)[3]、支持向量機（SVM）[4]、決策樹方法[5]、貝葉斯網(wǎng)絡(luò)方法[6]、隨機森林算法[7]、關(guān)聯(lián)規(guī)則挖掘方法[8]、集成學(xué)習(xí)方法[9]等方法，其中神經(jīng)網(wǎng)絡(luò)方法是一種非監(jiān)督分類方法依賴傳統(tǒng)方法尋找神經(jīng)網(wǎng)絡(luò)權(quán)值，所以比較難找到全局最優(yōu)解;SVM方法能較好的應(yīng)對不平衡數(shù)據(jù)和數(shù)據(jù)多維的情況，但容易受到噪聲樣本數(shù)據(jù)的影響;其他分類算法因為數(shù)據(jù)不平衡的問題導(dǎo)致預(yù)測精度比較低;集成學(xué)習(xí)方法集成了多個弱分類器的方法以構(gòu)成強分類器，所以較單個弱分類器分類預(yù)測性能較高，是目前比較好的一種缺陷預(yù)測方法。因為以上很多分類預(yù)測算法都受到數(shù)據(jù)集不平衡的影響，所以針對這個問題有非常多的學(xué)者進行了研究，而且在軟件缺陷預(yù)測研究領(lǐng)域中不平衡數(shù)據(jù)集對軟件缺陷預(yù)測方法的效果影響很大[10]，目前針對數(shù)據(jù)集不平衡的研究有多種方法，有向上過采樣補充少數(shù)樣本方法[11]，有向下欠采樣減少多數(shù)樣本方法[12]，還有同時使用過采樣和欠采樣相結(jié)合減少多數(shù)類樣本增加少數(shù)類樣本的方法[13]等。本文在研究了以上多種方法后發(fā)現(xiàn)采用向上過采樣的方法較其他兩種方法能保留更多原始樣本數(shù)據(jù)信息并且在軟件缺陷預(yù)測方法中分類預(yù)測效果也比較好，所以本文的實驗過程都是在使用SMOTE方法[11]（Synthetic Minority Oversampling Technique）對數(shù)據(jù)集進行預(yù)處理的基礎(chǔ)上進行實驗，然后在此基礎(chǔ)上使用新提出以隨機森林分類算法作為基分類算法并結(jié)合LogicBoost[14]邏輯集成算法集成多個基分類算法進行分類預(yù)測的方法進行驗證并與其他幾類常見的分類預(yù)測算法進行了比較，同時為驗證對數(shù)據(jù)集使用過采樣平衡處理后算法的性能是否提高本文還對各種方法在原始不平衡數(shù)據(jù)集和平衡后數(shù)據(jù)集的分類預(yù)測結(jié)果進行比較。為更有效的評價分類結(jié)果，本文選擇了準(zhǔn)確率、AUC值、G-mean值三個業(yè)界認(rèn)可的有效性能評價指標(biāo)對結(jié)果進行評價，并使用NASA MDP數(shù)據(jù)集[15]完成整個實驗。

2 ?基于LogicBoost的軟件預(yù)測方法

2.1 ?SMOTE采樣

數(shù)據(jù)集不平衡的問題一直是分類問題最大的困擾，而對于需要預(yù)測的有缺陷的數(shù)據(jù)集總是少數(shù)，而且在某些數(shù)據(jù)集中占比非常低，為解決樣本少，特征缺失的問題，Chawla等人提出了SMOTE方法，該方法通過計算少數(shù)樣本k個相鄰樣本間的歐式距離得到最近鄰的k個樣本，然后生成0到1之間的隨機數(shù)與隨機抽取的近鄰樣本合并生成新樣本，重復(fù)這個過程直到樣本間達到平衡。其具體生成生新樣本的方法如式1所示，其中Pj表示新樣本，N表示生成樣本數(shù)量。

2.2 ?LogicBoost算法

Logitboost算法是由Friedman等人提出的一種改進型Boosting算法[16]，是一種集成各弱分類器結(jié)果變成強分類器的集成分類算法。LogitBoost使用加權(quán)最小二乘法估計分類函數(shù)并以加權(quán)的方式對基礎(chǔ)分類器的結(jié)果進行評價，如果分類結(jié)果出現(xiàn)錯誤則會加大其權(quán)重，相反權(quán)重減小，通過迭代多次每次給不同的基礎(chǔ)分類器重新計算權(quán)重，最后采用加權(quán)的方式合成各基礎(chǔ)分類器的分類結(jié)果作為最終分類結(jié)果，具體現(xiàn)過程如下：

（1）給定一個測試集（xi1， xi2…xin， yi），yi={Y， N}表示有缺陷和無缺陷兩類。

（2）給樣本賦予權(quán)重wi=1/N， i=1…N，使得每個樣本被抽到的概率一致，然后使用基礎(chǔ)分類器，根據(jù)權(quán)重以迭代的方式建立預(yù)測模型，每一輪提升都會給錯誤分類的樣本增加權(quán)重，正確的減小權(quán)重，其中F（x）=0， Pi=1/2。

（3）假定算法迭代M次，m=1，2，…，M

2.3 ?隨機森林算法

隨機森林是由Breiman提出的一種基于Bagging[17]算法與隨機子空間算法[18]的集成算法，其基本思想是多個決策樹對同一個測試數(shù)據(jù)集進行分類建立隨機森林決策樹，然后在分類預(yù)測過程中通過多個決策樹投票的方式統(tǒng)計所有決策樹的結(jié)果來最終判定樣本的分類結(jié)果。隨機森林的算法主要優(yōu)點是算法的準(zhǔn)確性比單個決策樹都高，而且每棵決策樹選擇分類屬性可以隨機，同時每棵決策樹選擇測試數(shù)據(jù)集也可以隨機，這兩個隨機讓算法減少了算法產(chǎn)生過擬合的結(jié)果同時也降低了噪聲樣本數(shù)據(jù)的影響。算法的實現(xiàn)過程如下：

輸入：訓(xùn)練樣本數(shù)據(jù)集，特征集合

輸出：隨機森林決策樹

（1）隨機選擇訓(xùn)練樣本數(shù)據(jù)集。對于每棵樹而言，隨機且有放回地從訓(xùn)練集中的抽取N個訓(xùn)練樣本作為該樹的訓(xùn)練集。

（2）隨機選擇訓(xùn)練樣本的特征數(shù)。假定樣本的特征維度為M，指定一個常數(shù)m<

（3）每棵樹都盡最大程度的生長，并且沒有剪枝過程。

（4）所有生成樹都停止生長后，隨機森林決策樹構(gòu)建完成。

2.4 ?基于LogicBoost的軟件預(yù)測算法

輸入：測試數(shù)據(jù)屬性集{A1，A2…An}以及樣本實例數(shù)據(jù)

輸出：輸出分類預(yù)測結(jié)果和成功率

（1）對原數(shù)據(jù)集進行清理，清楚重復(fù)項，以消除重復(fù)項對測試結(jié)果過擬合的影響。

（2）根據(jù)SMOTE規(guī)則對數(shù)據(jù)集進行數(shù)據(jù)樣本隨機過采樣增加少數(shù)類樣本，采樣比例=（無缺陷實例數(shù)/有缺陷實例數(shù)）-1，設(shè)置k=5，即通過計算樣本間的歐式距離找到最鄰近的5個樣本，然后使用隨機的方式循環(huán)地選擇近鄰樣本乘以隨機數(shù)增加少數(shù)樣本使數(shù)據(jù)集均衡。

（3）構(gòu)建隨機森林算法的決策樹模型，隨機森林算法默認(rèn)的基分類算法為分類回歸樹，設(shè)置特征選擇數(shù)量隨機生成，通過多次實驗得到選擇訓(xùn)練樣本數(shù)量在70%的時候效果最好，同時設(shè)置生成樹無限生長直到葉子只包含一個類別的樣本后停止生長。

（4）建立LogitBoost計算模型，生成樣本權(quán)重矩陣，并生成工作變量，建立基于最小二乘法的擬合函數(shù)估計分類函數(shù)，并在每次迭代重新計算權(quán)重和樣本概率。

（5）使用隨機森林算法作為LogitBoost的基礎(chǔ)分類器，設(shè)置迭代次數(shù)為100，并使用十折交叉校驗的方式把樣本分成十分，每次使用其中九份作為訓(xùn)練數(shù)據(jù)集一份作為測試集，總共迭代十次最后經(jīng)過加權(quán)統(tǒng)計的方式得到所有樣本的分類預(yù)測結(jié)果。

（6）輸出分類預(yù)測結(jié)果和成功率。

3 ?實驗結(jié)果與分析

3.1 ?數(shù)據(jù)集

本文采用NASA公布的MDP軟件缺陷數(shù)據(jù)集作為實驗數(shù)據(jù)集，并且對原數(shù)據(jù)集進行了清理刪除了原始數(shù)據(jù)集中出現(xiàn)的重復(fù)樣本，具體如表1所示列出了樣本集名稱、樣本總數(shù)、有缺陷樣本數(shù)、無缺陷樣本數(shù)以及不平衡度，其中不平衡度等于無缺陷樣本和有缺陷樣本的除數(shù)，可以發(fā)現(xiàn)數(shù)據(jù)集非常不平衡，從1.84到45.56不等。

3.2 ?評價標(biāo)準(zhǔn)

為有效評價各算法性能，使用分類混淆矩陣如表2表示預(yù)測完成后各項結(jié)果數(shù)據(jù)，其中TP表 ? 示有缺陷樣本被正確預(yù)測的數(shù)量，F(xiàn)N表示無缺陷樣本預(yù)測成有缺陷樣本數(shù)量，F(xiàn)P表示有缺陷樣本預(yù)測為無缺陷樣本數(shù)量，TN表示無缺陷樣本正確預(yù)測 ?數(shù)量。

評價標(biāo)準(zhǔn)一：準(zhǔn)確率（Acc），即有缺陷樣本和無缺陷樣本都預(yù)測正確在整個樣本中的比例。

3.3 ?實驗結(jié)果與分析

本文實驗分成三個步驟，首先使用SMOTE隨機過采樣方法增加少數(shù)樣本數(shù)量使數(shù)據(jù)集達到均衡;第二步使用本文提出的新集成方法在數(shù)據(jù)集上使用十折交叉校驗的方式計算預(yù)測結(jié)果;第三步實現(xiàn)其他三個分類預(yù)測算法并與本文提出的方法進行比較，分類預(yù)測結(jié)果如表3所示。本文借助WEKA平臺實現(xiàn)的開源算法模擬整個實驗過程。

通過以上實驗可以得到本文方法在三個評價標(biāo)準(zhǔn)上較其他三個分類預(yù)測方法都表現(xiàn)比較好，圖1和圖2列出了各方法在數(shù)據(jù)集未做平衡處理與平衡處理后在數(shù)據(jù)集上的準(zhǔn)確率柱形圖，可以看到各算法在數(shù)據(jù)集平衡處理前后算法性能有不同程度的提升，而本文提出的方法樣本數(shù)據(jù)平衡的情況下預(yù)測性能比其他方法的準(zhǔn)確率都高。

4 ?結(jié)論

本文基于LogicBoost算法和隨機森林算法提出一種新的集成分類預(yù)測算法，該算法使用隨機森林分類算法作為基分類算法，有效發(fā)揮了隨機森林算法的高分類精度優(yōu)勢，同時結(jié)合LogicBoost集成算法進一步提高預(yù)測精度。選擇的NASA MDP數(shù)據(jù)集是美國宇航局公布的軟件缺陷數(shù)據(jù)集，該數(shù)據(jù)集收集了多個軟件的度量屬性和樣本數(shù)據(jù)，是軟件缺陷研究領(lǐng)域可直接進行分類預(yù)測的數(shù)據(jù)集。本文選擇了其中 12個基礎(chǔ)數(shù)據(jù)集驗證提出方法的預(yù)測效果，同時采用原始數(shù)據(jù)集和使用SMOTE方法隨機過采樣均衡的數(shù)據(jù)集兩個差異性的數(shù)據(jù)集進行對比實驗，實驗結(jié)果表明本文提出的方法在均衡數(shù)據(jù)集上效果比其他預(yù)測算法有較高的性能。雖然本文預(yù)測結(jié)果對比其他幾類分類算法較好，但本文未考慮多特征屬性對算法結(jié)果的影響，下一步將著重研究多特征屬性提取后驗證本文方法是否有更高的預(yù)測精度。

參考文獻

[1] 孔軍， 吳偉明， 谷勇浩. 基于缺陷模式匹配的靜態(tài)源碼分析技術(shù)研究[J]. 軟件， 2016， 37（11）： 146-149.

[2] 郝世錦， 崔冬華. 基于缺陷分層與PSO算法的軟件缺陷預(yù)測模型[J]. 軟件， 2012， 33（2）： 51-52.

[3] JIN C， JIN S W， YE J. Artificial neural network-based metric selection for software fault-prone prediction model[J]. IET Software， 2012， 6（6）： 479-487.

[4] LARADJI I H， ALSHAYEB M， GHOUTI L. Software defect prediction using ensemble learning on selected features[J]. Information & Software Technology， 2015， 58： 388-402.

[5] WANG J， SHEN B， CHEN Y. Compressed C4. 5 models for software defect prediction[C]//Proc of 2012 12th international conference on quality software.Washington DC： IEEE， 2012： 13-16.

[6] 段明璐. 軟件故障樹算法建模的研究[J]. 軟件， 2018， 39（2）： 66-74.

[7] PUSHPHAVATHI T P， Suma V， RAMASWAMY V. A novel method for software defect prediction： hybrid of FCM and random forest[C]//2014 International Conference on Electronics and Communication Systems （ICECS）. Piscataway： IEEE Press， 2014： 1-5.

[8] 顏樂鳴. 基于關(guān)聯(lián)規(guī)則挖掘的軟件缺陷分析研究[J]. 軟件， 2017， 38（1）： 70-76.

[9] WANG T， ZHANG Z， JING X， et al.Multiple kernel ensem-ble learning for software defect prediction[J]. Automated Software Engineering， 2016， 23（4）： 569-59.

[10] 劉學(xué)， 張素偉. 基于二次隨機森林的不平衡數(shù)據(jù)分類算法[J]. 軟件， 2016， 37（7）： 75-79.

[11] CHAWLA N V， BOWYER K W， HALL L O， et al. SMOTE： synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research， 2011， 16（1）： 321-357.

[12] SUN Z， SONG Q， ZHU X， et al. A novel ensemble method for classifying imbalanced data[J]. Pattern Recognition， 2015， 48（5）： 1623-1637.

[13] 戴翔， 毛宇光. 基于集成混合采樣的軟件缺陷預(yù)測研究[J]. 計算機工程與科學(xué)， 2015， 37（5）： 930-936.

[14] FRIEDMAN J H， TREVOR H，ROBERT T. Additive logistic regression： A statistical view of boosting[J]. The Annals of Statistics， 2000， 38（2）： 337-374.

[15] SHIRABAD J S， MENZIES T J. The PROMISE repository of software engineering databases[OL]. （2005-03-15）[2019-04- 23]. http：//promise.site.uottawa.ca/SERepository.

[16] YOAV F. Boosting a weak learning algorithm by majority[J]. Information and Computation， 1995， 121（2）， 256-285.

[17] BREIMAN L. Bagging predictors[J]. Machine learning， 1996， 24（2）： 123-4.

[18] HO T K. Random subspace method for constructing decision trees[J]. IEEE Transactions onPattern Analysis & Machine Intelligence， 1998， 20（8）： 832-844.