基于相空间重构和PSO-SVM的大型商场网络流量预测①

李子乔, 陈华亮

(安徽理工大学电气与信息工程学院,安徽 淮南 232001)

0 引 言

移动通信技术得到了高速度和高质量的发展,互联网给我们的日常生活带来了越来越多的便利,这也使得我们的生活和移动网络紧密相连。对于一些人员密集的场所,急速增长的流量会给其网络架构带来极大的压力,导致上网速度大幅度降低,用户无法进行正常通话以及上网。对人流量大的场景进行网络流量预测,可以让运营商提前知道网络流量的需求,提前做好网络保障工作以应对有可能出现的网络堵塞。

网络流量受到多方面因素所影响,其自身具备不确定性、时变性、非线性等多个特点[1]。当前对于流量预测的方法有很多种,主要分为线性和非线性两大类。但是由于网络流量实际上是一种复杂的非线性系统,传统的一些线性预测模型对其的预测效果就难以得到保证。所以,非线性模型就得到了迅速发展。支持向量机(Support Vector Machine,SVM)就是一种典型的非线性模型[2,3],这一模型实现的基础是统计学习理论,并具有良好的非线性拟合能力。该学习方法采用结构风险最小化准则代替了以往的经验风险最小化的学习原理[4],对于模型在小样本情况下的泛化能力有了很大的提高。与其他传统预测模型相比,不存在收敛速度慢,陷入局部极值的缺陷。在相同条件下,一般在预测上会获得比神经网络更优的效果。

但是经研究表明,若想保证SVM的预测性能达到更加优越的效果,首先要解决的问题就是参数的选择。一般来说,常被纳入考虑的几个参数如下:不敏感损失系数ε,惩罚系数C以及核函数中的参数g。目前,对于SVM参数的优化选择问题,最常被使用到的方法是交叉验证法(Crossvalidation,K-CV),但这种方法需要耗费大量的时间。这一方法的具体步骤如下:先对C和g进行研究,让这两个参数在给定的合适范围内进行取值。在进行完第一步之后,对于取定的C和g,把训练集作为原始数据集并利用K-CV方法得到在此组C和g下训练集验证回归拟合的准确率,接着将多组取值结果进行比较,最终取使得训练集验证回归拟合准确率最高的那组C和g作为最佳的参数。近年来,在参数选择问题上,智能算法被广泛使用。与交叉验证的方法相比,遗传算法(Genetic Algorithms,GA)耗时更少,并且可以很好地获得最优解,但是遗传算法的操作很困难,对于不同的最优解问题需要分别进行选择、交叉和变异三个步骤。为了提高模型预测的精度,和选择更加合适的参数,提出一种用粒子群算法(Particle Swarm Optimization,PSO)优化支持向量机参数的网络流量预测模型(PSO-SVM)。

1 SVM原理

支持向量机最初在分类问题这一研究领域上起到了很大作用[5],但随着不断的创新,它的原理也被扩展到了回归和预测的任务。为了利用SVM解决回归拟合方面的问题,Vapnik等人[6]在对SVM分类问题进行了一系列研究后,在这一问题的基础上引入了ε不敏感损失函数,从而得到了一种新的模型,即回归型支持向量机(Support Vector Machine for Regression,SVR),且在各类问题上取得了很好的性能和预测效果[7]。

和支持向量机在分类上有所不同的是,在回归拟合的问题上,最终实现的是对非线性问题进行线性化处理,以期达到所需要的目标。具体的处理方式可以简述为通过非线性变换,将输入数据映射到高维特征空间,在高维空间求解最优决策函数时,用核函数相关理论代替空间中的点积运算[8],有效避免了一系列需要进行复杂计算的步骤。然后在特征空间中进行线性回归,从而解决样本空间中的非线性回归问题。

设含有l个训练样本的训练集样本对为{(x i,y i),i=1,2,...,l},其中,x i（x i∈R d） 是第i个训练样本的输入列向量x i=［xi1,xi2,...,xi d］T,y i∈R为对应的输出值。SVM算法通过以下函数估计预测值:

式(1)中:Φ（x）表示从输入空间到高维特征空间的非线性映射函数,w是输入(仅支持向量)对输出的权重,b是偏差向量。

定义ε为线性不敏感损失函数,则有:

式(2)中:f（x）为回归函数返回的预测值;y为对应的真实值。

类似于SVM分类情况,并基于结构风险最小化理论,为了使优化问题有解,引入了松弛变量ξi,ξ*i。进一步,SVM回归模型可以表示为:

式(3)中:C为惩罚因子,它决定了对一个错误情况将给予多少惩罚,C越大表示对训练误差大于ε的样本惩罚越大;ε是用于计算经验风险或损失的不敏感损失函数,其不光可以决定支持向量的数目,除此之外还规定了回归函数的误差要求,ε越小表示回归函数的误差越小。

为了解决式(3)中的凸二次优化问题,将引入拉格朗日乘子α,目的是为了将该非线性规划问题转换成对偶形式:

式(4)中:K（x i,y i）=Φ（x i）Φ（x j）为SVM的核函数。求解上式,可以得到非线性回归函数为:

核函数可以使非线性样本数据能够被映射到高维空间中去,并使之成为线性可分的,而且在非线性计算的情况下更容易达到预测的效果,此外还可以有效地避免维数灾害[9]。因此,选择合适、有效的核函数就变得十分重要。常用的核函数如下:

(1)线性核函数:

(2)多项式核函数:

(3)径向基核函数:

基于核函数的性能和计算的复杂程度,选取径向基核函数为模型中的核函数,其中γ(g)是核函数参数。

因此,在模型中,有两个重要的参数会影响到SVM的学习性能,即核函数参数g和惩罚参数C,两者很大程度上决定了SVM的预测性能和泛化能力。因此,为了避免因主观经验选取参数的盲目性和不确定性,这里采用粒子群算法(PSO)对参数的选择进行优化。

2 PSO算法

作为一种群体智能的优化算法,粒子群算法是由Kennedy和Eberhart在1995年提出的。这是一种受鸟类觅食过程启发的进化算法,是用于解决全局优化问题的一系列基于群体智能的方法中的一员,当然也具有进化算法的启发式和随机搜索的特点。粒子群算法从搜索空间中粒子群体的随机初始化开始,这些粒子是初始模型的可行解,进而再对群体中粒子的社会行为进行研究。通过在搜索空间中的学习更新,调整每个个体的轨迹,不断修改可行解,使其朝着自己的最佳位置和整个群体中的最佳位置移动,在经过多次的迭代过程后,找到全局最佳解。毫无疑问,被选为最佳状态的标准取决于目标函数的适合度,适合度是通过计算要解决的问题的目标函数来评估的。

假设有一个由n个粒子组成的群体,在一个D维的搜索空间以一定的速度飞行。在给定的时间t内,第i个粒子当前位置和速度表示为:

和

其位置和速度都被限制在一定的区间内［-Xmax,Xmax］,［-Vmax,Vmax］。每个粒子的最佳位置被称为局部最佳,表示为:P i=［P i1,P i2,...,P iD］T,每一代所有粒子的最佳位 置被称为全局最佳,表示为:P g=［P g1,P g2,...,P g D］T。

那么第i个粒子在迭代次数k+1时的位置和速度可以通过以下等式计算:

式(6),(7)中:ω为惯性权重,其值为非负,影响整体优化能力;k为当前迭代次数;c1和c2是非负的常数,称为加速度因子,r1和r2是正态分布下［0,1］区间上的随机数。

3 相空间重构

因为采用的网络流量数据在空间上是一组一维的时间序列数据,且具有混沌性,因此还需要对原始数据进行相空间重构以得到预测模型中所需要的嵌入维数m的值和延迟变量τ的值,从而达到使预测精度更高的目的。对于一组网络流量时间序列d1,d2,...,d N,其中的N为这组序列的长度,根据选取的m和τ,可以构造成一个新的m维的相空间。

式(8)中:i=1,2,...,N-（m-1）τ。

接着就可以得到SVM中的预测样本集。输入样本集和输出样本集如下列矩阵所示:

确定m的方法有虚假邻点法、关联积分法等;确定τ的方法有自相关函数法、互信息法等方法[10]。上述方法各有其优缺点,但都是对于这两个系数分别进行求参,选择C-C方法以确定m和τ的值。该方法承认了m和τ之间所具有的关联性,通过两者之间的关联积分来得到时延序列的最优延迟τd和数据依赖的最大时间τw。延迟时间τd起到的作用是确保d i之间可以相互依赖,但不会依赖于m。与之不同的是,时间窗口τw对m有很大的依赖作用,且本身的值会随着m的值而发生变化。C-C方法主要是利用了统计结果,以获取所需要的参数的值,因此不需要进行大量的计算,且实现方式较为简单。这一方法的计算过程如下:

取m=1,2,...,k;r i=i×0.5σ;n=1,2,...,j,σ为时间序列标准差,参数计算所用的公式如下:

式(11)-(13)中,（）和（t）可以反映时间延迟序列中的自相关特征。

对于（t）图像中的第一个局部极小值或者（）图像第一次过零点所对应的t可以用来做最优延迟时间τ。将（t）和（t）综合考虑,最佳嵌入窗τw可以通过S cor（t）图像的全局极小值所对应的t来得到。根据下式可以得到最佳的嵌入维数m。

4 PSO-SVM流量预测模型构建

1)初始化:随机设定初始粒子和粒子群速度。

2)计算粒子适应度的值,本模型选取训练样本预测结果的均方根误差(RMSE)作为粒子的适应度函数。RMSE函数的表达式如下:

式(15)中:表示网络流量数据的实际值,y i表示为模型的预测值。最终得到的预测结果中,如果RMSE越小,则粒子更优,即选取的参数更加合适,最后的预测模型精度就越高。

3)根据适应度计算结果,设置个体最佳值和群体最佳值。

4)更新粒子的位置和速度,计算公式如式(6)和(7)。

5)更新适应度的值。

6)更新个体最佳值和群体最佳值。

7)重复以上步骤4到6,直到满足终止条件。

8)将得到的优化参数用于SVM以完成预测的任务。具体流程图如图1所示。

图1 PSO-SVM网络流量预测流程

5 仿真实验

5.1 数据来源

为了验证模型预测效果的有效性,采用淮南移动公司采集到的2020年4月24日零点开始,每隔15min采集一次,共1595组万达广场的网络流量数据,如图2所示。采用MATLAB2018a进行编程实现算法。

图2 网络流量原始数据

5.2 数据预处理

由于实际网络流量数据变化波动较大,并无较强的规律性,如果数据之间差异较大,会降低模型的预测性能。为了减小输入数据之间的差异,在进行训练之前应对网络流量初始数据进行归一化处理,将其归一化到［0,1］区间之内,具体如下:

式(16)中:x表示网络流量数据的初始值,xmax和xmin分别表示数据组中的最大值和最小值。

5.3 学习样本构建

在模型中,运用C-C方法得到的（t）和S cor（t）变化曲线如图3所示。

图3Δ（t）和S cor（t）变化曲线图

由图3(a)可以看出,当（t）取第一个局部极小值时,所对应的横坐标为12,即延迟变量τ的值取12。接着根据图3(b),得到当S cor（t）取得全局极小值时,对应的横坐标为96,即τw的值为96。再代入式(14)进行计算,得到嵌入维数m的值为9。

5.4 SVM参数的确定

在进行参数优化之前,首先要对PSO算法中的参数值和参数范围进行设置。具体的参数值如下:粒子群规模为20;最大的迭代次数为200;加速度因子c1=1.5,c2=1.7;c的取值范围设置为［0.1,100］,g的取值范围设置为［0.01,1000］。

寻优过程结束后,会分别得到三组所需要的参数的值。如表1所示,是三种方法分别进行优化后所得到的参数的值。

表1 各算法优化SVM的参数选择结果

5.5 模型的对比与分析

利用得到的τ和m进行相空间重构后,原始数据构成了1499组输入和输出所对应的新数据集,将前面1200组数据作为训练样本,后面299组数据作为测试样本。然后将PSO优化后的参数代入SVM预测模型继续训练模型。

在预测算法的参数优化过程中,寻优算法的适应度函数选取了RMSE,即在此过程中,模型的性能评估方法所采用的是比较RMSE的值。为了更加客观且避免片面地对各种模型的预测性能进行比较,最后采取均方根误差(RMSE)和相关系数(r2)作为预测模型的性能评价指标。RMSE的计算方法已在式(15)中提到过,r2的计算公式如下:

一个好的分类或回归模型,不仅在训练集中的误差小,而且在测试集中的误差也要小。选取的流量预测模型中,更关注的是在测试集上的预测性能,即预测数据和真实值的拟合程度。如表2所示,是几种预测模型在测试集和训练集上分别对应的评价指标的值。

表2 模型预测结果对比

从表2中可以看出,PSO-SVM预测模型在测试集上的均方根误差和相关系数分别为0.0027和99.966%,对比于另外两种预测模型,有着较好的体现。因此,经PSO优化的SVM模型相较于其他两种预测模型具有更好的预测能力,其最终的预测曲线如图4所示。

图4 PSO-SVM流量预测模型拟合结果

6 结 语

研究了一种基于相空间重构后的PSO-SVM移动流量高效预测模型。以淮南万达广场网络流量数据为案例,通过对样本数据的相空间重构,进而详细地对比、分析了采用不同参数优化方法时SVM对蜂窝流量数据的预测性能。实验中,SVM的最优参数的搜索,采取了三种寻优算法,分别是PSO,GA和CV。实验结果表明,相空间重构后的PSO-SVM预测模型相较于另外两种预测模型,在预测精度上有着明显提升。这意味着本次采用的流量预测方法,不仅能允许运营商提前做好准备以应对即将到来的网络拥堵,提高服务质量,还可以指导网络运营商合理地配置网络资源,节约能源,有效地降低运营成本。