基于改進PSO與NB算法的軟件缺陷預(yù)測模型

馬振宇,張 威,*,王曉嶺,高 飛,劉福勝

(1.裝甲兵工程學(xué)院，北京 100072； 2.中國人民解放軍91431部隊，湛江 524002；3.中國人民解放軍9596部隊，武漢 430300)

0 引 言

近幾年，隨著科技的不斷發(fā)展，軟件在各個領(lǐng)域都得到廣泛的應(yīng)用，軟件已然對國家經(jīng)濟走向以及國民生活品質(zhì)的高低起到至關(guān)重要的影響作用。為了能最大限度的利用好軟件，我們就需要在軟件開發(fā)的第一步把好關(guān)，盡可能多的預(yù)測出缺陷，降低日后軟件在使用過程中所需花費更大的代價。諸如軟件的再次開發(fā)、維護成本甚至直接造成軟件的失效，因此軟件缺陷預(yù)測技術(shù)[1-3]越來越受到人們的矚目。

為了尋找到一種高效地預(yù)測方法，可以更早地、更準地、更快地發(fā)現(xiàn)軟件潛在的缺陷，那么就可以通過高效地預(yù)測技術(shù)節(jié)省更多的資源。本文借鑒遺傳思想，將遺傳算法中變異的思想融入到粒子群算法中，通過變異算子使得種群里的粒子更新得到更好地速度和位置；然后將該方法與樸素貝葉斯算法相結(jié)合，得到最優(yōu)的分離點以及最低的錯誤率；最后建立軟件缺陷預(yù)測模型，提高軟件預(yù)測能力[4]。

1 相關(guān)工作

1.1 樸素貝葉斯

貝葉斯定理在250多年前就被發(fā)明，在當今領(lǐng)域內(nèi)有著無法撼動的位置。貝葉斯分類是一系列該分類算法的統(tǒng)稱，這些算法都是根據(jù)貝葉斯定理演變而來，所以都叫做貝葉斯分類。在該分類算法的領(lǐng)域里，樸素貝葉斯算法(Naive Bayesian)[5]是其中應(yīng)用最為廣泛的算法之一，本文將其做以重點介紹。

借鑒概率和數(shù)理統(tǒng)計的思想將NB分類。NB是貝葉斯算法的一種特殊情況，它簡化了屬性變量之間的關(guān)系，即簡化為相互獨立。雖然這個條件在一定范圍里制約了樸素貝葉斯算法，但是與此同時，樸素貝葉斯算法使得對參數(shù)的估計大量簡化，并通?？梢院雎詳?shù)據(jù)丟失帶來的影響，算法本身也就簡單化了，因而從較廣的范圍上降低了樸素貝葉斯算法的復(fù)雜度。

樸素貝葉斯算法模型如下：每一個數(shù)據(jù)樣本都有很多的屬性，把它的所有屬性構(gòu)建成一個n維的特征向量X={x1,x2,…xn}，分別對這n個屬性進行A1,A2,…An度量。假設(shè)有m個類Y={y1,y2,…ym}，對于給出的一個未知樣本X，預(yù)估X隸屬于具有最大后驗概率的類里，那么NB算法將未知樣本分到y(tǒng)i，也就是滿足下式：

P(yi|X)>P(yj|X), 1≤j≤m,j≠i

(1)

其中P(yi|X)最高對應(yīng)類的yi稱作最大后驗假定，由貝葉斯定理，得到：

由于數(shù)據(jù)樣本集具有很多的屬性，它們之間的關(guān)系錯綜復(fù)雜，計算P(X|yi)的開銷可能會異常的大，為了減少計算P(X|yi)的開銷。我們假設(shè)各個屬性相互獨立，即在屬性之間，沒有任何聯(lián)系，既有：

其中每個樣本的屬性條件概率P(x1|yi),P(x2|yi),…,P(xn|yi)可由訓(xùn)練樣本估算。其中Ak分為兩種情況討論，即：

(1)若Ak是連續(xù)的，我們一般就假設(shè)這個屬性滿足高斯分布，得到：

其中，給出yi樣本屬性值A(chǔ)k，g(xk,μyi,σyi)是屬性Ak的高斯密度函數(shù)，而μyi,σyi分別為平均值和標準差。

1.2 粒子群算法

粒子群算法[6-7]是人類根據(jù)鳥類群體的行為表象提出的一個算法，其核心思想就是模擬鳥類群體一起飛行尋食的過程，通過鳥類種群里各個小鳥的相互協(xié)作，反饋出自身最好的位置，然后再在鳥類種群里尋找到整個種群最佳的位置。現(xiàn)在我們把種群里的每一只鳥看成一個粒子，演化成現(xiàn)在的粒子群算法。就是在維數(shù)為D的搜尋空間里，有一粒規(guī)模數(shù)為N的種群粒子。然后規(guī)范粒子群相關(guān)參數(shù)，其中第i個粒子位置為：xi=(xi1,xi2,…,xiD)，第i個粒子速度為：vi=(vi1,vi2,…,viD)，第i個粒子歷史最優(yōu)位置為：pi=(pi1,pi2,…,piD), 所有粒子最優(yōu)位置為：pg=(pg1,pg2,…,pgD)，位置更新公式為：viD(t+1)=ωviD(t)+c1r1×(pid(t)-xiD(t))+c2r2(pgD(t)-xiD(t))速度更新公式為：xiD(t+1)=xiD(t)+viD(t+1)。

2 基于遺傳思想的PSO算法

為了保持粒子的高效性，根據(jù)遺傳算法[8-10]里的變異算法，避免求解過程中陷于局部最優(yōu)解。我們給出一個將變異思想融入PSO里的改進算法，即M-PSO(Mutation Swarm Optimization))。在歷代更新進程中使用變異手段，使之最終得到最優(yōu)解。

而PSO的具體變異迭代公式為：

(6)

在以上公式中，我們可以得出一些結(jié)論。第一塊通過參數(shù)變量可以有效地預(yù)計變異的幅度和運動軌跡。第二塊則是通過變異操作來達到目的的。

曾經(jīng)有種極端的改變方法。將一部分粒子的原有運動軌跡直接變異為逆方向，大大增強了該群的多樣性，提升了PSO的尋優(yōu)能力。就是把遺傳思想里的變異率應(yīng)用到粒子群算法中，用種群的規(guī)模大小去乘以變異率，算出需要變異的粒子個數(shù)，選定等同數(shù)目的粒子個數(shù)，不再按原來的迭代方程式進行速度的更新，而是選取種群現(xiàn)狀中最優(yōu)解的逆方向定為該粒子的飛行軌跡。這樣以來就擴大了粒子自身的搜尋范圍，消弱了粒子聚集的可能性，避免了“早熟”現(xiàn)象的出現(xiàn)。

其基本實現(xiàn)步驟如下，即圖1所示。

第一步：初始化該種群中所有粒子的初始位置和速度。假定粒子的種群數(shù)量為N。

第二步：通過適應(yīng)值函數(shù)，算出每個粒子最初的適應(yīng)值。將每個粒子在取適應(yīng)值時所處位置設(shè)為Pbest，然后在根據(jù)該群體里的初始粒子，選擇最優(yōu)的適應(yīng)值所對應(yīng)的位置設(shè)為Gbest。

第三步：根據(jù)粒子位置和速度公式更新每個新粒子的最優(yōu)位置和最佳速度。用其更新的位置和速度帶入適應(yīng)函數(shù)，計算出新的適應(yīng)值。

第四步：判斷β是否趨于0，如果是就對該代粒子采取變異手段，通過變異迭代公式去產(chǎn)生新的粒子,然后求解與其對應(yīng)的新的適應(yīng)值。否則直接跳過第五步，進行第六步。

第五步：比較所有適應(yīng)值。把該代的每一個粒子的適應(yīng)值分別于對應(yīng)的上一代粒子乃至歷代粒子的適應(yīng)值進行對比，假如該代粒子的適應(yīng)值比上一代粒子乃至歷代粒子的適應(yīng)值都要好，就把該粒子的位置更新為現(xiàn)在最好的位置，否則不進行替換。再拿下一代的每一個粒子的適應(yīng)值去和歷史全局的適應(yīng)值進行比較，假如該帶的適應(yīng)值高于歷史種群的適應(yīng)值，就用該粒子的位置更換歷史種群最優(yōu)位置，否則不進行更換。

第六步：判別該方法的終止條件，如果算法大于最多迭代次數(shù)或者找到最優(yōu)解，立刻終止。否則回到第三步，接著進行運算。

圖1 M-PSO算法實現(xiàn)步驟

3 基于M-PSO與NB的軟件缺陷預(yù)測模型

3.1 基于M-PSO與NB的屬性離散化

把各個樣本的屬性值離散化，不但能夠避免由于屬性值連續(xù)帶來的大量計算量，而且能使預(yù)測結(jié)果簡單明了和便于應(yīng)用。我們把M-PSO與樸素貝葉斯相結(jié)合來完成屬性值連續(xù)問題的離散化。為了更好地敘述這個方法，我們不妨假定樣本的屬性數(shù)量為N。粒子群探索范圍的上下界分別是：

Pmax=(pmax1,pmax2,…,pmaxN)

Pmin=(pmin1,pmin2,…,pminN)

(7)

其中Pmaxi和Pmini分別代表該樣本第i個屬性的最大值(上界)和最小值(下界)。各個樣本的屬性值的離散化其實就是在每個屬性所屬的范圍內(nèi)尋找?guī)讉€分離點，假設(shè)將屬性劃分出a個等級，那么就需要找到a-1個分離點。

3.2 M-PSO與NB實現(xiàn)介紹

各個樣本本身的屬性離散化本質(zhì)就是找尋該樣本的分離點，由于沒有統(tǒng)一的方法能夠使分離結(jié)果做到最好，所以這也是實現(xiàn)該問題的一個難點。我們將NB的分類錯誤率當做粒子群算法里的適應(yīng)函數(shù)，使用本文提出的M-PSO算法搜尋能夠使得適應(yīng)函數(shù)值最小的來找到最佳分離點。

第一步：對種群的粒子進行初始化，粒子群維數(shù)為N=20,w=0.3,c1=c2=1.5,r1=r2為0到1的隨機數(shù)。最大迭代次數(shù)為Tmax=50，初始迭代次數(shù)為t=0。然后把屬性劃分為3個級別，即有2個分離點。

第二步：依據(jù)每個粒子的坐標分離各個樣本的屬性，在應(yīng)用樸素貝葉斯算法得到分類錯誤率，也是在比較該粒子坐標的好壞。然后更替粒子群里各個粒子最優(yōu)位置以及種群最優(yōu)位置。

第三步：按照文章里指出的M-PSO算法更替該粒子種群兩個指標。

第四步：t=t+1，判別t是不是小于T，如果是，立刻回到第二步，否則繼續(xù)。

第五步：輸出最佳分離點和最小錯誤率，得到軟件缺陷預(yù)測模型。

3.3 軟件缺陷預(yù)測模型

建立軟件缺陷預(yù)測模型，即圖2所示。

第一步：收集軟件數(shù)據(jù)，輸入總樣本數(shù)以及各樣本屬性。

第二步：求解各個樣本屬性的的最大值(上界)與最小值(下界)。

第三步：根據(jù)文獻[11]中，葛賀賀給出的訓(xùn)練樣本與測試樣本的分配比例(3∶2)，本文為了方便進行實驗結(jié)果的對比分析，所以選擇一樣的分配比例。然后隨機進行樣本的分組。

第四步：將M-PSO與NB算法相結(jié)合，計算每個樣本的分離點，將樣本屬性離散化。

第五步:基于第四步的結(jié)果，建立軟件缺陷預(yù)測模型。

第六步：輸出預(yù)測結(jié)果。

圖2 軟件缺陷預(yù)測模型

4 實驗分析

為了更好地對比實驗效果，本文采用NASA提供的數(shù)據(jù)包，里面總樣本個數(shù)有10 855個，并包括21個屬性。我們首先從總共的樣本數(shù)里任意抽選6 000個當做訓(xùn)練樣本，然后從剩余的里面任意抽選4 000個當做測試樣本；然后根據(jù)數(shù)據(jù)離散化屬性，從每個屬性的最大值和最小值之間找出2個分離點，即把屬性分為了3個等級；最后的實驗結(jié)果如表1所示。

進一步我們可以得到分類錯誤率，在使用M-PSO與樸素貝葉斯方法相融合的情況下，使得錯誤率有了良好的改觀，控制到15.12%。比其他算法計算出來的錯誤率更好。比如在文章《Knowledge Discovery in Databases: An Attribute-oriented Approach》[12]中的錯誤率為20.45%，在文章《Extracting Classification Rule of Software Diagnosis Using Modified MEPA》[13]中的錯誤率為18.87，而在極為相似算法的文章《基于PSO和樸素貝葉斯的軟件缺陷預(yù)測模型》[11]中的錯誤率仍為16.8%，證明了該方法的有效性。

表1 數(shù)據(jù)離散化結(jié)果

5 結(jié) 語

本文通過將遺傳算法里的變異思想融入到PSO中，提出了兩個相融合的方法M-PSO，以此為基礎(chǔ)，和樸素貝葉斯算法相融合，構(gòu)建出軟件缺陷預(yù)測模型。實驗結(jié)果證明，由于M-PSO算法改良了粒子群算法本身收斂速度較慢的缺點，所以可以更加高效地預(yù)測缺陷，使得軟件有了更高的可靠性。

但對于多樣本多屬性的數(shù)據(jù)，會出現(xiàn)收斂速度較慢的現(xiàn)象，所以在今后的研究工作中，需要采用更高效的分類算法，提高預(yù)測效果。