穩(wěn)健邊界強化GMM-SMOTE軟件缺陷檢測方法

羅森林， 蘇霞， 潘麗敏

(北京理工大學 信息與電子學院，北京 100081)

軟件目前被廣泛用于自動化和操作系統(tǒng)，在軟件開發(fā)過程中不可避免的會產(chǎn)生功能、算法、交互等多種類型的缺陷(Bug)，若未能及時發(fā)現(xiàn)軟件產(chǎn)品中存在的缺陷而直接上線應用，可能會帶來不可預期的后果[1].隨著“持續(xù)交付模型”的廣泛應用，系統(tǒng)、軟件的開發(fā)日趨快速化與實時化，即時準確地進行自動化軟件缺陷檢測變得日漸重要.

研究表明，軟件是否有缺陷與某些軟件度量指標有很強的相關(guān)性，例如McCabe度量和Halstead度量等[2].因此，通過提取這些度量指標來構(gòu)造特征向量，并訓練機器學習模型以識別有缺陷的軟件已成為行之有效的檢測方法，與傳統(tǒng)的匹配檢測相比，檢測速度更快，精度更高[3].但面臨著數(shù)據(jù)不平衡這一挑戰(zhàn)，即被人工準確標記了缺陷的正樣本稀少，與之相應的則是大量被認定為無缺陷的負樣本，由此導致分類器易忽略正類實例特征，使分類結(jié)果更傾向?qū)嵗卸樨擃?，引發(fā)判別規(guī)則偏移問題，降低了軟件缺陷的識別精度.如何解決軟件缺陷檢測中數(shù)據(jù)不平衡的問題逐漸成為研究熱點.

目前針對數(shù)據(jù)不平衡問題的解決方案主要可分為3大類：數(shù)據(jù)層面、特征層面和算法層面[4].其中數(shù)據(jù)層面主要是通過對原始數(shù)據(jù)進行采樣來改變數(shù)據(jù)的分布狀況，改善不平衡情況，可解釋性強，與學習算法耦合性低、普適性好，因而在軟件缺陷檢測領(lǐng)域受到廣泛關(guān)注.

現(xiàn)有研究中，針對軟件缺陷檢測中數(shù)據(jù)不平衡的問題提出了一系列基于采樣方法的學習算法.Naufal等[5]使用SMOTE進行數(shù)據(jù)平衡，并采用模糊關(guān)聯(lián)規(guī)則挖掘(FARM)及CFS選擇復雜性指標實現(xiàn)軟件缺陷檢測.Bennin等[6]的研究提出了一種基于染色體遺傳學理論的軟件缺陷數(shù)據(jù)集的新型高效合成過采樣方法MAHAKIL.Huda等[7]使用不同的過采樣技術(shù)來構(gòu)建集合分類器，該分類器可以減少缺陷數(shù)據(jù)中少數(shù)樣本的影響.可以看出，在基于平衡化采樣的軟件缺陷檢測方法中，為避免因欠采樣過程刪除多數(shù)類樣本所導致的關(guān)鍵信息丟失問題，研究普遍使用過采樣來豐富原始數(shù)據(jù)中的少數(shù)類，一定程度上提高了分類器的判別性能.

過采樣方法通?？蓮臄?shù)據(jù)層面直接解決其多數(shù)類、少數(shù)類不平衡性問題，廣泛應用在各類機器學習任務中[8].隨機過采樣是最基本的過采樣方法之一，通過隨機的復制少數(shù)類樣本，達到類別平衡的目的.隨機過采樣簡單易實現(xiàn)，但是由于只是單純復制少數(shù)類樣本，容易導致過擬合.為解決該問題，Chawla等[9]提出了少數(shù)類樣本合成過采樣技術(shù)(SMOTE)，通過隨機選擇少數(shù)類樣本以及其相鄰的少數(shù)類樣本，對其線性插值來生成新樣本，可以顯著改善過擬合問題.然而該方法中，當噪聲點被選中來進行線性插值時，會進一步放大數(shù)據(jù)中的噪聲問題.為此，Georgios等[10]提出了K-means SMOTE方法，利用K-means聚類篩選高置信度樣本，可緩解采樣過程中的噪聲放大問題，但易將邊界點視為低置信樣本，降低其采樣率，模糊分類邊界.相反，Han等[11]提出的borderline-SMOTE方法，只在邊界附近的少數(shù)類樣本進行過采樣，雖解決了邊界模糊問題，但仍會受到噪聲影響，限制其穩(wěn)健性.

綜上，現(xiàn)有軟件缺陷檢測方法在數(shù)據(jù)平衡過程中，對噪聲點、邊界點的無區(qū)別對待或是不準確區(qū)分，是導致訓練數(shù)據(jù)噪聲加劇、邊界模糊的主要原因，由此限制了后續(xù)判別模型的穩(wěn)健性及準確性.為此，提出一種穩(wěn)健邊界強化GMM-SMOTE方法，通過建立簇內(nèi)類別比與后驗概率約束，精準識別噪聲點與邊界點，并以此為基礎(chǔ)進行加權(quán)過采樣，實現(xiàn)數(shù)據(jù)集的優(yōu)化平衡，提升軟件缺陷檢測模型的訓練及泛化性能.

針對上述問題，提出一種穩(wěn)健邊界強化GMM-SMOTE軟件缺陷檢測方法，其主要貢獻包括：(1)穩(wěn)健邊界強化數(shù)據(jù)平衡，可在防止判別規(guī)則偏移的同時，實現(xiàn)訓練數(shù)據(jù)的噪聲抑制及邊界強化；(2)在此基礎(chǔ)上，構(gòu)建多種基于集成學習、神經(jīng)網(wǎng)絡(luò)的軟件缺陷檢測模型，并在NASA公開的多個數(shù)據(jù)集上實驗證明該方法的有效性.

1 算法原理

1.1 原理框架

針對軟件缺陷檢測中數(shù)據(jù)不平衡問題，通過GMM-SMOTE對訓練數(shù)據(jù)進行穩(wěn)健邊界強化過采樣，在平衡優(yōu)化后的數(shù)據(jù)集上通過隨機森林、XGBoost和多層感知機等分類器進行缺陷檢測模型的構(gòu)建.其中(1)針對SMOTE方法易將噪聲點作為種子生成新樣本，使噪聲加劇的問題，通過高斯混合模型進行聚類，利用簇內(nèi)約束比進行非噪聲可靠樣本選擇；(2)針對穩(wěn)健過采樣方法易將邊界點識別為低置信度樣本，降低其采樣率而使邊界模糊的問題，利用后驗概率確定邊界點提高其采樣率.穩(wěn)健邊界強化GMM-SMOTE軟件缺陷檢測方法的原理框架圖如圖 1所示.

圖1 原理框架圖

1.2 GMM-SMOTE

軟件缺陷中的類不平衡問題會對分類模型的判別性能產(chǎn)生重大影響，對缺陷數(shù)據(jù)進行預處理，提升訓練數(shù)據(jù)集質(zhì)量是缺陷檢測模型構(gòu)建的關(guān)鍵初始步驟.GMM-SMOTE是一種處理不平衡問題并提升數(shù)據(jù)質(zhì)量的優(yōu)化算法，該算法可分為3步：高斯混合聚類、可靠樣本選擇以及邊界強化過采樣.

1.2.1高斯混合聚類

高斯混合模型(GMM)由于其多峰特性在實際應用中擬合范圍廣，在理論上能逼近任意分布[12].為挖掘軟件缺陷數(shù)據(jù)分布情況，采用高斯混合聚類方法進行擬合數(shù)據(jù)結(jié)構(gòu)并進行群集劃分.高斯混合模型由M個單高斯分布加權(quán)線性組合而成，其樣本分布為

(1)

高斯混合模型可以由參數(shù)θ=(ωi,μi,Σi)來確定.給定樣本數(shù)據(jù)X={x1,x2,…,xN}，通常用極大似然估計來求解模型參數(shù)θ.由于似然函數(shù)是θ的非線性函數(shù)，無法直接對參數(shù)求偏導來進行求解，可通過期望最大化(EM)算法[13]來迭代優(yōu)化.E步根據(jù)當前參數(shù)來計算每個樣本屬于每個高斯成分的后驗概率，第i個成分的后驗概率為

(2)

M步通過固定E步中的后驗概率來更新模型的混合系數(shù)、均值和方差.

1.2.2可靠樣本選擇

SMOTE通過對少數(shù)類進行線性插值來合成新少數(shù)類樣本[14]，但在對位于多數(shù)類樣本中的噪聲少數(shù)類樣本進行線性插值時，生成的新樣本大概率也是噪聲樣本，這樣就放大了數(shù)據(jù)中存在的噪聲.

1.2.3邊界強化過采樣

類別邊界上的樣本點對分類器分類邊界的訓練具有很強的指導意義，在采樣過程中提高邊界點的采樣率，將有助于加大模型分類間隔，提高泛化性能.SMOTE算法無法識別邊界點，且穩(wěn)健過采樣方法易將邊界點視為低置信度樣本，產(chǎn)生模糊邊界的問題，對后續(xù)的訓練產(chǎn)生負面影響.為了解決上述問題，GMM-SMOTE利用后驗概率來識別邊界點并提高其采樣率.

設(shè)第i個簇內(nèi)有Nmini個少數(shù)類，由公式(2)計算出第j個樣本屬于第i個簇的概率.根據(jù)所得的后驗概率計算采樣權(quán)重

(3)

(4)

綜上，GMM-SMOTE算法的偽代碼如下.

輸入:有噪不平衡數(shù)據(jù)集D={x1,x2,…,xn},簇數(shù)k,不平衡閾值α,采樣后樣本類別比β,過采樣權(quán)重上下界max和min輸出:低噪平衡數(shù)據(jù)1.創(chuàng)建組件數(shù)為k的高斯混合模型p(x|θ)=∑ki=1ωig(x|μi,Σi),用數(shù)據(jù)集D進行訓練2.fori←1tokdo3.計算簇內(nèi)少數(shù)類樣本個數(shù)Nmini,多數(shù)類樣本個數(shù)Nmaji4.計算高斯混合模型簇內(nèi)的類別比IRi=NminiNmaji+1,(i=1,2,…,k)5.whileIRi≥αdo6.依公式(2)計算后驗概率,其中j=1,2,…,Nmini7.依公式(3)、(4)計算簇內(nèi)樣本的采樣權(quán)重8.計算簇內(nèi)過采樣合成需合成的樣本數(shù)量Ni=(Nmaj-Nmin)βNminiNmin9.根據(jù)采樣權(quán)重進行SMOTE過采樣10.end11.end12.return低噪平衡數(shù)據(jù)

1.3 缺陷檢測模型構(gòu)建

構(gòu)建基于機器學習的軟件缺陷檢測模型能夠降低缺陷的定位和分析成本，提高缺陷識別性能.在機器學習領(lǐng)域中，隨機森林(random forest，RF)、極端梯度提升(eXtreme gradient Boosting，XGBoost)是集成學習中的兩種代表性算法，在實際分類任務中具有高擴展性和適用性.多層感知機(multilayer perceptron，MLP)是神經(jīng)網(wǎng)絡(luò)模型中的典型算法，通過仿生物神經(jīng)網(wǎng)絡(luò)實現(xiàn)在復雜模式或環(huán)境下進行自動預測.為了更好的評估GMM-SMOTE在不平衡軟件缺陷數(shù)據(jù)集上的效果，確保結(jié)果不受特定分類器的使用約束而具有普適性，將GMM-SMOTE平衡優(yōu)化后的數(shù)據(jù)輸入到上述3類分類模型中進行訓練，構(gòu)建3種軟件缺陷檢測模型，以實現(xiàn)軟件缺陷識別.

2 實驗分析

2.1 采樣效果驗證實驗

為了驗證GMM-SMOTE在噪聲環(huán)境下的穩(wěn)健性以及邊界強化效果，在模擬數(shù)據(jù)集上將該算法和SMOTE進行比較.數(shù)據(jù)樣本由4簇服從高斯分布的樣本組和任意添加的少數(shù)類噪聲點組合而成，其具體分布為

μ1=[0 0]T,μ2=[6 6]T,

μ3=[11 6]T,μ4=[0 8]T,

其中少數(shù)類占比為20%，多數(shù)類占比80%.原始數(shù)據(jù)如圖2所示.

圖2 原始數(shù)據(jù)分布

將原始數(shù)據(jù)分別用SMOTE和GMM-SMOTE進行過采樣處理，采樣后樣本類別比設(shè)為1，其結(jié)果如圖 3所示，其中用黑色“x”表示生成的少數(shù)類樣本.從圖 3(a)可以看出，SMOTE方法會對少數(shù)類噪聲樣本進行插值合成新的噪聲數(shù)據(jù)，且隨機選擇采樣樣本使得生成的少數(shù)類整體上密度均勻.由圖 3(b)可知，GMM-SMOTE有效的避免了噪聲數(shù)據(jù)的產(chǎn)生，且該方法可提高邊界樣本的過采樣率，使邊界部分生成的少數(shù)類樣本較其他部分更為密集.綜上，GMM-SMOTE在噪聲環(huán)境下的穩(wěn)健性以及邊界強化效果得到驗證.

圖3 模擬數(shù)據(jù)集實驗結(jié)果

2.2 缺陷檢測對比實驗

2.2.1實驗目的

為了驗證GMM-SMOTE對軟件缺陷檢測模型判別能力的提升效果，在7個NASA MDP軟件缺陷數(shù)據(jù)集上將所提算法與SMOTE[9]、BorderlineSMOTE[11]和KMeansSMOTE[10]3種對比算法進行比較.

2.2.2實驗數(shù)據(jù)

實驗所選NASA MDP軟件缺陷數(shù)據(jù)集的具體信息如表1所示.數(shù)據(jù)集涵蓋了3種編程語言.每個樣本數(shù)據(jù)由模塊屬性以及類標簽組成.模塊屬性包括McCabe指標、Halstead指標、代碼行數(shù)和總操作數(shù)等.類標簽為是否有缺陷.

表1 NASA MDP軟件缺陷數(shù)據(jù)集

2.2.3評價方法

在分類問題中，常用準確率(accuracy)、精確率(precision)、召回率(recall)、F-measure、G-means和AUC來評估模型.其中F-measure和G-means綜合考慮了精確率和召回率，廣泛應用于不平衡分類問題.本文采用F-measure和G-means作為評估指標，結(jié)果越高，則算法表現(xiàn)越好.

分類的混淆矩陣如表 2所示.其中TP表示將屬于正類的樣本預測為正類，F(xiàn)N表示將正類預測為負類，F(xiàn)P表示將負類預測為正類，TN表示將負類預測為負類.

表2 混淆矩陣

F-measure和G-means計算方法為

(12)

(13)

其中

(14)

(15)

γ表示召回率和精確率的重要程度，實驗中γ=1.

2.2.4實驗過程

將GMM-SMOTE及對比算法在上述7個數(shù)據(jù)集進行10次交叉驗證并取其平均結(jié)果進行對比分析.實驗的具體步驟為：

(1)數(shù)據(jù)預處理.對數(shù)據(jù)集中的缺失值進行刪除或填補，將數(shù)據(jù)按7∶2∶1分為訓練集、驗證集與測試集；

(2)對訓練集進行過采樣.不平衡閾值α設(shè)置過低，則易將噪聲點忽略，若設(shè)置過高，部分正常樣本將無法被選中進行過采樣，根據(jù)數(shù)據(jù)集的類別比例，將α設(shè)為0.05.采樣后樣本類別比β設(shè)為1.根據(jù)BIC和AIC來確定高斯混合模型的最佳組件數(shù)k；

(3)構(gòu)建軟件缺陷檢測模型.隨機森林中決策樹個數(shù)設(shè)為100.XGBoost學習率為0.025，樹最大深度為4.多層感知機的隱藏層為2層，神經(jīng)元個數(shù)需根據(jù)驗證集表現(xiàn)進行調(diào)整；

(4)性能評估.在測試集上對模型進行測試，使用F-measure和G-means對模型性能進行評估.

2.2.5實驗結(jié)果

實驗結(jié)果如表3所示.

表3 NASA MDP數(shù)據(jù)集實驗結(jié)果

實驗結(jié)果表明：(1)使用GMM-SMOTE對軟件缺陷數(shù)據(jù)集進行過采樣后，相同模型在F-measure和G-means兩個評價指標上的整體表現(xiàn)優(yōu)于其他對比算法，且在使用隨機森林和XGBoost作為分類器時，該算法在全部數(shù)據(jù)集上有效地提升了分類算法的判別性能；(2)MLP相較有一定抗不平衡能力的集成學習方法提升更顯著，驗證了該算法對有噪不平衡數(shù)據(jù)的過采樣效果.

為了更好地比較算法的性能，對共21組實驗結(jié)果進行統(tǒng)計排名，所提算法及對比算法實驗結(jié)果排名前n位的比率如圖 4所示，可以看出，GMM-SMOTE在F-measure和G-means指標下Top-1和Top-2的比率均排名第1，性能優(yōu)于對比算法.

圖4 各過采樣算法結(jié)果統(tǒng)計排名

3 結(jié) 論

提出一種穩(wěn)健邊界強化GMM-SMOTE軟件缺陷檢測方法，該方法采用高斯混合模型對不平衡訓練數(shù)據(jù)進行聚類，根據(jù)簇內(nèi)類別比約束準確篩選可靠樣本點用于數(shù)據(jù)生成，同時利用后驗概率識別邊界點，提高其過采樣率，實現(xiàn)了穩(wěn)健邊界強化過采樣，并建立了軟件缺陷檢測模型.實驗首先在模擬數(shù)據(jù)集上驗證了GMM-SMOTE的穩(wěn)健性和邊界強化效果，然后將GMM-SMOTE同SMOTE、BorderlineSMOTE和KMeansSMOTE等過采樣算法在7個NASA MDP數(shù)據(jù)集中進行對比實驗以評估該算法對軟件缺陷檢測模型判別能力的提升效果，依據(jù)F-measure和G-means兩個指標進行評價，結(jié)果表明，GMM-SMOTE有效提升了軟件缺陷檢測模型的判別能力.

軟件缺陷檢測方法的研究具有重要的實際應用價值，所提方法通過引入高斯混合聚類，對軟件數(shù)據(jù)進行分布與歸屬估計，有效發(fā)現(xiàn)了高可靠性及邊界樣本，解決不平衡問題提高軟件缺陷識別能力.但隨著軟件缺陷數(shù)據(jù)維度增加，數(shù)據(jù)的不平衡處理難度增大，因此下一步的研究重點是擴展該方法以適用于高維軟件缺陷數(shù)據(jù).