《软件失效时序数据的灰色拟合及多步预测算法》由会员分享,可在线阅读,更多相关《软件失效时序数据的灰色拟合及多步预测算法(11页珍藏版)》请在金锄头文库上搜索。
1、软件失效时序数据的灰色拟合及多步预测算法 黄雄波 佛山职业技术学院电子信息系 摘 要: 对于软件系统的可靠性模型而言, 其主要功能就是要求能准确地预测出后续的软件失效的发生时间, 研究了软件失效时序数据的灰色拟合问题, 并提出了相应的多步预测改进算法。首先, 基于某一拟合精度的条件下, 应用灰色理论的GM (1, 1) 模型为软件失效时序数据建立相应的分段拟合模型;然后, 以正交多项式函数估算出末段子序列的拟合残差, 并用该估计值对末段子序列的灰色预测模型进行修正和补偿;最后, 基于补偿后的组合预测模型对软件失效的发生时间进行多步预测。实验验证了算法的正确性和有效性。关键词: 软件失效时序数据
2、; 灰色拟合; GM (1, 1) 模型; 多步预测; 作者简介:黄雄波 (1975-) , 男, 博士研究生, 副教授, 主要研究方向:时间序列分析、数字图像处理。收稿日期:2017-11-29基金:佛山职业技术学院校级重点科研项目 (2015KY006) Grey fitting and multi-step prediction algorithm of software failure time series dataHUANG Xiongbo Department of Electronic and Information Engineering, Foshan Profession
3、al Technical College; Abstract: For the reliability model of the software system, its main function is to accurately predict the occurrence of a subsequent software failure time. The paper studies grey fitting problem of the software failure time series data, and proposes the corresponding multi-ste
4、p prediction algorithm. First of all, based on the condition of a fitting accuracy, apply grey theory GM ( 1, 1) model for the software failure time series data to establish the corresponding piecewise fitting model; then, use the orthogonal polynomial function to estimate fitting residual error at
5、the end of the sequence, and utilize the estimate result for correcting and compensating grey prediction model at the end of the sequence; in the end, apply the combined forecasting model based on compensation to realize multi-step projections for the occurrence of software failure time. The experim
6、ent verifies the correctness and effectiveness of the algorithm.Keyword: software failure time series data; grey fitting; GM (1, 1) model; multi-step prediction; Received: 2017-11-290 引言在软件可靠性的分析与建模过程中, 其首要任务就是建立一个精确易用的预测模型, 以便对软件系统的各种可靠状况做出精确的预测。根据预测目标的不同, 软件可靠性的预测模型通常可以分为两种:静态模型和动态模型。其中, 静态模型主要是利用
7、软件系统的各种复杂性参数来预测该软件所隐藏的缺陷总数;而动态模型则是基于软件测试过程中所获得的失效时序数据, 借助数理统计的方法来预测下一次软件失效的发生时间1-3。由于软件失效时序数据较为容易获取, 故动态模型在实际应用中得到了更为广泛的应用。目前, 软件可靠性的动态模型按其使用的建模方法划分, 又可分为统计分析方法和时序数据辨识方法两大类4-5。其中, 统计分析方法是在假设某些条件成立的情况下, 应用特定的函数分布来描述软件失效时间的发生过程。以基于非齐次泊松过程 (non-homogeneous poisson process, NHPP) 的预测方法为例, 由于该类方法具有预测精度高且
8、结构简单的优点, 故其成为软件可靠性的经典统计分析方法6-8。相对地, 时序数据辨识方法则无需指定任何先决条件的假设, 而是利用软件失效时序数据的前后相依关系, 直接将时序数据辨识方法应用于建模研究中。例如, 马飒飒等通过对软件失效时序数据设计提出多尺度分解, 并对分解后所得到的不同数据成分进行单独的建模, 进而得到了一种适应性较好的软件可靠性预测模型9;贾治宇等基于非平稳时序数据辨识方法, 运用自回归积分滑动平均模型 (auto-regressive integrated moving average model, ARIMA) 对软件失效时序数据进行建模, 从而得到了一种简捷易用的软件可靠
9、性预测模型10。此外, 由于时序数据辨识方法在建模过程中能较好地关注了数据的动态特性, 故在辨识精度上较统计分析方法更具有优势。在实际应用中, 用户往往需要预测下一次、甚至后续多次的软件失效的发生时间, 即需要进行多步预测。据此, 本文拟基于分段的灰色预测模型, 设计实现一种具有误差补偿机制的软件失效序列的多步预测算法, 并在软件可靠性评测领域的公开数据集中验证算法的正确性和有效性。1 问题描述软件失效时序数据是指软件系统在规定的环境中其各次无失效运行的持续时间, 以数学的形式进行描述, 有:其中, Y t为一随机变量, 用于记录软件的各次无失效运行的持续时间, t 为正整数。一般地, 如式
10、(1) 所描述的软件失效时序数据通常可以作式 (2) 所示的分解11-13:其中, H t、P t、X t分别为软件失效时序数据的趋势项、周期项和随机噪声项。在实际的辨识建模过程中, 趋势项 Ht、周期项 Pt和随机噪声项 Xt可分别用多项式、正弦谐波及自回归模型 (autoregressive, AR) 来进行拟合, 即有:基于一定的样本数量 n, 便可以通过最小二乘或极大似然等方法估算出式 (3) 中的各有关待定参数, 在此基础上, 令 t=n+1, n+2, , 并代入式 (3) 和式 (2) 进行计算, 便可以预测出该软件系统的下一次及后续多次的无失效运行的持续时间。然而, 随着预测步
11、数的增加, 上述预测模型的预测结果将严重地偏离真实值, 究其原因有:式 (3) 中的各有关待定参数虽然能使已有样本的拟合误差为最小值, 但过多的外延预测造成了预测精度无法保证;另一方面, 随机噪声项的估计值从第二步开始也引用了部分的预测值, 此时, 固有的误差累积效应也加剧了整体预测性能迅速变差。2 灰色分段拟合及多步预测算法的设计针对上述问题, 本文拟设计一种具有误差补偿机制的软件失效时序数据的多步预测算法。算法的主要思想是, 基于灰色理论的 GM (1, 1) 模型为软件失效时序数据 Yt建立合适的分段拟合模型, 并对末段子序列的拟合误差施行正交多项式函数的预测和补偿, 在此基础上, 对软
12、件失效发生时间进行多步预测。2.1 基于 GM (1, 1) 模型的时序数据的分段拟合灰色理论问世以来便引起了国内外众多专家学者的极大关注, 并已在理论和应用上取得了一系列丰富的成果14-15。灰色理论最早应用的预测模型就是 GM (1, 1) 模型, 模型中的第一个数字“1”表示微分方程是一阶的, 第二个数字“1”表示只含有一个变量, 该模型可用如下的微分方程进行描述:其中, a 和 b 为待估参数, 求解上述微分方程的解, 有:为了抵消随机因素的影响, GM (1, 1) 模型通常需要对序列样本进行一次累加生成数 (1-AGO) 的处理, 即如式 (6) 所示:将式 (4) 中的 yt换成
13、 yt, 有:以离散的形式描述式 (7) , 有:式中, 上述的 GM (1, 1) 模型的拟合精度可以利用式 (11) 所示的平均绝对百分误差 (mean absolute percent error, MAPE) 来评价其拟合精度, 具体如下:一般地, 若 MAPE10%, 是属于高精度拟合;若 10%MAPE20%, 则属于良好拟合;当 20%MAPE30%, 仍属于可行拟合, 而 MAPE50%, 即称为错误拟合。事实上, 当样本长度达到一定的数量时, 受数据饱和因素的影响, 此时模型的拟合精度将随着样本长度的增加而变差。针对这一特性, 可根据实际的拟合精度需求, 令 MAPE=, 然
14、后对整个样本序列进行分段划分, 并确保划分后的各子序列其 GM (1, 1) 模型的 MAPE, 从而完成原有序列的灰色分段拟合。2.2 基于正交多项式的拟合误差的补偿如前所述, 基于 GM (1, 1) 模型将可以把软件失效时序数据划分为数段子序列, 易知, 对后续的软件失效发生时间的预测应在末段子序列中设计展开。为进一步提高预测精度, 这里将应用正交多项式函数来估算末段子序列其 GM (1, 1) 模型的拟合残差, 在此基础上, 对原 GM (1, 1) 模型进行补偿, 进而构建具有误差补偿机制的组合预测模型。若软件失效时序数据被划分为 m 段子序列, 令末段子序列 (设该子序列的长度为
15、v) 其 GM (1, 1) 模型的拟合残差序列为 em, 则有:由于在高次多项式的曲线拟合过程中, 往往会遇到病态方程组的求解问题, 据此, 这里将基于正交多项式对上述的残差序列 emt进行拟合。设多项式集合P 0 (t) , P1 (t) , , Pu (t) 是关于点集t 0, t1, , tv的一个正交多项式族, 根据线性模型的最小二乘求解方法以及正交多项式的定义14-15, 有:又根据向量内积的定义, 便可推出如下的矩阵方程:其中, P j (j=0, 1, 2, , u) 为向量p 0 (t) , p1 (t) , , pv (t) 的缩写, (, ) 运算符为 2 向量的内积。求
16、解式 (14) 的矩阵方程, 便可得到正交多项式系数 cj (j=0, 1, , u) , 即:而正交多项式族p 0 (t) , p1 (t) , , pu (t) 则可通过如下的递推关系式得到:式 (16) 中, 2.3 算法的设计研究至此, 可设计得到如下的软件失效时序数据的多步预测算法。算法的步骤内容表述如下。算法名称:软件失效时序数据的多步预测算法输入:长度为 n 的时序数据 Yt, 平均绝对百分误差 MAPE 的阈值 , 各分段子序列的最小样本长度 , 预测步数 step;输出:软件失效序列的各 step 步的预测值。步骤 1 从 Yt的最左端选取 个右邻样本数据构成 Ysubt子序列, p=;步骤 3 利用式 (11) 计算 的平均绝对百分误差 MAPE, 若 MAPE成立, 转步骤 4;否则, 转步骤 5;步骤 4P=P+1, 若 Pn, 向 Ysubt中添加一个右邻样本数据, 转步骤 2;否则, 转步骤 6