City traffic flow breakdown prediction based on fuzzy rough set

1 Introduction

Intelligent transportation plays a key role in modern life, and it is closely linked to people’s daily life. From 1960s, with the rapid growth of the world economy, the requirements of fast, convenient and safe transportation have been proposed [1, 2]. Particularly, computer technology and electronic industry greatly promote the development of modern traffic. Furthermore, how to effectively manage city traffic flow is of great importance for city development [3].

With the development of economy, the number of vehicles is increasing rapidly. Therefore, we observe that there are many serious traffic problems in modern city traffic management, such as traffic congestion, environmental deterioration, and frequent traffic accidents. These problems should be paid more attention by all countries in the world [4]. Although some measures can made to solve traffic problem, such as building and expanding highway, city traffic efficiency is not satisfied by us. Under this background, people aim to solve the city traffic problem by fully utilizing all types of road and vehicle factors and computer and network technique. Then, the concept of intelligent transportation system is proposed. Currently, intelligent transportation does not have a standard definition, which contains many aspects, such as traffic specifications, traffic design, traffic management, traffic operation, and so on [5]. Generally speaking, intelligent transportation is a kind of effective operation management for city traffic.

In order to identify the current and future state of traffic flow in time and accurately and analyze the state of the road traffic flow, it is very crucial to establish the correct guidance and control measures in advance. Traffic flow breakdown refers to the case that several parameters in the model of traffic flow suddenly change. Such changes are often associated with traffic events, and reflect the features of traffic accidents. When traffic accidents or traffic jams occur, anomalous traffic flow will appear at the downstream or upstream of accident site. That is, vehicle speed in the upstream decreases due to traffic congestion, on the other hand, vehicle speed in the downstream increases due to traffic sparsity. Furthermore, we also can observe that the number of vehicles reduce in the lane where accident occurs, on the contrary, vehicles in its adjacent lanes may increase. The above qualitative analysis shows that when the traffic flow state occurs, the location of a certain time (or space) can be regarded as an interface. The traffic flow parameters are different at various sides of the interface. Utilizing this idea and analysis, many researchers have presented many traffic flow identification algorithms.

Main innovations of this paper lie in the following aspects:

1. We introduce three definitions to describe city traffic flow more accurately.

2. We propose an attribute reduction algorithm based on a fuzzy rough set, and then delete redundant and irrelevant attributes to construct the feature vector.

The rest of the paper is organized as follows. We explain the related works about traffic flow breakdown in section 2. In Section 3, we explain the city traffic flow breakdown problem. Section 4 illustrates the attribute reduction method based on a fuzzy rough set. In section 5, we present a novel city traffic flow breakdown prediction algorithm based on SVM. To testify the effectiveness of the proposed method, experiments are conducted to prove the effectiveness of our method in section 6. Finally, section 7 concludes the whole paper.

2 Related works

Traffic breakdown prediction is very crucial issue in city traffic systems, and traffic flow breakdown is usually defined as an amount of sudden drop in traffic flow speed if traffic requirements exceed capacity. In the following, we will discuss related works about traffic flow breakdown and its prediction.

Boris et al. analyzed the real field traffic data measured in 1996-2014 through road detectors installed on German freeways, and then reveal that physical features of empirical nuclei for spontaneous traffic breakdown in free flow at highway bottlenecks. Particularly, the authors proposed a microscopic stochastic three steps traffic model of the nucleation of spontaneous traffic breakdown. Experimental results of this paper demonstrated that in the most cases a nucleus for the breakdown happens through an interaction in free flow with an empirical permanent speed disturbance which occurred at a highway bottleneck [6].

Boris et al. found that a growing local speed wave of increase in speed that is able to randomly happen in synchronized flow (denoted as S) at a highway bottleneck. On the other hand, the development of such traffic flow instability leads to free flow (denoted as F) at the bottleneck. Finally, this paper concluded that the SF instability is able to happen when there is a finite time delay in driver over-acceleration [7].

Xu et al. presented a new evolution model of speed perturbations for quantifying the probability of the traffic flow breakdown on congested freeway flow. The proposed method can effectively control city traffic flow under different time headways, driver behaviors, and state transitions. Particularly, in this paper, two types of drivers, (including 1) adventurers and 2) conservatives), and two kinds of reacting behavior, that is copy and shift are used to describe driving behavior in this model [8].

Sun et al. analyzed that the main reasons about urban expressway congestion are the traffic flow breakdowns at bottlenecks. To obtain the probabilistic characteristics of breakdown at urban expressway, a novel city traffic breakdown analysis model is presented proposed based on a large scale of detector data. The main innovation of this paper lies in that breakdowns are identified in terms of speed and density thresholds [9].

Boris et al. proposed a generic physical feature of the three-phase models based on simulations with cellular automaton (denoted as CA) traffic flow models. In this work, the generic feature refers to a discontinuous character of driver over-acceleration which is inferred by an integration of two qualitatively different mechanisms of over-acceleration [10].

Dong et al. proposed a new model to produce random flow breakdowns on congested freeways and then obtain subsequent wave propagation among heterogeneous drivers. This research aimed to forecast travel time variability. Particularly, this work supposed that breakdown may possibly occur at various traffic flow levels with some probability and may sustain for a specific time duration [11].

Shiomi et al. analyzed the mechanism of city traffic breakdown and then constructed a traffic flow model to simulate the stochastic and dynamic processes of traffic flow at a bottleneck. In this work, the authors proposed two models of stochastic processes according to traffic flow dynamics [12].

Afonso et al. aimed to forecast the traffic behavior and then obtain effectiveness and productivity on the physical distribution. Particularly, this work proposed a novel algorithm to forecast the traffic behavior in a metropolitan area based on Artificial Neural Network. In particular, the proposed method utilizes Rough-Fuzzy Sets to define inference morphology for insertion of the behavior of Dynamic Routing in a structured rule basis. In this work, rough sets theory can distinguish the weight of attribute, and then choose which fuzzy relation to be added to the Rough Neuro Fuzzy Network type Multilayer Perceptron and type Radial Basis Function [13].

Wang et al. regarded the city traffic breakdown as a random event, and utilized discrete time Markov chain to describe traffic state transition path. Furthermore, the transition probability matrix is gained from empirical observations. In this work, the traffic flow breakdown probability is represented as the number of vehicles which are existed in a given freeway segment [14].

Inspired by the above works, in this paper, we introduce the fuzzy rough set theory to solve the task of attribute reduction, and then utilize SVM classifier to forecast city traffic flow breakdown.

3 Description of the city traffic flow breakdown problem

In the area of intelligent transportation, traffic flow breakdown is defined as the speed decrease over a period of time. In particular, the definition of the traffic flow breakdown refers to the absolute amount of vehicle speed decrease. Afterwards, three definitions are given as follows.

4 Attribute reduction based on fuzzy rough set

Rough set theory (denoted RST) was firstly proposed by Pawlak in 1982 as a powerful tool for data analysis through concept approximation. In the rough set theory, lower and upper approximations of concepts are established based on an indiscernibility relation. Particularly, objects which are contained in the lower approximation can be classified with a given degree. In the last three decades, RST has been attracted many researchers in many various fields. Such as Multi-source alert data understanding [15], vertex cover problem [16], Self-adaptive Extreme Learning Machine [17], Group multi-criteria design concept evaluation [18], Thyroid disease diagnosis [19], Road Safety Indicator Analysis [20], Low carbon technology integration innovation assessment [21], Outlier detection [22], Integrating agricultural sustainability into policy planning [23].

However, numerical attributes and hybrid attributes may both be used in practice. In order to tackle this issue, two feasible solutions are used. The first method is to transform numerical and hybrid attributes to categorical attributes by discretization, however, this approach can result in the information loss of original data. The second method is to process numerical or hybrid data by the fuzzy rough set [24, 25]. As is well known that fuzzy rough sets encapsulate the related but distinct concepts of vagueness and indiscernibility [26-28].

In the rough set theory, an information system is defined as (X,A), where X = {x₁,x₂,···,x_n} and A = {a₁, a₂,··· , a_m} are two sets of objects and attributes respectively. For the set A, each element in it is corresponding to a mapping function ã: X → V_a, where V_a refers to the value set of element a on X. For each subset B (B∈A), the following equivalence relation is defined as follows.

Suppose that A ⊆ X, and the lower and upper approximations are obtained as follows.

In the fuzzy rough set model, a universe of objects U⊆ {x₁, x₂,…, x_n} is represented as a fuzzy binary relation (denoted as R̃), and the membership of x _i in a fuzzy rough set (denoted as R_~x,R~¯x) is defined as follows.

where X ∈ 𝕽(U) is satisfied, where 𝕽(U) denotes the class of all fuzzy sets in U, and U refers to the discoursed universe.

In the city flow breakdown prediction problem, there are many redundant and irrelevant attributes, and these attributes may bring adverse effects to breakdown prediction. As attribute reduction process based on fuzzy rough sets is able to prune the irrelevant attributes, in this section, we propose an attribute reduction method based on a fuzzy rough set.

For a fuzzy decision table U,A⋃D, where B⊆A, then the fuzzy positive region of D is defined as follows.

Based the above analysis, attribute reduction based on fuzzy rough set is defined as follows.

5 The proposed city traffic flow breakdown prediction algorithm

In this section, we will illustrate the city traffic flow breakdown prediction algorithm based on the above attribute reduction process. After attribute reduction, more irrelevant features are preserved to construct feature vectors. Then, the flow chart of city traffic flow breakdown prediction based on SVM classifier is given in Figure 1.

Figure 1

Flow chart of city traffic flow breakdown prediction based on SVM classifier

As is shown in Figure 1, the key module of the proposed city traffic flow breakdown prediction is the classification process. We regard the city traffic flow breakdown prediction problem as a classification problem.

Suppose that the training samples are defined as (x_i,y_i), and i ∈ {1, 2,…, l},i ∈ {1, 2, · · · , l}, x_i ∈ Rⁿ, y_i ∈ {1-1} are satisfied. Then, SVM classifier solves the breakdown prediction problem by optimizing the following equation [29,30].

where x_i is mapped to a high dimensional space, and β refers to a penalty parameter.

Afterwards, the classification problem is solved using the following equation [31-33].

In Figure 1, we know that performance of SVM classifier greatly relies on the kernel function selection process.

In this work, we exploit the Gaussian kernel, which is described as follows.

6 Experiment

To testify the effectiveness of the proposed algorithm, in this section, we design a series of experiments and analyze the experimental results.

6.2 Experimental results and analysis

The above 16 types of occurrences occurred in the freeway are utilized to test the performance of our proposed algorithm. Figure 2 shows the relationship between traffic flow rate and density observed before and after city traffic breakdown occurring. Particularly, triangle and star denote the traffic conditions before and after breakdown respectively.

Figure 2

Traffic flow and density scatter plots

From Figure 2, we can see that the scattering of observations demonstrates that traffic flow breakdown happens at different flow rates. When traffic breakdown occurs, congested traffic states are affected by various traffic speeds, flows, and densities.

Considering the traffic breakdown speed and duration may significantly influence a specific breakdown event, we illustrate distribution of traffic flow breakdown speed and duration in Figure 3 and Figure 4, respectively.

Figure 3

Distribution of traffic flow breakdown speed

Figure 4

Distribution of traffic flow breakdown duration

The traffic flow breakdown speed can be utilized to normalize a left truncated normal distribution function. The distribution of traffic flow breakdown speed can be extracted from travel time reliability mining.

Just like the breakdown speed, the breakdown duration data can be exploited to normalize the hazard function to represent the probability of a specific breakdown occurs at a particular time.

Next, we show the city traffic flow breakdown prediction results in four days (denoted as {Day1, Day2, Day3, Day4}), and traffic breakdown rate is sampled for each 30 minutes for 6 h to 22 h. The related experimental results are shown in Figure 5 to Figure 8.

Figure 5

City traffic flow breakdown prediction result for Day 1

Figure 6

City traffic flow breakdown prediction result for Day 2

Figure 7

City traffic flow breakdown prediction result for Day 3

Figure 8

City traffic flow breakdown prediction result for Day 4

Integrating experimental data from Figure 5 to Figure 8, it can be observed that most occurrences of traffic flow breakdown occur in the evening rush hours. On the other hand, we also find that compared with the actual observed value (ground truth), our proposed algorithm predicts city traffic flow more accurately than the method without attribute reduction. Afterwards, average error rates of city traffic flow breakdown prediction for different methods are given in Table 2.

Table 2

Average error rate of city traffic flow breakdown prediction (%)

Method	Day 1	Day 2	Day 3	Day 4
Without attribute reduction	10.57	11.1	9.49	9.03
The proposed algorithm	2.86	2.48	3.49	2.99

Table 2 shows average error rates of city traffic flow breakdown prediction for out algorithm and the policy without attribute reduction are 2.96% and 10.05% respectively. We can see that our proposed algorithm can effectively promote the average error rate of city traffic flow breakdown prediction. The reasons lie in that 1) the proposed method converts the traffic flow breakdown prediction problem to a classification, 2) we utilize the attribute reduction to delete irrelevant or unimportant knowledge, and then classification accuracy can be promote significantly.

7 Conclusion

This paper proposes an effective city traffic flow breakdown prediction based on a fuzzy rough set. To promote the accuracy of city traffic flow breakdown prediction, we propose an attribute reduction algorithm utilizing the fuzzy rough set theory. Afterwards, we predict the city traffic flow breakdown by integrating the attribute reduction process and SVM classifier together. In the experiment, we set the minimum time interval to eliminate the negative influence of traffic flow abnormal fluctuation. Experimental results show that our proposed algorithm performs better than the method without attribute reduction.

In the future, we will try to test the performance of our proposed methods in various traffic scenes, such as pedestrian, bicycle, motor vehicle, and we will also try to optimize parameters of SVM classifier to enhance the accuracy of classification.