李 莉，任振康，石可欣

（東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，哈爾濱 150040）

0 概述

軟件的可靠性是軟件工程領(lǐng)域最重要的指標(biāo)之一［1-2］，軟件缺陷預(yù)測(cè)技術(shù)可以有效提高軟件可靠性，降低測(cè)試成本，合理進(jìn)行軟件缺陷預(yù)測(cè)可以幫助測(cè)試團(tuán)隊(duì)快速定位軟件缺陷，修復(fù)系統(tǒng)存在的漏洞。近年來的軟件缺陷預(yù)測(cè)研究結(jié)果表明［3］，絕大多數(shù)軟件缺陷集中在較小比例的軟件模塊中，即軟件缺陷預(yù)測(cè)領(lǐng)域存在嚴(yán)重的類不平衡問題。現(xiàn)有軟件缺陷預(yù)測(cè)技術(shù)產(chǎn)生的錯(cuò)誤分類主要分為2 種［4］：將有缺陷的模塊誤分為無缺陷的模塊；將無缺陷的模塊誤分為有缺陷的模塊。在軟件工程實(shí)踐中，第一類錯(cuò)誤的代價(jià)遠(yuǎn)高于第二類錯(cuò)誤。隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，眾多研究人員將機(jī)器學(xué)習(xí)技術(shù)應(yīng)用于軟件缺陷預(yù)測(cè)領(lǐng)域。研究結(jié)果表明，代價(jià)敏感學(xué)習(xí)技術(shù)可較好地解決樣本中類不平衡問題［5］，能夠?yàn)檐浖?xiàng)目的決策提供支持［6-7］。

目前，軟件缺陷預(yù)測(cè)領(lǐng)域采用的主要方法包括神經(jīng)網(wǎng)絡(luò)［8］、邏輯回歸（Logistic Regression，LR）［9］、支持向量機(jī)（Support Vector Machine，SVM）［10］、貝葉斯模型［11］、集成學(xué)習(xí)方法［12］等。然而，上述方法在面對(duì)第一類和第二類錯(cuò)誤分類代價(jià)不同的情況時(shí)，并未給出有效的解決方案。

YANG等使用以多個(gè)K最近鄰（K-Nearest Neighbor，KNN）為基分類器的Boosting算法進(jìn)行軟件缺陷預(yù)測(cè)［13］，但使用KNN 算法時(shí)存在以下問題：KNN 算法復(fù)雜度較高，且在處理類不平衡問題時(shí)對(duì)于稀有類別的預(yù)測(cè)準(zhǔn)確率低。例如，在樣本不平衡時(shí)，即有缺陷類樣本容量很小、無缺陷類樣本容量很大，此時(shí)若輸入一個(gè)新的缺陷樣本，該樣本的K個(gè)鄰居中可能大容量類占大多數(shù)，從而導(dǎo)致分類結(jié)果誤差偏大。

相較KNN 算法，決策樹易于理解和實(shí)現(xiàn)，可以較直觀地體現(xiàn)數(shù)據(jù)特點(diǎn)，且其擅長處理二分類問題，但決策樹模型對(duì)多類別問題或連續(xù)型字段的分類效果不佳。在軟件缺陷預(yù)測(cè)領(lǐng)域，分類問題是一個(gè)二分類問題，即預(yù)測(cè)模塊是有缺陷模塊還是無缺陷模塊，因此，可以選取決策樹作為基分類器。李勇等使用以C4.5 決策樹作為基分類器的代價(jià)敏感Bagging算法進(jìn)行軟件缺陷預(yù)測(cè)［14］，實(shí)驗(yàn)結(jié)果表明，該算法具有較好的性能，但時(shí)間復(fù)雜度較高。

針對(duì)以上問題，本文提出一種代價(jià)敏感的Boosting 軟件缺陷預(yù)測(cè)方法CSBst，以提升Boosting方法在二分類問題中的預(yù)測(cè)性能［15-17］。針對(duì)不同的錯(cuò)誤分類賦予其不同權(quán)重，采用閾值移動(dòng)方法進(jìn)行決策樹基分類器集成，從而解決類不平衡問題并在提高預(yù)測(cè)性能的同時(shí)降低算法的時(shí)間復(fù)雜度。

1 常規(guī)Boosting 方法

設(shè)訓(xùn)練數(shù)據(jù)集為{(x1，y1)，(x2，y2)，…，(xN，yN)}，其中：xi為一個(gè)含有d個(gè)元素的列向量，即xi∈X?R；yi為該訓(xùn)練數(shù)據(jù)集中的標(biāo)簽集，y∈{-1，+1}。Boosting 方法具體步驟如下：

1）給出N個(gè)數(shù)據(jù)，初始化每個(gè)數(shù)據(jù)的權(quán)重并取值相同：

2）對(duì)每一個(gè)弱分類器（1，2，…，m），按照樣本分布權(quán)重Dm訓(xùn)練數(shù)據(jù)，得到m個(gè)基學(xué)習(xí)器Gm(x)。Gm(x)的取值范圍為：

計(jì)算Gm(x)在加權(quán)訓(xùn)練集中的分類誤差：

式（3）表示模型的誤差等于每一個(gè)錯(cuò)分的樣本權(quán)重之和。

計(jì)算Gm(x)的系數(shù)，即該基分類器的權(quán)重：

3）根據(jù)模型權(quán)重更新數(shù)據(jù)的權(quán)重：

其中：Zm是正規(guī)化系數(shù)，用來確保所有的數(shù)據(jù)權(quán)重總和為1。

指數(shù)內(nèi)部為：

若弱分類器m的分類結(jié)果和真實(shí)結(jié)果相同，則θm小于1，該數(shù)據(jù)集的樣本權(quán)重降低；若弱分類器m的分類結(jié)果和真實(shí)結(jié)果不一致，即θm大于1，則該數(shù)據(jù)集樣本權(quán)重增加。

4）通過迭代將多個(gè)弱分類器集成為一個(gè)強(qiáng)分類器：弱分類器i的權(quán)重為ai，弱分類器對(duì)于樣本i的分類結(jié)果為Gi(x)，集成之后的學(xué)習(xí)器為G(x)，sign（x）為符號(hào)函數(shù)，x>0 時(shí)輸出為1，x<0 時(shí)輸出為-1，集成學(xué)習(xí)的公式為：

2 代價(jià)敏感的Boosting 方法

2.1 方法步驟

在軟件缺陷預(yù)測(cè)領(lǐng)域?qū)τ谡`報(bào)與漏報(bào)的懲罰因子實(shí)際不相同，誤報(bào)率較高易導(dǎo)致開發(fā)和測(cè)試資源的浪費(fèi)，漏報(bào)率較高易導(dǎo)致含有缺陷模塊的軟件被交付到用戶手中［18］。軟件開發(fā)后期對(duì)缺陷的修復(fù)代價(jià)是前期的指數(shù)倍，交付后存在的軟件缺陷甚至?xí){客戶的生命財(cái)產(chǎn)安全，因此，軟件缺陷預(yù)測(cè)過程中對(duì)漏報(bào)的懲罰應(yīng)大于誤報(bào)［19-20］。CSBst 方法在更新樣本權(quán)重時(shí)，增加產(chǎn)生第一類錯(cuò)誤樣本的權(quán)重，使產(chǎn)生第一類錯(cuò)誤的樣本權(quán)重高于無缺陷類樣本權(quán)重和產(chǎn)生第二類錯(cuò)誤的樣本權(quán)重［21-22］，由此可大幅提高預(yù)測(cè)結(jié)果的準(zhǔn)確率。CSBst 方法流程如圖1 所示，其中，加粗標(biāo)注為相對(duì)常規(guī)Boosting 的改進(jìn)部分。

圖1 CSBst 方法流程Fig.1 Procedure of CSBst method

CSBst 方法具體步驟如下：

1）第一步同常規(guī)Boosting 方法。

2）第二步同常規(guī)Boosting 方法。

3）根據(jù)模型權(quán)重更新數(shù)據(jù)的權(quán)重：

其中：Zm是正規(guī)化系數(shù)，用來確保所有的數(shù)據(jù)權(quán)重總和為1。

指數(shù)內(nèi)部為：

若弱分類器m的分類結(jié)果和真實(shí)結(jié)果相同，即分類正確，則Rresult<1，該數(shù)據(jù)集的樣本權(quán)重降低。若弱分類器m的分類結(jié)果和真實(shí)結(jié)果不同，即分類錯(cuò)誤，則Rresult>1，該數(shù)據(jù)集的樣本權(quán)重增加。數(shù)據(jù)集的樣本權(quán)重由CL值決定。其中，CL的取值為：

4）通過迭代將多個(gè)弱基分類器集成為一個(gè)強(qiáng)分類器，集成學(xué)習(xí)的公式如下：

其中：弱分類器i的權(quán)重為ai；弱分類器對(duì)于樣本i的分類結(jié)果為Gi(x)；集成之后的學(xué)習(xí)器為G(x)；Tthreshold為調(diào)整閾值的參數(shù)；sign（x）為符號(hào)函數(shù)，x>0 時(shí)輸出為1，x<0 時(shí)輸出為-1。

2.2 CSBst 方法實(shí)現(xiàn)

CSBst 方法主要包括數(shù)據(jù)處理和閾值選擇2 個(gè)階段：

1）在數(shù)據(jù)處理階段，對(duì)數(shù)據(jù)集進(jìn)行提取，將數(shù)據(jù)集分割為特征集和標(biāo)簽集，使用基分類器決策樹進(jìn)行數(shù)據(jù)集分類。決策樹對(duì)第一個(gè)特征進(jìn)行劃分，該特征最大值為FFEATURE_MAX，最小值為FFEATURE_MIN。對(duì)于該特征劃分的步長SStep為：

從FFEATURE_MIN開始，每次增加一個(gè)SStep進(jìn)行特征劃分，計(jì)算方式如式（16）所示，劃分完成后計(jì)算該劃分下的錯(cuò)誤率。每個(gè)特征計(jì)算20 次，依次計(jì)算每個(gè)特征直至遍歷特征集合，選出并存儲(chǔ)分類錯(cuò)誤率最低的特征和特征閾值。

2）閾值選擇階段主要對(duì)上述數(shù)據(jù)進(jìn)行進(jìn)一步處理。基于CSBst 方法思想，對(duì)于已經(jīng)完成分類的第一個(gè)弱分類器，更新第一類錯(cuò)誤、第二類錯(cuò)誤和正確樣本的權(quán)重。依次處理每個(gè)弱分類器，最后根據(jù)基分類器的錯(cuò)誤率更新其權(quán)重。

在CSBst 方法中，一直增加樣本權(quán)重雖會(huì)提高樣本的預(yù)測(cè)率，但也會(huì)在一定程度上使樣本過擬合，導(dǎo)致誤報(bào)率提高，無法有效解決類不平衡問題。為平衡預(yù)測(cè)率和誤報(bào)率，本文引入閾值移動(dòng)的思想。在集成基分類器分類結(jié)果時(shí)，選擇合適值作為區(qū)分待預(yù)測(cè)模塊是否為缺陷模塊的閾值，集成加權(quán)結(jié)果小于該閾值的模塊并標(biāo)記為正常模塊，大于該閾值的模塊標(biāo)記為缺陷模塊。

在軟件缺陷預(yù)測(cè)領(lǐng)域，評(píng)價(jià)準(zhǔn)則TPR、誤報(bào)率FPR、預(yù)測(cè)率P、平衡值BAL、平衡值F1 分別如式（17）～式（21）所示，定義二值分類的混淆矩陣如表1 所示。

表1 混淆矩陣Table 1 Confusion matrix

由混淆矩陣可知，TPR 值升高，F(xiàn)PR 值隨之升高。選取BAL 來平衡TPR 和FPR，最優(yōu)閾值和權(quán)重的選擇以BAL 取得最大值為標(biāo)準(zhǔn)。

在CSBst 方法中，設(shè)置閾值為Threshold，初始值為0，權(quán)重為Weigh，初始值為1。遍歷Weigh 和Threshold，Weigh 為2.5 或Threshold 為1.5 時(shí)，TPR 值等于1，故設(shè)置Weigh 最大值為2.5，Threshold 最大值為1.5。每次遍歷步長為0.1，循環(huán)結(jié)束或TPR 值為1時(shí)遍歷停止。以BAL 取得最大值為模型的最優(yōu)解。

2.3 CSBst 偽代碼

CSBst 方法的偽代碼如算法1 所示。

算法1代價(jià)敏感的軟件缺陷預(yù)測(cè)算法

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

3.1 實(shí)驗(yàn)環(huán)境

本文實(shí)驗(yàn)采用公開的NASA 軟件缺陷預(yù)測(cè)數(shù)據(jù)集，包括CM1、PC1、KC1、PC3 數(shù)據(jù)集。所有結(jié)果采用10 次十折交叉驗(yàn)證的平均值。實(shí)驗(yàn)環(huán)境為Windows10 64 位操作系統(tǒng)，計(jì)算機(jī)內(nèi)存為8 GB，處理器為Core i5-8250u。實(shí)驗(yàn)選取文獻(xiàn)［16］提出的CSBKNN 方 法、CSCE 方法和Boosting 方法進(jìn)行對(duì)比。數(shù)據(jù)集特征如表2 所示。

表2 數(shù)據(jù)集及其特征Table 2 Datasets and their characteristics

3.2 方法時(shí)間復(fù)雜度分析

CSBst 與CSBKNN 集成方式相同，與CSCE 集成時(shí)間復(fù)雜度一致。因此，CSBst 的時(shí)間復(fù)雜度由基分類器的時(shí)間復(fù)雜度決定。

CSBst 方法使用的基分類器為一維決策樹，決策樹的訓(xùn)練時(shí)間復(fù)雜度為O(NMD)，其中：N為訓(xùn)練集中的樣本數(shù)；M為數(shù)據(jù)的維度；D是樹的深度。一維決策樹的深度為1，則時(shí)間復(fù)雜度為O(NM)。

CSBKNN 為KNN 集成的Boosting 方 法，KNN的時(shí)間復(fù)雜度為O(NM)。

CSCE 是C4.5 決策樹集成的代價(jià)敏感Bagging方法，決策樹的訓(xùn)練時(shí)間復(fù)雜度為O(NMD)。

綜上，CSBst 方法與CSBKNN 方法所采用的基分類器時(shí)間復(fù)雜度以及集成時(shí)間復(fù)雜度均相同，因此，CSBst 與CSBKNN 時(shí)間復(fù)雜度一致。CSBst 和CSCE 相比，前者的基分類器時(shí)間復(fù)雜度更低，兩者集成時(shí)間復(fù)雜度相同，因此，CSBst 方法的時(shí)間復(fù)雜度低于CSCE 方法。

3.3 結(jié)果分析

3.3.1 實(shí)驗(yàn)結(jié)果

本文選用4 個(gè)NASA 缺陷預(yù)測(cè)數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果如表3 所示。

表3 4 種方法實(shí)驗(yàn)結(jié)果對(duì)比Table 3 Comparison of experimental results of four methods

從表3 可以看出：

1）與CSBKNN、CSCE 以及常規(guī)Boosting 方法相比，CSBst 方法在大部分?jǐn)?shù)據(jù)集中均能取得較好的預(yù)測(cè)率。CSBst方法的平均TPR 值為76%，而CSBKNN、CSCE 以及常規(guī)Boosting 方法分別為62.4%、76.2%、18.56%，其中，常規(guī)Boosting 方法的預(yù)測(cè)率最低，主要是因?yàn)槠錄]有處理類不平衡問題，預(yù)測(cè)結(jié)果自然偏向多數(shù)類。

2）CSBst、CSCE、CSBKNN方法的平均誤報(bào)率分別為31.6%、36%、25.8%，而常規(guī)Boosting 方法的平均誤報(bào)率僅為3.76%。本文選取BAL 作為綜合指標(biāo)來評(píng)價(jià)預(yù)測(cè)性能，CSBst 方法具有較高的誤報(bào)率和預(yù)測(cè)率。

常規(guī)Boosting 與CSBKNN、CSCE 以及CSBst 方法相比，在方法流程中沒有考慮類不平衡問題的處理。CSBKNN、CSCE 以及CSBst 是專門為處理類不平衡問題而提出的代價(jià)敏感方法。本文選取的數(shù)據(jù)集取自真實(shí)的軟件項(xiàng)目，都存在類不平衡問題，因此，常規(guī)Boosting 方法性能較低。此外，為提高預(yù)測(cè)率，本文選取的性能評(píng)價(jià)標(biāo)準(zhǔn)為BAL=TPR-FPR。3 種代價(jià)敏感的方法通常都具有高預(yù)測(cè)率、高誤報(bào)率的特點(diǎn)，常規(guī)Boosting 方法具有低預(yù)測(cè)率和低誤報(bào)率的特點(diǎn)，預(yù)測(cè)率和誤報(bào)率等比增長，最后評(píng)價(jià)指標(biāo)BAL 也等比增長，因此，在本文所采用的評(píng)價(jià)指標(biāo)中常規(guī)Boosting 方法性能偏低。

綜上，常規(guī)Boosting 方法與CSBKNN、CSCE、CSBst 的性能差距主要是因?yàn)椴捎昧颂囟ǖ臄?shù)據(jù)集與評(píng)價(jià)指標(biāo)。對(duì)于性能較為接近的CSBst 和CSCE方法，本文選用F1 指標(biāo)繼續(xù)進(jìn)行深入分析，實(shí)驗(yàn)結(jié)果如表4 所示。

表4 CSBst 與CSCE 的F1 指標(biāo)結(jié)果對(duì)比Table 4 Comparison of F1 index results between CSBst and CSCE

從表4 可以看出，對(duì)于綜合評(píng)價(jià)指標(biāo)F1，CSBst在4 個(gè)數(shù)據(jù)集中的性能均高于CSCE，分別高出0.41、0.33、0.25、0.31。CSBst 方法的F1 值較高，是由于其預(yù)測(cè)準(zhǔn)確率P和預(yù)測(cè)率TPR 均較高所致。

相較CSBKNN 方法，在4 個(gè)NASA 實(shí)驗(yàn)數(shù)據(jù)集中，CSBst 方法的BAL 提高7%，TPR 提高13.6%，F(xiàn)PR提高5.8%。相較CSCE 方法，在4 個(gè)實(shí)驗(yàn)數(shù)據(jù)集中，CSBst 方法的BAL 平均提高3%，TPR 降低0.22%，F(xiàn)PR 降低4.4%，總體性能接近。在F1 指標(biāo)上，CSBst性能優(yōu)于CSCE，且CSBst 具有更低的時(shí)間復(fù)雜度，因此，CSBst 方法性能優(yōu)于CSCE。與常規(guī)Boosting方法進(jìn)行如上的比較分析，能夠得出同樣的結(jié)論。

綜上，CSBst 方法對(duì)軟件缺陷進(jìn)行預(yù)測(cè)的整體性能明顯高于同類代價(jià)敏感的缺陷預(yù)測(cè)方法。

3.3.2a取值對(duì)實(shí)驗(yàn)結(jié)果的影響

本節(jié)以PC1 數(shù)據(jù)集為例，給出實(shí)驗(yàn)中代價(jià)因子a取值的選擇過程，為進(jìn)行簡化，設(shè)置threshold 值為0。在采用CSBst 方法構(gòu)建預(yù)測(cè)模型時(shí)，代價(jià)因子a≥1。當(dāng)a>1 時(shí)，表示將有缺陷模塊預(yù)測(cè)為無缺陷模塊的代價(jià)較高；當(dāng)a=1 時(shí)，表示正確和錯(cuò)誤分類具有相同的代價(jià)。較低的TPR 意味著沒有找全有缺陷模塊，較高的FPR 意味著要利用較多的人力資源來對(duì)沒有缺陷的模塊進(jìn)行測(cè)試。

從圖2 可以看出：

圖2 a 取值對(duì)模型性能的影響Fig.2 Influence of a values on model performance

1）當(dāng)a=1 時(shí)，誤報(bào)率FPR 為3.1%，預(yù)測(cè)率TPR 為20%，預(yù)測(cè)率和誤報(bào)率均較低，但預(yù)測(cè)率FPR 低于60%，無法投入實(shí)際應(yīng)用。

2）隨著a值的逐漸增大，誤報(bào)率FPR 和預(yù)測(cè)率TPR 都逐漸上升，當(dāng)a=1.6 時(shí)，綜合性能指標(biāo)BAL 最高，可以認(rèn)為a=1.6 為CSBst 在PC1 數(shù)據(jù)集上的最優(yōu)解。

3）當(dāng)a＞1.6 時(shí)，隨著a值的增大，綜合評(píng)價(jià)指標(biāo)BAL 下降，TPR 升高，適用于對(duì)系統(tǒng)要求較高或測(cè)試資源較充足的情況。

4）當(dāng)a>2.4 時(shí)，TPR>95%，隨著a值的繼續(xù)增大，TPR 呈穩(wěn)定趨勢(shì)，F(xiàn)PR 不斷增長，因此，BAL 不斷減小。綜上，1.6 為a的最佳取值。

4 結(jié)束語

為提升軟件缺陷預(yù)測(cè)精確度，本文提出一種代價(jià)敏感的Boosting 軟件缺陷預(yù)測(cè)方法CSBst。通過細(xì)化不同種類錯(cuò)誤樣本的權(quán)重更新方式來篩選出存在第一類錯(cuò)誤的模塊，采用移動(dòng)閾值加權(quán)集成的方法解決軟件缺陷模塊中的類不平衡問題，并有效提高軟件缺陷的預(yù)測(cè)率。在NASA 軟件缺陷預(yù)測(cè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，與CSBKNN、CSCE 方法相比，在指標(biāo)相同的情況下，CSBst 方法的預(yù)測(cè)性能較高，時(shí)間復(fù)雜度較低，對(duì)于第一類錯(cuò)誤分類樣本具有更好的查找效果。下一步將針對(duì)本文所設(shè)置的BAL 指標(biāo)調(diào)整TPR 和FTR 的比重，研究更加合理穩(wěn)定的比重設(shè)計(jì)方法，以保證算法的穩(wěn)定性。此外，將探究線性回歸、邏輯回歸等不同基分類器對(duì)算法預(yù)測(cè)性能的影響。