張 彤，李英梅

（哈爾濱師范大學）

0 引言

軟件缺陷指的存在于計算機程序或者軟件的不能使得程序正常運行的瑕疵.軟件缺陷問題不僅會浪費大量的人力、物力和財力，有的情況還會危及到人類的生命安全［1］.因此軟件缺陷預測問題在軟件工程領域上越來越受到人們的關注.

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

1 相關研究工作

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

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

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

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

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

2 算法介紹

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

圖1 MSKsmote算法流程

2.1 樣本預處理階段

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

圖2 Smote過采樣算法思想

該算法的算法流程如下：

輸入：T為少數樣本數據數量

N為過采樣數量

K為最近鄰的數量

輸出：新的少數類數據

（1）對于缺陷類每一個數據x，用歐式距離計算出它到其它所有有缺類數據的距離.

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

（3）對于每一個隨機選出的近鄰xn，按照公式（1）分別構建新的有缺陷數據.

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

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

圖3 borderline－smote算法

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

2.2 K－means聚類算法

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

輸入數據樣本集合D：｛x1，x2，x3…xn｝

輸入聚類的簇數：k 輸入最大迭代次數：T

（1）在初始的樣本集合D中，隨機選取k個點作為初始質心｛u1，u2，u3…uk｝.

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

（3）｛對于每一個數據樣本，利用公式（2）計算該點屬于何類.

其中ci表示樣本數據i與k個簇中距離最近的那個類.uj表示質心j.經過對初始數據的聚類之后，對簇的類型進行判斷，當一個簇中少數類數據多于多數類數據的時候稱為少數類數據簇，反之稱之為多數類數據簇.這一步的主要作用是可以找出簇中的異點（例如多數類簇中的少數數據），因為該點由于與其它點結構相似，但是與多數周圍其他點不同，這就會影響模型的最終預測效果.通過聚類算法，可以找出危險點中的異點，隨后刪除該點并最終對少數類點進行smote過采樣方法擴充少數類.

3 實驗

該文實驗將在AEEEM 數據集，在python的sklearn 工具包的基礎上，以貝葉斯分類器作為基分類器，采用十折交叉法，進行100 次的實驗，取平均值作為本次實驗的最終結果.該文將選取經典的類不平衡算法作為對照實驗組.

3.1 數據集

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

表1 AEEEM數據信息

3.2 評價指標

該文重點研究軟件是否有缺陷，所以該實驗被認為是一個二分類問題，一種是有缺陷標記模塊（少數類），一種是無缺陷模塊（多數類）.為了能更好的驗證該方法是否比其它經典的類不平衡算法更好，將介紹以下公式.

（1）準確率：又被叫做查準率，真正含有缺陷的模塊在所有被預測模型標記為有缺陷模塊所占的比例，其定義如式（4）.

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

3.3 實驗結果

該文將多個經典的類不平衡算法與MSKsmote算法進行比較，在AEEM 數據集上的各個方法實驗結果見表2.其中經典的類不平衡算法包括隨機過采樣方法（ROS），隨機欠采樣方法（RUS），Smote過采樣方法和ADASYN.

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

由表2 可知，在經典的類不平衡算法中，ADASYN算法效果最好.但是MSKsmote 算法在絕大多數的情況中表現最好，并且F1均值最高，因此該文提出的MSKsmote算法較經典的類不平衡算法更為好，這也說明將危險點中的異點清除會提高模型的預測效果.

4 結論

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

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