部分決策樹在軟件缺陷預測中的應用

摘 要：由于多個特征屬性的存在以及屬性間存在關(guān)聯(lián)和冗余等因素，導致軟件缺陷預測方法計算量較大，且降低了模型預測性能。因此，提出一種基于部分決策樹（PART）的特征屬性選擇算法，使用PART作為特征屬性選擇的評價準則，然后采用SMOTE方法使數(shù)據(jù)集達到平衡后，運用回溯爬山算法搜索屬性集子空間，找到最優(yōu)屬性子集，最后采用隨機森林分類算法預測結(jié)果。通過在NASA MDP基礎(chǔ)數(shù)據(jù)集上進行實驗，并與基于相關(guān)性關(guān)系、主成分分析（PCA）兩種特征屬性選擇方法進行比較，得出新方法在分類預測中的準確率比相關(guān)性分析方法高出1%～11%，比主成分分析方法高出3%～19%。所以該方法不僅能夠有效選取特征屬性子集，而且顯著提高了分類預測精度及效率。

關(guān)鍵詞：軟件缺陷預測;部分決策樹;特征屬性選擇;隨機森林分類算法

DOI：10. 11907/rjdk. 191625

中圖分類號：TP319 ? 文獻標識碼：A??????????????? 文章編號：1672-7800（2020）003-0182-04

Application of Partial Decision Tree in Software Defect Prediction

ZHANG Yang

（Ministry of Information Technology， Hunan Rural Credit Cooperatives Union， Changsha 410000， China）

Abstract：Because there is a connection between the existence of multiple attributes and attribute and redundancy， leading to large amount of software defect prediction method to calculate and reduce the performance forecast model， is proposed based on a PART of the decision tree （PART） feature attribute selection algorithm， using PART as an evaluation criterion of feature attribute selection， then the SMOTE method is used to balance the data set and the backtracking hill-climbing algorithm is used to search the subspace of attribute set to find the optimal attribute set， finally uses the random forest algorithm to predict the results. Through experiments on the basic data set of NASA MDP and comparison with two feature selection methods based on correlation and principal component analysis （PCA）， it is concluded that the new method has the best effect and the accuracy of classification prediction is 1%～11% higher than that of correlation analysis method and 3%～19% higher than that of principal component analysis method. Therefore， the new method not only effectively selects the subset of feature attributes， but also significantly improves the accuracy and efficiency of classification prediction.

Key Words：software defect prediction;partial decision tree;feature attribute selection;random forest algorithm

0 引言

隨著計算機技術(shù)的快速發(fā)展，計算機軟件的應用范圍也越來越廣，與人們生活息息相關(guān)的銀行系統(tǒng)、電信系統(tǒng)、證券系統(tǒng)等都是通過計算機軟件進行運作。同時在專業(yè)細分領(lǐng)域，越來越多軟件系統(tǒng)逐步取代了人們原先需要手工處理的工作，比如銀行自動柜員機、無人值守停車場以及正在研發(fā)的無人駕駛汽車等。因此，軟件的可用性成為一個重要問題，但現(xiàn)實情況是沒有人能開發(fā)出百分之百可靠的軟件，即使號稱具有99.999 999%可靠性的騰訊云也在2018年7月20日發(fā)生宕機，導致部分公司數(shù)據(jù)永久丟失，而且類似事件還在不定期發(fā)生，而軟件缺陷是導致相關(guān)事件最主要的原因。因此，如何盡早盡快發(fā)現(xiàn)軟件中的缺陷成為軟件工程領(lǐng)域的主要研究課題之一[1]。

軟件缺陷預測分為靜態(tài)軟件缺陷預測與動態(tài)軟件缺陷預測[2]，解決的主要問題是根據(jù)給定的軟件描述信息判斷軟件是否存在故障或缺陷。目前采用的主要方法有數(shù)據(jù)挖掘[3]、神經(jīng)網(wǎng)絡[4]、邏輯回歸（logistic Regression）[5]、支持向量機（SVM）[6]、貝葉斯模型[7]、集成學習方法[8]等。對給定的數(shù)據(jù)集進行特征屬性選擇，能有效減輕分類預測計算工作量，所以本文主要研究如何有效選擇軟件缺陷數(shù)據(jù)集中的特征屬性，并進行軟件缺陷預測。

1 相關(guān)研究

在軟件缺陷預測研究中，有缺陷的樣本數(shù)量一般非常少，而無缺陷樣本數(shù)量很多，這種不平衡性嚴重影響了分類預測效果[9]，所以首先需要解決數(shù)據(jù)集的不平衡問題。目前針對數(shù)據(jù)集不平衡問題有多種解決方法，包括：向上過采樣補充少數(shù)樣本方法[10]、向下欠采樣減少多數(shù)樣本方法[11]，以及將過采樣和欠采樣相結(jié)合，減少多數(shù)類樣本、增加少數(shù)類樣本的方法[12]等。

眾多學者針對軟件缺陷預測數(shù)據(jù)集的特征屬性進行了研究，如文獻[13]將主成分分析方法（PCA）應用于特征屬性選擇，從而有效地對多數(shù)據(jù)集進行降維，同時解釋了原始數(shù)據(jù)集特征間的關(guān)系;文獻[14]提出一種基于互信息的特征屬性選擇算法，通過計算兩個特征間的依賴關(guān)系輔助特征屬性選擇，并取得了一定效果;文獻[15]提出一種基于聚類分析的特征屬性選擇方法，根據(jù)特征間的關(guān)聯(lián)關(guān)系，使用K中心點聚類算法進行特征屬性選擇;文獻[16]構(gòu)建基于深度信念網(wǎng)與支持向量機的軟件缺陷預測模型，使用深度信念網(wǎng)進行學習與分析，并依據(jù)該方法進行特征屬性選擇;文獻[17]提出將遺傳算法應用于特征屬性選擇，基于遺傳算法的隨機搜索特性找到一個最優(yōu)特征集。

本文在靜態(tài)軟件缺陷預測基礎(chǔ)上分析以上多種特征屬性選擇方法，提出基于部分決策樹的特征屬性選擇方法，使用回溯算法調(diào)用部分決策樹算法以判斷特征屬性集的預測能力，并選擇具有最優(yōu)預測能力的特征屬性子集與隨機森林分類算法相結(jié)合進行軟件缺陷分類預測。通過NASA MDP數(shù)據(jù)集[18]上的實驗表明，該方法能保留主要特征屬性，在預測效果上優(yōu)于其它兩種方法。

2 基于部分決策樹的特征屬性選擇方法

2.1 數(shù)據(jù)集平衡處理

本文借鑒SMOTE（Synthetic Minority Oversampling Technique）方法實現(xiàn)數(shù)據(jù)集的隨機向上采樣，以隨機增加小類樣本，使樣本間達到平衡狀態(tài)，具體實現(xiàn)步驟如下：

設測試數(shù)據(jù)集少數(shù)類的樣本數(shù)為T？，需要插入N個少數(shù)類新樣本，N為正整數(shù)。

（1）首先從該少數(shù)類的T個樣本中找到樣本？xi，并使用歐氏距離計算得到？k個近鄰，記為{xi1，xi2，…，xik}。

（2）然后從近鄰集合實例中隨機選擇一個樣本？xik，并生成一個[0，1]的隨機變量，新樣本合成公式如式（1）所示。

（3）重復執(zhí)行N？次步驟（1）、（2），最終生成N個新樣本{xnew1，xnew2，…，xnewN}。

（4）輸出平衡后的數(shù)據(jù)集。

2.2 部分決策樹介紹

部分決策樹（PART）[19]是一種不需要應用全局優(yōu)化策略生成決策規(guī)則的局部優(yōu)化決策樹算法。具體實現(xiàn)策略是采用分治策略生成一組決策規(guī)則，然后從訓練集合中刪除所有符合該決策規(guī)則的實例，接著遞歸運行直到數(shù)據(jù)集中沒有任何實例時結(jié)束，并返回決策規(guī)則集。用該方式生成決策規(guī)則不需要構(gòu)建整棵決策樹，而是在生成單個決策規(guī)則后，馬上從生成樹中刪除決策規(guī)則子樹，從而避免了早期泛化結(jié)果，同時加快了決策規(guī)則生成速度。基于部分決策樹的算法能快速生成決策規(guī)則，且算法效率優(yōu)于其它傳統(tǒng)決策樹算法。本文選擇部分決策樹以快速對特征屬性集的分類能力進行預判，最后根據(jù)預判結(jié)果選擇特征屬性子集。

2.3 部分決策樹特征屬性選擇

輸入：屬性集合（A1，A2，…，Am），屬性個數(shù)為m，以及樣本數(shù)據(jù)集合。

輸出：最佳特征數(shù)據(jù)集 。

（1）對輸入的樣本數(shù)據(jù)集中的數(shù)據(jù)進行處理，刪除重復數(shù)據(jù)，并計算數(shù)據(jù)集的不平衡度，不平衡度=無缺陷樣本數(shù)/有缺陷樣本數(shù)。

（2）判斷樣本類別不平衡度是否大于閾值minBalance，如果大于閾值，則先執(zhí)行步驟（4），然后執(zhí)行步驟（3），最后執(zhí)行步驟（5）并返回結(jié)果，否則按順序執(zhí)行以下步驟。

（3）使用SMOTE隨機過采樣方法增加數(shù)據(jù)集中少數(shù)類樣本數(shù)量，如果樣本總數(shù)大于閾值minNum，則新插入到數(shù)據(jù)集中的樣本比例為N=int（（（多數(shù)類樣本數(shù)量/少數(shù)類樣本）-1）*100），否則按兩階段插入的方式首先執(zhí)行第一階段新插入樣本數(shù)N1（N1=int（（多數(shù)類樣本數(shù)量/少數(shù)類樣本）*100）），然后執(zhí)行第二階段插入新樣本N2（N2=int（（（多數(shù)類樣本數(shù)量/少數(shù)類樣本）-1）*100）），N=N1+N2。

（4）采用回溯的爬山算法遍歷整個特征子集列表與分類正確率，找到分類預測能力最大的對應特征子集，其中爬山算法搜索范圍k=5。具體過程為：①隨機初始化一個屬性子集，使用部分決策樹計算屬性子集的分類預測能力并返回;②根據(jù)搜索策略找到當前特征集，隨機擴大特征集，并使用部分決策樹計算特征集的分類預測能力，找到k個特征子集，保存與替換分類預測能力最大的特征子集及分類預測能力值;③回溯整個特征集，特征子集的分類預測能力不重復計算，重復步驟①和②，直到整個特征集都回溯完成。

（5）返回預測能力最大的特征子集。

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

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

本文采用NASA公布的MDP軟件缺陷數(shù)據(jù)集作為實驗數(shù)據(jù)集。文獻[20]發(fā)現(xiàn)研究人員廣泛使用的NASA 數(shù)據(jù)集內(nèi)部存在一些噪聲，并證實該噪聲將對研究人員得出結(jié)論的有效性造成影響，故對數(shù)據(jù)集進行了清理，本文使用的是清理后的數(shù)據(jù)集。NASA數(shù)據(jù)集描述了多個特征及大量樣本數(shù)據(jù)，從多個角度描述了軟件的靜態(tài)狀況。表1列出了數(shù)據(jù)集名稱、屬性數(shù)目、樣本總數(shù)、有缺陷樣本數(shù)、缺陷樣本占比5個方面的數(shù)據(jù)集信息，并能直觀看到數(shù)據(jù)集的不平衡性，缺陷樣本占比約為2.3%～35.2%。

3.2 評價標準

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

準確率（Acc）用于評價有缺陷樣本和無缺陷樣本都被正確預測的個數(shù)之和在整個樣本中的比例，體現(xiàn)了算法的全局正確性。

AUC值是以查全率為縱坐標、以誤報率為橫坐標構(gòu)成的曲線與坐標軸圍成的面積，取值區(qū)間為[0，1]。其值越接近1，表示分類器預測性能越好。

G-mean值是綜合考察無缺陷/有缺陷樣本被正確預測以及無缺陷/有缺陷樣本被錯誤預測的指標，比如樣本被正確預測的概率高，同時被錯誤預測的概率也高， G-mean值則會比較低，若相反則會較高。

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

本文經(jīng)過多次實驗得出，在樣本差異較大的數(shù)據(jù)集上先進行特征屬性選取，再對數(shù)據(jù)集作平衡處理，能保留更多特征屬性信息，而且在樣本數(shù)較少的情況下無法發(fā)揮特征屬性選擇方法的優(yōu)勢，故本文設定算法的兩個變量minBalance=10，minNum=300。實驗主要分為4個步驟：①采用SMOTE方法對數(shù)據(jù)進行過采樣，使數(shù)據(jù)集達到平衡;②使用本文提出的特征屬性選擇方法找到預測能力最好的特征屬性集合，表3列出了使用本文方法選擇的特征屬性集合;③使用隨機森林分類算法作為基分類算法，驗證選擇特征屬性的預測效果;④在步驟①的基礎(chǔ)上，基于WEKA平臺實現(xiàn)基于關(guān)聯(lián)規(guī)則方法和PCA方法的特征屬性選擇，然后使用隨機森林分類算法和J48決策樹算法對生成的特征屬性子集進行分類預測，并與本文方法預測結(jié)果進行比較。其中表4列出了使用隨機森林算法對上述3種特征屬性選擇方法選擇的特征屬性子集進行分類預測的結(jié)果比較情況，圖1則以直方圖形式更直觀地展示了使用J48決策樹算法對上述3種方法選擇的特征屬性子集進行分類預測的對比情況。

通過表3可以看到，本文方法選擇的特征屬性子集在隨機森林分類算法和J48決策樹算法上的分類預測精度都比較高，說明本文提出的特征屬性選擇方法相比另外兩種方法能更有效地選擇特征屬性，而且分類預測效果較好。圖2列出了使用隨機森林分類算法在特征屬性選擇前后算法建模時間的對比曲線，可以直觀地看到選擇特征屬性后，預測算法建模計算時間明顯減少。

4 結(jié)語

本文針對在軟件缺陷預測中數(shù)據(jù)集屬性數(shù)目多，且存在冗余的現(xiàn)象，以及多屬性導致的計算量過大等問題進行研究，提出一種基于部分決策樹的特征屬性選擇方法并進行軟件缺陷預測。通過在NASA MDP數(shù)據(jù)集上進行實驗，并與基于PCA與相關(guān)關(guān)系方法的特征屬性選擇方法選擇的特征屬性子集，在隨機森林分類算法和J48決策樹算法上進行缺陷預測性能對比。實驗結(jié)果表明，本文方法選擇的特征屬性子集有很高的分類預測精度。同時本文還驗證了精簡的特征屬性子集在分類預測算法上建模時間較短，且樣本數(shù)量越多，兩者差距越大。雖然本文方法測試結(jié)果較好，但仍有一定的提升空間，所以下一步工作將研究如何集成多個特征屬性預測方法，以實現(xiàn)更好的預測效果。

參考文獻：

[1]基于機器學習的軟件缺陷預測方法研究[D]. 徐州：中國礦業(yè)大學，2017.

[2]王青，伍書劍，李明樹. 軟件缺陷預測技術(shù)[J]. 軟件學報，2008，19（7）：1565-1580.

[3]李麗媛， 江國華.? 一種面向軟件缺陷預測的特征聚類選擇方法[J].? 計算技術(shù)與自動化， 2018，37（2）：126-131.

[4]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.

[5]BRIAND L C，MELO W L，WUS T J. A ssessing the applicability of fault-proneness models across object-oriented software projects[J]. IEEE Transactions on Software Engineering，2002，28（7）：706-720.

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

[7]OKUTAN A，YILDIZ O T. Software defect prediction using Bayesian networks[J]. Empirical Software Engineering，2014，19（1）：154-181.

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

[9]李勇，劉戰(zhàn)東，張海軍. 不平衡數(shù)據(jù)的集成分類算法綜述[J]. 計算機應用研究，2014，31（5）：1287-1291.

[10]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.

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

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

[13]陳佩，辛云宏. 一種有效的加權(quán)物質(zhì)分類方法[J]. 計算機與應用化學，2014，31（4）：466-470.

[14]王培，金聰，葛賀賀. 面向軟件缺陷預測的互信息屬性選擇方法[J]. 計算機應用，2012，32（6）：1738-1740.

[15]劉望舒，陳翔，顧慶. 軟件缺陷預測中基于聚類分析的特征屬性選擇方法[J]. 中國科學：信息科學，2016，46（9）：1298-1320.

[16]甘露. 基于深度學習的軟件缺陷預測技術(shù)研究[D]. 南京：南京航空航天大學，2017.

[17]陳翔，陸凌姣，吉人，等. SBFS：基于搜索的軟件缺陷預測特征屬性選擇框架[J]. 計算機應用研究，2017，34（4）：1105-1108.

[18]SHIRABAD J S，MENZIES T J. The promise repository of software engineering databases[EB/OL]. http：//promise.site.uottawa.ca/SERepository.

[19]EIBE F，IAN W. Generating accurate rule sets without global optimization[C]. Proceedings of the International Conference on Machine Learning，1998：144-151.

[20]SHEPPERD M，SONG Q B，SUN Z B，et al. Data quality： some comments on the NASA software defect datasets[J]. IEEE Trans on Software Engineering，2013，25（9）：1208-1215.

（責任編輯：黃 ?。?/p>

收稿日期：2019-04-29

作者簡介：張洋（1986-），男，碩士，湖南省農(nóng)村信用社聯(lián)合社信息科技部工程師，研究方向為軟件測試。