CN110020475A - A kind of Markov particle filter method of forecasting traffic flow - Google Patents

Abstract

The invention relates to a Markov particle filtering method for traffic flow prediction. The invention combines the Markov chain and the particle filter algorithm, uses the Markov to replace the state space prediction model and determines the initial weight, and then performs multiple iterative updates through the particle filter algorithm to obtain the prediction result. Make up for the shortcomings of Markov's inapplicability to nonlinear systems and insufficient prediction accuracy. The error analysis of the prediction results is carried out to verify the applicability of the method. The invention determines the traffic flow state division, and can realize short-term traffic flow prediction. It can provide good theoretical support and decision-making basis for traffic control and guidance.

Description

A Markov Particle Filter Method for Traffic Flow Prediction

technical field

The invention designs a prediction model, in particular to a traffic flow prediction model of Markov particle filtering.

Background technique

In intelligent transportation system, short-term traffic flow prediction is one of the key technologies to realize advanced traffic control and traffic guidance. Aiming at the shortcomings of the current Markov traffic flow forecasting model in terms of accuracy, as well as the randomness and volatility of traffic flow, a Markov particle filter traffic flow forecasting model is proposed.

With the rapid economic development, the number of motor vehicles continues to increase, and a series of traffic problems have appeared, such as traffic congestion, traffic pollution, traffic accidents, etc., which affect people's daily life. In recent years, the phenomenon of traffic jams during morning and evening peak hours has become an inevitable problem in life, especially during holidays, traffic jams are the main factor affecting traffic capacity. In order to carry out traffic management and control reasonably, it is necessary to adopt effective control strategies to divert the traffic flow in the current time period, so as to improve road traffic congestion and reduce environmental pollution. Short-term traffic flow prediction has become an important research content.

A single traffic flow forecasting method has its own special information variables and applicable conditions, and can only predict traffic flow from different perspectives. Therefore, a single forecasting method has certain limitations for the traffic flow with strong random fluctuations, and the forecast results also have some limitations. A certain one-sidedness.

The uncertainty of traffic flow is strong, not only has the characteristics of random nonlinearity, but also abnormal changes in flow caused by external changes such as weather. Markov model is a powerful tool for measuring state space and analyzing time series data, but it can only obtain rough prediction results and is not suitable for nonlinear systems. Particle filter technology is highly adaptable to nonlinear systems and non-Gaussian noise environments. Therefore, the Markov chain is combined with the particle filter algorithm, the state space prediction model is replaced by Markov and the initial weight is determined, and then the particle filter algorithm is used for multiple iterative updates to obtain the prediction result. Make up for the shortcomings of Markov's inapplicability to nonlinear systems and insufficient prediction accuracy. The error analysis of the prediction results is carried out to verify the applicability of the method.

SUMMARY OF THE INVENTION

In view of this, the purpose of the present invention is to provide a traffic flow prediction model based on Markov particle filtering, which determines the state division of traffic flow and can realize short-term traffic flow prediction. It can provide good theoretical support and decision-making basis for traffic control and guidance.

In order to realize the purpose of the present invention, the technical scheme adopted is:

Before prediction, the sample data needs to be preprocessed, and the empty data caused by the detector failure is repaired by averaging the data of adjacent periods.

The correction formula is as follows:

x _k ------------- is the traffic flow at time k.

x _k-1 ------------ is the traffic flow at time k-1.

x _k+1 ------------ is the traffic flow at time k+1.

Since the Markov model is a prediction of state transitions, it is necessary to attribute the traffic flow to different states. The process is as follows:

The traffic flow state is represented by the state set S, and the historical sample data constitutes the traffic flow state set S={s ₁ , s ₂ ,...,s _n }.

The threshold method is used to determine the traffic flow state. Introduce parameters μ ₁ , μ ₂ .

μ ₁ =x _k-1(min) : I:x _k-1(max) (2)

μ ₂ ={θ ₁ , θ ₂ , . . . , θ _n } (3)

μ ₁ ---------- means that the traffic flow is divided into multiple states at intervals of I. Generally take I=5.

μ ₂ ---------- used to save the threshold.

x _k-1(min) ----- Indicates the minimum traffic flow at time k-1.

x _k-1(max) ----- Indicates the maximum traffic flow at time k-1.

I---------- indicates the traffic flow division interval.

θ _ι ------------ is the threshold, representing the state boundary value, a state has two boundary values, i=1,2,...,n.

s _i ------------ represents a state in the interval (θ _i-1 ,θ _i ], i=1,2,...,n.

Status set OK. Sort the traffic volume x _k-1 from large to small, and calculate the number of states Among them, if h is not an integer, the state s _h+1 is added as the last state. That is, sh ₊₁ =x _k-1(max) ; the state set is S={s ₁ , s ₂ , . . . , s _h , s _h+1 }.

h---------- indicates the number of states.

s _h+1 ------------- represents the h+1th state.

In order to build a Markov traffic flow prediction model, first determine the traffic state to which the sample traffic flow belongs, and then obtain the state transition matrix, and predict the future traffic state according to the state transition matrix. The specific process is as follows:

Determination of state transition probabilities. The state transition matrix shows that Markov has no aftereffect, that is, the state at time k is only related to the traffic state at time k-1. The transition of the traffic flow state from the state _si (k-1) at the current time k-1 to the state s _j (k) at the next time k is uncertain, and its possibility is expressed as its state transition probability by probability:

m _i ------------- represents the number of times the state _si appears in different time periods.

m _ij ------------ represents the number of transitions from state _si to state s _j .

p(s _i (k-1)→s _j (k)), p(s _j |s _i ), p _ij (k)-----------represents the transition from state _si to state probability of s _j .

Determination of state transition matrix. According to the determination of the state transition probability p _ij (k), the state transition matrix is then formed as follows:

P(k)------------represents the state transition matrix.

Satisfy

p _j (k)------------represents the probability of being in state j at time k.

Build a Markov particle filter prediction model. Methods as below:

Build an equation of state.

Create an observation equation.

u ₂ (k-1)-------state boundary value at time k-1.

------------ Predicted value at time k, i=1,2,...,n.

------------ Observations at time k, i=1,2,...,n.

------------Observation noise.

H-------------observed value coefficient, let it be the identity matrix E.

The principle of particle filter algorithm. Particle filtering is a nonlinear filtering algorithm based on the statistical method simulation method of sequential Monte Carlo method and recursive Bayesian estimation. Its core idea is to represent its probability distribution by random state particles extracted from the posterior probability. It is a sequential importance sampling method. For real-time dynamic systems, the dynamic space model is as follows:

Determining the equation of state and observation equation

x _k =f(x _k-1 )+u _k-1 (9)

y _k =h(x _k )+v _k (10)

x _k -------------- Predicted value at time k.

y _k -------------- Observations at time k.

u _k-1 ------------ process noise.

v _k-1 ------------Observation noise.

f(x _k-1 )------------- is the state equation of the system at time k-1.

h(x _k )------------- is the system observation equation at time k.

Prediction process:

Let z _k ={y _1:i |i=1,2,...,k} be the set of all observations from the initial time to the k time.

p(x _k |z _k-1 )=∫p(x _k |x _k-1 )p(x _k-1 |z _k-1 )dx _k-1 (11)

p(x _k |x _k-1 )-------------state transition probability density of state equation, obtained from state equation (10).

p(y _k |x _k )--------------observation probability density of the observation equation.

p(x _k-1 |z _k-1 )------------ is the posterior probability distribution, obtained from the sample data.

p(x _k |z _k-1 )------------- is the prior probability, which is obtained according to the state transition probability density p(x _k |x _k-1 ).

Status update process:

p(y _k |z _k-1 )=∫p(y _k |x _k )p(x _k |z _k-1 )dx _k (13)

Formulas (12) and (13) are only theoretical solutions, and it is difficult to calculate the results in practice. The basic principle is to generate a set of random sample particle sets, and use the particle sets to determine the posterior probability distribution function p(x _k |z _k ) for approximation, so as to obtain the predicted value at time k on the basis of the observed value, the particle represents the ith possible traffic flow, according to And the state equation is obtained; is the weight corresponding to the i-th predicted traffic flow, that is, the importance weight, It needs to be updated and normalized in each iteration. can be expressed as:

The delta-function is the Dirac delta function, which means that the function is equal to zero at points other than zero, and its integral over the entire domain is equal to 1.

x _0:k ------------- is the state set at time 0 to k.

∝--------------represents a proportional function.

------------- is the normalized weight corresponding to the i-th particle at time k.

------------- is the weight corresponding to the i-th particle at time k, and it satisfies

Resampling process:

The basic connotation of the particle filter algorithm is iteration, so that the center of gravity of the calculation is placed on the particles with larger weights to improve the accuracy of the prediction results. Therefore, the resampling algorithm is used. The idea is to copy the particles with larger weights and remove the weights. Particles with small values, but they also have the phenomenon of lack of particle diversity. A random resampling method is proposed, as follows:

Generate n random numbers {d _l , l=1, 2, .

record sample and as a new sample particle. Finally, press the interval [0,1] by Divide into n small intervals, when the random number d _l falls in the nth interval (λ _n-1 ,λ _n ], copy the corresponding sample

Description of drawings

Figure 1. Comparison between the two prediction methods and the actual traffic flow (all day)

Figure 2 Comparison of the two prediction methods and the actual traffic flow (morning peak)

Figure 3 Comparison of absolute error ER between two methods (all day)

Figure 4 Comparison of absolute error ER between two methods (morning peak)

Figure 5 Comparison of the relative error RER of the two methods (all day)

Figure 6 Comparison of the relative error RER of the two methods (morning peak)

Detailed ways

In order to further illustrate the technical solutions of the present invention, descriptions are given here in conjunction with the accompanying drawings and specific implementations. 1. Determine the reference standard value of each main parameter:

Step 1: Take historical traffic flow as sample data at a time interval of 5 minutes, divide the traffic flow state according to the sample data, and determine the traffic flow state set S={s ₁ , s ₂ ,...,s _n }.

Step2: Determine the required parameters, the number of particles is n, and h is the number of state sets.

Step3: Predict the traffic flow according to the Markov prediction model, and calculate the n particle parameters and set initial particle weights

------------- The predicted value of the ith particle at time k.

-------------The observed value of the ith particle at time k.

Step4: Update the particle weights. According to the formula Calculate the weight corresponding to each particle

------------ Predict the i-th particle at time k , the probability of obtaining the observed value y _k .

Through the weight normalization process of formula (16), we can get

Step5: Judge the sample reselection process. The similarity efficiency method is used to judge whether the particle sample is subjected to the resampling process. Calculate the effective sampling scale N _eff ,

N _th ------------- is the threshold, the threshold is set as N _th =2n/3, and n is the number of particles.

N _eff ------------- is the effective sampling scale.

When the effective sampling scale is smaller than the set threshold, that is, when N _eff ≤ N _th is satisfied, resampling is performed according to the random resampling method. Traffic flow is re-predicted with new sample particles.

When the effective sampling scale is greater than the set threshold, that is, when N _eff >N _th is satisfied, proceed to the next step.

Step6: Predict the estimated value. The formula is as follows:

------------- The predicted value of the ith particle at time k.

-------------The weights after normalization.

x _k ------------- Predicted traffic flow at time k.

2. Traffic flow sample determination:

(1) The experimental data selects the traffic flow data collected by an entrance direction detector at an intersection in Changping District, Beijing, and the collection interval is 5 minutes.

(2) The data set includes 6048 groups of traffic data for 24 hours a day on 21 days (Monday to Friday) in July 2017. Among them, 20 days (3-7, 10-14, 17-21, 24-28) were selected. Day) 5760 groups of traffic data are used as training samples to determine the traffic state set, and predict the flow throughout the day on the 21st day (31st).

(3) 288 groups of data on the 21st day were used as test samples, and the 24-hour and morning peak (7:00-8:55) data were processed, and the error analysis was carried out with the prediction results respectively.

(4) During the experiment, it is determined that the prediction result with the interval I=5 is better.

3. Analysis of traffic flow prediction results:

(1) Compare the prediction results of Markov particle filtering and traditional Markov prediction with the traffic flow test samples obtained above on the 21st day, and analyze the traffic flow throughout the day and the morning peak flow. As shown in Figure 1 and Figure 2.

(2) It can be seen from Figure 1 that the Markov particle filter prediction method can well fit the actual situation and has the same change trend as the actual traffic flow. The traditional Markov prediction model describes the fluctuation trend of this time period well, but the prediction result is rough, and the error fluctuation is larger than that of the Markov particle filter traffic flow prediction model.

4. Traffic flow prediction error analysis:

(1) In order to further illustrate the accuracy and stability of the prediction results of the Markov particle filter model, the prediction results of the Markov particle filter model are compared with those of the traditional Markov prediction model, and the absolute error ER, relative error RER, mean square The root error RMSE and the average error ε are used as evaluation indicators, and the formulas are as follows:

xx------------The original value of the traffic flow.

------------- Traffic flow forecast value.

------------- Raw traffic flow average.

n-------------number of samples

The comparison and analysis are as shown in Figure 3, Figure 4, Figure 5, and Figure 6.

As can be seen from Figure 3 and Figure 4, with 1h and 5min as the prediction interval, the absolute error fluctuation ranges of the Markov particle filter prediction results are within 0 to 60 vehicles and 2 to 10 vehicles respectively, while the traditional Markov prediction results The absolute error fluctuation range is within 0 to 110 vehicles and 0 to 23 vehicles. Therefore, the absolute error of the Markov particle filter prediction model at different prediction intervals is much smaller than that of the traditional Markov prediction model.

It can be seen from Figure 5 and Figure 6 that with 1h and 5min as the prediction interval, the relative error of the Markov particle filter prediction result is basically controlled below 0.28, 0.15, while the absolute error of the traditional Markov prediction result is 0.65, 0.4 Below, the Markov particle filter traffic flow prediction model has small relative error and smooth fluctuation.

The root mean square error and error analysis of the two algorithms are shown in Table 1 and Table 2.

Table 1 The root mean square error of the two algorithms

Table 2 Error analysis of two algorithms

The root mean square error is very sensitive to the extremely large or extremely small error value of the predicted data, and can well reflect the precision of the method's prediction results. The results in Table 1 show that the root mean square errors of the Markov particle filter prediction model for the whole day and morning peak are 32.94 and 5.24, respectively, which are smaller than the root mean square errors of the traditional Markov prediction method.

The results in Table 2 show that with 1h and 5min as the prediction intervals, the average errors of the Markov particle filter prediction model are 6.04% and 6.41%, respectively, which are smaller than the traditional Markov prediction methods and the average errors of different time intervals are different. smaller.

The prediction results are compared with the traditional Markov model for prediction accuracy and error. The results show that the proposed traffic flow prediction model based on Markov particle filter has strong applicability and high prediction accuracy.

The invention is not limited to the above-mentioned best embodiment, and anyone can draw other various forms of products under the inspiration of the present invention, but no matter if any changes are made in its shape or structure, all products with the same or similar characteristics as the present application can be obtained. The technical solutions of the invention all fall within the protection scope of the present invention.

Claims (2)

1. a kind of Markov particle filter method of forecasting traffic flow, it is characterised in that:

Before prediction, sample data need to be pre-processed, the sky data as caused by detector failures, using adjacent time interval number It is repaired according to the method for averaging；

Correction formula is as follows:

x_k--- --- --- -- is the k moment magnitude of traffic flow；

x_k-1--- --- ----is the k-1 moment magnitude of traffic flow；

x_k+1--- --- ----is the k+1 moment magnitude of traffic flow；

Since Markov model is the prediction to state transfer, so needing the magnitude of traffic flow to be belonged to different states；Its Process is as follows:

Traffic flow modes are indicated with state set S, historical sample data constitutes traffic flow modes collection S={ s₁, s₂..., s_n}；

Traffic flow status is determined using threshold method；Introduce parameter μ₁、μ₂；

μ₁=x_k-1(min): I:x_k-1(max) (2)

μ₂={ θ₁, θ₂..., θ_n} (3)

μ₁--- --- --- -- indicates that traffic flow is divided into multiple states using I as interval；Take I=5；

μ₂--- --- --- -- is for saving threshold value；

x_k-1(min)--- --- indicates k-1 moment magnitude of traffic flow minimum value；

x_k-1(max)--- --- indicates k-1 moment magnitude of traffic flow maximum value；

I----------- indicates that the magnitude of traffic flow divides interval；

θ_l--- --- --- -- is threshold value, represents state boundaries value, there are two boundary value, i=1,2 ..., n for a state；

s_i--- --- --- -- indicates that section is (θ_i-1, θ_i] state, i=1,2 ..., n；

State set determines；By volume of traffic x_k-1Descending sequence calculates state numberWherein, if h It is not integer, then adds state s_h+1As the last one state；That is s_h+1=x_k-1(max)；State set is S={ s₁, s₂..., s_h, s_h+1}；

H---------- indicates state number；

s_h+1--- --- -- indicates the h+1 state；

To construct Markov forecasting traffic flow model, it is first determined then the affiliated traffic behavior of the sample magnitude of traffic flow finds out shape State transfer matrix predicts future transportation state according to state-transition matrix；Detailed process is as follows:

The determination of state transition probability；State-transition matrix shows the markov property of Markov, i.e., the state at k moment only with The traffic behavior at k-1 moment is related；State s of the traffic flow modes from the current k-1 moment_i(k-1) it is transferred to the subsequent time k moment State s_j(k) be it is uncertain, possibility is expressed as its state transition probability with probability:

m_i--- --- --- --- indicates state s_iIn the number that different periods occur；

m_ij--- --- --- -- indicates by state s_iIt is transferred to state s_jNumber；

p(s_i(k-1)→s_j(k))、p(s_j|s_i)、p_ij(k) --- --- --- -- indicates by state s_iIt is transferred to state s_jProbability；

The determination of state-transition matrix；According to determining state transition probability p_ij(k), state-transition matrix, following institute are then constituted Show:

--- --- --- -- indicates state-transition matrix to P (k)；

Meet

p_j(k) --- --- --- -- indicates that the k moment is in j shape probability of state；

Establish Markov particle filter prediction model；Method is as follows:

Establish state equation；

Establish observational equation；

u₂(k-1) --- --- the state boundaries value at --- ----k-1 moment；

--- --- predicted value at --- ----k moment, i=1,2 ..., n；

--- --- observation at --- ----k moment, i=1,2 ..., n；

--- --- --- ----observation noise；

H-------------- observes value coefficient, if it is unit matrix E；

Particle filter, dynamic space model are as follows:

Determine state equation and observational equation

x_k=f (x_k-1)+u_k-1 (9)

y_k=h (x_k)+v_k (10)

x_k--- --- the predicted value at --- ----k moment；

y_k--- --- the observation at --- ----k moment；

u_k-1--- --- --- -- process noise；

v_k-1--- --- --- -- observation noise；

f(x_k-1) --- --- -- is the system state equation at k-1 moment；

h(x_k) --- --- ----is the systematic observation equation at k moment；

Prediction process:

If z_k={ y_1:i| i=1,2 ..., k } be initial time to k moment in all observation value sets；

p(x_k|z_k-1)=∫ p (x_k|x_k-1)p(x_k-1|z_k-1)dx_k-1 (11)

p(x_k|x_k-1) --- --- the state transition probability density of --- --- state equation is obtained by state equation (10)；

p(y_k|x_k) --- --- the observation probability density of --- ----observational equation；

p(x_k-1|z_k-1) --- --- --- -- is Posterior probability distribution, is obtained by sample data；

p(x_k|z_k-1) --- --- --- --- is prior probability, according to state transition probability density p (x_k|x_k-1) gained；

State renewal process:

p(y_k|z_k-1)=∫ p (y_k|x_k)p(x_k|z_k-1)dx_k (13)

Formula (12) and formula (13) generate one group of random sample particle collection, using particle collection to Posterior probability distribution function p (x_k| z_k) make approximation processing, to obtain the predicted value at k moment, particle on the basis of observationIndicate i-th of possible friendship Through-current capacity,According toAnd state equation obtains；Weight, i.e. importance corresponding to the magnitude of traffic flow predicted for i-th Weight,It needs to update in each iteration and makees normalized；It indicates are as follows:

δ-function, that is, Dirac delta function is meant that the function is equal to zero in the point value other than zero, and it is entire Integral in domain is equal to 1；

x_0:k--- --- --- --- is 0 state set for arriving the k moment；

--- --- --- ----indicates direct proportion function to ∝；

--- --- --- ----is the corresponding normalization weight of i-th of particle of k moment；

--- --- --- ----is the corresponding weight of i-th of particle of k moment, and is met

2. a kind of Markov particle filter method of forecasting traffic flow, main process are as follows:

Step1: it takes historical traffic flows as sample data by time interval of 5min, traffic flow is carried out according to sample data The division of amount state determines traffic flow modes collection S={ s₁, s₂..., s_n}。

Step2: parameter needed for determining, population n, h are state set number.

Step3: traffic flow forecasting is carried out according to Markov prediction model, calculates n Fe coatingsWithIf just Beginning particle weight

--- --- the predicted value of i-th of particle of --- ----k moment.

--- --- the observation of i-th of particle of --- ----k moment.

Step4: more new particle weight.According to formulaCalculate weight corresponding to each particle

--- --- --- ----k moment predicts i-th of particleWhen, obtain observation y_kProbability.Pass through formula (16) weight normalization obtains

Step5: judgement sample gravity treatment sample process.Judge whether particle sample carries out gravity treatment sample process using similar efficiencies method. Calculate effectively sampling scale N_eff,

N_th--- --- --- ----is thresholding, threshold sets N_th=2n/3, n are the number of particle.

N_eff--- --- --- --- is scale of effectively sampling.

When effectively sampling scale meets N less than the thresholding of setting_eff≤N_thWhen, gravity treatment is carried out according to random gravity treatment quadrat method Sample.Traffic flow is predicted again using new samples particle.

When effectively sampling scale meets N greater than the thresholding of setting_eff> N_thWhen, it carries out in next step.

Wherein, resampling process is specific as follows:

Generate n random number { d equally distributed on [0,1]_l, l=1,2 ..., n }, satisfaction is found with formula by searching algorithm The integer m of sub (17)；

Record sampleAnd as new sample particles；Finally, section [0,1] is pressedPoint At n minizone, as random number d_lFall in n-th of section λ_n-1, λ_nWhen, replicate corresponding sample

Step6: predictive estimation value.Formula is as follows:

--- --- the predicted value of i-th of particle of --- ----k moment.

--- --- the weight after --- ----normalization.

--- --- the predicting traffic flow amount at --- ----k moment.