基于聚類和混合采樣的軟件缺陷預(yù)測(cè)研究

張 彤，李英梅

（哈爾濱師范大學(xué)）

0 引言

軟件缺陷指的存在于計(jì)算機(jī)程序或者軟件的不能使得程序正常運(yùn)行的瑕疵.軟件缺陷問題不僅會(huì)浪費(fèi)大量的人力、物力和財(cái)力，有的情況還會(huì)危及到人類的生命安全［1］.因此軟件缺陷預(yù)測(cè)問題在軟件工程領(lǐng)域上越來越受到人們的關(guān)注.

隨著軟件缺陷預(yù)測(cè)技術(shù)的不斷提高，人們發(fā)現(xiàn)傳統(tǒng)的機(jī)器學(xué)習(xí)能夠取得良好的效果是由于正例和反例的數(shù)目相差無幾，但是在醫(yī)學(xué)診斷［2］、網(wǎng)絡(luò)診斷［3］、信息安全［4］等方面中表現(xiàn)得不好，這是由于類不平衡所導(dǎo)致的問題.類不平衡指的是訓(xùn)練樣本中正例和反例數(shù)目相差很大，這將導(dǎo)致的在機(jī)器學(xué)習(xí)中預(yù)測(cè)的結(jié)果更偏向于多數(shù)類.經(jīng)過大量實(shí)驗(yàn)證明，軟件缺陷當(dāng)中有缺陷的數(shù)據(jù)與無缺陷的數(shù)據(jù)的數(shù)目之比符合八二定律［5］，這就可能導(dǎo)致最終的結(jié)果趨向于無缺陷數(shù)據(jù)，但是將錯(cuò)誤的數(shù)據(jù)當(dāng)做正確數(shù)據(jù)所付出的代價(jià)要遠(yuǎn)遠(yuǎn)大于把正確數(shù)據(jù)當(dāng)做錯(cuò)誤數(shù)據(jù)的代價(jià).通過采樣的方法可以將正例和反例數(shù)量變?yōu)橄嗤?，這也就解決了類不平衡問題，極大地提高軟件缺陷預(yù)測(cè)的能力.該文針對(duì)類不平衡問題提出MSKsmote算法，經(jīng)過實(shí)驗(yàn)得出該方法相較經(jīng)典的采樣方法有著更好的效果.

1 相關(guān)研究工作

根據(jù)多數(shù)類和少數(shù)類兩個(gè)不同的角度研究，專家們發(fā)現(xiàn)了三種采樣方法即過采樣、欠采樣和混合采樣方法.過采樣的方法主要思想是增加少數(shù)類數(shù)量直到與多數(shù)類數(shù)量相同；欠采樣方法的主要思想是減少多數(shù)類數(shù)據(jù)的數(shù)量直到與少數(shù)類數(shù)量相同；混合采樣方法則同時(shí)運(yùn)用以上兩種方法以解決類不平衡問題.

對(duì)于欠采樣方法，周傳華提出一種聚類欠采樣的集成算法，該方法通過得出樣本簇的中心位置，篩選出信息特征強(qiáng)的多數(shù)類樣本，再將該訓(xùn)練集放入引入代價(jià)敏感的集成算法［6］.陸鵬程提出一種聚類欠采樣的方法，將多數(shù)類進(jìn)行聚類之后有放回選出N個(gè)多數(shù)類子集與N個(gè)少數(shù)類子集組成N個(gè)新的訓(xùn)練集，再將N 個(gè)訓(xùn)練集訓(xùn)練成N個(gè)分類器［7］.張肖提出一種半監(jiān)督集成學(xué)習(xí)算法Tri＿Adaboost，在Tri＿training 算法進(jìn)行預(yù)測(cè)的時(shí)候引入欠采樣方法解決類不平衡問題［8］.

對(duì)于過采樣方法，V García 等學(xué)者提出隨機(jī)采樣方法（ROS），該算法直接對(duì)少數(shù)類數(shù)據(jù)進(jìn)行復(fù)制，以增加少數(shù)類數(shù)據(jù)數(shù)量，但是該方法容易造成嚴(yán)重的過擬合［9］.NV Chawlat 提出smote 過采樣方法，該算法的主要思想是多次在兩個(gè)少數(shù)類數(shù)據(jù)中加少數(shù)類數(shù)量以達(dá)到平衡［10］.Hui提出borderline－smote 算法，該算法將少數(shù)類分為三種情況，只對(duì)危險(xiǎn)點(diǎn)進(jìn)行過采樣從而使少數(shù)類樣本邊界更為清晰［11］.楊智明提出一種改進(jìn)的過采樣方法，根據(jù)數(shù)據(jù)的特性自適應(yīng)采用近鄰選擇策略，最終在不影響復(fù)雜度的情況下有效提高分類器的準(zhǔn)確性［12］. He 等學(xué)者提出ADASYN 算法，該算法的思想是根據(jù)密度分作為標(biāo)準(zhǔn)來自動(dòng)添加少數(shù)類樣本的數(shù)量，該算法生成的少數(shù)類樣本有效的緩解了數(shù)據(jù)重疊現(xiàn)象［13］.陳俊豐提出WKMeans－SMOTE方法，通過引進(jìn)”聚類一致性系數(shù)”篩選出邊界上的少數(shù)樣本，對(duì)少數(shù)樣本進(jìn)行smote過采樣以擴(kuò)充少數(shù)類樣本數(shù)量［14］.周建含等人將過采樣方法用到半監(jiān)督中，取得了較好的預(yù)測(cè)效果［15］.

對(duì)于混合采樣方法，王海等學(xué)者在類不平衡方面提出一種混合采樣方法，首先采用smote 過采樣方法增加缺陷類數(shù)量，對(duì)無缺陷類樣本采用K－modes聚類算法，聚類的簇?cái)?shù)等于過采樣后的缺陷樣本數(shù)量［16］.吳藝凡等學(xué)者利用SVM 算法得到分類超平面，刪除遠(yuǎn)的多數(shù)類樣本，對(duì)邊界類樣本進(jìn)行過采樣方法［17］.戴翔提出一種將混合采樣與集成學(xué)習(xí)相結(jié)合的方法，先用smote過采樣提高缺陷類樣本的數(shù)量，用K－means 聚類算法進(jìn)行欠采樣，最后運(yùn)用集成學(xué)習(xí)機(jī)制，通過投票機(jī)制進(jìn)行模型預(yù)測(cè)［18］.

雖然三種方法都可以緩解類不平衡所帶來的問題，但是過采樣容易出現(xiàn)過擬合問題，欠采樣由于刪減多數(shù)類數(shù)據(jù)可能導(dǎo)致重要的信息丟失.因此該文提出了一種結(jié)合聚類算法的混合采樣算法.

2 算法介紹

該文針對(duì)類不平衡的問題提出MSKsmote算法，其中可以主要分為兩個(gè)部分，第一部分是樣本預(yù)處理階段，類似于borderline－smote 算法，判斷出危險(xiǎn)點(diǎn)，安全點(diǎn)和噪聲點(diǎn)，將噪聲點(diǎn)去除.第二部分是聚類和混合采樣階段，主要是運(yùn)用K－means聚類算法，將數(shù)據(jù)集分為多個(gè)簇，然后根據(jù)簇中多數(shù)類數(shù)據(jù)和少數(shù)類數(shù)據(jù)的數(shù)量分為多數(shù)類數(shù)據(jù)簇和少數(shù)類數(shù)據(jù)簇，去除危險(xiǎn)點(diǎn)中是少數(shù)類數(shù)據(jù)簇的多數(shù)類數(shù)據(jù)以及對(duì)危險(xiǎn)點(diǎn)的少數(shù)類數(shù)據(jù)進(jìn)行smote 過采樣.該算法能夠使得邊界更為明確，從而有效解決類不平衡的問題.其流程如圖1 所示.

圖1 MSKsmote算法流程

2.1 樣本預(yù)處理階段

該階段是在borderline－smote 算法的基礎(chǔ)上進(jìn)行創(chuàng)新，而borderline－smote 算法的主要思想主要是基于smote 算法，因此在介紹該階段需要介紹smote 過采樣算法思想. Smote 算法基于隨機(jī)過采樣算法的一種創(chuàng)新，其基本思想是對(duì)少數(shù)類樣本進(jìn)行分析并根據(jù)少數(shù)類樣本人工合成新樣本添加到數(shù)據(jù)集中（如圖2 所示）.

圖2 Smote過采樣算法思想

該算法的算法流程如下：

輸入：T為少數(shù)樣本數(shù)據(jù)數(shù)量

N為過采樣數(shù)量

K為最近鄰的數(shù)量

輸出：新的少數(shù)類數(shù)據(jù)

（1）對(duì)于缺陷類每一個(gè)數(shù)據(jù)x，用歐式距離計(jì)算出它到其它所有有缺類數(shù)據(jù)的距離.

（2）設(shè)計(jì)一個(gè)采樣倍率N（根據(jù)有缺陷類和無缺陷類的比例確定），在每一個(gè)有缺陷類樣本x，用k近鄰算法隨機(jī)選取若干個(gè)數(shù)據(jù).

（3）對(duì)于每一個(gè)隨機(jī)選出的近鄰xn，按照公式（1）分別構(gòu)建新的有缺陷數(shù)據(jù).

雖然smote能夠合成少數(shù)類數(shù)據(jù)樣本數(shù)量，在一定程度上比隨機(jī)過采樣方法降低了過擬合性，但是容易模糊多數(shù)類數(shù)據(jù)和少數(shù)類數(shù)據(jù)的邊緣，使得分類器不能較好的區(qū)分邊界點(diǎn)的多數(shù)類數(shù)據(jù)和少數(shù)類數(shù)據(jù).

borderline－smote 算法為了使邊界更為清晰，將少數(shù)類數(shù)據(jù)分為三類：安全點(diǎn)，危險(xiǎn)點(diǎn)，噪音點(diǎn).安全點(diǎn)指周圍不同類型的數(shù)據(jù)數(shù)量要遠(yuǎn)遠(yuǎn)小于同類型的數(shù)據(jù)數(shù)量，噪音點(diǎn)指周圍不同類型的數(shù)據(jù)數(shù)量要遠(yuǎn)遠(yuǎn)大于同類型的數(shù)據(jù)數(shù)量，危險(xiǎn)點(diǎn)指周圍既有多數(shù)類數(shù)據(jù)又有少數(shù)類數(shù)據(jù)，但是多數(shù)類數(shù)據(jù)數(shù)量要大于少數(shù)類數(shù)據(jù)的數(shù)量且僅對(duì)危險(xiǎn)點(diǎn)進(jìn)行過smote過采樣方法.如圖3 所示.

圖3 borderline－smote算法

雖然borderline－smote 算法能夠使邊界更為清晰，但是該算法對(duì)于噪音未進(jìn)行處理，因此該文在采樣階段，為降低噪音帶來的干擾，將存在于少數(shù)類中的多數(shù)類噪音數(shù)據(jù)進(jìn)行刪除.其次，borderline－smote 只對(duì)少數(shù)類數(shù)據(jù)進(jìn)行過采樣，這樣容易造成過擬合，于是為了緩解欠擬合問題，該文結(jié)合聚類欠采樣方法，刪除部分為危險(xiǎn)點(diǎn)的多數(shù)類數(shù)據(jù)，再對(duì)危險(xiǎn)點(diǎn)的少數(shù)類數(shù)據(jù)進(jìn)行擴(kuò)充.

2.2 K－means聚類算法

聚類算法是一種探索性數(shù)據(jù)分析技術(shù)，其基本的原理是將相似的數(shù)據(jù)歸納為一組，不相似的數(shù)據(jù)則為不同組.K－means算法思想是尋找k個(gè)質(zhì)心，經(jīng)過多次迭代之后，形成k個(gè)簇，最終形成的k 個(gè)簇之間距離最大，簇間的數(shù)據(jù)距離最小.該算法的算法流程如下：

輸入數(shù)據(jù)樣本集合D：｛x1，x2，x3…xn｝

輸入聚類的簇?cái)?shù)：k 輸入最大迭代次數(shù)：T

（1）在初始的樣本集合D中，隨機(jī)選取k個(gè)點(diǎn)作為初始質(zhì)心｛u1，u2，u3…uk｝.

（2）重復(fù)下面過程直到達(dá)到最大迭代次數(shù)或者質(zhì)心不再發(fā)生變化為止.

（3）｛對(duì)于每一個(gè)數(shù)據(jù)樣本，利用公式（2）計(jì)算該點(diǎn)屬于何類.

其中ci表示樣本數(shù)據(jù)i與k個(gè)簇中距離最近的那個(gè)類.uj表示質(zhì)心j.經(jīng)過對(duì)初始數(shù)據(jù)的聚類之后，對(duì)簇的類型進(jìn)行判斷，當(dāng)一個(gè)簇中少數(shù)類數(shù)據(jù)多于多數(shù)類數(shù)據(jù)的時(shí)候稱為少數(shù)類數(shù)據(jù)簇，反之稱之為多數(shù)類數(shù)據(jù)簇.這一步的主要作用是可以找出簇中的異點(diǎn)（例如多數(shù)類簇中的少數(shù)數(shù)據(jù)），因?yàn)樵擖c(diǎn)由于與其它點(diǎn)結(jié)構(gòu)相似，但是與多數(shù)周圍其他點(diǎn)不同，這就會(huì)影響模型的最終預(yù)測(cè)效果.通過聚類算法，可以找出危險(xiǎn)點(diǎn)中的異點(diǎn)，隨后刪除該點(diǎn)并最終對(duì)少數(shù)類點(diǎn)進(jìn)行smote過采樣方法擴(kuò)充少數(shù)類.

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

該文實(shí)驗(yàn)將在AEEEM 數(shù)據(jù)集，在python的sklearn 工具包的基礎(chǔ)上，以貝葉斯分類器作為基分類器，采用十折交叉法，進(jìn)行100 次的實(shí)驗(yàn)，取平均值作為本次實(shí)驗(yàn)的最終結(jié)果.該文將選取經(jīng)典的類不平衡算法作為對(duì)照實(shí)驗(yàn)組.

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

在實(shí)驗(yàn)數(shù)據(jù)方面，該文主要采用的是AEEEM數(shù)據(jù)集，AEEEM 數(shù)據(jù)集是開源的數(shù)據(jù)集，是由D’Ambros［19］等人共同收集整理獲得，在軟件缺陷預(yù)測(cè)中具有可靠性.其表的信息見表1.

表1 AEEEM數(shù)據(jù)信息

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

該文重點(diǎn)研究軟件是否有缺陷，所以該實(shí)驗(yàn)被認(rèn)為是一個(gè)二分類問題，一種是有缺陷標(biāo)記模塊（少數(shù)類），一種是無缺陷模塊（多數(shù)類）.為了能更好的驗(yàn)證該方法是否比其它經(jīng)典的類不平衡算法更好，將介紹以下公式.

（1）準(zhǔn)確率：又被叫做查準(zhǔn)率，真正含有缺陷的模塊在所有被預(yù)測(cè)模型標(biāo)記為有缺陷模塊所占的比例，其定義如式（4）.

（2）召回率：又被叫做查全率，被預(yù)測(cè)模型正確標(biāo)記的但是有缺陷模塊在所有真正含有缺陷的模塊所占的比例，其定義如式（5）.

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

該文將多個(gè)經(jīng)典的類不平衡算法與MSKsmote算法進(jìn)行比較，在AEEM 數(shù)據(jù)集上的各個(gè)方法實(shí)驗(yàn)結(jié)果見表2.其中經(jīng)典的類不平衡算法包括隨機(jī)過采樣方法（ROS），隨機(jī)欠采樣方法（RUS），Smote過采樣方法和ADASYN.

表2 不同類不平衡方法的比較

由表2 可知，在經(jīng)典的類不平衡算法中，ADASYN算法效果最好.但是MSKsmote 算法在絕大多數(shù)的情況中表現(xiàn)最好，并且F1均值最高，因此該文提出的MSKsmote算法較經(jīng)典的類不平衡算法更為好，這也說明將危險(xiǎn)點(diǎn)中的異點(diǎn)清除會(huì)提高模型的預(yù)測(cè)效果.

4 結(jié)論

為了解決類不平衡問題，該文為避免過采樣的過擬合以及欠采樣的欠擬合問題，提出一種混合采樣方法，該方法為了使邊界更為清晰，將危險(xiǎn)點(diǎn)的部分多數(shù)類數(shù)據(jù)刪除，然后再對(duì)危險(xiǎn)點(diǎn)中的少數(shù)類數(shù)據(jù)進(jìn)行過采樣，從而達(dá)到數(shù)據(jù)的平衡. 通過在AEEEM 數(shù)據(jù)集的實(shí)驗(yàn)，證明出MSKsmote算法所表現(xiàn)的效果更為優(yōu)異.

該文只是考慮了軟件缺陷預(yù)測(cè)中類不平衡方面，下一步將研究能與MSKsmote 算法相匹配的特征選擇方法，進(jìn)一步提高模型的預(yù)測(cè)效果.