CN103413443B - Short-term traffic flow forecasting method based on hidden Markov model - Google Patents

Abstract

The invention relates to the field of intelligent traffic systems, in particular to predicting the short-term traffic flow state by using the parameter value sequence of road sections. A short-term traffic flow state prediction method based on the hidden Markov model, including the following steps: processing and counting the collected data, by setting the prediction window, averaging the values measured at the start time of the prediction window and the parameters in the prediction window The value and sequence contrast are discretized to form the hidden state and observation state set of the hidden Markov model, and then the model parameters are learned by using the Baum-Welch algorithm combined with the training data. Finally, for a certain prediction window, on the basis of the known observation state sequence, use the Viterbi algorithm to obtain the optimal hidden state sequence, then the last state of the optimal hidden state sequence is the predicted state. The method of the invention can predict the future short-term traffic state, and is an effective short-term traffic state prediction method.

Description

Short-term Traffic Flow State Prediction Method Based on Hidden Markov Model

technical field

The invention relates to the field of intelligent traffic systems, in particular to predicting short-term traffic flow states by using traffic flow parameter value sequences of road sections, and in particular to a short-term traffic flow state prediction method based on a hidden Markov model.

Background technique

With the continuous development and deepening of the country's urbanization level and the continuous improvement of people's living standards, cars have entered everyone's life and have a profound impact on everyone's work, life and study. Accompanied by the lagging of transportation infrastructure and the inefficiency of transportation service level, what is more serious is the resulting traffic congestion, environmental pollution and energy waste, which have caused great economic losses. Therefore, the Intelligent Transportation System (Intelligent Transportation System, ITS) came into being, based on the existing transportation infrastructure and vehicles, it effectively integrates advanced information technology, communication technology, sensor technology, control technology and computer technology. It is integrated and applied to the entire transportation management system, thus establishing a large-scale, all-round, real-time, accurate and efficient comprehensive transportation and management system. ITS is the focus and frontier of the world's transportation development and an important symbol of the modern transportation industry. And with the continuous deepening of ITS research, it has become an important part of the national development strategy.

Moreover, as people's requirements for traffic information increase, they often hope to obtain future traffic status information before travel, so as to choose a suitable travel mode and an optimal travel route. Short-term traffic flow state prediction is to predict the traffic state of a road section in a short period of time in the future. Short-term traffic flow state prediction is different from long-term traffic prediction. The main service object is traffic drivers, and it is completed in the advanced traffic information system (ATIS). The forecast duration of the latter is macro-traffic forecasts such as days, months, and years. The main service targets are traffic management departments, so that they can make infrastructure construction, bus route setting, development planning, etc., mainly in advanced traffic management. system (ATMS).

Real-time and accurate short-term traffic flow prediction is the key to intelligent traffic control and guidance. Short-term traffic state prediction is helpful for travelers to choose the appropriate travel mode and plan a reasonable travel route, thereby shortening travel time, reducing pollution, and facilitating traffic flow. The purpose of improving transportation and improving the level of municipal services has become a hot topic in the field of intelligent transportation research. And scholars at home and abroad have proposed a series of prediction models and methods for the prediction of traffic conditions.

Short-term traffic flow forecasting models and methods are mainly divided into three categories at present. One is a mathematical model based on traditional mathematical methods such as mathematical statistics and calculus, such as: History Average, linear regression model, time Sequence method (Time-seriesModel), auto-regressive integrated moving average algorithm (ARIMA, Auto-Regression Integrated Moving Average), Kalman filtering method (Kalman filtering), Markov prediction.

The other is the prediction model based on modern scientific methods such as neural network and fuzzy control. Its characteristic is the fitting prediction of traffic flow, but the parameter transplantation is poor.

The third category is the composite prediction method that combines the advantages and disadvantages of different methods, which has gradually become a research hotspot in recent years. For example, forecasting models based on wavelet decomposition theory and Kalman filter algorithm, forecasting methods combining time series and wavelet theory, etc.

Hidden Markov model is a probability model based on parameter representation to describe random process, which includes two parts of Markov chain and random process. The Markov chain describes the transition of the state, which is described by the transition probability; the general stochastic process describes the relationship between the state and the observation sequence, and is described by the probability of occurrence. The Hidden Markov Model can be represented by a quintuple, that is, λ=(N,M,Π,A,B), and the parameters are described as follows:

(1) N: The number of hidden states in the model. Let the state set be S={s ₁ ,s ₂ ,…,s _N }, when the Markov chain state is X _t at time t, then X _t ∈ S.

(2) M: The number of observation states in the model. Let the observation set be O={o ₁ ,o ₂ ,…,o _M }, when the observation state at time t is O _t , then O _t ∈ O.

(3) Π: the initial probability distribution of each state in the hidden Markov model; recorded as Π={π _i }, (1≤i≤N) here, π _i =P(X ₁ =s _i ), ( 1≤i≤N); and 0≤π _i ≤1, π _i represents the probability that the initial state s _i is selected at the beginning.

(4) A: state transition probability matrix of hidden Markov model, A=(a _ij ) _N×N , (1≤i,j≤N), where a _ij =P{X _t+1 =s _j |X _t = s _i }, (s _i , s _j ∈ S), a _ij represents the probability of transition from state s _i to s _j .

(5) B: The occurrence matrix in the hidden Markov model, which describes the relationship between the hidden state and the corresponding observed state; B=(b _ij ) _N×M , where b _ij =P{O _t =o _j |X _t = s _i }, (1≤i≤N, 1≤j≤M).

Contents of the invention

The purpose of the present invention is to provide a short-term method for predicting the traffic flow state of a road section, which solves the problem of predicting the short-term traffic flow state, and provides a short-term traffic flow state prediction method based on a hidden Markov model.

The present invention is realized by adopting the following technical solutions:

A short-term traffic flow state prediction method based on hidden Markov model, comprising the following steps:

(1) Determine the hidden state set and observed state set of the hidden Markov model, as follows:

1. Collect a certain traffic flow state parameter through a section cross-section with the acquisition period δ, and obtain a data sequence corresponding to the parameter in the detected period with the acquisition period δ as an interval;

Ⅱ. Set a fixed time period as the prediction window Φ, that is, the short-term prediction duration. The prediction window Φ is an integer multiple of the acquisition period δ, so the prediction window Φ contains Φ/δ parameters of a certain traffic flow state. data sequence;

Set the transfer window Δ, which means that the prediction window Φ slides backwards on the time axis in units of the transfer window Δ, and the transfer window Δ is an integer multiple of the acquisition period δ, and the range is δ≤Δ≤Φ; determined accordingly The number of prediction windows Φ in the detected period;

Using the gray-scale joint co-occurrence matrix C and the contrast, determine the contrast _CON of the data sequence in each prediction window Φ; and the intensity value of its adjacent data points is the frequency of data combinations such as j, that is but $\mathrm{CON}={\mathrm{\Σ}}_{i,j}|j-i|(j-i)c_{\mathrm{ij}};$

Each prediction window Φ corresponds to a parameter average

The initial moment parameter value θ _t in each prediction window Φ is used as the observation value, then all the observation values constitute the observation value sequence O={O ₁ ,O ₂ ,…,O _T }.

Ⅲ. Count the change range of all observed values. According to the statistical results, discretize the change range of observed values into M intervals, and at the same time obtain the grades corresponding to the intervals, that is, discretize all observed values into M grades, and set the grades as is the observation state o _i (i=1,2,...,M), so as to obtain the observation state set O={o ₁ ,o ₂ ,...,o _M };

Similarly, the average value of parameters within the statistical prediction window Φ and the variation range of the contrast CON, according to the statistical results, the parameter average and the contrast CON are discretized into m and n intervals respectively, and at the same time, the grade corresponding to the interval is obtained, that is, the parameter average value Discretize into m levels, discretize the contrast CON into n levels, and then use the average value of the parameters The two-dimensional full factors of all levels of contrast CON describe the hidden states jointly, which is m×n, so as to obtain the hidden state set S={s ₁ ,s ₂ ,…,s _N }, N=m×n.

(2) After determining the hidden state set and observed state set of the hidden Markov model, train the hidden Markov model to obtain a hidden Markov model suitable for traffic flow $\stackrel{\‾}{\mathrm{\λ}}=(\stackrel{\‾}{\mathrm{\Π}},\stackrel{\‾}{A},\stackrel{\‾}{B}),$ details as follows:

First, use random assignment to initialize the parameters of the hidden Markov model to obtain the hidden Markov initialization model λ _initial = (Π, A, B), according to λ _initial = (Π, A, B) and the known sequence of observations O={O ₁ ,O ₂ ,…,O _T }, using the hidden Markov revaluation formula to iteratively obtain a new hidden Markov model can prove Continue to iterate on the revaluation process until Convergence, at this time Hidden Markov model suitable for traffic flow $\stackrel{\‾}{\mathrm{\λ}}=(\stackrel{\‾}{\mathrm{\Π}},\stackrel{\‾}{A},\stackrel{\‾}{B}).$

(3), given the hidden Markov model suitable for traffic flow state On the basis of the observed value sequence and the Viterbi algorithm, the optimal hidden state sequence corresponding to the observed value sequence is obtained, then the last state in the optimal hidden state sequence is the predicted traffic flow state after the detected period; and Carry out short-term traffic flow state prediction sequentially. Because the observed value corresponds to the measured value at the beginning of each prediction window, the hidden state corresponds to the traffic flow state in the prediction window, and the length of the prediction time is the length of the prediction window.

When working, the present invention is aimed at predicting the traffic state in the short time (5min or 10min) of the road section in the future, based on the traffic flow parameter data sequence collected from the road section data station, and by analyzing it, further understanding of the traffic flow in the road section. From the change characteristics on the time axis, it can be known that traffic flow is a time-varying, non-linear random process. However, the traditional forecasting models usually predict the traffic state quantitatively and deterministically, and only study the static information of traffic flow, ignoring the changing trend of traffic flow. Based on this, the hidden Markov (HMM) statistical model is used to predict the traffic state.

Firstly, the hidden Markov model parameters are constructed, and the data sequence in the prediction window is statistically analyzed to obtain the average value and the contrast of the data sequence in the prediction window, so as to obtain the hidden state sequence of the model. And set the value interval corresponding to the measured value at the beginning of the forecast window as the observation state (value) sequence. Thus, the hidden state set and the observed state set are constructed.

Secondly, the EM algorithm in HMM is used to train the parameters of the model with the collected training data, and the model parameters are obtained, including the state transition matrix, occurrence matrix, and initial state probability distribution, and the parameters are analyzed in combination with the characteristics of traffic flow.

Then, on the basis of the obtained model, the short-term traffic state is predicted by using a new hidden Markov model.

The present invention processes and counts the collected data, and discretizes the measured value at the start time of the prediction window and the average value of parameters and sequence contrast in the prediction window by setting the prediction window to form the hidden state and observation of the hidden Markov model. State collection, and then use the Baum-Welch algorithm combined with training data to learn model parameters. Finally, for a certain prediction window, on the basis of the known observation state sequence, use the Viterbi algorithm to obtain the optimal hidden state sequence, then the last state of the optimal hidden state sequence is the predicted state.

The invention has a reasonable design, is used for short-term traffic state prediction on urban expressways in the future, helps travelers to choose a reasonable travel mode or an optimal route, and is an effective short-term traffic state prediction method.

Description of drawings

Figure 1 is a flow chart of short-term traffic state prediction.

Fig. 2 is a schematic diagram of prediction window Φ and transfer window Δ.

Fig. 3 is a schematic diagram of a gray-level joint co-occurrence matrix.

Figure 4 is a flow chart of Viterbi prediction.

Detailed ways

Specific embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

In this embodiment, the hidden Markov model determined based on the traffic flow state is called "traffic hidden Markov model", abbreviated as "THMM". Set the parameter acquisition period δ to 30s, then there are 2880 sets of data in 24 hours a day, and a total of 1001 sets of morning peak data sequences from 500 to 1500 per day are used as the data of this embodiment. In order to facilitate the construction of THMM, three time windows are defined: prediction window Φ, transfer window Δ, acquisition window (period) δ.

Definition 1: Prediction window Φ, the purpose is to predict the short-term traffic status in the future, and set the time length of 5 minutes as the prediction window, that is, the predicted future "short-term" is 5 minutes.

Definition 2: Transition window Δ, which refers to the time window from time t to t+(1*Δ), the traffic state has transitioned, for example, three transition windows are set, namely 30s/2min/5min.

Definition 3: Acquisition window δ: Since the data sequence takes 30s as the sampling interval, the system scrolls sequentially with 30s as a step, so 30s is set as the acquisition window δ, which is fixed in this embodiment.

To use Hidden Markov Model (HMM) to study traffic flow, it is first necessary to determine the hidden state and observed state of the model. For the prediction window Φ of 5 minutes, set the state corresponding to the measured value of the parameter at the beginning of the prediction window Φ as the observation state (observation value) of THMM; because the hidden state of the model should represent both static and dynamic information of traffic flow , so the hidden state is jointly determined by two factors, that is, using the parameter average value of the parameter sequence in the time window Combined expression with contrast CON. Figure 2 is a schematic diagram of the hidden state and observed values of the THMM model on the time axis.

Because the sampling interval is 30s, in this embodiment, a total of 1001 sets of data from 500 to 1500 in the morning peak period of the parameter value sequence are used for research. The length of the prediction window Φ is 5 minutes, which contains 10 data points of 30 seconds. Since 30 seconds is set as the transition window Δ, 992 prediction windows are covered in the morning peak hours, and there are overlaps between the windows. Among them, S _t (1≤t≤992) represents the hidden state of traffic flow in each 5min prediction window Φ. In order to use the model to predict the state in the prediction window, the observation state corresponding to the parameter value θ _t at the initial moment of each prediction window Φ is set as O _t , (1≤t≤992), and the observation state ( value) sequence O=(O ₁ ,O ₂ ,…,O ₉₉₂ ).

The following is a detailed description of a short-term traffic flow state prediction method based on the hidden Markov model, including the following steps:

(1) Determine the hidden state set and observed state set of the hidden Markov model, as follows:

I. Collect a certain traffic flow state parameter (such as any one of traffic flow speed, traffic volume, and occupancy rate) passing through a certain road section cross section with the collection period δ (30s), and obtain the parameters corresponding to the detected period of time. The data sequence within the interval of the acquisition period δ.

Ⅱ. Set a fixed period length as the prediction window Φ (5min), that is, the short-term prediction duration. The prediction window Φ is an integer multiple of the acquisition period δ, so the prediction window Φ contains Φ/δ (Φ/δ=10 ) A data sequence composed of a certain traffic flow state parameter value.

Set the transfer window Δ, which means that the prediction window Φ slides backwards on the time axis in units of the transfer window Δ, and the transfer window Δ is an integer multiple of the acquisition period δ, and the range is δ≤Δ≤Φ; determined accordingly The number of prediction windows Φ in the detected period (500min) is 992.

Each prediction window Φ corresponds to a parameter average .

The initial moment parameter value θ _t in each prediction window Φ is used as the observation value, then all the observation values constitute the observation value sequence O={O ₁ ,O ₂ ,…,O _T }.

Using the gray-scale joint co-occurrence matrix C, determine the contrast CON of the data sequence within each prediction window Φ. details as follows:

The average value of a certain traffic flow parameter in a certain period of time (the detected period is 500min) using the forecast window (first-order statistical variable) and the description parameter fluctuations on the time axis contrast ratio CON (second-order statistics) to describe the traffic state. Among them, the average value of the parameters can intuitively display the current or historical static information of the traffic flow, and the contrast ratio can describe the changing trend and fluctuation degree of the parameter sequence.

To analyze the change trend of traffic flow parameters on the time axis, from a statistical point of view, it is necessary to conduct second-order statistical analysis on the parameter sequence.

The present invention expands the definitions of gray level joint co-occurrence matrix (GLCM) and contrast (Contrast, CON), which are widely used in the field of image research. In image analysis, the gray level represents the brightness and intensity of pixels, and for the traffic flow parameter sequence, the traffic parameter value is equivalent to the gray value. The collection interval of the data set in this embodiment is 30s, and the data sequence composed of 10 parameter values within 5 minutes is analyzed to generate a gray-scale joint co-occurrence matrix, thereby obtaining the contrast CON. Given a set of data sequences, the element c _ij in the gray level joint co-occurrence matrix (GLCM) C represents the data whose intensity value (traffic flow parameter value) of the data point is i and the intensity value of its adjacent data point is j. How often the combination occurs. That is to say, the element c _ij represents the number of occurrences of the data combination with the strength value of the data point (traffic flow parameter value) i and its adjacent data point j in the sequence, and all The ratio of the total number of possible data combinations, as shown in formula (1). Here, the gray-level joint co-occurrence matrix C is a matrix of N _g ×N _g , where N _g represents the number of gray levels.

The contrast value that measures the intensity of a pixel point and its adjacent pixel points in the image, and the amount of local grayscale change in the image is called the contrast CON, and its expression is as follows:

$\mathrm{<span\; class="notranslate">\; CON</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; |</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

In the present invention, the above formula (2) is improved as follows:

$\mathrm{<span\; class="notranslate">\; CON</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; |</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; )</span>$

It can be seen from formula (3) that in the traffic sequence, the contrast CON represents the positive and negative changes of parameters over time, which can reflect the changing trend of traffic parameters. The magnitude of its absolute value |CON| indicates the intensity of the speed change trend.

Now take a set of data sequences as an example to visually illustrate the gray level joint co-occurrence matrix (GLCM) and contrast (Contrast, CON). Assuming that 10 data values in the 5min prediction window constitute a set of sequences: O=(10,10,7,10,8,9,10,10,8,8), the joint can be obtained according to formula (1) Co-occurrence matrix C, as shown in Figure 3. In the matrix C, the element c _10,10 =0.22, because the combination of (10,10) in the data sequence O appears twice, and the total number of combinations in the sequence is 9, so the ratio 2/9=0.22.

It can be seen from formula (3) that the contrast CON has positive and negative changes. In the traffic sequence, the contrast CON can represent the positive and negative changes of parameters over time. For example, when the speed has a rising trend, the contrast CON is positive, otherwise it is negative, and its absolute value |CON| represents the speed The severity of the changing trend. Then the contrast CON of the data sequence within the above 5min:

CON=0.11×(10-7) ² +0.11×(9-8) ² +0.11×(10-9) ²

-0.11×(10-7) ² -0.22×(10-8) ² =0.67.

Ⅲ. Count the change range of all observed values. According to the statistical results, discretize the change range of observed values into M intervals, and at the same time obtain the grades corresponding to the intervals, that is, discretize all observed values into M grades, and set the grades as To observe the state o _i (i=1,2,...,M), obtain the set of observed states O={o ₁ ,o ₂ ,...,o _M }.

In this embodiment, taking the parameter speed as an example, the speed change interval is about (0mph, 60mph), and the observed speed values are divided into 11 levels, as shown in Table 1.

Table 1 Discretization of speed observation state

Similarly, the average value of parameters within the statistical prediction window Φ and the variation range of the contrast CON, according to the statistical results, the parameter average and the contrast CON are discretized into m and n intervals respectively, and at the same time, the grade corresponding to the interval is obtained, that is, the parameter average value The discretization is m-level, and the contrast CON is discretized into n-level.

When constructing the hidden state of the THMM model, the average speed in the prediction window is discretized into 6 levels. Similar to the traditional method, different speed levels correspond to different parameter value intervals of traffic flow. As shown in table 2,

Table 2 Average speed discretization

From the average speed discretization table in the forecast window, it can be seen that different speed levels describe the static information of the traffic flow state, which can intuitively express the current traffic flow capacity.

In this embodiment, the variation range of the speed contrast CON is mainly (-70, 70). In order to facilitate the construction of the hidden state of the traffic hidden Markov model, similar to the discretization of the average speed in the prediction window, the contrast CON is discretized into 7 levels, and the 7 levels correspond to the contrast from negative to positive. range, as shown in Table 3.

Table 3 Velocity contrast discretization

When constructing a hidden Markov model of traffic flow, the average value of the sequence within the window will be predicted The discretization is divided into several levels representing different speed intervals and the discretization level of the parameter sequence contrast CON in the window is used as two factors of the hidden state respectively. Utilizing the contrast con with the data series mean The discretized two-dimensional full factor joint description model hidden state set S={s ₁ ,s ₂ ,…,s _N }. This joint representation of the hidden state overcomes the one-sided shortcoming of the traditional method which only describes the static information of the traffic state.

For example, for the parameter mean within the forecast window And the contrast CON is discretized into m levels and n levels respectively, then the hidden states of traffic flow that can be described are m×n. In this embodiment, "speed" is taken as an example, and the average speed and contrast in the prediction window are discretely divided into 6 levels and 7 levels, so there are 6×7=42 hidden states in the model, and the hidden state set is S={ s ₁ , s ₂ ,..., s ₄₂ }.

For simplicity, the hidden state is represented by Arabic numerals, as shown in Table 3. Therefore, the traffic conditions represented by the data sequence (including 10 detection values in 5 minutes) in the prediction window (5 minutes) can be set as a certain state.

Table 4 Hidden state composition table

Note: Some states in Table 4 are road conditions that are often encountered during driving. For example, state 17 is a situation where traffic flow speed is low due to congestion during peak hours. State 39 indicates that the road is clear and the road condition is good, and the influence between vehicles is small. However, some states are rare, such as state 1, the speed is already very low, and the possibility of further decline is very small. Nevertheless, it is still counted in order for the model to cover all states.

(2) After determining the hidden state set and observed state set of the hidden Markov model, train the hidden Markov model to obtain a hidden Markov model suitable for traffic flow $\stackrel{\&OverBar;}{\mathrm{\&lambda;}}=(\stackrel{\&OverBar;}{\mathrm{\&Pi;}},\stackrel{\&OverBar;}{A},\stackrel{\&OverBar;}{B}),$ details as follows:

First, use random assignment to initialize the hidden Markov model parameters, and obtain the hidden Markov initialization model λ _initial = (Π, A, B), according to λ _initial = (Π, A, B) and known observation values Sequence O={O ₁ ,O ₂ ,…,O _T }, use the hidden Markov revaluation formula to iteratively obtain a new hidden Markov model can prove Continue to iterate on the revaluation process until Convergence, at this time Hidden Markov model suitable for traffic flow $\stackrel{\&OverBar;}{\mathrm{\&lambda;}}=(\stackrel{\&OverBar;}{\mathrm{\&Pi;}},\stackrel{\&OverBar;}{A},\stackrel{\&OverBar;}{B}).$

(3) On the basis of a given hidden Markov model suitable for AC flow and an observation sequence, the Viterbi algorithm is used to obtain the optimal hidden state sequence corresponding to the observation sequence, then the last hidden state sequence in the hidden state sequence The state is the predicted traffic flow state after the detected period; and the short-term traffic flow state prediction is carried out sequentially. Because the observed value corresponds to the measured value at the beginning of each prediction window, the hidden state corresponds to the traffic flow state in the prediction window, and the length of the prediction time is the length of the prediction window.

First, given the hidden Markov model And on the basis of the observation sequence O=(O ₁ ,O ₂ ,…,O _t ), use the Viterbi algorithm to obtain the optimal hidden state sequence S=(S ₁ ,S ₂ ,…,S _t ) of the observation sequence .

Second, using the Viterbi variable δ _t (i) and the memory variable The hidden state sequence S corresponding to the O-optimum is obtained through Viterbi algorithm iteration.

Because the measured value at the beginning of the prediction window corresponds to the observation state O _t , and the last hidden state S _t in the corresponding optimal hidden state sequence is the description of the traffic state in the prediction window, so the optimal The state S _t at the last moment in the matching state sequence S is the predicted state, and the short-term traffic flow state prediction is carried out sequentially.

Claims (5)

1., based on a short-term traffic flow trend prediction method for Hidden Markov Model (HMM), it is characterized in that: comprise the steps:

(1), hidden state set and the observation state set of Hidden Markov Model (HMM) is determined, specific as follows:

I, with collection period δ, a certain traffic flow modes parameter by certain section xsect to be gathered, obtain corresponding to this parameter detecting the data sequence being interval with collection period δ in the period;

II, set fixing Period Length as prediction window Φ, i.e. short-term prediction duration, described prediction window Φ is the integral multiple of collection period δ, therefore contains the data sequence that Φ/δ a certain traffic flow modes parameter value forms in prediction window Φ;

Setting transition window Δ, represent that prediction window Φ slides backward transfer successively on a timeline in units of transition window Δ, described transition window Δ is the integral multiple of collection period δ, and scope is δ≤Δ≤Φ; Determine in the quantity detecting prediction window Φ in the period accordingly;

Utilize gray scale united symbiosis Matrix C, determine the contrast C ON of data sequence in each prediction window Φ; Element c in gray scale united symbiosis Matrix C _ijrepresent the intensity level of data point to be the intensity level of i and adjacent data point thereof be the frequency that the such data assemblies of j occurs, namely then CON=Σ _i,j| j-i| (j-i) c _ij;

Each prediction window Φ is all to there being a mean parameter

Initial time parameter value θ in each prediction window Φ _tas observed value, then all observed values form observed value sequence O={O ₁, O ₂..., O _t;

III, add up the variation range of all observed values, according to statistics, the variation range of observed value is carried out discrete turn to M interval, obtain corresponding to interval grade, turn to M level by all observed values are discrete, setting grade is observation state o simultaneously _i(i=1,2 ..., M), obtain observation state set O={o ₁, o ₂..., o _m;

In like manner, the mean parameter in statistical forecast window Φ with the variation range of contrast C ON, according to statistics, by mean parameter with contrast C ON carry out respectively discrete turn to m and n interval, obtain the grade corresponding to interval, by mean parameter simultaneously the discrete m of turning to level, contrast C ON are discrete turns to n level, then utilize mean parameter combining the hidden state of description with the two-dimentional total divisor of the grade of contrast C ON is exactly m × n, obtains hidden state set S={s ₁, s ₂..., s _n, N=m × n;

(2), after the hidden state set determining Hidden Markov Model (HMM) and observation state set, utilize Baum-Welch algorithm to train Hidden Markov Model (HMM), obtain the Hidden Markov Model (HMM) being suitable for traffic flow specific as follows:

First utilize random assignment to carry out initialization to Hidden Markov Model (HMM) parameter, obtain Hidden Markov initialization model λ _initial=(Π, A, B), according to λ _initial=(Π, A, B) and known observed value sequence O={O ₁, O ₂..., O _t, utilize Hidden Markov revaluation formula iteration to obtain new Hidden Markov Model (HMM) can prove to revaluation process continue iteration until convergence, now be the required Hidden Markov Model (HMM) being suitable for traffic flow $\stackrel{\&OverBar;}{\mathrm{\&lambda;}}=(\stackrel{\&OverBar;}{\mathrm{\&Pi;}},\stackrel{\&OverBar;}{A},\stackrel{\&OverBar;}{B});$

(3), on the basis of the given Hidden Markov Model (HMM) being applicable to traffic flow and observed value sequence, the hidden status switch of optimum utilizing Viterbi algorithm to try to achieve to answer with observed value sequence pair, the traffic flow modes predicted after final state then in hidden status switch is and detects the period, and short-term traffic flow status predication is carried out in passing successively.

2. the short-term traffic flow trend prediction method based on Hidden Markov Model (HMM) according to claim 1, is characterized in that: the traffic flow modes parameter of described collection is traffic flow speed or vehicle flowrate or occupation rate.

3. the short-term traffic flow trend prediction method based on Hidden Markov Model (HMM) according to claim 1 and 2, is characterized in that: the duration detecting the period in described step I is 500min.

4. the short-term traffic flow trend prediction method based on Hidden Markov Model (HMM) according to claim 3, is characterized in that: described collection period δ is 30s.

5. the short-term traffic flow trend prediction method based on Hidden Markov Model (HMM) according to claim 4, is characterized in that: the duration of described prediction window Φ is 5min or 10min.