一种基于时空关联数据挖掘的交通流预测方法

技术领域

本发明属于交通流预测技术领域， 具体涉及一种基于时空关联数据挖掘 的交通流预测方法。 背景技术

近年来， 交通流预测技术一直在智能交通系统 （ITS ) 中发挥很重要的作 用。 交通流预测技术能够帮助通行的个人进行智能 的出行路线选择， 也可以为 交通管理者提供决策支持。

早期的一些技术主要针对单序列的交通流预测 。 可以根据预测模型的有无 参数分为有参数预测模型和无参数预测模型。 在有参数预测模型中， 季节性

ARIMA ( Autoregress ive Integrate Moving Average ) 模型是应用最广泛的一 种方法 （见参考文献 [1 ] ) 。 它在基于单时间序列的交通流预测上可以达到 最 小的均方误差（MSE )。而在无参数预测模型中，最近邻方法（Neare st Ne i ghbor Method ) 被认为是可替代季节性 ARIMA的方案 （见参考文献 [2] ) ， 但是最邻 近预测方法的预测效果依赖于历史数据的质量 。 总体来讲， 单序列的交通流预 测方法只考虑了序列自身的特征， 忽视了不同序列之间的相互作用和关系。

由于交通流的演化是通过交通网中所有节点交 通流之间的相互作用而形 成的， 所以在交通流的预测中， 不同节点交通流之间的关系应该被考虑进去。 从而， 在近些年基于数据时空关联性的多因子交通流 预测成为了研究的热点。 目前流行的方法大致有三种： 1、 状态空间模型或卡尔曼滤波器 （见参考文献 [3] ) ； 2、 神经网络 （Neural Network ) 等机器学习方法 （见参考文献 [4] ) ； 3、 时间序歹 ϋ方法， 如 Vector Autoregress ive Moving Average模型 （见参考 文献 [5] ) ( VARMA) 。 而时空关联数据的选取则是进行多因子交通流 预测的必 要步骤。 在以往的研究中， 时空关联传感器的选取大部分是根据人工经验 手动 选取目标节点一定邻近范围内的传感器。 只选取目标节点邻近范围内的传感器 的数据作为与预测模型的输入比较主观， 没有反映现实中数据之间真正的时空 关联性， 无法获得最佳的预测性能， 基于人工经验的方法缺乏适应性， 很难实 施到大型的交通网中。

稀疏表达作为一种数学工具最早应用于信号处 理领域， 被广泛应用于信号 压缩、 图像去模糊、 特征提取等， 本发明提出将其应用于面向交通流预测的时 空关联数据挖掘。 稀疏表达的主要思想为： 一个信号 y可以通过一个字典 D包 含的 κ个原子信号 '… 的线性组合表示为 y = DX, 其中 y ^{e r} ， ^D J ^{G RN} , D G R- ^K _; 或者近似表达为 y ^¾ ， 这里 lb— ^D "i ^≤£ 。， 其中 为信 号 y的表示系数， 稀疏表达要求通过尽可能少的原子信号来表示 信号 y， 即要 求线性组合系数 X包含的非零系数尽可能少， 因此， 求稀疏解的目标函数可以 写作 _Λ

X - argminlUII _{f f} _^ ^ , ,

^S - ¹¹ "° 约束条件： y = Dx

或者

i ^=argm ? ⁿ IHL 约束条件： _D ^≤ s。 上式中的 HI。为 X的 0范式， 表示向量 X包含的非零元素的个数。 由于已 有一些稀疏表达的优化方法方面的数学工具 （见参考文献 [6]) ， 可以自动从 字典中选取有效的原子表示信号， 所以本发明将其应用到时空关联性数据挖掘 中， 以达到从整个交通网络中自动地选取与目标传 感器相关的时空关联传感 器、 并将时空关联传感器的数据作为预测模型的输 入用于预测的目的。

参考文献

[1] Williams, B. M. , Durvasula, P. K. , Brown, D. Ε. , 1998. Urban freeway traffic flow prediction: Application of seasonal autoregressive integrated moving average and exponential smoothing models.

Transportation Research Record 1644, 132 - 144.

[2] Smith, B. L. , Williams, B. M. , Oswalsd, R. K. , 2002. Comparison of parametric and nonparametric models for traffic flow forecasting. Transportation Research Part C 10, 303 - 321.

[3] Stathopouos, A. , Karlaf tis, A. , S. , 2003. A multivariate state space approach for urban traffic flow modeling and prediction.

Transportation Research Part C 11, 121 - 135.

[4] Vlahogianni, E. I. , Karlaftis, M. G. , Golias, J. C. , 2005. Optimized and meta- optimized neural networks for short-term traffic flow prediction: a genetic approach. Transportation Research Part C 13, 211-234.

[5] Min, W.， Wynter, L. , 2011. Real-time road traffic prediction with spatio-temporal correlations. Transportation Research Part C 19， 606 - 616.

[6] Elad, M.， 2010. Sparse and redundant representations- From theory to application in signal and image processing. Springer.。

发明内容

本发明的目的在于克服现有交通流预测技术在 时空关联数据选取上的不 足， 提出一种基于时空关联数据挖掘的交通流预测 方法， 从整个交通网络中自 动地确定与预测目标节点相关的时空关联传感 器。

本发明提出的基于时空关联数据挖掘的交通流 预测方法， 具体步骤为：

(a) 通过布局到交通网各个节点的传感器采集交通 流量的原始数据；

(b) 通过数据预处理， 将采集的原始数据处理为有效的交通流数据；

(c) 建立预测模型： 令 ¹ ^表示交通网中的传感器 j在第 i个时刻采集的 交通流量数据， 假设一个交通网中有 m个传感器， 则在第 i个时刻整个交通网 的状态表示为 ^V ' 提前 τ 时刻对传感器 j采集的交通流量数据进 行预测的线性回归模型为：

Vi+τ = V ₍ w ^J

上式中的权重 ^ ^=[ ， ，··· '，···， 为待优化的模型参数， ； 为预测值；

(d) 挖掘时空关联性： 通过稀疏表达的优化方法自动得到模型参数 ^， 权重^ ' =[ ， ，··· ，···， 表示整个交通网络的各个传感器的数据对于预 测目 标传感器 j的数据而言的时空关联性， 当 =0时， 传感器 k的数据与传感器 j 的数据之间没有关联性， 否则 ^值的大小表示传感器 k的数据与传感器 j的数 据之间关联程度的强弱， k=l，2，...，m;

(e) 以时空关联数据为预测模型的输入进行交通流 预测。

本发明中， 所述的步骤 （d) 有三种优化的目标， 分别用 （dl) 、 (d2) 和 （d3) 表示， 具体如下： 上式中， ^{ν = (ν} ^ ，···^Γ^表示从第 到第 _η 时刻所有传感器采集的交通流 数据， 其中第 i个时刻交通网中 m个传感器采集的交通流量为 ^V ' «， ，···， ]， i = l,2, -,m, «， 2， ， 《] 表示传感器」记录的从第1+1时刻到第 τ _+η 时刻的交通流量， ll^ ¹¹ 表示^的 0范数， 即权重向量^中非零元素的个数， εθ 是一个预先设定的门限， 用于控制预测误差 II 表示向

的 2范数， 即向量中所有元素的平方和的平方根；

(d2) 所述的稀疏表达方法要优化的目标为： 约束条件：

式中， L0为预先设定的门限， 用于控制向量 ^中非零元素个数； 上式表达 的优化目标通过 Orthogonal Matching Puisuit (0MP) 算法进行求解 [Tropp, J. A. , 2004. Greed is good： algorithmic results for sparse approximation. IEEE Trans. Information Theory 50, 2231-2242.】 ；

(d3) 所述的稀疏表达方法要优化的目标为：

W arg mm w Ι '- ^ν [ ⁼ ΣΙ ^- ^ν Γ ^{≤ £} ο

约束条件： 式中， 中所有元素绝对值之和， εθ是一 个预先设定的门限， 用于控制预测误 Ik ; 上式表达的优化目标等价地 表示为加入拉格朗日乘子 λ的无约束条件的优化目标

W argmin{/l }

上式表达的优化目标通过 Least Angle Regression Stagewise ( LARS) 算法进行求解 【Efron， B. , Hastie, T. , Johnstone, I. , Tibshirani, R. 2004. Least angle regression. Annals of Statistics 32 (2) , 407-499. ] 。

本发明中， 预测模型采用多因子线性回归模型外， 也可采用向量自回归模 型、 反向传播神经网络模型、 径向基函数神经网络模型等。

本发明提出的方法可以从整个交通网络中自动 地确定与预测目标节点的 传感器相关的时空关联传感器， 并以时空关联传感器的数据作为预测模型的输 入， 而不需要根据人工经验手动选取目标节点邻近 范围的交通路段流量数据作 为预测模型的输入， 相对于凭借人工经验从邻近范围选取的传感器 数据作为输 入， 本发明提出的全自动时空关联数据挖掘提升了 预测模型的预测性能。 附图说明

图 1为本发明方法的流程图

具体实施方式 如图 1所示， 本发明涉及的交通流预测可分为五个环节， 包括数据采集、数据 预处理、预测模型建立、 时空关联数据挖掘和以交通流预测。其中涉及 的数据采集 是通过布局到交通网各个节点的传感器获得的 交通流量数据；数据预处理是将采集 的原始数据处理为有效的交通流数据；时空关 联数据挖掘是通过稀疏表达的优化方 法自动地选取对于预测目标相关的时空关联数 据的方法；交通流预测是以时空关联 数据为预测模型的输入进行的预测。 具体实施方式如下：

实施例 1 :

(步骤 1 ) 数据采集： 通过布局到交通网各个节点的传感器， 采集以 30秒为 单位时间的交通数据流，得到整个交通网络各 个传感器记录的数据，用矩阵的形式 表示为： s s

S

其中 为整个交通网中传感器的个数， 为以 30秒为单位的时间序列的长 度， ^表示传感器 J'在第 i个时刻对应的 30秒内记录的交通流量；

(步骤 2 ) 预处理： 首先对原始数据进行时间尺度调整， 将单位时间为 30 秒的交通流数据转化为单位时间为 10分钟的数据， 即数据转化为如下矩阵形 式： V， V，

V

Ν

+λ η =—; 然后对 ^的每一列求得标准 记^ (j')为第 j

20

列的标准差， 如果 (j') < 20， 则认为传感器 的记录为无关记录， 从矩阵 中 删除， 从而得到有效交通流数据 V e R ^mx "， 其中 ^为预处理后参与预测的传感器 的个数； 完成如上所述的预处理后， 用于交通流预测的数据转化为如下矩阵形 式：

(步骤 3) 建立预测模型： 令 表示交通网中的传感器 在第 i个时刻记 录的交通流数据， 对于交通网中参与预测的 ^个传感器， 则在第 i个时刻整个 交通网的状态表示为 V, =[«,..., ]，提前 r时刻对传感器 的流量进行预测的 多因子线性回归模型为：

Vi+τ = V _{ w ^J

上式中的权重 =[ ，^, Γ为待优化的模型参数， 为预测值， r分 别取 1、 2、 3、 4、 5、 6， 即分别提前 10分钟、 20分钟、 30分钟、 40分钟、 50分钟、 60分钟对传感器 的流量进行预测；

(步骤 4) 时空关联性挖掘： 通过稀疏表达的优化方法自动得到模型参数 ^， 权重 =[W/,M^...W ,...,W^:T表示整个交通网络的各个传感器的数据 对于预测目标 传感器 J'的数据而言的时空关联性， 当 w =0时， 传感器 的数据与传感器 的数 据之间没有关联性， 否则 值的大小表示传感器 A的数据与传感器 J'的数据之间 关联程度的强弱， l， 2, ... ,m; 首先对 V的每一列和 =[νΚ ₊₂ ,..., ^Γ进行如 下归

所述的稀疏表达方法要优化的目标为:

w arg mm Vw 约束条件:

上式中 Zo为预先设定的门限， 用于控制向： w中非零元素个数； 上式表达的 优化目标通过 Orthogonal Matching Puisuit(OMP)算法进行求解【Tropp, J. A., 2004. Greed is good: algorithmic results for sparse approximation. IEEE Trans. Information Theory 50, 2231-2242.]；

(步骤 5) 将步骤 （4) 求解得到的权重 代入步骤 （3) 建立的预测模型， 得到如下预测结果：

Vi+τ = V _t w ³

上式中， 只有 ^中不为零的元素才参与预测， 对应于时空关联传感器。 实施例 2:

除步骤 4外， 其余部分与实施例 1相同；

(步骤 4)首先对 的每一列和 进行如下归一化处理， 得 到

稀疏表达方法要优化的目标为

w ^J = argmmf 约束条件: Vw

上式中 W 为 的 1范式， 表示向 中所有元素绝对值之和，

预先设定的门限， 用于控制预测误差 | -ν^'| ₂ , - | ₂ 表示向量^^ 的

2范数， 即向量中所有元素的平方和的平方根； 上式表达的优化目标等价地表 示为加入拉格朗日乘子 A的无约束条件的优化目标：

W argmin{/l }

上式表达的优化目标通过 Least Angle Regression Stagewise ( LARS) 算法 进行求角率 【Efron, Β·, Hastie, Τ·, Johnstone, I., Tibshirani, R.2004. Least angle regression. Annals of Statistics 32(2), 407-499.】； 求解时通过设定 λ的值来控制 中 非零元素的个数， 这里根据经验令 A = 0.001， 以获得较优的模型参数；

实施例 3:

除步骤 5外， 其余部分与实施例 2相同；

步骤 (5) ： 预测模型为向量自回归 (VAR) 模型 [Chandra, S.R.,A1-Deek, Η·, 2009. Predictions of freeway traffic speeds and volumes using vector

autoregressive models. Journal of Intelligent Transportation Systems 13 (2), 53-72.】 ， 具体计算公式为：

v B ^d v _t ^l + u _t ^J 上式中： 表示迟滞操作符， 即 β = _<ί ； 如果传感器 是传感器 J '的关 联传感器， 即 （步骤 4 ) 得到的 向量的第 i个元素不为零， 则令 ^ =1， 反之 令 ^ =0; _M /为独立标准高斯噪声； ^为待优化的参数， 可通过最大似然法训 练得到；

实施例 4:

除步骤 5外， 其余部分与实施例 2相同；

步骤 ( 5 ) ： 预测模型为 BP神经网络 （参考 [ Bishop, Ch.M., 1995. Neural Networks for Pattern Recognition. Oxford university press, ISBN

0-19-853864-2.】 ） ， 采用 3层网络结构， 输入层神经元个数为 （步骤 4 ) 得到 的 向量中不为零元素的个数， 输入数据来自 中不为零元素对应的传感器， 隐层神经元设定为 5个， 输出层神经元为 1个， 隐含层传输函数为双极性 S函 数， 输出层的传输函数为线性函数；

实施例 5:

除步骤 5外， 其余部分与实施例 2相同；

步骤 （5 ) ： 预测模型为 RBF神经网络 （参考 [ Bishop, Ch.M., 1995. Neural Networks for Pattern Recognition. Oxford university press, ISBN

0-19-853864-2.】 ） ， 采用的核函数为高斯核函数， 输入层神经元个数为 （步骤

4 ) 得到的 向量中不为零元素的个数， 输入数据来自 中不为零元素对应的 传感器， 隐层神经元个数和输入层神经元个数相同；

基于实施例 2、 3、 4、 5所述的方法， 利用真实交通数据测试了预测性能， 数据下载网址 http : //www. d. umn. edu/tkwon/TMCdata/TMCarchive. html ,数据 来自美国明尼苏达州的一个区域交通管理部门 ， 通过几千个传感器记录了明尼 苏达州双子城高速公路的交通流量。 实验设置如下： 训练数据从 2012年 2月 4 日到 2012年 3月 14日 总共 40天，测试数据从 2012年 3月 15 日到 2012年 4 月 3 日 总共 20天； 经过预处理后， 利用来自遍布于整个交通网络的 3254个 传感器的数据对 60个目标传感器的交通流进行预测。 此外， 进行了对比实验， 除了时空关联传感器的选取方法不同以外， 其它 实验配置与实施 2、 3、 4、 5完全相同， 对比实验中， 根据人工经验选取预测 目标节点一定邻近范围内的传感器作为关联传 感器， 将来自这些传感器的数据 作为预测模型的输入， 邻近传感器的个数分别取 10、 15、 20、 25、 30。

实验表明， 本发明提出的时空关联数据挖掘方法与基于人 工经验选取邻近 传感器作为输入相比， 提升了预测模型的预测性能， 详细的结果见表 1-6， 各 表中， 第一行的 " 10、 15、 20、 25、 30 " 分别表示取来自目标节点邻近的 10、 15、 20、 25、 30个传感器的数据作为预测模型的输入， "稀疏"表示使用实施 例 2的方法自动挖掘出的时空关联传感器的数据� �为预测模型的输入。 表中所 展示预测准确率定义如下 【Min, W., Wynter, L.， 201 1. Real-time road traffic prediction with spatio-temporal correlations. Transportation Research Part C 19, 606—616.】 ：

1 Vi

Accuracy = 1 ^ : 100%

n , V

上式中 表示预测过的交通数据的总数， 表示传感器 J'采集到的交通流 的真实值， 为预测值。 表 1-6列出的精度是 60个目标传感器预测精度的平均 值。

表 1 :选取 10,15,20,25,30个邻近传感器作为关联传感器与稀� ��表达方法挖 掘的关联传感器在提前 10分钟预测时的准确率

表 2:选取 10,15,20,25,30个邻近传感器作为关联传感器与稀� ��表达方法挖 掘的关联传感器在提前 20分钟预测时的准确率

表 3 :选取 10,15,20,25,30个邻近传感器作为关联传感器与稀� ��表达方法挖

表 4:选取 10,15,20,25,30个邻近传感器作为关联传感器点与� ��疏表达方法