軟件缺陷預測中基于排序集成的特征選擇方法

姜 麗，姜淑娟，于 巧

1(中國礦業大學 計算機科學與技術學院，江蘇 徐州 221116)2(江蘇師范大學 計算機科學與技術學院，江蘇 徐州 221116)

1 引 言

20世紀70年代，軟件工程領域的研究人員發現軟件中缺陷的分布并不是隨機或平均的，而是有規律的，軟件缺陷預測技術就是尋找這種規律的技術，它是軟件工程領域最為活躍的研究對象之一.軟件缺陷預測技術通過分析軟件代碼或軟件開發過程，設計出與軟件缺陷相關的度量元，隨后通過挖掘軟件歷史倉庫構建缺陷數據集，最后基于該數據集構建缺陷預測模型，預測被測項目中潛在的缺陷模塊.Boehm[1]指出軟件缺陷在軟件中的分布服從“2-8原則”，即80%的缺陷分布在20%的程序模塊中.軟件缺陷預測技術能幫助軟件測試人員定位這些可能有缺陷的模塊，使其著重針對這些模塊進行測試，修復盡可能多的軟件缺陷，提高軟件測試的效率，從而提高軟件質量，對指導和優化軟件測試工作起著重要的作用.

然而，在設計度量元的過程中，若考慮過多的度量元可能會引入冗余特征或無關特征，增加構建軟件缺陷預測模型的時間，甚至可能會影響軟件缺陷預測模型的分類性能，引起維數災難問題.特征選擇是解決維數災難的一種方法，從缺陷數據集中移除冗余特征和無關特征，選出最具代表性的特征子集，是特征選擇方法的關鍵，對于提高軟件缺陷預測性能有重要意義.

目前，典型的特征選擇方法有相關系數方法、信息增益率方法和ReliefF方法等，不同特征選擇方法的性能是有差異的，甚至可以說差異較大，這源于它們的方法原理不同，得到的特征排序序列也不同.那么是否可以選出三種常用的特征選擇方法(Correlation、GainRatio、ReliefF)的通用特征子集，能更好地對缺陷進行預測？

針對這個問題，本文提出了一種基于排序集成的特征選擇方法，它綜合了三種常用的基于排序的特征選擇方法，包括相關系數方法、信息增益率方法和ReliefF方法.該方法對于每一個缺陷數據集，在三種特征選擇方法得到的特征序列的基礎上，得到特征綜合排名，分別選取排名靠前的占特征總數10%至100%的特征構建新的數據集，然后采用邏輯回歸模型作為缺陷預測模型，并采用接受者操作特征曲線下面積AUC指標[2，3]來評價不同預測模型的分類性能.實驗結果表明：基于排序集成的特征選擇方法綜合了三種方法，進行特征選擇后選出的特征子集更準確，避免了一種或幾種特征選擇方法錯誤選擇特征子集而帶來的預測模型性能低的情況.

2 研究背景與相關工作

2.1 軟件缺陷預測

軟件缺陷預測技術是通過分析軟件代碼、軟件開發過程等，設計與軟件缺陷相關的度量元，隨后通過挖掘軟件歷史倉庫構建缺陷數據集，對數據集進行預處理后構建缺陷預測模型，對被測項目內新程序模塊有無缺陷進行預測的一種技術.

軟件缺陷預測的研究內容主要包括：(1) 設計與缺陷強相關的度量元，例如：McCabe環路復雜度度量[4]，Halstead科學度量[5]，Chidamber和Kemerer提出的CK度量元[6]，軟件演化度量元[7]等；(2) 研究數據集的預處理技術，如特征選擇、去除噪聲、聚類分析、抽樣、維數規約、離散化和二元化等，目前研究人員重點關注缺陷預測數據集中的噪聲問題、維數災難問題和分類不平衡問題等;(3)改進預測模型.

2.2 特征選擇方法

在軟件缺陷預測中，特征選擇是解決維數災難的一種有效方法，目前已有的特征選擇算法大致上可以分為兩大類：基于子集搜索的特征選擇算法和基于排序的特征選擇算法.其中，基于子集搜索的特征選擇算法考慮特征與類別屬性之間的相關性和特征之間的關聯性，但在特征較多的情況下，搜索空間太大，開銷也太大.基于排序的特征選擇算法根據每一個特征與類別屬性之間的關聯性，從高到低排序，排名越靠前，與類別屬性的相關性越高，表明該特征區分不同類別的能力越強，然后從中選出排名靠前的特征，建立缺陷預測模型，這類算法效率比較高，但選出的特征子集內通常含有冗余特征.

特征選擇方法還可以更細致地分為以下四類：

1)嵌入方法：將特征選擇嵌入到數據挖掘算法中，也就是數據挖掘算法本身會決定保留并使用的特征和要忽略的特征，決策樹就是這類方法中的一種.

2)過濾方法：在數據挖掘前，先使用獨立于數據挖掘的算法進行特征選擇，即對數據集進行預處理，產生一個特征子集.劉望舒等人[8]基于過濾方法，提出軟件缺陷預測中基于聚類分析的特征選擇方法.本文基于過濾方法進行研究.

3)包裝方法：分別將每一個特征子集作為數據挖掘算法的輸入，數據挖掘算法的結果反過來評價每一個特征子集，選取效果最好的特征子集.通常情況下無法枚舉出全部的子集，并且特征數較多時，這類算法的開銷太大.Menzies等人[9]和Song等人[10]提出的通用缺陷預測框架中均含有基于包裝方法的特征選擇方法.

4)混合方法：Gao等人[11]針對一個大規模遺留電信軟件系統，實現了一種混合特征選擇方法，在該方法中用到了多種特征排序評估方法和特征子集評估方法.Wang等人[12]嘗試借助集成學習方法將18種特征選擇方法進行組合，發現集成少數的特征選擇方法的預測性能要優于集成所有特征選擇方法.

不同特征選擇方法得到的特征排序序列不同，執行不同特征選擇方法后訓練出的預測模型的性能也有差異，執行單個特征選擇算法后構建的預測模型的泛化能力較差.我們提出了一種基于排序集成的特征選擇方法，它屬于過濾方法，集成了三種基于排序的特征選擇方法，包括相關系數方法、信息增益率方法和ReliefF方法，綜合了三種方法得到的特征排序序列，賦予每個特征一個權重，該方法能夠有效提高預測模型的泛化能力，有效避免單一特征選擇方法的不穩定性.

3 相關理論

3.1 特征選擇方法

3.1.1 皮爾森相關系數方法(Correlation)

皮爾森相關系數方法是通過衡量各特征與類別屬性之間的線性相關性，來評估一個特征對分類的貢獻程度的一種方法，最終選取相關度高的特征.相關系數通過兩個變量的協方差除以它們的標準差來計算，皮爾森相關系數的計算公式如公式(1)所示.

(1)

相關系數值在-1至1之間，其中，-1表示該特征與類別屬性完全負相關，1表示該特征與類別完全正相關，0表示該特征與類別屬性沒有關系.

3.1.2 信息增益率方法(GainRatio)

信息增益率方法根據特征給分類帶來的信息的多少進行特征選擇，一個特征帶來的信息越多，就越重要.其計算公式如公式(2)所示.

(2)

其中Gain(A)為特征A劃分數據集S后的信息增益，SplitE(A)表示特征的分裂信息.可以認為信息增益率最大的那個特征是與類別屬性最相關的特征.

信息增益率與信息增益相比，引入了分裂信息，特征取值點越多，分裂信息值就越大，這抵消了特征取值點的數目對特征為分類系統帶來的信息量的數目帶來的影響.

3.1.3 ReliefF方法

Relief方法在1992年由Kira和Rendell[13]提出，ReliefF方法是Relief方法的擴展，它不僅可以處理二分類數據集，還可以處理多分類數據集.ReliefF方法是基于實例的評估方法，它根據特征區分鄰近實例能力的好壞來評估特征的價值.ReliefF方法認為每個特征的平均權重可以通過如下計算公式求出：

(3)

在公式(3)中，k表示抽取的鄰近實例的數目，m表示隨機抽取實例的次數，Mj(C)代表類別C(除實例R所屬的類別外的其他類別)中第j個與實例R最近鄰的實例，p(C)表示屬于類別C的實例所占的比例，p(Class(R))表示與隨機選取的實例R屬于同一個類別的實例的比例，diff(A，R1，R2)表示實例R1和R2在特征A上的差，它的計算公式如下：

(4)

由公式(3)可以看出，權重的計算方法是初始權重減去相同分類的該特征值的差值，加上不同分類的該特征值的差值.若一個特征與分類有關，則相同分類的實例的該特征值應該相似，而不同分類的該特征值應該有差別，因此，權重高的特征分類能力強.

3.2 邏輯回歸模型

邏輯回歸模型(Logistic Regression，LR)[14]是在線性回歸模型的基礎上引入一個Sigmoid函數得到的，是一種非線性回歸方法，適合二分類問題.其中，Sigmoid函數如公式(5)所示.

(5)

3.3 預測模型評價指標

我們研究軟件缺陷預測中的二分類問題時，預測可能出現四種不同的結果，如表1所示.預測類別對應矩陣列，實際類別對應矩陣行，每一個單元格是對應類別的實例數目.真陽性(TP)和真陰性(TN)都是正確分類的結果，即得到的預測類別和實際類別相符.假陽性(FP)和假陰性(FN)是錯誤分類的結果，即得到的預測類別和實際類別不符.好的預測結果應該是矩陣的主對角線上的數值大，而非主對角線上的數值小.

表1 四種預測結果Table 1 Four prediction results

真陽性率(TPR)是被正確預測為有缺陷的實例數除以實際類別為有缺陷的實例總數，即

(6)

假陽性率(FPR)是被錯誤預測為有缺陷的實例數除以實際類別為無缺陷的實例總數，即

(7)

接受者操作特征曲線下面積就是AUC值[3]，該曲線表示的是預測模型的真陽性率和假陽性率之間的關系，如圖1所示.其中x軸為假陽性率，y軸為真陽性率，曲線上的每個點對應一個閾值，對于一種分類方法，每個閾值下會有一個TPR和FPR，通過調整該預測模型的閾值就可以得到ROC曲線.

較好的預測模型的假陽性率比較低，真陽性率比較高，所以較好的預測模型的接受者操作特征曲線較靠近(0，1)點，也就是靠近左上角.主對角線代表隨機預測的預測模型.

圖1 ROC曲線Fig.1 ROC curve

接受者操作特征曲線下面積AUC是評估模型平均性能的一種方法.如果一個預測模型的AUC值等于1，那么它是完美的；如果一個預測模型的AUC值等于0.5，那么它和隨機預測模型的效果是一樣的；如果一個預測模型的AUC值比另一個預測模型大，那么它的性能比另一個模型好.

于巧等人[15]指出由于AUC指標具有一個很好的性能：當訓練集中不同類別的實例分布變化時，即分類不平衡情況下，AUC值能夠保持相對穩定，所以使用AUC作為評價指標會更加準確可靠.Jiang等人[16]也通過實驗證明了AUC指標的誤差更小且更穩定，且在實證研究中AUC指標被廣泛應用于評價預測模型的性能[8，15].基于以上原因，本文實驗都在以AUC為性能評價指標的基礎上進行.

4 本文方法

本文提出一種基于排序集成的特征選擇方法，它結合了Correlation、GainRatio、ReliefF三種特征選擇方法，結合的具體方法如下：(1) 分別執行三種特征選擇方法，得到特征排序序列；(2) 對于每一個特征，將特征總數減去該特征的序列號作為權重賦給該特征；(3) 對于每一個特征，將三種方法得到的權重相加求和，得到該特征的總權重；(4) 根據特征總權重對特征從高到低進行排序，得到特征排序序列；(5) 從特征序列中從前往后依次選取排名前百分之x的特征.具體算法如算法1所示.

算法1.基于排序集成的特征選擇方法

Input：dataset，the percentage of featuresx

Output：the order of indexes

1begin

2a[]=correlation(dataset)；

3b[]=gainRatio(dataset)；

4c[]=reliefF(dataset)；

5n=numAttributes(dataset)；

6foreach featureiinado

7weight[a[i]]=n-i；

8foreach featurejinbdo

9ifa[i]==b[j]then

10weight[a[i]]=n-j+weight[a[i]]；

11end_for

12foreach featurekincdo

13ifa[i]==c[k]then

14weight[a[i]]=n-k+weight[a[i]]；

15end_for

16end_for

17 sortweight[] in descending order；

18 get the order of indexes which are the topx

percentage of features；

19end

該方法在本質上是一種投票法.第2行至第4行，分別執行Correlation方法、GainRatio方法、ReliefF方法，得到三個特征排序序列，與類別屬性最相關的特征排在前面，越靠后表示與類別屬性相關性越弱.第5行至第16行，將特征總數減去該特征的序列號作為權重賦給該特征，并將每種方法得到的每個特征的權重分別相加求和，得到該特征的總權重.第17行根據特征總權重對特征從高到低進行排序，排序越靠前的特征權重越大，即該特征越重要，得到基于排序集成的特征選擇方法獲得的特征排序序列.第18行選取排名前百分之x的特征，作為最終選出的特征子集.

5 實驗評估

本文為了研究基于排序集成的特征選擇方法對軟件缺陷預測性能的影響，提出了如下問題：在軟件缺陷預測問題中，與三種常用的基于排序的特征選擇方法(相關系數方法、信息增益率方法、ReliefF方法)相比，本文提出的基于排序集成的特征選擇方法能否提高缺陷預測模型的性能？

5.1 實驗對象

本文實驗以美國國家航空航天局NASA發布的11個缺陷數據集為實驗對象，包括CM1、JM1、KC3、MC1、MC2、MW1、PC1、PC2、PC3、PC4和PC5，這些數據集均為PROMISE庫1中的缺陷數據集.其中的特征均為軟件代碼度量元，包括McCabe環路復雜度度量和Halstead科學度量.McCabe環路復雜度度量是對程序內部結構的復雜度進行分析，認為循環和選擇所構成的環路越多，程序就越復雜，就越容易存在缺陷；Halstead科學度量根據操作符與操作數度量模塊的缺陷傾向性.數據集的基本信息如表2所示.

第1列是數據集名稱，第2列表示特征數，第3、4、5列分別表示全部的實例數，有缺陷的實例數，無缺陷的實例數.

1The Promise Repository of Empirical Software Engineering Data，http://openscience.us/repo/

5.2 實驗設計

為了驗證本文提出的基于排序集成的特征選擇方法的有效性，本文通過編程實現了該方法.實驗環境為Windows 7，32位，2G RAM，Open JDK 1.7，WEKA 3.7.

利用4種特征選擇方法，10個百分比和表2中的11個數據集進行組合實驗.

首先選取一個數據集，分別采用相關系數方法、信息增益率方法、ReliefF方法和基于排序集成的特征選擇方法對該數據集進行特征選擇；然后利用邏輯回歸方法構建預測模型，利用10折交叉驗證評估該預測模型的性能，得到該預測模型的性能評價指標AUC的值；最后對11個數據集做重復實驗，通過對這些AUC值畫折線圖，比較本文提出的方法與三種方法的性能差異，驗證軟件缺陷預測中基于排序集成的特征選擇方法的有效性.在實驗評估中，我們使用WEKA軟件包實現特征選擇算法、邏輯回歸分類算法等，各特征選擇方法除選取的特征數量參數按特征百分比設置外，其他的參數均采用WEKA默認的參數設置.

10折交叉驗證是評估分類方法性能的一種常用的方法，即將數據集分成10等份，依次選取其中的9份作為訓練集，剩下的1份作為測試集，進行10次訓練和測試，每次都會得到預測模型評價指標的值，將10次的平均值作為最終的評估值.在執行交叉驗證之前，先使用隨機數發生器將數據隨機化，使用的隨機種子不同會使數據的隨機化也不同，對同一數據集的交叉驗證就會產生不同的結果.為了使實驗多次運行都能得到完全相同的結果，也就是為了使實驗具有可重復性，本文實驗指定“1234”為固定的隨機種子.

5.3 實驗結果與分析

與三種常用的基于排序的特征選擇方法(相關系數、信息增益率、ReliefF方法)相比，本文提出的基于排序集成的特征選擇方法是否能夠提高缺陷預測模型的性能？

圖2表示在每一個數據集上執行四種特征選擇方法后的預測性能的對比，橫坐標表示采用特征選擇方法選取的特征百分比(10%至100%，100%表示不進行特征選擇)，縱坐標表示評價指標AUC的值，其中Assembly表示本文提出的基于排序集成的特征選擇方法.

從圖2可以看出：基于排序集成的特征選擇方法能在一定程度上消除某一種或某幾種特征選擇方法的不穩定性.以子圖(h)為例，ReliefF方法在從數據集PC2中選取10%的特征時，由于選取的最佳特征子集不準確，構建的預測模型與隨機預測模型相似，性能較差.執行基于排序集成的特征選擇方法后得到的預測模型性能較好，較ReliefF特征選擇方法性能提升了40.21%，原因在于基于排序集成的特征選擇方法會綜合考慮三種特征選擇方法選取的特征子集的優劣，選出更優質的特征子集.

從圖2的子圖(c)(d)(e)(g)(j)可以看出：在只選取10%的特征時，基于排序集成的特征選擇方法會選出較三種方法更好的特征子集，構建的預測模型的預測性能更好.

除了在上述10%的情況下執行基于排序集成的特征選擇方法后會提高缺陷預測性能外，在某些數據集中選取某些百分比的特征后，也會獲得比執行其他三種方法好的性能.以子圖(h)為例，從PC2數據集中選取40%的特征后的預測模型的預測性能與相關系數方法、信息增益率方法、ReliefF方法相比，分別提高了7.78%，6.08%和4.98%.

基于上述分析，基于排序集成的特征選擇方法能有效避免單一特征選擇方法錯誤地選擇特征子集，而帶來的預測模型性能低的情況，也避免了選擇特征選擇方法的盲目性.

6 結束語

本文提出一種基于排序集成的特征選擇方法，集成了相關系數方法、信息增益率方法、ReliefF方法，能避免單一特征選擇方法的不穩定性.由于綜合了三種方法，執行基于排序集成的特征選擇方法后選出的特征子集更準確，避免了單一特征選擇方法錯誤選擇特征子集，而帶來的預測模型性能低的情況，能消除某一或幾種特征選擇方法的不穩定性.

實驗中觀察到有些情況下采用基于排序集成的特征選擇方法的預測性能不會得到較大的提升，因為相關系數方法、信息增益率方法、ReliefF方法都只考慮特征與類別的相關性，而沒有考慮冗余特征，基于排序集成的特征選擇方法是三種方法的結合，也不會考慮特征冗余，假如一個數據集的特征之間具有很強的關聯性，那么從中選擇最優的特征子集時就很難考慮到特征冗余問題.如何加入去除冗余特征的方法是未來值得研究的內容.