在线临近支持向量回归机算法

吴 青，李明明，李飞燕

(西安邮电大学 自动化学院，陕西 西安 710121)

时间序列预测方法可以根据收集到的历史数据建模，从而预测未来某一时刻或时段内可能的结果，它是动态系统建模技术的核心方法之一[1-2]。特别是在多步超前预测过程中，应用时间序列预测方法能够根据在时间序列中观察到的规律预测未来多步的可能结果[3]，对于动态系统建模研究越来越重要[4-5]。

经典的时间序列预测方法有平均数法、指数平滑法和季节性趋势法等，但是，这些方法被应用于预测自然界中大量存在的非线性、非平稳的复杂数据时，泛化性能较差[6-7]。为了改善经典时间序列预测方法存在的问题，研究者们提出了神经网络方法。在实际应用中发现，神经网络方法具有不错的逼近能力，但是，也存在着过拟合以及容易陷入局部最优解等问题[8]。

针对神经网络方法存在的不足，研究者们开始将支持向量机[9](Support Vector Machine,SVM)技术应用于时间序列预测和动态系统建模过程中。Vapnik等人提出的SVM技术[9]是一种基于统计学习理论的机器学习方法，其克服了传统分类方法的一些缺点，当被应用于处理小样本、高维度、局部极小值等问题时，具有较好的泛化性能，但是，SVM的模型最后均需要转化为一个二次规划问题，计算复杂度较高。为了提高算法的效率，一方面，可以采用序列最小优化(Sequential Minimal Optimization，SMO)算法、Chunking算法和Osuna算法等算法对模型求解，以提高模型的训练速度[10]。另一方面，针对在训练时由于样本冗余所造成的计算效率低下问题，可以根据数据集中支持向量的分布特性，利用Fisher判别方法缩减训练样本的数量，从而提升算法的运算速度[11]。

为了将SVM拓展到回归问题中，Vapnik等人引入不敏感损失函数，提出了支持向量回归机[12](Support Vector Regression，SVR)算法。近年来，SVR被广泛应用于各种回归问题中，包括天气预测、股票市场和房地产定价等，并展现出了较好的预测性能[13]，但是，SVR算法的运算速度较慢。

为了进一步提高算法的速度，Suykens等在SVM方法的基础上，提出了最小二乘支持向量机[14](Least Square Support Vector Machine,LS-SVM)算法。LS-SVM算法将经典SVM算法中的损失函数替换为平方损失，把约束条件中的不等号变为等号，并最终通过求解一个优化方程组来得到原始问题的最优解，这个过程避免了复杂的二次规划问题，极大地降低了计算成本。另外，Fung等[15]提出了临近支持向量机(Proximal Support Vector Machine,PSVM)算法。PSVM的原理是将两类样本尽量集中在两个平行超平面附近，并使得两个类别的超平面间隔最大化，与LS-SVM算法相同，PSVM算法同样避免了求解二次规划问题，通过直接求解线性方程组，极大地提高了算法的训练速度。杜等[16]将PSVM算法推广到处理回归问题中，提出了临近支持向量回归机(Proximal Support Vector Machine Regression,PSVR)算法，并利用人工数据集与真实数据集验证了PSVR算法的预测性能。为了实现基于SVR算法的在线序列预测，文献[17]提出在线支持向量回归机(Online Support Vector Machine Regression,OL-SVR)算法，其核心思想是在训练过程中，通过增加新样本并删除旧样本来更新现有的样本数据，但是，这种思路导致训练速度较慢。为了提高训练速度，文献[18]在最小二乘支持向量回归机(Least Square Support Vector Regression,LS-SVR)算法的基础上，根据求解过程中核矩阵本身的特点，提出了在线最小二乘支持向量回归机方法；王等学者[19]提出了在线稀疏最小二乘支持向量回归机算法，提高了训练速度，但是，该方法的预测精度不如OLS-SVR算法；文献[20]结合鲁棒学习方法，提出了在线鲁棒最小二乘支持向量回归机算法，改善了OLS-SVR算法易受噪声点影响的问题，但是，该算法需要训练的时间较长。

为了兼顾预测精度和预测效率两个方面，本文拟提出一种在线临近支持向量回归机(Online Proximal Support Vector Machine Regression,OL-PSVR)算法。在PSVR算法的基础上，利用在线学习来更新样本数据以及核矩阵。然后，利用一个证券股票数据集与3个加州大学欧文分校(University of California Irvine，UCI)数据库的数据集进行实验，从预测精度和预测效率两个方面与OL-SVR算法、OLS-SVR算法以及在线序列核极限学习机[21](Online Sequential Extreme Learning Machine with Kernel,OS-KELM)算法等3种算法进行比较，以验证算法的可行性和有效性。

1 PSVR算法

PSVR算法的决策函数可以通过求解一个优化问题得到。该优化问题可以表示为

(1)

式中：ξ表示松驰变量；e为元素均为1的n维列向量；C为惩罚参数；(ω,b)为待求解的增广权向量。

式(1)中优化问题的Lagrange函数形式为

(2)

式中，α为拉格朗日乘子向量。

根据Karush-Kuhn-Tucker(KKT)条件[16]，令各变量的偏导为0，可以得到方程组

(3)

(4)

进一步，有

(5)

式中，I为单位矩阵。

令H=[A,e]，则有

(6)

当输入样本数目大于样本维数时，由于式(6)涉及到一个m×n维的矩阵求逆，可以利用SMW(Sherman-Morrison-Woodbury)公式[16]降低矩阵维数。由此可以得到

(7)

所以，可以将PSVR方法的决策函数表示为

f(x)=ωTx+b=(Ax+e)Tα

(8)

对于非线性临近支持向量回归机，可以通过引入核函数，使用K(A,AT)来代替约束等式中的A，则可以将式(1)的优化问题转化为

(9)

记K(A,AT)=K，与线性情况类似，通过构造Lagrange函数，并根据KKT条件可以得到

(10)

b=eTα

(11)

化解式(10)，可得

(12)

令G=[Ke]，可得

(13)

由此得到非线性PSVR算法的决策函数为

f(x)=ωTx+b=(KK(A,x)+e)Tα

(14)

PSVR算法的主要问题是，一方面，无法对在线更新数据进行预测；另一方面，其核矩阵随着数据的增多而急剧增大，影响了算法的效率。

2 OL-PSVR算法

为了改善PSVR无法对时间序列数据进行预测的问题，引入在线学习方法更新样本，提出OL-PSVR方法。

2.1 在线学习

在线学习通过增量学习和减量学习保证训练样本数目的恒定。为了说明固定窗口的在线序列预测方法，提出以下假设。

图1 在线学习样本更新示意图

2.2 OL-PSVR

由式(12)和式(13)式可知，非线性的PSVR算法的解可以通过求解一组方程得到。该方程组为

(15)

式中，K=K(A,AT)。

(16)

对于时间序列预测问题，PSVR算法求解矩阵的规模会随着样本数目的增加而急剧增大，为此，引入在线学习进行样本更新。假设存在一个固定大小的时间滑动窗口，其中包含N个存储单元，可以在特定的时刻加载训练样本。

假设在时刻k，更新中的训练样本集表示为{A(k),Y(k)}，其中，A(k)=[xk,xk+1,…,xk+N-1]T表示时刻k的样本属性，Y(k)=[yk,yk+1,…,yk+N-1]T表示k时刻的样本标签。随着时间的变化，可以利用时间滑动窗口对时刻k+1的训练样本进行更新和转换。

矩阵S、α和偏差项b都是关于时刻k的函数，可以将时刻k的S、α和偏差项b分别表示为

(17)

α(k)=[αk,αk+1,…,αk+N-1]T

(18)

b(k)=bk

(19)

式中，I为N维的单位矩阵。

式(17)、式(18)、式(19)结合式(16)可得

(S(k)+eeT)α(k)=Y(k)

(20)

b(k)=eTα(k)

(21)

根据式(20)和式(21)，可以得到

α(k)=(S(k)+eeT)-1Y(k)

(22)

在时刻k+1，若添加一个新的样本xnew，则将矩阵S(k)更新为一个新的矩阵S(k+1)，这样就可以有效地控制核矩阵的维度。

更新后的新矩阵可以表示为

(23)

式中，M(k)表示第k轮的S矩阵去掉一个旧样本后的新矩阵，表达式为

Knew1=[K(xnew,xk+1)…K(xnew,xk+N)]T

同理，当预测步长变为h(N>h>1)时，新添加的样本数目大于1，则相应地将矩阵S(k)更新为

(24)

式中，M(k*)表示第k轮的S矩阵去掉h(N>h>1)个样本后的新矩阵，表达式为

其中，xnew(h)为第h个加入的样本。

根据式(21)、式(22)以及式(24)可以得到α(k+1)和b(k+1)，并记φ(x)为x映射到特征空间的向量，则k+1轮的决策函数可以表示为

(25)

l=1,2,…,h

3 实验结果及分析

3.1 实验设置

为了评价所提算法的性能，对UCI数据库中的Air Quality数据集、Beijing PM2.5数据集和Parking Birmingham数据集3个数据集，以及Northeast Securities数据集进行实验，并将所提算法与已有的OL-SVR算法[17]、OLS-SVR算法[18]以及OS-KELM算法[21]等3种在线序列预测算法进行比较。

实验中，设置时间滑动窗口N=100。4种算法的核函数均采用高斯核

式中，σ为核参数。

另外，4种算法的性能都依赖于参数选择，将网格搜索法与五折交叉验证结合起来选取最优参数。需要选取的最优参数包括高斯核参数2-2≤σ≤24和惩罚参数C∈{2-2,2-1,…,210}。为了公平地比较算法的预测性能，对于相同的数据集，4种算法均选用相应的最优参数进行验证。

选择平均绝对误差[6](Mean Absolute Deviation，MAE)、均方根误差[6](Root Mean Squared Error，RMSE)、平均绝对百分比误差[6](Mean Absolute Percentage Error，MAPE)和泰尔不等式系数[6](Theil Inequality Coefficient，TIC)等4种评价指标来评价不同算法的预测精度。这4种评价指标值越小，表示算法的预测精度越高。

实验环境为AMD Ryzen5 4600U内核(2.10 GHz)且内存为16 GB的笔记本计算机，使用MATLAB R2016a编写程序。

3.2 使用的数据集

Air Quality数据集选自UCI数据库，包含空气质量化学多传感器设备的9 358个小时的响应数据，采样于意大利一座城市内道路高度严重污染地区，记录时间为2004年3月至2005年2月。选取前1 055个数据进行实验。

Northeast Securities数据集为中国证券股票数据集中的东北证券公司数据，下载于网易财经官网，包含2017年11月1日到2019年6月24日的400个历史交易日行情，共计1 199个数据。

Beijing PM2.5数据集选自UCI数据库，包含了美国驻北京大使馆每小时PM2.5的数据和来自北京首都国际机场每小时的气象数据，共计43 824个数据。数据采集的时间段为2010年1月1日至2014年12月31日。选取前1 108个数据进行实验。

Parking Birmingham数据集选自UCI数据库，由伯明翰市议会NCP运营的伯明翰停车场收集。用于预测停车场的占用率，包含35 717个数据，采集时间段为2016年10日至2016年12月19日。选取前1 200个数据进行实验。

实验采用的4个数据集的具体信息如表1所示。

表1 数据集信息

3.3 实验结果

设置预测步长h分别为1、5和10，在不同的预测步长条件下，4种算法对4个数据集的预测性能结果如表2所示。

表2 4种算法不同步长条件下的预测性能

表2的实验结果显示，从预测精度上看，当h为1时，OL-PSVR算法在Air Quality、Beijing PM2.5以及Parking Birmingham等3个数据集上预测精度与OLS-SVR算法和OS-KELM算法相当，高于OL-SVR算法；OL-PSVR算法仅在Northeast Securities数据集上的预测精度低于OS-KELM算法，这是因为，OS-KELM算法是一种单隐含层神经网络，相比于OL-PSVR算法，其预测的偶然性较大。当h为5时，OL-PSVR算法在4个数据集上的预测精度均是最高的，仅在Air Quality数据集上MAPE值低于OLS-SVR算法，这是由于数据的偶然性。当h为10时，OL-PSVR算法在4个数据集上的所有指标值均低于其他3种算法。这说明随着预测步长增大，OL-PSVR算法显示出更好的预测精度。

从预测效率上看，当h为1和5时，OS-KELM算法的预测速度最快。当h=10时，OL-PSVR算法的预测速度与OS-KELM算法相当。这说明当预测步长增大时，OL-PSVR算法的预测速度增幅最大。

通过观察表2中的数据可以发现，在步长h分别为1、5和10的条件下，OL-PSVR算法、OL-SVR算法、OLS-SVR算法以及OL-KELM算法等4种算法对Beijing PM2.5数据集预测的误差指标值差异最大，为了直观地展示4种不同算法预测的误差，选取4种不同算法对Beijing PM2.5数据集的预测来进行展示。在不同预测步长条件下，4种算法对Beijing PM2.5数据集的预测误差如图2所示。

图2 不同步长下4种算法对Beijing PM2.5数据集的预测误差

由图2可以看出，当h=1时，OL-PSVR算法的MAE、RMSE、MAPE和TIC等4个评价指标值与OLS-SVR算法几乎相等；当h增大为5时，4个指标值均略小于OLS-SVR算法与OL-SVR算法；当h增大为10时，4个指标值均明显小于对比算法。可见随着步长h的增大，相比于其他3种算法，OL-PSVR算法具有更高的预测精度。这是因为随着步长的增大，OL-PSVR算法所造成的累计误差最小。

表2不能清晰地看出预测时间随着预测步长的变化规律和预测效率，为此，在步长h分别为1、5和10的条件下，采用OL-PSVR算法、OL-SVR算法、OLS-SVR算法以及OL-KELM算法等4种算法对Air Quality数据集、Northeast Securities数据集、Beijing PM2.5数据集和Parking Birmingham数据集4个数据集进行仿真，不同步长条件下4种算法对4个数据集的预测时间仿真结果如图3所示。可以看出，OL-SVR算法预测所耗费的时间明显长于其他3种算法，说明该算法的效率明显低于其他3种算法。而OL-PSVR算法、OS-KELM算法和OLS-SVR算法的预测效率的差距不明显。

图3 不同步长条件下4种算法的预测时间

(续)图3 不同步长条件下4种算法的预测时间

为了更清晰地显示OL-PSVR算法、OS-KELM算法和OLS-SVR算法预测效率的差异，仅对比这3种算法的预测时间。在步长h分别为1、5和10的条件下，OL-PSVR算法、OS-KELM算法和OLS-SVR算法3种算法对Air Quality数据集、Northeast Securities数据集、Beijing PM2.5数据集和Parking Birmingham数据集4个数据集的预测时间如图4所示。可以看出，当h分别取1、5和10时，OL-PSVR算法预测时间明显比OLS-SVR短；当h由1增大到5时，OL-PSVR算法的预测时间大幅度缩短，h增大到10时与OS-KELM算法的预测时间几乎相等。这表明，在进行多步预测时，OL-PSVR算法预测速度快于OLS-SVR算法和OL-SVR算法，与OS-KELM算法预测速度相当。虽然OL-PSVR算法的预测时间会随着h的增大而接近OS-KELM算法，但是，考虑到OL-PSVR算法的预测精度会随着h的增大而明显高于OS-KELM算法，在进行多步预测时，相比于OS-KELM算法、OL-PSVR算法的预测性能更优。

图4 不同步长条件下3种算法的预测时间

4 结语

基于PSVR与在线学习提出了OL-PSVR算法，以实现对时间序列数据的多步预测。与经典的预测算法相比，OL-PSVR算法不仅能利用历史数据，还能实时捕获当前数据信息并实现数据的在线更新，节省了存储空间。这意味着当预测样本数目较大时，OL-PSVR算法具有较高的训练效率。实验结果表明，当选用最优参数时，与其他经典的在线预测算法相比，OL-PSVR算法不仅具有预测精度较高的优势，而且预测效率高于OLS-SVR算法和OL-SVR算法，与OS-KELM算法相当。并且，随着预测步长的增大，OL-PSVR算法在保证精度的同时，能够明显地提升预测速度，具有更好的预测性能。