Feature selection and extraction in spatiotemporal traffic forecasting: a systematic literature review

The most natural explanation of spatiotemporal relationships in traffic flow is based on cars’ movement: if a car is observed at a spatial point, it is expected to be observed later at another, downstream point. This fact creates a background for the most popular exogenous feature filtering approach (utilised in 44 studies) – to limit spatiotemporal dependencies to one direct upstream neighbour location. This approach perfectly matches the classic macroscopic traffic flow theory, and its effectiveness for traffic volume prediction is supported by many studies. For other traffic characteristics such as speed or travel time, the direction of this relationship could be different—congestion at a downstream spatial location affects upstream traffic flow; therefore, four studies consider selection of a direct downstream neighbour as a separate alternative specification of spatiotemporal links, and 34 studies simultaneously consider direct upstream and downstream neighbours. Approaches based on direct neighbours work well if two basic conditions are satisfied: 1) a time delay interval (time lag) of phenomena (traffic volume, speed, etc.) between spatial locations is identified correctly, and 2) the analysed road segment is a linear arterial road without traffic signals or ramps. The first issue can be solved within modern forecasting methodologies, but the second one is very limiting for real world urban road networks. A potential workaround is to include the number of intersections (of different types) into the model [7], but the general treatment is to model links between neighbouring spatial locations via independent model parameters. Thus, the Bayesian network, which allows a separate identification of every link, is the most popular modern methodology (10 studies) utilising direct neighbour-based spatiotemporal FSE.

A natural extension of the direct neighbour-based approach is simultaneous utilisation of several upstream locations (13 studies) or a predefined spatial “window” of upstream and downstream locations (8 studies). This approach is more flexible with respect to time lag identification, but in the case of a large interconnected network, it is highly dimensional and requires additional filtering of features. Convolutional neural networks, a modern deep learning approach applied in four studies [8‐11], utilise a predefined spatiotemporal window as an input and implement further FSE by embedded mechanisms.

Many researchers (26 studies) simultaneously utilised data from all available spatial locations, but given that most case studies included only a limited road network segment, this approach can be considered as a special case of the “window” feature selection.

Several researchers (six studies) utilised travel times between locations to reduce the number of spatial links (by excluding locations that are too close and too far to have an explainable influence within a specified time lag). For instance, Min and Wynter [12] utilised this approach to limit the number of coefficients in their vector autoregressive model and found it beneficial for traffic forecasting accuracy. If travel times between spatial locations are assumed as equal, these restrictions could allow use of a higher order neighbourhood (i.e. neighbours of neighbours are included in relationships for the second time lag). Higher order neighbours are typical in STARIMA models and were utilised in seven studies, based on this methodology.

An alternative exogenous feature filtering approach, which is not directly based on connections between spatial locations, has been suggested by Ermagun and Levinson [13‐15]. The introduced network weight matrix utilises graph characteristics of the road network such as betweenness centrality and vulnerability to discover complementary and competitive spatial links. Network weights can be purely graph-based or enhanced by associated characteristics of traffic flows (e.g. weighted by traffic volume). Associated links are not necessarily connected directly, thus, such spatiotemporal relationships can reach beyond the bounds of the physical road network.

Finally, exogenous filtering of spatiotemporal relationships can be performed on the basis of individual cars’ routes. Stathopoulos, Dimitriou, and Tsekeris [16, 17] report application of a micro-simulation procedure for a detailed analysis of spatiotemporal links under different traffic conditions. To the best of our knowledge, there are no studies that utilise real cars’ routes for FSE purposes, although the growing availability of probe cars’ data creates the possibility of new developments in this direction.

Considering the temporal dimension, the most popular exogenous feature selection method (utilised in 95 studies) is to set a maximum time lag T and include all lags {1, 2,  … , T} in the model. The maximum time lag is usually based on the size of an analysed road segment (to allow cars to leave the segment before the specified period). This approach works well for small road segments and regular traffic conditions but is not always suitable for large networks. The effects of congestion in a segment could continue for 2–3 h, and thus, the required maximum time lag for moderately detailed 5-min time spans is quite large. If related spatial locations are predefined, the number of time lags can be limited by the travel time (to exclude excessively fast and slow effects). The former approach is utilised in six analysed studies.

In contrast to exogenous feature filtering methods, endogenous methods are based on information regarding traffic flow at different spatial locations. The most widely used statistical technique is based on correlation analysis and the cross-correlation function (CCF). The CCF returns correlation coefficients between traffic flows at different spatial locations with specified time lags and can be used for identification of spatiotemporal relationships. Note that CCF is not based on physical connectivity of the road network and thus it can discover potential relationships between remote spatial locations (e.g. simultaneous traffic flows from different directions to the city centre every morning or to a stadium on match days). Authors in 21 studies utilise CCF for identification of both spatial and temporal relationships, six studies use it for temporal analysis and 11 studies for spatial dimensions. Application of the CCF function requires definition of a threshold value to exclude insignificant or weak spatial relationships. The formal Student’s test for insignificance of a correlation coefficient is not always appropriate, because this could lead to too many spatiotemporal links. Thus, many authors use a predefined threshold to reach a required level of STN sparsity (e.g. Li et al. [18] used a 0.94 value for the correlation coefficient). The modern graphical least absolute shrinkage and selection operator (LASSO) algorithm allows automatic identification of the most informative spatiotemporal links via estimation of the precision matrix (an inverse of the covariance matrix) based on l1-regularisation. The graphical LASSO is applied in four studies [18‐21] for filtering spatial relationships, but to the best of our knowledge, only Haworth and Cheng [20] applied it in both spatial and temporal dimensions simultaneously. The results of the graphical LASSO application are promising, but application of other forms of regularisation (i.e. the maximum concave penalty) is also recommended by authors [19].

Application of the CCF function for non-stationary time series may lead to a well-known problem of spurious correlations and incorrect conclusions reached regarding significant spatial relationships. To overcome this problem, Hasan and Kim [22] and Pavlyuk [23] applied Granger causality tests for identification of spatiotemporal relationships.

Another endogenous feature filtering approach is based on a preliminary application of regularised regression models. Least-angle regression (LARS) is an l1-norm-based algorithm that produces a full piecewise linear solution and excludes weak predictors. Recently, it was successfully applied to spatiotemporal FSE by Polson and Sokolov [24] and Yang et al. [25, 26]. Note that although the LARS algorithm and LASSO regularisation share the same principle, we distinguish them within this study based on the point of their application—outside of the model for LARS and within the model for LASSO. Thus, the LASSO approach will be separately discussed with other embedded feature selection methods.

Another technique, multivariate adaptive regression splines (MARS), also was successfully applied by Xu et al. [27, 28] and by Ye et al. [29]. Xu et el. [27] applied MARS to preliminary feature selection for the SVR model, while authors of other studies applied MARS directly to traffic flow forecasting.

Finally, several recent studies discover spatiotemporal relationships on the basis of special methods or indicators, designed by the authors to apply deeper analysis of traffic similarities. Dong et al. [7] constructed an indicator that simultaneously includes adjacency of spatial locations – the shortest distance and number of intersections between them; Zhu et al. [30] utilised similarity of traffic flows at different spatial locations; Cheng et al. [31] weighted the similarity by the distance between links; Deng and Jiang [32] suggested empirical association rules; Pascale and Nicoli [33] utilised a mutual information indicator; Chan et al. [34] applied the Taguchi method; Cai et al. [35] constructed an indicator using the distance and a connective grade of spatial locations and correlations for traffic flows; Wu et al. [36] suggested a custom bi-square function; Chen et al. [37] applied weighted traffic flows as a similarity metric.

Wrapper feature selection methods are based on multiple evaluations of a forecasting model for selection of an optimal set of features. We consider traffic forecasting as the primary research problem; therefore, the natural key performance indicator is the model’s forecasting accuracy. Root mean square error (RMSE), mean absolute error (MAE), and mean absolute percentage error (MAPE) are the most widely used model performance indicators. All mentioned indicators estimate the in-sample forecasting accuracy and can lead to incorrect preference of overfitted models with too many spatiotemporal relationships. Thus, many researchers penalise the model’s complexity by applying information criteria (Akaike or Bayesian). This approach is applied in most studies based on statistical forecasting models (VAR, STARIMA, etc.). Another option is to apply a cross-validation procedure (e.g. rolling window analysis [38]) to estimate the out-of-sample model performance.

Given the performance indicator of a forecasting model and repeated model evaluations, researchers apply different techniques to find an optimal set of features. The majority of researchers (50 studies) identify an optimal number of time lags empirically (testing the forecasting model for different time lag values), and 12 studies utilised a similar technique for the spatial dimension (e.g. using empirical identification of an optimal number of upstream sensors [38, 39]). In addition, many researchers (24 studies) compared different exogenous and endogenous filtering methods (e.g. network-connectivity versus CCF-based approaches), which can be considered as a special case of empirical wrapper feature selection.

Many forecasting methodologies provide specific metrics to support a decision on feature exclusion. Statistical methodologies apply hypothesis testing routines (i.e. Student’s test) for identifying significant features; neural networks allow estimation of elasticities of input components [40]; and random forests include permutation importance heuristics [41]. Using these metrics, researchers can refine the feature set of the forecasting model.

High computational complexity is a well-known problem in wrapper feature selection methods, which is widely solved by application of heuristic algorithms, such as particle swarm optimisation (PSO) and genetic algorithms (GA). Abdulhai et al. [42, 43] suggested application of GA for selection of an optimal number of upstream and downstream spatial locations (as well as for other parameters of their neural network-based forecasting model). Recently GA were applied for spatial [44‐46] and temporal [47] feature selection. The PSO approach was applied by Chan et al. [48, 49] and recently combined with GA by Zheng et al. [50].

Embedded methods incorporate feature selection as part of a forecasting model’s training process. The LASSO approach is the most widely used in spatiotemporal traffic forecasting (seven studies) and is based on the l1-norm of spatiotemporal links:

The l1-norm in the Lagrangian form is included in the objective function and ensures meaningful feature selection. Kamarianakis et al. [51] applied LASSO to vector autoregressive models; Piatkowski et al. [52] utilised LASSO and elastic net techniques to construct a graphical (random field) model; Li et al. [53] and Zhou et al. [54] executed preliminary feature selection and constructed LASSO-regularised autoregressive distributed lag models. Haworth and Cheng [55] analysed alternative regularisation techniques, maximum concave penalty (MCP) and smoothly clipped absolute deviation (SCAD), and found MCP beneficial with respect to the estimated STN sparsity.

Long short-term memory (LSTM) units are used in recurrent neural networks for automatic selection of an appropriate temporal memory structure. Such units are widely used for forecasting of time series with unknown duration of time lags between important events and have been effectively applied in several recent studies involving traffic flow [9, 11, 24, 56, 57].

Modern deep learning approaches allow a feature selection mechanism to be embedded into the multi-layer neural network architecture. Huang et al. [58] and Niu et al. [59] applied restricted Boltzmann machines as deep architecture components responsible for feature selection. Alternatively, Lv et al. [60] included sparse autoencoders that enforce encoding of the original set of spatiotemporal links into a smaller set of features (this approach works similar to dimension reduction methods, described below).

The feature selection methods described thus far are based on identification of the most important spatiotemporal features (edges in the time-expanded graph). An alternative approach is to apply a dimension reduction technique to limit the number of time periods (layers) or spatial locations (vertices in the time expanded graph). The most widely used technique is spatial clustering and followed by application of a forecasting model to clusters. This technique is applied in 12 studies using different clustering methods. Examples of these methods include neural networks [61, 62], self-organising maps [63], k-means [64, 65], simulated annealing [66], and empirical spatial aggregation [67, 68].

Temporal aggregation is an issue widely addressed in time series forecasting. Although the importance of correct temporal aggregation is widely acknowledged for traffic forecasting [2], it has rarely been directly addressed in publications (recently, Fusco et al. [68] provided empirical evidence of temporal aggregation effects on forecasting accuracy).

Feature selection methods and spatial clustering consider STN identification as a step of forecasting. If STN identification is not a required research result, then standard feature extraction techniques (e.g. principal component analysis based on eigenvalue decomposition (PCA-EVD)) can be applied to prepare composed inputs for an efficient predictor. Such composed inputs do not represent the STN structure, but do include its most important aspects. PCA-EVD was used in nine studies as a preliminary step for different forecasting models: neural networks [69, 70], support vector regression [71‐75], Bayesian networks [76], and random forests [77]. PCA-EVD has also been used as a method for tensor decomposition [78]. In most studies, PCA-EVD was applied for both temporal and spatial dimensions simultaneously.

Amongst other dimension reduction methods, we note applications of PCA based on singular-value decomposition [74, 79‐81], non-negative matrix factorisation [82, 83], local shrunk discriminant analysis [84], and singular spectrum analysis [79, 85, 86].