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

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

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

中圖分類號(hào)： TP206+.3 ? ?文獻(xiàn)標(biāo)識(shí)碼： 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 ?引言

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

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

1 ?相關(guān)研究

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

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

2.1 ?SMOTE采樣

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

2.2 ?LogicBoost算法

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

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

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

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

2.3 ?隨機(jī)森林算法

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

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

輸出：隨機(jī)森林決策樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 ?評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

4 ?結(jié)論

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

參考文獻(xiàn)

[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é)， 張素偉. 基于二次隨機(jī)森林的不平衡數(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]. 計(jì)算機(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.