基于相對密度的類不平衡軟件缺陷預測*

孫 丹 于化龍 鄭 尚 鄒海濤 王 琦

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

軟件缺陷預測［1］能夠保證軟件質量及其可靠性，現已成為軟件工程領域的研究熱點。軟件缺陷預測主要通過對軟件開發過程中的代碼進行分析，構建準確的預測模型，并用于發現軟件中潛在的缺陷。其預測結果可為測試人員進行有針對性的軟件測試和維護。

一般情況下，在軟件缺陷預測數據集中，無缺陷程序模塊的數量要遠超過有缺陷程序模塊的數量，且80%的缺陷集中分布于20%的程序模塊內，即軟件缺陷預測訓練數據集中普遍存在類不平衡問題［2］。所謂類不平衡問題，即數據集的某一類樣例高于另一類，從而導致以整體錯分率最小化為訓練目標的分類算法失效的問題。該問題的產生會影響軟件缺陷預測的結果，尤其是對少數類的預測精度降低。

目前，類不平衡問題的解決方法［3］可分為兩類：一類是從調整數據集中的類分布角度出發，即采樣法，包括過采樣和欠采樣，這類方法分別通過增加少數類樣本和減少多數類樣本得到分類相對平衡的新數據集［4］。另一類則從修改學習算法角度出發［·5］，通過修改算法的訓練過程，使得學習算法可以針對少數類有更好的預測精度。

由于軟件缺陷數據集的不斷增長，開發人員急需一種時間開銷小，預測性能高的預測模型。極限學習機（Extreme Learning Machine，ELM）［6］具有泛化能力強、訓練速度快的優點［7～8］，但其也存在缺點，即當數據分布極為不平衡，分類性能往往大幅下降。Zong等［9］借鑒代價敏感學習［10］的思想，提出了一種加權極限學習機（Weighted Extreme Learning Machine，WELM）算法，有效降低了少數類被錯分的概率。

盡管WELM算法能在一定程度上提升ELM在類不平衡數據上的分類性能，但僅根據類不平衡比率為每類樣本分配一個統一的權重，并沒有考慮樣例在特征空間中的具體分布情況。因此，為了解決上述問題，本文提出了一種基于相對密度方法的模糊加權極限學習機-FWELM-RD算法，該方法通過K近鄰概率密度估計法-KNN-PDE［11］來計算各訓練樣本間的類間相對密度，即通過精確計算任意不同類訓練樣本之間的概率密度比例關系來避免概率密度的測量。相對密度與數據在特征空間中的分布比無關，具有較強的魯棒性。并引入模糊集的概念，設計相應隸屬函數，從而提出用于類不平衡軟件缺陷預測的模糊加權學習機算法。通過在軟件缺陷數據集上的實驗驗證，該方法和傳統的處理軟件缺陷類不平衡問題方法相比，具有更好的預測性能，并且在 G-mean［12］、AUC［13］和 Balance［14］等評價指標上有較好表現。

2 基礎理論

2.1 極限學習機

2006年，Huang等［6］針對單隱層前饋神經網絡的訓練問題，提出了極限學習機的理論與算法。極限學習機不需要對網絡的權重和偏置進行迭代調整，而是通過隨機指定隱藏層參數，利用最小二乘法產生唯一的最優解，因而極大地提升了訓練速度，同時在一定程度上降低了陷入過擬合的概率。

假設訓練樣本集包括N個訓練樣本，將其表示為（xi，ti）∈Rn×Rm，其中，xi表示n×1維的輸入向量，ti表示第i個訓練樣本的期望輸出向量，在分類問題中，n代表訓練樣本的屬性數，m代表樣本的類別數。若一個具有L個隱層節點的單隱層前饋神經網絡能以零誤差擬合上述N個訓練樣本，則意味著存在 βi，ai及bi，使得下式成立：

其中，ai和bi分別表示第i個隱層節點的權重與偏置；βi表示第i個隱層節點的輸出權重；G表示激活函數。則式（1）可進一步簡化為下式：

2012年，Huang等［15］對ELM進行了改進，增加了懲罰因子C來調節算法的泛化性和準確度，改進后的優化式如下：

其中，εi表示第i個訓練樣本的實際輸出與期望輸出之差，h(xi)為第i個樣例xi在隱層的輸出向量，C為懲罰因子，用于調控網絡的泛化性與精確性間的平衡，根據 Karush-Kuhn-Tucker（KTT）理論［16］，上述優化式（3）可通過下式求得：

2.2 加權極限學習機

ELM在處理軟件缺陷類不平衡問題時，也面臨著和傳統分類器同樣的問題，即分類性能大幅度下降，大量的少數類被誤分為多數類。針對這種問題，Zong等［9］提出了WELM算法，該算法在式（3）的基礎上增加了一個加權矩陣，以此為不同類樣本賦予不同的權值，從而更好地反映出不同樣本在不同類中的重要性，獲得比ELM更好的泛化性能。其中，W為一個N×N的對角陣，它為各類樣本分配權值；Wii為第i個訓練樣例的權值。Zong等提供了如下兩種權值分配方法：

根據KKT定理，得到關于β的解：

3 本文方法

3.1 相對密度的計算

加權極限學習機的權值矩陣并不具有對軟件缺陷數據樣本信息的判別能力，即對同一類別中的噪聲樣本和非噪聲樣本所分配的權值是一樣的。因此，為了解決上述問題，得到分類性能更好的WELM算法，本文結合相對密度，引入模糊集并設計隸屬函數，提出基于相對密度的模糊加權極限學習機算法。

首先，若能精確地測出每一個訓練樣本的概率密度，從噪聲點和離群點中區分出具有重要信息的樣本則變得比較容易。但是，在高維特征空間中，獲得精確的概率密度是極為困難的，要獲取相對精確的概率密度也是十分耗時的。因此，本文采用了一種避免概率密度測量的方法，即精確計算任意兩個訓練樣本之間的概率密度的比例關系。這種反映比例關系的信息稱之為相對密度。為了獲取這種相對密度，本文采用類KNN-PDE方法［11］。作為一種無參概率密度估計法，KNN-PDE通過計算每個訓練樣本的K近鄰距離來評估多維特征空間的概率密度分布。當訓練樣本的數目無窮大時，KNN-PDE方法所獲得的結果更接近于真實的概率密度分布。

假設一個數據集有N個樣本，對于每個樣例xi，找到它的K個最近的樣本并計算它們之間的距離。眾所周知，越大，樣本xi的密度就越高。同樣地，對于那些出現在低密度區域的噪聲點和離群點，也可用來衡量每個樣本的重要程度。但是，為了分別增加和降低高密度樣本和低密度樣本（即噪聲和離群點）的影響，一般取的倒數，并將樣本的K近鄰距離的倒數稱之為相對密度。不難看出，任意兩個樣本之間的相對密度和它們之間K近鄰距離的比例關系成反比，即：

若K值太小，則很難將噪聲點和離群點從普通樣本中區分出來；若K值太大，則那些重要樣本與噪聲點或離群點之間的區別便會變得模糊不清而這些微小的差距將更難獲取。

3.2 隸屬函數的設計

對于一個模糊加權算法而言，影響其性能的最關鍵因素即是隸屬函數設計的合理性，故針對類不平衡問題，本文在相對密度概念的基礎上，設計了一種隸屬函數［17］，該函數采用類間密度信息來計算。在該方法中，定義該隸屬函數為，該函數和預估類邊界相關，即接近預估類邊界的樣本會被賦予一個較大的值。為了更準確地估量類邊界，本文深入研究了關于不同密度分布的四種樣本的特征。這些樣本被分為四種類型，分別為正常樣本、邊界樣本、噪聲樣本和離群樣本。圖3展示了這些樣本直觀描述。這四種樣本的特征總結如下。

1）正常樣本：該類樣本出現在自身類樣本的高密度區域，其他類樣本的低密度區域。

2）邊界樣本：該類樣本出現在兩類樣本的低密度或中間密度區域，但相比其他類樣本，其在自身類樣本密度要高一些。

3）噪聲樣本：該類樣本出現在自身類樣本的低密度區域，其他類樣本的高密度區域。

4）離群樣本：該類樣本出現在兩類樣本的低密度區域。

圖1 四種不同樣本示例圖

根據上述描述，我們可以準確地確定邊界。首先，對于每個樣本，可以通過比較其類內和類間的相對密度來尋找噪聲樣本，且可以根據一個判別式來尋找。若樣本是正類樣本，則它的判別式如下：

其中，d′表示該類和另類的距離計算而得，N+和N-分別為正類和負類樣本的個數。為為聚集操作，IR為類不平衡比率N-N+。若樣本xi是負類樣本，則它的判別式如下：

對于每個滿足判別式（10）和式（11）的樣本，將被作為噪聲樣本去除，并給它們賦予一個很小的函數值l。

對于剩下的樣本，根據類間相對密度對其分配函數值。模糊隸屬函數值可用分段函數表示：

其中，為Nc1和Nc2分別表示在同一類下的xi屬于非噪聲樣本和噪聲樣本的數目，且有Nc1+Nc2=Nc。

3.3 基于相對密度的模糊加權極限學習機

上述過程給出了類間相對密度及隸屬函數的求解過程，為了提升加權極限學習機的預測性能，將隸屬函數值作為每個訓練樣本的權值，轉換成對角陣，并將其替換WELM中的Wii對角陣，完成相對密度方法和加權極限學習機的結合，即基于相對密度的模糊加權極限學習機算法（FWELM-RD）。下面給出該算法步驟：

步驟1將Θ分成兩個數據集，Θ+只包含正類樣本，Θ-只包含負類樣本；

步驟2計算Θ+和Θ-的樣本數，并分別記為 N+和N-，且 N++N-=N ；

步驟3計算類不平衡比率IR=NN+；

步驟4分別計算正負類樣本的參數K，記為K+=

步驟5對于Θ+里的每個樣本xi+，計算它在Θ+里的K+近鄰距離及在Θ-里的K-近鄰距離，在分別并記為di+和di-，同樣地，對于Θ-里的每個樣本xi-，計算它在Θ-里的K-近鄰距離及它在Θ+里的K+近鄰距離，并分別記為dj-和dj+；

步驟6計算每個樣本的相對密度并分別通過式（10）和式（11）找出兩種不同類內的噪聲樣本；

步驟7對于每個樣本xi，通過式（12）計算其隸屬函數值Si；

步驟8將隸屬函數值 f()xi嵌入到WELM的加權矩陣Wii中；

步驟9用懲罰因子C，隱藏層神經元數L訓練WELM，獲得新的權值矩陣Wii′。

4 實驗分析

本文在極限學習機的基礎之上，提出類不平衡軟件缺陷預測算法，從而得到分類精度更高、泛化能力更好的模型。所提模型將采用10折交叉驗證，即每次將數據集分成10份，輪流將其中9份作為訓練集并建立模型，1份作為測試集進行驗證，整個過程將重復100次，最后取其結果的均值作為各種指標值，整個方法框架如圖1所示。

圖2 方法框架

為了驗證所提方法，本文從PROMISE數據庫中選取了10個NASA軟件缺陷預測數據集［18］，并與傳統的軟件缺陷預測方法進行實驗分析對比。

4.1 數據集與參數設置

本 文 的 實 驗 環 境 為 Intel（R）Core（TM）i5-3230M，CPU主頻2.6 GHz，內存8 GB；操作系統為Windows 10；編程環境為Matlab2014a。

實驗所用數據集為美國國家航空航天局（NASA）發布的專門用于構建軟件缺陷預測模型的公開數據集，度量屬性包括Halstead屬性、McCabe屬性、代碼行數等屬性。所用數據集的基本信息如表1所示，其中數據集按缺陷率排序。

表1 實驗數據的基本信息

本文將與具有代表性的DNC（Dynamic Ada-Boost.NC）集成學習方法［19］進行對比驗證。同時，為了驗證基準方法ELM的有效性，本文還與ELM［6］、ELM-RUS［5］、ELM-ROS［20］、ELM-SMOTE［21］、

WELM1［9］和 WELM2［9］算法進行比較，以上方法可根據前人文獻所提供代碼流程實現，并同樣采取10折交叉驗證方法保證結果一致性。

在實驗中，本文對所有ELM算法設置了統一參數，以此來保證實驗對比結果的公正性，即對于ELM中的隱藏層節點數L和懲罰因子C，均給定了相同的取值范圍，其中，L∈{ }10，20，…，300 ，C∈｛2-4，2-2，…，220｝，實驗中采用了Grid Search策略得到了最優的參數組合—L為100，C為212。

4.2 評估標準

考慮到軟件缺陷預測數據集的類不平衡分布問題以及軟件系統的不同需求性，本文采用了多個評估標準來衡量預測模型的性能。所用評價指標常用的G-mean［12］指標外，還采用了AUC值和Balance值作為評價指標。在人工智能中，混淆矩陣是表示精度評價的一種標準格式，用n行n列的矩陣形式來表示。本文所用混淆矩陣如表2所示，并定義預測率（Probability of Detection，PD）定義為PD=TP/（TP+FN）；誤報率（Probability of False Alarm，PF）定義為PF=FP/（FP+TN）。有G-mean定義為

其中TP指被model預測為正的正樣本，TN指被model預測為負的負樣本，FP指被model模型預測為正的負樣本，FN指被模型預測為負的正樣本。

AUC（Area Under Roc Curve）是評估模型準確率的一種方法，可通過對ROC曲線下各部分的面積求和而得。模型的準確率越高，面積越接近1。隨機預測的面積為0.5，而完美模型的面積為1。AUC值越大，則預測模型的性能越好。

考慮到點（PF=0，PD=1）是ROC曲線中最理想的點，在（0，1）點所有的錯誤都能被正確識別出，所以軟件工程師經常在實踐中用到一種權衡PD和PF的綜合指標Balance，該指標計算真實的（PF，PD）點到（0，1）的歐式距離，其定義如下：

由上式可知，Balance值越大，表示（PF，PD）點與（0，1）之間的距離越近，分類性能越好，反之則越差。

4.3 實驗結果與討論

表3～5分別列出了由8種方法構造的軟件缺陷預測模型在10個NASA數據集上的3種指標（G-mean、AUC和Balance）的平均值。

表2 混淆矩陣

表3 各類算法的G-mean測度比較

表4 各類算法的AUC測度比較

根據表3的G-mean描述，本文所提算法較其他基于ELM的類不平衡學習算法及兩種WELM算法都有很大的提高，同時也大部分優于基于集成學習的DNC方法。由表4的AUC結果得知，本文所提算法與其他方法相比皆有相當性能。針對軟件工程師常用的Balance指標，根據表5的結果可知，本文所提FWELM-RD方法在大部分數據集有著較優的性能。

此外，本文對各個算法的性能進行了統計分析。Friedman檢驗［22］是利用秩序實現對多個總體分布是否存在顯著差異的非參數檢驗方法，其原假設是：來自多個配對樣本的多個總體分布無顯著差異。通過計算Friedman統計量和對應的概率P（adjusted p-value，APV）值，來判斷其是否拒絕原假設。若APV值小于給定的顯著性水平α，則拒絕原假設，認為各組樣本的秩存在顯著差異，來自多個配對樣本的多個總體的分布有顯著差異；反之，則不能拒絕原假設，可認為各組樣本的秩不存在顯著性差異。

本文用Friedman檢驗來對各算法在所有數據集上的性能按G-mean、AUC和Balance分別計算它們的秩及APV值，其中，顯著性水平α設為0.05。統計分析結果如表6所示。其中，G-mean、AUC和Balance性能指標的平均秩和APV值分別用rankingG 、rankingA、rankingB和APVG、APVA、APVB表示。

表6 不同算法的統計結果

算法性能最好的ranking值最小，排序為1，算法性能其次的ranking值第二小，排序為2，并以此類推。從表6可以看出，FWELM-RD算法在三項指標里的ranking值均最小，即排名均為1，這表明該算法在所有算法中具有最好的預測性能。

5 結語

本文以軟件缺陷預測為背景，針對類不平衡對預測模型的性能產生的影響，提出了一種基于相對密度的模糊加權極限學習機算法。該算法在原有加權極限學習機算法的基礎上，引入模糊集的思想，通過隸屬函數的設計，對每個樣本的權重進行模糊化與個性化的設置，從而緩解類不平衡對軟件缺陷預測性能的影響，以達到提高預測模型性能的目的。選取了公開的NASA數據集進行實驗。結果表明，所提算法構造的預測模型具有更好的預測性能，從而幫助軟件缺陷預測工作更好地進行。

此外，在下一步的研究工作中，希望在以下方面進行拓展：

1）對于相對密度計算方法中涉及的參數K的選取，若選取其他更多值，結果是否有影響，還需進一步實驗驗證；

2）對更多的算法進行實驗比較，更進一步來驗證本文算法的有效性；

3）選取更多的軟件缺陷數據進行驗證所提算法。