CN113553350A

CN113553350A - Traffic flow partition model for similar evolution mode clustering and dynamic time zone partitioning

Info

Publication number: CN113553350A
Application number: CN202110587211.XA
Authority: CN
Inventors: 王知远; 陈良银; 陈彦如; 廖俊华; 刘畅; 刘诗佳; 何皓宇; 盘昊; 吴迪智; 袁道华
Original assignee: Sichuan University
Current assignee: Sichuan University
Priority date: 2021-05-27
Filing date: 2021-05-27
Publication date: 2021-10-26
Anticipated expiration: 2041-05-27
Also published as: CN113553350B

Abstract

The invention provides a traffic flow time sequence partition model based on similar evolution mode clustering and dynamic time zone partitioning, which tries to mine the dynamic space-time characteristics of traffic flow changing along with time for the first time and solves the challenge of traffic flow time instability in short-time traffic flow prediction. The specific work comprises the following steps: first, using affinity propagation clustering Algorithm (APC), automatically identifying road sections with similar traffic flow evolution mode in the road network. And secondly, aiming at the intra-day evolution difference of the traffic flow, carrying out dynamic time zone division on the traffic flow in the similar evolution mode by using a curve K-Means algorithm, and further excavating the space-time state characteristics of the traffic flow of the road network. Then after similar mode identification and automatic time zone division, traffic flows in different time zones in different modes are respectively modeled, and state information of the traffic flows is quantized, so that the prediction precision of the model is more accurate. And finally, verifying the validity of the proposed model by using the real data set.

Description

Traffic flow partition model for similar evolution mode clustering and dynamic time zone partitioning

One, the technical field

The invention relates to the field of intelligent traffic, in particular to short-time traffic flow prediction, and specifically relates to a traffic flow partition model which takes a similar evolution mode as a standard, clusters traffic flow data of all road sections of a road network and further dynamically partitions the traffic flow data of all the road sections with the similar evolution mode in a single day.

Second, background Art

The accurate real-time short-term traffic flow prediction can effectively relieve urban traffic jam and reduce urban air pollution, and has important social significance. Traffic flow data has characteristics of trend, periodicity, dynamic randomness and the like. The trend and periodicity belong to the regular characteristic of traffic flow, mainly show the trend or fluctuation changing according to the time law, and are the premise that the traffic flow can be predicted. The dynamic randomness is generated by regional road network traffic influence factor events (such as signal lamps, pedestrian traffic, road accidents, traffic control and the like), and can generate characteristics of fluctuation of traffic flow time series data. Dynamic randomness is the root cause that makes traffic flow difficult to predict accurately.

Third, the invention

The invention aims to further excavate the spatio-temporal information of regional road network traffic flow and establish a self-adaptive short-time traffic flow prediction model which can be more suitable for the dynamic randomness of the road network traffic flow so as to further improve the prediction accuracy of the model.

In the time dimension, the space-time distribution of the traffic flow in different time periods of the road section has obvious difference (such as peak time period and non-peak time period), the traffic flow evolution mode of one road section can be changed along with the time, namely the traffic flow can present obvious time non-stationarity in a single day. Therefore, it is necessary to study traffic flows of different time periods within a single day of a road segment.

Past traffic flow prediction models often employ full time series modeling or static time-partitioned modeling of time series. The static time partition modeling of the time series is often based on daily life experience, and the time partition is manually performed on the traffic flow time series data in a single day of a road segment, for example, the data is divided into 5 segments: 0:00-6:00, 6:00-9:00, 9:00-17:00, 17:00-20:00, 20:00-23:59, wherein 6:00-9:00 and 17:00-20:00 are morning peak and evening peak of the day. However, the partition strategy is often manually partitioned according to daily experience only, and the real data characteristic of the traffic flow is not adapted. Therefore, a dynamic time partition strategy is needed to adapt to the time non-stationarity of the traffic flow of the road network, and to represent the space-time state characteristics of the traffic flow in a finer granularity, so as to improve the prediction precision of the short-time traffic flow model.

Based on the analysis, the invention provides a traffic flow time sequence Partition model (SPC-DTSP) based on Similar evolution mode clustering and Dynamic time zones, which tries to mine the Dynamic space-time characteristics of traffic flow changing along with time for the first time and solves the challenge brought by traffic flow time non-stationarity in short-time traffic flow prediction. Specifically, the work done in this chapter contributes as follows:

(1) and automatically identifying road sections with similar traffic flow evolution modes in the road network by using an Affinity Propagation clustering Algorithm (APC).

(2) And aiming at the day-to-day evolution difference of the traffic flow, the traffic flow in the similar evolution mode is dynamically time-zone divided by using a curve K-Means algorithm (WKMS), and the space-time state characteristics of the traffic flow of the road network are dug more deeply.

(3) After the similar mode identification and the automatic time zone division, traffic flows in different time zones in different modes are respectively modeled, and the state information of the traffic flows is quantized in a finer granularity mode, so that the prediction precision of the model is more accurate.

(4) And verifying the effectiveness of the proposed model by using a real data set, comparing the effectiveness with the existing excellent prediction model, and showing the advancement of the proposed model.

The purpose of the invention is achieved by the following steps:

aiming at the problem that the dynamic randomness of traffic flow of each road section of a road network in a single day is not fully utilized in the existing research, and a static overall fixed model structure is used for prediction, the invention establishes a traffic flow time sequence partition model based on similar evolution mode clustering and dynamic time zone division. Firstly, classifying the traffic flow of each road section in a road network by using affinity propagation clustering, and classifying the road section traffic flow with similar evolution modes into one type; and then, carrying out single-day time zone division on the road sections with the similar traffic flow evolution modes by using a curve K-Means algorithm, and further finely dividing the traffic flow state of the standard road section on the time dimension. On the basis, modeling prediction of traffic flow is carried out, and prediction accuracy is further improved.

The specific method comprises the following steps:

firstly, preprocessing collected traffic flow data of a PeMS (highway management system) of the California, USA, including data aggregation, missing data filling, abnormal value processing and data screening. The data availability is improved, and the prediction accuracy of the model is improved.

(1) And (3) data aggregation: the original data sampling interval of the PeMS system is 30s, but too short sampling interval can cause the collected data to present larger degree of dispersion and randomness, which is not beneficial to the analysis and research of the traffic time series data. The PeMS itself provides various methods for aggregating data, which re-aggregates data at a sampling interval of 30s into a larger time interval, including 5 minutes, 15 minutes, and 60 minutes, to meet different data requirements of researchers. The short-term traffic flow prediction is focused on, and therefore, the time sequence data of the traffic flow with the time interval of 5 minutes is selected.

(2) Missing data filling: because the road annular detector is exposed to the outdoor environment for a long time, the road annular detector is influenced by various factors such as weather, geomagnetism, physical impact and the like, so that the sensor fails or even is damaged, and the collected time sequence data of the traffic flow may have conditions of local deletion and large-scale deletion. For locally missing data, linear interpolation is performed using data of adjacent times. For a large piece of missing data, this document is padded with average time series data for multiple identical week numbers.

(3) Abnormal value processing: outliers are manifested in the presence of data mutations in the traffic flow time series data. For example, in the early peak period, the traffic data of three sampling time points of a certain road section 8:10, 8:15 and 8:20 are 520, 20 and 540, and obviously, the data of 8:15 points is abnormal data. For sampled data, this document replaces with a linear average of the adjacent sampled time points before and after the outlier.

(4) And (3) screening data: the time sequence data of the traffic flow on the road section working day and on the weekend show different evolutionary trends, the time sequence data of the working day has obvious early peak and late peak, and the single peak time period on the weekend also generally appears in the noon, which is caused by different traveling habits of urban residents at different times. In order to verify the consistency of data, only the time series data of the traffic flow of the working day are selected as research objects.

After the preprocessing of the traffic flow data is finished, data with higher availability are obtained. Then, the characteristic representation of all time traffic flow data of each road section needs to be carried out firstly; secondly, similar evolution mode clustering needs to be carried out on traffic flow characteristic data of each road section; and finally, carrying out dynamic time zone division on the data with the similar traffic flow evolution mode to obtain a time division result of the traffic flow data.

1. Traffic flow time series data characterization

The time sequence data of the traffic flow in a single day of each road section presents a time-varying curve, taking the sampling frequency of 5 minutes as an example, the time-varying curve of the traffic flow takes 288 traffic flow data as constituent elements to form a time sequence of the traffic flow of a road section in one day, and the trend of the curve reflects the evolution mode of the traffic flow in a single day of the road section. Theoretically, all traffic flow time sequence data of the collection time (D days) should be clustered, and then an algorithm is used for filtering and combining the overlapped clusters, but the method increases the complexity of a prediction model, brings huge calculation load and is not beneficial to real-time prediction of traffic flow. In order to simplify the calculation, the traffic flow data of all the acquisition time of each road section is subjected to mean value calculation by taking a day as a unit, a traffic flow average time sequence is obtained, an average evolution intersection mode of the road section in the day within the statistical time is shown, and the average evolution intersection mode is used as the traffic flow data characteristic of the affinity propagation clustering algorithm.

Assume that a road network has M road segments, and traffic flow data of all road segments of the road network is represented as

Wherein all traffic data of the section p is defined by the formula (4-1):

wherein, N represents the traffic flow collection number with 5 minutes as sampling frequency in a single day, and N is 288; d represents the number of acquisition days; x is the number of_p,iAnd represents the traffic flow time-series data on the ith day of the link p.

Setting the traffic flow data characteristic of the section p as

Representing the average trend of the traffic flow over all acquisition times. Because of the significant difference in traffic flow data between weekdays and non-weekdays, the study object herein is limited to traffic flow data for road network weekdays.

Is defined as shown in formula (4-2):

2. affinity propagation clustering algorithm APC algorithm clusters all characteristic sequences of road network

The method for identifying the traffic flow similar evolution mode by using the APC algorithm comprises the following 5 steps:

(1) and characterizing the traffic flow time-series data of each road section.

(2) And mapping the road section traffic characteristics into Data points (Data points).

(3) Iterative computation of Responsibility information (responsiveness Message) r_i,jAnd Availability information (Availability Message) a_i,j。

(4) And judging whether the information transfer network converges or not through the global function.

(5) And converging the information transmission network to obtain each clustering center and each traffic flow evolution mode sequence.

The first step of the APC clustering algorithm is to map the traffic flow average time series data of the road segment i into 1 data point in N-dimensional space, where the data points of the traffic flow average time series data of all road segments in the road network are represented as {1,2, …, M }, and all data points constitute an information delivery network, and each data point is a node in the information delivery network. The APC clustering algorithm treats these data points as potential cluster centers and recursively computes and passes two types of real-valued messages along the edges of the information-passing network: r is_i,jAnd a_i,jUntil the information transmission network converges, the global function obtains the maximum value to obtain the optimal clustering center point set^[67]. The network global function is defined as formula (4-3) and formula (4-4):

where F is the cluster center set of all data points of the road network, c_iE F is the cluster center of data point i,

are data points i and c_iThe similarity is obtained by calculating the Euclidean distance between the two. The similarity calculation formula of any two points i and j is defined as formula (4-5):

the greater the similarity value, the greater the ability of point j to be point i. h is_jIs point j as the potential cluster center point c_jA penalty function of (2). If c is_iSelecting the point j as its cluster center point, the point j must also be its own cluster center, otherwise the point j cannot be called a cluster center point, i.e. formula (4-6):

c_i＝j，only if c_j＝j (4-6)

two types of information: accountability information r_u，lAnd availability information a_u，lPassing in iterative calculation of APC algorithm^[68]，r_i,jThe information from the point i to the candidate cluster center point j is included to characterize the fitness (Suitability) of the point j as the cluster center of the point i. a is_i，jInformation containing candidate cluster centers j through i indicates how well point f selects point j as the cluster center. By drawing a factor graph corresponding to the clustering criterion function and utilizing belief propagation to update two kinds of information, the global function of the factor graph is maximized, thereby completing clustering^[69]. Message updates are made using equations (4-7) through (4-9) as follows:

r_i,j←s_i,j-∑_{j′s.t.j′≠{i，j}}(a_i，j′+s_i，j′) (4-7)

a_i，j←min{0，r_j，j+∑_{i′s.t.i′≠{i，j}}max(0，r_i′,j)} (4-8)

r_j，j←∑_{i′s.t.i′≠j}max(0，r_i′,j) (4-9)

after convergence of the information transfer network, the cluster center c for each data point i_i，c_iSatisfies the formula (4-10):

when the clustering of all data points is completed, a cluster center point set as shown in equation (4-11) can be obtained:

C＝{c_i，i∈[1，w]，1＜w＜M} (4-11)

wherein w is the number of centers and M is the total number of road network segments.

After the cluster central point set is subjected to duplication elimination, a road network traffic flow modeling mode point set shown in a formula (4-12) can be obtained:

P＝unique(C)＝{p₁，p₂，...，p_r} (4-12)

wherein r is the traffic flow evolution mode number obtained by clustering, and r is len (p).

The road section point set contained in any traffic mode i is S_iIf the number of the road sections included in the mode i is N_i＝|S_i|，S_iAs shown in equations (4-13):

S_i＝{j|p_i＝c_j} (4-13)

assuming that the set of all traffic flow evolution mode time series characteristics is L, the expression of L is shown as the formula (4-14):

wherein N is the number of traffic flow data acquisitions within a single day.

After the clustering result is obtained, in order to more visually display the data distribution condition of the characteristic time sequence of each road section and the time sequence of the clustering center, the section sets X of the characteristic time sequence data of all road sections_pA standard score conversion is performed. The standard score is defined as shown in equations (4-15):

wherein, E [ X ]_p]Is X_pIn the expectation that the position of the target is not changed,

is X_pStandard deviation of (2).

3. Curve K-Means time zone division algorithm

The input of the curvature K-Means algorithm is a traffic flow evolution mode time sequence set P obtained through an APC clustering algorithm, and each traffic flow evolution mode sequence in the P is divided into time zones respectively. Through iterative computation, the WKMS algorithm obtains a homogenous class of discrete distributions.

In the initial stage of the algorithm, setting clustering boundary points b_i(black dots). Due to the introduction of the mandatory sequence constraint, in each iterative computation process, the first half elements of the time sequence can only be moved to the left to the data point (orange point) in front of the boundary; the second half of the time series can only be moved right behind the boundary. With this restriction, time zone division is performed on the entire traffic flow time-series data.

Now, it is assumed that the time series characteristic data of any p-th traffic flow evolution mode after APC clustering is

WKMS is targeted at

Is divided into k^pA different class of data

1＜k^p< 288, each data class represents traffic data of a time partition, k^pIs the time partition number of the WKMS to the m evolution mode traffic flow. In each iteration calculation, the contour coefficient of each cluster number in each evolution modeAll will be calculated, when the value of the contour coefficient takes the maximum value, the cluster number at that moment is the optimal time zone division number, that is, the partition number k of the mth traffic flow evolution mode at that moment^p。

Therefore, dynamic time zone division of similar traffic flow evolution modes is completed. After time zone division, the total number of traffic flow data in the q-th time zone is assumed to be

The mapping relationship between the time zone traffic data and the p-th evolution mode traffic flow time series data is shown in equations (4-16) and (4-17):

{1,2,…,k^p}→{1,2,…,288} (4-16)

wherein k is^pIs the number of time divisions, and,

and the traffic flow data of the p time partition in the p traffic flow evolution modes are represented.

Description of the drawings

FIG. 1 is a diagram of a traffic flow time sequence partition model structure with similar evolution mode clustering and dynamic time zone partitioning.

FIG. 2 is a schematic diagram of an affinity propagation clustering model.

FIG. 3 is a flow chart of the APC clustering algorithm.

FIG. 4 is a schematic diagram of traffic flow dynamic time zone division by curvature K-Mens.

Fifth, detailed description of the invention

The invention is implemented in 3 parts:

(1) traffic flow data characterization: in order to simplify the calculation, the average value calculation is carried out on the traffic flow data of all the acquisition time of each road section by taking a day as a unit, a traffic flow average time sequence is obtained, an intra-day average evolution intersection mode of the road section in the statistical time is shown, and the intra-day average evolution intersection mode is used as the traffic flow data characteristic of the affinity propagation clustering algorithm.

(2) Carrying out similar evolution mode clustering on the traffic flow characteristic data: because the road sections in the road network are physically connected directly or indirectly, the traffic state of a certain road section is influenced by the traffic states of the surrounding road sections to a certain extent, and thus a spatial correlation and traffic flow collaborative evolution mode among the road sections is formed. After the characteristic representation of the traffic flow data is finished, the method classifies the road traffic flow with the similar modeling mode in the road network by using the affinity clustering propagation algorithm, so that the construction range of the prediction model is narrowed to a more accurate data range.

(3) Dynamic time zone partitioning: and dynamically time-zone division is carried out on the traffic flow data with similar evolution modes after clustering. The urban traffic flow presents different evolution modes at different time intervals in one day, and the traffic flow data distribution at each time interval presents obvious difference. The data trend of the off-peak time in one day is gentle, the data of the peak time is in ascending and descending trend, and the traffic flow data distribution of each time period among different working days, working days and single day of weekends is different. Therefore, the data distribution characteristics of the traffic flow in each period are accurately identified, and the evolution mode of describing the traffic flow in a single day in a finer degree plays an important role in improving the performance of the prediction model. Therefore, the clustered traffic flow data with similar evolution modes are dynamically time-zone divided by using the improved K-Means algorithm curvature K-Means.

The user usage scenario of the invention is as follows:

an effective traffic flow prediction model is important for route planning, traffic control, intelligent driving, and the like. The traveler can judge the future congestion condition of the road by utilizing the flow prediction information to make a more efficient traveler plan. The real-time road condition prediction analysis is also helpful for travelers to adjust the advancing route in time, and the occurrence of traffic jam is reduced. The traffic manager can monitor the traffic state by using the prediction model, and take measures such as traffic signal control and the like in advance for areas where congestion is likely to occur. When emergency events such as car accidents occur, the future traffic flow change trend of the surrounding road sections is helpful for traffic managers to reasonably distribute resources, so that evacuation and rescue speed is increased. For applications such as intelligent driving and vehicle networking, accurate speed prediction information is the basis of an intelligent vehicle cooperative system and is an important guarantee for improving road traffic capacity and safety.

In conclusion, traffic flow prediction research has irreplaceable significance in the aspects of improving traffic problems, improving travel efficiency and the like.

Claims

1. A traffic flow time sequence partition model based on similar evolution mode clustering and dynamic time zone partitioning is characterized in that:

through characteristic representation and clustering of traffic flow data of different road sections, a traffic flow time sequence Partition model (SPC-DTSP) based on Similar evolution mode clustering and Dynamic time zone partitioning is provided, Dynamic space-time characteristics of traffic flow changing along with time are tried to be mined for the first time, and the challenge brought by traffic flow time non-stationarity in short-time traffic flow prediction is solved; proved researches on a real traffic data set of a California road 101 in the United states show that the model has higher prediction precision compared with a traditional space-time K neighbor model and a deep learning model;

specifically, firstly, carrying out characteristic representation on road network road section traffic flow data; secondly, classifying road section traffic flows with similar evolution modes in the road network by using an affinity propagation clustering algorithm; finally, the curve K-Means algorithm is used for carrying out dynamic time zone division on the classified traffic flow data to obtain a final time zone division result of the traffic flow data;

the algorithm comprises the following steps:

(1) the traffic flow time series data feature represents: the traffic flow time sequence data in a single day of each road segment presents a time-varying curve, taking a data sampling frequency of 5 minutes as an example, the traffic flow time-varying curve takes 288 traffic flow data as constituent elements to form a traffic flow time sequence of the road segment in one day, the trend of the curve reflects a traffic flow evolution mode in the single day of the road segment, theoretically, the traffic flow time sequence data of all acquisition times (D days) should be clustered, and then, a certain algorithm is used for filtering and combining the overlapped clusters, but the method increases the complexity of a prediction model, brings huge calculation load and is not beneficial to real-time prediction of the traffic flow, in order to simplify the calculation, the traffic flow data of all the acquisition times of each road segment are subjected to average calculation by taking the day as a unit to obtain an average time sequence of the traffic flow, and represents the day average evolution mode of the road segment in statistical time, the characteristic of the traffic flow data is used as the affinity propagation clustering algorithm;

(2) clustering all characteristic sequences of the road network by using an affinity propagation clustering Algorithm (APC) algorithm: because the road sections in the road network are physically connected directly or indirectly, the traffic state of a certain road section is influenced by the traffic states of the surrounding road sections to a certain extent, so that the spatial correlation between the road sections and a traffic flow collaborative evolution mode are formed, and after the characteristic representation of traffic flow data is completed, the road section traffic flows with similar evolution modes in the road network are classified by using an affinity clustering propagation algorithm, so that the construction range of a prediction model is narrowed to a more accurate data range;

(3) constructing dynamic space-time weighted Euclidean distance: the input of the curvedness K-Means algorithm is a traffic flow evolution mode time sequence set P obtained through an APC clustering algorithm, each traffic flow evolution mode sequence in the P is divided in time, and the WKMS algorithm obtains the homogeneity of discrete distribution through iterative computation.

2. The characterization of traffic flow data based on claim 1 wherein: the traffic flow time sequence data in a single day of each road segment presents a time-varying curve, taking a data sampling frequency of 5 minutes as an example, the traffic flow time-varying curve takes 288 traffic flow data as constituent elements to form a traffic flow time sequence of the road segment in one day, the trend of the curve reflects a traffic flow evolution mode in the single day of the road segment, theoretically, the traffic flow time sequence data of all acquisition times (D days) should be clustered, and then, a certain algorithm is used for filtering and combining the overlapped clusters, but the method increases the complexity of a prediction model, brings huge calculation load and is not beneficial to real-time prediction of the traffic flow, in order to simplify the calculation, the traffic flow data of all the acquisition times of each road segment are subjected to average calculation by taking the day as a unit to obtain an average time sequence of the traffic flow, and represents the day average evolution mode of the road segment in statistical time, as a traffic flow data feature of affinity propagation clustering algorithms.

3. The process of clustering all feature sequences of a road network using the affinity propagation clustering algorithm APC algorithm according to claim 2, wherein: optimizing 4 key steps of a space-time K nearest neighbor modeling process, specifically:

the method for identifying the traffic flow similar evolution mode by using the APC algorithm comprises the following 5 steps: 1, characterizing traffic flow time-series data of each road section; 2, mapping the road section traffic characteristics into Data points (Data points); 3 iterative computation of Responsibility information (Responsibility Message) r_i,jAnd Availability information (Availability Message) a_i,j(ii) a 4, judging whether the information transmission network is converged through a global function; 5, converging an information transmission network to obtain each clustering center and each traffic flow evolution mode sequence;

the first step of the APC clustering algorithm is to map the traffic flow average time series data of the road segment i into 1 data point in N-dimensional space, the data points of the traffic flow average time series data of all road segments in the road network are represented as {1,2, …, M }, all the data points form an information transfer network, each data point is a node in the information transfer network, and the APC clustering algorithm considers the data points as potential clustering centers and recursively calculates and transfers two types of real-valued messages r along the edge of the information transfer network_i,jAnd a_i,jAnd obtaining the maximum value of the global function until the information transfer network converges to obtain the optimal clustering center point set.

4. The time zone division algorithm using curvedness K-Means as claimed in claim 2 wherein: the input of the K-Means algorithm is a traffic flow evolution mode time sequence set P obtained by an APC clustering algorithm, each traffic flow evolution mode sequence in the P is divided into time zones respectively, homogeneity of discrete distribution is obtained by iterative computation and a WKMS algorithm, clustering boundary points are set at the initial stage of the algorithm, and because forced sequence limitation is introduced, the first half elements of the time sequence can only move to the data points in front of the boundary leftwards in each iterative computation process; with such restrictions, time zone division is performed on the entire traffic flow time-series data;

WKMS is targeted at

Is divided into k^pA different class of data

Each data class representing time-partitioned traffic flow data, k^pThe method is characterized in that the time partition number of the m evolution mode traffic flow is calculated by the WKMS, the contour coefficient of each cluster number in each evolution mode is calculated in each iterative calculation, when the contour coefficient value obtains the maximum value, the cluster number at the moment is the optimal time partition number, namely the partition number k of the m evolution mode traffic flow at the moment^pTherefore, dynamic time zone division of the similar traffic flow evolution mode is completed.