一种基于并联组合模型预测站点流量的策略

冯培坤，刘 杰，伍卫国，柴玉香，张祥俊

(1.西安交通大学 软件学院，陕西 西安 710000;2.上海超级计算中心，上海 201203;3.西安交通大学 计算机学院，陕西 西安 710000)

0 引 言

随着互联网的蓬勃发展，硬件成本不断降低，网络带宽得到了大幅提升，在进入Web2.0时代后，Web站点日志增长，同时也伴随着大量的用户日志访问数据。站点流量是网络维护的重要指标，反映着站点运行的状态，对于站点流量进行建模和预测成为了近几年的研究热点。

随着站点业务量的增加和用户的不断积累，网站的网络流量呈现出复杂多变的特点，对站点的流量进行有效的统计和预测，能很好地优化站点的运营和网络管理。用户访问站点的方式都是基于时间序列进行的，根据用户的每一个访问，服务器端都会记录用户的访问数据，其中包含有本次请求的流量大小，根据这些流量值来建立对应的时间序列的流量预测模型。基于时间序列的网络流量预测方法有很多，主要有回归预测模型、卡尔曼滤波模型、神经网络模型和支持向量机模型等[1]。

回归预测模型是一种常见的预测性建模技术，它研究的是因变量(目标)和自变量(预测器)之间的关系[2]。卡尔曼滤波预测模型是一种利用线性系统状态方程，通过系统输入输出观测数据，对系统状态进行最优估计的算法[3]。神经网络是具有自组织、自适应和自学能力的非线性动力学习系统[4-5]。基于支持向量机的模型预测是监督学习中的常见算法，经过长时间的发展，在预测方面引入核函数，在有限的样本信息中，往往能得到比较好的预测效果。下面对涉及到的两种预测模型进行简要介绍。

1 卡尔曼滤波

卡尔曼滤波算法利用多次观察和估计值来达到目的，整个算法是递归进行的，需要多次重复调整。卡尔曼滤波器用于估计离散时间过程的状态变量，记为X(t)，该算法可用线性随机微分方程(linear stochastic difference equation)来描述：

X(t)=AX(t-1)+BU(t)+W(t)

(1)

Z(t)=HX(t)+V(t)

(2)

其中，X(t)是t时刻的系统状态，U(t)是t时刻对系统的控制量，A和B是系统参数，Z(t) 是t时刻的测量值，H是测量系统的参数，W(t)和V(t)分别表示过程和测量的噪声，被假设成高斯白噪声(white Gaussian noise)，其协方差分别是Q和R。

卡尔曼滤波算法的具体过程如下所示：

(1)计算上一状态预测的结果X(t|t-1)。利用系统现有的状态来预测现在时刻状态，得到预测值：

X(t|t-1)=AX(t-1|t-1)+BU(t)

(3)

其中，X(t-1|t-1)是上一状态最优结果，U(t)为现在状态控制量，如果没有控制量即为零。

(2)计算X(t|t-1)对应的协方差P(t|t-1)。系统结果已经更新，更新X(t|t-1)时刻的协方差，用P表示：

P(t|t-1)=AP(t-1|t-1)A`+Q

(4)

其中，P(t-1|t-1)是X(t-1|t-1)对应的协方差，A'表示A的转置矩阵，Q是系统过程的协方差。

(3)计算现在t时刻的最优化估算值X(t|t)。目前为止有了对系统的预测值X(t|t-1)，然后再收集现在状态的测量值，结合预测值和测量值，根据公式计算可以得到现在t时刻的最优估算值：

X(t|t)=X(t|t-1)+Kg(t)(Z(t)-

HX(t|t-1))

(5)

(4)其中Kg为卡尔曼增益(Kalman gain)，其计算公式如下：

Kg(t)=P(t|t-1)H`/[HP(t|t-1)H+R]

(6)

(5)更新t状态下X(t|t)的协方差。到现在为止，得到了t状态下最优的估算值X(t|t)。但是为了让卡尔曼滤波器不断运行下去直到系统过程结束，还要更新t状态下X(t|t)的协方差，也就是对应式(4)中t-1时刻的协方差：

P(t|t)=[ (I-Kg(t))H]P(t|t-1)

(7)

2 支持向量机(SVM)

支持向量机，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解，在遇到线性不可分时，通常是把样例映射到高维空间中，引入核函数来代替非线性函数的内积运算，从而在维数可能为无穷大的线性空间中构造出最优分类超平面，并得到分离器的决策函数[6-7]。在预测领域，SVM的重视程度越来越高，例如：销售量预测、金融股票预测、电力负荷预测，网站业务量预测等[8]。

假定训练数据(x1,y1),…,(xn,yn),x∈Rn,y∈{+1,-1}(x1)可以被一个超平面g(x)=wx+b分开，存在一个最优超平面可以使数据分开并且离超平面最近的向量与超平面之间的距离是最大的，在线性可分时，SVM采用以下函数：

f(x)=sgn(wx+b)

(8)

超平面的参数不唯一，参数对分类结果无影响，故将决策函数值归一化为1，即：

yi(wxi+b)≥1,i=1,2,…,n;yi=-1,1

(9)

(10)

为了便于求解，将上述问题转化为：

(11)

即现在变成线性约束的二次规划问题，对上述的式子进行最优化求解，采用拉格朗日方法，构造拉格朗日函数：

(12)

其中，αi≥0为拉格朗日乘子，分别对w和b求偏微并令它们等于0，可得对偶问题：

(13)

针对上式的对偶问题进行求解，得到w*和b*:

其判别函数为f(x)，带入w*和b*，就可得最终的判别函数表达式：

(14)

对于线性不可分的情况，需要将原始的特征空间映射到高维空间，即x→φ(x)，需要引入核函数K(xi,xj)=φ(xi)Tφ(xj)带入到式(14)，则针对线性不可分的情况，最终的判别函数是：

(15)

从低维到高维所选择的核函数很多，根据Mercer定理，只需要关注K(xi,yi)，而不用在意φ(xi)。

SVM预测模型主要有3个参数：径向基核函数参数σ、惩罚参数C、不敏感损失参数ε[9]。

K折交叉验证常常用来选择SVM合适的参数，将原始数据分成K组(一般是均分)，将每个子集数据分别做一次验证集，其余的K-1组子集数据作为训练集，这样会得到K个模型，用这K个模型最终的验证集的分类准确率的平均数作为此K-CV下分类器的性能指标，K-CV可以有效地避免过学习以及欠学习状态的发生，最后得到的结果也比较具有说服性。

3 并联组合模型

基于时间序列，根据历史日志数据信息，使用并联组合模型，结合SVM和卡尔曼滤波算法来实现流量预测。以下对预测模型设计与实现以及结果分析进行详细介绍。

3.1 流量预测模型

SVM在时间序列预测中具有很好的效果，是优秀的监督学习算法，与此同时，卡尔曼滤波算法简单，可以快速迭代出下一个预测状态值[10]。考虑工业社区日志流量的特点和预测需求等因素，文中在站点网络流量预测模块中，采用卡尔曼滤波算法和SVM预测算法构建并联组合预测模型，为网站的流量预测提供可靠的参考数据。

文中使用RBF函数作为SVM的核函数，因为RBF函数可以将样本非线性规划到更高维的空间中，且核函数的参数较少，模型简单，限制条件少，更易于预测模型的实现。根据第2节的理论技术介绍，使用K折交叉验证，得到SVM最优参数组合：σ=1，C=10，ε=0.2。

文中的流量预测是将日志访问时间作为时间序列{X(t),t=1,2,…,n}，预测模型描述为：

X(t)=φ[X(t-1),X(t-2),…,X(t-p)]

(16)

其中，φ为非线性函数，p为嵌入维数。表示用t时刻的前p个值来预测第t个值。在此处时间间隔的设置不宜太小，太小对于流量预测意义不大，嵌入维度也不应过小或者过大，要考虑实际情况设置，权衡预测的精度和计算量[11]。

对于预测的精度，采用绝对误差(AE)、相对误差(RE)和平均误差率(MAPE)预测指标[12]来衡量，表1为预测的评价指标公式。

表1 预测评价指标

3.2 并联组合模型设计

采用组合算法对网络流量进行预测，弥补传统时间序列模型单一预测[12]的不足。预测模型的组合方式有多种，根据实际情况，文中采用并联组合模型，使用卡尔曼滤波算法和SVM算法来实现组合预测。

并联组合预测是利用两种不同的模型对时间序列进行预测，得到时间序列[13]的基本特征，对各个模型分别赋予合适的权重值，进行组合预测[14]。设计的并联组合模型基本步骤如下：

(1)设原始时间序列为{xt,t=1,2,…,n}，其中n为预测样本个数，第i种预测方法在第t时刻的预测值记为xit，对应方法的预测绝对误差记为eit=|xt-xit|，其中i=1,2，x1t和x2t分别表示卡尔曼预测值和SVM预测值，t为时间间隔，取值为1～n。

(2)令w1和w2分别为预测模型的加权系数[15]，且w1+w2=1，则在t时间的组合预测值为：

(17)

其中，x1t为卡尔曼预测值，x2t为SVM预测值，f(x)分别对应第2节中介绍的预测模型。

minSe

s.tw1+w2=1,wi≥0,i=1,2

(18)

上式为一个二次凸优化问题[16]，即对偶问题，可使用拉格朗日函数来将其转化为线性规划问题，从而确定出非负组合模型最优的权重系数。

基于并联组合预测模型的基本思想，按照上面的步骤，首先根据日志数据中的流量序列来建立预测模型，日志数据分训练数据和测试数据[17]，使用训练数据输入到卡尔曼和SVM预测模型中得到预测的站点网络流量值，分别计算得到绝对误差，针对上述步骤3进行最优化求解确定组合权值，使用测试数据来检验模型预测的精度。确定了组合模型系数后，在第3节日志数据分析模块的站点网络流量预测中，基于时间序列[18]，设计策略模式来进行流量预测。

4 实验及结果分析

实验使用的数据来自于上海超级计算中心的工业社区用户访问数据，当用户访问工业社区站点时，服务器端将记录用户的访问信息，其中包含本次请求的流量值。实验选取其中一部分的访问数据，进行数据清洗和数据统计分析，提取基于时间序列的站点流量数据作为实验数据和测试数据。实验构建Spark streaming流式处理集群来进行日志数据的清洗和统计分析[19]，然后进行并联组合预测模型的建立和实验。

4.1 实验环境

实验环境：搭建数据预处理平台的Hadoop和Spark集群均使用Cloudera提供的cdh5.7.0版本，使用Zookeeper来进行协调服务，提供分布式的可靠协议，构建Hadoop分布式文件系统，采用Spark on Yarn进行部署，进行资源的统一管理。测试环境的操作系统是Windows 10，CPU是Interl(R) Core(TM)i5-7400 CPU @ 3.00 GHz，机器内核为4核，固态硬盘为128 GB，内存大小为8 G。

图1是本次实验的日志数据处理平台架构，对日志数据源进行ETL[20]，在数据处理平台完成原始日志到结构化日志的转化，实现数据清洗和数据分析，然后在此基础上使用流量预测模型实现流量预测。

图1 日志数据处理平台架构

4.2 实验步骤

本实验首先构建站点日志数据处理平台，获取工业社区的日志数据，在处理平台进行数据清洗，整理统计出基于时间序列的流量数据，然后基于历史流量数据，分别根据卡尔曼滤波算法和支持向量机来计算出预测值，对比实际流量值计算权值，构建并联组合模型来实现更为准确的预测[21]。

首先构建站点的日志数据处理平台，搭建分布式集群Hadoop作为底层数据存储，部署Spark on Yarn来实现数据的实时数据处理，对重复的日志数据和非必要的日志数据进行剔除[22]，对空缺的数值进行补全，将原始的日志数据转化为结构化的日志数据，在此基础上，统计日志数据的时间和流量字段[23]，整理后存储HBase数据库中，为下一步提供实验数据。

依据3.2节中的并联组合模型的思路，读取流量数据，分别计算得到卡尔曼滤波和SVM的预测值，对比实际流量值得到绝对误差，建立预测模型，带入具体的数值，通过解决式(18)的二次凸优化的问题，依次得到多个最优权值，然后求均值得到最优的权重比例系数。

图2 并联组合预测流量结构

4.3 结果分析

通过对一段时间的工业社区日志数据进行数据分析和统计，统计出一部分的日志流量值做流量预测模型分析测试数据。在基于3.1和3.2的介绍上，文中采用的是并联组合预测方法，通过解决式(18)中的二次凸规划问题，得到卡尔曼和SVM预测模型的权值为：w1=0.35，w2=0.65。

将w1和w2的值代入卡尔曼和SVM预测模型(式(16))中，可得流量预测结果，选取2018年4月份的日志流量进行预测对比，根据实际值和预测值进行对比，然后分别得到图3～图5的预测折线图。预测模型误差对比如表2所示。

表2 预测模型误差对比

图3 卡尔曼预测

图4 SVM预测

图5 并联组合预测模型流量预测折线

从图3～图5可以看出，其组合预测模型的平均误差率更小，折线拟合效果也更合理，组合预测模型与实际流量值的误差更小，说明组合模型对于流量预测也是可靠有效的。实验表明在预测步长上，随着步长的增加平均误差率也不断增大，相比较长期的来说，短期的误差积累更明显，步长越大对于预测越没有实际意义。

5 结束语

使用站点的用户访问日志数据，通过数据清洗和数据分析处理[24]，利用其中的流量值来构建并联组合预测模型以实现站点的流量预测。使用分布式技术，集合Hadoop和Spark来实现日志数据的实时处理，保证历史流量值能及时结构化存储，然后基于历史流量数据来建立并联组合预测模型，分别使用卡尔曼滤波算法和支持向量机进行最优化找到合适的权值，然后基于实时的流量处理数据进行实时预测。

下一步将集成新的预测算法，实现细粒度[25]的站点流量预测，并考虑站点的环境因素来进一步提升预测方法的准确性，提升该模型的精度。