作者简介:王电钢(1973— ),国网四川省电力公司信息通信公司教授级高级工程师. 研究方向:电力信息化.E-mail:wang_dg@qq.com
中文责编:坪 梓; 英文责编:木 柯
1)国网四川省电力公司信息通信公司,四川成都 610015; 2) 电子科技大学计算机科学与工程学院,四川成都 611731
1)State Grid Sichuan Electric Power Company Information and Communication Corporation, Chengdu 610015, Sichuan Province, P.R.China 2)School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, Sichuan Province, P.R.China
computer application technology; time series; load forecasting; least square method; auto regressive integrated moving average(ARIMA); classification and regression tree(CART)
DOI: 10.3724/SP.J.1249.2019.03245
主机资源的负载预测对其运营维护工作具有重要意义.传统负载预测方法通常采用线性时间序列模型拟合负载数据,而负载受复杂的内外部环境影响,线性模型无法很好地表征负载数据规律.为提高模型的精度,提出将负载信息分解为线性部分和非线性部分的思想,并将自回归差分滑动平均(autoregressive integrated moving average,ARIMA)模型和分类回归树(classification and regression tree,CART)模型相结合进行预测.通过加权最小二乘法改进的ARIMA预测线性部分,通过边界判定优化的CART预测非线性部分,并结合两者获得综合预测结果.在真实负载数据集下进行对比实验,结果表明,改进后的算法预测精度相比传统方法提高了15%以上,且对偏远值和不同的时间间隔都均有良好的适应性.
The load forecasting of host resources is of great significance to the operation and maintenance work. The traditional load forecasting methods usually use linear model to fit the load data. In the actual operation of equipment, the load is affected by the complex internal and external environment where many nonlinear factors are included. The linear time series model can not well characterize the law of load data. In order to improve the model accuracy, the idea of decomposing the load information into linear part and nonlinear parts is proposed, and the autoregressive integrated moving average(ARIMA)model and the classification and regression tree(CART)model are combined for prediction. Specifically, the ARIMA model improved by the weighted least squares method is used to predict the linear part and the CART optimized by the boundary determination is used to predict the nonlinear part, and the prediction results of the two parts are combined to obtain a comprehensive prediction result. The comparison experiments are carried out on the real load dataset. The results show that the prediction accuracy of the proposed algorithm is improved by more than 15% compared with the traditional method, and it has good adaptability to remote values and different time intervals.
随着业务量的上升,服务器主机上的负载压力不断增大,而长时间处于高负载状态不利于主机设备的稳定运行,需要运维操作人员及时发现并释放资源,这对运维工作带来了困难.虽然现有的运维监控系统中已有对CPU和内存等的监控功能,并可以通过设置告警阈值提醒运维人员,但这种事后处理的方式具有一定滞后性,存在问题处理不及时的风险.因此,对CPU和内存等资源的历史负载信息和波动模式进行分析挖掘,并预测未来一段时间的负载趋势,对于智能化运维工作是极其重要的.负载的趋势预测有助于提高运维工作的预见性,为运维人员制定解决方案提供一定的缓冲期,对于可能出现的问题防患于未然.
对于负载预测的研究,目前主流的方法是利用历史数据建立线性预测模型.然而在实际工作中,主机负载受复杂的内外部环境影响,如温度、网络、业务量和硬件状况等.真实的主机负载信息并不严格满足线性关系,存在一定的非线性部分,而现有的一些方法并未对非线性部分进行预测,预测效果较差.如李刚等[1-3]基于特定范围内的历史数据,采用自回归差分滑动平均(autoregressive integrated moving average,ARIMA)模型来预测未来特定范围的值,可以较好地拟合线性部分,但并未考虑非线性部分,丢失了部分模型精度.此外,虽然部分研究提出不同的参数估计方法来提升模型精度.如单锐等[4-5]提出基于改进谱共轭梯度的ARIMA模型参数估计法,通过调整参数,使得算法满足充分下降条件或者共轭条件,达到优化的目的.张宗华等[6]提出了基于加权改进的AR模型的负载预测,他认为不同时间点对当前时间点的影响不同,离当前时间点距离越近,通常对预测造成更大的影响,应在不同的时间点上分配不同的权值,让影响更大的点拥有更大的权值,减小偏远点的影响,提升精度.上述方法尽管在不同层次上提升了模型对负载数据的预测效果,但是这种提升仅体现在对模型线性部分的预测,并未真正解决数据中非线性部分的预测问题.为此,本研究提出将负载数据分解为线性部分和非线性部分,并分别对两部分进行训练和预测,采用基于加权最小二乘参数估计方法[7]的线性模型ARIMA[8]预测负载数据的线性部分,采用基于Fayyad边界判定[9]优化方法的分类回归树[10-11] (classification and regression tree,CART)模型拟合负载数据的非线性部分,最后将预测结果融合,提升预测精度.
给定数据集D={x1, x2, …, xt}, 其中, xt表示以负载数据作为时间序列时t时刻的负载值,负载预测模型解决的是t时刻后续的多个数据值的预测问题.
ARIMA模型是一种基于时间序列的预测方法,它用某种数学模型将时间和预测对象组成的序列拟合起来.一旦模型确定后,就可以通过这个模型预测未来,被广泛应用在实际中,如就业发展趋势分析、机场客流量预测、疫情分析和负荷预测等.ARIMA模型满足
Φ(B)Δ dxt=Θ(B)εt(1)
其中, Φ(B)=1-φ1B-…-φpBp, Bp为延迟算子,与xt作用后得到xt-p; Δ d=(1-B)d, d为差分次数, φp为自回归系数; Θ(B)=1-θ1B-…-θqBq, θq为移动平滑系数; εt为零均值白噪声序列. 式(1)可简记为
Δ dxt=(Θ(B))/(Φ(B))εt(2)
当模型中心化后,可简写为
xt=φ1xt-1+…+φpxt-p+εt-
θ1εt-1-…-θqεt-q(3)
ARIMA模型的建模步骤如下:
1)首先用ADF[12]单位根检验法判断数据的平稳性.当数据不平稳时,对序列进行差分处理.差分阶数的选取方法一般为将其从1逐渐增大,直至序列满足ADF校验.
ADF单位根检验法:
如果序列经过d阶差分后平稳,不妨设
Φ(B)=∏pi=1(1-λiB),
|λi<1|; i=1, 2, …, p(4)
则
Φ(B)Δ d=[∏pi=1(1-λiB)](1-B)d(5)
由式(5)可知,ARIMA模型共有p+d个根,其中, p个根在单位圆外, d个根在单位圆上.当d≠0时,ARIMA模型不平稳.
2)根据样本自相关函数ACF和偏自相关函数PACF的拖尾性和截尾性来确定p和q值.采用AIC[13]标准,选择使AIC达到最小值的自回归滑动平均模型(autoregressive moving average model,ARMA)进行拟合.AIC标准函数为
AIC=nlnL+2(p+q+1)(6)
其中, L为似然函数.选择最佳p、 q值使得AIC达到最小.
3)估计线性预测模型中参数的值.常用的方法是最小二乘法.
在ARIMA中,记
∂ ^=(φ1, …, φp, θ1, …, θq)'(7)
ft(x; ∂ ^)=φ1xt-1+…+φpxt-p-
θ1εt-1-…-θqεt-q(8)
其中, φi为自回归系数; θi为移动平滑系数; εi为零均值白噪声序列. 则残差项为
σ ^t=xt-f(x, ∂ ^)(9)
当∑nt=1σ ^2t最小时, ∂ ^为最小二乘参数估计值.
4)检验模型的显著性.如果拟合模型未通过检验,则转向步骤2)重新选择模型再拟合,直到残差序列为白噪声为止.
5)利用拟合的模型,预测将来的走势.
CART是一种非线性的分类和回归模型.它能很好地处理高维数据,并筛选出重要的变量,具有良好的可解释性.在机器学习中,利用对象属性和对象值之间的映射关系,可以将回归树作为预测模型.但当训练集太大时,需要多次顺序扫描数据集,因此传统构造回归树的算法效率比较低.本研究对传统CART算法的分裂策略进行了优化.传统CART回归树的训练算法包括2个步骤.
CART的生成是决策树的核心问题之一,决策树的生长是反复分支的过程,当分支没有意义,即分支后结果差异不再显著下降,就不再分组.也就是说,分组的目的是为了使输出变量更加接近.在CART中,为了使预测的效果更好,通常使GINI值更小.GINI值为
GINI=1-∑i∈Ip2i(10)
其中, pi为在样本集中取到分类为Ci的子集的概率; l为子集数量.对于回归树来说,采用均方根误差来确定分法,均方根误差公式为
σ=(∑i∈I(xi-μ)2)1/2=(∑i∈Ix2i-nμ2)1/2(11)
其中, xi为样本值; μ为样本均值; n为样本数量. σ越小,表明预测效果越好.因此要选择使回归方差最小的属性作为分裂方案.
对决策树的精简,是另一个核心问题.回归树的剪枝是为了防止模型过拟合,CART使用CCP[14-15]算法进行剪枝,在训练集上计算表面误差增益率为
α=(R(t)-R(T))/(N(T)-1)(12)
其中, R(t)为结点数t的错误代价,为
R(t)=r(t)p(t)(13)
其中, r(t)为结点t的错分样本率; p(t)为所有样本中落入结点t的样本所占的比例; R(T)为子树T的错误代价; N(T)为子树中的结点数.CCP的剪枝策略为取出最小指标α对应的节点,将其剪掉,生成第1个子树,重复这个过程,直到只剩下根节点时,将其作为最后一个子树.然后利用验证集去验证所有子树,取误差最小的树.
运用组合模型对负载序列进行预测,存在两个关键点:
1)需要通过ARIMA模型较好的拟合序列中存在的线性因素,使序列的线性因素基本提取完全.因此,本研究在传统ARIMA模型参数估计方法上做了优化,采用加权最小二乘估计法来消除异方差性,使得参数估计更加准确,模型拟合更好.
2)当拟合完序列中存在的线性因素后,需要对残差序列的非线性因素进行提取,本研究采用CART来拟合非线性因素,降低了训练时间,并且分类更为简单.
定义wi为滞后i阶的数据的权重,我们认为,残差更大的项占有的权值应该更低,这样能使误差更小.为了消除正负号带来的影响,用残差的平方来表达,即
wi=1/(ε2i)(14)
以此构建对角权重矩阵[16]
W=[wi
wn-p](15)
则∂ ^即为加权最小二乘参数估计值,
∂ ^=(XTW-1X)-1XTWY(16)
其中,W=[xp … x1
xn-1 … xn-p](17)
xi为时间序列; Y为预测时间t前真实值组成的(n-p)×1矩阵.
Fayyad边界点判定与熵[17]有关,其熵越小,对属性进行分类所需的平均信息量就越少.熵值为
I(|C1|,|C2|,…,|Cn|)=-∑ni=1pilog pi(18)
其中, pi表示在样本集中取到分类为Ci的子集的概率. 由于熵值和GINI系数的变化趋势相同,因此,要找到最小GINI系数,只需要找到使平均类熵达到最小的值.由Fayyad边界点判定原理可知,该值在排序后两个相邻异类样本之间.本研究的CART分裂属性为连续属性,所以每次只需要找出一个将属性取平均值后的分界点作为分割阈值,将样本集分为两边,此时,阈值点即为该分界点.此方法并不需要计算每个分割点的GINI系数,大大提升了训练效率.只有当出现属性值达到最小这种不理想情况时,才会与原来的分类次数相同.
通过改进的ARIMA模型得到预测数据和历史数据的线性组合,即式(3).由于εt参数的不可获得性,所以xt的估计值为
(^overx)t=φ1xt-1+…+φpxt-p(19)
当线性因素提取完后,通过式(19)预测时刻t的值(^overx)t, 与真实值相减后得到残差(^overz)t, 即
(^overz)t=yt-(^overx)t(20)
其中, yi是i时刻的观测值; 残差(^overz)t代表负载数据中的非线性部分.
由式(20)得到负载数据的非线性部分后,需要利用改进的CART回归树对滞后期从1到p阶的历史数据进行残差拟合训练,提取序列中的非线性关系,得到拟合更为准确的非线性关系,即
(^overz)t=θ(xt-1, …, xt-p)(21)
最终i时刻的观测值可以表示为
(^overy)t=(^overx)t+(^overz)t(22)
具体算法为:
步骤1:数据预处理,并通过AIC标准确定最优阶数p、 q;
步骤2:通过加权最小二乘参数估计法得到ARIMA的相应参数,得到线性预测模块ARIMA的预测模型;
步骤3:将观测值与预测模型的拟合值作差,得到残差序列;
步骤4:通过步骤一中所定阶数p, 用CART回归树将p个历史数据与对应残差进行训练;
步骤5:结合ARIMA模型和CART模型的预测结果,得到最终结果.
本研究采用不同采样频率的CPU和内存负载数据,采集自某企业真实的主机(表1).算法采用Python实现,实验环境为Windows8.1、Intel Core i7- 4510CPU@2.60 GHz、4 Gbyte内存.
本研究在采样频率为5、10和20 min的CPU负载上进行训练,并预测未来的40个数据,与传统ARIMA模型进行对比,实验结果如图1至图3.
从图1至图3可见,ARIMA+CART组合模型对偏远点的预测均比ARIMA模型准确,整体的预测效果也要比ARIMA模型好.这是由于它预测了负载数据中的非线性部分,更接近实际数据分布.
进一步,以不同采样间隔的内存负载数据分别对ARIMA模型和ARIMA+CART组合模型进行训练并预测,实验结果如图4至图6.
从图4至图6可见,ARIMA+CART组合模型的预测均比ARIMA模型准确,这是由于组合模型拟合了残差中含有的非线性因素,所以比ARIMA更贴近真实值,误差更小.在不同时间间隔的内存利用率数据中,组合模型同样有更好的效果.
为了量化本研究算法的预测精度,我们采用平均绝对误差和作为评价标准,即
(^overσ)=1/t∑ti=1|yi-(^overy)i|(23)
通过分析实验数据,得到ARIMA模型和ARIMA+CART组合模型的负载预测误差,如表2.
从表2可见,ARIMA+CART模型相比ARIMA模型的预测误差有明显降低,预测精度比传统ARIMA模型提高了15%以上,证明了本研究模型的预测精度更高.
本研究提出基于加权参数估计法的ARIMA和CART的组合负载预测模型,较单一线性模型而言,CART解决了负载数据中非线性部分的预测问题,模型预测精度得到明显提升.实验结果证明,本研究模型对一些波动较大的偏远点预测要更优于单一线性模型,这是由于CART对残差的非线性部分的预测弥补了线性模型的缺陷,使得模型的最终预测值要比传统模型更靠近真实值,整体的预测精度提高了15%以上.
深圳大学学报理工版
JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING
(1984年创刊 双月刊)
主 管 深圳大学
主 办 深圳大学
编辑出版 深圳大学学报理工版编辑部
主 编 李清泉
国内发行 深圳市邮电局
国外发行 中国国际图书贸易集团有限公司(北京399信箱)
地 址 北京东黄城根北街16号
邮 编 100717
电 话 0755-26732266
0755-26538306
Email journal@szu.edu.cn
标准刊号 ISSN 1000-2618
CN 44-1401/N