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

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

0 引 言

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

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

1 相關(guān)工作

1.1 樸素貝葉斯

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

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

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

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

(1)

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

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

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

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

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

1.2 粒子群算法

粒子群算法[6-7]是人類根據(jù)鳥類群體的行為表象提出的一個(gè)算法，其核心思想就是模擬鳥類群體一起飛行尋食的過程，通過鳥類種群里各個(gè)小鳥的相互協(xié)作，反饋出自身最好的位置，然后再在鳥類種群里尋找到整個(gè)種群最佳的位置。現(xiàn)在我們把種群里的每一只鳥看成一個(gè)粒子，演化成現(xiàn)在的粒子群算法。就是在維數(shù)為D的搜尋空間里，有一粒規(guī)模數(shù)為N的種群粒子。然后規(guī)范粒子群相關(guān)參數(shù)，其中第i個(gè)粒子位置為：xi=(xi1,xi2,…,xiD)，第i個(gè)粒子速度為：vi=(vi1,vi2,…,viD)，第i個(gè)粒子歷史最優(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)解。我們給出一個(gè)將變異思想融入PSO里的改進(jìn)算法，即M-PSO(Mutation Swarm Optimization))。在歷代更新進(jìn)程中使用變異手段，使之最終得到最優(yōu)解。

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

Pmax=(pmax1,pmax2,…,pmaxN)

Pmin=(pmin1,pmin2,…,pminN)

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

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