部分決策樹(shù)在軟件缺陷預(yù)測(cè)中的應(yīng)用

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

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

DOI：10. 11907/rjdk. 191625

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

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

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

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

2.2 部分決策樹(shù)介紹

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

2.3 部分決策樹(shù)特征屬性選擇

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

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

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

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

（3）使用SMOTE隨機(jī)過(guò)采樣方法增加數(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）采用回溯的爬山算法遍歷整個(gè)特征子集列表與分類正確率，找到分類預(yù)測(cè)能力最大的對(duì)應(yīng)特征子集，其中爬山算法搜索范圍k=5。具體過(guò)程為：①隨機(jī)初始化一個(gè)屬性子集，使用部分決策樹(shù)計(jì)算屬性子集的分類預(yù)測(cè)能力并返回;②根據(jù)搜索策略找到當(dāng)前特征集，隨機(jī)擴(kuò)大特征集，并使用部分決策樹(shù)計(jì)算特征集的分類預(yù)測(cè)能力，找到k個(gè)特征子集，保存與替換分類預(yù)測(cè)能力最大的特征子集及分類預(yù)測(cè)能力值;③回溯整個(gè)特征集，特征子集的分類預(yù)測(cè)能力不重復(fù)計(jì)算，重復(fù)步驟①和②，直到整個(gè)特征集都回溯完成。

（5）返回預(yù)測(cè)能力最大的特征子集。

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

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

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

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

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

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

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

G-mean值是綜合考察無(wú)缺陷/有缺陷樣本被正確預(yù)測(cè)以及無(wú)缺陷/有缺陷樣本被錯(cuò)誤預(yù)測(cè)的指標(biāo)，比如樣本被正確預(yù)測(cè)的概率高，同時(shí)被錯(cuò)誤預(yù)測(cè)的概率也高， G-mean值則會(huì)比較低，若相反則會(huì)較高。

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]基于機(jī)器學(xué)習(xí)的軟件缺陷預(yù)測(cè)方法研究[D]. 徐州：中國(guó)礦業(yè)大學(xué)，2017.

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

[3]李麗媛， 江國(guó)華.? 一種面向軟件缺陷預(yù)測(cè)的特征聚類選擇方法[J].? 計(jì)算技術(shù)與自動(dòng)化， 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]. 計(jì)算機(jī)應(yīng)用研究，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]戴翔，毛宇光. 基于集成混合采樣的軟件缺陷預(yù)測(cè)研究[J].? 計(jì)算機(jī)工程與科學(xué)，2015，37（5）：930-936.

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

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

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

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

[17]陳翔，陸凌姣，吉人，等. SBFS：基于搜索的軟件缺陷預(yù)測(cè)特征屬性選擇框架[J]. 計(jì)算機(jī)應(yīng)用研究，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.

（責(zé)任編輯：黃 ?。?/p>

收稿日期：2019-04-29

作者簡(jiǎn)介：張洋（1986-），男，碩士，湖南省農(nóng)村信用社聯(lián)合社信息科技部工程師，研究方向?yàn)檐浖y(cè)試。