自适应参数寻优短期车流量预测

王凤琴 卢官明 柯亨进

1(湖北师范大学物理与电子科学学院 湖北 黄石 435102) 2(南京邮电大学信息与通信工程学院 江苏 南京 210003) 3(武汉大学计算机学院 湖北 武汉 430072)

0 引 言

当前，交通拥堵是影响城市生活的重要问题。交通疏导系统通过预测短时路口车流量，向上下班高峰期的司机推荐合适的路径，以达到疏导交通目的。针对这一问题，国内外很多研究学者致力于相关方面的研究[1-2]。在短期流量预测上，自回归滑动平均模型(ARIMA)可取得较高的预测性能[1]。在有效理解周期变化较为明显数据的变化趋势以及季节性模式的基础上，已有时间序列模型可有效刻画历史数据模式，从而演化预测数据的变化趋势[2]。然而，缺乏对影响预测性能起关键作用的步长和顺序等隐变量进行有效建模。

鉴于很多不确定因素(季节、气候条件、交通事故和司机的心里状态)对交通状况有着不可忽视的巨大影响，致使现实中的交通流量数据往往呈现出非线性、非平稳和高噪声、高干扰等特性，其结果是实时的交通流量预测难上加难。尽管数据呈现出随机的、杂乱无章的特性，但毕竟是有序的、有界的。因此模式具备潜在规律，简言之，灰色预测就是利用这种规律建立灰色模型对灰色系统进行预测[3]。灰色预测由于其高预测精度、简单和易用性而受到越来越多研究者的关注，并已成功应用于交通流量预测中[4]。针对灰色模型对呈现出近似指数增长的数据所取得的预测性能出现震荡和下降等问题，一个新的组合模型(组合灰色模型和最小二乘支持向量机)被提出进行交通流量预测并取得较优的预测性能[5]。但由于支持向量机的所需训练时间太长，在实际应用中难以实现实时动态训练。

一个有效刻画时间序列的隐变量的策略是对时间序列历史时间点进行加权。当前，加权策略包括设定固定值的静态策略和线性回归预测法等[6]。静态策略对于动态数据的拟合程度不高，不满足动态系统的要求。线性回归预测法所预测的权值对于属性权值呈现线性的情况下，其预测性能较好。而对于非线性、非平稳、高噪声高干扰的数据，拟合效果欠佳。为消除由于隐变量的不确定性和非线性而造成的序列的动态性，本文对隐变量进行动态建模，动态拟合隐变量的非线性变化关系，对隐变量自动寻优建模，以期对时间序列的动态建模。

随着近几年统计学习理论和统计方法的发展，很多相干性度量方法被提出，以弥补线性相关系数无法识别非线性关系的缺陷。如相关比例、最大相关系数、均方列联系数、斯皮尔曼相关系数、距离相关和基于信息理论的指标等。从相依性指标所应用的性质上看，基于信息理论的指标是最好的。而文献[7]从线性、非线性、抗噪性、健壮性和寻求非函数关系等方面对最大信息系数MIC(Maximal Information Coefficient)，相关系数和互信息进行比较，MIC都取得了较优的性能。其主要优点包括：(1) 不需要对数据分布做任何假设，估计变量之间的相关性(包括线性和非线性)；(2) MIC也能检测非线性相关性(正弦关系)；(3) 最大信息系数的非参数特性与抗噪能力。

综上所述，本文基于动态建模理论，提出一种针对动态非线性变化的隐变量的动态随机过程模型，以期理解时间序列的动态演化模式，并结合度量双变量相关性的最大信息系数对时间序列属性加权，最后成功运用于短时车流量预测。本文的贡献如下：

1) 基于步长有限时间序列，提出近似平稳假设条件，结合动态建模理论，设计一种对影响预测性能隐变量的建模方法。

2) 理论证明隐变量动态随机过程模型的收敛条件。

3) 采用无监督学习策略对诸如条件模型、权值和阈值等参数进行自动学习，这样可以节省大量的人力，使得模型具有现实意义。

1 动态随机过程模型

现实数据往往呈现出非线性、非平稳、高噪声、高干扰、无固定模式等特点，其主要原因是影响数据变化的因数是不确定的。动态建模是解决这一问题的有效手段，如基于状态空间可测的准域动态系统[8]和状态约束动态系统[9]，但其只能刻画固定状态空间的动态系统而无法刻画状态变化的动态系统。而针对状态空间实时动态变化的数据，动态随机过程模型可感知外界环境，依据历史状态持续更新当前状态和未来状态，自适应动态地选择不同的超参数，以至于对未来状态的预测。

动态模型由一组模型行为所组成，包含一组随机变量以及所需满足的隐变量条件。根据强化学习策略，动态随机过程模型对影响优化目标的隐变量进行建模，逐步确定优化目标与隐变量之间的关系，最终达到目标优化。传统贝叶斯强化学习无法用于加权时间序列分析的主要原因是时间序列往往比较长，所需训练参数太多而算不了、算不清。针对POMDP[11]的Markov特性限制，无法刻画多个状态间关系等缺陷。因此有必要设计一种动态建模方法，解决隐变量的动态演化与动态反馈问题。针对这一问题，动态随机过程模型DSPM(Dynamic Stochastic Process Model)试图对隐变量进行动态建模，其定义如下：

定义1(DSPM) 一个动态随机过程模型是一个四元组(V,P,TS,C,T)，其中：V是随机变量的有限集合，P是特定时间点随机变量的联合概率，TS是整个时间序列，C是时间序列的隐变量，是影响预测性能的参数，T：P×Cts→Π(P)是概率转移函数，在特定时间点，对于每一个状态和行动，计算相应状态下采取行动的概率分布。

动态随机过程模型需要解决两个问题：一方面是隐变量的量化，另一方面是确定概率转移矩阵。第二个问题在第一个问题解决的基础上结合Markov链而解决，因此，第一个问题是解决动态随机过程的首要问题，该问题用Bayes强化学习策略[10]解决。在特定时间点，令P(ci)是隐变量的先验概率分布，P(p|ci)是在特定隐变量下，观测目标的条件概率，依据贝叶斯原理，隐变量的后验概率更新如下：

(1)

传统POMDP认为当前状态和回报值只与前一个状态和回报值有关。但在实际中，当前状态与之前多于1时刻的先前状态有关。选择多少步长的时间序列是至关重要的：(1) 可以减弱无关步长序列的影响；(2) 大大减少权值训练参数。所有历史决策条件的分布都被保存，结合贝叶斯强化学习策略，预测当前相应的上下文条件分布。即在每一个时刻，后验分布Pr(Ct)被递归更新，且agent执行一个动作(参数的确定)a，同时接受一个观测值Z[10]:

(2)

动态随机过程模型随着所有之前时间步长下的所有隐变量的确定而创建。其计算过程是一个迭代过程，图1显示了该逐步求解过程。在当前第i步，之前的所有步(1…i-1)条件C(c和c″)和观测值Z都已经被求解出，依据式(2)可以求出当前时刻的隐变量，当前时刻的权值由式(11)(见下一节)求出，而当前观测值由灰色加权预测得出。

图1 动态随机过程模型的迭代更新过程

定义2(动态随机过程) 对于随机过程{X(t),t∈T}，及任何n时刻点ti,i=1,2,…,n,满足t1

(1)X(0) = 0。

(2)X(t)是独立增量过程。

(3)P{X(t+h)-X{t}=1}=f(c,t)h+o(h)

P{X(t+h)-X{t}>1}=o(h)

(4) 均值函数是条件和时间的函数，也称为条件期望。即：

定理1(收敛性条件) 如果X的动态随机过程的收敛性、满足定义2得计算条件方程：

(3)

2 自适应参数寻优灰色加权预测

为高效准确地对早高峰车流量进行预测以辅助交通疏导，针对影响时间序列预测性能的隐变量动态变化问题，建立基于阈值系统和动态随机过程模型的数据特征选择模型，结合贝叶斯强化学习策略与动态随机过程模型，实现最大信息系数属性加权灰色算法。图2显示了系统的总体架构图。系统对早高峰车流量信息建立时间序列数据库，主体包含分析建模、模型运行和模型发布三个模块。分析建模模块主要完成学习率等超参数设定的阈值系统建立、建立步长和顺序的上下文条件动态模型以实现特征选择、利用动态随机过程模型实现属性重要程度的最大信息系数的属性加权策略。模型运行模块主要实现灰色模型时间序列预测算法和基于贝叶斯强化学习策略的动态随机过程模型。模型发布主要产生基于知识库的模型文件、后台监控日志和各种预测曲线的图表生成。

图2 系统架构图

2.1 惩罚因子选择

时间序列预测的一个重要目标是获得预测值与真实值之间绝对残差的最小值，因此，选择绝对残差作为惩罚因子是合适的。绝对残差的定义如下：

εi=|predicti-reali|/reali

(4)

在任意需要决策的时间点，之前所有的惩罚因子被观测。依据贝叶斯强化学习策略，并运用式(2)，可计算当前时间点的惩罚因子。

2.2 最大信息系数

为量化双变量非线性函数关系，Reshef提出“最大信息系数”，通过在线性和非线性度量、抗噪声、健壮性和寻找非线性函数关系等方面比较MIC和MI、相关系数，得出MIC具有较优的性能[7]。

给定有序属性对的有限集合D，每一个属性都有x方向和y方向两个方向的成分。将x成分以网格方式分割成x网格，同理，将y部分分割为y网格，整个网格称为x×y网格。每个子格的互信息计算如下：

I(D|G)=I(X;Y)=

(5)

其中最大的互信息定义为：

I*(D,G(b1,b2,…,bm))=maxI(D/G)

(6)

对于无限数据，MIC定义为：

(7)

而对于样本大小为n并且格数小于B(n)的双变量，MIC定义为：

(8)

式中:ω(1)

MIC可以有效度量大量数据集各属性之间关联强度，具有如下性质：

• 有界性：所有MIC值都落在[0,1]区间内。

• 对称性：MIC(x,y)=MIC(y,x)。

• 稳健性：MIC不受异常值的影响，而相关系数易受异常值的影响。

2.3 动态特征融合权值计算

时间序列预测中，有两个问题亟待解决。

(1) 为避免过分拟合，需进行特征选择。特征选择一般基于阈值系统。有别于传统专家建议的固定阈值，本文把阈值当作一种隐变量，运用动态随机过程模型对阈值与预测精度关系的迭代更新，最终获得较优的动态阈值。

(2) 属性加权问题。在每个时间点，依据动态随机过程模型获取历史隐变量，以及根据式(2)所得相应概率，不同时间点所有隐变量(步长和逆序数)的融合度量值：

(9)

式中：P(C=ci)表示选择第i个隐变量的后验概率，依据动态随机过程模型，由式(2)计算出，ci是对第i个隐变量的量化，其量化值如下：

(10)

式中:MIC(εi)为第i步所有隐变量预测残差序列之间的相干性度量，其具体计算过程如下：

首先依据DSPM选择决定性隐变量，也即时间步长，由式(2)确定不同步长的后验概率，其概率大者就是步长的最佳选择。例如，在当前步长为4时，其最佳步长是3(见3.2节的图5)；其次，在特定步长下，依据DSPM选择出逆序数候选集，本文采用击中概率前10的逆序数候选集，继而计算所有候选集内每个逆序数所对应的残差序列。最后，依据式(8)计算所有残差序列之间的MIC度量值。

2.4 属性加权灰色模型

2.4.1 灰色模型

灰色预测模型[3]由于具有所需原始信息量少、计算简单及预测精度高等优点而受到研究学者关注[12-13]。王利等基于滚动推演策略提出动态灰色预测模型，并成功应用于大坝变形的预测预报[12]。为提高雷达电子部件状态趋势预测精度，黄建军等人改进GM(1，1)和SVR模型，提出基于GM(1，1)与支持向量回归机(SVR)组合预测模型，取得更高的预测精度与更强的适应能力[13]。详细算法请参见文献[3]。

2.4.2 权值计算

不同属性具有不同的重要程度，如何进行属性加权是机器学习领域的一个重要问题。计算过程包括：(1) 历史时间步长的选择；(2) 步长固定情况下逆序数确定；(3) 步长固定情况下，度量不同逆序数下残差序列的相干性；(4) 基于相干性度量的权值计算。本文利用所提出的动态随机过程解决问题(1)和(2)，值得注意的是，步长和逆序数的确定有主次之分，考虑到MIC的计算需要相同长度的序列，因此首先需将步长选择出来，利用最大信息系数进行相干性度量以解决问题(3)，对于问题(4)，我们利用相干度量值的平均化来去掉权值的波动性，致使预测算法的平稳性。在当前时间点的权值计算步骤如下：

(1) 在每个时间点，式(8)计算出两两隐变量的相互关系强度，对于整个时间序列来说，第i个融合步长的相关强度度量为co-stepi，正则化相关强度度量可以得到每个时间点的权值wi：

(11)

(2) 最终的权值序列如下：

W={w1,…,wi,…,wn}

(12)

2.4.3 加权灰色模型

通常，统计模型总是可以表示为：

Y=Xβ+ε

(13)

式中:X是观测向量，β为系数，ε为残差，Y是回归预测向量。

定义广义残差平方和对参数β进行评估：

RSS(β)=(Y-Xβ)TΣ-1(Y-Xβ)

(14)

式中:Σ是对角阵，也是本文中的权值矩阵：

(15)

依据最小二乘法，其参数β的评估值如下：

β=(XTΣ-1X)-1XTΣ-1Y

(16)

加权灰色模型x(0)(i)+az(1)(i)=u，其中z(1)(i)为滑动平均算子(z(1)(i)=0.5x(1)(i-1)+x(1)(i))，a和u是待估计的模型参数。最小化平方加权残差和argmin(εTΣε)，所以灰色参数向量估计如下：

(au)T=(BTWB)-1BT

(17)

2.5 预测算法

本节讨论动态随机过程预测算法。算法1是整体框架。算法2计算第一步中提取的所有特征所组成的融合步长，不失一般性，系统初始化隐变量的概率分布为泊松过程，最后，计算在时间序列中的每一个时间点的权值并应用于灰色模型，建构属性加权灰色模型。

算法1整体框架

输入：交通流向量组A{a1,a2,…,an}

输出：预测向量y

从A中的每一个时间点中抽取特征向量

训练阈值、步长和顺序

计算融合步长

建构属性加权灰色模型

算法2DSPM算法

初始化隐变量先验分布为泊松分布

输入：特征列向量，之前动作、可信状态和上下文条件

输出：隐变量后验分布预测值

循环:在所有之前的时间点

在第i列，从数据库中装载之前所有的动作和回报

装载第i个动作

装载第i个观察值

当前条件回报值计算，通过残差re的正负号来确定是否是采用之前的条件还是对条件进行更新：

c(a,z)←min(c(a,z),c(a,z)+re*f(z)*P(z|c)))

根据式(2)更新该条件以及相关条件的回报值的后验分布

结束循环

输出：取得最大回报值的隐变量

3 范例——交通流量短期预测

城市交通线视为一个动态随机图(N,E,W)，N表示节点，E表示双向边，W是通过公路某段时间的车辆数。本文的预测目标是实时预测图(N,E,W)中所有W的值。

本文的数据集来自于武汉市光谷大道早高峰的交通流数据，数据集以15 min为间隔，采集时间段内通过金融港前面的段截面的车流量作为预测目标。

3.1 特征提取

本节旨在提取出那些影响预测性能的特征，也即上下文条件。在任意时间点，所有之前的步长与相应的残差被记录下来。图3显示了不同步长下平均残差与该步长之间的关系。x轴是当前时间点的所有步长，y轴是在不同步长下的平均残差。在其他条件固定的情况下，步长的选择对预测性能的影响较大，最大平均残差几乎可以达到最低平均残差的1.5倍，因此，选择不同的步长可以改善预测性能。

图3 在当前步长，当选取不同步长时其平均残差的变化趋势

类似的，数据顺序也会影响预测性能。图4显示不同逆序数情况下的平均残差。x轴是当前时间点的逆序数，y轴是对应的平均残差。排列逆序数是一个排列中逆序的总数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21、43、41、31是逆序，逆序数是4，为偶排列。从图中可看出，最大平均残差几乎可以达到最低平均残差的1.5倍，合适的逆序数可以极大改善预测性能。

图4 显示了不同逆序数与残差之间的关系

3.2 步长与顺序训练

在当前时间点，所有之前的决策选择以及与之相应的残差都保存到数据库中，在选择步长时，计算在当前步长下，不同步长的选择而产生的残差，当残差小于当前步长下的平均残差时，认为该步长的选择是有效的(为方便描述，本文定义该概率值为击中概率)，否则是无效的(非击中概率)，也即：

ε(p(cp|cc))

(18)

式中：ε表示残差函数，p表示概率，cc表示当前步长，cp表示选择在当前时间点前的某个步长，avg表示均值。图5显示了在不同时间点时，取不同步长时的击中概率的转移概率图。从图中可以看出，在当前步长小于6时，倾向于选择较少的步长，反之选择较长的步长比较合适。图中的粗线显示出在当前步长下的最优选择概率。逆序数选择策略，逆序数的选择在步长小于等于6时，通过转移概率图进行选取，在大于6的时候，在上一步的逆序数选取的基础上随机插入当前要插入的步长进行选取，该方法主要考虑逆序数对于预测性能影响较小，但是考虑全面需非常高昂的计算费用。

图5 不同时间点下不同历史步长的击中概率的转移概率图

3.3 结果比较

本节从两个方面进行比较，一方面，本文方法与其他灰色模型的横向比较；其二是同其他经典回归模型的纵向比较。图6显示了纵向比较结果(包括支持向量机(左)，Arima(中)和我们的方法(右))下早高峰车流量的真实值(细线条)和预测值(粗线条)。ARIMA方法对周期不明显的数据拟合欠佳，有些情况下几乎是一条水平横线，而支持向量机的快速拟合性不如我们的方法。我们的方法在短数据的时候能够快速地拟合数据，特别适合早高峰时期的车流量预测，因为开始预测早高峰前时的类似模式的数据量较少，无法呈现出与早高峰车流量相匹配的车流量信息。

图6 三种不同预测方法下早高峰车流量的真实值和预测值

3.3.1 与其他灰色模型进行比较

计算不同灰色模型策略(经典的灰色模型[3]，属性加权灰色模型[14]和本文的基于动态随机过程的贝叶斯强化学习策略)下每天早高峰预测值与真实值之间的平均残差，通过该残差比较不同策略的性能。图7显示了不同月份三种模型下的平均残差。从图中显示，相较于经典灰色模型，加权灰色模型有一定的性能改进，但是由于其固定加权策略，无法准确地动态拟合数据，而本文的策略由于动态针对不同时期的数据进行加权，从而较好较快地对数据进行拟合，从而有一倍以上的性能改善。

图7 2014年1月份到七月份不同灰色模型下的平均残差

3.3.2 与其他回归模型的比较

计算不同预测模型策略(ARIMA模型、径向基支持向量机模型和本文的基于动态随机过程的贝叶斯强化学习策略)下每天早高峰预测值与真实值之间的平均残差，通过该残差比较不同策略的性能。图8显示了不同月份三种模型下的平均残差。从图中可以看出，ARIMA和SVM模型的性能基本相同，而本文的性能有大约20%的性能改善。

图8 2014年1月份到七月份不同回归模型下的平均残差

4 结 语

针对影响回归预测的上下文条件的动态性问题，据我们所知，本文首次提出动态随机过程模型，并利用贝叶斯强化学习策略对动态上下文条件进行建模，同时理论证明了动态随机过程模型的收敛条件，最后运用该模型对早高峰车流量进行短期预测。实验结果显示，相较于其他的灰色模型和其他回归预测模型，本文所提出的模型在预测精度上都有一定的改善。本文将如何利用该方法进行城市交通疏导作为下一步的研究重点。