基于改進GM(1,1)模型預(yù)測軟件缺陷率

王曙燕，黃煒青，孫家澤

(西安郵電大學(xué) 計算機學(xué)院，陜西 西安710121)

基于改進GM(1,1)模型預(yù)測軟件缺陷率

王曙燕，黃煒青，孫家澤

(西安郵電大學(xué) 計算機學(xué)院，陜西 西安710121)

給出一種基于隨機抽樣一致性算法(RANSAC)的GM(1,1)改進模型。運用RANSAC篩除異常值，選擇估計誤差最小的點作為定解條件，結(jié)合插值思想對軟件缺陷率進行預(yù)測。分別對有無奇異值的數(shù)據(jù)預(yù)測，結(jié)果表明改進后的模型不僅能夠改善異常值對預(yù)測的影響，而且比GM(1,1)模型取得較高的預(yù)測精度。

灰色模型；隨機抽樣一致性算法；定解條件；異常值；軟件缺陷率

軟件缺陷是軟件產(chǎn)品開發(fā)中不可避免的問題，這些缺陷可能導(dǎo)致軟件的失效甚至崩潰，而軟件缺陷預(yù)測技術(shù)[1]就可以預(yù)測軟件系統(tǒng)中可能存在的缺陷數(shù)目，以決定軟件系統(tǒng)是否穩(wěn)定、可交付。

目前，軟件缺陷預(yù)測主要是基于機器學(xué)習(xí)的，例如利用支持向量機SVM作為二值分類器的軟件缺陷預(yù)測模型[2]；通過模擬退火技術(shù)來改進BP神經(jīng)網(wǎng)絡(luò)來建立軟件缺陷預(yù)測模型[3]；根據(jù)Boosting理論，訓(xùn)練基本k-NN預(yù)測器建立軟件缺陷預(yù)測模型[4]。這些方法雖然實現(xiàn)了軟件缺陷的預(yù)測，但都存在著所需的樣本數(shù)據(jù)量多，計算工作量大的問題。

灰色系統(tǒng)理論(Grey Theory)已廣泛應(yīng)用于社會、經(jīng)濟、科技、農(nóng)業(yè)、生態(tài)、生物等各個領(lǐng)域[5]。由該理論建立的GM(M,N)模型即灰色模型，其中1階，1變量的微分方程模型稱為GM(1,1)[6]，該模型可以通過少量的、不完全的信息，建立灰色微分預(yù)測模型，用以揭示事物的發(fā)展過程，預(yù)測其未來的發(fā)展規(guī)律，屬于模糊預(yù)測領(lǐng)域中的一支[7]。利用GM(1,1)模型進行預(yù)測已十分普遍，以GM(1,1)模型為基礎(chǔ)建立了兩類離散GM(1,1)模型對軟件缺陷進行預(yù)測，解決了對于原始數(shù)據(jù)為非齊次指數(shù)序列的預(yù)測問題[8]；運用灰色預(yù)測模型對ISS歷年發(fā)現(xiàn)的軟件安全缺陷個數(shù)進行預(yù)測[9]；文獻[10]提出一種基于灰色預(yù)測理論的軟件缺陷率預(yù)測模型。但是，上述方法在運用GM(1,1)模型預(yù)測時，均未考慮原始數(shù)據(jù)可能有異常值的出現(xiàn)。而GM(1,1)模型計算參數(shù)時，采用最小二乘法求解，一旦數(shù)據(jù)出現(xiàn)奇異點，結(jié)果就會出現(xiàn)問題，導(dǎo)致預(yù)測效果較差。因此，本文引入隨機抽樣一致性算法(RANdom Sample Consensus Algorithm，RANSAC)[11]，篩除異常值，建立軟件缺陷率預(yù)測模型。

1 GM(1,1)模型概述

灰色系統(tǒng)是對離散序列建立的微分方程，GM(1,1)是一階微分方程模型，其形式為[7]

(1)

由導(dǎo)數(shù)定義知

(2)

當(dāng)Δt很小并且取為1時，近似的有

(3)

離散表達式為

(4)

(5)

(6)

基于上述機理，GM(1,1)模型的建模過程主要分為數(shù)據(jù)處理、模型建立和模型檢驗與預(yù)測3步。

步驟1數(shù)據(jù)處理

設(shè)原始數(shù)據(jù)X(0)={x(0)(1),x(0)(2),…,x(0)(n)}一次累加得到新數(shù)列X(1)={x(1)(1),x(1)(2),…,x(1)(n)}

其中

(7)

式中k表示離散化的時間節(jié)點，x(1)右上角的數(shù)字表示累加的次數(shù)，0表示原始數(shù)據(jù)，1表示經(jīng)過一次累加，累加完成之后對數(shù)字序列進行準(zhǔn)光滑性檢驗[9]

(8)

(9)

其中σ表示數(shù)字序列的指數(shù)比，若當(dāng)k>3時，σ(k)∈[1,1.5]成立則準(zhǔn)指數(shù)規(guī)律滿足。

如果原始數(shù)據(jù)序列滿足準(zhǔn)光滑條件和準(zhǔn)指數(shù)規(guī)律，則可直接建立GM(1,1)預(yù)測模型，進行數(shù)據(jù)預(yù)測；如果不滿足，則需要對原始數(shù)據(jù)序列進行二階弱化算子處理[7]。將弱化后所得的新序列作為新的原始數(shù)據(jù)，建立GM(1,1)預(yù)測模型。

步驟2模型建立

GM(1,1)的灰微分方程模型[9]為

(10)

(11)

其中B，Yn表達式為

Yn=(x(0)(2),x(0)(3),…,x(0)(n))T,

(12)

則式(10)通解[12]為

(13)

假定

(14)

則預(yù)測模型為式(13)在式(14)條件下的特解[9]

(15)

(16)

步驟3模型檢驗

GM(1,1)模型的精度檢驗[13]一般有相對誤差大小檢驗法、關(guān)聯(lián)度檢驗法和后驗差檢驗法3種方法。

后驗差檢驗方法主要利用后驗差D和最小誤差概率p來綜合評定預(yù)測模型的精度。記殘差序列[11]為

(17)

表1 灰色預(yù)測精度等級標(biāo)準(zhǔn)

2 模型改進

2.1 基于RANSAC算法優(yōu)化參數(shù)計算

RANSAC算法[11]是一種參數(shù)估算方法，其基本思想是將數(shù)據(jù)分為局內(nèi)點和局外點，局內(nèi)點符合一定的模型，而局外點不符合該模型。利用該模型可以進行數(shù)據(jù)篩選，符合該模型的點也被認(rèn)為是局內(nèi)點，不符合模型的點就會被舍棄，找到符合該模型的點之后，結(jié)合該點與之前確定的局內(nèi)點，重新計算模型，用新模型繼續(xù)驗證，直到剔除了所有局外點。RANSAC改進GM(1,1)模型流程如圖1所示。

(1) 取向量Y第n和n-1的元素，作為新向量Yn，同理取B中第n行和n-1行的組成子矩陣Bn，依據(jù)式(11)由Yn、Bn計算出模型參數(shù)a。

(2) 將向量Y第n-2的元素加入Yn中組成新的向量Yn+，同理選取B中第n-2行組成新的子矩陣Bn+，由Yn+、Bn+計算模型參數(shù)a1。

(4) 如果a和a1的差異高于一定閾值，則認(rèn)為新加入的數(shù)據(jù)是異常值，若異常值處于奇數(shù)位置則利用降采樣的思想將奇數(shù)位置的數(shù)據(jù)都剔除掉。若處于偶數(shù)位置，則原數(shù)據(jù)中偶數(shù)位置的數(shù)據(jù)均剔除掉。

(5) 算法結(jié)束后，由Yn和Bn計算出來的參數(shù)即為最后結(jié)果。

圖1 RANSAC改進模型流程

2.2 擇優(yōu)選擇約束條件

假定擬合曲線通過時間序列的第m個點，則定解條件為

(18)

則定解為

(k=1,2,…)。

(19)

假設(shè)每一點都是約束條件，即在每個約束條件的基礎(chǔ)上都進行預(yù)測，預(yù)測結(jié)果與實際結(jié)果之間的誤差用來反映該約束條件是否可取，最終選擇誤差最小的約束條件作為標(biāo)準(zhǔn)約束條件。

在進行預(yù)測時，經(jīng)過RANSAC算法篩選數(shù)據(jù)，奇數(shù)或偶數(shù)位置的數(shù)據(jù)被剔除，由式(19)中的具體參數(shù)可計算出部分?jǐn)?shù)據(jù)，剩余部分的數(shù)據(jù)可以利用插值思想，基于已建立的模型，由平移時間節(jié)點得到

(k=1,2,…)。

(20)

將兩部分計算所得數(shù)據(jù)，交替按順序整理可得到最終預(yù)測結(jié)果。

3 實驗與分析

實驗在Windows操作系統(tǒng)下利用MATLAB軟件進行，利用改進模型分別對軟件缺陷率[14](Model Bug Rate,MBR)(表2)數(shù)據(jù)源在有無奇異值數(shù)據(jù)情況下進行預(yù)測。

表2 MBR統(tǒng)計值

實驗1對無奇異值的數(shù)據(jù)利用改進的GM(1,1)模型進行預(yù)測。

由表2數(shù)據(jù)構(gòu)建原始序列

X(0)={125.0, 102.3, 92.5, 72.0, 64.2, 53.0, 43.9},

一次累加后生成序列

X(1)={125.0, 227.3, 319.8, 391.8, 456, 509, 552.9},

數(shù)據(jù)滿足準(zhǔn)光滑性以及準(zhǔn)指數(shù)規(guī)律，可以建立GM(1,1)模型。

計算模型參數(shù)為

a=0.168 615,b=134.346 193,

表3 MBR統(tǒng)計值與預(yù)測值

圖2 預(yù)測值與實際值結(jié)果對比

由圖2的結(jié)果可看出，在沒有異常值的情況下，改進后的模型預(yù)測值與實際值相比，相對誤差較小，MBR實際值與預(yù)測值有較好的擬合性。

實驗2對有奇異值的數(shù)據(jù)進行預(yù)測，假設(shè)人為的失誤將原數(shù)據(jù)92.5錯誤記錄為925。

現(xiàn)原始序列為

X(0)={125.0, 102.3, 925, 72.0, 64.2, 53.0, 43.9},

一次累加后生成序列

X(1)={125.0, 277.3, 1 152.3, 1 224.3, 1 288.5, 1 341.5, 1 385.4}

數(shù)據(jù)仍滿足準(zhǔn)光滑性以及準(zhǔn)指數(shù)規(guī)律，因此不需弱化直接建立GM(1,1)模型。

當(dāng)GM(1,1)模型利用最小二乘法求解，計算模型參數(shù)

a=0.276 5,b=486.105 6,

預(yù)測模型為

在改進模型中，一次累加后生成序列

X(1)={125.0, 227.3, 1 152.3, 1 224.3, 1 288.5, 1 341.5, 1 385.4}

根據(jù)式(12)計算得到

利用RANSAC算法選取Yn、Bn，首先分別選取B和Y第6行和第7行數(shù)據(jù)作為初始值，即

根據(jù)式(11)計算出參數(shù)a=[0.187 8 295.441 3]

然后將B和Y第5行數(shù)據(jù)添加到Y(jié)n+、Bn+中得到

根據(jù)式(11)計算出參數(shù)a1，如果a和a1差小于閾值，則令a=a1，并繼續(xù)按照從后到前的順序給Yn、Bn中添加新數(shù)據(jù)，比較新計算的a和a1之間的差異。如果a和a1之間差大于閾值，則新加入的點為奇異點。

在本次實驗中，添加第二行數(shù)據(jù)，即奇異值925所對應(yīng)的數(shù)據(jù)時，a和a1差大于閾值，所以判斷新加入數(shù)據(jù)為奇異值。

奇異值處于原始數(shù)據(jù)第三位置，按照降采樣做法將奇數(shù)位置的數(shù)據(jù)舍棄，利用剩余數(shù)據(jù)計算出模型參數(shù)為

a=0.304 0,b=114.043 2,

根據(jù)擇優(yōu)選取約束條件的思想，最終選取第二個點為標(biāo)準(zhǔn)約束條件并得到預(yù)測模型

后驗差D=0.115 0<0.35，最小誤差概率p=1>0.95，由表1可知精度等級為一級，實驗結(jié)果如表4。兩種模型預(yù)測結(jié)果對比如圖 3所示。

表4 兩種模型預(yù)測結(jié)果

圖3 兩種模型預(yù)測結(jié)果對比

由圖3結(jié)果可以看出，改進模型預(yù)測效果比傳統(tǒng)GM(1,1)模型的預(yù)測效果更佳準(zhǔn)確，幾乎與MBR原始統(tǒng)計值一樣。改進模型在處理有奇異值的數(shù)據(jù)時，不僅摒棄掉奇異值的數(shù)據(jù)，而且還對奇異值位置應(yīng)有的數(shù)據(jù)進行了有效的估計。

上述兩個實驗結(jié)果表明，基于RANSAC的GM(1,1)改進模型有較好的預(yù)測效果，尤其是在有異常值的情況下，MBR原始的統(tǒng)計值為{102.3, 92.5, 72.0, 64.2, 53.0, 43.9}，改進模型預(yù)測值為{102.3, 83.26, 71.52, 61.44, 52.77, 45.33}，與統(tǒng)計值十分接近，而原模型受奇異值影響，預(yù)測值為{394.48, 299.16, 226.90, 172.08, 140.50, 98.97}，可以看出與MBR原始的統(tǒng)計值差異過大。改進模型在當(dāng)前數(shù)據(jù)下預(yù)測準(zhǔn)確率可以達到97.4%，改善了原模型不能處理含有奇異值數(shù)據(jù)的問題。

4 結(jié)束語

將RANSAC算法與GM(1,1)模型相結(jié)合，選擇最小估計誤差的點作為定解條件，改善了GM(1,1)模型在預(yù)測具有異常值的數(shù)據(jù)序列問題。在無奇異值和有奇異值的數(shù)據(jù)上分別進行實驗，實驗結(jié)果表明改進模型能在軟件缺陷率記錄數(shù)據(jù)中含有奇異值的情況下進行有效的預(yù)測。

[1] 王青,伍書劍,李明樹.軟件缺陷預(yù)測技術(shù)[J].軟件學(xué)報,2008,19(7):1555-1580.

[2] 王濤,李偉華,劉尊,等.基于支持向量機的軟件缺陷預(yù)測模型[J].西北工業(yè)大學(xué)學(xué)報,2011,29(6):864-869.

[3] 尹然,丁曉明,李小亮,等.基于SA-BP神經(jīng)網(wǎng)絡(luò)的軟件缺陷預(yù)測模型的研究[J].西南師范大學(xué)學(xué)報：自然科學(xué)版,2013,38(8):147-152.

[4] 何亮,宋擒豹,沈鈞毅.基于Boosting的集成k-NN軟件缺陷預(yù)測方法[J].模式識別與人工智能,2012,25(5):792-802.

[5] 王立宏.面向測試過程的軟件可信性度量[D].西安：西安郵電大學(xué), 2013:22-24.

[6] 張濤,吳成茂,高向鵬.灰色系統(tǒng)理論在郵政業(yè)務(wù)預(yù)測中的應(yīng)用[J].西安郵電學(xué)院學(xué)報,1999,4(2):25-28.

[7] 劉思峰.灰色系統(tǒng)理論及其應(yīng)用[M].科學(xué)出版社,2010:5-40.

[8] 尹紅健.兩類離散GM(1,1)模型及其軟件缺陷預(yù)測建模[J].海南大學(xué)學(xué)報：自然科學(xué)版,2010,28(2): 148-152.

[9] 楊俊峰.基于GM(1,1)模型的軟件缺陷數(shù)預(yù)測[J].中國科技信息,2010,10(47):119-120.

[10]李心科,金元杰.基于灰色預(yù)測理論的軟件缺陷預(yù)測模型研究[J].計算機應(yīng)用與軟件,2009,26(3):101-103.

[11]黃梅.基于改進RANSAC算法的圖像拼接技術(shù)[J].海南大學(xué)學(xué)報：自然科學(xué)版,2011,29(2):172-177.

[12]楊華龍，劉金霞，鄭斌.灰色預(yù)GM(1,1)模型的改進及應(yīng)用[J].數(shù)學(xué)的實踐與認(rèn)識，2011，41(23)：39-46.

[13]Xiang Zhuoyuan,Tang Zhitao.Research of Software Detect Prediction Model Based on Gray Theory[C]//IEEE Management and Service Science2009. USA Washington DC:IEEE Computer Society,2009:20-22.

[14]Zhu Dianqin,Wu Zhongyuan.The Application of Gray-Prediction Theory in the Software Defect Management[C]//IEEE Computational Intelligence and Software Engineering 2009. USA Washington DC: IEEE Computer Society,2009:11-13.

[責(zé)任編輯：祝劍]

Model bug rate prediction based on improved GM(1,1) model

WANG Shuyan, HUANG Weiqing, Sun Jiaze

(School of Computer Science and Technology,Xi’an University of Posts and Telecommunications, Xi’an 710121,China)

The traditional GM (1,1) model performs poorly in the processing of abnormal data containing singular value. An improved model based on RANdom Sample Consensus (RANSAC) algorithm is therefore proposed. The improved model deselect the singular value via RANSAC algorithm, choose the point which make a minimum estimation error as boundary condition, and combine with interpolation to make the prediction of Model Bug Rate(MBR). Results show that the improved model can not only improve the effect of the abnormal value but also get higher accuracy than the GM (1,1) model.

GM(1,1), RANSAC, boundary condition, singular value, MBR

2015-04-02

國家自然科學(xué)基金資助項目(61050003)；陜西省教育廳專項科研計劃資助項目(11JK1037)。

王曙燕(1964-)，女，教授，博士，從事軟件測試、數(shù)據(jù)挖掘研究。E-mail：wsylxj@126.com 黃煒青(1991-)，女，碩士研究生，研究方向為軟件測試。E-mail:372630399@qq.com

10.13682/j.issn.2095-6533.2015.06.015

TP311.52

A

2095-6533(2015)06-0069-06