一種改進的半監督集成軟件缺陷預測方法

周建含,李英梅,李文昊

(哈爾濱師范大學 計算機科學與信息工程學院,哈爾濱 150000)

1 引 言

軟件缺陷是編程人員在編碼過程中因開發過程管理不當,難以正確理解軟件需求、或者開發經驗欠缺等原因產生的[1].軟件缺陷對軟件的生產帶來負面的影響,會浪費大量的財力人力,因此,項目主管會在軟件部署前通過軟件測試等手段盡可能地找出軟件中存在的缺陷,但是對所有的軟件模塊進行測試將是一項巨大的工程,可能會超出軟件開發預算或延誤軟件發布時間.軟件缺陷預測技術可以根據軟件的歷史數據信息,通過機器學習等方法來預測軟件模塊中是否含有缺陷,從而對可能含有缺陷的模塊投入足夠的測試資源[2].

目前,許多研究人員通過有監督機器學習建立起了很多性能優越的軟件缺陷預測模型[3-8]但是,由于各種現實原因,很多時候無法獲取到足夠的標記模塊信息.在這種帶標記模塊有限,未標記模塊充足的情況下,使用有監督機器學習建立的軟件缺陷預測模型往往不能取得較好的預測結果[9].因此,一些研究人員利用半監督機器學習建立了軟件缺陷預測模型[10-14],來緩解標記樣本匱乏的問題.但很少有研究考慮解決類不平衡和特征冗余、不相關問題對半監督軟件缺陷預測模型帶來的影響.因此本文分別在解決半監督缺陷預測模型的類不平衡和特征冗余、不相關問題上對多種方法進行了實驗分析,最終在監督集成學習算法Tri-training的基礎上提出一種改進的半監督集成軟件缺陷預測方法FeSSTri.

FeSSTri是個兩階段算法:

1)對目標數據集中的標記樣本使用ADASYN自適應綜合過采樣算法進行采樣,通過增加少數類樣本,使少數類樣本規模與多數類樣本規模達到一致,來解決半監督缺陷預測模型中的類不平衡問題.

2)利用標記樣本結合采樣后的半監督預測結果,使用最小冗余最大相關mRMR算法對目標數據集進行特征選擇,得到最優的特征子集,解決特征冗余、不相關問題.

最后,利用采樣后以及特征選擇后的訓練集使用Tri-training算法構建最終的預測模型.

本文在NASA數據集和AEEEM數據集上對FeSSTri算法進行了驗證,在標記模塊數量較少的情況下,相較于普通的Tri-training算法和經典的機器學習算法,FeSSTri可以取得更好的預測結果.

2 相關研究

軟件缺陷預測的領域中有標記樣本的數量與未標記樣本的數量相比微乎其微,典型的有監督學習方法難以建立有效的預測模型,并且獲得大量有標記樣本的費用十分昂貴,而與有監督學習方法不同,半監督學習方法能同時利用少部分有標簽樣本和大部分沒有標簽的樣本進行學習,解決了實際環境中有標記樣本難以獲取的問題,增強了分類模型的準確性.

2.1 半監督軟件缺陷預測研究

Seliya等人基于期望最大化EM(Expectation-Maxi-mization)算法建立半監督預測模型,實驗證明,該模型提高了預測的泛化性能[15].Catal等人利用半監督學習算法YASTI(Yet Another Two-Sta-ge Idea)構建了軟件缺陷預測模型,并在YASTI算法的第一階段對多種機器學習算法進行了實驗,實驗表明利用樸素貝葉斯算法構建的YASTI半監督軟件缺陷預測模型效果最好.Lu等人提出了一種半監督軟件缺陷預測模型FTF(Fitting The Fits),FTF第一步為全部未標記的實例設置標簽,然后迭代訓練模型直到未標記實例的預測結果趨于穩定,實驗結果證明FTF在標記數據有限的情況下可以有效提高隨機森林的預測結果[16].Lu HH等人提出了一種半監督降維學習的軟件缺陷預測方法,是自訓練算法FTcF(Fitting-the-confifident-Fits)的變體,通過利用標記樣本反復進行訓練,在每次迭代中對未標記樣本進行預測,并且在降低軟件度量的維度復雜性方法中嵌入了一個預處理策略,實驗結果表明在降維之后半監督學習的預測效果顯著優于隨機森林算法[17].通過上述研究可以發現,在標記樣本有限、未標記樣本充足的情況下使用半監督學習算法構建軟件缺陷預測模型的效果會更好,但是上述研究都很少考慮到類不平衡問題對半監督軟件缺陷預測帶來的影響.

針對半監督軟件缺陷預測中的類不平衡問題,Ma等人提出一種基于半監督集成學習算法Tri-training的軟件缺陷預測模型RusTri,通過對多數類樣本作隨機抽樣的方法,使得Tri-training每次迭代更新的訓練數據集達到類間平衡,實驗證明,RusTri可以有效提升Tri-training的預測效果[9].張肖等人提出一種半監督集成軟件缺陷預測方法Tri_Adaboost,通過欠采樣和集成學習算法Adaboost來解決類不平衡問題的影響.Tri_Adaboost首先對標記樣本進行欠采樣,利用Tri-training算法擴充標記樣本,然后利用已標記樣本使用Adaboost算法構建最終的預測模型[2].上述研究的實驗結果表明基于Tri-training算法構建的半監督軟件缺陷預測模型效果非常好,但是上述研究都是利用欠采樣方法來解決類不平衡對Tri-training算法的影響.在軟件缺陷數據集中,有缺陷模塊只能占到總體數目的10%-20%,如果使用欠采樣方法訓練數據集,使多數類樣本減少到少數類樣本數目,會丟棄大量寶貴的標記樣本信息.因此,本文在采樣階段使用ADASYN自適應綜合過采樣算法來解決類不平衡對Tri-training算法的影響.

2.2 軟件缺陷預測的特征選擇研究

特征選擇可以消除冗余特征和無關特征,從而得到良好的特征子集達到降維的效果,使模型泛化能力更強并有效提高分類模型的分類效果[18-20].Wang 等人借助集成學習方法來提高特征選擇的性能[21].Menzies等人基于信息增益利用前向搜索和窮盡搜索來尋找最優特征子集[22].Song等人在缺陷預測框架中考慮了包裹式特征選擇方法[23].Shivaji 等人在基于代碼修改的軟件缺陷預測中對各種特征選擇方法進行了實驗[24].Gao等人對多種過濾式特征選擇方法在不同的子集評估策略上進行了實驗對比[25].

但是目前在軟件缺陷預測中常用的過濾式特征選擇方法主要依據特征與標簽列的相關度來進行選擇,很少考慮特征之間的相似性,因此選出的特征子集很容易出現冗余問題.Peng等人提出了一種濾波式的特征選擇方法mRMR(Max-Relevance,and Min-Redundancy)可以找出最小冗余最大相關的特征子集[26].因此,本文在半監督軟件缺陷預測中對mRMR算法進行了嘗試并與經典的過濾式特征選擇方法進行了對比.

雖然,特征選擇在軟件缺陷預測領域已經有了很多研究[27],但很少有研究考慮到提出的方法在半監督軟件缺陷預測上的適應性.因此本文提出一種應用在半監督軟件缺陷預測上的特征選擇框架,可以充分利用標記樣本和未標記樣本的信息.首先,利用采樣后的半監督分類器可以建立一個有效的半監督缺陷預測模型,使用該模型對未標記樣本進行預標記,然后對所有的已標記樣本信息使用特征選擇方法來對特征進行選擇,實驗證明在標記樣本有限、未標記樣本充足的情況下該框架可以有效提高特征選擇方法的性能.

3 改進的半監督集成軟件缺陷預測模型

3.1 研究動機

利用軟件的歷史缺陷信息以及相關度量,通過機器學習算法可以構建出有效的軟件缺陷預測模型以此將足夠的測試資源投入到可能存在缺陷的軟件模塊中.但是在實際環境中,由于軟件模塊的缺陷信息難以獲取,常常面對標記模塊有限、未標記模塊充足的情況,因此構建一種穩定有效的半監督軟件缺陷預測模型是非常有意義的.軟件缺陷預測中的類不平衡、特征冗余和不相關問題會嚴重影響半監督軟件缺陷預測模型的預測效果,因此本文基于采樣和特征選擇方法提出了一種改進的半監督集成軟件缺陷預測方法FeSSTri來解決上述問題.

3.2 算法框架

圖1、圖2為FeSSTri算法的框架圖,其中圖1為FeSSTri算法得到最優特征子集的過程,圖2為FeSSTri算法構建最終軟件缺陷模型的過程.如圖1所示,為了解決半監督缺陷預測的無關特征、冗余特征的問題,FeSSTri使用最小冗余最大相關mRMR算法進行特征選擇,得到最優特征子集.但是由于初始標記樣本數量很少,如果直接利用初始標記數據來進行特征選擇只能獲取到整體數據集的局部信息并且容易造成過擬合,降低軟件預測模型的泛化性能.因此為了充分利用初始的標記樣本和未標記樣本的信息,本文提出了一種適應于半監督軟件缺陷預測的特征選擇框架.首先利用過采樣后的標記樣本使用Tri-training算法建立一個效果良好的半監督分類器,使用該分類器給未標記樣本進行預標記,然后利用初始標記樣本和預標記樣本的信息進行特征選擇.用上述方法尋找到的特征子集增強了分類器的泛化性能并且更加貼近原數據集的全局信息特點.

圖1 FeSSTri算法過程1

如圖2所示,在得到最優特征子集后,再將過采樣后的標記樣本根據最優特征子集進行特征選擇,使用Tri-training算法構建最終的軟件缺陷預測模型,最后用此模型對同樣特征選擇后的初始未標記樣本進行預測,得出預測結果.

圖2 FeSSTri算法過程2

3.3 采樣階段

軟件缺陷預測中的類不平衡問題是指訓練數據集中無缺陷樣本的數目要遠遠大于有缺陷樣本的數目.在這種情況下,如果直接使用機器學習算法構造分類器雖然可以較好地預測大類樣本,但是無法對小類樣本進行準確預測.軟件缺陷數據集就存在著嚴重的類不平衡問題,有缺陷樣本往往只能占到數據集的10%-20%,所以解決類不平衡問題是構建軟件缺陷預測模型的一個重要課題.

采樣方法是一種在數據層面上解決類不平衡問題的有效手段,通過采樣可以使得數據集中各類別的樣本數目達到一致.采樣方法一般分為欠采樣和過采樣,欠采樣減少了大量的大類樣本,使其數目與小類樣本達到一致,過采樣則是增加小類樣本的數目,使其數量與大類樣本達到一致.在半監督軟件缺陷預測模型的構建中,往往只能夠獲取到一個完整數據集10%-40%的標記樣本數據而且里面的有缺陷樣本更是少之又少,如果采用欠采樣方法會丟失大量寶貴的標記樣本信息.因此,采用過采樣方法來解決半監督軟件缺陷預測模型的類不平衡問題更加合理.

1)計算需要合成的樣本總數量:

(1)

其中,Smaj為大類樣本數量,Smin為小類樣本數量,β∈(0,1)為系數,這里設為1即合成后小類樣本數目與大類樣本數目達到一致.

2)對于每個小類樣本xi,找出其K個最近鄰點,并計算:

(2)

其中,Δi為K近鄰個點中大類樣本的數量.

(3)

3)計算每個小類樣本xi需要合成的樣本數量gi,最后用SMOTE方法合成新樣本:

(4)

由以上描述可知,在ADASYN算法中,小類樣本周圍的大類樣本越多,則其周圍生成的新樣本就越多.這樣生成的新樣本大多都在分類邊界處,可以提供有效的分類信息.ADASYN自適應綜合過采樣算法偽代碼如下:

算法1.ADASYN自適應綜合過采樣算法

輸入:初始標記樣本集合S、小類樣本近鄰數目K

輸出:過采樣后的標記樣本集合S′

1.Calculate the number of samples for large and small categories:Smaj、Smin;

2.Calculate the total number of samples to be generated:G=Smaj-Smin;

3.forXi∈Smin

4. Calculates the number of samples of large classes in K nearest neighbors:Δi

6.end for

7.forXi∈Smin

9. for 1:gi

10. Generate new samples:xnew=xi+(gi-xi)*δ,δ∈(0,1)

11. S′=S+xnew

12. end for

13.end for

14.return S′

3.4 特征選擇階段

軟件工程師為了提高軟件缺陷預測的準確性,增加了很多與軟件缺陷密切相關的度量標準來度量程序模塊,但是隨著軟件產品復雜度的增加,就會生成大量的特征值,導致了高維問題.使用特征選擇可以從高維數據集中選出所含分類信息豐富的特征子集,降低數據集維度,提高預測模型的預測能力.一個優秀的特征子集有兩大特點:1)具有很大的分類識別信息量,2)具有很強的獨立性,因為特征間相關性太強難以提供多余的分類信息.在軟件缺陷預測的研究中,過濾式特征選擇是常用的方法,即選出與標簽列相關性最大的特征,常用的相關性度量有距離相關系數、信息增益率、Pearson相關系數、卡方檢驗值等.上述方法都僅考慮了特征與分類變量之間的相關性而沒有考慮到特征冗余問題,這就導致所選特征可能并不具備較好的獨立性.

Peng等人提出一種最小冗余最大相關mRMR特征選擇方法,該方法保證了所選特征和分類變量的相關度達到最高,而特征與特征之間的相關度最小.因此,采用mRMR方法更加合理.在mRMR中,互信息用來度量相關性,特征集S與標簽列c的相關性是根據各個特征fi和標簽列c之間的所有互信息值的平均值定義,如下所示:

(5)

集合S中所有特征的冗余由每個特征之間的所有互信息值的平均值定義:

(6)

mRMR方法定義如下:

(7)

mRMR方法根據已選擇的特征,對剩下的候選子集中的特征進行計算并且排序,以便找到能使上述公式最大化的特征.這種搜索方法為增量搜索,目的是要找到最優特征子集.假設我們已有特征集Sm-1,那么接下來就是從剩下的特征F-Sm-1中找到第m個特征使得下式值最大:

(8)

基于mRMR的半監督軟件缺陷預測特征選擇方法偽代碼如下:

算法2.最小冗余最大相關mRMR算法

輸入:數據集S、特征集合F、特征選擇數目K

輸出:最優特征子集F′

1.set F′={};

2.set bestF=-1;

3.set bestScore=0;

4.for x in 1:K

5. forfj∈F

7. if Score>bestScore

8. bestScore=Score;

9. bestF=fj;

10. end if

11. end for

12. F′=F′+fj;

13. F=F-fj;

14.end for

15.return F′

3.5 利用Tri-training算法構建半監督軟件缺陷預測模型

Tri-training算法是非常強大的半監督集成學習方法,能夠使用少量標記的數據來構建效果良好的分類器,可以很好的解決標記模塊不足的問題.Tri-training算法首先對帶有標記的數據進行3次隨機抽樣,以此訓練出各不相同的分類器,之后對沒有標記的數據作出預測.若兩個分類器將一個未標記的樣本預測為負類,而第3個分類器預測為正類,那么第3個分類器應該把這個樣本當作負類學習,通過3個分類器相互通知,很容易地處理標記置信度估計問題.對3個分類器進行多次迭代訓練直至結果趨于穩定,最后使用最大投票法對3個分類器進行集成學習.可是在有些情況下,多數票分類器的預測結果有可能是錯誤的,那么就會給少數票分類器引入噪音,但是Z.-H.Zhou 和 M.L[28]表明,在一定條件下,分類噪聲率的增加可以由新標記樣本的數量補償.在本文中Tri-training算法的基分類器采用RandomForest分類器.

Tri-training算法、FeSSTri算法偽代碼如下:

算法3.Tri-training算法

輸入:標記數據集S、未標記數據集U

輸出:未數據集U的預測結果Y(U)

1.Bootstrap(S)→S1′,S2′,S3′;

2.RandomForest(S1′),RandomForest(S2′),RandomForest(S3′)→h1,h2,h3;

4.repeattrainingh1,h2,h3

5. for i in 1:3

6.ei←MeasureRrror(hj&hk)(j,k≠i)

8. usehjandhkto predict samples in U,append them into Si′;

9. end if

10.untilh1,h2,h3no longer change

11.retrun Y(U)=vote(h1(U),h2(U),h3(U));

算法4.FeSSTri算法

輸入:初始標記樣本集合S、初始未標記樣本集合U、特征集合F、特征選擇數目K

輸出:未標記樣本集合U的預測結果Y(U)

1.ADASYN(S,5)→S′;

2.Tri-training(S′,U)→U′;

3.L=S+U′

4.mRMR(L,F,K)→F′;

5.S*←FeatureselectionofS′ by F′;

6.U*←Featureselectionof U′ by F′;

7.Y(U)=Tri-training(S*,U*);

8.return Y(U);

4 實 驗

4.1 實驗設計

為驗證FeSSTri方法在各階段的有效性,設計了3組實驗進行對比.

第1組實驗驗證ADASYN自適應綜合過采樣算法在采樣階段的有效性,選取隨機欠采樣、隨機過采樣、SMOTE過采樣以及不做采樣的Tri-training算法作為對比算法.

第2組實驗驗證本文提出的適應于半監督學習的特征選擇框架的有效性,以及mRMR算法在特征選擇階段的有效性,選取基于信息增益率的過濾式方法、基于Pearson相關系數的過濾式方法、基于卡方檢驗值的過濾式方法以及不做特征選擇的Tri-training算法作為對比算法.

第3組實驗驗證本文提出的FeSSTri方法在半監督軟件缺陷預測上的有效性,選取J4.8、NaiveBayes、RandomForest、Tri-training算法作為對比算法.

上述實驗數據均采用NASA數據集和AEEEM數據集,以F1值為實驗評測指標.上述所有算法均基于python的sklearn工具包來實現.參照文獻[9],將3組實驗數據集的標記率設定為0.2,即隨機選取數據集中的20%作為標記樣本訓練集,剩下80%的未標記樣本作為輔助數據集和測試集.參照文獻[29],將特征選擇的數量設置為原始特征數目的40%.每組實驗均隨機選取10次標記樣本,每次對各算法分別運行10次,取100次實驗結果的平均值作為最終結果.

4.2 實驗數據集

本研究使用了具有代表性的NASA數據集和AEEEM數據集[30-33],表 1和表2列出了這兩個數據集的統計特征.

表1 NASA 數據集信息

表2 AEEEM 數據集信息

NASA數據集在軟件缺陷預測領域被廣泛應用,因為NASA中的數據有很強的的真實性,提升了數據集的可信度.

AEEEM 數據集是由 D′Ambros 等人[33]搜集,他們分析了5個開源項目,從中收集到61種不同的度量元,這些度量元關注了代碼復雜度以及軟件的開發過程.

4.3 實驗評測指標

軟件缺陷預測是一個二分類問題,并且對于每個樣本都有兩個標記,一個是樣本的真實類別,另一個是預測出來的類別,因此我們可以用混淆矩陣[34]中的數據來評估預測算法的性能.可能的結果如下:樣本的真正標記是正,也被預測為正,記為 TP(true positive);樣本的真正標記是正,但是被預測為負,記為FN(false negative);樣本的真正標記是負,但是被預測為正,記為FP(false positive);樣本的真正標記是負,也被預測為負,記為TN(true negative).通過這4種評估指標可以初次評估算法的性能,之后可以定義查準率(precision)、召回率(recall)以及F1度量(F1-measure).

1)查準率:在所有被預測為有缺陷的實例中,真實類別為有缺陷的實例所占的比例.

(9)

2)召回率:在所有真實類別為有缺陷的實例中,被正確預測為有缺陷的實例所占的比例.

(10)

3)F1度量:是一個綜合評估數,是召回率和查準率之間的權衡.

(11)

查準率能得出檢索到的缺陷模塊有多少是準確的,召回率能得出模型是否能預測出有缺陷模塊的能力.但是查準率和查全率是一對矛盾的度量,而F1是通過計算查準率和召回率的調和平均定義的,可以避免出現極端現象,能夠得出合理的性能估計.基于以上原因,本文使用 F1 評價各方法的性能.

4.4 實驗結果分析

4.4.1 采樣階段實驗結果及分析

表3、表4為Tri-training算法經過不同采樣算法后在NASA數據集和AEEEM數據集上的實驗結果.由表3、表4可見,在缺陷模塊較少的NASA數據集上,隨機欠采樣方法只有在項目cm、jm上可以略微改進Tri-training算法的預測結果,在其余項目上的預測結果均比初始Tri-training算法差;

表3 各采樣方法在NASA數據集上的F1值

而在缺陷模塊較多的AEEEM數據集上,隨機欠采樣方法只有在缺陷數目較少的項目LC上的預測結果低于初始Tri-training算法.說明當訓練集所含的缺陷模塊信息很少時,使用欠采樣方法會丟失訓練集中大量寶貴的標記模塊信息從而使得訓練后的預測模型性能降低.在表3、表4中可以看出隨機過采樣、SMOTE過采樣、ADASYN自適應綜合過采樣方法在NASA和AEEEM兩個數據集上均可以提升初始Tri-training算法的預測結果,其中ADASYN自適應綜合過采樣方法的提升最大,SMOTE方法次之,說明使用過采樣方法解決半監督軟件缺陷預測的類不平衡問題效果更好,使用ADASYN自適應綜合過采樣方法可以達到最好.

表4 各采樣方法在AEEEM數據集上的F1值

4.4.2 特征選擇階段實驗結果及分析

表5、表6為Tri-training算法經過不同特征選擇方法后在NASA數據集和AEEEM數據集上的實驗結果,其中括號里的數據為該特征選擇方法在本文提出的適應于半監督學習的特征選擇框架下的實驗結果.由表5、表6可見,在兩個數據集上本文提出的適應于半監督學習的特征選擇框架可以提升基于信息增益率的過濾式方法、基于卡方檢驗值的過濾式方法以及最小冗余最大相關mRMR方法的預測結果,只有在基于Pearson相關系數的過濾式方法上會降低原方法的預測結果.其中,基于信息增益率的過濾式方法和基于卡方檢驗值的過濾式方法在使用該框架后才可以提升初始Tri-training算法的預測結果,說明本文提出的特征選擇框架可以在標記模塊有限的情況下充分利用未標記模塊的信息使得特征選擇方法更加有效.

表5 各特征選擇方法在NASA數據集上的F1值

表6 各特征選擇方法在AEEEM數據集上的F1值

由表5、表6可見在本文提出的特征選擇框架下,基于信息增益率的過濾式方法、基于卡方檢驗值的過濾式方法以及最小冗余最大相關mRMR方法均可以提升初始Tri-training算法的預測結果,其中最小冗余最大相關mRMR方法的提升效果最大,說明mRMR方法在軟件缺陷預測的特征選擇階段更加有效.

4.4.3 FeSSTri實驗結果及分析

圖3、圖4為NASA數據集和AEEEM數據集上的各分類模型在0.2標記率下的平均實驗結果.由圖3、圖4可見,在兩個數據集上本文提出的FeSSTri方法可以有效提高Tri-training算法的預測結果,并且比起J48、NaiveBayes、RandomForest等算法也可以取得最佳的預測結果.在NASA數據集上,FeSSTri與其他4種經典算法相比,性能可以提升36%、41%、45%、18%;在AEEEM數據集上,FeSSTri與其他4種經典算法相比,性能可以提升40%、27%、22%、14%.由此可說明,結合了ADASYN自適應綜合過采樣方法和最小冗余最大相關mRMR方法的FeSSTri是一種有效的半監督軟件缺陷預測模型.

圖3 各方法在NASA數據集上的F1平均值

圖4 各方法在AEEEM數據集上的F1平均值

5 結束語

為了進一步提升半監督軟件缺陷預測模型的性能,本文提出一種半監督集成軟件缺陷預測方法FeSSTri,采用ADASYN自適應綜合過采樣算法以及最小冗余最大相關mRMR算法來解決半監督軟件缺陷預測中的類不平衡和特征冗余、不相關問題.實驗表明,FeSSTri方法可以在采樣階段和特征選擇階段最大化提升基于Tri-training算法的半監督軟件缺陷預測模型的效果,并且比起經典的機器學習算法在標記樣本不足的情況下可以取得更好的預測結果.下一步工作主要探究特征選擇的數量對軟件缺陷預測模型的影響以及包裹式特征選擇方法在半監督軟件缺陷預測模型中的應用.