一种应用于话务量预测的分段在线支持向量回归方法

摘要

应用于话务量预测的分段在线支持向量回归方法，它涉及一种在线支持向量回归方法，本发明针对在线支持向量回归(Online Support Vector Regression)算法难以兼顾预测精度和运行效率，提出一种分段支持向量回归时间序列预测方法，通过缩减在线建模数据长度实现快速训练，并对Online SVR进行分段存储，根据预测邻域样本与各子分段支持向量回归模型的匹配度，选取最优子分段模型预测输出，提高预测精度。该算法在保持在线预测执行效率的同时，相比普通在线支持向量回归算法，可提高预测精度5％～10％。算法由于采用了分段的策略，并采取了较小的建模数据长度，算法效率高。可以实现对于移动通信话务量时间序列的在线、实时和快速建模和预测。

说明书

技术领域

本发明涉及一种在线支持向量回归方法，具体涉及一种应用于移动通信话务量时间序列预测的分段在线支持向量回归方法。

背景技术

随着计算机科学技术的不断发展，知识和数据的获取变得越来越容易，呈爆炸性增长，有效挖掘已知数据、提取数据特征和通过已知序列进行未来状态的预测，使得数据挖掘变成时下的热点问题之一，与此同时，预测技术成为时间序列数据挖掘的重点内容，吸引越来越多研究者的关注。

移动通信话务量的大小在一定程度上体现了话音信道被占用的强度。移动通信话务量数据预测对于移动网络的维护以及移动通信的决策具有重要的价值，如果能够及时、准确地预测话务网络的流量，就能够有效减少网络维护费用，提高网络运行质量。

目前，时间序列分析和预测技术是进行移动通信话务量数据的分析和预测的一种有效方法。随着预测时间序列渐趋复杂，尤其对于复杂的非线性、非平稳时间序列，传统统计学的AR、ARMA等方法很难获得令人满意的结果。加之，在线实时预测的应用需求也逐渐增加，使得人工智能技术中的神经网络、模糊逻辑等离线建模方法很难取得实效的应用。

近年，采用在线支持向量回归(Online Support Vector Regression，OnlineSVR)进行时间序列预测的研究十分广泛。由于其算法简单、不存在局部最小、维数灾难和泛化能力强等优点，在时间序列预测方面取得很好的效果。SVR建立在统计学习理论和结构风险最小化原理基础上，能够较好地解决小样本、非线性、高维数和局部极小等实际问题，但是一般的Online SVR(比如增量学习算法、减量学习算法、AOSVR等)方法在获得良好预测效果的同时，由于其算法复杂度较高，其执行效率往往无法满足实际应用的需求。

在实际应用中，话务量涵盖了大量的小区数据，且历史积累的话务数据量也很丰富，这就需要预测的方法具有很高的效率，而且不同的小区、不同的区域、不同时段话务量都会呈现不同的变化特性，因此对预测模型的实时更新的特性提出很高的要求。

在线支持向量回归进行时间序列预测的基本原理：

对于时间序列数据(x₁，y₁)，(x₂，y₂)，…，(x_l，y_l)，x_i，y_i∈R，构造回归函数(预测函数)为：

f(x)＝W^Tφ(x)+b                          (1)

式(1)中，w^T∈Rⁿ，b∈R，Φ(·)把输入样本从输入空间映射到高维特征空间，通过优化问题求解w和b。

$\underset{w,b}{\min }P=\frac{1}{2}{\left|\right|w\left|\right|}^2+C\underset{i=1}{\overset{l}{\Sigma }}({\xi }_i+{\xi }_i^{*}).---\left(2\right)$

式(2)的约束条件为：

((w□x_i)+b)-y_i≤ε+ξ_i，i＝1，2，...，l，

y_i-((w□x_i)+b)≤ε+ξ_i，i＝1，2，...，l，

${\xi }_i^{*}\ge 0,i=\mathrm{1,2},...,l,$

ξ和ξ^*为松弛变量，C为惩罚参数，ε为不敏感损失函数；转换上述问题的Lagrange优化问题：

$\underset{\alpha ,{\alpha }^i}{\min }\frac{1}{2}\underset{i}{\overset{l}{\Sigma }}\underset{j}{\overset{l}{\Sigma }}{Q}_{\mathrm{ij}}({\alpha }_i-{\alpha }_i^{*})({\alpha }_j-{\alpha }_j^{*})+ϵ\underset{i}{\overset{l}{\Sigma }}({\alpha }_i+{\alpha }_i^{*})-\underset{i}{\overset{l}{\Sigma }}{y}_i({\alpha }_i-{\alpha }_i^{*})---\left(3\right)$

式(3)需满足以下条件：

$\underset{i=1}{\overset{l}{\Sigma }}({\alpha }_i-{\alpha }_i^{*})=0,$

$0\le {\alpha }_i,{\alpha }_i^{*}\le \frac{C}{l},i=\mathrm{1,2},...,l$

定义核函数Q_ij＝φ(x_i)^Tφ(x_j)＝K(x_i，x_j)，对于回归函数(预测函数)f(x)＝W^Tφ(x)+b表达为：

$f\left(x\right)=\underset{i=1}{\overset{l}{\Sigma }}({\alpha }_i-{\alpha }_i^{*})K(x_i,x)+b---\left(4\right)$

按照KKT(Karush-Kuhn-Tucker)定理，可以得到样本x_i的边界函数：

$\left(\begin{array}{cc}h\left(x_i\right)\ge ϵ,& {\theta }_i=-C\\ h\left(x_i\right)=ϵ,& -C<{\theta }_i=0\\ -ϵ\le h\left(x_i\right)\le ϵ,& {\theta }_i=0\\ h\left(x_i\right)=ϵ,& 0<{\theta }_i=C\\ h\left(x_i\right)\le -ϵ,& {\theta }_i=C\end{array}\right)---\left(5\right)$

其中：

${\theta }_i={\alpha }_i-{\alpha }_i^{*}$

$h\left(x\right)\equiv f\left(x_i\right)-y_i=\underset{j=1}{\overset{l}{\Sigma }}{Q}_{\mathrm{ij}}{\theta }_j-y_i+b$

根据式(5)，将训练数据集划分为三个子集：错误支持向量集E＝{i||θ_i|＝C}(Error Support vectors)、边缘支持向量集S＝{i|0＜|θ_i|＜C}(Margin support vectors)和保留样本集R＝{i|θ_i＝0}(Remaining samples)。

普通离线SVR训练是对数据集一次或者批量选取进行训练，获得模型后再进行预测，而Online SVR是随着在线数据的更新而不断进行训练、不断优化的过程，应用较多的在线学习算法就是增量学习算法和减量学习算法。

假设现有一个新的样本x_c加入到训练集中，此时需要加入θ_c，并计算各个θ_i(i＝1，2，...，n)和θ_c的更新值Δθ_i及Δθ_c以使得所有的样本均满足KKT条件。

$\mathrm{\Delta h}\left(x_i\right)=K(x_i,x_c)\Delta {\theta }_c+\underset{i=1}{\overset{n}{\Sigma }}K(x_i,x_j)\Delta {\theta }_j+\mathrm{\Delta b}---\left(6\right)$

又因为

${\theta }_c+\underset{i=1}{\overset{n}{\Sigma }}{\theta }_i=0---\left(7\right)$

对集合S，可得：

$\underset{j\in S}{\Sigma }K(x_i,x_j)\Delta {\theta }_j+\mathrm{\Delta b}=-K(x_i,x_c)\Delta {\theta }_c$

$\underset{j\in S}{\Sigma }\Delta {\theta }_j=-\Delta {\theta }_c---\left(8\right)$

i∈S

如果定义集合S中样本的下标集为$S=\{s_1,s_2,...,s_{l_s}\},$则(8)式可以表示为矩阵形式：

由上式(9)可得：

由上面推导可得：

由式(8)～(11)实现SVR在线训练，从而实现S、E和R集的更新。应用减量训练算法从训练样本集中去除一个数据样本与上面过程类似。

在线支持向量回归虽然解决了模型动态更新的问题，能够实现时间序列的在线建模和预测。但是，从算法的流程上分析，当训练数据集更新时，增量(或减量)训练算法对所有的Lagrange乘子进行更新，并涉及大规模矩阵的求逆，因此，算法的计算复杂度仍然较高。另一方面，如果选取的训练数据集规模很大，算法在进行模型更新、训练和预测过程中，效率会下降比较明显。

图1选取不同建模长度进行在线时间序列预测(移动通信话务量数据)获得的建模长度与算法运行时间的关系。从图1可知，如果达到较好的建模预测效率(较短的算法执行时间)，必须降低在线建模数据长度。

图2(移动通信话务量预测实验)说明了在选取确定参数的条件下，采用更大规模的建模数据长度，可以获得更好的预测精度。

采用Online SVR算法进行时间序列预测过程中，算法效率和所预测的精度处于矛盾中，样本规模的持续增加，致使每次在线进行模型更新过程中涉及的运算量增加，从而导致算法运行速度的下降；而如果采用较少的建模预测数据长度，OnlineSVR模型所能记录的数据历史知识或模式过于有限，从而致使算法泛化能力下降，从而导致预测精度下降。

发明内容

本发明为了解决在移动通信话务量预测中，采用在线支持向量回归方法进行时间序列预测时，在提高预测效率的同时，其预测精度会有所降低的问题，提供了一种应用于话务量时间序列预测的分段在线支持向量回归方法。

本发明的设计构思：根据上述试验结果和分析(图1和图2)，提高算法执行效率最为直接的方式就是缩减在线建模数据样本的规模，同时采用一种方式来弥补对于建模数据规模过短损失历史知识而降低预测精度。为此，在进行Online SVR在线学习和模型更新的同时，应用分段存储的策略，以细化分段的方式对Online SVR历史模型进行逐个存储。而在预测时，选择多个子分段模型中最适合的分段模型进行预测输出。

分段在线支持向量回归(Segmental Online SVR，简记为SOSVR)算法的原理如图3所示原理框图。

本发明为解决上述技术问题采取的技术方案是：

本发明所述应用于话务量时间序列预测的分段在线支持向量回归方法包括如下步骤：

步骤一、数据预处理：将时间序列数据转换进行相空间重构，使之符合设定的嵌入维数EmbededDimension；

步骤二、Online SVR初始化训练：采用支持向量回归增量算法对完成步骤一的数据进行训练，获得初始Online SVR模型；

步骤三、对于在线更新的样本序列(x_c，y_c)，采用支持向量回归增量算法进行在线训练；

步骤四、判断在线支持向量回归是否满足分段条件SGP：若满足分段条件SGP，则执行步骤五；否则，执行步骤六；

步骤五、赋值新子分段模型SOSVR(s)＝OnlineSVR，s＝s+1，并存储；s代表子分段模型的序号；用SOSVR表示分段在线支持向量回归；

步骤六、Online SVR预测输出值PredictfY(i)；i为预测的步数；

步骤七、SOSVR预测输出PredictSY(s，i)：s代表子分段模型的序号，i为预测的步数，以下同；

步骤八、判断步骤七中所述的SOSVR预测输出Pr edictSY(s，i)是否符合最优预测输出条件SBPP，如果符合，则执行步骤九；否则，执行步骤十；

步骤九、预测最终值Pr edictL(i)＝Pr edictSY(s，i)；

步骤十、预测最终值Pr edictL(i)＝Pr edictfY(i)；

步骤十一、判断子分段模型是否符合子分段模型更新条件UpdateSOSVR(l)，l∈(1，2，...，s)，若符合，执行步骤十二；否则，执行步骤十三；

步骤十二、删减按照子分段模型更新条件选定的子分段模型SOSVR(l)，l∈(1，2，...，s)；

步骤十三、删掉最远点历史数据，并采用支持向量回归减量算法训练OnlineSVR；

步骤十四、数据在线更新，并重复步骤三～步骤十三。

本发明的有益效果是：针对在线时间序列预测问题，提出一种分段支持向量回归在线时间序列预测方法，算法采用支持向量回归增量学习算法进行Online SVR训练，通过缩减建模数据长度实现在线快速训练，并对Online SVR模型进行分段存储，根据待预测邻域时间序列与各子分段模型的匹配度，选取最优的子分段模型预测输出，提高算法预测精度。既避免了由于样本数量增加导致的增量在线学习效率的下降，又通过分段策略保存了样本的历史知识，执行效率和预测精度得到提高。本文提出的算法在中国移动黑龙江有限公司实际话务量数据的预测中取得很好的应用效果。实验结果表明，该算法在保持在线预测执行效率的同时，可通过分段提高预测精度5％～10％。由于采用了较小的建模数据长度，算法效率得以提高。可以实现对于时间序列的在线、实时、快速预测。

附图说明

图1为Online SVR时间序列预测中在线建模数据长度与算法执行时间关系图；图2Online SVR时间序列预测中在线建模数据长度与预测精度关系图；图3分段在线支持向量回归算法(本发明)时间序列预测算法原理框图(对Online SVR模型进行分段，划分为多个子分段支持向量回归模型，通过模式匹配选择最优子分段模型预测输出)，图4是本发明程序流程图；图5a是基于分段支持向量回归算法对移动通信话务量数据进行预测实验结果图(繁华商业区，话务小区编号HUAM28A)，图5b是基于分段支持向量回归算法对移动通信话务量数据进行预测实验结果图(高等院校，话务小区编号HCAD26C)，图5c是基于分段支持向量回归算法对移动通信话务量数据进行预测实验结果图(居民住宅区，话务小区编号HOA026B)，图5d是基于分段支持向量回归算法对移动通信话务量数据进行预测实验结果图(交通主干线，话务小区编号HPA001A)。

具体实施方式

具体实施方式一：

一种应用于话务量时间序列预测的分段在线支持向量回归方法：

定义：在线支持向量回归模型Online SVR，惩罚参数C，不敏感损失系数ε，核函数类型KernelType，核函数参数p，子分段模型SOSVR(s)，s＝1，2，3...，初始训练集长度TrainLength，分段条件SGP，选择最优子分段模型预测输出条件SBPP，分段更新机制UpdateSOSVR(l)，l∈(1，2，...，s)，嵌入维数EmbededDimension；

输出：第i步预测值PredictL(i)，时间序列真实值Test(i)；

如图3和图4所示，本发明所述方法包括如下步骤：

步骤一、数据预处理：将时间序列数据转换进行相空间重构，使之符合设定的嵌入维数EmbededDimension；

步骤二、Online SVR初始化训练：采用支持向量回归增量算法对完成步骤一的数据进行训练，获得初始Online SVR模型；

步骤三、对于在线更新的样本序列(x_c，y_c)，采用支持向量回归增量算法进行在线训练；

步骤四、判断在线支持向量回归是否满足分段条件SGP：若满足分段条件SGP，则执行步骤五；否则，执行步骤六；

步骤五、赋值新子分段模型SOSVR(s)＝OnlineSVR，s＝s+1，并存储；s代表子分段模型的序号；用SOSVR表示分段在线支持向量回归；

步骤六、Online SVR预测输出值PredictfY(i)；i为预测的步数；

步骤七、SOSVR预测输出PredictSY(s，i)：s代表子分段模型的序号，i为预测的步数，以下同；

步骤八、判断步骤七中所述的SOSVR预测输出Pr edictSY(s，i)是否符合最优预测输出条件SBPP，如果符合，则执行步骤九；否则，执行步骤十；

步骤九、预测最终值Pr edictL(i)＝Pr edictSY(s，i)；

步骤十、预测最终值Pr edictL(i)＝Pr edictfY(i)；

步骤十一、判断子分段模型是否符合子分段模型更新条件UpdateSOSVR(l)，l∈(1，2，...，s)，若符合，执行步骤十二；否则，执行步骤十三；

步骤十二、删减按照子分段模型更新条件选定的子分段模型SOSVR(l)，l∈(1，2，...，s)；

步骤十三、删掉最远点历史数据，并采用支持向量回归减量算法训练OnlineSVR；

步骤十四、数据在线更新，并重复步骤三～步骤十三。

具体实施方式二：本实施方式在步骤四中所述分段条件SGP用于保证分段的条件能够最大效率地保存数据集的历史知识，使得各个子分段SOSVR模型差异最大化，增强模型的泛化能力。其它步骤与具体实施方式一相同。

具体实施方式三：本实施方式在步骤四中，采用聚类的方法作为分段条件，使得每个子分段SOSVR(s)适应不同特性的子时间序列段。其它步骤与具体实施方式一或二相同。

具体实施方式四：本实施方式在步骤四中，比较子分段模型SOSVR(s)之间的相似度(如欧式距离)，定义SOSVR(s)相似性度量SM(s)，若SM(s)-SM(s-1)＞P，P为设定相似性度量阈值，以相邻子分段SOSVR相似度值超出阈值作为分段条件。其它步骤与具体实施方式一或二相同。

具体实施方式五：本实施方式在步骤四中，根据支持向量SV变化情况作为分段条件，如两个相邻子分段支持模型的支持向量SV_SOSVR(s)∩SV_SOSVR(s-1)＜Q作为分段条件，即相邻SOSVR相同支持向量数少于阈值。其它步骤与具体实施方式一或二相同。

具体实施方式六：本实施方式在步骤四中，采用等分方法进行分段，即在线训练数据长度TrainLength＞L时进行分段。其它步骤与具体实施方式一或二相同。

具体实施方式七：本实施方式在步骤八中，最优预测输出条件SBPP是按照待预测序列邻域D(x_i，y_i)，i＝1，2，...，N各个子分段模型SOSVR(k)，k∈(1，2，...，s)的匹配度作为选择子分段模型预测输出的条件；可以选择子分段模型满足上一步预测误差最小，如下式：

min(Error(i-1)＝SOSVR_Predict(k，i-1)-Test(i-1))，k＝1，2，...s

式中SOSVR_Predict(k，i-1)为第i-1步中第k个子分段模型预测值，Test(i-1)为第i-1步序列实际值。其它步骤与具体实施方式一相同。

具体实施方式八：本实施方式在步骤八中，按照样本邻域序列与各个子分段SOSVR(k)，k∈(1，2，...，s)支持向量的核空间欧式距离最小作为最优预测输出条件。其它步骤与具体实施方式一或七相同。

具体实施方式九：本实施方式在步骤十一中，子分段模型更新UpdateSOSVR(l)，l∈(1，2，...，s)是为了选择出需要删减的子分段模型，实现对子分段模型进行更新，以避免存储效率下降和存储溢出；若子分段模型数量到达预设的阈值，则选择抛弃应用较少或删减相似的子分段模型。其它步骤与具体实施方式一相同。

具体实施方式十：本实施方式按照模型预测输出次数删除应用最少的子分段模型；或删除产生最早的子分段模型；还可以进行子分段模型模式匹配，合并相似度较高的子分段模型；如果预测步数不大或连续预测过程中所获得的子分段模型数量在可承受范围之内，也可不进行更新。其它步骤与具体实施方式九相同。

本发明所述方法的实验验证与应用

应用SOSVR进行移动通信网络话务量数据预测，实现对于话务量数据的快速预测。实验所用数据为中国移动黑龙江有限公司提供的话务量数据，话务量数据以文件形式提供，每个文件中以1小时为采集间隔，包含全省所有小区一天24小时共约500000条记录。数据属性包括记录时间、小区名称、话务量、信道拥塞率、切换成功率等。实验中仅选用话务量作为预测对象，单位是爱尔兰(erl)。一般以一定的时间尺度(一般是小时)进行采集和计算的话务量数据序列。

图5a～图5d是采用SOSVR算法进行四种类型移动通信话务量小区预测的结果(168个小时连续预测，移动基站：繁华商业区——话务小区编号HUAM28A、高等院校——话务小区编号HCAD26C、居民住宅区——话务小区编号HOA026B、交通主干线——话务小区编号HPA001A)。实验中SVR参数选取统一的、通过实验比较所选择的、适合一般预测的参数，而子分段模型最优预测输出条件SBPP采用上一步模型预测误差最小确定，即：

min(abs(SOSVR_Predict(i-1)-Test(i-1)))

式中SOSVR_Predict(i-1)为各个分分段SOSVR(s)第i-1步预测值，Test(i-1)为第i-1步实际序列值。

为了说明算法的适应性和一般性，采用AOSVR、Incremental SVR(采用增量训练的Online SVR算法)和本文提出的SOSVR，进行四类典型话务小区一周话务量的连续预测，实验环境选择Matlab。为全面比较算法的预测性能，采用两种性能评价标准：平均绝对误差(Mean Absolute Error，MAE)和规范化均方根误差(NormalizedRoot Mean Square Error，NRMSE)。

SOSVR与其它算法预测实验(一步预测，连续预测一周话务量20080713～20080719)的综合比较的情况如表1所示。相同参数条件下，综合比较各种在线支持向量回归算法的预测精度和执行效率。

表1算法预测性能比较表

从实验结果来看，由于未采用减量学习，单独的Incremental SVR受样本规模逐渐增加，表中Incremental SVR的执行时间相比于AOSVR、SOSVR，效率明显低，虽然在预测精度方面相比占优，但是对于实际应用并不是十分适合。

而对比AOSVR和本文提出的SOSVR算法，由于算法在流程上比较相近，只是在预测输出的策略上有所差异，因此，两种算法在建模数据长度相同的条件下，其执行效率比近乎一致。而由于采用较小的初始建模长度，可实现快速在线预测。而SOSVR采用了分段建模、选取最优子分段模型预测输出，其预测精度指标相比AOSVR要高，从四类典型的话务量小区预测结果上来看，预测误差MAE、NRMSE要比AOSVR降低约5％～10％。

如果以预测精度大致相同的条件下对算法的效率进行比较，表2为AOSVR和SOSVR算法执行效率对比的情况。

表2算法执行效率对比表

如表2，SOSVR与AOSVR算法在预测精度基本一致的条件下，本文所提出算法的执行效率相比SOSVR提高50％以上，究其原因，由于算法采用分段策略很好地保留了话务量时间序列的历史知识，相应地，通过在线建模和预测数据规模的减小，大大地提高了算法预测的执行效率。

从算法复杂度方面进行分析，在线学习的算法复杂度为O(m²)，m为在线训练数据集的样本数，在相同的预测精度条件下，如果SOSVR算法建模序列长度减小为AOSVR的70％，则其算法复杂度相应会降低约50％，对应地，算法效率会提高约50％。

SOSVR算法由于采用在线训练数据建模长度较小，所以预测具有很好的实时性，能够符合实际应用的需求。

验证结论

分段在线支持向量回归算法的快速时间序列预测方法，通过采用分段存储策略，利用选择最优子分段SVR模型进行预测，从而在保持算法具有很高的效率的情况下，进一步提高了算法预测精度。从基于移动通信话务量数据的实际应用实验上来看，算法较Online SVR算法在执行速度不变的条件下，能够使得算法的精度提高5％以上；如果在精度大致一致的条件下，算法的执行效率会至少提高50％。SOSVR算法在综合性能上优于基于增量学习和减量学习的普通Online SVR。