法律状态公告日
法律状态信息
法律状态
2015-10-07
授权
授权
2014-06-11
实质审查的生效 IPC(主分类):G08G1/00 申请日:20131230
实质审查的生效
2014-04-02
公开
公开
技术领域
本发明属于交通流预测技术领域,具体涉及一种基于时空关联数据挖掘的交 通流预测方法。
背景技术
近年来,交通流预测技术一直在智能交通系统(ITS)中发挥很重要的作用。 交通流预测技术能够帮助通行的个人进行智能的出行路线选择,也可以为交通管 理者提供决策支持。
早期的一些技术主要针对单序列的交通流预测。可以根据预测模型的有无参 数分为有参数预测模型和无参数预测模型。在有参数预测模型中,季节性ARIMA (Autoregressive Integrate Moving Average)模型是应用最广泛的一种方法(见参 考文献[1])。它在基于单时间序列的交通流预测上可以达到最小的均方误差 (MSE)。而在无参数预测模型中,最近邻方法(Nearest Neighbor Method)被认 为是可替代季节性ARIMA的方案(见参考文献[2]),但是最邻近预测方法的预 测效果依赖于历史数据的质量。总体来讲,单序列的交通流预测方法只考虑了序 列自身的特征,忽视了不同序列之间的相互作用和关系。
由于交通流的演化是通过交通网中所有节点交通流之间的相互作用而形成 的,所以在交通流的预测中,不同节点交通流之间的关系应该被考虑进去。从而, 在近些年基于数据时空关联性的多因子交通流预测成为了研究的热点。目前流行 的方法大致有三种:1、状态空间模型或卡尔曼滤波器(见参考文献[3]);2、神 经网络(Neural Network)等机器学习方法(见参考文献[4]);3、时间序列方法, 如Vector Autoregressive Moving Average模型(见参考文献[5])(VARMA)。而时 空关联数据的选取则是进行多因子交通流预测的必要步骤。在以往的研究中,时 空关联传感器的选取大部分是根据人工经验手动选取目标节点一定邻近范围内 的传感器。只选取目标节点邻近范围内的传感器的数据作为与预测模型的输入比 较主观,没有反映现实中数据之间真正的时空关联性,无法获得最佳的预测性能, 基于人工经验的方法缺乏适应性,很难实施到大型的交通网中。
稀疏表达作为一种数学工具最早应用于信号处理领域,被广泛应用于信号压 缩、图像去模糊、特征提取等,本发明提出将其应用于面向交通流预测的时空关 联数据挖掘。稀疏表达的主要思想为:一个信号y可以通过一个字典D包含的K 个原子信号{d1,d2,...,dj,...,dK}的线性组合表示为y=Dx,其中y∈Rn,dj∈Rn, D∈Rn×K;或者近似表达为y≈Dx,这里其中x∈RK为信号y 的表示系数,稀疏表达要求通过尽可能少的原子信号来表示信号y,即要求线性 组合系数x包含的非零系数尽可能少,因此,求稀疏解的目标函数可以写作
约束条件:y=Dx
或者
上式中的||x||0为x的0范式,表示向量x包含的非零元素的个数。由于已有 一些稀疏表达的优化方法方面的数学工具(见参考文献[6]),可以自动从字典中 选取有效的原子表示信号,所以本发明将其应用到时空关联性数据挖掘中,以达 到从整个交通网络中自动地选取与目标传感器相关的时空关联传感器、并将时空 关联传感器的数据作为预测模型的输入用于预测的目的。
参考文献
[1]Williams,B.M.,Durvasula,P.K.,Brown,D.E.,1998.Urban freeway traffic flow prediction:Application of seasonal autoregressive integrated moving average and exponential smoothing models.Transportation Research Record1644,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 C10,303–321.
[3]Stathopouos,A.,Karlaftis,A.,S.,2003.A multivariate state space approach for urban traffic flow modeling and prediction.Transportation Research Part C11, 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 C13,211-234.
[5]Min,W.,Wynter,L.,2011.Real-time road traffic prediction with spatio-temporal correlations.Transportation Research Part C19,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个时刻整个交通网的状 态表示为提前τ时刻对传感器j采集的交通流量数据进行预 测的线性回归模型为:
上式中的权重为待优化的模型参数,为预测值;
(d)挖掘时空关联性:通过稀疏表达的优化方法自动得到模型参数wj,权 重表示整个交通网络的各个传感器的数据对于预测目 标传感器j的数据而言的时空关联性,当时,传感器k的数据与传感器j 的数据之间没有关联性,否则值的大小表示传感器k的数据与传感器j的数 据之间关联程度的强弱,k=1,2,...,m;
(e)以时空关联数据为预测模型的输入进行交通流预测。
本发明中,所述的步骤(d)有三种优化的目标,分别用(d1)、(d2)和(d3) 表示,具体如下:
(d1)所述的稀疏表达方法要优化的目标为:
上式中,表示从第1到第n时刻所有传感器采集的交通 流数据,其中第i个时刻交通网中m个传感器采集的交通流量为
(d2)所述的稀疏表达方法要优化的目标为:
式中,L0为预先设定的门限,用于控制向量wj中非零元素个数;上式表达的 优化目标通过Orthogonal Matching Puisuit(OMP)算法进行求解【Tropp,J.A., 2004.Greed is good:algorithmic results for sparse approximation.IEEE Trans. Information Theory50,2231-2242.】;
(d3)所述的稀疏表达方法要优化的目标为:
式中,||wj||1为wj的1范式,表示向量wj中所有元素绝对值之和,ε0是一个 预先设定的门限,用于控制预测误差||Vwj-vj||2;上式表达的优化目标等价地表 示为加入拉格朗日乘子λ的无约束条件的优化目标:
上式表达的优化目标通过Least Angle Regression Stagewise(LARS)算 法进行求解【Efron,B.,Hastie,T.,Johnstone,I.,Tibshirani,R.2004.Least angle regression.Annals of Statistics32(2),407-499.】。
本发明中,预测模型采用多因子线性回归模型外,也可采用向量自回归模型、 反向传播神经网络模型、径向基函数神经网络模型等。
本发明提出的方法可以从整个交通网络中自动地确定与预测目标节点的传 感器相关的时空关联传感器,并以时空关联传感器的数据作为预测模型的输入, 而不需要根据人工经验手动选取目标节点邻近范围的交通路段流量数据作为预 测模型的输入,相对于凭借人工经验从邻近范围选取的传感器数据作为输入,本 发明提出的全自动时空关联数据挖掘提升了预测模型的预测性能。
附图说明
图1为本发明方法的流程图。
具体实施方式
如图1所示,本发明涉及的交通流预测可分为五个环节,包括数据采集、数 据预处理、预测模型建立、时空关联数据挖掘和以交通流预测。其中涉及的数据 采集是通过布局到交通网各个节点的传感器获得的交通流量数据;数据预处理是 将采集的原始数据处理为有效的交通流数据;时空关联数据挖掘是通过稀疏表达 的优化方法自动地选取对于预测目标相关的时空关联数据的方法;交通流预测是 以时空关联数据为预测模型的输入进行的预测。具体实施方式如下:
实施例1:
(步骤1)数据采集:通过布局到交通网各个节点的传感器,采集以30秒 为单位时间的交通数据流,得到整个交通网络各个传感器记录的数据,用矩阵的 形式表示为:
其中M为整个交通网中传感器的个数,N为以30秒为单位的时间序列的长 度,表示传感器j在第i个时刻对应的30秒内记录的交通流量;
(步骤2)预处理:首先对原始数据进行时间尺度调整,将单位时间为30 秒的交通流数据转化为单位时间为10分钟的数据,即数据转化为如下矩阵形式:
其中然后对的每一列求得标准差,记std(j)为 第j列的标准差,如果std(j)<20,则认为传感器j的记录为无关记录,从矩阵 中删除,从而得到有效交通流数据V∈Rm×n,其中m为预处理后参与预测的传 感器的个数;完成如上所述的预处理后,用于交通流预测的数据转化为如下矩阵 形式:
(步骤3)建立预测模型:令表示交通网中的传感器j在第i个时刻记录 的交通流数据,对于交通网中参与预测的m个传感器,则在第i个时刻整个交通 网的状态表示为提前τ时刻对传感器j的流量进行预测的多 因子线性回归模型为:
上式中的权重为待优化的模型参数,为预测值,τ 分别取1、2、3、4、5、6,即分别提前10分钟、20分钟、30分钟、40分钟、 50分钟、60分钟对传感器j的流量进行预测;
(步骤4)时空关联性挖掘:通过稀疏表达的优化方法自动得到模型参数wj, 权重表示整个交通网络的各个传感器的数据对于预测 目标传感器j的数据而言的时空关联性,当时,传感器k的数据与传感器 j的数据之间没有关联性,否则值的大小表示传感器k的数据与传感器j的数 据之间关联程度的强弱,k=1,2,...,m;首先对V的每一列和 进行如下归一化处理,得到
所述的稀疏表达方法要优化的目标为:
上式中L0为预先设定的门限,用于控制向量wj中非零元素个数;上式表达 的优化目标通过Orthogonal Matching Puisuit(OMP)算法进行求解【Tropp,J. A.,2004.Greed is good:algorithmic results for sparse approximation.IEEE Trans. Information Theory50,2231-2242.】;
(步骤5)将步骤(4)求解得到的权重代入步骤(3)建立的预测模型, 得到如下预测结果:
上式中,只有中不为零的元素才参与预测,对应于时空关联传感器。
实施例2:
除步骤4外,其余部分与实施例1相同;
(步骤4)首先对V的每一列和进行如下归一化处理, 得到
稀疏表达方法要优化的目标为:
上式中||wj||1为wj的1范式,表示向量wj中所有元素绝对值之和,ε0是一个 预先设定的门限,用于控制预测误差表示向量的2范数,即向量中所有元素的平方和的平方根;上式表达的优化目标等价地表 示为加入拉格朗日乘子λ的无约束条件的优化目标:
上式表达的优化目标通过Least Angle Regression Stagewise(LARS)算 法进行求解【Efron,B.,Hastie,T.,Johnstone,I.,Tibshirani,R.2004.Least angle regression.Annals of Statistics32(2),407-499.】;求解时通过设定λ的值来控制中非零元素的个数,这里根据经验令λ=0.001,以获得较优的模型参数;
实施例3:
除步骤5外,其余部分与实施例2相同;
步骤(5):预测模型为向量自回归(VAR)模型【Chandra,S.R.,Al-Deek,H., 2009.Predictions of freeway traffic speeds and volumes using vector autoregressive models.Journal of Intelligent Transportation Systems13(2),53–72.】,具体计算公式 为:
上式中:B表示迟滞操作符,即Bdvt=vt-d;如果传感器i是传感器j的关联 传感器,即(步骤4)得到的向量的第i个元素不为零,则令反之令 为独立标准高斯噪声;为待优化的参数,可通过最大似然法训练得 到;
实施例4:
除步骤5外,其余部分与实施例2相同;
步骤(5):预测模型为BP神经网络(参考【Bishop,Ch.M.,1995.Neural Networks for Pattern Recognition.Oxford university press,ISBN0-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,ISBN0-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.,2011.Real-time road traffic prediction with spatio-temporal correlations.Transportation Research Part C19,606–616.】:
上式中n表示预测过的交通数据的总数,表示传感器j采集到的交通流的 真实值,为预测值。表1-6列出的精度是60个目标传感器预测精度的平均值。
表1:选取10,15,20,25,30个邻近传感器作为关联传感器与稀疏表达方法挖 掘的关联传感器在提前10分钟预测时的准确率
表2:选取10,15,20,25,30个邻近传感器作为关联传感器与稀疏表达方法挖 掘的关联传感器在提前20分钟预测时的准确率
表3:选取10,15,20,25,30个邻近传感器作为关联传感器与稀疏表达方法挖 掘的关联传感器在提前30分钟预测时的准确率
表4:选取10,15,20,25,30个邻近传感器作为关联传感器点与稀疏表达方法 挖掘的关联传感器在提前40分钟预测时的准确率
表5:选取10,15,20,25,30个邻近传感器作为关联传感器与稀疏表达方法挖 掘的关联传感器在提前50分钟预测时的准确率
表6:选取10,15,20,25,30个邻近传感器作为关联传感器与稀疏表达方法挖 掘的关联传感器在提前60分钟预测时的准确率
机译: 基于时空关联挖掘的交通流量预测方法
机译: 基于时间和空间的数据挖掘交通流量预测方法
机译: 基于时空相关的短期交通流量预测方法