Spatial—Temporal Traffic Flow Data Restoration and Prediction Method Based on the Tensor Decomposition

Abstract

As an important part of urban big data, traffic flow data play a critical role in traffic management and emergency response. Traffic flow data contain multi-mode characteristics, which need to be deeply mined. To make full use of multi-mode characteristics, we use a 3-order tensor to represent the traffic flow data, considering “temporal-spatial-periodic” characteristics. To recover the missing data of traffic flow, we propose the Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition (MDCA-RVTD), which combines linear regression, univariate spline, and CP decomposition. Then, we predict the future traffic flow data by using the proposed Traffic Flow Prediction Algorithm Based on Data Completion Strategy (TFPA-DCS). The experimental results show that recovering the missing data is helpful in improving the prediction accuracy. Additionally, the prediction accuracy of the proposed Algorithm is better than gray model and traditional tensor CP decomposition method.

1. Introduction

Urban big data involves the daily life of citizens and the stable running of industries; it is characterized by large volume, complex sources, and heterogeneous structure [1]. How to make full use of urban big data to analyze city development issues and provide informational assistance for government departments has attracted great interest in recent years [2,3]. In challenges of city management, traffic problems such as increasingly traffic congestion, frequently traffic accidents, severely environmental pollution, should be of the upmost concern [4]. The traffic flow prediction is an important part of urban traffic management and emergency response [5]. In the background of controlling and preventing epidemic diseases, traffic flow prediction can obtain travel indicators, judge crowd-gathering areas, analyze cross-regional movements.

Traffic flow data are typical spatial-temporal data, which relate to various elements of the traffic network, including humans, vehicles, roads, and environmental information [6]. In the period of big data, city managers must dig deep into the potential value contained in traffic flow data. Traffic flow data contain multi-mode characteristics [7]. Most of the existing traffic flow prediction methods are based on three kinds of characteristics: temporal characteristics, spatial characteristics, and periodic characteristics [8,9].

In recent years, the common traffic flow prediction methods fall into two categories: the model-driven methods and the data-driven methods [10]. The model-driven methods, also known as parametric methods, including Autoregressive (AR), Historical Average (HA), Autoregressive Integrated Moving Average (ARIMA), Seasonal ARIMA (SARIMA) [11,12,13,14], etc. Generally, the model-driven methods only focus on temporal characteristics and need to satisfy predetermined theoretical assumptions, so the application of these methods is limited. The data-driven methods, also known as non-parametric methods, can be further divided into machine learning-based methods and deep learning-based methods [15,16,17,18]. For example, machine learning methods, such as Support Vector Regression (SVR) and K-Nearest Neighbor (KNN), were employed for traffic flow prediction [19,20]. Convolution Neural Networks (CNNs) are a classical type of deep learning method which can automatically capture spatial structural information and take spatial characteristics into account [21,22,23]. To settle spatial-temporal forecasting problems, some researchers proposed hybrid methods to improve the prediction accuracy, such as Convolutional LSTM Networks (ConvLSTMs) [24] and Spatio-Temporal Residual Network (ST-ResNet) [25]. However, hybrid methods increase the complexity of the prediction model. Moreover, all of the above methods cannot recover missing data. In the scenario of traffic flow prediction, missing data is inevitable due to equipment failure, bad weather and transmitting interference [26]. According to the report of the Texas Transportation Institute, the missing data of transportation system account for 16–93% in some states, with an average missing data rate of 67%. Therefore, how to recover the missing data is also an urgent problem in traffic flow prediction.

To take full advantage of multi-mode characteristics, and recover missing data as much as possible, some researchers have applied tensor decomposition to traffic flow prediction [27,28]. Using tensor to present traffic flow data can preserve the integrity of multi-mode characteristics. Tensor decomposition is an important part of multidimensional linear algebra theory, which can effectively mine potential characteristics contained in data. The common tensor decomposition methods include CP (CANDECOMP/PARAFAC) decomposition and Tucker decomposition.

In this paper, we use a high-dimensional tensor to represent the traffic flow data, considering “temporal-spatial-periodic” multi-mode characteristics. Firstly, we recover the missing data of the traffic flow data. Then, based on the completed data, the future traffic flow is predicted. The main contributions of this paper include the following.

(1)

Combined with linear regression, univariate spline and CP decomposition, we propose the Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition (MDCA-RVTD). The linear regression and the univariate spline are used to obtain “day-hour trend” features and “hour-minute trend” features, respectively. Then, we get the residual value tensor by eliminating the “day-hour trend” features and the “hour-minute trend” features. We apply CP decomposition for the residual value tensor, and add “day-hour trend” features and the “hour-minute trend” features after reconstruction, which can recover missing data better;

(2)

We propose the Traffic Flow Prediction Algorithm Based on Data Completion Strategy (TFPA-DCS). The united tensor is composed by the historical data that recover the missing data and the prospective data that need to be predicted. The prospective data is regarded as missing data, which can be determined by using data completion strategy;

(3)

We verify the proposed Algorithms by experiments. The experimental results show that recovering the missing data is helpful in improving the prediction accuracy. And the prediction accuracy of the proposed Algorithm is better than gray model and traditional tensor CP decomposition method.

The rest of the paper is organized as follows: Section 2 introduces the related works. Section 3 introduces the theoretical background. Section 4 proposes the Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition (MDCA-RVTD). Section 5 proposes a Traffic Flow Prediction Algorithm Based on Data Completion Strategy (TFPA-DCS). Section 6 explains the experiment’s results, and Section 7 provides a conclusion.

2. Related Works

Traffic flow prediction problems always attract great interest. Several studies have adopted model-driven methods and data-driven methods. Zambrano et al. discovered that only some street segments offered a good fit for quadratic regression, while a great number of street segments did not. They applied logistic regression to most of the street segments. Experimental results showed that they significantly improved the curve fitting results [29]. Zhang et al. proposed a method to predict freeway travel times using a linear model in which the coefficients varied as smooth functions of the departure time. They demonstrated the effectiveness of the proposed method by applying the method to two real-life loop detector data sets [30]. Wu et al. proposed a novel hybrid data-driven travel time prediction method. They explored a convolutional long short-term memory network with a self-attention mechanism that can accurately predict the running time of each segment of the trips and the waiting time at each station [31]. However, these methods can hardly take full advantage of potential multi-mode characteristics contained in traffic flow data effectively.

To make full use of multi-mode characteristics, some works apply tensor decomposition to traffic flow prediction. For example, Tan et al. presented a short-term traffic flow prediction approach based on Dynamic Tensor Completion (DTC), which was designed to use the multi-mode characteristics to forecast traffic flow with a low-rank constraint [32]. Duan et al. used a high-dimensional tensor to represent traffic flow data, considering “week-day-time” multi-mode. The Grey Model (GM (1, 1)) was used to week-mode prediction, the Scrolling Grey Model (SGM (1, 1)) was used to day-mode prediction, and the wavelet neural network was used to time-mode prediction. Then, the prediction results of the three different models were weighted by the grey correlation analysis method [33]. Tong et al. applied the tensor decomposition Algorithm to the Verhulst model and established the Verhulst model of the tensor decomposition Algorithm. Then, the new method was applied to short-term traffic flow prediction [34]. Yang et al. pointed out that the main challenge of traffic flow prediction was the data sparsity problem. To tackle this problem, they proposed the representation of the traffic flow using a tensor and utilized the gradient descent strategy to design a traffic flow prediction Algorithm [35].

3. Theoretical Background

3.1. Tensor Basics

Tensors, also referred to multi-dimensional arrays, are higher-order extension of vectors and matrices. For example, a vector can be regarded as a 1-order tensor, and a matrix can be regarded as a 2-order tensor. The N-order tensor is expressed as $\chi \in R^{I_1\times I_2\times \dots \times I_N}$. Here are some related concepts [32,33,34].

Definition 1.

N-order tensor$\chi \in R^{I_1\times I_2\times \dots \times I_N}$can be unfolded to a matrix, which is defined as unfolding matrix$(\chi ,n)=X_{(n)}$. The tensor element$(i_1,i_2,\dots ,i_n)$is mapped to the element$(i_n,j)$in matrix$X_{(n)}$, where$j=1+{\displaystyle \sum _{k=1,k\ne n}^N\left[(i_k-1){\displaystyle \prod _{m=1,m\ne n}^{k-1}{I}_m}\right]}$.

Definition 2.

Set two N-order tensors as$\chi \in R^{I_1\times I_2\times \dots \times I_N}$and$y\in R^{I_1\times I_2\times \dots \times I_N}$, then,

$$<\chi ,y>={\displaystyle {\sum }_{i_1=1}^{I_1}{\displaystyle {\sum }_{i_2=1}^{I_2}{\displaystyle {\sum }_{i_N=1}^{I_N}{x}_{i_1{i}_2\dots i_N}}}}{y}_{i_1{i}_2\dots i_N}$$

(1)

is the inner product of two N-order tensors.

Definition 3.

Set N-order tensor$\chi \in R^{I_1\times I_2\times \dots \times I_N}$and define the Frobenius norm as follows:

$$\Vert \chi \Vert =\sqrt{<\chi ,\chi >}=\sqrt{{\displaystyle {\sum }_{i_1=1}^{I_1}{\displaystyle {\sum }_{i_2=1}^{I_2}{\displaystyle {\sum }_{i_N=1}^{I_N}{x}_{i_1{i}_2\dots i_N}^2}}}}.$$

(2)

Definition 4.

The multiplication of a tensor$\chi \in R^{I_1\times I_2\times \dots \times I_N}$and a matrix$U\in R^{J\times I_n}$can be expressed as$(\chi {\times }_{n}U)\in R^{I_1\times \dots \times I_{n-1}\times J\times I_{n+1}\times \dots \times I_N}$, then,

$${(\chi {\times }_{n}U)}_{i_1\dots i_{n-1}j{i}_{n+1}\dots i_N}={\displaystyle {\sum }_{i_n=1}^{I_n}{x}_{i_1{i}_2\dots i_N}{u}_{j{i}_n}}$$

(3)

Definition 5.

If N-order tensors$\chi \in R^{I_1\times I_2\times \dots \times I_N}$can be expressed as a form of N vector exterior product$\chi =x_1\otimes x_2\otimes \dots \otimes x_N$,$x_k\in R^{I_k}(k=1,2,\dots ,N)$, then the tensor χ is a rank-1 tensor.

3.2. Tensor CP (CANDECOMP/PARAFAC) Decomposition

There are two central tensor decomposition methods: CP decomposition and Tucker decomposition. This paper adopts CP decomposition. Therefore, CP decomposition is introduced as following.

The CP decomposition is used to decompose the N-order tensor $\chi \in R^{I_1\times I_2\times \dots \times I_N}$ into the sum of several rank-1 tensors:

$$\chi \approx \left[A^{(1)},A^{(2)},....,A^{(N)}\right]={\displaystyle {\sum }_{r=1}^R{\lambda }_r}{a}_r^{(1)}\otimes a_r^{(2)}\otimes \dots \otimes a_r^{(N)}$$

(4)

R is an integer. The factor matrix of tensor $\chi$ as follow: $A^{(1)}=(a_1^{(1)},a_2^{(1)},\dots ,a_R^{(1)})$, $A^{(2)}=(a_1^{(2)},a_2^{(2)},\dots ,a_R^{(2)})$, …, $A^{(N)}=(a_1^{(N)},a_2^{(N)},\dots ,a_R^{(N)})$.

For example, the CP decomposition of a 3-order tensor $\chi \in R^{I\times J\times K}$ as Figure 1, it is as follow:

$$\chi \approx {\displaystyle {\sum }_{r=1}^R{\lambda }_r}{a}_r\otimes b_r\otimes c_r$$

(5)

where $a_r\in R^I$, $b_r\in R^J$, $c_r\in R^K$, r = 1, 2, …, R, ${\lambda }_r$ is the coefficient. Set

$$\widehat{\chi }={\displaystyle {\sum }_{r=1}^R{\lambda }_r}{a}_r\otimes b_r\otimes c_r=\Vert \lambda ;A,B,C\Vert$$

(6)

where corresponding element of tensor is ${\widehat{x}}_{ijk}={\displaystyle \sum _{r=1}^R{\lambda }_r{a}_{ir}}\otimes b_{jr}\otimes c_{kr}$, $i=1,2,\dots ,I$; $i=1,2,\dots ,J$; $i=1,2,\dots ,K$; The objective function of CP decomposition is as follow.

$$\min \Vert \chi -\widehat{\chi }\Vert$$

(7)

Firstly, we must determine the number of rank-1 tensors, which is expressed as R. However, it is an NP hard problem. In general, we traverse R starting at 1 until we find a suitable solution. When the number of rank-1 tensors is determined, CP decomposition can be performed by Alternating Least Square (ALS).

4. The Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition

4.1. Tensor Model for Traffic Flow Data

Considering the multi-mode characteristics of traffic flow data, we model traffic flow data as a 3-order tensor ${\chi }_{t,d,n}\in R^{T\times D\times N}$ ($t=1,2,\dots ,T-1,T$, $d=1,2,\dots ,D-1,D$, $n=1,2,\dots ,N-1,N$), where $T$ is the total number of time slices, $D$ is the total number of days, $N$ is the total number of links. For example, if the sample data are collected in two minutes, 720 time slices can be collected in a day, so the value of $T$ is 720. If the data are collected for 30 days, then the value of $D$ is 30. If the road network has 132 links, then the value of $N$ is 132. As shown in Figure 2, the potential data distribution contained in adjacent time slices can be obtained by the dimension of “time slices”. The fluctuation in the data on different days can be observed by the dimension of “days”, which also includes periodic variation, such as weeks and months. The correlation of data of adjacent links can be obtained by the dimension of “links”.

The advantages of tensor-based traffic flow data representation are as following.

(1)

When the tensor has structure of multi-dimension, it is intuitively easy to represent the multi-mode characteristics of traffic flow data;

(2)

The tensor can effectively preserve the structural features of the original traffic flow data;

(3)

The tensor can effectively solve the problems of dimension disasters and matrix singularity.

In the collection of traffic flow data, missing data is inevitable due to equipment failure, bad weather, and transmitting interference. There are missing data and non-missing data in the original traffic flow tensor. The missing data is denoted as ${\tilde{\chi }}_{t,d,n}$ while the non-missing data is denoted as ${\stackrel{⌢}{\chi }}_{t,d,n}$. Therefore, ${\chi }_{t,d,n}={\tilde{\chi }}_{t,d,n}\cup {\stackrel{⌢}{\chi }}_{t,d,n}$, ${\tilde{\chi }}_{t,d,n}\cap {\stackrel{⌢}{\chi }}_{t,d,n}=\varnothing$. The problem of missing data restoration is how to recover the missing data by using the non-missing data.

Set the non-negative weight tensor $\omega$ has the same size with the original traffic flow tensor, that means $\omega \in R^{I_1\times I_2\times I_3}$, $I_1=T,I_2=D,I_3=N$. The corresponding element of tensor $\omega$ is as follows:

$${\omega }_{i_1{i}_2{i}_3}=\{\begin{array}{l}0\hspace{1em}if\hspace{0.17em}{\chi }_{i_1{i}_2{i}_3}\hspace{0.17em}is\hspace{0.17em}missing\\ 1\hspace{1em}if\hspace{0.17em}{\chi }_{i_1{i}_2{i}_3}\hspace{0.17em}is\hspace{0.17em}non\text{-}missing\end{array}$$

(8)

where $i_1=1,2,\dots ,T-1,T$, $i_2=1,2,\dots ,D-1,D$, $i_3=1,2,\dots ,N-1,N$. Let ${\chi }_{t,d,n}={\chi }_{t,d,n}\ast \omega$, then, the missing data is set to 0, and the non-missing data remains unchanged.

4.2. Features Extraction and Residual Value Tensor Construction

The traffic flow tensor can simultaneously represent spatial features and temporal features. The spatial features in traffic flow tensor are reflected by the data of adjacent links are also closely arranged in the dimension of “links”. The temporal feature is the most important feature of traffic flow data, which needs to be fully utilized. The temporal features have different granularity, such as “day-hour trend” features and “hour-minute trend” features.

The “day-hour trend” features refer to the similar data distribution at the same hour of the day. For example, on a link of road network, there is less traffic volume between 5:00 am and 5:59 am. Moreover, there is a higher volume of traffic between 8:00 am and 8:59 am. The “day-hour trend” features can be extracted for 24 h in a day, which can be calculated as follows:

$${\overline{x}}_h^{d,n}=\frac{{\displaystyle {\sum }_{i=h*(60/\tau )+1}^{(h+1)*(60/\tau )}{x}_i^{d,n}}}{60/\tau }$$

(9)

where $h=0,1,2,\dots ,23$, and it represents 24 h in a day. $d$ and $n$, respectively, represent number of days and number of links. $\tau$ is the size of the time slice, and $60/\tau$ is the total number of time slices in an hour, and $i$ is sequence number of time slices. For example, if the sample data are collected in two minutes, there are 30 time slices in an hour. The corresponding sequence number of time slices for each hour is shown in Figure 3. ${\overline{x}}_h^{d,n}$ is the mean value of data of time slices within each hour in every day, where the data are grouped by link-ID before computing. The size of ${\overline{x}}_h^{d,n}$ is same as the original traffic flow tensor, and the data at the same hour in the same day are equal.

The “hour-minute trend” features refer to that the data of every time slice have similar distribution in different days. For example, on a link of road network, although the data of time slices at 5:00 am differ from that at 5:59 am, the data of time slices at 5:00 am are very similar each day. The “hour-minute trend” features are fine-granularity features, which can be calculated as follows:

$${\overline{x}}_m^{d,n}=\frac{{\displaystyle \sum _{j=1}^D{x}_m^{j,n}}}{D}$$

(10)

where $m=1,2,\dots ,T-1,T$, and it represents sequence number of time slices. $d$ and $n$, respectively, represent the number of days and the number of links. $D$ is the total number of days. ${\overline{x}}_m^{d,n}$ is the mean value of data at same time slices within D days, where the data are grouped by link-ID before computing. The size of ${\overline{x}}_m^{d,n}$ is same as the original traffic flow tensor, and the data at the same time slice in the different day are equal.

Due to inevitably missing data, it is possible that a situation emerges where missing data appears continuously for several days. In this case, the “day-hour trend” features and the “hour-minute trend” features cannot be calculated. We can predict these features that cannot be calculated by means of regression or interpolation. According to the experimental data distribution, this paper adopts linear regression to predict the “day-hour trend” features that cannot be calculated, which is as following:

$${\overline{x}}_{{\varnothing }_h}^{d,n}=Linear Regression({\overline{x}}_h^{d,n})$$

(11)

where ${\overline{x}}_{{\varnothing }_h}^{d,n}$ represents the “day-hour trend” features that cannot be calculated, while ${\overline{x}}_h^{d,n}$ represents the “day-hour trend” features that can be calculated by Equation (9). Set ${\overline{x}}_h^{d,n}={\overline{x}}_h^{d,n}\cup {\overline{x}}_{{\varnothing }_h}^{d,n}$ when we have predicted ${\overline{x}}_{{\varnothing }_h}^{d,n}$.

According to the experimental data distribution, this paper adopts univariate spline to predict the “hour-minute trend” features that cannot be calculated, which is as following:

$${\overline{x}}_{{\varnothing }_m}^{d,n}=Univariate Spline({\overline{x}}_m^{d,n})$$

(12)

where ${\overline{x}}_{{\varnothing }_m}^{d,n}$ represents the “hour-minute trend” features that cannot be calculated, while ${\overline{x}}_m^{d,n}$ represents the “hour-minute trend” features that can be calculated by Equation (10). Set ${\overline{x}}_m^{d,n}={\overline{x}}_m^{d,n}\cup {\overline{x}}_{{\varnothing }_m}^{d,n}$ when we have predicted ${\overline{x}}_{{\varnothing }_m}^{d,n}$.

In this paper, we extract the “day-hour trend” features ${\overline{x}}_h^{d,n}$ from the original traffic flow tensor ${\chi }_{t,d,n}$. And we get an intermediate tensor ${{\chi }^{\prime }}_{t,d,n}$ by eliminating the “day-hour trend” features from the original traffic flow tensor. Then, we extract the “hour-minute trend” features ${\overline{x}}_m^{d,n}$ from intermediate tensor. Moreover, we obtain a residual value tensor $E$ by eliminating the “hour-minute trend” features from intermediate tensor. The temporal characteristics have been approximately determined by “day-hour trend” and “hour-minute trend” features, while the remaining residual value means fluctuation caused by random factors. The residual value tensor is decomposed by CP-ALS, and the potential structure of the residual tensor is obtained. Since the two main features have been eliminated, the difference of the data elements of the residual value tensor is small. Therefore, the missing values could be recovered more accurately by CP decomposition. Then, we add “day-hour trend” features and the “hour-minute trend” features to the residual value tensor after reconstruction $\widehat{E}$. We can get the completed traffic flow tensor as follows:

$$x_{t,d,n}=x_{t,d,n}\ast \omega +(\widehat{E}+{\overline{x}}_h^{d,n}+{\overline{x}}_m^{d,n})\ast (1-\omega )$$

(13)

which means the non-missing data remains unchanged, and the missing data is set to $\widehat{E}+{\overline{x}}_h^{d,n}+{\overline{x}}_m^{d,n}$.

4.3. The Process of the Algorithm

The Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition is shown as Algorithm 1.

Algorithm 1 The Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition

Input: the original traffic flow tensor ${\chi }_{t,d,n}$

calculate the date-hour trend of ${\chi }_{t,d,n}$, get ${\overline{x}}_h^{d,n}$ get the intermediate tensor ${{\chi }^{\prime }}_{t,d,n}={\chi }_{t,d,n}-{\overline{x}}_h^{d,n}$ calculate the hour-minute trend of ${{\chi }^{\prime }}_{t,d,n}$, get ${\overline{x}}_m^{d,n}$ get the residual tensor $E={{\chi }^{\prime }}_{t,d,n}-{\overline{x}}_m^{d,n}$ $\widehat{E}=CP\_ALS(E)$ calculate $\widehat{E}+{\overline{x}}_h^{d,n}+{\overline{x}}_m^{d,n}$ $x_{t,d,n}=x_{t,d,n}\ast \omega +(\widehat{E}+{\overline{x}}_h^{d,n}+{\overline{x}}_m^{d,n})\ast (1-\omega )$

Return $x_{t,d,n}$

The input of the Algorithm 1 is original traffic flow tensor ${\chi }_{t,d,n}$, which has the missing data. Firstly, we extract the “day-hour trend” features ${\overline{x}}_h^{d,n}$ from the original traffic flow tensor ${\chi }_{t,d,n}$, when predict the “day-hour trend” features that cannot be calculated by linear regression. Secondly, we get an intermediate tensor ${{\chi }^{\prime }}_{t,d,n}$ by eliminating the “day-hour trend” features from the original traffic flow tensor. Thirdly, we extract the “hour-minute trend” features ${\overline{x}}_m^{d,n}$ from intermediate tensor, when predict the “hour-minute trend” features that cannot be calculated by univariate spline. Fourthly, we get a residual value tensor $E$ by eliminating the “hour-minute trend” features from intermediate tensor. Fifthly, the residual value tensor is decomposed by CP-ALS. The CP-ALS Algorithm is shown as Algorithm 2. Sixthly, we add “day-hour trend” features and the “hour-minute trend” features to the residual value tensor after reconstruction ($\widehat{E}$). Seventhly, the non-missing data remain unchanged, and the missing data are set to $\widehat{E}+{\overline{x}}_h^{d,n}+{\overline{x}}_m^{d,n}$.

Algorithm 2 CP-ALS Algorithm

$procedure\hspace{0.17em}CP-ALS(E,R)$

Initialize $A,B,C$

repeat

$A\leftarrow {\chi }_{(1)}(C\odot B){(C^{T}C\ast B^{T}B)}^{\uparrow }$

$B\leftarrow {\chi }_{(2)}(C\odot A){(C^{T}C\ast A^{T}A)}^{\uparrow }$

$C\leftarrow {\chi }_{(3)}(B\odot A){(B^{T}B\ast A^{T}A)}^{\uparrow }$

normalize columns

until maximum iterations times or iterations convergence

return $\lambda ,A,B,C$

5. Traffic Flow Prediction Algorithm Based on Data Completion Strategy

The missing data of the original traffic flow tensor can be recovered by the Algorithm 1 proposed in the previous Section. To distinguish the original traffic flow tensor from the tensor after completion, we denote completed tensor as ${\chi }_t^{d,n}$. We predict the future traffic flow based on the completed tensor. When we predict the future traffic flow, the data of time slices that close to the forecast point play a greater role, while the data of time slices that far away from the forecast point are less effective. Therefore, we introduce the tensor window $W(T,s)=\{{\chi }_{T-s+1}^{d,n},\dots ,{\chi }_T^{d,n}\}$, which localizes the tensor into smaller time slices sequence with size $s$ at time $T$. As shown in Figure 4, the traffic flow prediction problem can be defined. Given the data in $W_{\{D-1\}}(T,s)$ of previous $D-1$ days and the data in $W_D(T-1,s)$ of the $D$ day, we need to predict data at time $T$ of the $D$ day (${\chi }_T^{D,n}$), where $n=1,2,\dots ,N-1,N$.

This problem can be solved by using data completion strategy, which means regarding data at forecast point as the missing data. As Algorithm 3 shows, we use data completion strategy to predict the future traffic flow. Firstly, we extract the data in $W_{\{D-1\}}(T,s)$ and $W_D(T-1,s)$ as historical data. Secondly, we recover the missing data of the historical data. Thirdly, the united tensor is composed by the historical data that recover the missing data and the prospective data that need to be predicted. Fourthly, the united tensor is processed by Algorithm 1.

Algorithm 3 Traffic Flow Prediction Algorithm Based on Data Completion Strategy

Input: the value of $D$ and $T$ of ${\chi }_T^{D,n}$,the size of tensor window $s$ get the historical data in $W_{\{D-1\}}(T,s)$ and $W_D(T-1,s)$ complete the missing values of the historical data construct $W_{\{D+1\}}(T,s)$, $W_D(T-1,s)$, ${\chi }_T^{D,n}$ to the united tensor process the united tensor by Algorithm 1

Return ${\chi }_T^{D,n}$

6. Instance Analysis and Experiment Results

We conduct an experiment to validate the effect of our approach. The experiment tool is MATLAB Tensor Toolbox, and we use Python for data processing and features extraction. The dataset provided by “Intelligent Traffic Prediction Competition” of Ali Tianchi is used. The dataset includes the road network information of 132 links, and average travel time of each links from 1 March to 31 May 2016, in which the sample data are collected every 2 min. For example,

Table 1. Example for travel time of links.

Link_ID	Time_Interval_Begin	Date	Travel_Time
4377906289869500514	2016-03-01 06:18:00	2016-03-01	Nan
4377906289869500514	2016-03-01 06:20:00	2016-03-01	4.8
4377906289869500514	2016-03-01 06:22:00	2016-03-01	6.3
4377906289869500514	2016-03-01 06:24:00	2016-03-01	6.6
4377906289869500514	2016-03-01 06:26:00	2016-03-01	6.6
4377906289869500514	2016-03-01 06:28:00	2016-03-01	Nan

shows the travel time of links. The other information, such as road network information, could be downloaded from Ali Tianchi official website. Since the dataset is real-data, there are a lot of missing data, some of statistical outliers, and out-of-order time slices. Therefore, it can be analyzed as an instance, and the effect of missing data completion and future data prediction can be verified.

The traffic flow prediction scenario predicts the travel time of each link during the first day of the May Day holiday by using the data in March and April 2016. To compare different time periods, according to the tensor window, we select the data of time slices between 6:00 am and 9:58 am for morning peak prediction, the data of time slices between 10:00 am and 13:58 pm for noon peak prediction, the data of time slices between 14:00 pm and 17:58 pm for evening peak prediction. The prediction results will be demonstrated below.

Our task is to validate the missing data restoration accuracy and future traffic flow prediction accuracy. Since we cannot obtain real value of the missing data, the restoration accuracy cannot be directly verified. Therefore, we compare the prediction accuracy of using the completed data and non-completed data to verify the restoration accuracy.

Figure 5 shows the data distribution, and there are some obvious outliers. Since the provided information cannot determine whether the outliers are actual fluctuations or incorrect records, we cannot simply delete the outliers. For the missing data, the dataset is not marked with the missing data. In other words, the time slices of missing data do not appear in the time slices sequence. Therefore, we need preprocess the dataset and mark the missing values. As shown in Figure 6, we take the data of time slices from 6:00 am to 9:58 am as an example to explain the missing data distribution. It can be seen that there are serious missing data. Moreover, most of data are missing in some links. Therefore, it is very necessary to recover the missing data.

The effect of missing data completion is shown in Figure 7. It can be seen that the Missing Data Completion Algorithm proposed in this paper has a high completion rate. Except for some links where almost all data are missing, other missing data have been completed. For the missing data of the links where almost all data are missing, the data of the upstream and downstream links can be used for approximate completion.

In this paper, the Root Mean Square Error (RMSE) is used to evaluate the prediction accuracy, and it is as follows [36]:

$$RMSE=\sqrt{\frac{{\displaystyle {\sum }_{i=1}^N{(tt{p}_i-tt{r}_i)}^2}}{N}}$$

(14)

where $ttp$ represents the predicted travel time of each link, $ttr$ represents the actual travel time of each link, and $N$ represents the total number of links, with the value of 132. The smaller RMSE means the better the prediction accuracy.

We predict the travel time of each link during the first day of the May Day holiday by using the data from March and April 2016. The data of time slices between 6:00 am ad 9:58 am are selected for morning peak prediction, and we suppose the morning peak appears at 10:00 am, because this day is a holiday. The data of time slices between 10:00 am and 13:58 pm are selected for noon peak prediction, and we suppose the noon peak appears at 14:00 pm. The data of time slices between 14:00 pm and 17:58 pm are selected for evening peak prediction and we suppose evening peak appears at 18:00 pm. Then, we compare the prediction value with real value. The results are shown in Figure 8. As shown in Figure 8, the predicted value is consistent with the actual value, but some points fluctuate. The reason is the influence of outliers, which will affect the “day-hour trend” features and the “hour-minute trend” features to affect the predicted value. In addition, the prediction value and real value at the morning peak is closer than that of the noon peak and the evening peak. Since it is the first day of the May Day holiday, people’s travel habits are different from the usual. As

Table 2. Comparison of prediction accuracy.

	Indicator	RMSE
Model
Gray Model		12.01486
Traditional CP-WOPT		11.63461
Uncompleted-Missing-Data-Based		13.055
Proposed Algorithm		3.6672

shown, we compare the prediction Algorithm proposed in this paper with gray model, CP-WOPT, and uncompleted-missing-data-based prediction. The experimental results show that completing the missing data is helpful to improve the prediction accuracy. Moreover, the prediction accuracy of the proposed Algorithm is better than gray model and traditional CP-WOPT decomposition method. The reason is that the proposed Algorithm makes full use of “temporal-spatial-periodic” multi-mode characteristics based on the completed data, and the tensor window makes the data of time slices that close to the forecast point play a greater role.

7. Conclusions

Traffic flow data contain multi-mode characteristics and provide a foundation for researching intelligent transportation systems. In this paper, we use a 3-order tensor to represent the traffic flow data to make full use of “temporal-spatial-periodic” multi-mode characteristics. To deal with the inevitable missing data in transportation systems, we propose an Algorithm called the Missing Data Completion Algorithm Based on Residual Value Tensor Decomposition (MDCA-RVTD), which combines linear regression, univariate spline, and CP decomposition. This approach can extract critical different granularity features and preserve potential multi-mode characteristics. Experimental results show that recovering the missing data is helpful in improving the prediction accuracy. To predict the future traffic flow data, we propose an Algorithm called Traffic Flow Prediction Algorithm Based on Data Completion Strategy (TFPA-DCS), which performs CP decomposition on the united tensor. Experimental results show that the prediction accuracy of the proposed Algorithm is better than gray model and traditional tensor CP decomposition method.

The advantages of the method based on tensor decomposition include preserving correlation of the original data, representing the multi-mode characteristics, and solving the problems of dimension disasters. However, the proposed Algorithms also require improvement. For our future work, we plan to integrate multiple context factors, such as weather parameters and regions partition.