CN103413443B - Short-term traffic flow forecasting method based on hidden Markov model - Google Patents
Short-term traffic flow forecasting method based on hidden Markov model Download PDFInfo
- Publication number
- CN103413443B CN103413443B CN201310276581.7A CN201310276581A CN103413443B CN 103413443 B CN103413443 B CN 103413443B CN 201310276581 A CN201310276581 A CN 201310276581A CN 103413443 B CN103413443 B CN 103413443B
- Authority
- CN
- China
- Prior art keywords
- traffic flow
- hidden markov
- markov model
- hmm
- hidden
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000013277 forecasting method Methods 0.000 title abstract 3
- 238000000034 method Methods 0.000 claims abstract description 32
- 239000011159 matrix material Substances 0.000 claims description 18
- 230000007704 transition Effects 0.000 claims description 16
- 230000031068 symbiosis, encompassing mutualism through parasitism Effects 0.000 claims description 12
- 238000012546 transfer Methods 0.000 claims description 6
- 230000000712 assembly Effects 0.000 claims description 4
- 238000000429 assembly Methods 0.000 claims description 4
- 238000012549 training Methods 0.000 abstract description 3
- 238000010586 diagram Methods 0.000 description 5
- 230000003068 static effect Effects 0.000 description 5
- 238000011161 development Methods 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 4
- 238000004458 analytical method Methods 0.000 description 3
- 238000001914 filtration Methods 0.000 description 3
- 238000011160 research Methods 0.000 description 3
- 238000005309 stochastic process Methods 0.000 description 3
- 238000012417 linear regression Methods 0.000 description 2
- 238000007726 management method Methods 0.000 description 2
- 238000005070 sampling Methods 0.000 description 2
- PEDCQBHIVMGVHV-UHFFFAOYSA-N Glycerine Chemical compound OCC(O)CO PEDCQBHIVMGVHV-UHFFFAOYSA-N 0.000 description 1
- 238000013528 artificial neural network Methods 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 150000001875 compounds Chemical class 0.000 description 1
- 238000000354 decomposition reaction Methods 0.000 description 1
- 230000007423 decrease Effects 0.000 description 1
- 230000003247 decreasing effect Effects 0.000 description 1
- 230000003111 delayed effect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000003912 environmental pollution Methods 0.000 description 1
- 230000003203 everyday effect Effects 0.000 description 1
- 230000006698 induction Effects 0.000 description 1
- 238000009440 infrastructure construction Methods 0.000 description 1
- 230000002045 lasting effect Effects 0.000 description 1
- 238000013178 mathematical model Methods 0.000 description 1
- YHXISWVBGDMDLQ-UHFFFAOYSA-N moclobemide Chemical compound C1=CC(Cl)=CC=C1C(=O)NCCN1CCOCC1 YHXISWVBGDMDLQ-UHFFFAOYSA-N 0.000 description 1
- 230000021715 photosynthesis, light harvesting Effects 0.000 description 1
- 238000004064 recycling Methods 0.000 description 1
- 230000000630 rising effect Effects 0.000 description 1
- 238000004904 shortening Methods 0.000 description 1
- 238000013179 statistical model Methods 0.000 description 1
Landscapes
- Traffic Control Systems (AREA)
Abstract
The invention relates to the field of the intelligent transportation system, and especially relates to short-term traffic flow forecasting with use of a parameter value sequence of a road segment. A short-term traffic flow forecasting method based on a hidden Markov model comprises the following steps: collected data are processed and counted; a prediction window is set; a starting time measured value of the prediction window, and an average parameter value and a sequence contrast ratio in the prediction window are discretized, so as to form a hidden state and an observation state set of the hidden Markov model; and a Baum Welch algorithm combined with training data are used for learning the model parameter. Finally, for a certain prediction window, a Viterbi algorithm is used to obtain an optimal hidden state sequence based on a known observation state sequence, and a last state of the optimal hidden state sequence is a prediction state. The short-term traffic flow forecasting method based on the hidden Markov model can be used to predict the short-term traffic state in the future, and is an effective method of prediction of the short-term traffic state.
Description
Technical field
The present invention relates to intelligent transport system field, be specifically related to utilize the traffic flow parameter value sequence in section to predict short-term traffic flow state, particularly a kind of short-term traffic flow trend prediction method based on Hidden Markov Model (HMM).
Background technology
Along with the development of the national level of urbanization is deepened, and the lasting raising of living standards of the people, automobile has entered in everyone life already, and produces deep effect to everyone work, life, study.Adjoint is with it the poor efficiency of the delayed of traffic infrastructure and level of service, and the traffic congestion more seriously therefore caused, environmental pollution, energy dissipation cause great economic loss.Therefore, intelligent transportation system (Intelligent Transportation System, ITS) arise at the historic moment, it is on the basis of existing traffic infrastructure and delivery vehicle, apply to whole traffic management system by effectively integrated to the infotech of advanced person, mechanics of communication, sensing technology, control technology and computer technology etc., thus the one set up on a large scale, comprehensive, in real time, multi-transportation and management system accurately and efficiently.ITS is the hot-point and frontier of TRANSPOWORLD transportation development, is the important symbol of Modern Traffic forwarding business.And along with deepening continuously of ITS research, become the important component part of national development strategy.
Further, the raising required for transport information along with people, often just wishes to obtain following traffic related information before travel, to select suitable trip mode, selects optimum traffic path.Short-term traffic flow status predication is exactly predict for the following traffic behavior interior in short-term in certain section, traffic forecast when short-term traffic flow status predication is different from long, the former prediction duration is generally the situation that 5min, 10min, 15min etc. are no more than 1h, main services, to liking traffic human pilot, completes in the traffic information system (ATIS) of advanced person.The prediction duration of the latter is then the traffic forecast of the macroscopic views such as sky, the moon, year, main services is to liking vehicle supervision department, so that it makes infrastructure construction, bus routes setting, development plan etc., it mainly completes in advanced traveler information systems (ATMS).
The prediction of short-term traffic flow is the key realizing intellectual traffic control and induction accurately in real time, short time traffic conditions prediction is conducive to the suitable trip mode of trip personnel selection, plan rational traffic path, and then reach the object shortening running time, decreasing pollution, the municipal services level that relieves traffic congestion, improves, therefore become the hot subject of intelligent transportation research field.And Chinese scholars has proposed a series of forecast model and method, for the prediction to traffic behavior.
Short-term traffic flow forecasting model and method are mainly divided three classes at present, one class is the mathematical model developed based on the traditional mathematics such as mathematical statistics and infinitesimal analysis method, such as: the history method of average (History Average), linear regression model (LRM), Time Series Method (Time-series Model), the comprehensive moving average algorithm of autoregression (ARIMA, Auto-Regression Integrated Moving Average), Kalman filtering method (Kalman filtering), Markov prediction.
Another kind of is utilize the forecast model proposed based on the modern scientific method such as neural network, fuzzy control, is characterized in predicting the matching of traffic flow, but parameter transplantability is poor.
3rd class is the compound Forecasting Methodology of comprehensive distinct methods relative merits, becomes the focus of Recent study gradually.Such as based on the Forecasting Methodology etc. that the forecast model of wavelet decomposition theory and Kalman filtering algorithm, time series combine with wavelet theory.
Hidden Markov Model (HMM) is a kind of probability model of the description stochastic process based on Parametric Representation, wherein comprises Markov chain and stochastic process two parts.Markov chain describes the transfer of state, describes with transition probability; Relation between general random process prescription state and observation sequence, describes with probability of happening.Hidden Markov Model (HMM) can represent with five-tuple, i.e. λ=(N, M, Π, A, B), and parameter declaration is as follows:
(1) N: the number of hidden state in model, if state set is S={s
1, s
2..., s
n, when t Markov chain state is X
t, then X
t∈ S.
(2) M: the number of observer state in model, if observation set is O={o
1, o
2..., o
m, when t observation state is O
t, then O
t∈ O.
(3) Π: the initial probability distribution of each state in Hidden Markov Model (HMM); Be designated as Π={ π
i, (1≤i≤N) here, π
i=P (X
1=s
i), (1≤i≤N); And 0≤π
i≤ 1,
π
irepresent start time original state s
iselected probability.
(4) A: the state transition probability matrix of Hidden Markov Model (HMM), A=(a
ij)
n × N, (1≤i, j≤N), wherein, a
ij=P{X
t+1=s
j| X
t=s
i, (s
i, s
j∈ S), a
ijexpression state s
ito s
jthe probability of transfer.
(5) B: the generation matrix in Hidden Markov Model (HMM), description be the relation of hidden state and corresponding observation state; B=(b
ij)
n × M, wherein b
ij=P{O
t=o
j| X
t=s
i, (1≤i≤N, 1≤j≤M).
Summary of the invention
The object of the present invention is to provide the method for a certain road section traffic volume stream mode of a kind of short-term prediction, solve the problem of prediction short-term traffic flow state, provide a kind of short-term traffic flow trend prediction method based on Hidden Markov Model (HMM).
The present invention adopts following technical scheme to realize:
Based on a short-term traffic flow trend prediction method for Hidden Markov Model (HMM), 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 and contrast, determine the contrast C ON of data sequence in each prediction window Φ; As follows: the element c in gray scale united symbiosis Matrix C
ijrepresent that intensity level that the intensity level (traffic flow parameter value) of data point is i and adjacent data point thereof is the frequency that the such data assemblies of j occurs, namely
then
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
1, O
2..., 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), thus obtain observation state set O={o
1, o
2..., 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, recycling mean parameter
combining the hidden state of description with the gradational two-dimentional total divisor of contrast C ON is exactly m × n, thus obtains hidden state set S={s
1, s
2..., s
n, N=m × n.
(2), after the hidden state set determining Hidden Markov Model (HMM) and observation state set, Hidden Markov Model (HMM) is trained, 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
1, O
2..., 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
(3), in the given Hidden Markov Model (HMM) being suitable for traffic flow modes
with on the basis of observed value sequence, the hidden status switch of optimum utilizing Viterbi algorithm to try to achieve to answer with observed value sequence pair, then the final state in optimum hidden status switch is the traffic flow modes predicted after detecting the period; And short-term traffic flow status predication is carried out in passing successively.Because observed value is corresponding with the initial time measured value of each prediction window, then hidden state is corresponding with the traffic flow modes in prediction window, then predicted time length is exactly the length of prediction window.
During work, the present invention is to predict for the purpose of the traffic behavior in short-term in (5min or 10min) in section future, based on the traffic flow parameter data sequence gathered from section data station, by analyzing it, further understanding traffic flow Variation Features on a timeline, known, change, nonlinear stochastic process when traffic flow is a kind of.But Classical forecast model carries out quantitative deterministic prediction to traffic behavior often, only studies traffic flow static information, have ignored the variation tendency of traffic flow.Based on this, Hidden Markov (HMM) statistical model is utilized to predict traffic behavior.
First, Hidden Markov Model (HMM) parameter is constructed, statistical study is carried out to the data sequence in prediction window, obtain its mean value, and data sequence contrast in prediction window, thus obtain the hidden status switch of model.And interval corresponding to the measured value setting prediction window start time is as observation state (value) sequence.Thus constructed hidden state set and observation state set.
Secondly, utilize the EM algorithm in HMM, utilize the parameter of training data to model gathered to train, obtain model parameter, comprise state-transition matrix, matrix occurs, initial state probabilities distributes, and in conjunction with the feature of traffic flow, parameter is analyzed.
Then, on obtained model basis, utilize new Hidden Markov Model (HMM) to predict short time traffic conditions.
The present invention processes the data gathered and adds up, by setting prediction window, to prediction window initial time measured value and prediction window intrinsic parameter mean value and alignment's degree discretize, form hidden state and the observation state set of Hidden Markov Model (HMM), then utilize Baum-Welch algorithm combined training data to learn model parameter.Finally, for certain prediction window, on the basis of known observation state sequence, utilize Viterbi algorithm to try to achieve optimum hidden status switch, then the last state of optimum hidden status switch is predicted state.
The present invention is reasonable in design, for the following traffic status prediction interior in short-term of city expressway, contributes to the trip rational trip mode of personnel selection or optimal path, is a kind of effective short time traffic conditions Forecasting Methodology.
Accompanying drawing explanation
Fig. 1 is the prediction process flow diagram of short time traffic conditions.
Fig. 2 is prediction window Φ and transition window Δ schematic diagram.
Fig. 3 is gray scale united symbiosis matrix schematic diagram.
Fig. 4 is that Viterbi predicts process flow diagram.
Embodiment
Below in conjunction with accompanying drawing, specific embodiments of the invention are described in detail.
In the present embodiment, the Hidden Markov Model (HMM) determined based on traffic flow modes is called " traffic Hidden Markov Model (HMM) ", referred to as " THMM ".Setup parameter collection period δ is 30s, then in one day 24h containing 2880 groups of data, amount to the data of 1001 groups of morning peak data sequences as the present embodiment using every day from 500 to 1500.For the ease of the structure to THMM, define three time window: prediction window Φ, transition window Δ, acquisition window (cycle) δ.
Definition 1: prediction window Φ, object is the following traffic behavior in short-term of prediction, and the time span of setting 5min is as prediction window, and the future " in short-term " namely predicted is exactly 5min.
Definition 2: transition window Δ, refers to that traffic behavior there occurs transfer by the time window of moment t to t+ (1* Δ), such as, set 3 kinds of transition window, i.e. 30s/2min/5min.
Definition 3: acquisition window δ: because data sequence take 30s as sampling interval, therefore system is that 1 step is rolled successively with 30s, then setting 30s is acquisition window δ, is fixing in the present embodiment.
Utilize Hidden Markov Model (HMM) (HMM) to study traffic flow, first need to determine the hidden state of model and observation state.For the prediction window Φ of 5min, the state corresponding to parameter measured value of setting prediction window Φ start time is as the observation state (observed value) of THMM; Because the hidden state of model will represent Static and dynamic information two aspects of traffic flow simultaneously, so hidden state is determined by two agents, namely utilize the mean parameter of the argument sequence in time window
statement is combined with contrast C ON.Be illustrated in figure 2 the schematic diagram of THMM model hidden state and observed value on a timeline.
Because sampling interval is 30s, the 500-1500 getting the parameter value sequence morning peak period in the present embodiment amounts to 1001 groups of data and studies.Prediction window Φ length is 5min, and the data point wherein containing 10 30s, owing to setting 30 seconds as transition window Δ, therefore, covers 992 prediction window, there is lap between window in the morning peak period.Wherein, S
t(1≤t≤992) represent the hidden state of traffic flow in each 5min prediction window Φ.In order to utilize model to predict the state in prediction window, set the parameter value θ of the initial time of each prediction window Φ
tcorresponding observation state is O
t, (1≤t≤992), and constitute observation state (value) sequence O=(O
1, O
2..., O
992).
Below a kind of short-term traffic flow trend prediction method based on Hidden Markov Model (HMM) is described in detail, comprises the steps:
(1), hidden state set and the observation state set of Hidden Markov Model (HMM) is determined, specific as follows:
I, to gather by a certain traffic flow modes parameter of certain section xsect (in such as traffic flow speed, vehicle flowrate, occupation rate any one) with collection period δ (30s), obtain corresponding to this parameter detecting the data sequence being interval with collection period δ in the period.
II, the Period Length that setting is fixing is as prediction window Φ (5min), i.e. short-term prediction duration, described prediction window Φ is the integral multiple of collection period δ, the data sequence therefore containing the individual a certain traffic flow modes parameter value composition of Φ/δ (Φ/δ=10) 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 detecting the quantity 992 of prediction window Φ in the period (500min) accordingly.
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
1, O
2..., O
t.
Utilize gray scale united symbiosis Matrix C, determine the contrast C ON of data sequence in each prediction window Φ.Specific as follows:
Utilize the mean parameter of a certain traffic flow parameter of prediction window within certain period (having detected period 500min)
(first-order statistics variable) and characterising parameter fluctuate situation contrast C ON(second-order statistic on a timeline) combining of the two traffic behavior is described.Wherein, mean parameter can represent intuitively to the static information of the current of traffic flow or history, and contrast then can the variation tendency of characterising parameter sequence and degree of fluctuation.
To analyze traffic flow parameter variation tendency on a timeline, from the angle of statistics, just must carry out second-order statistics analysis to argument sequence.
The present invention extends the gray scale united symbiosis matrix (GLCM) of widespread use in picture research field and the definition of contrast (Contrast, CON).To in graphical analysis, the brightness of gray level expressing pixel and intensity, and for traffic flow parameter sequence, traffic parameter value is just equivalent to gray-scale value.The acquisition interval of the data acquisition in the present embodiment is 30s, analyzes the data sequence that the parameter value of 10 in 5min is formed, and then generates gray scale united symbiosis matrix, thus tries to achieve contrast C ON.Given one group of data sequence, the element c in gray scale united symbiosis matrix (GLCM) C
ijrepresent that intensity level that the intensity level (traffic flow parameter value) of data point is i and adjacent data point thereof is the frequency that the such data assemblies of j occurs.I.e. element c
ijrepresent the intensity level (traffic flow parameter value) of data point in sequence for the intensity level of i and adjacent data point thereof be the number of times that the combination of j composition data occurs, the ratio of the sum of all possible data assemblies in the data sequence formed with 10 parameter values, as the formula (1).Herein, gray scale united symbiosis Matrix C is a N
g× N
gmatrix, wherein N
grepresent the number of gray level.
Weigh the correlative value that pixel is adjacent the intensity of pixel in image, and the amount of image local grey scale change is called contrast C ON, its expression formula is as follows:
In the present invention, above formula (2) is improved, as follows:
From formula (3), in traffic sequence, contrast C ON represents parameter positive and negative change in time, can reflect the variation tendency of traffic parameter.Its absolute value | the size of CON| illustrates the severe degree of velocity variations trend.
Now for one group of data sequence, intuitively gray scale united symbiosis matrix (GLCM) and contrast (Contrast, CON) are described.If 10 data values in the prediction window of 5min constitute one group of sequence: O=(10,10,7,10,8,9,10,10,8,8), united symbiosis Matrix C can be tried to achieve according to formula (1), as shown in Figure 3.In Matrix C, element c
10,10=0.22 because the combination of (10,10) has occurred 2 times in data sequence O, and sequence always total number of combinations be 9, therefore its ratio 2/9=0.22.
From formula (3), contrast C ON has positive and negative change.In traffic sequence, contrast C ON just can represent parameter positive and negative change in time, such as, when speed has the trend of rising, contrast C ON be just on the occasion of, otherwise be negative, and its absolute value | the size of CON| illustrates the severe degree of velocity variations trend.The then contrast C ON of data sequence in above-mentioned 5min:
CON=0.11×(10-7)
2+0.11×(9-8)
2+0.11×(10-9)
2
-0.11×(10-7)
2-0.22×(10-8)
2=0.67。
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
1, o
2..., o
m.
In the present embodiment, for parametric speed, velocity variations interval is approximately (0mph, 60mph), speed observer value is divided in order to 11 grades, as shown in table 1.
Table 1 speed observer sate discretization
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.
When constructing the hidden state of THMM model, carry out discretely turning to 6 grades to speed average in prediction window, similar with classic method, friction speed level corresponds to the different parameters interval of traffic flow.It is as shown in table 2,
Table 2 average velocity discretize
From the average velocity discretize table in prediction window, friction speed descriptive grade be the static information of traffic flow modes, the traffic capacity of current flows can be stated intuitively.
In the present embodiment, the variation range of velocity contrast's degree CON is mainly (-70,70).For the ease of the structure to the hidden state of traffic Hidden Markov Model (HMM), similar with the discretize of average velocity in prediction window, turn to 7 grades by discrete for contrast C ON, 7 grades correspond respectively to contrast from negative value on the occasion of 7 intervals, as shown in table 3.
Table 3 velocity contrast degree discretize
When constructing traffic flow Hidden Markov Model (HMM), by serial mean in prediction window
discrete turn to some represent friction speed interval grade and window intrinsic parameter alignment degree CON discretize grade respectively as two factors of hidden state.Utilize contrast C ON and data sequence mean value
the hidden state set S={s of two-dimentional total divisor associating descriptive model of grade after discretize
1, s
2..., s
n.This statement is combined to hidden state, overcome classic method and only describe the more unilateral shortcoming of traffic behavior static information.
Such as, to the mean parameter in prediction window
and contrast C ON is discrete respectively turns to m level and n level, then the hidden state of its describable traffic flow is exactly m × n.The present embodiment for " speed ", to speed average in prediction window and contrast discrete be respectively 6 grades and 7 grades, therefore the hidden state of model just has 6 × 7=42 kind, then hidden state set is S={s
1, s
2..., s
42.
In order to easy, hidden state arabic numeral are represented, as shown in table 3.Thus, the traffic represented by the data sequence (containing 10 detected values in 5min) in prediction window (5min) can be set to certain state.
The hidden state of table 4 forms table
Note: in table 4, some states are the road conditions often run in the process of moving, such as state 17 is exactly the crowded situation causing traffic flow speed less peak period.State 39 represents the coast is clear, and road conditions are good, affect less situation between vehicle.But some states are rarely found, such as state 1, speed is very low, and the possibility continuing to decline is very little.However, in order to make model contain all states, will it count.
(2), after the hidden state set determining Hidden Markov Model (HMM) and observation state set, Hidden Markov Model (HMM) is trained, 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
1, O
2..., 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
(3), be applicable to exchange on the Hidden Markov Model (HMM) of stream and the basis of observed value sequence at given, the hidden status switch of optimum utilizing Viterbi algorithm to try to achieve to answer with observed value sequence pair, then the traffic flow modes predicted after the final state in hidden status switch is and detects the period; And short-term traffic flow status predication is carried out in passing successively.Because observed value is corresponding with the initial time measured value of each prediction window, then hidden state is corresponding with the traffic flow modes in prediction window, then predicted time length is exactly the length of prediction window.
First, in given Hidden Markov Model (HMM)
and observed value sequence O=(O
1, O
2..., O
t) basis on, utilize Viterbi algorithm to try to achieve and the hidden status switch S=of the optimum of observation sequence (S
1, S
2..., S
t).
Secondly, Viterbi variable δ is utilized
t(i) and memory variable
the hidden status switch S corresponding to O optimum is obtained by Viterbi algorithm iteration.
Because the measured value of setting prediction window initial time corresponds to observation state O
t, and the last hidden state S in the hidden status switch of the optimum of correspondence
tbe the description of the traffic behavior in prediction window, the state S of last moment in the status switch S of therefore Optimum Matching
tbe the state of prediction, and short-term traffic flow status predication is carried out in passing successively.
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
1, O
2..., 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
1, o
2..., 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
1, s
2..., 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
1, O
2..., 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
(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.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310276581.7A CN103413443B (en) | 2013-07-03 | 2013-07-03 | Short-term traffic flow forecasting method based on hidden Markov model |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310276581.7A CN103413443B (en) | 2013-07-03 | 2013-07-03 | Short-term traffic flow forecasting method based on hidden Markov model |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103413443A CN103413443A (en) | 2013-11-27 |
| CN103413443B true CN103413443B (en) | 2015-05-20 |
Family
ID=49606448
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201310276581.7A Expired - Fee Related CN103413443B (en) | 2013-07-03 | 2013-07-03 | Short-term traffic flow forecasting method based on hidden Markov model |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103413443B (en) |
Families Citing this family (28)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103745602B (en) * | 2014-01-16 | 2016-04-13 | 银江股份有限公司 | A kind of traffic flow forecasting method average based on sliding window |
| CN104021665B (en) * | 2014-06-06 | 2016-09-07 | 河南理工大学 | Genetic search Short-time Traffic Flow Forecasting Methods |
| CN104464291B (en) * | 2014-12-08 | 2017-02-01 | 杭州智诚惠通科技有限公司 | Traffic flow predicting method and system |
| CN104408203A (en) * | 2014-12-18 | 2015-03-11 | 西安电子科技大学宁波信息技术研究院 | Method for predicting path destination of moving object |
| CN106228850A (en) * | 2014-12-30 | 2016-12-14 | 江苏理工学院 | Ship track real-time prediction method based on rolling planning strategy |
| CN104616498B (en) * | 2015-02-02 | 2017-01-25 | 同济大学 | Markov chain and neural network based traffic congestion state combined prediction method |
| CN109255493A (en) * | 2015-03-31 | 2019-01-22 | 江苏理工学院 | Subway train track real-time prediction method based on robust strategy |
| CN105303835B (en) * | 2015-11-13 | 2017-09-01 | 西安邮电大学 | A kind of Forecasting Approach for Short-term of road traffic stream mode |
| CN106097726A (en) * | 2016-08-23 | 2016-11-09 | 苏州科达科技股份有限公司 | The detection determination in region, traffic information detection method and device |
| CN106373410B (en) * | 2016-09-21 | 2018-12-21 | 青岛大学 | A kind of Optimal Method of Urban Traffic Signal Control |
| CN106530715B (en) * | 2016-12-24 | 2019-05-31 | 浙江工业大学 | Road network traffic state prediction method based on fuzzy Markov process |
| CN106649122B (en) * | 2016-12-28 | 2020-06-26 | Tcl科技集团股份有限公司 | Model construction method and device for terminal application |
| US10140854B2 (en) | 2017-04-03 | 2018-11-27 | Here Global B.V. | Vehicle traffic state determination |
| CN107437339A (en) * | 2017-06-20 | 2017-12-05 | 北京交通大学 | Variable information advices plate control method for coordinating and system under a kind of information guidance |
| CN108629457B (en) * | 2018-05-09 | 2021-09-28 | 西南交通大学 | Travel prediction mode and method and device for building prediction model |
| CN109147325B (en) * | 2018-09-04 | 2022-01-28 | 广州视源电子科技股份有限公司 | Road condition prediction method and device, storage medium and processor |
| CN109344195B (en) * | 2018-10-25 | 2021-09-21 | 电子科技大学 | HMM model-based pipeline security event recognition and knowledge mining method |
| CN109637128B (en) * | 2018-12-14 | 2021-06-18 | 南通大学 | Markov-based gray Verhulst short-time traffic flow prediction method and system |
| CN109981358A (en) * | 2019-03-13 | 2019-07-05 | 南京理工大学 | A kind of adaptive network performance method for early warning based on built-up pattern |
| CN110084112B (en) * | 2019-03-20 | 2022-09-20 | 太原理工大学 | Traffic jam judging method based on image processing |
| CN110085026A (en) * | 2019-03-28 | 2019-08-02 | 中国公路工程咨询集团有限公司 | A kind of traffic status prediction method based on clustering and Markov model |
| CN110020475B (en) * | 2019-04-03 | 2023-10-10 | 北京工业大学 | Markov particle filtering method for traffic flow prediction |
| CN110415521B (en) * | 2019-07-31 | 2021-03-05 | 京东城市(北京)数字科技有限公司 | Traffic data prediction method, apparatus and computer-readable storage medium |
| CN111444302B (en) * | 2020-04-17 | 2020-12-18 | 中国传媒大学 | Mobility prediction method, system and device based on user classification |
| CN111951553B (en) * | 2020-08-17 | 2022-11-11 | 上海电科智能系统股份有限公司 | Prediction method based on traffic big data platform and mesoscopic simulation model |
| CN113380026B (en) * | 2021-05-28 | 2022-07-22 | 南京理工大学 | HMM-based highway traffic prediction method |
| CN113762644B (en) * | 2021-09-26 | 2023-11-24 | 中国联合网络通信集团有限公司 | Congestion state prediction method and device based on Markov chain |
| CN114282169B (en) * | 2021-10-12 | 2024-07-12 | 腾讯科技（深圳）有限公司 | Abnormal data detection method and related device |
Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1707544A (en) * | 2005-05-26 | 2005-12-14 | 上海交通大学 | Method for estimating city road network traffic flow state |
| CN1776739A (en) * | 2004-11-16 | 2006-05-24 | 微软公司 | Traffic predictiong using model-setting and analuzing to probability relativity and environment data |
| US20070208492A1 (en) * | 2006-03-03 | 2007-09-06 | Inrix, Inc. | Dynamic time series prediction of future traffic conditions |
| CN101188002A (en) * | 2007-12-24 | 2008-05-28 | 北京大学 | A city traffic dynamic prediction system and method with real time and continuous feature |
| US20090002195A1 (en) * | 2007-06-29 | 2009-01-01 | Microsoft Corporation | Sensing and predicting flow variance in a traffic system for traffic routing and sensing |
| US20120072096A1 (en) * | 2006-03-03 | 2012-03-22 | Chapman Craig H | Dynamic prediction of road traffic conditions |
| CN102695637A (en) * | 2009-08-31 | 2012-09-26 | 丰田自动车欧洲股份有限公司 | Vehicle or traffic control method and system |
-
2013
- 2013-07-03 CN CN201310276581.7A patent/CN103413443B/en not_active Expired - Fee Related
Patent Citations (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1776739A (en) * | 2004-11-16 | 2006-05-24 | 微软公司 | Traffic predictiong using model-setting and analuzing to probability relativity and environment data |
| CN1707544A (en) * | 2005-05-26 | 2005-12-14 | 上海交通大学 | Method for estimating city road network traffic flow state |
| US20070208492A1 (en) * | 2006-03-03 | 2007-09-06 | Inrix, Inc. | Dynamic time series prediction of future traffic conditions |
| US20120072096A1 (en) * | 2006-03-03 | 2012-03-22 | Chapman Craig H | Dynamic prediction of road traffic conditions |
| US20090002195A1 (en) * | 2007-06-29 | 2009-01-01 | Microsoft Corporation | Sensing and predicting flow variance in a traffic system for traffic routing and sensing |
| CN101188002A (en) * | 2007-12-24 | 2008-05-28 | 北京大学 | A city traffic dynamic prediction system and method with real time and continuous feature |
| CN102695637A (en) * | 2009-08-31 | 2012-09-26 | 丰田自动车欧洲股份有限公司 | Vehicle or traffic control method and system |
Non-Patent Citations (2)
| Title |
|---|
| 基于小波分析的随机交通流组合预测方法研究;丁恒，等;《系统仿真学报》;20120208;第24卷(第2期);第377-381页 * |
| 基于影响模型的短时交通流预测方法;丁栋，等;《计算机工程》;20120520;第38卷(第10期);第164-167页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103413443A (en) | 2013-11-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103413443B (en) | Short-term traffic flow forecasting method based on hidden Markov model | |
| Majumdar et al. | Congestion prediction for smart sustainable cities using IoT and machine learning approaches | |
| CN109035761B (en) | Travel time estimation method based on auxiliary supervised learning | |
| CN102110365B (en) | Road condition prediction method and road condition prediction system based on space-time relationship | |
| Osorio et al. | Urban transportation emissions mitigation: Coupling high-resolution vehicular emissions and traffic models for traffic signal optimization | |
| CN110570651A (en) | Road network traffic situation prediction method and system based on deep learning | |
| CN105405293B (en) | A kind of road travel time short term prediction method and system | |
| CN105185115A (en) | Vehicle forecasting method and forecasting system | |
| CN103177570A (en) | Method for predicting traffic jam indexes for rush hours in morning and evening | |
| Dimitriou et al. | Fuzzy modeling of freeway accident duration with rainfall and traffic flow interactions | |
| CN103632546A (en) | Floating car data-based urban road traffic accident influence prediction method | |
| CN109376906B (en) | Travel time prediction method and system based on multi-dimensional trajectory and electronic equipment | |
| Mucsi et al. | An Adaptive Neuro-Fuzzy Inference System for estimating the number of vehicles for queue management at signalized intersections | |
| CN105243428A (en) | Bus arrival time prediction method through optimizing support vector machine based on bat algorithm | |
| Chen et al. | A review on traffic prediction methods for intelligent transportation system in smart cities | |
| CN106156890A (en) | Detection of passenger flow and Forecasting Methodology and system thereof in a kind of urban track traffic passage | |
| Zhang et al. | Road section traffic flow prediction method based on the traffic factor state network | |
| CN106875681A (en) | A kind of traffic congestion tendency Forecasting Methodology and system | |
| Zhao et al. | A traffic flow prediction approach: LSTM with detrending | |
| CN112669595A (en) | Online taxi booking flow prediction method based on deep learning | |
| CN111209979A (en) | Method and device for monitoring vehicle voltage and electronic equipment | |
| Wang et al. | Statistical learning for train delays and influence of winter climate and atmospheric icing | |
| CN113420925B (en) | Traffic health prediction method and system based on naive Bayes | |
| Chen | Research on short-term traffic flow forecasting model based on LSTM | |
| CN107403241A (en) | A kind of urban track traffic for passenger flow second order fluctuation computational methods |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20150520 |