基于支持向量机免疫集成预测的电信网络性能监控
郭建华1, 杨海东2
(1. 广东技术师范学院 计算机科学学院,广东 广州,510665;
2. 广东工业大学 机电工程学院,广东 广州,510090)
摘要:为实现持续有效的电信网络性能监控,提出一种改进的支持向量机预测基线法。利用人工免疫网络优化支持向量机参数、核函数参数、嵌入维数和样本规模等回归分析的自由参数,提出支持向量机免疫集成预测算法。根据电信网络性能的周期性特点构建同点时间序列模型,以预测的置信区间为基线对电信网络性能进行监控,通过对某软交换服务器的CPU负荷进行实验分析。研究结果表明:与经验自由参数相比,支持向量机免疫集成预测算法能取得更加精确的回归模式,其误差平方和减少55.4%,同点时间序列模型能有效克服连续时间序列中存在的异常输入敏感问题,准确发现多个连续的异常点。
关键词:电信网络;性能监控;支持向量机;人工免疫系统;时间序列预测
中图分类号:TP183,TP393 文献标志码:A 文章编号:1672-7207(2012)03-1020-07
Telecom networks performance monitoring based on artificial immune support vector regression
GUO Jian-hua1, YANG Hai-dong2
(1. School of Computer Science, Guangdong Polytechnic Normal University, Guangzhou 510665, China;
2. School of Mechatronics Engineering, Guangdong University of Technology, Guangzhou 510090, China)
Abstract: To continuously monitor telecom network performance, an improved baseline generating method based on support vector machine (SVM) was proposed. An artificial immune support vector regression algorithm (AI-SVR) was presented, which optimized SVM parameters, kernel radius, embedding dimension and sample size by artificial immune network. The same point time series was built according to the cycle of telecom network performance and the baseline for telecom networks performance monitoring was defined as the predicted confidence interval. Taking the CPU load of a certain softswitch server for analysis, the results show that AI-SVR can obtained a better regression mode than SVR with experienced parameters, the sum of error squares decreases by 55.4%, and the same point time series can overcome the problem that the output is sensitive to the abnormal input when using continuous series, and the monitoring method can find a few continuous anomalies.
Key words: telecom network; performance monitoring; support vector machine; artificial immune system; time series prediction
电信网络性能监控是主动发现问题,保障客户感知的有效手段。它定时采集关键网络性能指标(如话务量、CPU负荷和接通率等),通过观察和分析,及时发现异常的网络性能状态,进而快速定位故障点并修复故障[1]。下一代电信运营管理系统中强调问题的生命周期管理[2],而对性能异常的持续监控能力是性能问题生命周期管理的基础。电信网络性能监控主要通过基线和容忍线来判断性能是否异常,基线包括上基线和下基线,两者共同描述一个性能指标的正常波动范围,而基线外延一定比例则形成容忍线,1个性能指标如果不在容忍线范围之内,则被认为是异常状态,监控系统需要产生性能告警信号。实际应用较为广泛的是静态基线法和统计基线法。静态基线法根据经验设置不随时间变化的固定基线,该方法不能发现性能的突然变化,容易产生误警和漏警,持续监控能力较弱。统计基线法通过历史数据的概率统计获取不同时间点的置信区间作为基线,该方法的不足在于:随着网络性能的发展变化,统计基线很快就会失效,持续监控能力有限。预测基线法[3]是一种新型的基线获取方法,可持续地、动态地获取基线,有着较强的自适应能力和持续监控能力。预测基线法的关键是构建合适的数据模型,并采用合适的回归分析方法获得有效的回归模式。连续时间序列模型是预测中被广为采用的数据模型,但该数据模型对异常点输入比较敏感,输入向量包含异常点时其输出往往也是异常的,从而产生误警,降低了持续监控能力。回归分析方法上,支持向量机(SVM)时间序列预测有着较强的泛化能力,是产生基线的有效方法,于艳华等[4]验证了该法的有效性。SVM的自由参数对预测精度影响较大,自由参数的选取也是一个优化问题。SVM的自由参数主要包括精度参数ε、惩罚参数C、径向基核函数半径γ等。Cherkassky等[5]提出训练样本归一化处理后各参数的经验公式,但该经验公式缺乏理论依据,并不适用于所有场合。Cristianini等[6]提出利用核矩阵和核校准来优化γ,该法有一定的理论基础,但整个过程包含多个优化问题,计算比较复杂。研究者提出用粒子群算法[7]、网格搜索法[8]、遗传算法[9]和人工免疫算 法[10]来寻优C和γ,但是ε未纳入优化范围,优化算法的效率也有待进一步提高。此外,时间序列预测在训练样本构建时需要考虑嵌入维数和样本规模,两者对SVM的参数也会产生影响,也应作为自由参数与SVM参数一起优化,而目前尚未发现将两者纳入优化参数的报道。在此,本文作者以实现持续有效的电信网络性能监控为目标,针对SVM自由参数优化和数据模型对异常输入敏感等问题进行改进,提出一种以支持向量机免疫集成预测算法(AI-SVR)和同点时间序列数据模型为基础的监控方法。
1 支持向量机免疫集成预测算法的提出
回归分析预测的基本原理是从历史数据中挖掘出输入向量x与输出变量y之间的回归模式(即函数关系)f,再使用当前的输入向量xf求得预测值yf =f(xf)。本文提出的支持向量机免疫集成预测算法、人工免疫算法在高维空间上有着强大的全局寻优能力,SVM免疫集成算法以回归模式为抗原,以回归过程的自由参数为抗体,通过克隆选择和免疫网络调节来获取最佳的自由参数组合。
1.1 支持向量机预测的自由参数分析
使用ε-不敏感损失函数建立的支持向量回归机算法描述如下[11]。
(1) 构建训练集,其中,,i=1, …, l。
(2) 选择适当的精度参数ε,惩罚参数C,适当的核K(xi,xj)。
(3) 求解最优化问题:
得到最优解;
(4) 构造回归模式:
选择位于开区间的或,则
或者
只有对应的拉氏乘子满足条件,输入xi才对f(x)有影响,且f(x)也完全由这些输入向量决定,所以这些向量被称为支持向量。
精度参数ε和惩罚参数C是SVR的自由参数,ε的含义是:当x点的观察值y与预测值f(x)之差不超过预设的ε时,即认为该点的预测值f(x)是无损失的。经验风险最小化和置信区间最小化是2个互相矛盾的目标,惩罚参数C起着调和两者的作用,C越大意味着越强调最小化经验风险。
核K(xi,xj)代表实现输入空间到特征空间的映射,常用的核函数有线性核函数、多项式核函数、径向基核函数和Sigmoid核函数等,需要根据特征空间的特点来选取。常用的径向基核函数如下:
其中:γ为高斯分布的宽度。
参数γ控制着函数的径向作用范围,反映非线性映射的本质。当径向基核函数取较小的γ时,其性能类似多项式核函数;当径向基核函数取较大的γ时,其性能类似线性核函数。所以,对于无先验知识的数据集,核函数首选径向基核函数[12],此时,γ也是向量回归(SVR)的自由参数。
电信网络性能预测属于时间序列预测,样本的嵌入维数m和样本规模l也属于自由参数,对于时间序列预测而言,训练集规模并非越大越好,太旧的样本点可能会成为训练样本的噪声,但目前尚无选取l的方法。嵌入维数m在自回归移动平均等线性时间序列预测中,常用最终预测误差[13]法确定,但对于非线性序列预测尚无成熟方法。
可见:在电信网络性能预测中,需要确定的自由参数包括:精度参数ε、惩罚参数C、径向基核函数高斯分布宽度γ、样本规模l和嵌入维数m。
1.2 支持向量机回归模式的性能评价
回归模式关注的是对于未来的输入,其预测值与观察值的接近程度。在评估回归模式时,一般构造一个与训练集不相交的测试集来验证。对于时间序列预测,选择最近的一部分数据作为测试集,其他的作为训练集。根据回归分析的无偏性和最小方差性评价原则,测试误差的平均值和标准差可以作为回归模式的评价指标,而误差平方和能综合评价无偏性和最小方差性,并且其变化比误差平均值和标准差更灵敏,因此误差平方和更适合作为评价指标,误差平方和的计算如:
其中:为输出的预测值;yt为输出的观察值;et为误差;Se为误差平方和;k为测试集规模。
在时间序列预测中,自相关是评价回归模式性能的1个主要指标。回归模式应尽量降低自相关性,才能获得可信的区间预测,自相关一般用1阶自相关系数来衡量,即:
|r|越接近1,则自相关程度越高,回归模式应尽量使误差分布接近白噪声状态。因此,基于r和Se进一步建立1个综合评价指标,
其中:q侧重指数。q=1表示r和Se同等重要;q>1表示侧重于采用无偏性和最小方差性评价准则;q<1表示侧重于采用自相关评价准则。
1.3 支持向量机免疫集成
采用文献[14]中人工免疫网络优化算法来集成支持向量机,以SVR的自由参数编码为抗体,以生成的回归模式为抗原,以回归模式的综合评价指标Pe的相反数为抗体亲和力,获取优化的自由参数组合。
算法首先根据问题确定各自由参数的数值范围,并将其编码为抗体,各自由参数占据一定长度的编码段,而根据抗体编码段按照式(10)译码可还原自由参数,如:
其中:di,ui和li分别为第i个自由参数的下限值、上限值和编码长度。
抗体亲和力评价抗体对于抗原的匹配程度,其计算如下:将抗体译码为自由参数,根据l和m组织训练样本,以C,ε和σ为参数运行SVR模型,产生回归模式,使用测试集计算回归模式的综合评价指标Pe,Pe的相反数即为抗体亲和力。
抗体间亲和力评价两抗体之间的相似程度,取2个抗体的海明码距离。
算法中的过程参数预先设定最大迭代次数g、最优抗体连续相同次数gc、抗体群规模N、克隆数Nc、记忆数Nm、变异概率Pm、压缩阈值σs和新生抗体率d。算法过程描述如下。
步骤1 随机产生初始抗体,构成初始抗体群。
步骤2 当迭代次数没有达到g,并且最优抗体连续相同次数没有达到gc时进行迭代。
(1) 计算抗体群中各抗体的亲和力;
(2) 对每个抗体产生Nc个克隆抗体;
(3) 按照变异概率Pm变异克隆抗体;
(4) 计算克隆抗体的亲和力;
(5) 若克隆抗体的亲和力大于其父抗体,则在抗体种群中用其替代父抗体;
(6) 免疫抑制,除Nm个亲和力最高的抗体,将抗体间亲和力小于压缩阈值σs的抗体从抗体群中删除;
(7) 随机产生N×d个抗体,进入抗体群,返回步骤2;
步骤3 停止循环,输出最优自由参数组合及SVR的回归模式。
虽然AI-SVR也带过程参数,但这些参数均可通过经验设置,并对最终收敛结果无显著影响。
2 电信网络性能同点序列数据模型的提出
时间序列预测广为采用的连续时间序列模型是以连续采集点按照时间排序组成的数列。其训练集的构建如[4]:
,
其中:X为输入矩阵;Y为输出向量;l为训练集规模;m为嵌入维数;t为训练用时间序列中的最后时间点。
性能监控中的基线期望能描述性能指标正常的波动范围,连续时间序列模型虽然能产生出比较精确的回归模式,但是有异常点作为输入时,其预测值也可能是异常的,以此生成的基线容易产生误警和漏警。许多电信网络性能指标,如CPU负荷和话务量,正常情况下其短期的变化趋势是连续的,而其长期的变化则具有显著的周期性,性能指标随着用户的作息规律一般以1 d为周期有规律地变化,每天同一时间段的性能值波动较小,本文针对电信网络性能指标的这一周期性特点,提出同点时间序列数据模型。同点时间序列定义为相同采集时间点(如上午10:00)按照采集日期排序组成的数列,构建训练集时,其输出向量与连续时间序列相同,而其输入向量则由与输出同点的连续m天数据序列构成,即
,
其中:n为1 d中采集的时间点数,如每小时采集1次,则n=24。
为了便于区分,按照连续时间序列和同点时间序列构建的训练集分别成为连续训练集和同点训练集。以连续训练集和同点训练集产生的回归模式分别称为连续回归模式fc和同点回归模式fs。构建1个规模为l的连续训练集和同点训练集分别需要l+m和l+nm个连续样本点。电信网络的异常事件一般会持续多个性能采集周期,性能异常点持续出现的概率比较大,因此连续时间序列中,输入向量包含多个异常点的概率也会较大。而同点时间序列的数据点比较分散,输入向量同时包含多个异常点的概率会比较小,因此,在回归和预测时,同点训练集比连续训练集稳定,同点回归模式预测时受单一输入的影响不会有连续回归模式那么敏感。
3 基于测试误差的性能基线计算
假设测试集误差呈正态分布,即,则预测值yt也服从正态分布,如。当测试样本规模足够大(一般假定大于50),则可以用测试集的方差来估计总体方差,构建统计量z*,如:
给定显著性水平α,则概率
即
其中:和分别为一定置信度1-α时的下基线值和上基线值,Zα/2查正态分布表获取,如给定置信度1-α=95%, 查正态分布表得Z0.05/2=1.96。
4 实验分析
以某移动通信运营商的软交换服务器10 min统计的CPU负荷为例,分别以AI-SVR和带经验参数的SVR获取回归模式,通过比较,验证前者获取优化回归模式的能力。然后,模拟性能监控过程,验证其基线的可用性和持续监控能力。
4.1 AI-SVR与SVR的比较分析
交换设备的CPU负荷综合反映了电信网络的性能状态,是性能监控中的主要指标之一,实验时选择某一软交换服务器,获取其7 d内10 min统计的CPU负荷(1 d中采集的时间点数为144)进行预测和监控分析。回归分析时数据均做归一化处理,提取其最近1 d的数据作为测试集,训练集则根据训练集规模和嵌入维数在其余样本上构建,分别构建连续训练集和同点训练集。
根据样本特征,实验时采用38位二进制数依次对l,m,C,ε和γ编码,抗体编码表如表1所示。
表1 抗体编码表
Table 1 Antibody coding table
关于SVR的经验参数,训练集规模l=200, 嵌入维数m见文献[4],m=7。精度参数ε和惩罚参数C据文献[5]中的经验公式计算。径向基函数的核函数的宽度γ=0.5。AI-SVR回归时,设定最大迭代次数g=10,抗体群规模N=20,克隆数Nc=5,记忆数Nm=5,变异概率Pm=0.2,压缩阈值σs=5和新生抗体率d=30%,回归模式综合评价指标中侧重指数q=1,初始抗体群中包含由经验参数编码的抗体。预测时按照嵌入维数,利用预测时间点前的数据构建输入向量,输入向量全部由观察值组成,不包含预测数据,即预测数据全是1次预测结果。这2种算法的自由参数组合和预测性结果如表2所示。由表2可知:AI-SVR获得的自由参数与经验参数差别很大。AI-SVR获得回归模式,其测试集的r、Se和Pe等评价指标均显著比带经验参数的SVR的小,对于同点回归模式,AI-SVR的误差平方和比SVR减少55.4%,证明AI-SVR能获得比经验参数更优的回归模式。
AI-SVR和SVR各自的同点回归模式在测试集上的预测曲线和观察曲线如图1所示。
由图1可知:AI-SVR的预测曲线比SVR更接近于观察曲线,并且变化相对平缓,进一步说明了AI-SVR能获得比经验参数更优的回归模式。
4.2 性能监控实验
以CPU负荷的一段实测数据来模拟监控实验,监控样本集的规模为288(2 d),已知其中包含13个异常点,其中有11个连续的异常点,表现为CPU负荷持续过低,表示某一服务意外终止较长一段时间,2个随机分布的异常点,表现为CPU负荷突然过高或过低,表示短暂的服务故障。采用AI-SVR获得的回归模式,分别采用连续回归模式和同点回归模式进行监控,基线计算时,容忍度取0,置信度为95%,按照式(15)计算,2种模式的监控曲线如图2所示。
从图2可见:其预测线与观察线非常接近,当观察线上有异常点时,预测线的下一个预测点将预测出与前一个观察点非常接近的值。连续回归模式监控时能正确检测出2个随机异常点,但是其后的2个正常点也被误检为异常点,对于连续的异常点,仅检测出第1个异常点,其后的异常点均漏检,其后的首个正常点却被误检为异常点。另外,还产生了其他3个误检点。表明连续回归模式的预测对于最近异常点的输入非常敏感,容易产生误检,而对连续异常点则容易产生漏检。
表2 AI-SVR和SVR的自由参数表和预测性能
Table 2 Free parameters and predicted performance of AI-SVR and SVR
图1 2010年AI-SVR和SVR的预测曲线图
Fig.1 Predicted curves of AI-SVR and SVR at 2010
图2 2010年软交换服务器CPU负荷监控曲线
Fig.2 Monitoring curves of CPU load of softswitch server at 2010
观察同点回归模式,其预测线比连续回归模式的预测线要平滑,其预测值接近于正常状态时的值。当有异常点输入时,其预测值所受影响较小,同点回归模式正确检测出全部13个异常点,没有误检点。表明其检测性能要明显优于连续回归模式,特别是能正确检测出连续的异常点,具有较强的持续监控能力。连续的异常点实际反映的是一个性能问题,其首个异常点的出现和最后异常点的消失正好反映了对应性能问题的生命周期,因此,能较好地支持性能问题的生命周期管理。
5 结论
(1) 给出了AI-SVR算法,利用人工免疫网络优化支持向量机参数、核函数参数、嵌入维数和样本规模等回归分析的自由参数。
(2) 定义了电信网络性能同点序列数据模型及其与连续时间序列数据模型的区别。
(3) 实验验证了AI-SVR比带经验参数的SVR能获得更加精确的回归模式, AI-SVR同点回归模式的误差平方和比SVR的小55.4%。
(4) 实验验证了基于AI-SVR和同点时间序列数据模型的电信网络性能监控方法具备持续监控能力,能支持对性能问题的生命周期管理。
参考文献:
[1] Telemanagment Forum GB 922 Release 3.1, Shared Information/Data (SID) Model-Physical Resource [S].
[2] Telemanagment Forum GB 921 Concepts and Principles_V8.1, Business Process Framework_Enhanced Telecom Operations Map? (eTOM) Concepts and Principles [S].
[3] Ho L L, Cavuto D J, Papavassiliou S, et al. Adaptive and automated detection of service anomalies in transaction-oriented WAN's network analysis, algorithms, implementation, and deployment[J]. IEEE Journal of Seletected Areas in Communications, 2000, 18(5): 744-757.
[4] 于艳华, 宋俊德. 一种基于异常点检测的电信网络性能监控策略[J]. 电子与信息学报, 2009, 31(9): 2220-2224.
YU Yan-hua, SONG Jun-de. A mechanism of telecommunication network performance monitoring based on anomaly detection[J]. Journal of Electronics & Information Technology, 2009, 31(9): 2220-2224.
[5] Cherkassky V, Yunqian M. Practical selection of SVM parameters and noise estimationfor SVM regression[J]. Neural Networks, 2004, 17: 113-126.
[6] Cristianini N, Kandola J, Elisseeff A. On kernel target alignment[C]//Advances in Neural Information Processing Systems 14. Cambridge, MA: MIT Press, 2002: 367-373
[7] 武优西, 郭磊, 柴欣,等. 基于优化算法的核函数参数选择的研究[J]. 计算机应用与软件, 2010, 27(1): 137-140.
WU You-xi, GUO Lei, CHAI Xin, et al. On parameter selection of kernel function based on optimization algorithm[J] .Computer Application and Software, 2010, 27(1): 137-140.
[8] 王兴玲, 李占斌. 基于网格搜索的支持向量机核函数参数的确定[J]. 中国海洋大学学报, 2005, 35(5): 859-862.
WANG Xing-ling, LI Zhan-bin. Identifying the parameters of the kernel function in support vector machines based on the grid-search method[J]. Periodical of Ocean University of China, 2005, 35(5): 859-862.
[9] 吴景龙, 杨淑霞, 刘承水. 基于遗传算法优化参数的支持向量机短期负荷预测方法[J]. 中南大学学报: 自然科学版, 2009, 40(1): 180-184.
WU Jing-long, YANG Shu-xia, LIU Cheng-shui. Parameter selection for support vector machines based on genetic algorithms to short term-term power load forcasting[J]. Journal of Central South University: Science and Technology, 2009, 40(1): 180-184.
[10] 杨福刚. 基于人工免疫算法的最小二乘支持向量机参数优化算法[J]. 计算机应用研究, 2010, 27(5): 1702-1704.
YANG Fu-Gang. Method for optimizing parameters of least squares supportvector machine based on artificial immune algorithm[J]. Application Research of Computers, 2010, 27(5): 1702-1704.
[11] Vapnik V M. The nature of statistical learning theory[M]. 2nd ed. New York: Springer-Verlag Press, 2000: 138-146.
[12] Schlkopf B, Smola A. Learning with kernels: support vector machines, regularization and beyond[R]. Cambridge, MA: MIT Press, 2002.
[13] Akaike H. Fitting autoregressive models for prediction[J]. Annals of the Institute of Statistical Mathematics, 1969, 21: 243-247.
[14] Castro L N, Timmis J. An Artificial Immune Network for Multimodal Function Optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation (CEC'02). Hawaii, USA: 2002: 674-699.
(编辑 邓履翔)
收稿日期:2011-08-23;修回日期:2011-09-18
基金项目:国家自然科学基金资助项目( 60973132 );广东高校优秀青年创新人才培育项目(LYM09097)
通信作者:郭建华(1972-),男,湖南涟源人,博士,副教授,从事电信网络管理,人工免疫系统和信息安全研究;电话:020-38256730;E-mail: gjh209@163.com