張 麗，沈雅婷，朱園園

(南京理工大學紫金學院 計算機學院，江蘇 南京 210023)

0 引 言

軟件缺陷預(yù)測數(shù)據(jù)中存在的類不平衡問題嚴重影響了分類器的性能[1-3]。為了解決不平衡問題，已有研究方法大致分為兩類：基于數(shù)據(jù)層面和基于算法層面[3，4]?；跀?shù)據(jù)層面主要采用過抽樣或者欠抽樣技術(shù)，即人工合成少數(shù)類樣本或者刪除部分多數(shù)類樣本，以實現(xiàn)樣本數(shù)據(jù)的平衡。例如，典型過抽樣算法SMOTE[4](synthetic minority oversampling technique)、欠抽樣算法RUS[4](random under sampling)?；谒惴▽用嫱ㄟ^改進分類器的算法設(shè)計，使其更適合于不平衡數(shù)據(jù)，主要包括代價敏感方法，如AdaCost[5]；集成學習方法，如AdaBoost[5]等。SMOTE過抽樣算法隨機選取少數(shù)類樣本的近鄰樣本合成新樣本，并且每一個少數(shù)類樣本合成數(shù)量相同，存在一定的盲目性，可能會產(chǎn)生冗余數(shù)據(jù)[6]。有研究者提出基于聚類的思想進行過抽樣，并且考慮樣本權(quán)重，使新樣本更有代表性。Georgios等[7]提出了基于K-means聚類和SMOTE的過抽樣算法。王換等[8]聚類訓練集后，確定樣本的合成權(quán)重，實現(xiàn)新樣本合成。王忠震等[9]聚類訓練樣本后，在簇內(nèi)樣本和簇心之間進行新樣本的合成。夏英等[10]使用層次聚類法聚類少數(shù)類，確定樣本采樣權(quán)重。董宏成等[11]基于HDBACAN(hierarchical density-based spatial clustering of app-lications with noise)聚類少數(shù)類，根據(jù)集群稀疏度合成樣本。

以上研究中計算樣本權(quán)重時沒有考慮樣本的關(guān)鍵特征權(quán)重，樣本中的每一個特征價值不同，在合成新樣本時需要重點考慮關(guān)鍵特征值更高的樣本。本文使用基于聚類分析的特征選擇算法FECAR[12](feature clustering and feature ranking)，篩選出樣本的關(guān)鍵特征集，并基于聚類思想提出了改進的SMOTE方法。

1 相關(guān)技術(shù)介紹

1.1 SMOTE算法

SMOTE算法由Chawla提出，其原理為通過少數(shù)類樣本與其N個近鄰樣本之間使用線性插值的方法合成新的少數(shù)類樣本，算法步驟為：

(1)對每一個少數(shù)類樣本，計算到其它少數(shù)類樣本的歐式距離，得到N個近鄰。

(2)從N個近鄰中，隨機選擇一個少數(shù)類樣本，合成新的少數(shù)類樣本。合成公式如式(1)所示

xnew=xi+rand(0，1)*(xj-xi)

(1)

其中，xnew代表新合成樣本，xi為第i個少數(shù)類樣本，xj為xi的隨機近鄰樣本。

1.2 AdaBoost算法

AdaBoost算法為經(jīng)典的集成算法，針對同一個訓練集經(jīng)過多次迭代學習，將多個弱分類器組合成強分類器。

假設(shè)訓練樣本集為S={(x1，y1)，(x2，y2)，…，(xm，ym)}，xi∈X，yi∈Y={-1，+1}， 迭代次數(shù)為T，基分類器為h。算法流程如下所示：

(1)初始化樣本集權(quán)重

D1(i)=1/m

(2)

(2)對于t=1，2，…T：

1)使用具有權(quán)重Dt的樣本集訓練弱分類器ht

2)計算弱分類器ht的分類誤差

(3)

3)計算弱分類器權(quán)重

(4)

4)更新樣本集權(quán)重

(5)

(3)構(gòu)建最終分類器

(6)

2 算法設(shè)計

本文提出基于聚類的樣本過采樣算法，樣本權(quán)重計算時考慮了關(guān)鍵特征權(quán)重及與簇心距離權(quán)重，分類模型分為3個階段：構(gòu)建關(guān)鍵特征集階段、過采樣階段和構(gòu)建模型階段。分類模型處理過程如圖1所示。

2.1 構(gòu)建關(guān)鍵特征集

采用基于聚類分析的特征選擇算法FECAR[12]選取樣本的關(guān)鍵特征集。具體過程包括特征聚類和特征選擇，如下所示：

(1)首先使用最小描述長度準則MDLP[12](minimum description length principle)方法對特征進行離散化。

(2)利用對稱不確定性SU(symmetric uncert-ainty)計算特征之間的關(guān)聯(lián)性。

(3)利用信息增益IG(information gain)計算特征與類標之間的相關(guān)性。

(4)使用K中心點聚類(K-Medoids)算法進行特征聚類：

1)選擇topK個與類標信息增益最高的特征為初始代表特征。

2)將每個特征指派到關(guān)聯(lián)度最高的簇。

3)更新簇的代表特征為關(guān)聯(lián)性和最大的特征。

4)重復(fù)2)和3)，直到簇的代表特征不再變化。

(5)對每個簇中的特征，按照與類別信息增益由高到低排序。

(6)每個簇按照特征數(shù)目占總特征數(shù)目比例篩選出靠前的特征，共選擇m個特征，構(gòu)建關(guān)鍵特征集Key-Features。

(7)returnKey-Features。

2.2 基于聚類的改進SMOTE過采樣算法

Georgios等[7]提出的基于K-means聚類和SMOTE過采樣算法，但是通過聚類全部訓練集樣本，再合成新樣本，可能會產(chǎn)生噪聲樣本[13]。因此，本文只聚類少數(shù)類樣本，對聚類后每一個簇進行新樣本合成，確保合成樣本在簇內(nèi)，提高了數(shù)據(jù)的可靠性。合成樣本總數(shù)目為多數(shù)類與少數(shù)類樣本的差值[7]。首先，根據(jù)簇內(nèi)樣本數(shù)占少數(shù)類樣本比值，計算該簇合成樣本數(shù)目。然后，根據(jù)少數(shù)類樣本的關(guān)鍵特征值占全部關(guān)鍵特征值比值的平均值計算關(guān)鍵特征權(quán)重，根據(jù)樣本與簇心的距離倒數(shù)占比計算距離權(quán)重。由這兩個權(quán)重計算得到樣本合成權(quán)重。由樣本合成權(quán)重和所在簇的生成數(shù)目計算得出每個樣本的合成數(shù)目，最后采用改進SMOTE算法合成樣本。

算法1：基于聚類的改進SMOTE算法

Input：訓練樣本S，合成樣本數(shù)目Num，關(guān)鍵特征集Key-Features，關(guān)鍵特征索引indexes，聚類數(shù)目K，近鄰數(shù)目N。

Output：合成新樣本集Snew

(1)Smin=?Smaj=?Snew=?

(2) forsinS:

(3) ifs.deactive==1Smin=s∪Smin

(4) elseSmaj=s∪Smaj

(5) end for

(6)clf=KMeans(n_clusters=K)

(7)clf.fit(Smin) //聚類少數(shù)類

(8) foriin range(K):

(9)Ci=[(clf.labels_==i)]//得到聚類后的簇

(10) 計算每個簇的合成樣本數(shù)目

(7)

|Ci| 為簇Ci中的樣本數(shù)目, |Smin| 為少數(shù)類樣本的總數(shù)目。

(11) end for

// 計算樣本合成數(shù)量

(12) foriin range(K)://處理每個簇

(13) forjin range(|Ci|)://處理簇中每個樣本

(14)Wf=0 //每個樣本的關(guān)鍵特征權(quán)重

(15) forkin (indexes):

//計算樣本xj每一個關(guān)鍵特征k占簇內(nèi)全部樣

//本關(guān)鍵特征的比值之和

(16)

(8)

(17) end for

//樣本xj關(guān)鍵特征權(quán)重為比值之和除關(guān)鍵特征

//集的數(shù)目

(18)

(9)

(19) 計算樣本xj與簇心Ci的歐式距離Dji

//計算樣本xj與簇心Ci距離權(quán)重, 樣本距離簇

//心越近, 權(quán)重越高。

(20)

(10)

//計算樣本xj權(quán)重

(21)

W=αWf+βWd

(11)

其中α+β=1。

//計算樣本xj合成數(shù)量

(22)

(12)

//計算樣本合成數(shù)量結(jié)束

//合成新樣本

(23) 計算樣本xj到簇中其它樣本的歐式距離, 得到其N個近鄰樣本k_neighbors

(24) formin range(Nxj):

(25)neighbor=radom.choice(k_neighbors)

(26)diff=neighbor-xj

(27)xnew=xj+random(0,1)*diff

(28)Snew=xnew∪Snew

(29) end for

(30) end for

(31) end for

(32) returnSnew

2.3 構(gòu)建CSMOTE-AdaBoost模型

樣本集經(jīng)過算法1處理后得到合成新樣本集，與原訓練集合并后得到平衡數(shù)據(jù)集，然后使用AdaBoost算法訓練樣本，得到分類模型。本文提出的CSMOTE-AdaBoost(clustering SMOTE AdaBoost)算法模型訓練過程如下所示：

(1)通過算法1合成新樣本，得到Snew。

(2)將合成新樣本集與原訓練樣本集合并，得到平衡樣本集

St=S∪Snew

(3)對平衡樣本集使用AdaBoost算法進行訓練。

(4)獲得分類模型CSMOTE-AdaBoost。

3 實 驗

本文采用NASA公布的軟件缺陷數(shù)據(jù)集MDP作為實驗數(shù)據(jù)，采用十折交叉驗證法，每次取9份作為訓練集，1份作為測試集，最后取平均值進行算法評估。首先，采用改進SMOTE算法平衡訓練集，使用AdaBoost算法進行訓練，得到分類模型 CSMOTE-AdaBoost，然后使用測試集驗證模型分類效果。同時，對本文提出的算法尋找最優(yōu)參數(shù)，驗證算法中選取關(guān)鍵特征權(quán)重和距離權(quán)重的有效性，并與傳統(tǒng)算法進行比較，驗證本算法的有效性。

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

本文選取NASA公布的軟件缺陷數(shù)據(jù)集MDP中7組數(shù)據(jù)集，這些數(shù)據(jù)的信息見表1。

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

3.2 評價指標

軟件缺陷預(yù)測模型的評價指標包括查準率Precision、查全率Recall、ROC(receiver operating characteristics)曲線下面積AUC(area under the curve)和F1，這些指標的計算均基于混淆矩陣，見表2。

表2 分類結(jié)果混淆矩陣

Precision表示預(yù)測正確的正類模塊數(shù)量占所有預(yù)測結(jié)果為正類的模塊數(shù)量比例

(13)

Recall表示預(yù)測正確的正類模塊數(shù)量占實際正類模塊數(shù)量比例

(14)

F1是查準率和召回率的調(diào)和平均數(shù)

(15)

3.3 參數(shù)尋優(yōu)

本算法使用Python3.7中的Scikit-learn庫實現(xiàn)，主要參數(shù)包括少數(shù)類簇數(shù)目K、少數(shù)類樣本近鄰數(shù)目N，關(guān)鍵特征權(quán)重和距離權(quán)重系數(shù)α和β，其余參數(shù)均使用默認值，采用默認CART決策樹作為AdaBoost算法的基分類器。

少數(shù)類聚類數(shù)目K和近鄰數(shù)目N設(shè)置要綜合考慮，7組數(shù)據(jù)集中絕大部分少數(shù)類樣本數(shù)目較少，因此簇的數(shù)目設(shè)置不能過大。本文中少數(shù)類簇數(shù)目的確定采用“肘部法則”[14]，根據(jù)選定的不同聚類簇數(shù)K，計算簇的誤差平方和SSE(sum of squared error)，得到折線圖。SSE的計算公式如下所示

(16)

其中，K為聚類簇數(shù)，cj為第j個聚類簇，μj為cj的簇心，x為cj中的樣本數(shù)據(jù)點。

在7組數(shù)據(jù)集中JM1樣本數(shù)量明顯多于其它數(shù)據(jù)集，該數(shù)據(jù)集的K-SSE圖如圖2所示，其它數(shù)據(jù)集的K-SSE圖如圖3所示。從圖中可以看出，在K為4時，大部分數(shù)據(jù)集的SSE值減小變緩。因此，本文中的K取值為4。

圖2 JM1 K-SSE

圖3 其它數(shù)據(jù)集K-SSE

本文驗證α和β以下組合(0.1，0.9)，(0.2，0.8)，(0.3，0.7)，(0.4，0.6)，(0.5，0.5)，(0.6，0.4)，(0.7，0.3)，(0.8，0.2)，(0.9，0.1)，實驗結(jié)果如圖4～圖7所示。

圖4 α和β不同取值Precision對比

圖6 α和β不同取值A(chǔ)UC對比

圖7 α和β不同取值F1對比

從圖中結(jié)果可以看出，當α和β取值為(0.5，0.5)時，Precision、Recall和F1這3個指標總體取得較好的結(jié)果；AUC指標中取得的最大值數(shù)據(jù)集數(shù)目也大于其它取值。因此本算法中α和β取值為(0.5，0.5)。

在α和β均為0.5，K為4，驗證近鄰數(shù)目N對4個評價指標的影響。通過表1數(shù)據(jù)集信息可以看出，不同數(shù)據(jù)集中的少數(shù)類樣本數(shù)目有較大差異，對于JM1數(shù)據(jù)集，近鄰數(shù)目設(shè)置從3開始，分別驗證3、4、5、6、8、10、12、15、18、20、25、30、35、40、45、50，實驗結(jié)果如圖8所示。從圖中結(jié)果可以看出，近鄰數(shù)目的增加對指標影響波動較小，僅當N=5時，Recall和F1值最高。

對于其它數(shù)據(jù)集少數(shù)類樣本較少，近鄰數(shù)目設(shè)置在3到8之間，測試結(jié)果分別如圖9～圖12所示。大多數(shù)數(shù)據(jù)集在N取值為5時取得了較好的結(jié)果，因此本文中的N設(shè)置為5。

圖9 N不同取值其它數(shù)據(jù)集Precision對比

圖11 N不同取值其它數(shù)據(jù)集AUC對比

圖12 N不同取值其它數(shù)據(jù)集F1對比

3.4 特征權(quán)重和距離權(quán)重有效性驗證

為了驗證關(guān)鍵特征權(quán)重和距離權(quán)重對算法的影響，將算法中的α取值為0，即刪除關(guān)鍵特征權(quán)重，只保留聚類少數(shù)類并計算距離權(quán)重，記為DW-Ada(distance weight AdaBoost)；將算法中的β取值為0，即刪除除聚類和距離權(quán)重，只保留關(guān)鍵特征權(quán)重，記為KFW-Ada(KeyFeatures weight AdaBoost)。3種算法均采用10次十折交叉驗證的平均值，結(jié)果見表3(加粗為最高值)。

表3 DW-Ada、KFW-Ada與本算法實驗結(jié)果對比

從表3中的實驗結(jié)果可以看出，本文提出算法在絕大多數(shù)情況下均優(yōu)于DW-Ada和KFW-Ada算法。其中Preci-sion、AUC在7個數(shù)據(jù)集上均獲得了6次第1，F(xiàn)1獲得了5次第1，Recall獲得了4次第1，均領(lǐng)先于其它兩種算法。平均值最高分別提高了1.1%、1.8%、2.8%和1.4%。以數(shù)據(jù)集KC3為例，在十折交叉驗證中，篩選出的關(guān)鍵特征見表4(僅列出次數(shù)大于5的特征)。

表4 KC3數(shù)據(jù)集關(guān)鍵特征

本算法在合成新樣本時，綜合考慮樣本的關(guān)鍵特征權(quán)重和與簇心距離權(quán)重，在4個評價指標Precision、Recall、AUC和F1比另外兩種算法最高分別提高了3.7%、5.7%、6%和4.5%。由此驗證了關(guān)鍵特征權(quán)重及與簇心距離權(quán)重的有效性。

3.5 本算法與其它算法比較

為了驗證本文提出算法的有效性，首先，分別使用SMOTE[4]、K-means SMOTE[7]、ADASYN[15]、Borderline-SMOTE[15]過抽樣算法實現(xiàn)數(shù)據(jù)集平衡，然后采用AdaBoost算法進行分類。為保證實驗結(jié)果的有效性，均采用十折交叉驗證，5種算法實驗結(jié)果見表5～表8(加粗為最高值)。

表5 5種算法Precision實驗結(jié)果對比

表6 5種算法Recall實驗結(jié)果對比

表7 5種算法AUC實驗結(jié)果對比

表8 5種算法F1實驗結(jié)果對比

從表中的實驗結(jié)果可以看出，本文提出的算法在絕大多數(shù)情況下優(yōu)于其余4種算法，Precision、AUC和F1在7個數(shù)據(jù)集中均獲得6次第1，平均值最高分別提高了2.1%、5.6%和2.1%。Recall在7個數(shù)據(jù)集上獲得了5次第1，平均值最高提高了2.2%。對于數(shù)據(jù)集JM1，本算法的Recall低于K-means SMOTE+AdaBoot，AUC低于SMOTE+AdaBoost，但是，本算法的Precision和F1均不低于這兩種算法。對于數(shù)據(jù)集KC3，本算法的Precision低于算法SMOTE+AdaBoost，但是其余指標均高于此算法；對于數(shù)據(jù)集PC3，本算法的Recall和F1低于算Borderline-SMOTE+AdaBoost，但是Precision和AUC均高于這兩種算法。由此驗證了本算法的有效性。

4 結(jié)束語

本文針對軟件缺陷預(yù)測中的不平衡數(shù)據(jù)問題，提出了基于聚類的改進SMOTE過采樣算法，聚類少數(shù)類樣本后，在合成樣本時綜合考慮少數(shù)類樣本的關(guān)鍵特征權(quán)重以及與簇心的距離權(quán)重。平衡數(shù)據(jù)集后，采用AdaBoost算法構(gòu)建分類模型CSMOTE-AdaBoost。經(jīng)過實驗，確定了最優(yōu)參數(shù)，驗證了本算法中關(guān)鍵特征權(quán)重和距離權(quán)重的有效性，并與傳統(tǒng)算法進行實驗結(jié)果對比，驗證了本算法具有更好分類效果。不足之處在于，本文僅在現(xiàn)有數(shù)據(jù)集中驗證，工業(yè)環(huán)境具體使用沒有實際驗證。后續(xù)過程需要驗證提出模型在實際使用中的有效性，并加以改進。