# Big Data-Driven Based Real-Time Traffic Flow State Identification and Prediction

Authors: Hua-pu Lu; Zhi-yuan Sun; Wen-cong Qu
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

With the rapid development of urban informatization, the era of big data is coming. To satisfy the demand of traffic congestion early warning, this paper studies the method of real-time traffic flow state identification and prediction based on big data-driven theory. Traffic big data holds several characteristics, such as temporal correlation, spatial correlation, historical correlation, and multistate. Traffic flow state quantification, the basis of traffic flow state identification, is achieved by a SAGA-FCM (simulated annealing genetic algorithm based fuzzyc-means) based traffic clustering model. Considering simple calculation and predictive accuracy, a bilevel optimization model for regional traffic flow correlation analysis is established to predict traffic flow parameters based on temporal-spatial-historical correlation. A two-stage model for correction coefficients optimization is put forward to simplify the bilevel optimization model. The first stage model is built to calculate the number of temporal-spatial-historical correlation variables. The second stage model is present to calculate basic model formulation of regional traffic flow correlation. A case study based on a real-world road network in Beijing, China, is implemented to test the efficiency and applicability of the proposed modeling and computing methods.


---

## Body

## 1. Introduction

Real-time traffic flow state identification and prediction is one of the critical components of intelligent transportation system. It is of practical significance to identify and predict traffic flow state quickly, precisely and timely. As the first problem that needs to be solved, traffic flow state can be measured by level of service (LOS), which is first introduced in the 1965 Highway Capacity Manual (HCM 1965) [1]. The latest version of Highway Capacity Manual (HCM 2010) [2] divided LOS into six levels. Sasaki and Iida [3] divided LOS into three levels. China GB 50220-1995 [4] divided LOS into four levels. Existing studies of LOS evaluation can be classified into four categories in transportation literature: subjective evaluation based models [5], statistical analysis based models [6], artificial intelligence based models [7], traffic flow theory based models [8, 9].Many previous research works concerning traffic flow state identification especially for Beijing have been carried out. Guan and He [10] analyzed the statistical features of speed distribution at different density and divided traffic flow state into four levels based on flow-rate-density plane. Liao et al. [11] studied traffic state identification based on perceptual experiment. Xia et al. [12] built traffic state rapid identification model based on fuzzy theory. Qu et al. [13] determined the relation between traffic state and travel speed. Moreover, Beijing Traffic Management Bureau built Beijing Regional Traffic Conditions and LOS Evaluation System mainly based on fixed detectors [14], and Beijing Municipal Commission of Transport built Traffic Performance Index System mainly based on floating car data [15].Real-time traffic flow prediction aims at evaluating anticipated traffic flow state at a future time. Many studies focused on traffic flow state and parameters prediction. Liu et al. [16] analyzed multidimensional parameters and developed the traffic prediction models of different dimensions based on the support vector machine. Dong et al. [17] proposed a preselection space time model to estimate the traffic condition at poor-data-detector, especially nondetector locations. Canaud et al. [18] presented a probability hypothesis density filtering based model for real-time traffic flow state prediction. Pan et al. [19] put forward a modified stochastic cell transmission model to support short-term traffic flow state prediction. Antoniou et al. [20] proposed an approach for local traffic flow state estimation and prediction based on data-driven computational approaches. Zhang et al. [21] designed a traffic flow state estimator based on extended-Kalman-filter method.Traffic big data, massive and multisource, brings both opportunities and challenges to effective traffic management and control. During data processing, traffic big data meets the same difficulties with the general big data, such as capture, storage, search, sharing, analytics, and visualization. The differences between traffic big data and traditional data in the field of traffic flow state identification and prediction are obvious. For traffic flow state identification, the advantage of traffic big data is mainly manifested in the full coverage. That is, traffic big data can represent traffic flow characteristics as much as possible. However, the difficulties of data processing are enhanced with the increasing of the size of data. Therefore, big data-driven methods should have a stronger capacity of data processing. For traffic flow state prediction, the advantage of traffic big data is mainly manifested in the multisource. That is, the traffic big data has a higher accuracy to describe the relationships between traffic flow state of sections at time t and the others. However, the relationships are not easy to be found. So, big data-driven methods should have a clearer description of physical significance of traffic flow. Traffic big data can improve the efficiency of real-time traffic flow state identification and prediction. However, it may face more challenges.Taking into account all the present researches in this field, there is still a lack of consideration of traffic big data. Further researches remain to be conducted on the direction of traffic flow state analysis. In this paper, the method of real-time traffic flow state identification and prediction, which perceives ability to handle big data, is put forward in detail. The remainder of this paper is organized as follows. Section2 presents the basic characteristics of traffic big data. In Section 3, the methodology of real-time traffic flow state identification and prediction is proposed. A case study based on a real-world road network is carried out in Section 4 to demonstrate the performance and applicability of the proposed method. Finally, conclusions are drowned in Section 5.


## 2. Traffic Big Data Analysis

### 2.1. Temporal Correlation

By laying fixed and mobile traffic flow detectors, dynamic traffic data of a section can be obtained. Dynamic traffic flow dataV are time-series data, which continuously change over time t with a certain trend; namely,
(1)
V
t
=
T
V
t
-
1
,
V
t
-
2
,
…
,
where V
t is the traffic flow parameter at time t, representing flow q
t, speed v
t, or occupancy ρ
t. T is a function that describes trends of traffic flow time-series data.


### 2.2. Spatial Correlation

A regional transportation network consists of multiple intersections and roads. It exists a spatial association between traffic flow data of neighboring junctions or sections and that of target junctions or sections; namely,(2)
V
s
,
t
=
S
V
1
,
t
,
V
2
,
t
,
…
,
where V
s
,
t is the traffic flow parameter of section s at time t, representing flow q
s
,
t, speed v
s
,
t, or occupancy ρ
s
,
t. S defines the relationship between the data of upstream and downstream sections.


### 2.3. Historical Correlation

For different weekdays or weekends, trip distribution of inhabitants in the same period shows similar characteristics. The law of traffic flow cycle is especially evident. Correlation between dynamic traffic flow data and historical data is as follows:(3)
V
D
,
t
=
H
V
D
-
1
,
t
,
V
D
-
2
,
t
,
…
,
where V
D
,
t is the traffic flow parameter on day D at time t, representing flow q
D
,
t, speed v
D
,
t, or occupancy ρ
D
,
t. H defines the relationship between the data of different workdays or holidays at the same time.


### 2.4. Multistate

Traffic flow state can be determined by the traffic flow parameters. The correspondence between traffic flow states and traffic flow parameters is as follows:(4)
A
=
MS
v
,
q
,
ρ
,
where A is LOS. v, q, and ρ are the traffic flow parameters. MS defines the relationship between traffic flow states and traffic flow parameters.


## 2.1. Temporal Correlation

By laying fixed and mobile traffic flow detectors, dynamic traffic data of a section can be obtained. Dynamic traffic flow dataV are time-series data, which continuously change over time t with a certain trend; namely,
(1)
V
t
=
T
V
t
-
1
,
V
t
-
2
,
…
,
where V
t is the traffic flow parameter at time t, representing flow q
t, speed v
t, or occupancy ρ
t. T is a function that describes trends of traffic flow time-series data.


## 2.2. Spatial Correlation

A regional transportation network consists of multiple intersections and roads. It exists a spatial association between traffic flow data of neighboring junctions or sections and that of target junctions or sections; namely,(2)
V
s
,
t
=
S
V
1
,
t
,
V
2
,
t
,
…
,
where V
s
,
t is the traffic flow parameter of section s at time t, representing flow q
s
,
t, speed v
s
,
t, or occupancy ρ
s
,
t. S defines the relationship between the data of upstream and downstream sections.


## 2.3. Historical Correlation

For different weekdays or weekends, trip distribution of inhabitants in the same period shows similar characteristics. The law of traffic flow cycle is especially evident. Correlation between dynamic traffic flow data and historical data is as follows:(3)
V
D
,
t
=
H
V
D
-
1
,
t
,
V
D
-
2
,
t
,
…
,
where V
D
,
t is the traffic flow parameter on day D at time t, representing flow q
D
,
t, speed v
D
,
t, or occupancy ρ
D
,
t. H defines the relationship between the data of different workdays or holidays at the same time.


## 2.4. Multistate

Traffic flow state can be determined by the traffic flow parameters. The correspondence between traffic flow states and traffic flow parameters is as follows:(4)
A
=
MS
v
,
q
,
ρ
,
where A is LOS. v, q, and ρ are the traffic flow parameters. MS defines the relationship between traffic flow states and traffic flow parameters.


## 3. Methodology

### 3.1. Overall Framework

The overall traffic flow state identification and prediction framework is outlined in Figure1.Figure 1
Overall traffic flow state identification and prediction framework.(a) SAGA-FCM Based Traffic Clustering Model. As a random social phenomenon, traffic flow state holds fuzzy characteristics. For example, “congested” and “uncongested” are the fuzzy descriptions of traffic flow. It is difficult to describe these states quantitatively. Since membership function can be used to explain the fuzzy phenomenon, fuzzy c-means algorithm (FCM) is designed to evaluate traffic flow state [22]. However, FCM is sensitive to its initial clustering center and it is easy to fall into the local optimum, especially for big data [23]. SAGA-FCM algorithm integrates the strong local search ability of simulated annealing algorithm (SA) and the strong global search ability of genetic algorithm (GA) to overcome the drawbacks of traditional FCM algorithm [24].(b) DFT Based Historical Data Fusion Model. Road traffic flow state information is periodic [25]. Each object to predict can be associated with a set of historical data. Actual intelligent traffic system has accumulated massive historical data. However, it is difficult to achieve the integration of historical data. During the on-going development of traffic prediction system in Beijing, discrete Fourier transform (DFT) is found effective in achieving the average of historical data and noise elimination [26]. Traffic parameters are discrete time series sequence; therefore DTF is applied to integrate massive historical data [27].(c) Regional Traffic Flow Correlation Model. Temporal correlation, spatial correlation and historical correlation are the characteristics of traffic big data. Based on this principle, regional traffic flow correlation model can be established to predict traffic flow parameters. Taking simple calculation and predictive accuracy into consideration, a bi-level optimization model is proposed to simplify the regional traffic flow correlation model.(d) Correction Coefficients Optimization Model.Considering the amount of temporal, spatial, and historical variables, each of which corresponds to an unknown parameter, the model is too difficult to calibrate. Therefore, a two-stage model for correction coefficients optimization is put forward to reduce the number of variables and ensure accuracy simultaneously.


### 3.2. SAGA-FCM Based Traffic Clustering Model

#### 3.2.1. Basic Traffic Clustering Model

Based on HCM 2010 [2], LOS (A) can be divided into six types, as A
=
A
1
,
A
2
,
…
,
A
6. Considering the monotonicity between traffic flow parameters and LOS, speed (v) and occupancy (ρ) are chosen as clustering parameters. Therefore, data sample used for traffic clustering model can be written as X
=
x
1
,
x
2
,
…
,
x
n, x
j
=
v
j
,
ρ
j. Since traditional FCM algorithm is put forward to find an optimal classification, the objective function is expressed as(5)
min
⁡
J
b
U
,
a
=
∑
i
=
1
6
∑
j
=
1
n
μ
i
j
b
d
i
j
2
s
.
t
.
∑
i
=
1
6
μ
i
j
=
1
,
0
≤
μ
i
j
≤
1
i
=
1,2
,
…
,
6
,
j
=
1,2
,
…
,
n
,
where U is membership matrix, U
=
μ
i
x
j
6
×
n. a is the set of clustering centers, a
=
a
1
,
a
2
,
…
,
a
6, a
i
=
v
i
,
ρ
i. d
i
j is the Euclidean distance that measures distance between data sample (x
j) and clustering center (a
i), d
i
j
=
d
x
j
-
a
i
=
x
j
-
a
i. b is weighted parameter, b
∈
1
,
+
∞. μ
i
x
j is the degree of membership of which the sample data x
j belongs to LOS A
i, shorten for μ
i
j.a
i can be calculated by the flowing formulation
(6)
a
i
=
∑
j
=
1
n
μ
i
j
b
x
j
∑
j
=
1
n
μ
i
j
b
,
s
.
t
.
∑
i
=
1
6
μ
i
j
=
1
,
0
≤
μ
i
j
≤
1
,
0
≤
∑
j
=
1
n
μ
i
j
≤
1
i
=
1,2
,
…
,
6
,
j
=
1,2
,
…
,
n
.μ
i
j can be calculated by the flowing formulation
(7)
μ
i
j
=
1
∑
k
=
1
6
d
i
j
/
d
k
j
2
/
(
b
-
1
)
,
d
i
j
>
0
,
1
,
d
i
j
=
0
,
i
=
j
,
0
,
d
i
j
=
0
,
i
≠
j
.Modification of the clustering centers and degrees of membership is the core of FCM. When the algorithm is convergent, clustering centersa
i can be found, and degrees of membership μ
i
j can be calculated. Therefore, fuzzy clustering result can be achieved.


#### 3.2.2. SAGA-FCM Based Solution Algorithm

SAGA-FCM algorithm is used to improve the clustering quality of FCM. The process of SAGA-FCM algorithm can be summarized as in the following steps [28].Step 1 (parameters initialization). Population size (s
i
z
e
p
o
p), maximum genetic evolution algebra (M
A
X
G
E
N), crossing probability (P
c), gene variation probability (P
m), original temperature (T
0), cooling coefficient (l), and final temperature (T
end).Step 2 (clustering centers initialization). Randomly selecting six clustering centers (a), designing the original sequence (c
h
r
o
m), calculating degrees of membership (μ
i
j), and fitness value of each individual (f
i).Step 3 (genetic evolution algebra initialization). g
e
n
=
0.Step 4 (genetic operations). Selection, crossover, and mutation of original sequence (c
h
r
o
m), achieving new clustering centers (a), calculating degrees of membership (μ
i
j
′), and fitness value of each individual (f
i
′).Step 5 (fitness value judgment). If f
i
′
>
f
i, replace all of the old individual with the new individual; otherwise, replace the old individual with the new individual by probability (P
=
exp
⁡
f
i
-
f
i
′
T).Step 6 (M
A
X
G
E
N judgment). If g
e
n
<
M
A
X
G
E
N, g
e
n
=
g
e
n
+
1, turn to Step 4; otherwise, turn to Step 7.Step 7 (temperature judgment). If T
i
<
T
end, the new solution is outputted, and that is the most optimized assembly sequence; otherwise, T
i
+
1
=
l
T
i, turning to Step 3.


#### 3.2.3. Calculation of LOS

Based on SAGA-FCM algorithm, six clustering centers (a) can be found. Thus, μ
i
j is calculated by formulation 7. Combining the numerical magnitude of μ
i
j, the LOS of x
j
A
x
j is achieved:
(8)
A
x
j
=
A
k
s
.
t
.
μ
k
j
>
μ
i
j
,
k
≠
i
,
where A
x
j is the LOS of x
j.


### 3.3. DFT Based Historical Data Fusion Model

Given a discrete temporal seriesx
0
,
x
1
,
…
,
x
N
-
1, the length of which is N, its discrete Fourier transform with M sampling points can be calculated:
(9)
X
k
=
1
N
×
∑
n
=
0
N
-
1
x
n
×
e
-
j
(
2
k
π
/
N
)
n
,
k
=
0,1
,
…
,
M
-
1
.The corresponding inverse Fourier transform formulation is(10)
x
n
=
∑
k
=
0
M
-
1
X
k
×
e
j
(
2
k
π
/
N
)
n
,
k
=
0,1
,
…
,
M
-
1
.Normally, takeM
=
N. To facilitate the program, the natural logarithm complex power form above is converted to trigonometric form:
(11)
x
i
=
a
0
+
∑
f
=
1
N
-
1
α
n
cos
⁡
2
π
N
f
i
+
β
n
sin
2
π
N
f
i
v
v
v
v
v
v
v
v
v
v
×
f
i
=
e
j
2
k
π
/
N
i
i
=
0,1
,
…
,
N
-
1
.Suppose that the traffic flow varies in one week cycle, which includes 7 days with different characteristics. Each day contains 288 pieces of data with a time interval of 5 minutes. Apply DFT to average massive historical data and to eliminate noise, so as to achieve the integration of historical data. Consider(12)
V
D
H
=
V
D
,
1
H
,
…
,
V
D
,
t
H
,
…
,
V
D
,
288
H
,
where V
D
H is the collection of historical data on day D, D
=
1,2
,
…
,
7. V
D
,
t
H is the traffic data on day D at time t, V
D
,
t
H
=
q
D
,
t
H
,
v
D
,
t
H
,
ρ
D
,
t
H
T, t
=
1,2
,
…
,
288.For example, the process of DFT of traffic volume(
q
) can be summarized as in the following steps.Step 1. Enter the discrete temporal series q
0
,
q
1
,
…
,
q
287.Step 2. Apply DFT and acquire Fourier coefficients sequence α
1
,
β
1
,
α
2
,
β
2
,
…
,
α
287
,
β
287.Step 3. Filter Fourier coefficients series to excise all coefficients less than the specified amplitude threshold of coefficient. Record the rest of the coefficients. The value of the threshold needs to be chosen by analyzing the historical data.Step 4. Restore data at any point in the sequence q
i.


### 3.4. Regional Traffic Flow Correlation Model

#### 3.4.1. Basic Model Formulation

The basic assumption of the regional traffic flow correlation model is that traffic flow has a strong temporal-spatial-historical correlation, namely:(i)
in the temporal series, the traffic flow of the last moment can be regarded as the continuation of the current traffic flow;
(ii)
in the spatial series, downstream sections of the traffic flow can be seen as a continuation of the upstream traffic flow;
(iii)
in the historical series, traffic demand characteristics determine that traffic flow characteristics of the same day in the same period are similar.Basic form of regional traffic flow correlation model is expressed as(13)
V
s
t
=
γ
T
V
T
t
+
γ
S
V
S
t
+
γ
H
V
H
t
s
.
t
.
γ
T
+
γ
S
+
γ
H
=
1
,
γ
T
,
γ
S
,
γ
H
≥
0
,
where V
s
t is the traffic flow parameter of section s at time t, representing flow q
s
t, speed v
s
t, or occupancy ρ
s
t. V
T
t, V
S
t, and V
H
t are the estimated value of V
s
t. V
T
t is calculated by temporal correlation analysis. V
S
t is calculated by spatial correlation analysis. V
H
t is calculated by historical correlation analysis. γ
T, γ
S, and γ
H are coefficients of these three variables.According to formulation1, T is generally achieved by regression analysis model. Thus, V
T
t is created by the following equation:
(14)
V
T
t
=
θ
1
V
s
t
-
1
+
θ
2
V
s
t
-
2
+
⋯
s
.
t
.
∑
θ
=
1
,
θ
≥
0
,
where V
s
t
-
d is the traffic flow parameter of section s at time t
-
d. d is time delay, d
≥
0. θ
1
,
θ
2
,
… are regression coefficients.According to formulation2, S is generally achieved by neighbor regression model. Thus, V
S
t is created by the following equation:
(15)
V
S
t
=
λ
1
V
1
t
-
1
+
λ
2
V
2
t
-
2
+
⋯
s
.
t
.
∑
λ
=
1
,
λ
≥
0
,
where V
j
t
-
d is the traffic flow parameter of section j at time t
-
d. λ
1
,
λ
2
,
… are regression coefficients.According to formulations12, 13, 14, and 15, simplified equation is achieved:
(16)
V
s
t
=
∑
∑
ω
j
d
V
j
t
-
d
s
.
t
.
∑
ω
=
1
,
ω
>
0
,
η
∈
N
*
,
where ω
j
d is regression coefficient of V
j
t
-
d. η is the number of ω
j
d.


#### 3.4.2. Effectiveness Proof of Proposed Formulation

The general form of formula16 is
(17)
Y
=
∑
i
=
1
n
w
i
Y
i
s
.
t
.
∑
i
=
1
n
w
i
=
1
,
w
i
≥
0
,
where Y is the state of physical system with the measurement of multisensors. Y
i is the measured value of i
th sensor, and they are independent. w
i is a weighting factor.The total mean square errorδ
2 is a multivariate quadratic function of w
i:
(18)
δ
2
=
∑
i
=
1
n
w
i
2
δ
i
2
,
where δ
i is the mean square error of Y
i.According to extreme value theorem of multivariate quadratic function, weighting factor can be calculated as follows:(19)
w
i
=
1
δ
i
2
∑
i
=
1
n
1
/
δ
i
2
.Assume that the detection accuracy varies with sensors, the mean square error of the measurements from the least accurate sensor isδ
min
⁡
2 and that from the most accurate sensor is δ
max
⁡
2. Then,
(20)
esp
Y
=
1
δ
max
⁡
2
+
1
δ
min
⁡
2
+
∑
i
=
1
n
-
2
1
δ
i
2
-
1
<
1
δ
min
⁡
2
+
∑
i
=
1
n
-
2
1
δ
i
2
-
1
<
δ
min
⁡
2
.The formula above shows that the measurement accuracy of the system can be improved by multisensor measurement and that participation of an inaccurate sensor also helps improve the accuracy of the system.


#### 3.4.3. Bilevel Optimization Model

For big date-driven analysis, the speed and accuracy of data processing are both important. The number of unknown parameters in formulation16 is large and uncontrolled. Therefore, taking simple calculation and predictive accuracy into consideration, a bilevel optimization model is proposed.The upper level model is formulated to optimize the speed of date processing by minimizing the number of temporal-spatial-historical correlation variables. The upper level formulation is(21)
min
⁡
η
s
.
t
.
η
∈
N
*
.The lower level model is articulated in accordance with predictive accuracy. Therefore, the lower level formulation is proposed in order to minimize predictive encoding. The lower level formulation is(22)
min
⁡
V
s
t
-
V
^
s
t
s
.
t
.
V
s
t
=
∑
∑
ω
j
d
V
j
t
-
d
,
∑
ω
=
1
,
ω
≥
0
,
where V
^
s
t is actual value of V
s
t.In the bilevel optimization model, the purpose of objective function is to achieve a best combination, which holds both fast calculation speed and high prediction accuracy.


### 3.5. Correction Coefficients Optimization Model

The more the temporal-spatial-historical correlation variables are, the slower the program calculates and the higher the accuracy is. The bilevel optimization model above is difficult to solve. To put it in another way, we can define a threshold of computing speed and therefore derive the maximum of acceptable number of temporal-spatial-historical correlation variables. In addition, we can put forward a new variable which can be calculated to replace the variableω
j
d. Since the alternative process will bring some errors, which are likely to be systematic, a linear correction method is put forward. Therefore, the correction coefficients optimization model is a two-stage model.


#### 3.5.1. The First Stage Model

The first stage model is mainly used to determine the number of unknown parametersη. It can be determined through the following steps.Step 1 (determination of the range of η). The number of unknown parameters should not exceed a threshold value. After several data tests, it is found that when η is less than 4, the correlation coefficients are not very different from relatively high values; when η is more than 8, the rapid decay of the correlation coefficients is observed with relatively low values. Therefore η ranges from 4,8.Step 2 (calculation of the correlation coefficients). Calculate the correlation coefficients (r
j
d) between the studied section s and the related section j, solve the max correlation coefficient (r
j) corresponding to each section j, and determine the corresponding time delay (d); namely, r
j
=
max
⁡
r
j
d. r
j
d can be solved by
(23)
r
j
d
=
∑
t
=
1
n
-
d
V
s
(
t
)
V
j
(
t
-
d
)
-
1
n
-
d
∑
t
=
1
n
-
d
V
s
(
t
)
∑
t
=
1
n
-
d
V
j
(
t
-
d
)
×
∑
t
=
1
n
-
d
V
s
2
(
t
)
-
1
n
-
d
∑
t
=
1
n
-
d
V
s
t
2
×
∑
t
=
1
n
-
d
V
j
2
t
-
d
-
1
n
-
d
∑
t
=
1
n
-
d
V
j
t
-
d
2
-
1
/
2
s
.
t
d
≥
0
.
Step 3 (selection of the relative section). Sort r
j in ascending order, and take the first η section as a range of temporal and spatial correlation.


#### 3.5.2. The Second Stage Model

The second stage model is mainly used to reduce parameters and determines the base model. Through the first stage model, the number of unknown parameters is reduced. But the model is still difficult to solve and can be further simplified.Step 1 (calculation of the normalization factor). Take normalized r
j as the parameters of V
j
t
-
d:
(24)
ω
j
=
r
j
∑
j
=
1
η
r
j
,
∑
j
=
1
η
ω
j
=
1
,
ω
j
>
0
.
Step 2 (solving the system error). Introduce the correction parameters φ and ε to calibrate, in order to reduce the system error caused by parameter substitution:
(25)
min
⁡
V
s
t
-
V
^
s
t
s
.
t
.
V
s
t
=
φ
∑
j
=
1
η
ω
j
V
j
t
-
d
+
ε
.


## 3.1. Overall Framework

The overall traffic flow state identification and prediction framework is outlined in Figure1.Figure 1
Overall traffic flow state identification and prediction framework.(a) SAGA-FCM Based Traffic Clustering Model. As a random social phenomenon, traffic flow state holds fuzzy characteristics. For example, “congested” and “uncongested” are the fuzzy descriptions of traffic flow. It is difficult to describe these states quantitatively. Since membership function can be used to explain the fuzzy phenomenon, fuzzy c-means algorithm (FCM) is designed to evaluate traffic flow state [22]. However, FCM is sensitive to its initial clustering center and it is easy to fall into the local optimum, especially for big data [23]. SAGA-FCM algorithm integrates the strong local search ability of simulated annealing algorithm (SA) and the strong global search ability of genetic algorithm (GA) to overcome the drawbacks of traditional FCM algorithm [24].(b) DFT Based Historical Data Fusion Model. Road traffic flow state information is periodic [25]. Each object to predict can be associated with a set of historical data. Actual intelligent traffic system has accumulated massive historical data. However, it is difficult to achieve the integration of historical data. During the on-going development of traffic prediction system in Beijing, discrete Fourier transform (DFT) is found effective in achieving the average of historical data and noise elimination [26]. Traffic parameters are discrete time series sequence; therefore DTF is applied to integrate massive historical data [27].(c) Regional Traffic Flow Correlation Model. Temporal correlation, spatial correlation and historical correlation are the characteristics of traffic big data. Based on this principle, regional traffic flow correlation model can be established to predict traffic flow parameters. Taking simple calculation and predictive accuracy into consideration, a bi-level optimization model is proposed to simplify the regional traffic flow correlation model.(d) Correction Coefficients Optimization Model.Considering the amount of temporal, spatial, and historical variables, each of which corresponds to an unknown parameter, the model is too difficult to calibrate. Therefore, a two-stage model for correction coefficients optimization is put forward to reduce the number of variables and ensure accuracy simultaneously.


## 3.2. SAGA-FCM Based Traffic Clustering Model

### 3.2.1. Basic Traffic Clustering Model

Based on HCM 2010 [2], LOS (A) can be divided into six types, as A
=
A
1
,
A
2
,
…
,
A
6. Considering the monotonicity between traffic flow parameters and LOS, speed (v) and occupancy (ρ) are chosen as clustering parameters. Therefore, data sample used for traffic clustering model can be written as X
=
x
1
,
x
2
,
…
,
x
n, x
j
=
v
j
,
ρ
j. Since traditional FCM algorithm is put forward to find an optimal classification, the objective function is expressed as(5)
min
⁡
J
b
U
,
a
=
∑
i
=
1
6
∑
j
=
1
n
μ
i
j
b
d
i
j
2
s
.
t
.
∑
i
=
1
6
μ
i
j
=
1
,
0
≤
μ
i
j
≤
1
i
=
1,2
,
…
,
6
,
j
=
1,2
,
…
,
n
,
where U is membership matrix, U
=
μ
i
x
j
6
×
n. a is the set of clustering centers, a
=
a
1
,
a
2
,
…
,
a
6, a
i
=
v
i
,
ρ
i. d
i
j is the Euclidean distance that measures distance between data sample (x
j) and clustering center (a
i), d
i
j
=
d
x
j
-
a
i
=
x
j
-
a
i. b is weighted parameter, b
∈
1
,
+
∞. μ
i
x
j is the degree of membership of which the sample data x
j belongs to LOS A
i, shorten for μ
i
j.a
i can be calculated by the flowing formulation
(6)
a
i
=
∑
j
=
1
n
μ
i
j
b
x
j
∑
j
=
1
n
μ
i
j
b
,
s
.
t
.
∑
i
=
1
6
μ
i
j
=
1
,
0
≤
μ
i
j
≤
1
,
0
≤
∑
j
=
1
n
μ
i
j
≤
1
i
=
1,2
,
…
,
6
,
j
=
1,2
,
…
,
n
.μ
i
j can be calculated by the flowing formulation
(7)
μ
i
j
=
1
∑
k
=
1
6
d
i
j
/
d
k
j
2
/
(
b
-
1
)
,
d
i
j
>
0
,
1
,
d
i
j
=
0
,
i
=
j
,
0
,
d
i
j
=
0
,
i
≠
j
.Modification of the clustering centers and degrees of membership is the core of FCM. When the algorithm is convergent, clustering centersa
i can be found, and degrees of membership μ
i
j can be calculated. Therefore, fuzzy clustering result can be achieved.


### 3.2.2. SAGA-FCM Based Solution Algorithm

SAGA-FCM algorithm is used to improve the clustering quality of FCM. The process of SAGA-FCM algorithm can be summarized as in the following steps [28].Step 1 (parameters initialization). Population size (s
i
z
e
p
o
p), maximum genetic evolution algebra (M
A
X
G
E
N), crossing probability (P
c), gene variation probability (P
m), original temperature (T
0), cooling coefficient (l), and final temperature (T
end).Step 2 (clustering centers initialization). Randomly selecting six clustering centers (a), designing the original sequence (c
h
r
o
m), calculating degrees of membership (μ
i
j), and fitness value of each individual (f
i).Step 3 (genetic evolution algebra initialization). g
e
n
=
0.Step 4 (genetic operations). Selection, crossover, and mutation of original sequence (c
h
r
o
m), achieving new clustering centers (a), calculating degrees of membership (μ
i
j
′), and fitness value of each individual (f
i
′).Step 5 (fitness value judgment). If f
i
′
>
f
i, replace all of the old individual with the new individual; otherwise, replace the old individual with the new individual by probability (P
=
exp
⁡
f
i
-
f
i
′
T).Step 6 (M
A
X
G
E
N judgment). If g
e
n
<
M
A
X
G
E
N, g
e
n
=
g
e
n
+
1, turn to Step 4; otherwise, turn to Step 7.Step 7 (temperature judgment). If T
i
<
T
end, the new solution is outputted, and that is the most optimized assembly sequence; otherwise, T
i
+
1
=
l
T
i, turning to Step 3.


### 3.2.3. Calculation of LOS

Based on SAGA-FCM algorithm, six clustering centers (a) can be found. Thus, μ
i
j is calculated by formulation 7. Combining the numerical magnitude of μ
i
j, the LOS of x
j
A
x
j is achieved:
(8)
A
x
j
=
A
k
s
.
t
.
μ
k
j
>
μ
i
j
,
k
≠
i
,
where A
x
j is the LOS of x
j.


## 3.2.1. Basic Traffic Clustering Model

Based on HCM 2010 [2], LOS (A) can be divided into six types, as A
=
A
1
,
A
2
,
…
,
A
6. Considering the monotonicity between traffic flow parameters and LOS, speed (v) and occupancy (ρ) are chosen as clustering parameters. Therefore, data sample used for traffic clustering model can be written as X
=
x
1
,
x
2
,
…
,
x
n, x
j
=
v
j
,
ρ
j. Since traditional FCM algorithm is put forward to find an optimal classification, the objective function is expressed as(5)
min
⁡
J
b
U
,
a
=
∑
i
=
1
6
∑
j
=
1
n
μ
i
j
b
d
i
j
2
s
.
t
.
∑
i
=
1
6
μ
i
j
=
1
,
0
≤
μ
i
j
≤
1
i
=
1,2
,
…
,
6
,
j
=
1,2
,
…
,
n
,
where U is membership matrix, U
=
μ
i
x
j
6
×
n. a is the set of clustering centers, a
=
a
1
,
a
2
,
…
,
a
6, a
i
=
v
i
,
ρ
i. d
i
j is the Euclidean distance that measures distance between data sample (x
j) and clustering center (a
i), d
i
j
=
d
x
j
-
a
i
=
x
j
-
a
i. b is weighted parameter, b
∈
1
,
+
∞. μ
i
x
j is the degree of membership of which the sample data x
j belongs to LOS A
i, shorten for μ
i
j.a
i can be calculated by the flowing formulation
(6)
a
i
=
∑
j
=
1
n
μ
i
j
b
x
j
∑
j
=
1
n
μ
i
j
b
,
s
.
t
.
∑
i
=
1
6
μ
i
j
=
1
,
0
≤
μ
i
j
≤
1
,
0
≤
∑
j
=
1
n
μ
i
j
≤
1
i
=
1,2
,
…
,
6
,
j
=
1,2
,
…
,
n
.μ
i
j can be calculated by the flowing formulation
(7)
μ
i
j
=
1
∑
k
=
1
6
d
i
j
/
d
k
j
2
/
(
b
-
1
)
,
d
i
j
>
0
,
1
,
d
i
j
=
0
,
i
=
j
,
0
,
d
i
j
=
0
,
i
≠
j
.Modification of the clustering centers and degrees of membership is the core of FCM. When the algorithm is convergent, clustering centersa
i can be found, and degrees of membership μ
i
j can be calculated. Therefore, fuzzy clustering result can be achieved.


## 3.2.2. SAGA-FCM Based Solution Algorithm

SAGA-FCM algorithm is used to improve the clustering quality of FCM. The process of SAGA-FCM algorithm can be summarized as in the following steps [28].Step 1 (parameters initialization). Population size (s
i
z
e
p
o
p), maximum genetic evolution algebra (M
A
X
G
E
N), crossing probability (P
c), gene variation probability (P
m), original temperature (T
0), cooling coefficient (l), and final temperature (T
end).Step 2 (clustering centers initialization). Randomly selecting six clustering centers (a), designing the original sequence (c
h
r
o
m), calculating degrees of membership (μ
i
j), and fitness value of each individual (f
i).Step 3 (genetic evolution algebra initialization). g
e
n
=
0.Step 4 (genetic operations). Selection, crossover, and mutation of original sequence (c
h
r
o
m), achieving new clustering centers (a), calculating degrees of membership (μ
i
j
′), and fitness value of each individual (f
i
′).Step 5 (fitness value judgment). If f
i
′
>
f
i, replace all of the old individual with the new individual; otherwise, replace the old individual with the new individual by probability (P
=
exp
⁡
f
i
-
f
i
′
T).Step 6 (M
A
X
G
E
N judgment). If g
e
n
<
M
A
X
G
E
N, g
e
n
=
g
e
n
+
1, turn to Step 4; otherwise, turn to Step 7.Step 7 (temperature judgment). If T
i
<
T
end, the new solution is outputted, and that is the most optimized assembly sequence; otherwise, T
i
+
1
=
l
T
i, turning to Step 3.


## 3.2.3. Calculation of LOS

Based on SAGA-FCM algorithm, six clustering centers (a) can be found. Thus, μ
i
j is calculated by formulation 7. Combining the numerical magnitude of μ
i
j, the LOS of x
j
A
x
j is achieved:
(8)
A
x
j
=
A
k
s
.
t
.
μ
k
j
>
μ
i
j
,
k
≠
i
,
where A
x
j is the LOS of x
j.


## 3.3. DFT Based Historical Data Fusion Model

Given a discrete temporal seriesx
0
,
x
1
,
…
,
x
N
-
1, the length of which is N, its discrete Fourier transform with M sampling points can be calculated:
(9)
X
k
=
1
N
×
∑
n
=
0
N
-
1
x
n
×
e
-
j
(
2
k
π
/
N
)
n
,
k
=
0,1
,
…
,
M
-
1
.The corresponding inverse Fourier transform formulation is(10)
x
n
=
∑
k
=
0
M
-
1
X
k
×
e
j
(
2
k
π
/
N
)
n
,
k
=
0,1
,
…
,
M
-
1
.Normally, takeM
=
N. To facilitate the program, the natural logarithm complex power form above is converted to trigonometric form:
(11)
x
i
=
a
0
+
∑
f
=
1
N
-
1
α
n
cos
⁡
2
π
N
f
i
+
β
n
sin
2
π
N
f
i
v
v
v
v
v
v
v
v
v
v
×
f
i
=
e
j
2
k
π
/
N
i
i
=
0,1
,
…
,
N
-
1
.Suppose that the traffic flow varies in one week cycle, which includes 7 days with different characteristics. Each day contains 288 pieces of data with a time interval of 5 minutes. Apply DFT to average massive historical data and to eliminate noise, so as to achieve the integration of historical data. Consider(12)
V
D
H
=
V
D
,
1
H
,
…
,
V
D
,
t
H
,
…
,
V
D
,
288
H
,
where V
D
H is the collection of historical data on day D, D
=
1,2
,
…
,
7. V
D
,
t
H is the traffic data on day D at time t, V
D
,
t
H
=
q
D
,
t
H
,
v
D
,
t
H
,
ρ
D
,
t
H
T, t
=
1,2
,
…
,
288.For example, the process of DFT of traffic volume(
q
) can be summarized as in the following steps.Step 1. Enter the discrete temporal series q
0
,
q
1
,
…
,
q
287.Step 2. Apply DFT and acquire Fourier coefficients sequence α
1
,
β
1
,
α
2
,
β
2
,
…
,
α
287
,
β
287.Step 3. Filter Fourier coefficients series to excise all coefficients less than the specified amplitude threshold of coefficient. Record the rest of the coefficients. The value of the threshold needs to be chosen by analyzing the historical data.Step 4. Restore data at any point in the sequence q
i.


## 3.4. Regional Traffic Flow Correlation Model

### 3.4.1. Basic Model Formulation

The basic assumption of the regional traffic flow correlation model is that traffic flow has a strong temporal-spatial-historical correlation, namely:(i)
in the temporal series, the traffic flow of the last moment can be regarded as the continuation of the current traffic flow;
(ii)
in the spatial series, downstream sections of the traffic flow can be seen as a continuation of the upstream traffic flow;
(iii)
in the historical series, traffic demand characteristics determine that traffic flow characteristics of the same day in the same period are similar.Basic form of regional traffic flow correlation model is expressed as(13)
V
s
t
=
γ
T
V
T
t
+
γ
S
V
S
t
+
γ
H
V
H
t
s
.
t
.
γ
T
+
γ
S
+
γ
H
=
1
,
γ
T
,
γ
S
,
γ
H
≥
0
,
where V
s
t is the traffic flow parameter of section s at time t, representing flow q
s
t, speed v
s
t, or occupancy ρ
s
t. V
T
t, V
S
t, and V
H
t are the estimated value of V
s
t. V
T
t is calculated by temporal correlation analysis. V
S
t is calculated by spatial correlation analysis. V
H
t is calculated by historical correlation analysis. γ
T, γ
S, and γ
H are coefficients of these three variables.According to formulation1, T is generally achieved by regression analysis model. Thus, V
T
t is created by the following equation:
(14)
V
T
t
=
θ
1
V
s
t
-
1
+
θ
2
V
s
t
-
2
+
⋯
s
.
t
.
∑
θ
=
1
,
θ
≥
0
,
where V
s
t
-
d is the traffic flow parameter of section s at time t
-
d. d is time delay, d
≥
0. θ
1
,
θ
2
,
… are regression coefficients.According to formulation2, S is generally achieved by neighbor regression model. Thus, V
S
t is created by the following equation:
(15)
V
S
t
=
λ
1
V
1
t
-
1
+
λ
2
V
2
t
-
2
+
⋯
s
.
t
.
∑
λ
=
1
,
λ
≥
0
,
where V
j
t
-
d is the traffic flow parameter of section j at time t
-
d. λ
1
,
λ
2
,
… are regression coefficients.According to formulations12, 13, 14, and 15, simplified equation is achieved:
(16)
V
s
t
=
∑
∑
ω
j
d
V
j
t
-
d
s
.
t
.
∑
ω
=
1
,
ω
>
0
,
η
∈
N
*
,
where ω
j
d is regression coefficient of V
j
t
-
d. η is the number of ω
j
d.


### 3.4.2. Effectiveness Proof of Proposed Formulation

The general form of formula16 is
(17)
Y
=
∑
i
=
1
n
w
i
Y
i
s
.
t
.
∑
i
=
1
n
w
i
=
1
,
w
i
≥
0
,
where Y is the state of physical system with the measurement of multisensors. Y
i is the measured value of i
th sensor, and they are independent. w
i is a weighting factor.The total mean square errorδ
2 is a multivariate quadratic function of w
i:
(18)
δ
2
=
∑
i
=
1
n
w
i
2
δ
i
2
,
where δ
i is the mean square error of Y
i.According to extreme value theorem of multivariate quadratic function, weighting factor can be calculated as follows:(19)
w
i
=
1
δ
i
2
∑
i
=
1
n
1
/
δ
i
2
.Assume that the detection accuracy varies with sensors, the mean square error of the measurements from the least accurate sensor isδ
min
⁡
2 and that from the most accurate sensor is δ
max
⁡
2. Then,
(20)
esp
Y
=
1
δ
max
⁡
2
+
1
δ
min
⁡
2
+
∑
i
=
1
n
-
2
1
δ
i
2
-
1
<
1
δ
min
⁡
2
+
∑
i
=
1
n
-
2
1
δ
i
2
-
1
<
δ
min
⁡
2
.The formula above shows that the measurement accuracy of the system can be improved by multisensor measurement and that participation of an inaccurate sensor also helps improve the accuracy of the system.


### 3.4.3. Bilevel Optimization Model

For big date-driven analysis, the speed and accuracy of data processing are both important. The number of unknown parameters in formulation16 is large and uncontrolled. Therefore, taking simple calculation and predictive accuracy into consideration, a bilevel optimization model is proposed.The upper level model is formulated to optimize the speed of date processing by minimizing the number of temporal-spatial-historical correlation variables. The upper level formulation is(21)
min
⁡
η
s
.
t
.
η
∈
N
*
.The lower level model is articulated in accordance with predictive accuracy. Therefore, the lower level formulation is proposed in order to minimize predictive encoding. The lower level formulation is(22)
min
⁡
V
s
t
-
V
^
s
t
s
.
t
.
V
s
t
=
∑
∑
ω
j
d
V
j
t
-
d
,
∑
ω
=
1
,
ω
≥
0
,
where V
^
s
t is actual value of V
s
t.In the bilevel optimization model, the purpose of objective function is to achieve a best combination, which holds both fast calculation speed and high prediction accuracy.


## 3.4.1. Basic Model Formulation

The basic assumption of the regional traffic flow correlation model is that traffic flow has a strong temporal-spatial-historical correlation, namely:(i)
in the temporal series, the traffic flow of the last moment can be regarded as the continuation of the current traffic flow;
(ii)
in the spatial series, downstream sections of the traffic flow can be seen as a continuation of the upstream traffic flow;
(iii)
in the historical series, traffic demand characteristics determine that traffic flow characteristics of the same day in the same period are similar.Basic form of regional traffic flow correlation model is expressed as(13)
V
s
t
=
γ
T
V
T
t
+
γ
S
V
S
t
+
γ
H
V
H
t
s
.
t
.
γ
T
+
γ
S
+
γ
H
=
1
,
γ
T
,
γ
S
,
γ
H
≥
0
,
where V
s
t is the traffic flow parameter of section s at time t, representing flow q
s
t, speed v
s
t, or occupancy ρ
s
t. V
T
t, V
S
t, and V
H
t are the estimated value of V
s
t. V
T
t is calculated by temporal correlation analysis. V
S
t is calculated by spatial correlation analysis. V
H
t is calculated by historical correlation analysis. γ
T, γ
S, and γ
H are coefficients of these three variables.According to formulation1, T is generally achieved by regression analysis model. Thus, V
T
t is created by the following equation:
(14)
V
T
t
=
θ
1
V
s
t
-
1
+
θ
2
V
s
t
-
2
+
⋯
s
.
t
.
∑
θ
=
1
,
θ
≥
0
,
where V
s
t
-
d is the traffic flow parameter of section s at time t
-
d. d is time delay, d
≥
0. θ
1
,
θ
2
,
… are regression coefficients.According to formulation2, S is generally achieved by neighbor regression model. Thus, V
S
t is created by the following equation:
(15)
V
S
t
=
λ
1
V
1
t
-
1
+
λ
2
V
2
t
-
2
+
⋯
s
.
t
.
∑
λ
=
1
,
λ
≥
0
,
where V
j
t
-
d is the traffic flow parameter of section j at time t
-
d. λ
1
,
λ
2
,
… are regression coefficients.According to formulations12, 13, 14, and 15, simplified equation is achieved:
(16)
V
s
t
=
∑
∑
ω
j
d
V
j
t
-
d
s
.
t
.
∑
ω
=
1
,
ω
>
0
,
η
∈
N
*
,
where ω
j
d is regression coefficient of V
j
t
-
d. η is the number of ω
j
d.


## 3.4.2. Effectiveness Proof of Proposed Formulation

The general form of formula16 is
(17)
Y
=
∑
i
=
1
n
w
i
Y
i
s
.
t
.
∑
i
=
1
n
w
i
=
1
,
w
i
≥
0
,
where Y is the state of physical system with the measurement of multisensors. Y
i is the measured value of i
th sensor, and they are independent. w
i is a weighting factor.The total mean square errorδ
2 is a multivariate quadratic function of w
i:
(18)
δ
2
=
∑
i
=
1
n
w
i
2
δ
i
2
,
where δ
i is the mean square error of Y
i.According to extreme value theorem of multivariate quadratic function, weighting factor can be calculated as follows:(19)
w
i
=
1
δ
i
2
∑
i
=
1
n
1
/
δ
i
2
.Assume that the detection accuracy varies with sensors, the mean square error of the measurements from the least accurate sensor isδ
min
⁡
2 and that from the most accurate sensor is δ
max
⁡
2. Then,
(20)
esp
Y
=
1
δ
max
⁡
2
+
1
δ
min
⁡
2
+
∑
i
=
1
n
-
2
1
δ
i
2
-
1
<
1
δ
min
⁡
2
+
∑
i
=
1
n
-
2
1
δ
i
2
-
1
<
δ
min
⁡
2
.The formula above shows that the measurement accuracy of the system can be improved by multisensor measurement and that participation of an inaccurate sensor also helps improve the accuracy of the system.


## 3.4.3. Bilevel Optimization Model

For big date-driven analysis, the speed and accuracy of data processing are both important. The number of unknown parameters in formulation16 is large and uncontrolled. Therefore, taking simple calculation and predictive accuracy into consideration, a bilevel optimization model is proposed.The upper level model is formulated to optimize the speed of date processing by minimizing the number of temporal-spatial-historical correlation variables. The upper level formulation is(21)
min
⁡
η
s
.
t
.
η
∈
N
*
.The lower level model is articulated in accordance with predictive accuracy. Therefore, the lower level formulation is proposed in order to minimize predictive encoding. The lower level formulation is(22)
min
⁡
V
s
t
-
V
^
s
t
s
.
t
.
V
s
t
=
∑
∑
ω
j
d
V
j
t
-
d
,
∑
ω
=
1
,
ω
≥
0
,
where V
^
s
t is actual value of V
s
t.In the bilevel optimization model, the purpose of objective function is to achieve a best combination, which holds both fast calculation speed and high prediction accuracy.


## 3.5. Correction Coefficients Optimization Model

The more the temporal-spatial-historical correlation variables are, the slower the program calculates and the higher the accuracy is. The bilevel optimization model above is difficult to solve. To put it in another way, we can define a threshold of computing speed and therefore derive the maximum of acceptable number of temporal-spatial-historical correlation variables. In addition, we can put forward a new variable which can be calculated to replace the variableω
j
d. Since the alternative process will bring some errors, which are likely to be systematic, a linear correction method is put forward. Therefore, the correction coefficients optimization model is a two-stage model.


### 3.5.1. The First Stage Model

The first stage model is mainly used to determine the number of unknown parametersη. It can be determined through the following steps.Step 1 (determination of the range of η). The number of unknown parameters should not exceed a threshold value. After several data tests, it is found that when η is less than 4, the correlation coefficients are not very different from relatively high values; when η is more than 8, the rapid decay of the correlation coefficients is observed with relatively low values. Therefore η ranges from 4,8.Step 2 (calculation of the correlation coefficients). Calculate the correlation coefficients (r
j
d) between the studied section s and the related section j, solve the max correlation coefficient (r
j) corresponding to each section j, and determine the corresponding time delay (d); namely, r
j
=
max
⁡
r
j
d. r
j
d can be solved by
(23)
r
j
d
=
∑
t
=
1
n
-
d
V
s
(
t
)
V
j
(
t
-
d
)
-
1
n
-
d
∑
t
=
1
n
-
d
V
s
(
t
)
∑
t
=
1
n
-
d
V
j
(
t
-
d
)
×
∑
t
=
1
n
-
d
V
s
2
(
t
)
-
1
n
-
d
∑
t
=
1
n
-
d
V
s
t
2
×
∑
t
=
1
n
-
d
V
j
2
t
-
d
-
1
n
-
d
∑
t
=
1
n
-
d
V
j
t
-
d
2
-
1
/
2
s
.
t
d
≥
0
.
Step 3 (selection of the relative section). Sort r
j in ascending order, and take the first η section as a range of temporal and spatial correlation.


### 3.5.2. The Second Stage Model

The second stage model is mainly used to reduce parameters and determines the base model. Through the first stage model, the number of unknown parameters is reduced. But the model is still difficult to solve and can be further simplified.Step 1 (calculation of the normalization factor). Take normalized r
j as the parameters of V
j
t
-
d:
(24)
ω
j
=
r
j
∑
j
=
1
η
r
j
,
∑
j
=
1
η
ω
j
=
1
,
ω
j
>
0
.
Step 2 (solving the system error). Introduce the correction parameters φ and ε to calibrate, in order to reduce the system error caused by parameter substitution:
(25)
min
⁡
V
s
t
-
V
^
s
t
s
.
t
.
V
s
t
=
φ
∑
j
=
1
η
ω
j
V
j
t
-
d
+
ε
.


## 3.5.1. The First Stage Model

The first stage model is mainly used to determine the number of unknown parametersη. It can be determined through the following steps.Step 1 (determination of the range of η). The number of unknown parameters should not exceed a threshold value. After several data tests, it is found that when η is less than 4, the correlation coefficients are not very different from relatively high values; when η is more than 8, the rapid decay of the correlation coefficients is observed with relatively low values. Therefore η ranges from 4,8.Step 2 (calculation of the correlation coefficients). Calculate the correlation coefficients (r
j
d) between the studied section s and the related section j, solve the max correlation coefficient (r
j) corresponding to each section j, and determine the corresponding time delay (d); namely, r
j
=
max
⁡
r
j
d. r
j
d can be solved by
(23)
r
j
d
=
∑
t
=
1
n
-
d
V
s
(
t
)
V
j
(
t
-
d
)
-
1
n
-
d
∑
t
=
1
n
-
d
V
s
(
t
)
∑
t
=
1
n
-
d
V
j
(
t
-
d
)
×
∑
t
=
1
n
-
d
V
s
2
(
t
)
-
1
n
-
d
∑
t
=
1
n
-
d
V
s
t
2
×
∑
t
=
1
n
-
d
V
j
2
t
-
d
-
1
n
-
d
∑
t
=
1
n
-
d
V
j
t
-
d
2
-
1
/
2
s
.
t
d
≥
0
.
Step 3 (selection of the relative section). Sort r
j in ascending order, and take the first η section as a range of temporal and spatial correlation.


## 3.5.2. The Second Stage Model

The second stage model is mainly used to reduce parameters and determines the base model. Through the first stage model, the number of unknown parameters is reduced. But the model is still difficult to solve and can be further simplified.Step 1 (calculation of the normalization factor). Take normalized r
j as the parameters of V
j
t
-
d:
(24)
ω
j
=
r
j
∑
j
=
1
η
r
j
,
∑
j
=
1
η
ω
j
=
1
,
ω
j
>
0
.
Step 2 (solving the system error). Introduce the correction parameters φ and ε to calibrate, in order to reduce the system error caused by parameter substitution:
(25)
min
⁡
V
s
t
-
V
^
s
t
s
.
t
.
V
s
t
=
φ
∑
j
=
1
η
ω
j
V
j
t
-
d
+
ε
.


## 4. Case Study

### 4.1. Data Characteristics

Taking a section of the Second Ring Road (Section 1, as shown in Figure2) and its surrounding roads in Beijing, China, as the object of study, it verifies the effectiveness and feasibility of the proposed method. Basic traffic flow data are detected by microwave detectors.Figure 2
Spatial location of research object.As shown in Figure2, Section 1, Section 2, Section 3, and Section 9 are all Second Ring Road. Section 4 and Section 5 are Expressway Tie Line. Section 6, Section 7, Section 8, and Section 10 are Secondary Road. Section 2
,
3
,
…
,
10 are the temporal-spatial correlated sections of Section 1.For traffic flow state identification, it needs enough data to divide LOS. The historical data of Section 1 (one week, five minutes for the interval) are used to build SAGA-FCM based traffic clustering model. The amount of data is large enough to represent nearly all the traffic flow characteristics.For traffic flow prediction, it needs enough data to describe the temporal-spatial-historical correlation characteristic, that is, to build correction coefficients optimization model. The historical data of Section 1 (one week, five minutes for the interval) are used for temporal-spatial correlation analysis. The historical data of Section1
,
2
,
…
,
10 (one week, five minutes for the interval) are used for temporal-spatial-historical correlation analysis. The historical data of Section 1 (one month, five minutes for the interval) are used for historical correlation analysis.


### 4.2. Traffic Flow State Identification

#### 4.2.1. Offline Training

The main task of offline training is to establish the evaluation method of traffic flow state. Case study of traffic flow state identification is done based on the two clustering methods (FCM and SAGA-FCM). The value of objective function calculated by SAGA-FCM is better than the one by FCM. Different traffic flow states are respected by different colors. As shown in Figure3, traffic flow state is divided into six levels, as A to F. Clustering centers are shown in Table 1.Table 1
Clustering centers.
LOS
Speed (km/h)
Occupancy (%)
A
68.1
2.1
B
58.3
3.1
C
51.2
11.4
D
46.0
14.9
E
38.0
20.5
F
23.4
35.1Figure 3
Traffic flow state evaluation result.


#### 4.2.2. Online Application

The main task of online application is to realize traffic flow state identification. Traffic flow state identification result is shown in Figure4.Figure 4
Traffic flow state identification.


### 4.3. Traffic Flow State Prediction

#### 4.3.1. Offline Training

The offline training mainly summarizes the prior knowledge based on historical data.(1) Parameter Initialization. Choose 9 of the upstream and downstream sections of Section 1 based on their attributes and transport network characteristics. Let η
∈
4
,
8.(2) Search of Temporal-Spatial-Historical Correlative Sections. Calculate the correlation coefficient between Section 1 and its relative sections, time series data, and historical trend data. The top 6 of the calculation result are shown in Figure 5, where the abscissa is the time delay d and the vertical axis is the value of the correlation coefficient r
j
d.Figure 5
Temporal-spatial-historical correlation analysis based speed.
(a)
Section 9
(b)
Section 1 (time series data)
(c)
Section 1 (historical trend data)
(d)
Section 2
(e)
Section 6
(f)
Section 4Comparer
j
d, decide the value of corresponding d, and then get r
j. According to the distribution characteristics of r
j, let η
=
4. The search results of temporal-spatial-historical correlative sections are Section 9, Section 1 (time series data), Section 1 (historical trend data), and Section 2.Results of temporal-spatial-historical correlation coefficients are shown in Table2.Table 2
Temporal-spatial-historical correlation coefficients.
j
d (min)
r
j
d
ω
j
9
0
0.9970
0.2677
1 (temporal correlation)
5
0.9797
0.2630
1 (historical correlation)
0
0.9167
0.2461
2
0
0.8312
0.2232(3) Calculation of Normalization Parameter. Calculate the normalization parameters ω
j, as shown in Table 2.(4) Solving Correction Parameters. Apply regression analysis to solve correction parameters φ and ε:
(26)
v
1
t
=
1.029
×
v
1
H
t
0.2677
·
v
9
t
+
0.2630
·
v
1
t
-
5
vvvvvvvvv
+
0.2461
·
v
1
H
t
+
0.2232
·
v
2
t
+
1.8173
,
where v
j
t is the velocity of section j at time t and v
1
H
t is the historical relative data of Section 1.Apply the same method to analyze flow and occupancy:(27)
q
1
t
=
1.0629
×
0.2246
·
q
9
t
+
0.2151
·
q
1
t
-
5
vvvvvvvvvvvvvvv
+
0.2145
·
q
1
H
t
-
5
+
0.1787
·
q
2
t
vvvvvvvvvvvvvvv
+
0.1670
·
q
6
t
-
10
+
22.652
,
(28)
ρ
1
t
=
1.0148
×
ρ
1
H
t
0.2791
·
ρ
9
t
+
0.2747
·
ρ
1
t
-
5
vvvvvvvvvvvvvvv
+
0.2294
·
ρ
2
t
+
0.2168
·
ρ
1
H
t
vvvvvv
+
0.4793
,
where q
j
t is the flow of Section j at time t, q
1
H
t is the historical relative data of Section 1, ρ
j
t is the occupancy of Section j at time t, and ρ
1
H
t is the historical relative data of Section 1.Fitting curve is shown in Figure6.Figure 6
Fitting curve.
(a)
Speed(
R
2
=
0.9655
)
(b)
Flow(
R
2
=
0.8885
)
(c)
Occupancy(
R
2
=
0.9664
)


#### 4.3.2. Online Application

Online calculations mainly deal with real-time data based on prior knowledge. Figure7 shows the predicted results. The prediction errors of speed, flow, and occupancy are controlled around 10%. Traffic state deviation is shown in Table 3. Two-level-deviation and Three-level-deviation are considered as errors, which are controlled in 10%.Table 3
Comparative analysis.
Deviation
Non-level-deviation
One-level-deviation
Two-level-deviation
Three-level-deviation
Accuracy
75.37%
15.80%
8.46%
0.37%Figure 7
Modification effective analysis.


## 4.1. Data Characteristics

Taking a section of the Second Ring Road (Section 1, as shown in Figure2) and its surrounding roads in Beijing, China, as the object of study, it verifies the effectiveness and feasibility of the proposed method. Basic traffic flow data are detected by microwave detectors.Figure 2
Spatial location of research object.As shown in Figure2, Section 1, Section 2, Section 3, and Section 9 are all Second Ring Road. Section 4 and Section 5 are Expressway Tie Line. Section 6, Section 7, Section 8, and Section 10 are Secondary Road. Section 2
,
3
,
…
,
10 are the temporal-spatial correlated sections of Section 1.For traffic flow state identification, it needs enough data to divide LOS. The historical data of Section 1 (one week, five minutes for the interval) are used to build SAGA-FCM based traffic clustering model. The amount of data is large enough to represent nearly all the traffic flow characteristics.For traffic flow prediction, it needs enough data to describe the temporal-spatial-historical correlation characteristic, that is, to build correction coefficients optimization model. The historical data of Section 1 (one week, five minutes for the interval) are used for temporal-spatial correlation analysis. The historical data of Section1
,
2
,
…
,
10 (one week, five minutes for the interval) are used for temporal-spatial-historical correlation analysis. The historical data of Section 1 (one month, five minutes for the interval) are used for historical correlation analysis.


## 4.2. Traffic Flow State Identification

### 4.2.1. Offline Training

The main task of offline training is to establish the evaluation method of traffic flow state. Case study of traffic flow state identification is done based on the two clustering methods (FCM and SAGA-FCM). The value of objective function calculated by SAGA-FCM is better than the one by FCM. Different traffic flow states are respected by different colors. As shown in Figure3, traffic flow state is divided into six levels, as A to F. Clustering centers are shown in Table 1.Table 1
Clustering centers.
LOS
Speed (km/h)
Occupancy (%)
A
68.1
2.1
B
58.3
3.1
C
51.2
11.4
D
46.0
14.9
E
38.0
20.5
F
23.4
35.1Figure 3
Traffic flow state evaluation result.


### 4.2.2. Online Application

The main task of online application is to realize traffic flow state identification. Traffic flow state identification result is shown in Figure4.Figure 4
Traffic flow state identification.


## 4.2.1. Offline Training

The main task of offline training is to establish the evaluation method of traffic flow state. Case study of traffic flow state identification is done based on the two clustering methods (FCM and SAGA-FCM). The value of objective function calculated by SAGA-FCM is better than the one by FCM. Different traffic flow states are respected by different colors. As shown in Figure3, traffic flow state is divided into six levels, as A to F. Clustering centers are shown in Table 1.Table 1
Clustering centers.
LOS
Speed (km/h)
Occupancy (%)
A
68.1
2.1
B
58.3
3.1
C
51.2
11.4
D
46.0
14.9
E
38.0
20.5
F
23.4
35.1Figure 3
Traffic flow state evaluation result.


## 4.2.2. Online Application

The main task of online application is to realize traffic flow state identification. Traffic flow state identification result is shown in Figure4.Figure 4
Traffic flow state identification.


## 4.3. Traffic Flow State Prediction

### 4.3.1. Offline Training

The offline training mainly summarizes the prior knowledge based on historical data.(1) Parameter Initialization. Choose 9 of the upstream and downstream sections of Section 1 based on their attributes and transport network characteristics. Let η
∈
4
,
8.(2) Search of Temporal-Spatial-Historical Correlative Sections. Calculate the correlation coefficient between Section 1 and its relative sections, time series data, and historical trend data. The top 6 of the calculation result are shown in Figure 5, where the abscissa is the time delay d and the vertical axis is the value of the correlation coefficient r
j
d.Figure 5
Temporal-spatial-historical correlation analysis based speed.
(a)
Section 9
(b)
Section 1 (time series data)
(c)
Section 1 (historical trend data)
(d)
Section 2
(e)
Section 6
(f)
Section 4Comparer
j
d, decide the value of corresponding d, and then get r
j. According to the distribution characteristics of r
j, let η
=
4. The search results of temporal-spatial-historical correlative sections are Section 9, Section 1 (time series data), Section 1 (historical trend data), and Section 2.Results of temporal-spatial-historical correlation coefficients are shown in Table2.Table 2
Temporal-spatial-historical correlation coefficients.
j
d (min)
r
j
d
ω
j
9
0
0.9970
0.2677
1 (temporal correlation)
5
0.9797
0.2630
1 (historical correlation)
0
0.9167
0.2461
2
0
0.8312
0.2232(3) Calculation of Normalization Parameter. Calculate the normalization parameters ω
j, as shown in Table 2.(4) Solving Correction Parameters. Apply regression analysis to solve correction parameters φ and ε:
(26)
v
1
t
=
1.029
×
v
1
H
t
0.2677
·
v
9
t
+
0.2630
·
v
1
t
-
5
vvvvvvvvv
+
0.2461
·
v
1
H
t
+
0.2232
·
v
2
t
+
1.8173
,
where v
j
t is the velocity of section j at time t and v
1
H
t is the historical relative data of Section 1.Apply the same method to analyze flow and occupancy:(27)
q
1
t
=
1.0629
×
0.2246
·
q
9
t
+
0.2151
·
q
1
t
-
5
vvvvvvvvvvvvvvv
+
0.2145
·
q
1
H
t
-
5
+
0.1787
·
q
2
t
vvvvvvvvvvvvvvv
+
0.1670
·
q
6
t
-
10
+
22.652
,
(28)
ρ
1
t
=
1.0148
×
ρ
1
H
t
0.2791
·
ρ
9
t
+
0.2747
·
ρ
1
t
-
5
vvvvvvvvvvvvvvv
+
0.2294
·
ρ
2
t
+
0.2168
·
ρ
1
H
t
vvvvvv
+
0.4793
,
where q
j
t is the flow of Section j at time t, q
1
H
t is the historical relative data of Section 1, ρ
j
t is the occupancy of Section j at time t, and ρ
1
H
t is the historical relative data of Section 1.Fitting curve is shown in Figure6.Figure 6
Fitting curve.
(a)
Speed(
R
2
=
0.9655
)
(b)
Flow(
R
2
=
0.8885
)
(c)
Occupancy(
R
2
=
0.9664
)


### 4.3.2. Online Application

Online calculations mainly deal with real-time data based on prior knowledge. Figure7 shows the predicted results. The prediction errors of speed, flow, and occupancy are controlled around 10%. Traffic state deviation is shown in Table 3. Two-level-deviation and Three-level-deviation are considered as errors, which are controlled in 10%.Table 3
Comparative analysis.
Deviation
Non-level-deviation
One-level-deviation
Two-level-deviation
Three-level-deviation
Accuracy
75.37%
15.80%
8.46%
0.37%Figure 7
Modification effective analysis.


## 4.3.1. Offline Training

The offline training mainly summarizes the prior knowledge based on historical data.(1) Parameter Initialization. Choose 9 of the upstream and downstream sections of Section 1 based on their attributes and transport network characteristics. Let η
∈
4
,
8.(2) Search of Temporal-Spatial-Historical Correlative Sections. Calculate the correlation coefficient between Section 1 and its relative sections, time series data, and historical trend data. The top 6 of the calculation result are shown in Figure 5, where the abscissa is the time delay d and the vertical axis is the value of the correlation coefficient r
j
d.Figure 5
Temporal-spatial-historical correlation analysis based speed.
(a)
Section 9
(b)
Section 1 (time series data)
(c)
Section 1 (historical trend data)
(d)
Section 2
(e)
Section 6
(f)
Section 4Comparer
j
d, decide the value of corresponding d, and then get r
j. According to the distribution characteristics of r
j, let η
=
4. The search results of temporal-spatial-historical correlative sections are Section 9, Section 1 (time series data), Section 1 (historical trend data), and Section 2.Results of temporal-spatial-historical correlation coefficients are shown in Table2.Table 2
Temporal-spatial-historical correlation coefficients.
j
d (min)
r
j
d
ω
j
9
0
0.9970
0.2677
1 (temporal correlation)
5
0.9797
0.2630
1 (historical correlation)
0
0.9167
0.2461
2
0
0.8312
0.2232(3) Calculation of Normalization Parameter. Calculate the normalization parameters ω
j, as shown in Table 2.(4) Solving Correction Parameters. Apply regression analysis to solve correction parameters φ and ε:
(26)
v
1
t
=
1.029
×
v
1
H
t
0.2677
·
v
9
t
+
0.2630
·
v
1
t
-
5
vvvvvvvvv
+
0.2461
·
v
1
H
t
+
0.2232
·
v
2
t
+
1.8173
,
where v
j
t is the velocity of section j at time t and v
1
H
t is the historical relative data of Section 1.Apply the same method to analyze flow and occupancy:(27)
q
1
t
=
1.0629
×
0.2246
·
q
9
t
+
0.2151
·
q
1
t
-
5
vvvvvvvvvvvvvvv
+
0.2145
·
q
1
H
t
-
5
+
0.1787
·
q
2
t
vvvvvvvvvvvvvvv
+
0.1670
·
q
6
t
-
10
+
22.652
,
(28)
ρ
1
t
=
1.0148
×
ρ
1
H
t
0.2791
·
ρ
9
t
+
0.2747
·
ρ
1
t
-
5
vvvvvvvvvvvvvvv
+
0.2294
·
ρ
2
t
+
0.2168
·
ρ
1
H
t
vvvvvv
+
0.4793
,
where q
j
t is the flow of Section j at time t, q
1
H
t is the historical relative data of Section 1, ρ
j
t is the occupancy of Section j at time t, and ρ
1
H
t is the historical relative data of Section 1.Fitting curve is shown in Figure6.Figure 6
Fitting curve.
(a)
Speed(
R
2
=
0.9655
)
(b)
Flow(
R
2
=
0.8885
)
(c)
Occupancy(
R
2
=
0.9664
)


## 4.3.2. Online Application

Online calculations mainly deal with real-time data based on prior knowledge. Figure7 shows the predicted results. The prediction errors of speed, flow, and occupancy are controlled around 10%. Traffic state deviation is shown in Table 3. Two-level-deviation and Three-level-deviation are considered as errors, which are controlled in 10%.Table 3
Comparative analysis.
Deviation
Non-level-deviation
One-level-deviation
Two-level-deviation
Three-level-deviation
Accuracy
75.37%
15.80%
8.46%
0.37%Figure 7
Modification effective analysis.


## 5. Conclusions

In the era of big data, real-time traffic flow state identification, and prediction may face many challenges. This difficulty is decided by the characteristics of big data. This paper uses speed and occupancy to build the traffic flow state clustering model. And real-time traffic flow state identification is based on speed and occupancy. Traditional fuzzyc-mean clustering does not meet the requirements of big data analysis. To improve the feasibility of traffic flow state clustering, this paper uses the simulated annealing genetic algorithm based fuzzy c-means (SAGA-FCM). Case study shows that the value of objective function calculated based on SAGA-FCM is better.Traffic flow big data strongly shows temporal, spatial, and historical correlations. The regional traffic flow correlation model is established for real-time traffic flow prediction. The characteristics of big data make it difficult to resolve the model. In order to reduce parameters and ensure calculation speed and calculation accuracy, the correction coefficients optimization model, which can be divided into two stages, is put forward. Effectiveness of the method has been validated by the case study.The core of this paper is to present a traffic temporal-spatial-historical correlation model, which comprehensively considers the temporal, spatial, and historical correlations of traffic flow big data. Compared with the model based on a single nature, the accuracy of proposed model is relatively high. Besides, this model quantitatively solves, from the perspective of spatiotemporal correlation analysis, the weight selection problem of different analytical methods in the traditional combined model. The traffic temporal-spatial-historical correlation model can be applied in other researches such as identification and correction of abnormal data and traffic congestion mechanism analysis.



---

*Source: 284906-2015-08-03.xml*