面向軟件缺陷預測的過采樣方法①

紀興哲,邵培南

(中國電子科技集團第三十二研究所,上海 201808)

隨著軟件技術的發展,軟件項目中的缺陷越來越受開發人員的重視,占據大量開發和維護時間,降低開發人員的工作效率,而且給企業帶來許多財物損失.目前,軟件缺陷預測(SDP)[1,2]已經成為了一個快速發展的研究領域,許多研究[3,4]大都通過機器學習方法來挖掘版本控制系統數據集,運用歷史數據訓練預測模型來預測軟件項目的缺陷.在整個數據集達到平衡的前提下,機器學習中許多算法可以解決這類問題;然而,現在的絕大多數軟件項目數據集都極為不平衡,有缺陷的樣本都遠遠少于無缺陷的樣本(前者通常被稱為少數類,后者稱為多數類),這在SDP中稱為類不平衡問題,類不平衡問題存在于眾多現實領域中,例如生物醫學診斷[5]、多媒體數據分類[6]、垃圾郵件識別[7]、信用卡及電信詐騙檢測[8]等,這類問題都具有鮮明的類不平衡問題.

許多優秀的用于構建分類預測模型的方法[9]已經被提出,包括常用的決策樹(DT),k 最近鄰(KNN) 樸素的貝葉斯,邏輯回歸,多層感知(MLP),支持向量機(SVM),極限學習機(ELM)和深度神經網絡(DNN)等,在對SDP 問題進行建模預測時,它們的整體分類準確率通常都不錯.但是當面對類不平衡數據集時,尤其是例如癌癥患者預測[5]這類高失衡率的問題中,即只有極少數樣本需要正確的預測時,這些分類算法只能對大多數不患病的樣本進行分類,而忽略了少數患病樣本,這從算法應用的本質上與出發點是相違背的.

解決類不平衡問題的廣泛被采用的方法是二次采樣法,代價敏感法和集合學習法[10],集合學習方法是一種通過疊加多個弱監督分類器以獲得更好的強監督分類器的學習方法,常用的組裝學習方法是裝袋,提升和堆疊.代價敏感法是給每一類實例分配不同的權重,以使在分類時少數類比多數類更有被分類的價值.二次采樣法包括欠采樣和過采樣.欠采樣是通過丟棄部分數據集中的多數類來平衡數據集,例如RUS,CNN,TL,OSS,以及SBC[3]等,缺點是丟棄的部分實例可能包含潛在的有用信息;過采樣是合成新實例添加到少數類中,例如ROS,SMOTE,以及SMOTE 算法的拓展等.一般情況下,過采樣方法是優于欠采樣方法的,因為過采樣避免了信息的丟失,但也有數據復制導致擬合度過高和多樣性不足的困擾.

針對以上缺點,本文提出一種基于異類距離排名的過采樣方法(HDR),通過衡量少數類實例與最近多數類之間距離的排名關系,選出與邊界聯系最強的實例組合生成新實例,緩解數據分布的不均衡性并且提升數據的多樣性,在此數據集基礎上繼而提高軟件缺陷預測的準確性.同時與SMOTE 算法[11]和Borderline-SMOTE 算法[12]等作比較,通過對三者算法的研究和對相同數據集進行實驗,挖掘出新方法的優越性.本文結構如下:在第1 節討論了軟件缺陷預測的技術現狀,在第2 節中討論了不同的采樣方法;在第3 節中詳細介紹了本文提出的HDR 算法;在第4 節中介紹了實驗對象和評估方法以及實驗結果;在第5 節中對本文進行了總結并展望了未來的工作.

1 軟件缺陷預測

為了減少軟件故障并提高軟件質量,開發人員往往會采用許多軟件質量保證活動(例如缺陷預測,代碼審查和單元測試等).根據文獻了解到軟件故障在軟件項目中通常遵從八二定律[13],即80%的缺陷存在于20%的模塊中,而軟件質量保證活動需要對整個軟件項目進行覆蓋,往往會在無缺陷的大量模塊上花費若干時間.為了最大程度的降低成本,軟件開發人員需要知道哪些模塊包含更多缺陷,并首先檢查此模塊.由此,研究人員提出了軟件缺陷預測技術.

軟件缺陷預測技術的過程包含3 個主要步驟:收集歷史缺陷數據集;使用歷史數據通過機器學習或深度學習技術來訓練分類或回歸模型;將訓練后的模型應用與預測軟件缺陷的數量或可能性.隨著PROMISE知識庫[10],NASA 缺陷樣本集[14]和AEEEM 等數據集相繼被公開,軟件缺陷預測技術得到了快速的發展,并出現了多種不同的分類方法.從不同的數據集粒度來看,軟件缺陷預測技術可分為四類:包級別,文件級別,方法級別,代碼行級別.從不同指標來看,分為兩類:靜態和動態.靜態缺陷預測采用靜態軟件指標來預測缺陷數量或缺陷分布,指標包括McCabe 度量和Halstead度量.動態缺陷預測采用缺陷生成來預測系統缺陷隨時間的分布狀況.采用機器學習方法研究軟件缺陷預測分為3 種不同的方向,分別是項目間缺陷預測(WSDP),跨項目缺陷預測(CSDP),以及非均勻缺陷預測(HDP)[15],比起相較而言已經成熟的WSDP,當前研究人員更關注CSDP的發展進程.目前研究人員已經提出了許多缺陷預測方法,但是大多數缺陷預測研究對軟件模塊的缺陷傾向性描述較多,而忽視了模塊本身的缺陷數及缺陷分布,并且機器學習的方法都采用默認參數,沒有探究修改參數帶來的影響.

2 軟件缺陷預測的二次采樣方法

關于SDP中的類不平衡問題已有一些研究,相關文獻多是采用是二次采樣方法[16].二次采樣方法分為欠采樣和過采樣兩種.

欠采樣是通過刪除數據集中的部分多數類,縮小多數類的規模達到類平衡,.目前經常作為過采樣方法的補充技術.

過采樣技術是通過復制現有少數類或生成新的合成少數類來平衡數據集的一種采樣方法,隨機過采樣(ROS)[16]是在少數類中隨機復制部分插入數據集中,雖然這種方法能夠簡單有效的解決類不平衡問題,但由于重復采樣,數據缺乏多樣性,常常導致嚴重的過擬合.Chawla 等人在2002年提出了SMOTE 算法[11],作為迄今為止該研究領域內影響最大的過采樣方法,它基于最近鄰思想,提出根據兩個少數類樣本在方向上人工生成新的少數類的解決方法,實驗證明在處理類不平衡時能有效緩解數據的不平衡分布.Han 等認為SMOTE 算法忽視了多數類的分布,有導致類間重疊的風險,提出了Borderline-SMOTE 算法[12],認為算法應著眼于多數類與少數類的決策邊界上.后人的研究多是依據SMOTE 算法的優越性和特殊性對其進行拓展,例如:Bunkhumpornpat 等提出了Safe-Level-SMOTE算法[17],用安全等級系數來保證K 鄰居中其他少數類實例數量;Feng 等人提出了基于復雜度的過采樣技術(COSTE)[3],顯著提高了生成實例的質量;He 等人基于密度分布提出了改進算法ADASYN (自適應合成采樣)[18];Ding 等人在He 工作的基礎上結合EasyEnsemble集成方法提出了KA-Ensemble[9],動態改善多數類和少數類的平衡分布,并且在解決多分類問題中依然有效;Romero 等人提出了KINOS 算法[19],先刪除部分少數類,對余下數據過采樣,最后將刪除部分恢復,既通過生成新實例拓展了少數類,又保留了少數類的高價值數據;Tarawneh 等人基于最遠鄰提出了SMOTEFUNA 算法[20];Paria 等人提出了RCSMOTE[4],該方法能夠改進SMOTE算法的泛化問題,避免對無意義的少數類進行過采樣,同時解決決策邊界的重疊問題.

3 基于異類距離排名的過采樣方法

本文參考SMOTE 算法和Borderlin-SMOTE 算法生成新合成實例的方法提出一種新的基于異類距離排名的過采樣方法(HDR).由于多數類和少數類的邊界數據分布情況對分類問題的解決至關重要.HDR 將過采樣的重點著眼于邊界實例[12]上,在結合了噪聲過濾,基于排名和高值數據保留等思想和方法后,提出了以下方法步驟.首先,對樣本數據集采用實例分類方法進行區分,剔除噪聲數據,然后計算邊界實例與最近的多數類的距離,之后HDR 基于距離以升序排列所有邊界實例,并且將排名相鄰的邊界實例成對生成新合成實例.對距離排名的目的是,較高排名的邊界實例更貼合邊界,在數據分類時更具有區分度,將排名相鄰的邊界少數實例兩兩組合進而生成新實例,實則是通過組合區分度高、代表性強的實例來創造更具多樣性,更有利于均衡類分布的新實例.在之后,刪除新生成的噪聲合成實例并且恢復最開始刪除的少數類噪聲數據以避免丟失有價值的信息.以下是SMOTE 算法,Borderline-SMOTE 以及HDR 算法的詳細描述.

3.1 SMOTE 算法

SMOTE 算法是在隨機過采樣(ROS)基礎上改進的一種合成少數類過采樣方法,不同于ROS 采取簡單復制的方法進行過采樣,SMOTE的基本思想是依據少數類實例樣本人工生成新的合成實例.SMOTE 如圖1,具體內容由文獻[11]詳細介紹,算法流程如下.

圖1 SMOTE 算法基本思想

1)在少數類中,為每一個少數類實例x使用KNN算法依據歐氏距離確定K個最近鄰居;

2)根據數據集的不平衡率設置一個過采樣比例M,根據M確定采樣倍率N,對每一個實例x,從x的K近鄰中隨機選擇T個實例(x1,x2,···,xT),T的大小由N決定.對于選擇的每一個實例xT,執行以下公式生成少數類新實例xnew;

3)將新生成的實例xnew添加到原始數據集中,使訓練數據集的不平衡度達到要求.

SMOTE 算法的缺陷有以下幾個方面:首先對所有的少數類一視同仁,會導致多數類與少數類的邊界會隨著新添加的生成實例的增多而越加模糊,其次對于噪聲數據的過采樣會增加數據集的不平衡性,最后對于控制SMOTE 算法的兩個重要參數K和N需要反復調整.

3.2 Borderline-SMOTE 算法

Borderline-SMOTE 算法是針對SMOTE 算法的缺陷提出的一種改良算法.SMOTE 對所有的少數類實例都是同等對待.然而有些實例遠離邊界,對分類并沒有幫助,這部分實例在過采樣時應該被丟棄,同時需要強化邊界生成更多的邊界實例,來提升數據分布不均衡中的少數類分布比例,Borderline-SMOTE 算法基于此思想被提出.算法的基本思想是將少數類實例分為3 類,分別為safe,danger,noise,如圖2,僅對分類為danger的少數類實例進行過采樣.通過類似Borderline-SMOTE算法的縮小樣本采樣策略,許多研究者相繼提出了諸如SMOTEBoost,AND-SMOTE[21]和ADASYN 等算法,本文提出的HDR 也基于此思想.

圖2 Borderline-SMOTE 算法技術要點

3.3 HDR 算法

HDR 算法可分為3 個步驟:樣本預處理,過采樣和樣本后處理.

1)樣本預處理

樣本數據預處理,首先將樣本數據根據標簽分為多數類和少數類,算法的目的是對少數類的過采樣進行優化,基本思想是在不引入嘈雜數據的情況下擴充少數類實例數量.正如在第3.2 節中提到的SMOTE 算法的缺陷之一就是對噪聲實例的過采樣加劇了數據集的不平衡,而安全實例的過采樣產生的新實例對分類器的學習過程也不會有大的影響.考慮到上述事實,首先需要將少數類實例進行分類,包括邊界實例,安全實例,噪聲實例,考慮邊界實例(這在步驟2中運用)并且去除噪聲實例.少數類實例的分類方法[4]類似Borderline-SMOTE 如算法1 所示.

算法1.少數類分類方法輸入:數據集,包含少數類實例和多數類實例,datadD,d∈(d1,d2,d3,···,dnnum)nnumd為的數量.輸出:邊界實例B,安全實例S,噪聲實例N.

方法:1.針對中的每一個,計算 在數據集中的近鄰,獲得 近鄰中的多數類實例數量.m′=mdimdi di∈Nm d dididatamm m′2.如果,即 所有的近鄰都是多數類實例,可被判定為噪聲實例,;如果,即的近鄰中有超過一半的實例是多數類實例,可被判定為邊界實例,;如果,即的近鄰中有少于一半的多數類實例,可被判定為噪聲實例,.2

依據算法1 區分了3 種不同類型的實例,在去除了噪聲實例N后,在步驟2)中不會再有噪聲實例生成新實例干擾數據集的平衡性以及分類器的性能.根據已有研究[12]表明,調整m的取值,當邊界實例B的數量達到少數類實例數量的一半,此時m為最佳值.

2)過采樣

在預處理步驟之后,過采樣步驟確定如何生成新合成少數實例以及生成的數量.這一步驟的目的是平衡類之間的分布,提高數據集的多樣性,擴充邊界實例,這將有利于分類器更好的發揮作用.通過計算邊界實例的多數類最近鄰的歐式距離,然后將計算結果升序排名,將距離相似的兩個數類成對組合在一起,之后參考SMOTE 算法,在二者之間的連線上隨機選擇一點作為新生成的少數類實例.計算的每一個結果,都是在尋找對分類更有效的邊界實例,越接近多數類的少數類,具有的分類代表意義越深,通過組合排名相似的實例,可以提升生成數據的多樣性,緩解類不平衡問題.HDR-過采樣算法如算法2 所示.

算法2.HDR-過采樣算法輸入:邊界實例B,多數類實例D,少數類實例,d B∈(b1,b2,b3,···,bi)D∈(D1,D2,D3,···,Di)輸出:平衡數據集newdata方法:1.定義:與其多數類最近鄰的歐氏距離random(a,b)ab xibi 2.定義:和之間任取一點作為結果M∈(m1,m2,m3···mi)3.定義M:異類距離集合,C 4.定義:生成新實例集合,,根據文獻[22]實驗表明,當生成新實例后少數類總量達到總體數量的40%,L 則為最佳值i=1,2,3···L C∈(c1,c2,c3,···,ci) L=length(C)5.forthen:dism=dist(bi,Di) Dibi,為屬于多數類的的最近鄰xi=dism,存入M 集合6.對M 進行升序排序,得到,最小j=1;j=j+2;j≤length(M)m1,m2,m3,···,mim1 7.forthen:repeat:random(mi,mi+1)→cilength(ci)=L/length(B),newdata=C+D+d,

3)樣本后處理

雖然新實例是通過一組異類距離相似度高的實例生成而來,這意味著大多數情況它都存在于少數類群體內部,如圖3,虛線為邊界線,藍色圓形對勾代表的是根據黑實線兩側異類距離相似的實例隨機生成,新合成實例是安全的,但不排除有黑色圓形對勾的情況,呈凹形的邊界線分布兩側分布著異類距離相似的實例,通過HDR 算法生成的新實例存在于多數類內部,這將形成噪聲,影響分類.因此采用KNN 算法來去除新生成的噪聲實例.KNN 算法的核心思想是通過判斷當前樣本的鄰居所屬類別來推斷樣本所屬的類別.首先,應用歐幾里得距離來計算每個實例的K 近鄰,在其K 鄰域內,如果少數類的數量小于多數類的數量,就意味著當前實例是噪聲實例,并且應該被刪除.

圖3 HDR-過采樣算法生成新合成實例

由于有缺陷實例部分通常較少,每一個實例都對應了真實數據,刪除任意一個都是對數據樣本的污染,因此采取與諸多文獻不同的后處理方式 在預處理步驟中去除的少數類噪聲樣本需要被添加回過采樣后的數據集.同時為了研究恢復實例對整個算法的影響,將未進行恢復操作的HDR 算法命名為HDR-half 算法,并通過實驗進行研究.

4 實驗分析

4.1 實驗數據集

為了驗證HDR 算法的有效性,實驗選用了NASA MDP 數據集,MDP 數據集包含了13 個NASA 實際項目,在SDP 研究文獻內被多次運用.表1選取了MDP 8 個具有代表性的數據集的詳細信息,包括項目名,度量屬性數,總實例數量和有缺陷實例所占比例.其中度量屬性包含了McCabe 度量,Halstead 度量,代碼行數,操作數復雜度等,圖中可以觀察到,有缺陷實例所占比例都遠低于50%,這表明MDP 數據集可以用做評估解決類不平衡方法的實驗對象.

表1 NASA的MDP 部分數據集

4.2 實驗評價指標

在SDP中,通常基于混淆矩陣計算性能評價指標,如表2所示.其中真陽性(TP)表示正確預測為缺陷實例的數量,假陽性(FP)表示錯誤預測為缺陷實例的數量,真陰性(TN)表示正確預測為無缺陷實例的數量,假陰性(FN)表示錯誤預測為無缺陷實例的數量.

表2 混淆矩陣

為了有效評估HDR 算法的性能,實驗選用了平衡率(balance),F測量(F1-measure,F1)和G 均值(G-Mean,GM)3 項性能指標,balance是召回率和準確率之間的平衡,balance值越大,證明實驗方法性能越好.F1-measure體現模型的穩定性,當F1-measure 較高時表明實驗方法有更好的性能.G 均值也可以用來評價不平衡數據的模型表現.根據混淆矩陣,banlance,F1,GM定義如下:

4.3 實驗設計

為驗證HDR 方法的有效性,實驗分別與SMOTE、Borderlin-SMOTE 實驗作比較;為研究算法中步驟3)處理方法的影響,實驗將HDR-half 算法與HDR 算法進行比較.實驗中所涉及的近鄰參數均按照文獻設置為5,分類器采用隨機森林(RF),RF 作為決策樹(DT)的集成方式,目前已被廣泛地應用在分類問題中,它的特點是在處理數據量較大或度量屬性較多的項目時訓練速度快,訓練成本低.實驗采用5 折交叉驗證,將數據集的80%作為訓練集,20%作為測試集,訓練過程重復20 次,性能結果取20 次5 折交叉驗證平均值.

4.4 實驗結果分析

表3,表4和表5分別列出了采用4 種方法關于MDP 數據集的balance,F1-measure和G-Mean 三項指標.從表中可以看到,HDR-half 算法相比于HDR 算法在balance指標上有相似的表現,而在F1-measure和G-Mean 指標上則得到了相比HDR 算法較差的結果,由此,本文采用的在過采樣之后恢復其原始部分少數類數據的獨特方法,減少了寶貴數據的浪費,豐富了數據集和數據分布,并且對實驗結果有巨大的提升.

從表3中可以看到,在HDR 算法采用RF 分類器得到的balance值相對于SMOTE和Borderline-SMOTE取得了全面的優勢,尤其在JM1 數據集上相比于SMOTE具有23.3%的巨大提升,最低提升發生在KC3 數據集上,提升了3.5%,平均有8.76的提升.這些提升都源自新算法在數據集上進行了預處理+后處理的操作;同樣,從表4和表5來看,本文提出的新算法結果明顯較好,相較于SMOTE 算法在F1-measure 上和G-Mean上分別有8.76%和16.89%的性能提升,和Borderline-SMOTE 相比也分別有6.64%和4.24%的性能提升.其中表4Borderline-SMOTE 在KC3 數據集和MC2 數據集上結果較好.經過多次實驗分析,原因是兩者的數據量太小導致新算法對數據集的優化不如Borderline-SMOTE 明顯.總體而言,相較于同類型算法Borderline-SMOTE,HDR 采用異類距離排名的方法穩定性更強,對不平衡數據集預測性能的提升更明顯.

表3 3 種方法在數據集上的balance 值

表4 3 種方法在數據集上的F1-measure 值

表5 3 種方法在數據集上的G-Mean 值

綜上所述,本文在SMOTE 算法和Borderline-SMOTE算法的影響下提出的HDR 算法,在解決SDP的類不平衡問題時,有效緩解了數據分布的不平衡性,并且其生成的多樣性新合成實例也大大提升了分類器的性能,提高了模型預測的準確率.

5 結論與展望

由于已有的過采樣技術往往導致不同程度的過擬合,并且算法的處理過程通常覆蓋絕大多數實例,提高了模型預測的成本.針對以上缺點,本文提出一種基于異類距離排名的過采樣方法(HDR),HDR 利用邊界實例與最近多數類的歐氏距離,幫助生成更加多樣性的新合成實例,同時噪聲過濾步驟大大降低了新實例導致的過擬合的可能性.本文通過在NASA的MDP 實際項目數據集上采用RF 分類器與兩種過采樣算法進行比較來評估HDR的性能,在用來評估的3 個指標(balance,F1-measure,G-Mean)上可以看到經過HDR算法處理過的不平衡數據集在軟件預測模型的性能上體現了較大的優勢,然而同時也看到了HDR 面對小樣本數據集的性能缺陷.因此,如何調整HDR 算法使之能較好的解決各種不同大小的數據集以及采取更多的分類器驗證其性能將是接下來的研究重點.