基于R-FPOP变点检测的城市路段旅行时间预测
|
摘要
针对城市路段旅行时间精准推送的不足,提出一种基于动态规划变点检测算法的旅行时间预测方法。以车牌识别数据为研究对象,利用R-FPOP算法对旅行时间均值变点进行在线检测,研究变点时域分布特征;基于均值变点检测结果,预测旅行时间并给出其预测区间。结果表明:在线检测出的变点能够有效辨识旅行时间的均值突变,变点时域分布主要集中在高峰期;旅行时间预测值对实际序列变化趋势估计准确,推送的预测区间平均覆盖率为79.54%,具有较优的预测精度。论文方法兼顾旅行时间均值突变且建模简单,可为路段旅行时间的在线智能推送及交通需求者的路线规划提供技术支持。
For the shortcomings of the precise pushing of urban road section travel time,a travel time prediction method based on dynamic programming algorithm for change point detection was proposed. The license plate recognition data was used as the research object,and the robust functional pruning optimal partitioning( R-FPOP)algorithm was used to detect the mean change points of travel time sequences online. Further,the temporal distribution characteristics of the change points were studied. Based on the detection results of the mean change points,the road section travel time sequences were predicted and their prediction intervals were given. The results show that the mean change of the travel time sequences can be effectively identified by the detected change points online,and the temporal distributions of the change points were mainly concentrated in the peak period. The predicted values of the travel time were estimated accurately for the change trend of actual sequences. The average coverage ratio of the pushed prediction intervals is 79.54%,and the prediction accuracy of the travel time is excellent. The method takes into account the mean change of the travel time sequences and is simple to model,which&could provide technical support for the intelligent pushing of road section travel time online and route planning for traffic demanders.
For the shortcomings of the precise pushing of urban road section travel time,a travel time prediction method based on dynamic programming algorithm for change point detection was proposed. The license plate recognition data was used as the research object,and the robust functional pruning optimal partitioning( R-FPOP)algorithm was used to detect the mean change points of travel time sequences online. Further,the temporal distribution characteristics of the change points were studied. Based on the detection results of the mean change points,the road section travel time sequences were predicted and their prediction intervals were given. The results show that the mean change of the travel time sequences can be effectively identified by the detected change points online,and the temporal distributions of the change points were mainly concentrated in the peak period. The predicted values of the travel time were estimated accurately for the change trend of actual sequences. The average coverage ratio of the pushed prediction intervals is 79.54%,and the prediction accuracy of the travel time is excellent. The method takes into account the mean change of the travel time sequences and is simple to model,which&could provide technical support for the intelligent pushing of road section travel time online and route planning for traffic demanders.
引文
[1]赵卓峰,丁维龙,张帅.海量车牌识别数据集上基于时空划分的旅行时间计算方法[J].电子学报,2016,44(5):1227-1233.
[2]AHMAD S,LAVIN A,PURDY S,et al. Unsupervised real-time anomaly detection for streaming data[J]. Neurocomputing,2017,262:134-147.
[3]LV Y,DUAN Y,KANG W,et al. Traffic flow prediction with big data:a deep learning approach[J]. IEEE Transactions on Intelligent Transportation Systems,2015,16(2):865-873.
[4]GUO T,XU Z,YAO X,et al. Robust online time series prediction with recurrent neural networks[C]//International Conference on Data Science and Advanced Analytics. Montreal,Canada:IEEE,2016:816-825.
[5]COMERT G,BEZUGLOV A,CETIN M. Adaptive traffic parameter prediction:effect of number of states and transferability of models[J]. Transportation Research Part C:Emerging Technologies,2016,72(11):202-224.
[6]柴华骏,李瑞敏,郭敏.基于车牌识别数据的城市道路旅行时间分布规律及估计方法研究[J].交通运输系统工程与信息,2012,12(6):41-47.
[7]王晓原,隽志才,贾洪飞,等.交通流突变分析的变点统计方法研究[J].中国公路学报,2002,15(4):69-74.
[8]JEON S,HONG B. Monte Carlo simulation-based traffic speed forecasting using historical big data[J]. Future Generation Computer Systems,2016,65:182-195.
[9]SUREGAONKAR S,ASHOK S D,KARAR V,et al. Change point monitoring for vehicle incident detection at intersection[C]//International Conference on Science Technology Engineering and Management. Chennai,India:IEEE,2017:100-105.
[10]YAN Q,SUN Z,GAN Q,et al. Automatic identification of nearstationary traffic states based on the PELT changepoint detection[J]. Transportation Research Part B:Methodological,2018,108(2):39-54.
[11]ARNESEN P,HJELKREM O A. An estimator for traffic breakdown probability based on classification of transitional breakdown events[J]. Transportation Science,2017,52(3):593-602.
[12]SHENG R,ZHONG S,BARNETT A G,et al. Effect of traffic legislation on road traffic deaths in Ningbo,China[J]. Annals of Epidemiology,2018,28(8):576-581.
[13]ZHAO Z,KOUTSOPOULOS H N,ZHAO J. Detecting pattern changes in individual travel behavior:a Bayesian approach[J].Transportation Research Part B:Methodological,2018,112(06):73-88.
[14]KIDANDO E,MOSES R,SANDO T,et al. Evaluating recurring traffic congestion using change point regression and random variation Markov structured model[J]. Transportation Research Record,2018,2672(20):63-74.
[15]AMINIKHANGHAHI S,COOK D J. A survey of methods for time series change point detection[J]. Knowledge and Information Systems,2017,51(2):339-367.
[16]WU J,CHEN Y,ZHOU S,et al. Online steady-state detection for process control using multiple change-point models and particle filters[J]. IEEE Transactions on Automation Science and Engineering,2016,13(2):688-700.
[17]RIGAILL G. A pruned dynamic programming algorithm to recover the best segmentations with 1 to Kmax change-points[J]. Journal de la SociétéFrancaise de Statistique,2015,156(4):180-205.
[18]JACKSON B,SCARGLE J D,BARNES D,et al. An algorithm for optimal partitioning of data on an interval[J]. IEEE Signal Processing Letters,2005,12(2):105-108.
[19]AUGER I E,LAWRENCE C E. Algorithms for the optimal identification of segment neighborhoods[J]. Bulletin of Mathematical Biology,1989,51(1):39-54.
[20]KILLICK R,FEARNHEAD P,ECKLEY I A. Optimal detection of changepoints with a linear computational cost[J]. Journal of the American Statistical Association,2012,107(500):1590-1598.
[21]TRUONG C,OUDRE L,VAYATIS N. Selective review of offline change point detection methods. Ar Xiv e-print,2019,1801.00718v2.
[22]MAIDSTONE R,HOCKING T,RIGAILL G,et al. On optimal multiple changepoint algorithms for large data[J]. Statistics and Computing,2017,27(2):519-533.
[23]FEARNHEAD P,RIGAILL G. Changepoint detection in the presence of outliers[J]. Journal of the American Statistical Association,DOI:10.1080/01621459.2017.1385466.
[24]HAYNES K,ECKLEY I A,FEARNHEAD P. Computationally efficient changepoint detection for a range of penalties[J]. Journal of Computational and Graphical Statistics,2017,26(1):134-143.
[25]YAO Y C,AU S T. Least-squares estimation of a step function[J]. Sankhyā:The Indian Journal of Statistics,Series A,1989,51(3):370-381.
[26]HUBER P J. Robust statistics[M]//LOVRIC M. International Encyclopedia of Statistical Science. Berlin,Heidelberg:Springer,2011:1248-1251.
[27]FRYZLEWICZ P. Wild binary segmentation for multiple changepoint detection[J]. The Annals of Statistics,2014,42(6):2243-2281.
[2]AHMAD S,LAVIN A,PURDY S,et al. Unsupervised real-time anomaly detection for streaming data[J]. Neurocomputing,2017,262:134-147.
[3]LV Y,DUAN Y,KANG W,et al. Traffic flow prediction with big data:a deep learning approach[J]. IEEE Transactions on Intelligent Transportation Systems,2015,16(2):865-873.
[4]GUO T,XU Z,YAO X,et al. Robust online time series prediction with recurrent neural networks[C]//International Conference on Data Science and Advanced Analytics. Montreal,Canada:IEEE,2016:816-825.
[5]COMERT G,BEZUGLOV A,CETIN M. Adaptive traffic parameter prediction:effect of number of states and transferability of models[J]. Transportation Research Part C:Emerging Technologies,2016,72(11):202-224.
[6]柴华骏,李瑞敏,郭敏.基于车牌识别数据的城市道路旅行时间分布规律及估计方法研究[J].交通运输系统工程与信息,2012,12(6):41-47.
[7]王晓原,隽志才,贾洪飞,等.交通流突变分析的变点统计方法研究[J].中国公路学报,2002,15(4):69-74.
[8]JEON S,HONG B. Monte Carlo simulation-based traffic speed forecasting using historical big data[J]. Future Generation Computer Systems,2016,65:182-195.
[9]SUREGAONKAR S,ASHOK S D,KARAR V,et al. Change point monitoring for vehicle incident detection at intersection[C]//International Conference on Science Technology Engineering and Management. Chennai,India:IEEE,2017:100-105.
[10]YAN Q,SUN Z,GAN Q,et al. Automatic identification of nearstationary traffic states based on the PELT changepoint detection[J]. Transportation Research Part B:Methodological,2018,108(2):39-54.
[11]ARNESEN P,HJELKREM O A. An estimator for traffic breakdown probability based on classification of transitional breakdown events[J]. Transportation Science,2017,52(3):593-602.
[12]SHENG R,ZHONG S,BARNETT A G,et al. Effect of traffic legislation on road traffic deaths in Ningbo,China[J]. Annals of Epidemiology,2018,28(8):576-581.
[13]ZHAO Z,KOUTSOPOULOS H N,ZHAO J. Detecting pattern changes in individual travel behavior:a Bayesian approach[J].Transportation Research Part B:Methodological,2018,112(06):73-88.
[14]KIDANDO E,MOSES R,SANDO T,et al. Evaluating recurring traffic congestion using change point regression and random variation Markov structured model[J]. Transportation Research Record,2018,2672(20):63-74.
[15]AMINIKHANGHAHI S,COOK D J. A survey of methods for time series change point detection[J]. Knowledge and Information Systems,2017,51(2):339-367.
[16]WU J,CHEN Y,ZHOU S,et al. Online steady-state detection for process control using multiple change-point models and particle filters[J]. IEEE Transactions on Automation Science and Engineering,2016,13(2):688-700.
[17]RIGAILL G. A pruned dynamic programming algorithm to recover the best segmentations with 1 to Kmax change-points[J]. Journal de la SociétéFrancaise de Statistique,2015,156(4):180-205.
[18]JACKSON B,SCARGLE J D,BARNES D,et al. An algorithm for optimal partitioning of data on an interval[J]. IEEE Signal Processing Letters,2005,12(2):105-108.
[19]AUGER I E,LAWRENCE C E. Algorithms for the optimal identification of segment neighborhoods[J]. Bulletin of Mathematical Biology,1989,51(1):39-54.
[20]KILLICK R,FEARNHEAD P,ECKLEY I A. Optimal detection of changepoints with a linear computational cost[J]. Journal of the American Statistical Association,2012,107(500):1590-1598.
[21]TRUONG C,OUDRE L,VAYATIS N. Selective review of offline change point detection methods. Ar Xiv e-print,2019,1801.00718v2.
[22]MAIDSTONE R,HOCKING T,RIGAILL G,et al. On optimal multiple changepoint algorithms for large data[J]. Statistics and Computing,2017,27(2):519-533.
[23]FEARNHEAD P,RIGAILL G. Changepoint detection in the presence of outliers[J]. Journal of the American Statistical Association,DOI:10.1080/01621459.2017.1385466.
[24]HAYNES K,ECKLEY I A,FEARNHEAD P. Computationally efficient changepoint detection for a range of penalties[J]. Journal of Computational and Graphical Statistics,2017,26(1):134-143.
[25]YAO Y C,AU S T. Least-squares estimation of a step function[J]. Sankhyā:The Indian Journal of Statistics,Series A,1989,51(3):370-381.
[26]HUBER P J. Robust statistics[M]//LOVRIC M. International Encyclopedia of Statistical Science. Berlin,Heidelberg:Springer,2011:1248-1251.
[27]FRYZLEWICZ P. Wild binary segmentation for multiple changepoint detection[J]. The Annals of Statistics,2014,42(6):2243-2281.