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

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

軟件缺陷預(yù)測(cè)［1］能夠保證軟件質(zhì)量及其可靠性，現(xiàn)已成為軟件工程領(lǐng)域的研究熱點(diǎn)。軟件缺陷預(yù)測(cè)主要通過對(duì)軟件開發(fā)過程中的代碼進(jìn)行分析，構(gòu)建準(zhǔn)確的預(yù)測(cè)模型，并用于發(fā)現(xiàn)軟件中潛在的缺陷。其預(yù)測(cè)結(jié)果可為測(cè)試人員進(jìn)行有針對(duì)性的軟件測(cè)試和維護(hù)。

一般情況下，在軟件缺陷預(yù)測(cè)數(shù)據(jù)集中，無(wú)缺陷程序模塊的數(shù)量要遠(yuǎn)超過有缺陷程序模塊的數(shù)量，且80%的缺陷集中分布于20%的程序模塊內(nèi)，即軟件缺陷預(yù)測(cè)訓(xùn)練數(shù)據(jù)集中普遍存在類不平衡問題［2］。所謂類不平衡問題，即數(shù)據(jù)集的某一類樣例高于另一類，從而導(dǎo)致以整體錯(cuò)分率最小化為訓(xùn)練目標(biāo)的分類算法失效的問題。該問題的產(chǎn)生會(huì)影響軟件缺陷預(yù)測(cè)的結(jié)果，尤其是對(duì)少數(shù)類的預(yù)測(cè)精度降低。

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

由于軟件缺陷數(shù)據(jù)集的不斷增長(zhǎng)，開發(fā)人員急需一種時(shí)間開銷小，預(yù)測(cè)性能高的預(yù)測(cè)模型。極限學(xué)習(xí)機(jī)（Extreme Learning Machine，ELM）［6］具有泛化能力強(qiáng)、訓(xùn)練速度快的優(yōu)點(diǎn)［7～8］，但其也存在缺點(diǎn)，即當(dāng)數(shù)據(jù)分布極為不平衡，分類性能往往大幅下降。Zong等［9］借鑒代價(jià)敏感學(xué)習(xí)［10］的思想，提出了一種加權(quán)極限學(xué)習(xí)機(jī)（Weighted Extreme Learning Machine，WELM）算法，有效降低了少數(shù)類被錯(cuò)分的概率。

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

2 基礎(chǔ)理論

2.1 極限學(xué)習(xí)機(jī)

2006年，Huang等［6］針對(duì)單隱層前饋神經(jīng)網(wǎng)絡(luò)的訓(xùn)練問題，提出了極限學(xué)習(xí)機(jī)的理論與算法。極限學(xué)習(xí)機(jī)不需要對(duì)網(wǎng)絡(luò)的權(quán)重和偏置進(jìn)行迭代調(diào)整，而是通過隨機(jī)指定隱藏層參數(shù)，利用最小二乘法產(chǎn)生唯一的最優(yōu)解，因而極大地提升了訓(xùn)練速度，同時(shí)在一定程度上降低了陷入過擬合的概率。

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

其中，ai和bi分別表示第i個(gè)隱層節(jié)點(diǎn)的權(quán)重與偏置；βi表示第i個(gè)隱層節(jié)點(diǎn)的輸出權(quán)重；G表示激活函數(shù)。則式（1）可進(jìn)一步簡(jiǎn)化為下式：

2012年，Huang等［15］對(duì)ELM進(jìn)行了改進(jìn)，增加了懲罰因子C來調(diào)節(jié)算法的泛化性和準(zhǔn)確度，改進(jìn)后的優(yōu)化式如下：

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

2.2 加權(quán)極限學(xué)習(xí)機(jī)

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

根據(jù)KKT定理，得到關(guān)于β的解：

3 本文方法

3.1 相對(duì)密度的計(jì)算

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

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

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

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

3.2 隸屬函數(shù)的設(shè)計(jì)

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

1）正常樣本：該類樣本出現(xiàn)在自身類樣本的高密度區(qū)域，其他類樣本的低密度區(qū)域。

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

3）噪聲樣本：該類樣本出現(xiàn)在自身類樣本的低密度區(qū)域，其他類樣本的高密度區(qū)域。

4）離群樣本：該類樣本出現(xiàn)在兩類樣本的低密度區(qū)域。

圖1 四種不同樣本示例圖

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

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

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

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

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

3.3 基于相對(duì)密度的模糊加權(quán)極限學(xué)習(xí)機(jī)

上述過程給出了類間相對(duì)密度及隸屬函數(shù)的求解過程，為了提升加權(quán)極限學(xué)習(xí)機(jī)的預(yù)測(cè)性能，將隸屬函數(shù)值作為每個(gè)訓(xùn)練樣本的權(quán)值，轉(zhuǎn)換成對(duì)角陣，并將其替換WELM中的Wii對(duì)角陣，完成相對(duì)密度方法和加權(quán)極限學(xué)習(xí)機(jī)的結(jié)合，即基于相對(duì)密度的模糊加權(quán)極限學(xué)習(xí)機(jī)算法（FWELM-RD）。下面給出該算法步驟：

步驟1將Θ分成兩個(gè)數(shù)據(jù)集，Θ+只包含正類樣本，Θ-只包含負(fù)類樣本；

步驟2計(jì)算Θ+和Θ-的樣本數(shù)，并分別記為 N+和N-，且 N++N-=N ；

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

步驟4分別計(jì)算正負(fù)類樣本的參數(shù)K，記為K+=

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

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

步驟7對(duì)于每個(gè)樣本xi，通過式（12）計(jì)算其隸屬函數(shù)值Si；

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

步驟9用懲罰因子C，隱藏層神經(jīng)元數(shù)L訓(xùn)練WELM，獲得新的權(quán)值矩陣Wii′。

4 實(shí)驗(yàn)分析

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

圖2 方法框架

為了驗(yàn)證所提方法，本文從PROMISE數(shù)據(jù)庫(kù)中選取了10個(gè)NASA軟件缺陷預(yù)測(cè)數(shù)據(jù)集［18］，并與傳統(tǒng)的軟件缺陷預(yù)測(cè)方法進(jìn)行實(shí)驗(yàn)分析對(duì)比。

4.1 數(shù)據(jù)集與參數(shù)設(shè)置

本 文 的 實(shí) 驗(yàn) 環(huán) 境 為 Intel（R）Core（TM）i5-3230M，CPU主頻2.6 GHz，內(nèi)存8 GB；操作系統(tǒng)為Windows 10；編程環(huán)境為Matlab2014a。

實(shí)驗(yàn)所用數(shù)據(jù)集為美國(guó)國(guó)家航空航天局（NASA）發(fā)布的專門用于構(gòu)建軟件缺陷預(yù)測(cè)模型的公開數(shù)據(jù)集，度量屬性包括Halstead屬性、McCabe屬性、代碼行數(shù)等屬性。所用數(shù)據(jù)集的基本信息如表1所示，其中數(shù)據(jù)集按缺陷率排序。

表1 實(shí)驗(yàn)數(shù)據(jù)的基本信息

本文將與具有代表性的DNC（Dynamic Ada-Boost.NC）集成學(xué)習(xí)方法［19］進(jìn)行對(duì)比驗(yàn)證。同時(shí)，為了驗(yàn)證基準(zhǔn)方法ELM的有效性，本文還與ELM［6］、ELM-RUS［5］、ELM-ROS［20］、ELM-SMOTE［21］、

WELM1［9］和 WELM2［9］算法進(jìn)行比較，以上方法可根據(jù)前人文獻(xiàn)所提供代碼流程實(shí)現(xiàn)，并同樣采取10折交叉驗(yàn)證方法保證結(jié)果一致性。

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

4.2 評(píng)估標(biāo)準(zhǔn)

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

其中TP指被model預(yù)測(cè)為正的正樣本，TN指被model預(yù)測(cè)為負(fù)的負(fù)樣本，F(xiàn)P指被model模型預(yù)測(cè)為正的負(fù)樣本，F(xiàn)N指被模型預(yù)測(cè)為負(fù)的正樣本。

AUC（Area Under Roc Curve）是評(píng)估模型準(zhǔn)確率的一種方法，可通過對(duì)ROC曲線下各部分的面積求和而得。模型的準(zhǔn)確率越高，面積越接近1。隨機(jī)預(yù)測(cè)的面積為0.5，而完美模型的面積為1。AUC值越大，則預(yù)測(cè)模型的性能越好。

考慮到點(diǎn)（PF=0，PD=1）是ROC曲線中最理想的點(diǎn)，在（0，1）點(diǎn)所有的錯(cuò)誤都能被正確識(shí)別出，所以軟件工程師經(jīng)常在實(shí)踐中用到一種權(quán)衡PD和PF的綜合指標(biāo)Balance，該指標(biāo)計(jì)算真實(shí)的（PF，PD）點(diǎn)到（0，1）的歐式距離，其定義如下：

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

4.3 實(shí)驗(yàn)結(jié)果與討論

表3～5分別列出了由8種方法構(gòu)造的軟件缺陷預(yù)測(cè)模型在10個(gè)NASA數(shù)據(jù)集上的3種指標(biāo)（G-mean、AUC和Balance）的平均值。

表2 混淆矩陣

表3 各類算法的G-mean測(cè)度比較

表4 各類算法的AUC測(cè)度比較

根據(jù)表3的G-mean描述，本文所提算法較其他基于ELM的類不平衡學(xué)習(xí)算法及兩種WELM算法都有很大的提高，同時(shí)也大部分優(yōu)于基于集成學(xué)習(xí)的DNC方法。由表4的AUC結(jié)果得知，本文所提算法與其他方法相比皆有相當(dāng)性能。針對(duì)軟件工程師常用的Balance指標(biāo)，根據(jù)表5的結(jié)果可知，本文所提FWELM-RD方法在大部分?jǐn)?shù)據(jù)集有著較優(yōu)的性能。

此外，本文對(duì)各個(gè)算法的性能進(jìn)行了統(tǒng)計(jì)分析。Friedman檢驗(yàn)［22］是利用秩序?qū)崿F(xiàn)對(duì)多個(gè)總體分布是否存在顯著差異的非參數(shù)檢驗(yàn)方法，其原假設(shè)是：來自多個(gè)配對(duì)樣本的多個(gè)總體分布無(wú)顯著差異。通過計(jì)算Friedman統(tǒng)計(jì)量和對(duì)應(yīng)的概率P（adjusted p-value，APV）值，來判斷其是否拒絕原假設(shè)。若APV值小于給定的顯著性水平α，則拒絕原假設(shè)，認(rèn)為各組樣本的秩存在顯著差異，來自多個(gè)配對(duì)樣本的多個(gè)總體的分布有顯著差異；反之，則不能拒絕原假設(shè)，可認(rèn)為各組樣本的秩不存在顯著性差異。

本文用Friedman檢驗(yàn)來對(duì)各算法在所有數(shù)據(jù)集上的性能按G-mean、AUC和Balance分別計(jì)算它們的秩及APV值，其中，顯著性水平α設(shè)為0.05。統(tǒng)計(jì)分析結(jié)果如表6所示。其中，G-mean、AUC和Balance性能指標(biāo)的平均秩和APV值分別用rankingG 、rankingA、rankingB和APVG、APVA、APVB表示。

表6 不同算法的統(tǒng)計(jì)結(jié)果

算法性能最好的ranking值最小，排序?yàn)?，算法性能其次的ranking值第二小，排序?yàn)?，并以此類推。從表6可以看出，F(xiàn)WELM-RD算法在三項(xiàng)指標(biāo)里的ranking值均最小，即排名均為1，這表明該算法在所有算法中具有最好的預(yù)測(cè)性能。

5 結(jié)語(yǔ)

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

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

1）對(duì)于相對(duì)密度計(jì)算方法中涉及的參數(shù)K的選取，若選取其他更多值，結(jié)果是否有影響，還需進(jìn)一步實(shí)驗(yàn)驗(yàn)證；

2）對(duì)更多的算法進(jìn)行實(shí)驗(yàn)比較，更進(jìn)一步來驗(yàn)證本文算法的有效性；

3）選取更多的軟件缺陷數(shù)據(jù)進(jìn)行驗(yàn)證所提算法。