,,

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

隨著智能工具不斷發(fā)展，軟件的更新迭代越來(lái)越頻繁，軟件缺陷[1]預(yù)測(cè)問(wèn)題也受到社會(huì)的廣泛關(guān)注。比如2009年出現(xiàn)的Gmail故障，由于測(cè)試小組遺漏了一個(gè)軟件缺陷，造成了極大的損失和不便，因此有效地預(yù)測(cè)軟件缺陷模塊成為亟待解決的問(wèn)題。而應(yīng)用機(jī)器學(xué)習(xí)的軟件缺陷預(yù)測(cè)模型能夠盡早地預(yù)測(cè)和發(fā)現(xiàn)軟件缺陷，保證軟件質(zhì)量，減小損失，是一種高效的軟件缺陷預(yù)測(cè)手段。軟件缺陷問(wèn)題也屬于不平衡數(shù)據(jù)[2-4]問(wèn)題。軟件缺陷只存在于小部分軟件模塊中，缺陷模塊數(shù)量遠(yuǎn)小于正常模塊數(shù)量。目前應(yīng)用在軟件缺陷預(yù)測(cè)模型中的算法主要有支持向量機(jī)[5-8](Support vector machine，SVM)、樸素貝葉斯算法[9](Naive bayes，NB)、人工神經(jīng)網(wǎng)絡(luò)[10]和馬爾可夫鏈[11]等，結(jié)合SVM的改進(jìn)算法存在泛化能力不足的問(wèn)題，結(jié)合樸素貝葉斯的改進(jìn)算法由于樸素貝葉斯假定特征向量的各個(gè)分量獨(dú)立地作用于決策變量而同樣存在泛化能力不足的問(wèn)題，結(jié)合人工神經(jīng)網(wǎng)絡(luò)的改進(jìn)算法存在容易陷入局部最優(yōu)和網(wǎng)絡(luò)結(jié)構(gòu)需要多次調(diào)整的問(wèn)題。

為了提高軟件缺陷模型的準(zhǔn)確性，提出了改進(jìn)的軟件缺陷預(yù)測(cè)模型(FREDSVM)。即采用改進(jìn)的頻繁項(xiàng)集挖掘算法(IMMFIA)[12]來(lái)獲取頻繁項(xiàng)集，具有低時(shí)間復(fù)雜度和空間復(fù)雜度的特點(diǎn)；在具有相同前件的所有規(guī)則中選擇相關(guān)度最大的規(guī)則，利用新的規(guī)則排序度量(RSS)對(duì)規(guī)則進(jìn)行排序，得到分類器；針對(duì)規(guī)則匹配無(wú)果(對(duì)于不能被分類器中的規(guī)則所滿足的測(cè)試樣例)和規(guī)則匹配溢出(對(duì)于有多個(gè)規(guī)則滿足測(cè)試樣例的情況)問(wèn)題，結(jié)合EDSVM[13]進(jìn)行分類。

1 相關(guān)工作

1.1 改進(jìn)的關(guān)聯(lián)分類算法

1.1.1 改進(jìn)的頻繁項(xiàng)集挖掘算法(IMMFIA)

馬麗生等提出的IMMFIA算法在FP-tree[12-14]基礎(chǔ)上，對(duì)其結(jié)構(gòu)進(jìn)行修改，減少了FP-tree分支重復(fù)遍歷的次數(shù)，同時(shí)利用剪枝策略和壓縮策略縮小搜索空間和壓縮FP-tree的規(guī)模，降低了時(shí)間復(fù)雜度和空間復(fù)雜度。

1.1.2 相關(guān)度和排序規(guī)則強(qiáng)度(RSS)

設(shè)Q為元組的數(shù)據(jù)集合，Q中每個(gè)元組用n個(gè)屬性R1,R2,…,Rn和一個(gè)類標(biāo)號(hào)屬性Rc描述。項(xiàng)k為一個(gè)形如(Ri,v)的屬性-值對(duì)，其中Ri為屬性，取值v。項(xiàng)的集合稱為項(xiàng)集，滿足最小支持度閾值的項(xiàng)集稱為頻繁項(xiàng)集。支持度和置信度是關(guān)聯(lián)分類[15-16]算法中的重要概念，分別衡量關(guān)聯(lián)規(guī)則的重要性和正確率。

規(guī)則A?B的支持度s為

s(A?B)=P(A?B)

(1)

規(guī)則A?B的置信度c為

c(A?B)=P(B|A)

(2)

規(guī)則R:A?B的規(guī)則強(qiáng)度[17]SS(A?Bi)為

(3)

規(guī)則的類支持度CLSup為

(4)

規(guī)則的補(bǔ)類支持度CCS為

(5)

式中：s(A∪～Bi)為規(guī)則補(bǔ)類的支持度；s(～Bi)為類Bi的補(bǔ)類支持度。

1.2 EDSVM算法

1.2.1SVM算法

支持向量機(jī)方法(Support vector machine，SVM)借助于最優(yōu)化方法來(lái)解決機(jī)器學(xué)習(xí)問(wèn)題的工具，逐漸成為克服“維數(shù)災(zāi)難”和過(guò)擬合等問(wèn)題的有效手段。定義是根據(jù)給定的訓(xùn)練集，即

T={(x1,y1),(x2,y2),…,
(xl,yl)}∈(X×Y)l

(6)

式中：xi∈X=Rn，X稱為輸入空間，輸入空間中的每一個(gè)點(diǎn)xi由n個(gè)屬性特征組成；yi∈{-1,1},i=1,2,…,l。尋找Rn上的一個(gè)實(shí)值函數(shù)g(x)，以便用分類函數(shù)f(x)=sgn(g(x))，推斷任意一個(gè)模式x相對(duì)應(yīng)的y值的問(wèn)題為分類問(wèn)題。當(dāng)樣例線性不可分時(shí)，可以嘗試使用核函數(shù)來(lái)將特征映射到高維。核函數(shù)可以形式化定義為：如果原始特征內(nèi)積是，映射后為<φ(x),φ(z)>，那么核函數(shù)(Kernels)為

K(x,z)=φ(x)Tφ(z)

(7)

SVM對(duì)復(fù)雜的非線性邊界的建模能力較強(qiáng)，盡管訓(xùn)練較慢，但是分類結(jié)果非常準(zhǔn)確，且不容易過(guò)擬合，使得SVM算法在許多領(lǐng)域被廣泛應(yīng)用。

1.2.2 KNN算法

KNN[18-20]算法又稱K-最近鄰分類算法(K-nearest-neighbor-classifier)，該算法的基本思路是：如果一個(gè)樣本在特征空間中的K個(gè)最近鄰的樣本中的大多數(shù)樣本屬于1個(gè)類別，則該樣本也屬于這個(gè)類別。該算法主要涉及3個(gè)量：訓(xùn)練集、距離或相似的度量、K的大小。該算法簡(jiǎn)單、易于實(shí)現(xiàn)，屬于懶惰算法，需要掃描全部樣本計(jì)算，計(jì)算量大、速度較慢和內(nèi)存消耗較大，而且受K值影響嚴(yán)重:若K值太小，則分類獲得的有效信息少，甚至丟失；若K值太大，則包含較多其他類別的點(diǎn)，精度降低。

1.2.3 EDSVM算法

王超學(xué)等[13]提出的EDSVM算法的基本思想是：當(dāng)測(cè)試樣例與SVM分離超平面之間的距離q大于一定值d時(shí)，采用SVM算法進(jìn)行分類；否則以所有的支持向量作為測(cè)試樣例的近鄰樣本，進(jìn)行KNN 分類。EDSVM算法充分利用支持向量能夠代表訓(xùn)練數(shù)據(jù)集的含義，同時(shí)，使得KNN 算法降低對(duì)近鄰參數(shù)的依賴，有利于提高分類器的分類精度。

2 軟件缺陷測(cè)試模型的建立

基于FREDSVM建立軟件缺陷預(yù)測(cè)模型，主要步驟如圖1所示。

圖1 基于FREDSVM建立軟件缺陷預(yù)測(cè)模型流程圖Fig.1 The flow chart of establishing software defect prediction model based on FREDSVM

2.1 構(gòu)造分類器

獲取數(shù)據(jù)集之后，利用IMMFIA來(lái)獲取頻繁項(xiàng)集，它具有低時(shí)間復(fù)雜度和空間復(fù)雜度的特點(diǎn)，分析頻繁項(xiàng)集，產(chǎn)生每個(gè)類的滿足置信度和支持度閾值的關(guān)聯(lián)規(guī)則，結(jié)合相關(guān)度，在具有相同前件的所有規(guī)則中選擇相關(guān)度最大的規(guī)則，利用RSS對(duì)規(guī)則進(jìn)行排序，得到分類器。得到分類器之后，便可以對(duì)測(cè)試樣例進(jìn)行分類預(yù)測(cè)。

規(guī)則R:(A?Bi)的相關(guān)度[21]CL為

CL(A?Bi)=c(A?Bi)-s(Bi)

(8)

規(guī)則R:A?Bi的排序規(guī)則強(qiáng)度為

(9)

由CL和RSS 可以看出：小類規(guī)則的置信度和支持度較小，但是兩者相減之后的數(shù)值與大類的置信度和支持度相減的數(shù)值相差不大，所以在具有相同前件的所有規(guī)則中選擇相關(guān)度最大的規(guī)則，可以有效提高小類的匹配概率；利用RSS 對(duì)規(guī)則進(jìn)行排序，同樣可以有效提高小類的優(yōu)先級(jí)，弱化不平衡數(shù)據(jù)集帶來(lái)的問(wèn)題，從而提高分類準(zhǔn)確性。

2.2 結(jié)合EDSVM進(jìn)行分類預(yù)測(cè)

傳統(tǒng)的關(guān)聯(lián)分類算法在進(jìn)行分類預(yù)測(cè)的時(shí)候通常存在兩種情況：1) 對(duì)于不能被分類器中的規(guī)則所滿足的測(cè)試樣例(規(guī)則匹配無(wú)果)，分類器具有一個(gè)最低優(yōu)先級(jí)的默認(rèn)規(guī)則，自動(dòng)為其指定默認(rèn)規(guī)則，例如CBA[22]就把規(guī)則集中具有最大置信度的規(guī)則指定給測(cè)試樣例；2) 對(duì)于有多個(gè)規(guī)則滿足測(cè)試樣例的情況(規(guī)則匹配溢出)。

針對(duì)不平衡數(shù)據(jù)而言，上述兩種做法的分類精度并不理想，可能會(huì)出現(xiàn)小類規(guī)則無(wú)法分類或者分類錯(cuò)誤的情況。在出現(xiàn)規(guī)則匹配無(wú)果和規(guī)則匹配溢出情況時(shí)，結(jié)合EDSVM進(jìn)行分類預(yù)測(cè)能達(dá)到“因材施教”的效果。當(dāng)規(guī)則匹配無(wú)果時(shí)，在除去規(guī)則集的訓(xùn)練集中采樣EDSVM算法進(jìn)行分類預(yù)測(cè)，即當(dāng)測(cè)試樣例與SVM分離超平面之間的距離q1大于一定值d時(shí)，采用SVM算法進(jìn)行分類；否則以所有的支持向量作為測(cè)試樣例的近鄰樣本，進(jìn)行KNN 分類；當(dāng)規(guī)則匹配溢出時(shí)，在規(guī)則集中采樣EDSVM算法進(jìn)行分類預(yù)測(cè)，即當(dāng)測(cè)試樣例與SVM分離超平面之間的距離q2大于一定值d時(shí)，采用SVM算法進(jìn)行分類；否則以所有的支持向量作為測(cè)試樣例的近鄰樣本，進(jìn)行KNN 分類。具體算法步驟如下：

輸入測(cè)試樣例T，訓(xùn)練集Q，規(guī)則集R，除去規(guī)則集的訓(xùn)練樣本ExpR，常量d。

輸出測(cè)試樣例的類別。

步驟1在規(guī)則集R中找出滿足測(cè)試樣例T的m個(gè)規(guī)則。

步驟2若選出的m個(gè)規(guī)則相同，則測(cè)試樣例的類別即為該規(guī)則的類別，輸出結(jié)束。

步驟3若選出的m個(gè)規(guī)則相異，則判斷是規(guī)則匹配無(wú)果還是規(guī)則匹配溢出，規(guī)則匹配無(wú)果跳轉(zhuǎn)步驟4，規(guī)則匹配溢出跳轉(zhuǎn)步驟5。

步驟4若規(guī)則匹配無(wú)果，則在除去規(guī)則集R的訓(xùn)練集Q中計(jì)算測(cè)試樣例與SVM分離超平面之間的距離q1，若q1>d，則采用SVM算法進(jìn)行分類，否則以所有的支持向量作為測(cè)試樣例的近鄰樣本，進(jìn)行KNN分類。

步驟5若規(guī)則匹配溢出，則在規(guī)則集R中計(jì)算測(cè)試樣例與SVM分離超平面之間的距離q2，若q2>d，采用SVM算法進(jìn)行分類，否則以所有的支持向量作為測(cè)試樣例的近鄰樣本，進(jìn)行KNN分類。

步驟6輸出測(cè)試樣例的類別。

3 改進(jìn)的軟件缺陷預(yù)測(cè)模型實(shí)驗(yàn)

3.1 評(píng)估性能度量

采用混淆矩陣作為評(píng)估性能度量，如表1所示。

表1 混淆矩陣1)Table 1 Confusion matrix

注：1)TP表示被分類器正確分類的正類數(shù)；TN表示被分類器正確分類的負(fù)類數(shù)；FN表示被分類器錯(cuò)誤分類的負(fù)類數(shù)；FP表示被分類器錯(cuò)誤分類的正類數(shù)。

傳統(tǒng)的分類算法一般采用準(zhǔn)確率，即

(10)

作為評(píng)估性能度量。針對(duì)不平衡數(shù)據(jù)集，該度量不夠合理。因?yàn)闇?zhǔn)確率偏向于反映大類的分類情況而忽略了小類的分類情況，可能會(huì)導(dǎo)致錯(cuò)誤判斷了分類器的分類預(yù)測(cè)效果。因此，采用F值(調(diào)和平均值)和準(zhǔn)確率指標(biāo)共同作為評(píng)估性能度量。

精度為

(11)

召回率為

(12)

F值為

(13)

3.2 實(shí)驗(yàn)數(shù)據(jù)

NASAMDP(Metrics data program)是由美國(guó)航空航天局發(fā)布的專門用于構(gòu)建軟件缺陷預(yù)測(cè)模型的公開(kāi)數(shù)據(jù)集，是實(shí)驗(yàn)最常用的數(shù)據(jù)。采用4個(gè)公開(kāi)數(shù)據(jù)集JM1，KC1，PC1和CM1進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集具體分布情況如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)Table 2 Experimental data

表2中，數(shù)據(jù)集中字段Defective值為Y的模塊屬于有缺陷的模塊，否則為無(wú)缺陷的模塊，計(jì)算出缺陷率。因?yàn)閿?shù)據(jù)集中存在部分冗余的屬性，所以要對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理操作，只取其中有用的屬性，如表3所示。

表3 數(shù)據(jù)集屬性Table 3 Attribute of datasets

3.3 實(shí)驗(yàn)結(jié)果與分析

圖2中的4張子圖分別為L(zhǎng)R，SVM，ACO-SVM以及提出的方法FREDSVM在JM1，KC1，PC1和CM1數(shù)據(jù)集上的測(cè)試結(jié)果。從圖2中可以看出：LR與SVM這兩種方法預(yù)測(cè)結(jié)果受數(shù)據(jù)集影響較大，在JM1和PC1數(shù)據(jù)集上，SVM測(cè)試效果優(yōu)于LR，而在KC1和CM1數(shù)據(jù)集上，LR較優(yōu)，這是由于LR受數(shù)據(jù)容量的限制，而SVM則受限于調(diào)參；ACO-SVM方法不僅克服了數(shù)據(jù)容量的局限，還優(yōu)化了SVM調(diào)參受限的問(wèn)題，所以測(cè)試效果優(yōu)于LR和SVM；FREDSVM利用IMMFIA獲取頻繁項(xiàng)集，再根據(jù)RSS提高小類的優(yōu)先級(jí)，然后運(yùn)用EDSVM針對(duì)規(guī)則匹配無(wú)果和規(guī)則匹配溢出問(wèn)題進(jìn)行分類，得到的測(cè)試結(jié)果優(yōu)于LR，SVM及ACO-SVM方法。

圖2 數(shù)據(jù)集預(yù)測(cè)結(jié)果對(duì)比Fig.2 Comparison of forecasting results in datasets

4 結(jié) 論

針對(duì)軟件缺陷預(yù)測(cè)模型的準(zhǔn)確性問(wèn)題，提出了改進(jìn)的軟件缺陷預(yù)測(cè)模型(FREDSVM)。主要思想是將利用IMMFIA獲取到的頻繁項(xiàng)集根據(jù)相關(guān)度和新的規(guī)則排序度量RSS進(jìn)行排序，提高小類的優(yōu)先級(jí)，然后運(yùn)用EDSVM針對(duì)規(guī)則匹配無(wú)果和規(guī)則匹配溢出問(wèn)題進(jìn)行分類。通過(guò)對(duì)LR，SVM，ACO-SVM以及FREDSVM算法在JM1，KC1，PC1和CM1數(shù)據(jù)集上測(cè)試對(duì)比分析，結(jié)果表明：FREDSVM比傳統(tǒng)的軟件缺陷預(yù)測(cè)模型效果更優(yōu)，在相同數(shù)據(jù)集上具有更高的精確率和召回率。在運(yùn)用EDSVM進(jìn)行分類時(shí)，針對(duì)SVM的調(diào)參問(wèn)題在今后可以進(jìn)行優(yōu)化。