基于改进GM(1,1)模型预测软件缺陷率

王曙燕，黄炜青，孙家泽

(西安邮电大学 计算机学院，陕西 西安710121)

基于改进GM(1,1)模型预测软件缺陷率

王曙燕，黄炜青，孙家泽

(西安邮电大学 计算机学院，陕西 西安710121)

给出一种基于随机抽样一致性算法(RANSAC)的GM(1,1)改进模型。运用RANSAC筛除异常值，选择估计误差最小的点作为定解条件，结合插值思想对软件缺陷率进行预测。分别对有无奇异值的数据预测，结果表明改进后的模型不仅能够改善异常值对预测的影响，而且比GM(1,1)模型取得较高的预测精度。

灰色模型；随机抽样一致性算法；定解条件；异常值；软件缺陷率

软件缺陷是软件产品开发中不可避免的问题，这些缺陷可能导致软件的失效甚至崩溃，而软件缺陷预测技术[1]就可以预测软件系统中可能存在的缺陷数目，以决定软件系统是否稳定、可交付。

目前，软件缺陷预测主要是基于机器学习的，例如利用支持向量机SVM作为二值分类器的软件缺陷预测模型[2]；通过模拟退火技术来改进BP神经网络来建立软件缺陷预测模型[3]；根据Boosting理论，训练基本k-NN预测器建立软件缺陷预测模型[4]。这些方法虽然实现了软件缺陷的预测，但都存在着所需的样本数据量多，计算工作量大的问题。

灰色系统理论(Grey Theory)已广泛应用于社会、经济、科技、农业、生态、生物等各个领域[5]。由该理论建立的GM(M,N)模型即灰色模型，其中1阶，1变量的微分方程模型称为GM(1,1)[6]，该模型可以通过少量的、不完全的信息，建立灰色微分预测模型，用以揭示事物的发展过程，预测其未来的发展规律，属于模糊预测领域中的一支[7]。利用GM(1,1)模型进行预测已十分普遍，以GM(1,1)模型为基础建立了两类离散GM(1,1)模型对软件缺陷进行预测，解决了对于原始数据为非齐次指数序列的预测问题[8]；运用灰色预测模型对ISS历年发现的软件安全缺陷个数进行预测[9]；文献[10]提出一种基于灰色预测理论的软件缺陷率预测模型。但是，上述方法在运用GM(1,1)模型预测时，均未考虑原始数据可能有异常值的出现。而GM(1,1)模型计算参数时，采用最小二乘法求解，一旦数据出现奇异点，结果就会出现问题，导致预测效果较差。因此，本文引入随机抽样一致性算法(RANdom Sample Consensus Algorithm，RANSAC)[11]，筛除异常值，建立软件缺陷率预测模型。

1 GM(1,1)模型概述

灰色系统是对离散序列建立的微分方程，GM(1,1)是一阶微分方程模型，其形式为[7]

(1)

由导数定义知

(2)

当Δt很小并且取为1时，近似的有

(3)

离散表达式为

(4)

(5)

(6)

基于上述机理，GM(1,1)模型的建模过程主要分为数据处理、模型建立和模型检验与预测3步。

步骤1数据处理

设原始数据X(0)={x(0)(1),x(0)(2),…,x(0)(n)}一次累加得到新数列X(1)={x(1)(1),x(1)(2),…,x(1)(n)}

其中

(7)

式中k表示离散化的时间节点，x(1)右上角的数字表示累加的次数，0表示原始数据，1表示经过一次累加，累加完成之后对数字序列进行准光滑性检验[9]

(8)

(9)

其中σ表示数字序列的指数比，若当k>3时，σ(k)∈[1,1.5]成立则准指数规律满足。

如果原始数据序列满足准光滑条件和准指数规律，则可直接建立GM(1,1)预测模型，进行数据预测；如果不满足，则需要对原始数据序列进行二阶弱化算子处理[7]。将弱化后所得的新序列作为新的原始数据，建立GM(1,1)预测模型。

步骤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)

则预测模型为式(13)在式(14)条件下的特解[9]

(15)

(16)

步骤3模型检验

GM(1,1)模型的精度检验[13]一般有相对误差大小检验法、关联度检验法和后验差检验法3种方法。

后验差检验方法主要利用后验差D和最小误差概率p来综合评定预测模型的精度。记残差序列[11]为

(17)

表1 灰色预测精度等级标准

2 模型改进

2.1 基于RANSAC算法优化参数计算

RANSAC算法[11]是一种参数估算方法，其基本思想是将数据分为局内点和局外点，局内点符合一定的模型，而局外点不符合该模型。利用该模型可以进行数据筛选，符合该模型的点也被认为是局内点，不符合模型的点就会被舍弃，找到符合该模型的点之后，结合该点与之前确定的局内点，重新计算模型，用新模型继续验证，直到剔除了所有局外点。RANSAC改进GM(1,1)模型流程如图1所示。

(1) 取向量Y第n和n-1的元素，作为新向量Yn，同理取B中第n行和n-1行的组成子矩阵Bn，依据式(11)由Yn、Bn计算出模型参数a。

(2) 将向量Y第n-2的元素加入Yn中组成新的向量Yn+，同理选取B中第n-2行组成新的子矩阵Bn+，由Yn+、Bn+计算模型参数a1。

(4) 如果a和a1的差异高于一定阈值，则认为新加入的数据是异常值，若异常值处于奇数位置则利用降采样的思想将奇数位置的数据都剔除掉。若处于偶数位置，则原数据中偶数位置的数据均剔除掉。

(5) 算法结束后，由Yn和Bn计算出来的参数即为最后结果。

图1 RANSAC改进模型流程

2.2 择优选择约束条件

假定拟合曲线通过时间序列的第m个点，则定解条件为

(18)

则定解为

(k=1,2,…)。

(19)

假设每一点都是约束条件，即在每个约束条件的基础上都进行预测，预测结果与实际结果之间的误差用来反映该约束条件是否可取，最终选择误差最小的约束条件作为标准约束条件。

在进行预测时，经过RANSAC算法筛选数据，奇数或偶数位置的数据被剔除，由式(19)中的具体参数可计算出部分数据，剩余部分的数据可以利用插值思想，基于已建立的模型，由平移时间节点得到

(k=1,2,…)。

(20)

将两部分计算所得数据，交替按顺序整理可得到最终预测结果。

3 实验与分析

实验在Windows操作系统下利用MATLAB软件进行，利用改进模型分别对软件缺陷率[14](Model Bug Rate,MBR)(表2)数据源在有无奇异值数据情况下进行预测。

表2 MBR统计值

实验1对无奇异值的数据利用改进的GM(1,1)模型进行预测。

由表2数据构建原始序列

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},

数据满足准光滑性以及准指数规律，可以建立GM(1,1)模型。

计算模型参数为

a=0.168 615,b=134.346 193,

表3 MBR统计值与预测值

图2 预测值与实际值结果对比

由图2的结果可看出，在没有异常值的情况下，改进后的模型预测值与实际值相比，相对误差较小，MBR实际值与预测值有较好的拟合性。

实验2对有奇异值的数据进行预测，假设人为的失误将原数据92.5错误记录为925。

现原始序列为

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}

数据仍满足准光滑性以及准指数规律，因此不需弱化直接建立GM(1,1)模型。

当GM(1,1)模型利用最小二乘法求解，计算模型参数

a=0.276 5,b=486.105 6,

预测模型为

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

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

根据式(12)计算得到

利用RANSAC算法选取Yn、Bn，首先分别选取B和Y第6行和第7行数据作为初始值，即

根据式(11)计算出参数a=[0.187 8 295.441 3]

然后将B和Y第5行数据添加到Yn+、Bn+中得到

根据式(11)计算出参数a1，如果a和a1差小于阈值，则令a=a1，并继续按照从后到前的顺序给Yn、Bn中添加新数据，比较新计算的a和a1之间的差异。如果a和a1之间差大于阈值，则新加入的点为奇异点。

在本次实验中，添加第二行数据，即奇异值925所对应的数据时，a和a1差大于阈值，所以判断新加入数据为奇异值。

奇异值处于原始数据第三位置，按照降采样做法将奇数位置的数据舍弃，利用剩余数据计算出模型参数为

a=0.304 0,b=114.043 2,

根据择优选取约束条件的思想，最终选取第二个点为标准约束条件并得到预测模型

后验差D=0.115 0<0.35，最小误差概率p=1>0.95，由表1可知精度等级为一级，实验结果如表4。两种模型预测结果对比如图 3所示。

表4 两种模型预测结果

图3 两种模型预测结果对比

由图3结果可以看出，改进模型预测效果比传统GM(1,1)模型的预测效果更佳准确，几乎与MBR原始统计值一样。改进模型在处理有奇异值的数据时，不仅摒弃掉奇异值的数据，而且还对奇异值位置应有的数据进行了有效的估计。

上述两个实验结果表明，基于RANSAC的GM(1,1)改进模型有较好的预测效果，尤其是在有异常值的情况下，MBR原始的统计值为{102.3, 92.5, 72.0, 64.2, 53.0, 43.9}，改进模型预测值为{102.3, 83.26, 71.52, 61.44, 52.77, 45.33}，与统计值十分接近，而原模型受奇异值影响，预测值为{394.48, 299.16, 226.90, 172.08, 140.50, 98.97}，可以看出与MBR原始的统计值差异过大。改进模型在当前数据下预测准确率可以达到97.4%，改善了原模型不能处理含有奇异值数据的问题。

4 结束语

将RANSAC算法与GM(1,1)模型相结合，选择最小估计误差的点作为定解条件，改善了GM(1,1)模型在预测具有异常值的数据序列问题。在无奇异值和有奇异值的数据上分别进行实验，实验结果表明改进模型能在软件缺陷率记录数据中含有奇异值的情况下进行有效的预测。

[1] 王青,伍书剑,李明树.软件缺陷预测技术[J].软件学报,2008,19(7):1555-1580.

[2] 王涛,李伟华,刘尊,等.基于支持向量机的软件缺陷预测模型[J].西北工业大学学报,2011,29(6):864-869.

[3] 尹然,丁晓明,李小亮,等.基于SA-BP神经网络的软件缺陷预测模型的研究[J].西南师范大学学报：自然科学版,2013,38(8):147-152.

[4] 何亮,宋擒豹,沈钧毅.基于Boosting的集成k-NN软件缺陷预测方法[J].模式识别与人工智能,2012,25(5):792-802.

[5] 王立宏.面向测试过程的软件可信性度量[D].西安：西安邮电大学, 2013:22-24.

[6] 张涛,吴成茂,高向鹏.灰色系统理论在邮政业务预测中的应用[J].西安邮电学院学报,1999,4(2):25-28.

[7] 刘思峰.灰色系统理论及其应用[M].科学出版社,2010:5-40.

[8] 尹红健.两类离散GM(1,1)模型及其软件缺陷预测建模[J].海南大学学报：自然科学版,2010,28(2): 148-152.

[9] 杨俊峰.基于GM(1,1)模型的软件缺陷数预测[J].中国科技信息,2010,10(47):119-120.

[10]李心科,金元杰.基于灰色预测理论的软件缺陷预测模型研究[J].计算机应用与软件,2009,26(3):101-103.

[11]黄梅.基于改进RANSAC算法的图像拼接技术[J].海南大学学报：自然科学版,2011,29(2):172-177.

[12]杨华龙，刘金霞，郑斌.灰色预GM(1,1)模型的改进及应用[J].数学的实践与认识，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.

[责任编辑：祝剑]

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

国家自然科学基金资助项目(61050003)；陕西省教育厅专项科研计划资助项目(11JK1037)。

王曙燕(1964-)，女，教授，博士，从事软件测试、数据挖掘研究。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