基于自適應聚類過采樣的軟件缺陷預測研究*

賈燕華，李英梅

（哈爾濱師范大學）

0 引言

在軟件的開發研究過程中，由于需求分析不清晰、接口參數傳遞不匹配等因素的影響，會使得軟件不可避免地產生各種缺陷.它的存在會降低軟件使用過程中的可維護性，而且缺陷數量會隨著軟件規模和復雜度的增加而隨之增加.軟件缺陷預測技術通過對已有程序模塊的可度量特征及出現規律的認知，挖掘軟件歷史倉庫構建缺陷數據集并預處理，構建缺陷預測模型預測待檢程序模塊的缺陷分布［1－2］.及早地預測缺陷可以幫助軟件測試人員有的放矢地進行軟件測試，提高軟件質量的可靠性.

當某些類的樣本數量明顯大于其他類樣本數量時，就會引發數據集類不平衡問題.類不平衡問題廣泛存在于各種實際工作領域中，如醫學診斷［3］、網絡入侵檢測［4］、信貸欺詐［5］等.由于缺陷預測數據集中無缺陷樣本（即多數類）比有缺陷樣本（即少數類）要多得多，且80%的缺陷集中分布于20%的程序模塊內，這說明在軟件缺陷預測領域中也普遍存在類不平衡問題.傳統的分類方法通常為確保得到較高的整體分類性能會傾向于多數類樣本，導致分類器性能產生偏差，少數類樣本被錯誤分類［6］.同樣地，使用傳統分類方法構建的軟件缺陷預測模型，其結果將趨向于無缺陷數據，從而影響軟件正常運行，致使軟件產生故障甚至失效，帶來巨大的經濟損失.該文所提出的LDKMAS 算法是在數據級層面對不平衡數據進行過采樣處理，該算法使模型的最終預測結果不再偏向于無缺陷數據，經過實驗驗證該法較之流行、經典的過采樣方法效果更優異.

1 相關研究

1.1 軟件缺陷預測研究

根據軟件缺陷傾向性分類結果，可以將其當作一個二分類問題，其結果為有缺陷傾向性和無缺陷模塊傾向性兩類.典型的軟件缺陷預測模型構造和預測過程如圖1所示.

圖1 軟件缺陷預測過程

該過程主要包括4個階段：

（1）構建缺陷預測數據集.從軟件歷史倉庫抽取程序模塊，根據提取程序模塊的度量元和缺陷類別，構建軟件缺陷預測數據集.

（2）數據預處理.由于構建的數據集質量欠佳，需采用有效方法預處理數據，目前主要采用特征工程、數據采樣等方法.

（3）建立預測模型.經過必要的數據預處理后，借助特定的建模方法構建缺陷預測模型，并使用數據集對預測模型進行訓練.

（4）預測新程序模塊.基于度量元取值和缺陷預測模型判斷被測項目內新程序模塊的缺陷類別（有缺陷或者無缺陷）.

軟件缺陷預測的研究內容主要包括設計與缺陷強相關的度量元、研究數據集的預處理技術和改進軟件缺陷預測模型.該文將關注由缺陷類樣本和無缺陷類樣本之間的不平衡分布引起的數據集質量問題.

1.2 不平衡數據過采樣研究

目前解決不平衡數據的方法主要分為兩類：數據級方法、算法級方法.算法級方法側重于引入成本敏感因素［7］、集成學習［8］等，使分類器偏向于少數類.數據級方法通過一些重采樣技術來尋求類別的平衡分布.與算法級方法相比，數據級方法能真實反映研究對象的性質，因其獨立于分類器的靈活性和實現的簡易性顯示出無限潛力［9］.

過采樣技術是通過復制現有少數樣本或生成新的少數樣本來平衡不平衡數據.隨機過采樣是最簡單的平衡數據集過采樣方法，即通過隨機復制少數樣本合成新樣本，但因重復樣本過多容易過擬合.Chawla等人提出合成少數類過采樣技術SMOTE，該方法是通過對隨機選擇的少數類樣本及其k 近鄰樣本進行線性插值而生成新樣本，而不是僅復制現有樣本［10］.但是，SMOTE 將所有少數類樣本視為同等重要，忽略了樣本的分布信息而導致采樣具有盲目性［11］.為了消除其缺點，許多學者采用安全區域采樣或邊界區域采樣的策略來選擇樣本進行合成.

邊界區域采樣：根據支持向量機（SVM）的原理，樣本越靠近決策邊界區域其包含的重要信息就越多［12］，因此許多研究者強調對邊界區域樣本采樣并提出相應算法.Borderline Smote［13］和ADASYN［14］是邊界區域采樣中較為常用的兩種方法，但因其強調邊界區域則不可避免的會容易產生大量噪聲，降低數據集質量.

安全區域采樣：避免引入新的重疊或噪聲樣本，分布較為密集的樣本被采樣的幾率更大.Bunkhumpornpat等人根據少數類樣本K 近鄰樣本中同類樣本占比識別安全樣本，提出了Safe－Level SMOTE，以此生成較為安全的新樣本［15］.Douzas等人提出了K－Means SMOTE 算法，該算法應用K－Means 算法對整體數據進行聚類，依據簇中異類樣本數占比選擇安全子簇進行過采樣來減少噪聲的影響［16］.

為避免產生噪聲和離群點，該文采取安全區域采樣策略使得平衡后數據集分布更集中.首先為缺陷數據聚類，然后根據聚類后各子簇密度自適應確定各子簇采樣量.較于小子簇和稀疏簇，大子簇、密集簇中的樣本更可能處于安全區域，因此越大越密集的子簇所獲采樣量越多.

2 算法介紹

LDKMAS算法包含三個步驟：K－Means＋＋聚類、［17］、局部密度計算以及自適應采樣.首先利用K－Means＋＋聚類將缺陷數據劃分成k個子簇；然后計算各子簇中樣本的局部密度，合計為子簇密度；最后根據子簇密度識別子簇重要性自適應插值過采樣.LDKMAS算法框架如圖2所示.

圖2 LDKMAS算法框架

2.1 K－Means＋＋聚類

為避免K－Means算法隨機選取初始聚類中心點導致聚類結果有所差異，K－Means＋＋算法對此進行了優化調整.該算法要求初始的k個聚類中心之間的相互距離要盡可能的遠，即逐個選取k個聚類中心，離已選聚類中心越遠的樣本點越有可能被選為下一個聚類中心.

2.2 局部密度

該文局部密度結合樣本分布特點計算，可估算當前樣本的潛在價值，提高樣本合成質量.樣本i的局部密度計算方式如下：

其中KNN（i）為樣本i的Kn個近鄰樣本構成的集合，dij為樣本i，j間的歐式距離.由式（1）可知，樣本點i到其Kn近鄰的距離越小，其密度值ρi越大.該文采用樣本i的Kn近鄰信息定義樣本i的局部密度ρi更能反映數據集樣本的真實分布信息.

假設缺陷數據類被分為k個子簇Cminj，j ＝1，2，…，k，每個子簇Cminj的密度SDminj定義如下：

其中，｜Cminj｜表示的是子簇Cminj的大小，ρi表示屬于子簇Cminj各樣本的局部密度.由式（2）可知，子簇密度數值與該子簇所包含樣本的數量和局部密度成正相關.

2.3 自適應過采樣

對缺陷類樣本進行聚類和局部密度計算后，首先根據子簇密度值自適應計算每個子簇的采樣量OSminj，其定義如下：

其中N是總過采樣量，即無缺陷樣本與缺陷樣本的數量差，則子簇越大、越密集，其采樣量越大.確定每個子簇采樣量后，在子簇樣本與其Kn近鄰之間執行線性插值，直至達到該子簇采樣量.插值公式如下：

其中a表示（0，1）之間的隨機數，xij表示第i個子簇中的第j個樣本，Knij表示樣本xij的隨機某個Kn近鄰樣本.

3 實驗

為驗證該文所提算法的有效性，該文實驗將在AEEEM 數據集上使用不做處理的原始數據和六種經典的過采樣算法作為實驗對比組，以決策樹為分類器進行10 次十折分層交叉驗證，取平均值作為最終實驗結果.

3.1 數據集

AEEEM數據集是由D’Ambros等人共同收集整理的開源數據集［18］，包含61 個特征值，在軟件缺陷預測領域具有真實可靠性，其基本信息見表1.

其中，設非缺陷數為N，缺陷數為Q，不平衡率（Imbalance Ratio，IR）為無缺陷模塊數與有缺陷模塊數的比值，計算如下：

項目 特征數 樣本量 缺陷數 不平衡率EQ 61 324 129 1.51 JDT 61 997 206 3.84 LC 61 691 64 9.80 ML 61 1862 245 6.60 PDE 61 1497 209 6.16

3.2 評價指標

對于不平衡數據，少數類的正確分類尤為重要，基于單一準確率的傳統評估方法不再適用.因此，為了定量評估不平衡數據過采樣后的分類性能，該文使用F1值和AUC值作為性能度量，比較不同的方法.這些性能指標通常取決于混淆矩陣，見表2.

預測值有缺陷模塊 無缺陷模塊真實值有缺陷模塊 TP FN無缺陷模塊 FP TN

（1）查準率：預測為有缺陷樣本中真實類別為有缺陷所占的比例.

（2）召回率：預測為有缺陷樣本的數量占真實有缺陷樣本的比例.

（3）F1－score：Precision和Recall的加權和平均值.

（4）AUC：ROC 曲線下的面積.ROC 曲線是接受者工作特征曲線，其橫坐標為假陽率，縱坐標為真陽率.

其中，TPrate為真陽率，其值等于召回率；FPrate為假陽率

3.3 實驗結果

將多個經典的類不平衡過采樣算法與LDKMAS算法進行比較，在AEEEM數據集上的原始數據和各個方法的實驗結果見表3、表4 所示.其中OD、ROS、SMO、ADA、BLS、SLS、KMS、LKS分別為原始數據、隨機過采樣、SMOTE 過采樣、ADASYN 過采樣、Borderline Smote 過采樣、Safe Level Smote過采樣、K－Means Smote 過采樣、LDKMAS過采樣的簡稱.上述6 種對比過采樣算法通過python 中的imblearn 工具包和Github中的somte－variants工具包調用，決策樹分類器通過python中的sklearn工具包調用.

項目 OD ROS SMO ADA BLS SLS KMS LKS EQ 0.647 0.638 0.651 0.635 0.621 0.628 0.639 0.649 JDT 0.316 0.261 0.296 0.311 0.290 0.291 0.324 0.328 LC 0.539 0.522 0.535 0.522 0.528 0.518 0.519 0.554 ML 0.329 0.344 0.337 0.336 0.353 0.328 0.323 0.358 PDE 0.303 0.328 0.308 0.308 0.301 0.309 0.306 0.333平均 0.427 0.419 0.425 0.422 0.419 0.415 0.422 0.444

由表3和表4可看出，對數據集進行過采樣預處理確實能夠提升預測模型分類效果.進一步而言，不平衡率較低的數據集中SMOTE 過采樣算法效果雖略勝于該文算法，但是LDKMAS 過采樣在絕大多數的情況下表現更優.LDKMAS過采樣較于不做處理的原始數據和其他6 種過采樣算法平均提升了2%，且F1和AUC均值最高.上述結果證明了LDKMAS過采樣在數據不平衡缺陷預測中的有效性，也說明利用子簇密度自適應判斷過采樣方法會提高模型的預測效果.

4 總結

為了解決類不平衡問題，該文采取安全區域采樣思想，考慮樣本分布特點，提出一種子簇密度自適應判斷過采樣方法.根據各子簇重要性自適應判斷確定自身采樣量，最大程度地利用樣本的潛在價值，使平衡后的數據盡量能還原初始數據分布，有效減少過擬合，緩解類不平衡問題對缺陷預測模型性能的影響.選取了具有真實可靠性的AEEEM 數據集上進行實驗，結果表明LDKMAS算法在F1值和AUC值指標上均得到了不同程度地提升，具有更好的缺陷預測性能.

該文只研究了軟件缺陷預測中不平衡數據過采樣方法，下一步將研究能與算法相匹配的提升數據集質量方法，如噪聲處理、特征選擇、重疊區清理等，結合高效的集成學習算法進一步提高模型的預測效果.