張 肖，王黎明

(鄭州大學(xué) 信息工程學(xué)院，鄭州 450001)

1 引 言

隨著社會(huì)的發(fā)展，軟件的多樣性以及普遍性已經(jīng)滲入到人們的生活中，軟件的可靠性是人們進(jìn)行日常交易的重要保證,導(dǎo)致軟件系統(tǒng)不可靠的主要原因之一是軟件缺陷[1].軟件缺陷預(yù)測(cè)分為動(dòng)態(tài)缺陷預(yù)測(cè)和靜態(tài)缺陷預(yù)測(cè)，靜態(tài)軟件缺陷預(yù)測(cè)是指在不運(yùn)行程序的情況下，根據(jù)軟件的歷史開發(fā)數(shù)據(jù)以及已發(fā)現(xiàn)的缺陷,借助機(jī)器學(xué)習(xí)等方法來(lái)預(yù)測(cè)軟件系統(tǒng)中的缺陷數(shù)目和類型等[2].

在軟件缺陷預(yù)測(cè)中，標(biāo)記樣本難以獲取，無(wú)標(biāo)記樣本數(shù)量較多且容易收集.半監(jiān)督學(xué)習(xí)利用標(biāo)記樣本訓(xùn)練模型，同時(shí)利用未標(biāo)記樣本加強(qiáng)學(xué)習(xí)過(guò)程，不僅提高了分類器的性能，而且使標(biāo)記樣本匱乏的問(wèn)題得以緩解.在軟件測(cè)試中，80%的缺陷集中分布于20%的模塊內(nèi)，因此軟件缺陷數(shù)據(jù)集是高度類不平衡的[3].集成方法[4]、代價(jià)敏感方法[5]以及抽樣方法[6]是解決分類不平衡問(wèn)題的有效途徑.

為了解決標(biāo)記樣本較少以及分類不平衡問(wèn)題對(duì)預(yù)測(cè)模型造成的影響，提出一種基于半監(jiān)督集成學(xué)習(xí)算法的軟件缺陷預(yù)測(cè)模型.將半監(jiān)督Tri_training算法應(yīng)用到集成學(xué)習(xí)算法AdaBoost中對(duì)缺陷數(shù)據(jù)集進(jìn)行分類預(yù)測(cè).預(yù)測(cè)算法分為兩個(gè)階段：

1) 利用Tri_training算法以及欠采樣方法對(duì)無(wú)標(biāo)記樣本進(jìn)行標(biāo)記，將新標(biāo)記的樣本添加到已標(biāo)記樣本中形成標(biāo)記樣本集.

2)利用SMOTE算法對(duì)新的標(biāo)記樣本集進(jìn)行采樣，再使用AdaBoost集成學(xué)習(xí)方法對(duì)采樣后的標(biāo)記樣本集進(jìn)行預(yù)測(cè).

在第一階段中，半監(jiān)督算法可以充分利用無(wú)標(biāo)記樣本解決標(biāo)記樣本不足的問(wèn)題，在第二階段中，集成算法能更好的解決分類不平衡的問(wèn)題，并且能取得較好的預(yù)測(cè)效果.

2 相關(guān)工作

半監(jiān)督學(xué)習(xí)能夠充分利用少量的有標(biāo)記樣本和大量的未標(biāo)記樣本提高分類模型的性能，而集成學(xué)習(xí)通過(guò)對(duì)幾個(gè)分類器的組合能夠有效提高分類器的泛華性能,同時(shí)也能有效解決分類不平衡的問(wèn)題.因此，很多半監(jiān)督學(xué)習(xí)和集成學(xué)習(xí)方法已經(jīng)被廣泛應(yīng)用于軟件缺陷預(yù)測(cè)領(lǐng)域.

2.1 半監(jiān)督學(xué)習(xí)

文獻(xiàn)[7]對(duì)Tri-training算法進(jìn)行了改進(jìn)，將隨機(jī)下采樣方法與Tri-training進(jìn)行結(jié)合，有效的降低了分類不平衡和標(biāo)記樣本不足對(duì)預(yù)測(cè)模型性能的影響.文獻(xiàn)[8]等人研究利用了樸素貝葉斯方法建立了半監(jiān)督缺陷預(yù)測(cè)模型，其結(jié)果表明樸素貝葉斯算法是構(gòu)建小規(guī)模數(shù)據(jù)集半監(jiān)督缺陷預(yù)測(cè)模型的最佳選擇，提出的兩階段YATSI方法可以提高樸素貝葉斯在大規(guī)模數(shù)據(jù)集上的性能.文獻(xiàn)[9]提出了一種迭代的半監(jiān)督方法FTF，首先使用模型為所有的未標(biāo)記實(shí)例設(shè)置標(biāo)簽，以確保樣本中所有的實(shí)例都帶有標(biāo)簽，然后在整個(gè)數(shù)據(jù)集上實(shí)現(xiàn)經(jīng)典的監(jiān)督過(guò)程.結(jié)果表明，與傳統(tǒng)的監(jiān)督方法相比，F(xiàn)TF有比較明顯的優(yōu)點(diǎn).文獻(xiàn)[10]利用期望最大化(Expectation Maximization，EM)算法對(duì)半監(jiān)督學(xué)習(xí)進(jìn)行研究，使用有限的缺陷傾向性數(shù)據(jù)評(píng)估軟件質(zhì)量.實(shí)驗(yàn)表明，基于EM的半監(jiān)督分類提高了軟件缺陷預(yù)測(cè)模型的泛化性能. 此外，半監(jiān)督軟件缺陷預(yù)測(cè)模型通常會(huì)產(chǎn)生比利用已知故障傾向性模塊訓(xùn)練的決策樹模型更好的性能.

2.2 集成學(xué)習(xí)

集成學(xué)習(xí)方法通過(guò)構(gòu)建并結(jié)合多個(gè)分類器進(jìn)行訓(xùn)練和分類，其泛化性能通常會(huì)優(yōu)于單個(gè)分類器的性能.文獻(xiàn)[11]提出一種基于軟件度量元的集成KNN軟件缺陷預(yù)測(cè)方法，實(shí)驗(yàn)結(jié)果表明集成KNN缺陷預(yù)測(cè)模型的性能與廣泛采用的預(yù)測(cè)方法相比有明顯的提高.文獻(xiàn)[12]提出一種分類不平衡影響分析方法，設(shè)計(jì)了一種新的數(shù)據(jù)集構(gòu)造算法，將原不平衡數(shù)據(jù)集轉(zhuǎn)化為一組不平衡率依次遞增的新數(shù)據(jù)集，實(shí)驗(yàn)結(jié)果表明代價(jià)敏感學(xué)習(xí)和集成學(xué)習(xí)在分類不平衡時(shí)的性能更優(yōu).文獻(xiàn)[13]提出一種多分類不平衡的方法，將特征選擇與Boosting進(jìn)行結(jié)合，實(shí)驗(yàn)結(jié)果表明，所提出的算法分類精確率更高.

隨著半監(jiān)督方法和集成方法的不斷發(fā)展，如何將二者結(jié)合應(yīng)用到軟件缺陷預(yù)測(cè)中，成為一個(gè)值得探究的內(nèi)容.文獻(xiàn)[14]提出一種基于半監(jiān)督集成學(xué)習(xí)的軟件缺陷預(yù)測(cè)方法SSEL，利用軟件中大量存在的未標(biāo)記樣本進(jìn)行學(xué)習(xí)，并采用訓(xùn)練樣本集權(quán)重向量更新策略提升模型的預(yù)測(cè)性能，實(shí)驗(yàn)結(jié)果表明，SSEL模型具有較好的預(yù)測(cè)效果.文獻(xiàn)[15]提出一種基于非負(fù)稀疏圖的SemiBoost軟件缺陷預(yù)測(cè)方法NSSB，由標(biāo)記數(shù)據(jù)、未標(biāo)記數(shù)據(jù)、非負(fù)稀疏相似度矩陣組成一個(gè)提升框架，同時(shí)使用集成分類器Adaboost 提升模型的性能.實(shí)驗(yàn)結(jié)果表明，NSSB方法能有效解決分類不平衡以及標(biāo)記樣本不足的問(wèn)題.文獻(xiàn)[16]提出一種基于搜索的半監(jiān)督集成跨項(xiàng)目軟件缺陷預(yù)測(cè)方法S3EL，實(shí)驗(yàn)結(jié)果表明，S3EL方法在多個(gè)公開數(shù)據(jù)集上與多種典型的跨項(xiàng)目缺陷預(yù)測(cè)方法相比均能獲得較好的預(yù)測(cè)性能，并且能有效提高樸素貝葉斯的預(yù)測(cè)能力.

上述方法大部分只針對(duì)軟件缺陷預(yù)測(cè)中存在的一個(gè)問(wèn)題進(jìn)行研究，即只研究標(biāo)記樣本不足或者類分布不平衡的情況，綜合考慮兩種情況的研究還較少.而且，在軟件缺陷預(yù)測(cè)中，綜合利用Tri_training方法、采樣方法與集成方法的研究還相對(duì)較少.本文創(chuàng)新性地將半監(jiān)督Tri_training方法與集成AdaBoost方法進(jìn)行結(jié)合，同時(shí)在預(yù)標(biāo)注樣本的過(guò)程中加入欠采樣方法，并且在對(duì)新樣本進(jìn)行預(yù)測(cè)之前加入SMOTE過(guò)采樣方法.半監(jiān)督方法能有效利用未標(biāo)記樣本提升分類器的預(yù)測(cè)性能，而采樣方法與集成方法在解決分類不平衡問(wèn)題方面能取得較好的效果.結(jié)合這些方法的優(yōu)勢(shì)對(duì)軟件缺陷的傾向性進(jìn)行分類預(yù)測(cè)，從而有效提高分類模型的性能.

3 基于機(jī)器學(xué)習(xí)的軟件缺陷預(yù)測(cè)模型

軟件缺陷預(yù)測(cè)是一個(gè)二分類問(wèn)題，其分類結(jié)果可以分為有缺陷模塊和無(wú)缺陷模塊，通常使用機(jī)器學(xué)習(xí)方法構(gòu)建軟件缺陷預(yù)測(cè)模型，如圖1所示.

圖1 基于機(jī)器學(xué)習(xí)的軟件缺陷預(yù)測(cè)過(guò)程

圖1展示了靜態(tài)軟件缺陷預(yù)測(cè)的一般過(guò)程，其中預(yù)測(cè)模型通常使用機(jī)器學(xué)習(xí)方法構(gòu)建.基于機(jī)器學(xué)習(xí)的軟件缺陷預(yù)測(cè)過(guò)程如下：

1)數(shù)據(jù)獲取：在獲取缺陷數(shù)據(jù)的過(guò)程中，首先利用版本控制系統(tǒng)以及缺陷跟蹤系統(tǒng)對(duì)軟件歷史倉(cāng)庫(kù)中的項(xiàng)目進(jìn)行屬性度量，然后對(duì)數(shù)據(jù)進(jìn)行歸一化、過(guò)濾等數(shù)據(jù)預(yù)處理操作.

2)特征選擇：數(shù)據(jù)規(guī)模過(guò)大會(huì)對(duì)分類結(jié)果產(chǎn)生一定的影響，選擇合適的特征數(shù)據(jù)集有助于減少計(jì)算量并且能提升分類模型的性能.

3)缺陷預(yù)測(cè)：使用經(jīng)過(guò)調(diào)整后的分類模型對(duì)每個(gè)新的測(cè)試模塊進(jìn)行預(yù)測(cè)，輸出結(jié)果為True或者False，開發(fā)人員可以根據(jù)預(yù)測(cè)結(jié)果對(duì)缺陷模塊進(jìn)行檢查并修改.

4 基于半監(jiān)督集成學(xué)習(xí)算法的軟件缺陷預(yù)測(cè)

假設(shè)L={(x1,y1),(x2,y2)…(xl，yl)}表示有標(biāo)記樣本集，U={xl+1,xl+2,…,xu+l}表示無(wú)標(biāo)記樣本集.x?X代表軟件模塊，x由一組軟件度量元m={d1,d2,d3,…,dn}(di∈Rd)組成.y代表與模塊相對(duì)應(yīng)的缺陷標(biāo)記，其中Y={true，false}，true表示有缺陷模塊，false表示無(wú)缺陷模塊.假設(shè)缺陷模塊數(shù)為D，無(wú)缺陷模塊數(shù)為N.則軟件系統(tǒng)中缺陷率和不平衡率定義如下：

定義1.(缺陷率)軟件系統(tǒng)的缺陷率DP為缺陷模塊數(shù)與總模塊數(shù)的比值：

(1)

定義2.(不平衡率)軟件系統(tǒng)中的不平衡率IP為無(wú)缺陷模塊數(shù)與有缺陷模塊數(shù)的比值：

(2)

從缺陷率以及不平衡率的定義中能夠看出，缺陷模塊數(shù)越多，缺陷率就越高，數(shù)據(jù)集的不平衡程度就越小.

4.1 空指針引用缺陷數(shù)據(jù)集處理

軟件缺陷預(yù)測(cè)結(jié)果一般分為有缺陷和無(wú)缺陷兩類，并沒(méi)有具體到某一種缺陷類別.為了更深入的探究軟件缺陷預(yù)測(cè)模型能否對(duì)具體缺陷類別的數(shù)據(jù)集進(jìn)行預(yù)測(cè)，本文使用兩種類型的數(shù)據(jù)集對(duì)模型進(jìn)行驗(yàn)證.一種是NASA MDP數(shù)據(jù)集，另一種是基于開源項(xiàng)目的包含有空指針引用缺陷的數(shù)據(jù)集.

空指針引用缺陷(Null Pointer Defect,NPD)是一種常見的代碼級(jí)別的缺陷.文獻(xiàn)[17]將空指針引用缺陷定義為：引用了可能為null的變量.以java語(yǔ)言為例，其產(chǎn)生的主要原因如下：

1)當(dāng)一個(gè)對(duì)象不存在時(shí)，調(diào)用其方法會(huì)產(chǎn)生異常，比如object是一個(gè)不存在的對(duì)象，當(dāng)調(diào)用object.method時(shí)會(huì)產(chǎn)生空指針異常.

2)當(dāng)訪問(wèn)或修改一個(gè)對(duì)象不存在的字段時(shí)會(huì)產(chǎn)生異常.比如method對(duì)象不存在，則訪問(wèn)object.method時(shí)會(huì)產(chǎn)生空指針異常.

本文初次嘗試針對(duì)特定的缺陷類別進(jìn)行探究.以java開源項(xiàng)目為例，使用靜態(tài)分析工具SourceMonitor和缺陷檢測(cè)工具Findbugs對(duì)項(xiàng)目中的缺陷進(jìn)行檢測(cè)，將檢測(cè)結(jié)果分為：空指針引用缺陷(NPD)模塊、無(wú)缺陷(No)模塊.經(jīng)Findbugs檢測(cè)后的開源項(xiàng)目缺陷數(shù)量極少，其缺陷率均低于5%，同時(shí)這些缺陷中包含多種不同類別的缺陷.由于本文只針對(duì)空指針缺陷進(jìn)行研究，因此提出一種將空指針引用缺陷注入開源項(xiàng)目中的方法.將原缺陷數(shù)據(jù)集轉(zhuǎn)化為只含有一種空指針缺陷類別的數(shù)據(jù)集.其處理過(guò)程如圖2所示.

圖2 空指針缺陷數(shù)據(jù)集生成過(guò)程Fig.2 Generation process of null pointer defect datasets

為模擬實(shí)際項(xiàng)目中不平衡程度較低和較高兩種情況，將實(shí)驗(yàn)選取的兩個(gè)開源項(xiàng)目中的空指針引用缺陷率設(shè)定為P，P取兩個(gè)不同的值P1和P2，P1和P2的范圍分別設(shè)定為：0< P1<10%,10%< P2<20%.引入空指針缺陷的算法如下：

算法1.空指針缺陷數(shù)據(jù)集構(gòu)造算法

輸入：SourceDataSet -開源項(xiàng)目數(shù)據(jù)集

輸出：New SourceDataSet -含有空指針引用缺陷的開源項(xiàng)目數(shù)據(jù)集

1.將SourceDataSet分為Defect、NoDefect、NullDefect //將源數(shù)據(jù)集分為缺陷、無(wú)缺陷、空指針缺陷數(shù)據(jù)集

2.DNum=Defect.size() //有缺陷樣本數(shù)

3.NNum=NoDefect.size() //無(wú)缺陷樣本數(shù)

4.NPDNum= NullDefect.size() //空指針缺陷樣本數(shù)

5.OtherNum= DNum- NPDNum //非空指針的其他缺陷樣本數(shù)

6.DNum= NPDNum +OtherNum //項(xiàng)目中的缺陷數(shù)為空指針缺陷數(shù)量和非空指針缺陷數(shù)量的和

9.P=Pi(i=1,2) //設(shè)定注入空指針后總的空指針缺陷率為P

10.if (Dp<=P) //開源項(xiàng)目中的缺陷率小于設(shè)定的P值

11. if (Defect has noNPD) //缺陷數(shù)據(jù)集中沒(méi)有空指針缺陷

12. add Dpand P-DpNPD into Defect and NoDefect //將一定比例的空指針缺陷注入缺陷和無(wú)缺陷數(shù)據(jù)集中

13. end if

14. else if (Defecthas NPD)

15. add (P- NPDp) NPD into Defect and NoDefect

16. end if

17.end if

18.if (Dp>P) //開源項(xiàng)目中的缺陷率大于設(shè)定的P值

19. if(Defecthas no NPD)

20. add PNPD into Defect

21. delete (Dp-P) NPD //刪除Dp-P比例的空指針缺陷

22. end if

23. if(Defect has NullDefect and P>=NPDp)

24. add (P- NPDp) NPD into Defect

25. end if

26.end if

27.更新數(shù)據(jù)集 New SourceDataSet

在算法第12、15、20、24步中注入空指針引用缺陷數(shù)據(jù)集時(shí)，選擇符合以下規(guī)則的模塊進(jìn)行添加：根據(jù)開源項(xiàng)目中代碼的特征及結(jié)構(gòu)，選擇源代碼中被賦值為null的對(duì)象并注入空指針缺陷.在Java中每個(gè)類都默認(rèn)繼承Object類，除非聲明繼承某個(gè)類.而Object類中有一個(gè)叫做toString的方法.該方法返回的是該Java對(duì)象的內(nèi)存地址經(jīng)過(guò)哈希算法得出的int類型的值再轉(zhuǎn)換成十六進(jìn)制.這個(gè)輸出的結(jié)果可以等同的看作Java對(duì)象在堆中的內(nèi)存地址.比如有如下代碼,

(1) if (arg == null)

sb.append("nil");

else

return 0;

則將引入空指針后的代碼改為：

(2) if (arg == null)

arg.toString();

sb.append("nil");

else

return 0;

以上述方式引入的空指針引用缺陷不會(huì)破壞代碼的整體結(jié)構(gòu)和功能，同時(shí)Findbug能夠報(bào)告出空指針異常，以此使更新后的實(shí)驗(yàn)數(shù)據(jù)集更具有真實(shí)性.

4.2 擴(kuò)充標(biāo)記樣本

Tri-training算法由Zhou and Li[18]提出，是對(duì)1998年A.Blum和T.Mitchell[19]提出的協(xié)同訓(xùn)練算法Co-training的改進(jìn).Co-training算法要求數(shù)據(jù)集有兩個(gè)充分冗余的視圖，但是在實(shí)際應(yīng)用中很難達(dá)到這一要求.Tri-training算法不要求充分冗余視圖、也不要求使用不同類型的分類器，因此其適用范圍更加廣泛.Tri-training算法使用投票法將三個(gè)分類器進(jìn)行組合之后對(duì)未標(biāo)記樣本進(jìn)行預(yù)測(cè)，投票法能有效減少不相關(guān)特征和冗余特征對(duì)預(yù)測(cè)模型性能的影響.

Tri-training算法擴(kuò)充標(biāo)記樣本時(shí)，首先由其中任意兩個(gè)分類器h1和h2對(duì)任意一個(gè)無(wú)標(biāo)記樣本x∈U進(jìn)行標(biāo)記.如果兩個(gè)分類器對(duì)x的標(biāo)記結(jié)果相同，則將其中一個(gè)標(biāo)記結(jié)果作為分類器h3的訓(xùn)練樣本，即：h1(x)=h2(x)，則將Li={ (x,h2(x))},x∈U加入h3的訓(xùn)練集中.

h3在訓(xùn)練的過(guò)程中若能達(dá)到較高的準(zhǔn)確度，則訓(xùn)練結(jié)果會(huì)得到優(yōu)化；反之，會(huì)將噪聲引入h3的訓(xùn)練集中，降低分類器的標(biāo)記性能.基于此，Zhou等人[18]作出如下證明：

(3)

在PAC可學(xué)習(xí)框架下，如果新標(biāo)記的訓(xùn)練樣本足夠多并且能夠滿足公式(3)中的條件，那么h3再次進(jìn)行訓(xùn)練時(shí)所得假設(shè)的分類性能會(huì)提高.其中，

Lt：第t次迭代時(shí)h1、h2為h3新標(biāo)記的訓(xùn)練樣本

ηL：初始訓(xùn)練集L的噪聲率

第t輪迭代后的分類噪聲率可由如下公式表示：

(4)

(5)

因此，公式(3)可變換如下：

(6)

對(duì)標(biāo)記樣本進(jìn)行擴(kuò)充的過(guò)程中，可用公式(6)判斷經(jīng)分類器h1和h2標(biāo)記的樣本{x,h2(x)}能否加入分類器h3中作為新一輪的訓(xùn)練樣本.

由于Tri-training對(duì)樣本進(jìn)行預(yù)標(biāo)注時(shí)需要使用少量的標(biāo)記樣本和大量的未標(biāo)記樣本，但是標(biāo)記樣本不僅數(shù)量少，而且也是分類不平衡的.為了提高預(yù)標(biāo)注樣本的準(zhǔn)確率，在Tri-training算法中加入欠采樣方法.通過(guò)隨機(jī)刪除訓(xùn)練集中的無(wú)缺陷樣本提升預(yù)標(biāo)注樣本的準(zhǔn)確率.欠采樣方法的偽代碼如下：

算法2.UnderSampling算法

輸入：訓(xùn)練數(shù)據(jù)集S

輸出：采樣后的訓(xùn)練集S_deal

1.正類樣本集Y，負(fù)類樣本集N，S=Y+N

2.for xi∈N do

3. for xj∈N do

4. for xk∈S do

5. Find=false

6. if d(xi,xk)

7. Find=true

8. break

9. end if

10. end for

11. if (Find==true)

12. delete xj//刪除多數(shù)類樣本

13.end if

14. end for

15.end for

16.更新數(shù)據(jù)集S，S_deal=S

4.3 Tri_AdaBoost分類模型

SMOTE(Synthetic Minority OverSampling)算法由Chawla在2002年提出[20].SMOTE是基于隨機(jī)過(guò)采樣算法的一種改進(jìn)方案，其基本思想是對(duì)少數(shù)類樣本進(jìn)行分析并根據(jù)少數(shù)類樣本人工合成新樣本添加到數(shù)據(jù)集中.由于經(jīng)過(guò)擴(kuò)充后的樣本依然是一個(gè)不平衡的數(shù)據(jù)集，因此，為了提高預(yù)測(cè)模型的性能，在對(duì)新數(shù)據(jù)集進(jìn)行分類預(yù)測(cè)之前，使用SMOTE算法對(duì)其進(jìn)行采樣.

AdaBoost(Adaptive Boost)算法由Freund和Schapire在1996年提出[21].AdaBoost是一種集成學(xué)習(xí)算法，集成學(xué)習(xí)就是通過(guò)綜合多個(gè)分類器的預(yù)測(cè)結(jié)果來(lái)提高分類準(zhǔn)確率.該算法的核心思想是針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的弱分類器,它根據(jù)每次訓(xùn)練集中每個(gè)樣本的分類是否正確，以及樣本的分類誤差，來(lái)確定下一次迭代時(shí)每個(gè)樣本的權(quán)值.最后將每次訓(xùn)練得到的分類器按一定的權(quán)重融合到一起，形成強(qiáng)分類器并將其作為最終的決策分類器.

AdaBoost算法使用加法模型，如公式(7)所示.損失函數(shù)為指數(shù)函數(shù)，如公式(8)所示.學(xué)習(xí)算法使用前向分步算法，強(qiáng)學(xué)習(xí)器通過(guò)前向分步算法得到.

加法模型：

(7)

損失函數(shù)：

Ly,f(x)=exp(-yf(x))

(8)

AdaBoost能夠提高分類的準(zhǔn)確性可能有如下兩個(gè)原因：

1)通過(guò)將具有較高誤分類率的分類器進(jìn)行組合，減少了最終分類器的誤分類率.Freud在文獻(xiàn)[22]中證明：假設(shè)AdaBoost每一輪迭代中生成的子分類器錯(cuò)誤率分別為：1,2,…,R,，則集成分類器H的訓(xùn)練錯(cuò)誤率有上界：

(9)

2)最終組合分類器的方差小于弱分類器的方差.

結(jié)合半監(jiān)督算法Tri_training與集成算法Adaboost的優(yōu)勢(shì)，對(duì)AdaBoost算法進(jìn)行改進(jìn)，提出一種新的分類算法Tri_AdaBoost(Tri_training and Adaboost).該算法隨機(jī)選取一部分未標(biāo)記數(shù)據(jù)，利用Tri-Training算法以及欠采樣方法對(duì)未標(biāo)記數(shù)據(jù)集進(jìn)行預(yù)標(biāo)注，將預(yù)標(biāo)注的數(shù)據(jù)集擴(kuò)充到原始的已標(biāo)記數(shù)據(jù)集中形成新的標(biāo)記樣本；再利用SMOTE算法對(duì)新的樣本集進(jìn)行采樣，然后使用采樣后的數(shù)據(jù)集訓(xùn)練AdaBoost分類器；最后，對(duì)測(cè)試集進(jìn)行預(yù)測(cè)并分類.Tri_AdaBoost預(yù)測(cè)模型如圖3所示.

4.4 Tri_AdaBoost分類算法

在集成算法AdaBoost中，隨著分類器的增加，損失函數(shù)會(huì)逐漸減小，即偏差會(huì)越來(lái)越小，方差逐漸增大.因此與構(gòu)成AdaBoost的基礎(chǔ)分類模型相比，AdaBoost更容易過(guò)擬合，但是當(dāng)構(gòu)成AdaBoost的基分類模型比較簡(jiǎn)單時(shí)，AdaBoost模型很難發(fā)生過(guò)擬合，因此本文將單層決策樹DecisionStump作為基礎(chǔ)分類器.使用SMOTE方法對(duì)新數(shù)據(jù)集進(jìn)行采樣時(shí)，過(guò)采樣倍率N設(shè)置為1，k值取5.

Tri_AdaBoost分類算法步驟如算法3所示.

算法3.Tri_AdaBoost算法

輸入：有標(biāo)記訓(xùn)練集L={(x1,y1),(x2,y2)...(x1,y1)}，無(wú)標(biāo)記訓(xùn)練集U={(xl+1),(xl+2)...(xl+u)}，監(jiān)督學(xué)習(xí)算法Learn

1.S_deal=L+U

2.UnderSampling (L) →L′

3.Bootstrap(L′) → L1′,L2′,L3′

4.use Learn and L1′,L2′,L3′ train classifier h1,h2,h3

5.e1′=e2′= e3′=0.5，l1′= l2′= l3′=0

6. repeat training h1,h2,h3

8.fori{1…3} do

9.ei←MeasureError(hj&hk)(j,k≠i)

12. end if

13. untilhjno longer changes

15.end for

17.SMOTE(D,N,k) //D為正類樣例數(shù)目，N為采樣倍率，k為最近鄰數(shù)

18.L={Lj=1/n′| j=1,2,…,n′} //設(shè)置標(biāo)記樣本L中每個(gè)樣本的權(quán)值,經(jīng)SMOTE采樣后的標(biāo)記樣本數(shù)量設(shè)為n′

19.for i=1 to T do // T表示迭代次數(shù)

20. train weak classifier ht

23.end for

圖3 Tri_AdaBoost分類模型的過(guò)程Fig.3 Process of Tri_AdaBoost classification model

5 實(shí) 驗(yàn)

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

實(shí)驗(yàn)數(shù)據(jù)集由兩部分組成.

1)選取開放軟件缺陷數(shù)據(jù)庫(kù)PROMISE庫(kù)[23]中4個(gè)項(xiàng)目的缺陷數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，分別是：PC1，PC3，PC4，KC2，這些數(shù)據(jù)集均由美國(guó)航空航天局(NASA)提供.項(xiàng)目分別采用C語(yǔ)言或java語(yǔ)言實(shí)現(xiàn)，其中包含了對(duì)數(shù)據(jù)集中各模塊有缺陷或者無(wú)缺陷標(biāo)注情況的描述以及對(duì)數(shù)據(jù)集的屬性說(shuō)明，數(shù)據(jù)集中的屬性由McCabe、Halstead等度量方法生成，McCabe、Halstead能客觀的表征與軟件質(zhì)量相關(guān)聯(lián)的質(zhì)量特征.表1給出了4個(gè)項(xiàng)目的基本信息，包括項(xiàng)目名稱、度量元個(gè)數(shù)、模塊總數(shù)、缺陷模塊數(shù)以及缺陷率.

表1 NASA MDP數(shù)據(jù)集基本信息Table 1 Basic information of NASA MDP datasets

2)使用Findbugs缺陷檢測(cè)工具對(duì)aTunes、Nutch兩個(gè)開源項(xiàng)目進(jìn)行檢測(cè)，經(jīng)過(guò)分析總結(jié)之后其缺陷數(shù)據(jù)集信息如表2所示，經(jīng)過(guò)算法1更新后的實(shí)驗(yàn)數(shù)據(jù)集如表3所示.

表2 開源項(xiàng)目數(shù)據(jù)集基本信息

表3 更新后的開源項(xiàng)目數(shù)據(jù)集基本信息Table 3 Basic information updated open source project datasets

表4 混淆矩陣

5.2 評(píng)價(jià)指標(biāo)

軟件缺陷預(yù)測(cè)的結(jié)果可以用含混矩陣表示.如表4所示，以TP、TN、FP、FN表示分類結(jié)果.TP表示被正確分類的正類樣本，TN表示被正確分類的負(fù)類樣本，F(xiàn)P表示實(shí)際為負(fù)類的樣本被錯(cuò)誤分類為正類樣本，F(xiàn)N表示實(shí)際為正類的樣本被錯(cuò)誤分類為負(fù)類樣本.預(yù)測(cè)結(jié)果為正類則表示模塊是有缺陷的，預(yù)測(cè)結(jié)果為負(fù)類則表示模塊是無(wú)缺陷的.

為了有效評(píng)價(jià)分類器的性能及分類不平衡對(duì)分類結(jié)果的影響，采用召回率、精確度、F-measure值、準(zhǔn)確率和AUC值5個(gè)評(píng)價(jià)指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析.AUC作為數(shù)值可以直觀的評(píng)價(jià)分類器的性能，是用來(lái)衡量缺陷預(yù)測(cè)模型好壞的一個(gè)標(biāo)準(zhǔn).各評(píng)價(jià)指標(biāo)可表示如下：

1)召回率(Recall)：被模型正確預(yù)測(cè)的正類樣本占實(shí)際總的正類樣本的比例

(10)

2)AUC：受試者工作特征(Receiver Operating Characteristic，ROC)曲線下方的面積.ROC曲線的橫坐標(biāo)為FPR (false positive rate)，即實(shí)際為負(fù)類的樣本被錯(cuò)誤分類為正類的樣本占實(shí)際總的負(fù)類樣本的比例.縱坐標(biāo)為TPR (true positive rate)，即被正確分類的正類樣本占實(shí)際總的正類樣本的比例.ROC曲線越接近左上角，代表結(jié)果越好.即AUC值越大，分類器性能越好.

3)準(zhǔn)確率(Accuracy)：被模型正確分類的樣本(正類和負(fù)類)占實(shí)際總樣本數(shù)的比例

(11)

4)精度(Precision)：被模型正確分類的正類樣本占被正確分類的正類樣本與被錯(cuò)誤分類的負(fù)類樣本和的比例

(12)

5)F-measure：召回率和精度有時(shí)候會(huì)出現(xiàn)矛盾的情況，這樣就需要綜合考慮二者.最常見的方法是F-measure，它是召回率和精度的加權(quán)調(diào)和平均值.F-measure值較高時(shí)，說(shuō)明模型性能較好.

(13)

5.3 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果及分析

本節(jié)分別對(duì)NASA MDP數(shù)據(jù)集和基于開源項(xiàng)目生成的空指針缺陷數(shù)據(jù)集進(jìn)行分析.選取J48、NaiveBayes兩種經(jīng)典機(jī)器學(xué)習(xí)方法[24]以及Adaboost、RandomForest兩種集成學(xué)習(xí)方法與Tri_Adaboost算法進(jìn)行對(duì)比，實(shí)驗(yàn)所用對(duì)比方法的運(yùn)行參數(shù)均取weka中的默認(rèn)值.

本文實(shí)驗(yàn)設(shè)置如下，將每一個(gè)數(shù)據(jù)集按照3∶2的比例劃分成訓(xùn)練集和測(cè)試集，再根據(jù)特定的標(biāo)記率L將訓(xùn)練集劃分成有標(biāo)記樣本和無(wú)標(biāo)記樣本，本文將L的標(biāo)記率分別設(shè)定為0.2、0.3、0.4三種.對(duì)于本文的方法以及選用的對(duì)比方法采取10折交叉驗(yàn)證的方式重復(fù)進(jìn)行10次實(shí)驗(yàn).比如，對(duì)于Tri_Adaboost方法，假設(shè)數(shù)據(jù)集中有100個(gè)數(shù)據(jù)樣本，從這些樣本中隨機(jī)選取60個(gè)樣本作為半監(jiān)督階段的訓(xùn)練集，對(duì)其余的40個(gè)樣本進(jìn)行標(biāo)記，最后對(duì)所有帶標(biāo)記的樣本進(jìn)行10折交叉驗(yàn)證，選取其中9份作為訓(xùn)練集，1份作為測(cè)試集.

5.3.1 NASA MDP數(shù)據(jù)集實(shí)驗(yàn)結(jié)果及分析

如表5所示為各分類模型在NASA MDP數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

從表5中可以看出，在3種標(biāo)記率下進(jìn)行的共60次評(píng)估結(jié)果中，半監(jiān)督集成學(xué)習(xí)算法(Tri_Adaboost)共獲得52次最優(yōu)值，占比86.7%.其中，

1)在PC1數(shù)據(jù)集上，與其他四種方法相比，Tri_Adaboost方法在三種標(biāo)記率下均獲得最優(yōu)值.

2)在PC3數(shù)據(jù)集上，雖然Tri_Adaboost方法不能一直獲得最優(yōu)值，但是其Accuracy和Recall值與其他幾種方法的差值最大分別為0.033(0.878-0.845)、0.126(0.690-0.564)，依然能得到與對(duì)比方法可比的結(jié)果.由于三種標(biāo)記率下，Tri_Adaboost在AUC以及F-measure上均獲得最優(yōu)值.因此，總體來(lái)說(shuō)，Tri_Adaboost的預(yù)測(cè)性能優(yōu)于其他四種方法.

3)在PC4數(shù)據(jù)集上，Tri_Adaboost方法在Accuracy和Precision上不能一直獲得最優(yōu)值，但是其AUC以及F-measure值均高于對(duì)比方法.因此，Tri_Adaboost的預(yù)測(cè)性能依然優(yōu)于其他四種方法.

4)在KC2數(shù)據(jù)集上，Tri_Adaboost方法在三種標(biāo)記率下均獲得最優(yōu)值.從平均值能夠看出，Tri_Adaboost方法在各個(gè)評(píng)價(jià)指標(biāo)上的均值都高于其他幾種方法.

圖4 各方法在三種標(biāo)記率下的F-measure平均值Fig.4 F-measure mean of each method under three mark rates 圖5 各方法在三種標(biāo)記率下的AUC平均值Fig.5 AUC mean of each method under three mark rates

為了更直觀的看出各分類模型的分類效果，以折線圖表示各分類模型在幾種標(biāo)記率下的F-measure和AUC平均值.從圖4和圖5中可以看出，與其他幾種方法相比，Tri_Adaboost方法的F-measure和AUC最優(yōu).同時(shí)，其F-measure和AUC值分別至少提高了0.344(0.779-0.435)、0.099(0.952-0.853).結(jié)合表5中的實(shí)驗(yàn)結(jié)果可以得出，標(biāo)記樣本的擴(kuò)充以及未標(biāo)記樣本的使用在一定程度上能提升預(yù)測(cè)模型的性能，Tri_Adaboost方法是一種有效的半監(jiān)督集成學(xué)習(xí)方法，并且具備比其他幾種方法較強(qiáng)的學(xué)習(xí)能力.

5.3.2 基于開源項(xiàng)目下的空指針引用缺陷數(shù)據(jù)集實(shí)驗(yàn)結(jié)果及分析

如表6所示為各分類方法在引入空指針缺陷數(shù)據(jù)集后的實(shí)驗(yàn)結(jié)果.

從表6中可以看出，Tri_Adaboost在大部分情況下的評(píng)價(jià)指標(biāo)值都高于其他方法.aTunes和Nutch在三種標(biāo)記率下的AUC值都高于其他方法，即使在Nutch的不平衡率較高的情況下，本文的方法依然能獲得較高的AUC值，說(shuō)明Tri_Adaboost方法能有效的解決分類不平衡的問(wèn)題.同時(shí)，aTunes和Nutch在三種標(biāo)記率下的F-measure值均優(yōu)于對(duì)比方法，說(shuō)明本文所提出的模型性能較好.

表5 不同樣本標(biāo)記率下各分類方法在NASA MDP數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 5 Experimental results of various classification methods on NASA MDP datasets under different sample labeling rates

表6 不同樣本標(biāo)記率下各分類方法在開源項(xiàng)目數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 6 Experimental results of various classification methods on data setsof open source projects under different sample mark rates

以折線圖表示各分類方法在兩個(gè)空指針缺陷數(shù)據(jù)集上的F-meausre和AUC平均值.從圖中可以看出，與其他幾種方法相比，Tri_Adaboost方法在兩個(gè)評(píng)價(jià)指標(biāo)上的平均值能獲得最高值.因此，在空指針引用缺陷數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果依然能表明本文方法的有效性.

6 結(jié)束語(yǔ)

針對(duì)軟件缺陷預(yù)測(cè)中標(biāo)記樣本難以獲取以及類別分布不平衡的情況，本文提出了一種基于半監(jiān)督Adaboost集成方法的軟件缺陷預(yù)測(cè)模型，將Tri_training與AdaBoost兩種算法進(jìn)行結(jié)合形成一種新的分類框架.同時(shí)在擴(kuò)充標(biāo)記樣本的過(guò)程中加入欠采樣方法，以降低Tri_training標(biāo)記樣本時(shí)的錯(cuò)誤率；在分類預(yù)測(cè)之前，對(duì)擴(kuò)充樣本集進(jìn)行SMOTE采樣，以降低新樣本集的不平衡率，提升模型的性能.實(shí)驗(yàn)中除使用NASA MDP數(shù)據(jù)集進(jìn)行驗(yàn)證外，首次嘗試使用基于開源項(xiàng)目生成的空指針引用缺陷數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn).

圖6 各方法在三種標(biāo)記率下的F-measure平均值Fig.6 F-measure mean of each method under three mark rates圖7 各方法在三種標(biāo)記率下的AUC平均值Fig.7 AUC mean of each method under three mark rates

從實(shí)驗(yàn)結(jié)果可以看出，本文提出的Tri_AdaBoost方法在不同比例的標(biāo)記樣本下的預(yù)測(cè)效果均優(yōu)于J48、NaiveBayes、Adaboost以及RF.下一步工作的重點(diǎn)將探究度量元對(duì)軟件缺陷預(yù)測(cè)的影響，并且將嘗試加入其它類別的軟件缺陷進(jìn)行實(shí)驗(yàn)，同時(shí)會(huì)進(jìn)一步探究無(wú)監(jiān)督方法與集成方法或者半監(jiān)督方法與Bagging等集成方法的結(jié)合對(duì)軟件缺陷預(yù)測(cè)模型的影響.