J. Cent. South Univ. (2016) 23: 2728-2734
DOI: 10.1007/s11771-016-3334-3
Three-stage approach for dynamic traffic temporal-spatial model
LU Hua-pu(陆化普)1, SUN Zhi-yuan(孙智源)1, 2, QU Wen-cong(屈闻聪)1
1.Institute of Transportation Engineering, Tsinghua University, Beijing 100084, China;
2.College of Metropolitan Transportation, Beijing University of Technology, Beijing 100124, China
Central South University Press and Springer-Verlag Berlin Heidelberg 2016
Abstract: In order to describe the characteristics of dynamic traffic flow and improve the robustness of its multiple applications, a dynamic traffic temporal-spatial model (DTTS) is established. With consideration of the temporal correlation, spatial correlation and historical correlation, a basic DTTS model is built. And a three-stage approach is put forward for the simplification and calibration of the basic DTTS model. Through critical sections pre-selection and critical time pre-selection, the first stage reduces the variable number of the basic DTTS model. In the second stage, variable coefficient calibration is implemented based on basic model simplification and stepwise regression analysis. Aimed at dynamic noise estimation, the characteristics of noise are summarized and an extreme learning machine is presented in the third stage. A case study based on a real-world road network in Beijing, China, is carried out to test the efficiency and applicability of proposed DTTS model and the three-stage approach.
Key words: dynamic traffic flow; temporal-spatial model; big-data driven
1 Introduction
During the past decade, the digital city and smart city have arrived one after another in rapid succession, and promoted the advent of big data era. The journal Nature published a special issue of “Big Data” [1] in 2008. And the journal Science published a special issue of “Dealing with Data” [2] in 2011. In the research field of transportation, the traditional data collection approach has been converted to the electrical devices and its advanced applications. Therefore, traffic big data was born and made the comprehensive access, deep analysis and long-term storage of dynamic traffic flow possible. Literature review shows that dynamic traffic flow holds the following characteristics: 1) Temporal correlation [3]; 2) Spatial correlation [4]; 3) Historical correlation [5]; 4) Multiple traffic states [6].
Researches on these characteristics provide some foundations for data quality assurance [7], traffic state estimation [8], short-term traffic flow forecasting [9], real-time traffic control [10] and dynamic route guidance service [11], etc.
Recently, there is a vivid discussion in the literature concerning temporal-spatial model. SHENG et al [12] studied the impact of the location of the intersections, the travel habits of residents and traffic management on traffic flow. CHEN et al [13] established a temporal- spatial model, considering queue length parameters, to reveal mechanism of traffic congestion. To describe the temporal-spatial distribution and evolution of traffic state, CHEN et al [14] improved Moran’s I to calibrate temporal-spatial characteristics of traffic flow. Based on temporal-spatial relevance of traffic flow, an improved random cellular transmission model was realized by PAN et al [15] to predict traffic flow. Expressing temporal-spatial characteristics of traffic flow with distance measurements and state vectors, the KNN algorithm was ameliorated by WU et al [16] to improve the accuracy of short-term traffic flow forecasting.
The existing researches can be divided into three types: empirical model, mechanistic model and data-driven model. These three types of models have their own advantages and disadvantages: 1) Empirical models are based on experience and with low accuracy; 2) Mechanistic models are complicated to be established and calibrated; 3) Data-driven models are difficult to be extended, with low interpretability of results.
The conception of big data, however, promotes the generation of big-data-driven modeling ideas and the integration of these three types of models. A new way for the establishment of DTTS is put forward in this background.
2 Basic DTTS model
With consideration of the temporal correlation, spatial correlation and historical correlation of dynamic traffic flow, the basic DTTS model [17] can be expressed as follows:
(1)
s.t.
(2)
(3)
where Vs(t) is the traffic flow parameters of section S during time t, which represents traffic volume, speed or occupancy; VT(t) is the value of Vs(t) inferred by temporal correlation; VS(t) is the value of Vs(t) inferred by spatial correlation; VH(t) is the value of Vs(t) inferred by historical correlation; γT, γS, γH are weighting coefficients.
In general, VT(t) needs to be calculated through regression analysis, such as autoregressive integrated moving average model [18], the general expression of VT(t) is shown as:
(4)
s.t.
(5)
(6)
where Vs(t-d) is the traffic flow parameters of section s during time t-d; d is delay; θs,d is the weighting coefficient.
VS(t) needs to be calculated by neighborhood regression, such as K-nearest neighbor algorithm [19]. The general expression of VS(t) is shown as
(7)
s.t.
(8)
(9)
(10)
where Vi(t-d) is the traffic flow parameters of section i during time t-d; I is the set of neighborhood sections of section s; λi,d is the weighting coefficient.
VH(t) needs to be calculated based on Fourier transform algorithm [20]. The general expression of VH(t) is shown as:
(11)
where is the set of historical time-series data obtained by Fourier transform; if the time interval is 5 min, there will be 288 sampling points per day; the traffic flow parameters of virtual section h represents the historical traffic flow parameters of section s.
Substitute Eqs. (4), (7) and (11) into Eq. (1), and normalize to get:
(12)
s.t.
(13)
(14)
(15)
(16)
where Vj(t-d) is the traffic flow parameters of section j during time t-d; ωj,d is the weighting coefficient; η is the number of ωj,d; J is the set of section j, J={s, h, I}.
To meet the demand of real-time analysis, there are some problems with Eq. (12) that need to be solved:
1) The variables are so numerous and uncontrollable that the speed of data processing cannot be assured;
2) It is difficult to calibrate so many variables while ensuring high accuracy and speed of date processing;
3) The terms of the expression are fixed and lack of consideration of dynamic noise. The accuracy of data processing is affected by this problem.
It is necessary, therefore, to simplify and calibrate the proposed basic DTTS model.
3 Three-stage approach of simplification and calibration
3.1 Critical data pre-selection
The first stage is proposed to solve the problem that variables are numerous and uncontrollable. This stage is divided into two steps.
3.1.1 Critical sections pre-selection
Because of the spatial correlation, Vs(t) is influenced by Vi(t), and different sections i have different influence. The rule of critical sections pre-selection is shown as follows:
1) Section that has important influence is defined as critical section, and the corresponding variables are retained in the model;
2) Other sections should be deleted.
Then the section set I′ with fewer variables is obtained. Regarding one or several sections in upstream/downstream direction as critical sections belongs to the traditional method, which is lack of persuasion. Therefore, the Pearson correlation coefficient [21] is considered as the criterion of critical sections pre- selection:
(17)
where rs,i is the Pearson correlation coefficient of section s and section i; represents the Pearson correlation coefficient of volume, represents the Pearson correlation coefficient of speed; represents the Pearson correlation coefficient of occupancy; rs,i>0 represents the positive correlation and rs,i<0 represents the negative correlation, |rs,i|=1 represents a total equality and |rs,i|=0 represents a total inequality; is the arithmetic mean value of Vs(t), and is the arithmetic mean value of Vi(t).
Take as an example in Fig. 1, its value varies in different directions. And it decreases with the augmentation of distance in the same direction.
Fig. 1 Variation trend of Pearson correlation coefficient
Critical sections pre-selection is used for the preliminary determination of section set I′, and there is no need to determine a very small set. Therefore, r0=0.618 (the gold segmentation point of [0, 1]) is set as the threshold for pre-selection. Concrete steps are as follows:
Step 1: Along upstream/downstream direction, calculate rs,i in decreasing order of section spacing;
Step 2: If rs,i>r0, return to Step 1; otherwise go to Step 3;
Step 3: If there is an upstream/downstream direction that has not been calculated, change the direction and return to Step 1; otherwise go to Step 4;
Step 4: Keep the sections which satisfy rs,i≥r0, then the section set I′ is got.
3.1.2 Critical time pre-selection
From a comprehensive view of temporal, spatial and historical correlation, it is found that Vs(t) is influenced by Vj(t-d). Section j has different influences in different time t-d. The rules of critical time pre-selection are as follows:
1) Time point that has the most important influence is defined as critical time, and the corresponding variable is retained in the model;
2) Others should be deleted.
Then, the number of variables is further decreased. Based on Pearson correlation coefficient, a temporal- spatial correlation coefficient [22] is considered as the criterion of critical time pre-selection:
(18)
(19)
where rj,d defines the correlation between Vs(t) and Vj(t-d); represents the temporal-spatial correlation coefficient of volume;is the temporal-spatial correlation coefficient of speed;is the temporal- spatial correlation coefficient of occupation; rj is the maximum value of rj,d; corresponding time t-d is the critical time; n is the length of data sequence.
Take as an example (as shown in Fig. 2), the time interval of data is 5 min, and the value of d is the integral multiple of 5 min. The value of varies with delay time d, and is circled in the figure.
Fig. 2 Variation trend of temporal-spatial correlation coefficient
By pre-selection of critical sections and time, the number of variables in the basic model has decreased to the number of sections η′ in set J′ (J′={s, h, I′}).
3.2 Variable coefficient calibration
The second stage is intended to assure the accuracy and speed of data processing. This stage is also divided into two steps.
3.2.1 Basic model simplification
As critical data pre-selection has decreased the number of variables, noise is occurred to describe the comprehensive characteristics of the deserted variables. Because of the existences of correlation among each section, the variables and noises are not independent in the model, which brings difficulty for the calibration. The basic model simplification is presented to avoid this phenomenon. As rj signifies the influence of Vj(t-d) on Vs(t), a normalized coefficient ωj is introduced to replace the variable coefficients ωj,d in the model. The method to calculate ωj is:
(20)
s.t.
(21)
(22)
(23)
The replacement of coefficient brings in bias. Correction parameters φ and ε are introduced to control the bias. Formula (12) could transform into
(24)
s.t.
(25)
3.2.2 Stepwise regression analysis
The first stage focuses on the pre-selection and gives a relatively loose threshold where r0=0.618. And it makes η′, which is the number of sections in set J′ and is equal to the number of variables in Formula (24), still big. To further reduce variables based on experience or random methods belong to the traditional method, which is lack of objective judgment. Stepwise regression analysis [23] can help to decrease the number of variables while assuring the accuracy of model. On the basis of backward stepwise regression analysis, the threshold of coefficient of determination R2 is determined to realize goodness of fit test; simultaneously the threshold of mean absolute percent error (MAPE, Emap) is designed to realize the model error test. Concrete steps are shown as follows:
Step 1: For fit Formula (24) and obtain correction coefficient φ and ε;
Step 2: Realize the goodness of fit test, if R2≥0.90, then go to Step 4; otherwise, go to Step 3;
Step 3: Delete j with the lowest significance, update J′, and go back to Step 1;
Step 4: Realize error test for training set, if Emap≤0.10, then stop and note the final section set as J″; otherwise, return to Step 3.
By basic model simplification and stepwise regression analysis, the number of variables has been decreased to the number of sections η″ in set J″, and the unknown coefficient only includes φ and ε.
3.3 Dynamic noise estimation
The third stage is proposed to improve the accuracy from view of dynamic analysis. This stage also is divided into two steps:
3.3.1 Noise characteristics analysis
Traffic state is one of the impact factors of the temporal-spatial model [24]. However, it has not been considered in the basic DTTS and the first two stages. Its impact should be studied during the dynamic noise estimation. The noise is dynamic because of the temporal correlation characteristics of dynamic traffic flow. Besides, as the dynamic noise estimation is based on basic DTTS model and it is not a new method, there is a bound for the noise. That is to say, the noise varies within the standard deviation range of the first two stages. Therefore, to establish the model which considers dynamic noise, Eq. (24) should be expanded as follows:
(26)
s.t.
(27)
(28)
where is the fixed term of the model; Δ(t) is the dynamic term of the model, that is to say the dynamic noise term; σ is the normal error of the fixed term.
3.3.2 Extreme learning machine
Traffic state is a discrete variable, which makes it hard to control the error of the model. According to time-varying characteristics of traffic state, one day traffic flow can be divided into several time intervals. In each time interval, the traffic state is basically the same. With consideration of the peak hour characteristic, the division is implemented: 7:00-10:00 as T1, 10:00-17:00 as T2, 17:00-20:00 as T3, 20:00-7:00 of the next day as T4. The dynamic noise of different time intervals should be estimated independently.
As dynamic noise is time-varying and is related with the traffic flow parameters of each section in the model, the noise should be estimated through the following pattern matching relationship:
(29)
s.t.
(30)
Considering the advantages of extreme learning machine (ELM), such as its learning speed and generalization performance, it is chosen to study the pattern matching relationship above. The ELM network training model [25] uses forward single layer structure, as shown in Fig. 3.
Concrete steps are shown as follows:
Step 1: Determine the number of hidden layer neurons, and set randomly the bias of neuron b in hidden layer and weights w of connections between the input layer and hidden layer;
Step 2: Choose an infinitely differentiable function as the activation function g of neuron in the hidden layer, and calculate the output matrix H of the hidden layer;
Step 3: Calculate the connection weights β between the hidden layer and the output layer.
Fig. 3 Network training model of ELM
4 Case study
4.1 Data
Actual traffic data collected in Beijing, China are applied in this part. Researched section s and the set of its neighborhood section I are shown in Fig. 4. The data of each section during a week are used to study the three-stage approach of DTTS model. Basic data are collected by detectors every 5 min and each line includes collected time, volume, speed and occupancy. There are 2016 lines of data for each section.
Fig. 4 Road network topology map
4.2 Calculation
Simplification and calibration of basic DTTS are studied through three stages.
4.2.1 Critical data pre-selection
The traffic flow coefficients of section set J are analyzed and calculated to get section set J′, rj and its corresponding critical time t-d. 16 critical sections are pre-selected through volume; 7 are pre-selected through speed; 9 are pre-selected through occupancy. Table 1 shows the first 5 sections ranged by rj.
4.2.2 Variable coefficient calibration
Through basic model simplification and stepwise regression analysis, the following formulations are obtained:
(31)
(32)
Table 1 Results of key data preselection
(33)
Coefficient of determination of Eq. (31) is 0.90, coefficient of determination of Eq. (32) is 0.95 and coefficient of determination of Eq. (33) is 0.97.
4.2.3 Dynamic noise estimation
From the aspects of volume, speed and occupancy, the data of four time intervals are trained separately and the corresponding w, b, g and β are recorded. As shown in Fig. 5, by comparing two-stage model (without ELM) with three-stage model (with ELM), it is found that ELM may improve the accuracy of the model.
Fig. 5 Effectiveness analysis of ELM
4.3 Results and discussion
Considering the evident difference of traffic flow between peak hours and normal hours, MAPE (Emap) index is taken to analyze accuracy:
(34)
where yt is the accurate value of time t; is the estimated value of time t; and m is the length of data sequence.
As shown in Table 2, comparing with the existing system (traffic flow prediction system), the traffic flow model of which is based on nonparametric regression, the errors of the models in this work are relatively low, and the three-stage approach further reduces the error. The result shows the effectiveness of the proposed model.
In addition, case study all shows that the computation time of these three methods can reach the high real-time requirements.
The advantages of DTTS model are not only reflected in the higher accuracy, but also include:
1) The integration of empirical model, mechanism model and data-driven model is used to build the model system in this work. Based on knowledge and data, the mechanism model is simplified, and the model calibration is implemented based on data-driven; in order to improve the robustness of data-driven model, knowledge and mechanism are used to optimize data selection, reduce noise and select appropriate training sample; these three models are infiltrated with each other and complete each other.
Table 2 Precision analysis
2) The fixed term of the DTTS model describes the temporal correlation, spatial correlation and historical correlation of dynamic traffic flow from the perspective of mechanism. When there are some problems with data collection, it can rapidly evaluate the impacts and intuitively select the DTTS model that needs to be corrected. Besides, the revising process can be realized rapidly because of the simplicity of model calibration.
3) The dynamic term of the DTTS model describes the influence of traffic state variance on the temporal correlation, spatial correlation and historical correlation from the view of data-driven. As ELM is able to learn online, after the fixed term of the model is changed, the accuracy of the model will be stabilized through a period of data accumulation.
5 Conclusions
Based on big-data driven methods, a three-stage approach for DTTS model is put forward with consideration of the temporal correlation, spatial correlation, historical correlation, and multiple traffic states characteristic of dynamic traffic flow.
1) The proposed model consists of a fixed term and a dynamic term. The former focuses on the description of temporal correlation, spatial correlation, and historical correlation; while the latter emphasizes on the influence of traffic state on the temporal correlation, spatial correlation, and historical correlation. Case study verifies the feasibility and validity of this composition.
2) Future works may discuss the dynamic variation of such composition of DTTS model. Besides, applications of the proposed model should be more deeply studied. The application development can be extended to abnormal data identification, error data correction, missing data complementing, short-term traffic flow forecast, traffic state estimation, etc.
References
[1] FRANKEL F, REID R. Big data: Distilling meaning from data [J]. Nature, 2008, 455(7209): 30.
[2] LOS W, WOOD J. Dealing with data: Upgrading infrastructure [J]. Science, 2011, 331(6024): 1515-1516.
[3] ZHANG Yong, LI Shi-gao. Analysis of scale-free characteristic on sharp variation point of trafficc flow [J]. Acta Physica Sinica, 2014, 63(24): 240509. (in Chinese)
[4] CHANG Gang, ZHANG Yi, YAO Dan-ya. Missing data imputation for traffic flow based on improved local least squares [J]. Tsinghua Science and Technology, 2012, 17(3): 304-309.
[5] DONG Shen, LI Rui-min, SUN Li-guang, CHANG T H, LU Hua-pu. Short-term traffic forecast system of Beijing [J]. Transportation Research Record, 2010(2193): 116-123.
[6] XU Cheng-cheng, LIU Pan, WANG Wei, LI Zhi-bin. Evaluation of the impacts of traffic states on crash risks on freeways [J]. Accident Analysis and Prevention, 2012, 47: 162-171.
[7] TAN Hua-chun, WU Yuan-kai, CHENG Bin, WANG Wu-hong, RAN Bin. Robust missing traffic flow imputation considering nonnegativity and road capacity [J]. Mathematical Problems in Engineering, 2014, 2014: 763469.
[8] XU Dong-wei, DONG Hong-hui, LI Hai-jian, JIA Li-min, FENG Yuan-jing. The estimation of road traffic states based on compressive sensing [J]. Transportmetrica B: Transport Dynamics, 2015, 3(2): 131-152.
[9] WANG Jin, SHI Qi-xin. Short-term traffic speed forecasting hybrid model based on chaos-wavelet analysis-support vector machine theory [J]. Transportation Research Part C, 2013, 27(S1): 219-232.
[10] CHENG Rong-jun, HAN Xiang-lin, LO Siu-ming, GE Hong-xia. A control method applied to mixed traffic flow for the coupled-map car-following model [J]. Chinese Physics B, 2014, 23(3): 030507.
[11] LIANG Zi-lu, WAKAHARA Y. Real-time urban traffic amount prediction models for dynamic route guidance systems [J]. EURASIP Journal on Wireless Communications and Networking, 2014, 2014: 85.
[12] SHENG Peng, WANG Jun-feng, TANG Tie-qiao, ZHAO Shu-long. Long-range correlation analysis of urban traffic data [J]. Chinese Physics B, 2010, 19(8): 080205.
[13] CHEN Xi-qun, LI Li, LI Zhi-heng. Phase diagram analysis based on a temporal-spatial queueing model [J]. IEEE Transactions on Intelligent Transportation System, 2012, 13(4): 1705-1716.
[14] CHEN Shao-kuan, WEI Wei, MAO Bao-hua, GUAN Wei. Analysis on urban traffic status based on improved spatio-temporal Moran’s I [J]. Acta Physica Sinica, 2013, 62(14): 148901. (in Chinese)
[15] PAN T L, SUMALEE A, ZHONG R X, INDRA-PAYOONG N. Short-term traffic state prediction based on temporal-spatial correlation [J]. IEEE Transactions on Intelligent Transportation System, 2012, 14(3): 1242-1254.
[16] WU Shan-hua, YANG Zhong-zhen, ZHU Xiao-cong, YU Bin. Improved k-nn for short-term traffic forecasting using temporal and spatial information [J]. Journal of Transportation Engineering, 2014, 140(7): 04014026.
[17] LU Hua-pu, SUN Zhi-yuan, QU Wen-cong. Big data-driven based real-time traffic flow state identification and prediction [J]. Discrete Dynamics in Nature and Society, 2015, 2015: 284906.
[18] PENG Yu, LEI Miao, LI Jun-bao, PENG Xi-yuan. A novel hybridization of echo state networks and multiplicative seasonal ARIMA model for mobile communication traffic series forecasting [J]. Neural Computing & Application, 2014, 24(3/4): 883-890.
[19] ZHENG Zu-duo, SU Dong-cai. Short-term traffic volume forecasting: A k-nearest neighbor approach enhanced by constrained linearly sewing principle component algorithm [J]. Transportation Research Part C, 2014, 43(S1): 143-157.
[20] ZHANG Ru-hua, YANG Xiao-guang, CHU Hao. Application of signal sampling theory on traffic flow detector layout [J]. China Journal of Highway Transport, 2007, 20(6): 105-110. (in Chinese)
[21] GUYON I, ELISSEEFF A. An introduction to variable and feature selection [J]. Journal of Machine Learning Research, 2003, 3(7/8): 1157-1182.
[22] XIA Ying, LIANG Zhong-jun, WANG Guo-yin. Research of short- term traffic flow forecasting model based on spatio-temporal analysis [J]. Journal of Nanjing University: Natural Sciences, 2010, 46(5): 552-560. (in Chinese)
[23] DONG Hong-hui, SUN Xiao-liang, JIA Li-min, LI Hai-jian, QIN Yong. Traffic condition estimation with pre-selection space time model [J]. Journal of Central South University, 2012, 19(1): 206-212.
[24] LU Hua-pu, SUN Zhi-yuan, QU Wen-cong, WANG Ling. Real-time corrected traffic correlation model for traffic flow forecasting [J]. Mathematical Problems in Engineering, 2015, 2015: 348036.
[25] ALEXANDRE E, CUADRA L, SALCEDO-SANZ S, PASTOR- SANCHEZ A, CASANOVA-MATEO C. Hybridizing extreme learning machines and genetic algorithms to select acoustic features in vehicle classification applications [J]. Neurocomputing, 2014, 152: 58-68.
(Edited by FANG Jing-hua)
Foundation item: Project(2014BAG01B0403) supported by the National High-Tech Research and Development Program of China
Received date: 2015-06-16; Accepted date: 2015-11-19
Corresponding author: SUN Zhi-yuan, PhD; Tel: +86-10-62772615; E-mail: sunzhiyuan@bjut.edu.cn