黃 琳，荊曉遠(yuǎn)，董西偉

(南京郵電大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210003)

0 引 言

軟件缺陷的產(chǎn)生往往是由于開(kāi)發(fā)人員需求理解不正確或是經(jīng)驗(yàn)不足。而含有缺陷的軟件在運(yùn)行時(shí)可能會(huì)產(chǎn)生意料之外的結(jié)果，嚴(yán)重的時(shí)候會(huì)給企業(yè)造成巨大的經(jīng)濟(jì)損失，甚至?xí){到人們的生命安全。軟件缺陷預(yù)測(cè)(software defect prediction，SDP)是軟件工程中最重要的研究課題之一[1]，吸引了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注?；诙攘康撵o態(tài)軟件缺陷預(yù)測(cè)技術(shù)借助于從已有的軟件模塊中獲得歷史數(shù)據(jù)，對(duì)新的軟件模塊進(jìn)行缺陷預(yù)測(cè)，來(lái)判斷它們是否存在缺陷，從而為軟件項(xiàng)目提供決策支持[2-4]。近年來(lái)，支持向量機(jī)(support vector machine，SVM)[5]、決策樹(shù)[6]、樸素貝葉斯[7-8]、代價(jià)敏感學(xué)習(xí)[9]和集成學(xué)習(xí)[10-11]這些機(jī)器學(xué)習(xí)技術(shù)已經(jīng)被廣泛地用于軟件缺陷預(yù)測(cè)領(lǐng)域。最近，字典學(xué)習(xí)[12]、稀疏表示[13]等方法也被引入了軟件缺陷預(yù)測(cè)中。軟件缺陷預(yù)測(cè)的歷史數(shù)據(jù)具有樣本不足、結(jié)構(gòu)復(fù)雜和類(lèi)別分布不平衡的特點(diǎn)。為了解決這些問(wèn)題，文中提出一種基于多核集成學(xué)習(xí)的跨項(xiàng)目軟件缺陷預(yù)測(cè)算法(cross-project software defect prediction based on multiple kernel ensemble learning，CMKEL)。

1 相關(guān)工作

1.1 跨項(xiàng)目缺陷預(yù)測(cè)

軟件缺陷預(yù)測(cè)是當(dāng)前大數(shù)據(jù)技術(shù)在軟件工程領(lǐng)域的重點(diǎn)研究方向之一[14]。在早期大多數(shù)的研究都是使用項(xiàng)目?jī)?nèi)已經(jīng)標(biāo)記的程序模塊，一部分樣本來(lái)構(gòu)建預(yù)測(cè)模型，另一部分樣本作為預(yù)測(cè)。然而在實(shí)際應(yīng)用中項(xiàng)目?jī)?nèi)的歷史數(shù)據(jù)是有限的。由于歷史數(shù)據(jù)的缺少，研究者們開(kāi)始關(guān)注跨項(xiàng)目軟件缺陷預(yù)測(cè)的問(wèn)題，跨項(xiàng)目就是使用其他項(xiàng)目的訓(xùn)練數(shù)據(jù)來(lái)構(gòu)建預(yù)測(cè)模型,并對(duì)一個(gè)全新項(xiàng)目進(jìn)行缺陷預(yù)測(cè)。

1.2 多核學(xué)習(xí)技術(shù)

多核學(xué)習(xí)就是將不同特性的核函數(shù)進(jìn)行組合，獲得多類(lèi)核函數(shù)的優(yōu)點(diǎn)，來(lái)達(dá)到更優(yōu)的映射性能。和傳統(tǒng)的單核方法相比，多核學(xué)習(xí)不僅能夠組合利用各基本的單核函數(shù)的特征映射的能力，而且還能將不同特性的核函數(shù)進(jìn)行組合，來(lái)獲得多類(lèi)單核數(shù)的優(yōu)點(diǎn)，從而得到更優(yōu)的映射能力，提高預(yù)測(cè)的精度。

1.3 集成學(xué)習(xí)技術(shù)

集成學(xué)習(xí)就是用多個(gè)弱分類(lèi)器結(jié)合為一個(gè)強(qiáng)分類(lèi)器,從而提升分類(lèi)方法的效果。集成學(xué)習(xí)能夠得到比基分類(lèi)器更好的分類(lèi)效果和泛化能力,不容易出現(xiàn)過(guò)擬合情況,因此適用于跨項(xiàng)目缺陷預(yù)測(cè)問(wèn)題。

2 基于多核集成學(xué)習(xí)的跨項(xiàng)目軟件缺陷預(yù)測(cè)

對(duì)于靜態(tài)軟件缺陷模塊存在的結(jié)構(gòu)復(fù)雜、類(lèi)別不平衡、歷史數(shù)據(jù)缺少的問(wèn)題，文中提出一種基于多核集成學(xué)習(xí)的跨項(xiàng)目軟件缺陷預(yù)測(cè)方法。

假設(shè)訓(xùn)練的軟件模塊D={(xi,yi),i=1,2,…,N},其中xi是模塊屬性的向量，yi∈{0,1}是模塊的標(biāo)簽，N是項(xiàng)目數(shù)。K={kj:X×X→R,j=1,2,…,M}是M個(gè)核函數(shù)的集合，其中X是輸入空間。CMKEL主要是學(xué)習(xí)基于多核的一個(gè)分類(lèi)器f(x),這個(gè)分類(lèi)器是通過(guò)有標(biāo)記的歷史數(shù)據(jù)進(jìn)行多核訓(xùn)練得到的，通過(guò)基于多核的分類(lèi)器f(x)來(lái)預(yù)測(cè)新的軟件模塊，基于多核分類(lèi)器表示為：

(1)

其中，T為整個(gè)boosting過(guò)程的次數(shù)；ft(x)為第t次(1≤t≤T)boosting過(guò)程得到的弱分類(lèi)器；αt為相應(yīng)的權(quán)重值。

該算法的關(guān)鍵點(diǎn)是每次在M個(gè)基于核函數(shù)的分類(lèi)器中進(jìn)行boosting過(guò)程后，學(xué)習(xí)得到一個(gè)錯(cuò)誤分類(lèi)誤差最小的ft(x)分類(lèi)器及其組合權(quán)重αt。經(jīng)過(guò)T次boosting過(guò)程之后，將這些分類(lèi)器按照權(quán)重值集成，得到最終的分類(lèi)器。

2.1 多核學(xué)習(xí)分類(lèi)器

(2)

多核學(xué)習(xí)的目標(biāo)是通過(guò)最優(yōu)化方法來(lái)求取合成核的參數(shù)，將上式轉(zhuǎn)化為如下的最優(yōu)化形式：

(3)

2.2 多核集成學(xué)習(xí)分類(lèi)器

為了學(xué)習(xí)一個(gè)多核集成的分類(lèi)器，文中采用一個(gè)典型且有效的boosting算法。具體而言，在初始化訓(xùn)練集之后通過(guò)一系列boosting過(guò)程，重復(fù)學(xué)習(xí)一些基于核的分類(lèi)器，然后根據(jù)它們的組合權(quán)重進(jìn)行集合，從而得到最終的CMKEL分類(lèi)器。在boosting過(guò)程之前，需要先對(duì)訓(xùn)練集進(jìn)行初始化。文中在整個(gè)訓(xùn)練集上直接執(zhí)行隨機(jī)抽樣策略，然后將這些選擇的樣本作為CMKEL初始訓(xùn)練集。

在訓(xùn)練集初始化完成之后，需要有對(duì)應(yīng)的Dt向量，Dt表示每個(gè)樣本在整個(gè)boosting過(guò)程的不同權(quán)重。最初，這些權(quán)重都是相同的。為了更加關(guān)注那些錯(cuò)誤分類(lèi)的樣本，在每一次boosting過(guò)程增加錯(cuò)誤分類(lèi)的權(quán)重或是減少正確分類(lèi)的權(quán)重,來(lái)調(diào)整權(quán)重向量Dt。一旦得到訓(xùn)練集和權(quán)重向量Dt，就可以進(jìn)行boosting過(guò)程。每次boosting過(guò)程的關(guān)鍵是要從M個(gè)基于核函數(shù)的分類(lèi)器中學(xué)習(xí)得到一個(gè)基于核假設(shè)的分類(lèi)器ft(x)。

樣本中無(wú)缺陷模塊的標(biāo)簽為0，有缺陷模塊的標(biāo)簽為1。軟件缺陷預(yù)測(cè)模型對(duì)有缺陷的模塊被預(yù)測(cè)為無(wú)缺陷時(shí)稱(chēng)為Ⅰ類(lèi)錯(cuò)誤，代價(jià)表示為cost(1,0)；反之Ⅱ類(lèi)錯(cuò)誤表示無(wú)缺陷模塊被預(yù)測(cè)為有缺陷的，代價(jià)表示為cost(0,1)，顯然Ⅰ類(lèi)錯(cuò)誤的代價(jià)敏感要遠(yuǎn)大于Ⅱ錯(cuò)誤代價(jià)敏感。文中定義的代價(jià)矩陣如表1所示。

表1 代價(jià)矩陣

在表1中，μ表示I類(lèi)錯(cuò)誤的代價(jià)敏感系數(shù)。

考慮到代價(jià)矩陣后的每個(gè)基于核分類(lèi)器的錯(cuò)誤分類(lèi)誤差的計(jì)算為：

(4)

其中，cost(l,g)為代價(jià)矩陣，cost(l,g)表示l類(lèi)被錯(cuò)分成g類(lèi)的代價(jià)。

最好的分類(lèi)器是得到最小的錯(cuò)誤分類(lèi)誤差，在第t次boosting過(guò)程之后得到的弱分類(lèi)器為：

(5)

在第t次的boosting過(guò)程中，ft(x)分類(lèi)器的權(quán)重αt和錯(cuò)誤分類(lèi)誤差的關(guān)系表達(dá)式為：

(6)

在得到權(quán)重αt之后，第t次的boosting過(guò)程完成。在下一次boosting開(kāi)始前，要根據(jù)第t次boosting過(guò)程的結(jié)果更新下一次boosting過(guò)程中的權(quán)重向量Dt+1。權(quán)重向量的更新原則是根據(jù)分類(lèi)結(jié)果進(jìn)行更新，通過(guò)提高錯(cuò)分樣本的權(quán)重，降低正確分類(lèi)樣本的權(quán)重。目的是在下一次boosting過(guò)程中將重點(diǎn)放在錯(cuò)誤分類(lèi)的樣本上，訓(xùn)練樣本集的權(quán)重向量更新表達(dá)式為：

(7)

其中，Zt是規(guī)范化因子。

根據(jù)分類(lèi)的結(jié)果，權(quán)重向量的更新策略詳細(xì)表示為：

(8)

其中，ft(xi)=yi表示被正確分類(lèi)；ft(xi)≠yi表示被錯(cuò)誤分類(lèi)。

經(jīng)過(guò)T次boosting過(guò)程后，最終的分類(lèi)器為：

(9)

綜上所述，CMKEL算法的描述如下：

輸入：訓(xùn)練集、核函數(shù)kj、初始權(quán)重分布D1=1/N。

(1)開(kāi)始第t=1～T次的boosting過(guò)程，權(quán)重向量表示每個(gè)訓(xùn)練樣本Dt的權(quán)重分布。

(2)對(duì)于j=1～M來(lái)訓(xùn)練對(duì)應(yīng)kj核函數(shù)的弱分類(lèi)器，根據(jù)式4計(jì)算在Dt下的錯(cuò)誤分類(lèi)誤差。

(3)訓(xùn)練完所有的基于核的分類(lèi)器之后，選擇最小錯(cuò)誤分類(lèi)的分類(lèi)器，由式5得到ft(x)。

(4)由式6計(jì)算αt。

(5)根據(jù)式8權(quán)重更新的策略，更新下一次boosting過(guò)程的權(quán)重向量分布。

(6)T次boosting過(guò)程之后，得到T組分類(lèi)器和與之對(duì)應(yīng)的權(quán)重。

輸出：最終分類(lèi)器G(x)。

3 實(shí) 驗(yàn)

為驗(yàn)證CMKEL算法的預(yù)測(cè)效果，將該算法與加權(quán)樸素貝葉斯(weighted Na?ve Bayes，NB)算法[7]、壓縮的C4.5決策樹(shù)(compressed C4.5 decision tree，CC4.5)算法[15]和代價(jià)敏感的Boosting神經(jīng)網(wǎng)絡(luò)(cost-sensitive boosting neural network，CBNN)算法[16]在NASA、AEEEM數(shù)據(jù)庫(kù)中進(jìn)行對(duì)比驗(yàn)證。

3.1 實(shí)驗(yàn)數(shù)據(jù)庫(kù)

NASA、AEEEM數(shù)據(jù)庫(kù)的工程數(shù)都是五個(gè)，它們各個(gè)工程的靜態(tài)代碼度量和缺陷占比如表2所示。

3.2 實(shí)驗(yàn)指標(biāo)

預(yù)測(cè)模型的評(píng)估指標(biāo)有召回率(pd)、誤報(bào)率(pf)、查準(zhǔn)率(precision)和精確度(acc)。

表2 數(shù)據(jù)集的詳細(xì)信息

文中主要采用兩個(gè)綜合性能指標(biāo)：F-measure，就是將pd與precision結(jié)合起來(lái)評(píng)價(jià)；AUC值(area under curve)被定義為ROC曲線下的面積，使用AUC值可以評(píng)估二分類(lèi)問(wèn)題分類(lèi)效果的優(yōu)劣。F-measure和AUC的數(shù)值越大，表示軟件缺陷預(yù)測(cè)模型的預(yù)測(cè)性能越好。

3.3 實(shí)驗(yàn)設(shè)置

在多核學(xué)習(xí)的訓(xùn)練中，選擇具有20個(gè)不同寬度(2-10,2-9,…,29)的高斯核函數(shù)，然后使用這20個(gè)基核分別將NASA和AEEEM里面的每一個(gè)工程映射到一個(gè)新的特征空間。對(duì)于弱分類(lèi)器SVM，結(jié)合每個(gè)核函數(shù)訓(xùn)練得到一個(gè)基于核的分類(lèi)器，整個(gè)過(guò)程采用流行的LISVM工具箱作為SVM求解器。為了驗(yàn)證代價(jià)敏感系數(shù)對(duì)模型是否有影響，設(shè)置μ=1,5,10,15,20，觀察代價(jià)敏感系數(shù)不同時(shí)對(duì)實(shí)驗(yàn)的影響。Boosting過(guò)程的初始設(shè)計(jì)如下：在同一個(gè)數(shù)據(jù)庫(kù)下，隨機(jī)選擇一個(gè)工程作為訓(xùn)練樣本，另一個(gè)工程作為測(cè)試樣本，每組算法迭代20次，最后將20次跑出來(lái)的數(shù)據(jù)取平均。Boosting的過(guò)程和文獻(xiàn)[17]中一致，訓(xùn)練次數(shù)T為100。

3.4 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證在CMKEL算法中代價(jià)敏感系數(shù)的大小對(duì)實(shí)驗(yàn)結(jié)果的影響，設(shè)置了不同的μ值，在AEEEM數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果如表3所示。其中μ=1表示沒(méi)有引入代價(jià)敏感系數(shù)。

表3 不同代價(jià)敏感系數(shù)下的AUC值

從表3中的實(shí)驗(yàn)結(jié)果可以看出：當(dāng)μ>1時(shí)，AUC值要比μ=1高，說(shuō)明引入代價(jià)敏感系數(shù)提高了預(yù)測(cè)的效果；隨著μ值的增大，AUC的值也在增長(zhǎng)，但是當(dāng)μ>15時(shí)，AUC值開(kāi)始下降，說(shuō)明代價(jià)敏感系數(shù)并不是越大越好，當(dāng)μ=15時(shí)，CMKEL算法能達(dá)到最好的效果。

為了驗(yàn)證文中算法是否有更好的性能，分別在NASA和AEEEM兩個(gè)數(shù)據(jù)庫(kù)與其他算法進(jìn)行對(duì)比，結(jié)果如表4所示。(實(shí)驗(yàn)結(jié)果中將F-measure值表示成F值)

表4 算法對(duì)比結(jié)果

通過(guò)以上實(shí)驗(yàn)可以看出：NB，CC4.5，CBBN算法在某些項(xiàng)目上面能夠有比較好的F-measure值，但是CMKEL在大部分項(xiàng)目上都同時(shí)有很好的F-measure值、AUC值，效果要比前三種算法好，表明了CMKEL算法的優(yōu)越性。

4 結(jié)束語(yǔ)

為了解決軟件缺陷預(yù)測(cè)中樣本數(shù)據(jù)結(jié)構(gòu)復(fù)雜與類(lèi)別分布不平衡的問(wèn)題，提出一種基于多核集成學(xué)習(xí)的跨項(xiàng)目軟件缺陷預(yù)測(cè)算法。利用多核學(xué)習(xí)將數(shù)據(jù)映射到新的特征空間，更好地表示數(shù)據(jù)，提高預(yù)測(cè)的精確度。集成學(xué)習(xí)能夠解決類(lèi)別分布不平衡的問(wèn)題。在NASA和AEEEM這兩個(gè)數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果證明了該算法的有效性。