1 Urban Road Network Traffic Flow Prediction Based on High-order Multi-variable Markov Chain and Environmental Influential Factor Yaoyao Feng 1, Weibin Zhang 1,YongQi 2,Haifeng Guo 3 (1. Nanjing University of Science and Technology, School of Electronic and Optical Engineering, Nanjing 210094; 2. Nanjing University of Science and Technology, School of Computer Science and Engineering, Nanjing 210094) Abstract: With the rapid development of the economy, the number of motor vehicles is increasing rapidly. The contradiction between the limited roads of the city and the huge number of traffic flows is increasing. The problem of traffic management has become a hot issue in society. As an important issue in traffic management, traffic flow forecasting of urban road network has attracted the attention of many scholars at home and abroad.in this paper, the high-order multivariate Markov model is used to analyze and predict the traffic flow at the upstream and downstream intersections, and the EM algorithm is used to find the hidden relationship between the traffic flow at the upstream and downstream intersections,this hidden relationship is defined as an environmental impact factor of urban road network and is (2016YFE0108000) (20172011A022)
effectively utilized in traffic flow prediction,increased prediction accuracy by about 30%. key words: Traffic flow prediction; Higher order multivariate Markov chain; EM algorithm; Environmental impact factor [1] [2] [3,4] [5] [6] EM SCATS 2018 6 12 1
1 [7] 2 3 1., [8],, q i, qi [ qik], k 1,..., N, N,(1) q i, q j, q j, C ij cov( i, j) (1) D( q ) D( q ) i j : Eq ( i ) q i ; Dq ( i ) i q ; cov( i, j) E( qq i j) E( qi) E( qj), q i, q Cij =0.8174 2. j
{ x ( k ) k 1,2,, s; t 1,2 N} i,j t 1 c ( d) ( x x )( x x ), d 0,1,, N1 (2) Nd ( ij) () i () i ( j) ( j) td t N t1 d i,j r Nd () i () i ( j) ( j) ( ij) ( xt x )( xt d x ) ( ij) c ( d) t1 ( d) c (0) c (0) ( ii) ( ii) N N () i () i 2 ( j) ( j) 2 ( xt x ) ( xt x ) t1 t1 (3) d 0,1,, N 1,1 is,1 j s ( ij r ) ( d) 0.3 d ( ij) d d ( ij) d d ( ij) [9] 1 ( ij) d d 185 ( ij r ) ( d) 0.3 185 1
[10] 2 2
[11,12] { x ( k ), k 1,2; t 1,2...} 10 { x ( k ), k 1,2; t 1,2...} n Markov t j r+1 rr-1 r-n+1 [13] t s n ( k) ( h) ( j) ( jk) r1 jk rh1 h j1 h1 x x P, k 1,2,..., s, r n1, n,... (4) ( h ) jk 0, 1 j, k s, 1 hn s n ( h) jk 1, k 1, 2,..., s P ( jk ) h j1 h1 r-h+1 r r+1 h j (1) (2) ( s) X ( X, X,..., X ) ( j ) ( j ) ( j (, ),..., ( j X x x x ) ) Markov r1 r1 r1 r1 r r r1 rn1 (11) (12) (1 s) B B B (21) (22) (2 s) B B B X r 1 X r XrQ (1) s (2) s ( ss) B B B (5) B ( ii) (1) ( ii) ii P1 I 0 0 (2) ( ii) ii P2 0 I 0 P 0 0 I ( n1) ( ii) ii n1 ( n) ( ii) ii Pn 0 0 0 mnmn B P 0 0 0 0 0 0 0 0 0 ( n) ( ij) ij Pn 0 0 0 0 (1) ( ij) ij 1 (2) ( ij) ij P2 ( ij) (1) ( ij) ij P3 mnmn
( h ) Q X XQ. X XQ i j ( h) jk [14] 2 min X XQ h 2 jk s n h h st.. jk 1, j1, 2,, s jk 0 j1 h1 (6) (1) (2) (3) X ( X, X, X ) ( k ) ( k ) ( k ( ˆ, ˆ ),, ˆ ( k X x x x ) ) k t1 t1 t1 t1 ( k ) t 1 1 2 t1 t1 t tn1 xˆ (,, m) t 1 ( k x ) t 1 xˆ l, max{ } (7) ( k ) t1 l 1 i m i r N s t1 k1 I(, tk) N (8) 1 xˆ t xt I(, tk) Itk (, )= 0 [15] [16] 3 { V 1, V 2, V n }
3 X ( x T 1, x T 2,, x T n ) G px (, ) k fk( xi k, k) (9) k1 fk( xi k, k) k k k (, ) k k [17] 1 1 { ( xik) k ( xik)} 2 T e fk( xi k, k)= (2 ) p/2 k 1/2 (10) Y ( X, Z) yi ( xi, zi) X { x1, x2,, x n } Z Z ( z1, z2,, z G ) G z j 1 xi group( j) 0 xi group( j) (11)
n G L,, z x) z [log f ( x )] (12) k k k k k k i k i1 k1 z k EM EM E-step z k Q E L X Z L X Z f Z dz ( 1) 1 (, i i ) (log (, )) log (, ) ( ) z (13) Z d 1 1 ( xi, k, k) 2 2 2 k fk( xi k, k) k(2 ) k e k G G d 1 1 ( xi, j, j) (, ) 2 2 2 j f j xi j j j(2 ) k e j1 j1 (14) M-step ( i 1) Q(, ) * * ( i) ( i 1) arg max Q(, ) (15) k zˆ n i1 k n k ( zx ˆk i)/ n n i1 T ( zˆ ( x )( x ) )/( zˆ ) n k k i k i k k i1 i1 201867 802803 803802 612 4 n
4 r 0.5188 EM 5 (a)
(b) 5 t 1 t 802803 5 12 3 45 256 (a)2
(b)5 6 2 r 0.7775 5 r 0.8201 ARMA ARMA ARIMA ARMA EM
EM 5 5 [1] Okutani I, Stephanedes Y J. Dynamic prediction of traffic volume through Kalman filtering theory[j]. Transportation Research Part B: Methodological, 1984, 18(1): 1-11. [2] M. S. Ahmed, A. R. Cook. Analysis of freeway traffic time-series data by using Box-Jenkins Techniques. Transportation Research Record, 1979, 722:1-9 [3] I. Okutani. The Kalman filtering approaches in some transportation and traffic problems.transportation Research Record, 1987, 2(1):397-416 [4] H. Ji, A. Xu, X. Sui, et al. The applied research of Kalman in the dynamic travel timeprediction.2010 18th International Conference on Geoinformatics. Beijing:IEEE, 2010:1-5 [5] Ledoux C. An urban traffic flow model integrating neural networks[j]. Transportation Research Part C: Emerging Technologies, 1997, 5(5): 287-300. [6] W. X. Yu, J. Su, W. C. Zhang. Research on short-term traffic flow prediction based on wavelet denoising preprocessing. 2013 Ninth international conference on Natural computation(icnc). Shenyang:IEEE, 2013:252-256 [7]. [D].,2017. [8],,,.[J].( ),2011,51(03):313-317 [9]. Markov [D].,201260. [10] Zhang, W., Qi, Y., Kris, H., Tang, J., Wang, Y., Vehicle traffic delay prediction in ferry terminal based on Bayesian multiple models combination method, Transportmetrica A: Transport Science. vol 42, no. 8, pp. 467-490. 2017 [11] Hofleitner, A., Herring, R., Bayen, A., Arterial travel time forecast with streaming data: A hybrid approach of flow modeling and machine learning, Transportation Research Part B., vol. 46, pp.1097-1122, 2012. [12] Park, J., Chebbah, M., Jendoubi, S., Martin A., Second-Order Belief Hidden Markov Models, Oxford, United Kingdom, 2014, pp. 284-293, 2014. [13] Ching, W.K., Fung, E.S., Ng M.K., A multivariate Markov chain model for categorical data sequences and its applications in demand predictions, IMA Journal of Management Mathematics, vol. 2002, no. 13, pp. 187-199, 2002. [14] Chvatal, V., Linear Programming, Freeman, New York, 1983.
[15] Yang M SLai C Y.A robust EM clustering algorithm for Gaussian mixture models[j].patter Recognition201245103950-3961. [16]. EM [J].200622 11244-246. [17] Quost B, Denœux T. Clustering and classification of fuzzy data using the fuzzy EM algorithm[j]. Fuzzy Sets & Systems, 2016, 286(2):134-156. 15195989213yaoyao_feng@126.com 13236532288weibin.zhang@njust.edu.cn