# A Road Network Enhanced Gate Recurrent Unit Model for Gather Prediction in Smart Cities

Authors: Mingchao Yuan; Ling Tian; Ke Yan; Xu Zheng
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Gather prediction is an indispensable part of smart city projects. The city government can respond in advance based on gather predictions and greatly reduce the loss and risks caused by vicious gatherings. Compared with other trajectory prediction tasks (i.e., the recommendation of point of interest), gather prediction pay more attention to real-time trajectory data and requests stronger spatial-temporal dependence. At the same time, gather prediction is more focused on scenes with multiple types of trajectories. And the existing methods majorly rely on the trajectory data and ignore the great influence of geographical environment (i.e., road network structure). Therefore, this paper transforms the gather prediction into the trajectory prediction task with strong real-time condition in a certain city and conducts the gathering situations by predicting users’ aggregated movements in next minutes or hours. A novel Spatiotemporal Gate Recurrent Unit (STGRU) model is proposed, where spatiotemporal gates and road network gate are introduced to capture the spatiotemporal relationships between trajectories. Compared with existing methods, we improve the performance of the model by adding road network structure and external knowledges, as well as time and distance gates to reduce model parameters. The proposed STGRU is evaluated on three real-world trajectory datasets, and the experimental results demonstrate the effectiveness of the proposed model.


---

## Body

## 1. Introduction

In recent years, various problems caused by the gathering of people are one of the main reasons hindering urban construction and development. Crowd gatherings are prone to various accidents, such as stampede, fighting, and wounding, which place high demands on the city’s management and control capabilities. Therefore, gather prediction can greatly help the city government react in advance and significantly reduce the losses and risks caused by vicious gatherings [1, 2]. As an indispensable part of smart transportation, gather prediction mainly leverages the trajectory data collected by various Internet of Things sensing devices [3–6] (such as mobile phones [7], cars, and other GPS devices [8]). These trajectory data include multiple types of patterns such as walking, driving, and public transportation. Firstly, the city government needs to predict the gathering situation to take preventive measures in advance and combine the geographical features such as rivers and buildings to divide the regions. Then, the city government may process all the trajectory data at the current moment in the city by predicting its location at a certain time in the future. Finally, the gather is obtained through statistical methods or clustering algorithms on trajectory prediction results.In order to achieve high-accuracy trajectory prediction, current methods majorly focus on modeling the sequential of the trajectory data and the time interval and distance interval between adjacent trajectory points. The main object is to integrate temporal and spatial features to model user behavior patterns. Typical techniques like recurrent neural networks (RNN) [9], Long short-term memory (LSTM) [10], and Gate Recurrent Unit (GRU) [11] have been successfully applied to various types of sequential data modeling and have greatly improved performance. However, none of the above methods consider time intervals and geographic informations [12] in the trajectory data. Some recent works are devoted to extending RNN and LSTM to enable modeling of time and distance intervals between neighbor points. For example, ST-RNN [13] tries to model spatiotemporal context by extending RNN, and HST-LSTM [14] merged the spatiotemporal influence into LSTM. Recently, STGN [15] achieves SOTA by designed two pairs of time and distance gates to model the time interval and distance interval separately.Nevertheless, trajectory data applied for gather prediction usually suffers the data sparsity [16], due to the uneven sampling interval and distribution of sensing devices. Previous efforts tried to apply spatial-temporal relations to mitigate the problem of data sparsity, but the effect is not obvious. Inspired by Li et al. [17], geographic environment information (such as road network structure) and external knowledge (such as weather information and holiday information) can effectively alleviate the problem of data sparsity. The impact of the geographic environment is essential for the modeling of short-term and long-term behavior patterns of users, and weather and holiday information will affect the overall behavior of users. For example, if the user’s continuous trajectories are on the same road segment, it can be judged that the current behavior patterns are similar. Meanwhile, the long-term historical trajectory road network information can well assist in modeling the long-term behavior pattern of users. Furthermore, on weekends, more people are willing to visit more distant areas and stay in a certain location for a long time. All these side information can benefit mitigate the problem of data sparsity and improve the performance of gather prediction.In order to make full use of external knowledge, this paper proposes a new spatiotemporal gated network by integrating road network structure and external knowledge, named Spatiotemporal Gate Recurrent Unit (STGRU). One pair of time gate and distance gate is designed to capture the short-term behavior pattern by utilize time and distance intervals, and a road network gate is introduced to memorize road network structures to model geographical environment constraints.The proposed model abstracts the road network structure of the city into a planar graph and extracts the road network structure of a certain track point. And the weather and holiday information are integrated into the track information for input. Moreover, STGRU can model the long-term and short-term behavior patterns of users and reduce the scale of model parameters to a certain extent. Finally, the proposed model processes the trajectory prediction results with statistic methods to achieve gather prediction. Experiments show that considering the road network structure and external knowledge can effectively improve the performance of the model.Our contributions are summarized below:(1)
Based on the standard Gate Recurrent Unit, we proposed a Spatiotemporal Gate Recurrent Unit (STGRU) model, which integrates road network structure and external knowledge, and reduces the amount of model parameters to a certain extent(2)
We propose an innovative gating mechanism, adding road network gate, which can model the road network structure for learning spatiotemporal relationships between users’ trajectories(3)
We evaluate the proposed method on three real-world datasets including population data of Nagoya, Osaka, and Tokyo. The comprehensive comparisons with the state-of-the-art methods show the effectiveness of our model


## 2. Related Work

### 2.1. Smart Transportation and Trajectory Data

Smart transportation is a major component of smart city. The main research difficulty is the analysis and decision-making reaction of traffic information.Traffic information analysis [18] includes traffic flow forecasting and traffic demand forecasting. Traffic flow forecasting [19, 20] and traffic congestion forecasting can help better regulate and control traffic and can effectively alleviate traffic congestion. The taxi demand forecasting method proposed by Geng et al. [21] can help taxi companies to better allocate vehicles. Li et al. [22] proposed a method for forecasting the demand for shared bicycles, which can optimize resource scheduling.Mining and analysis of trajectory data can assist in traffic planning decisions. Wei et al. [23] used the number of stops and the parking position to analyze the effectiveness of the main line coordination.


### 2.2. Spatiotemporal Data Modeling

On the other hand, trajectory data is a type of spatiotemporal data, with two dimensions of time and space. Data mining of spatiotemporal data is very difficult, and it is also one of the current research hotspots. The Markov chain-based model [24] is a classic sequence model. And deep learning methods [25] such as RNN, LSTM, and GRU have excellent results in time modeling. The method based on matrix factorization [26] or tensor factorization [27] can model spatial features. CNN [28, 29] and GCN [30] are currently the best spatial modeling methods.In order to capture the spatiotemporal features, Al-Molegi et al. (2016) proposed STF-RNN [31] to learn different temporal and spatial features. The TGCN [32] proposed by Zhao et al. uses GRU and GCN stacking to model spatiotemporal features. The STGCN [33] innovatively used CNN to model temporal features and achieved good results.


### 2.3. Gather Prediction

Gather prediction is an indispensable part of smart transportation, which includes many application scenarios, such as hotspot area analysis, passenger flow prediction, and population transfer prediction. Tomaharu et al. [34] proposed a collective graphical model to predict the transition populations between areas. Verma et al. [35] use trajectory data to mine hotspots and realized large-granularity gather prediction. Ni et al. [36] through passenger flow forecasting realized the gather prediction between cities. Kumar et al. [37] used trajectory clustering and similarity analysis for gather prediction. Gather prediction also can be transformed into a multitrajectory prediction task under the same time and space, which is focus on the time and space characteristics between multiple trajectories.


### 2.4. Trajectory Prediction

Different with other prediction tasks, the main features of trajectory prediction are geographic information and time information. Trajectory prediction can also use position semantics, speed, and direction. Based on the traditional probability, matrix factorization decomposes the matrix with a low-rank matrix to obtain the implicit feature vector of the user and the trajectory. Tensor factorization expands to three dimensions, including user, time information, and spatial information. Kurashima et al.’s [38] sampling is based on the subject and the distance between the user and the historical location. Liu et al. [39] combined location semantics to embed geographic context information. Research has shown that the sequence between consecutive trajectory points plays a vital role in trajectory prediction, and it is more significant in strong real-time trajectory data, because human behavior patterns are sequential. For prediction based on sequential data, the Markov chain model [40] is the most classic. Cheng et al. proposed a tensor-based model, named FPMC-LR [41], by fusing first-order Markov chains and distance constraints. Feng et al. proposed a personalized ranking metric embedding method (PRME) [42], which embeds the state at all times uniformly, and calculate the Euclidean distance between vectors to measure the similarity.Neural networks are widely used in various tasks because they can learn to model various nonlinear features. The ST-RNN proposed by Liu et al. (2016) is the first method to introduce a deep neural network into trajectory prediction, ST-RNN uses spatiotemporal information to expand RNN, and its effect is improved. STF-RNN replaced the transition matrix with the internal representation of automatically extracted spatiotemporal features, which can more effectively discover useful features related to model human behavior. Zhu et al. [43] considered modeling time intervals to improve performance and equipped LSTM with time gating. Yang et al. [44] used neural network models to model social network structure and user trajectory behavior patterns. HST-LSTM introduces spatiotemporal factors into the gates existing in LSTM to model spatiotemporal features.A recently proposed STGN considers the spatiotemporal context. Our proposed STGRU has the following differences from STGN. First, STGRU is extended based on GRU, which reduces the amount of parameters and is more suitable for real-time trajectories. STGN adds time and space gates to LSTM, and the amount of parameters is more than twice that of LSTM. Secondly, STGRU is equipped with external knowledge gate to extract the road network structure to enhance the spatiotemporal characteristics and the influence of external knowledge on the overall movement pattern. However, STGN is only based on the trajectory of a single user, and it is difficult to capture the spatiotemporal relationship between users.


## 2.1. Smart Transportation and Trajectory Data

Smart transportation is a major component of smart city. The main research difficulty is the analysis and decision-making reaction of traffic information.Traffic information analysis [18] includes traffic flow forecasting and traffic demand forecasting. Traffic flow forecasting [19, 20] and traffic congestion forecasting can help better regulate and control traffic and can effectively alleviate traffic congestion. The taxi demand forecasting method proposed by Geng et al. [21] can help taxi companies to better allocate vehicles. Li et al. [22] proposed a method for forecasting the demand for shared bicycles, which can optimize resource scheduling.Mining and analysis of trajectory data can assist in traffic planning decisions. Wei et al. [23] used the number of stops and the parking position to analyze the effectiveness of the main line coordination.


## 2.2. Spatiotemporal Data Modeling

On the other hand, trajectory data is a type of spatiotemporal data, with two dimensions of time and space. Data mining of spatiotemporal data is very difficult, and it is also one of the current research hotspots. The Markov chain-based model [24] is a classic sequence model. And deep learning methods [25] such as RNN, LSTM, and GRU have excellent results in time modeling. The method based on matrix factorization [26] or tensor factorization [27] can model spatial features. CNN [28, 29] and GCN [30] are currently the best spatial modeling methods.In order to capture the spatiotemporal features, Al-Molegi et al. (2016) proposed STF-RNN [31] to learn different temporal and spatial features. The TGCN [32] proposed by Zhao et al. uses GRU and GCN stacking to model spatiotemporal features. The STGCN [33] innovatively used CNN to model temporal features and achieved good results.


## 2.3. Gather Prediction

Gather prediction is an indispensable part of smart transportation, which includes many application scenarios, such as hotspot area analysis, passenger flow prediction, and population transfer prediction. Tomaharu et al. [34] proposed a collective graphical model to predict the transition populations between areas. Verma et al. [35] use trajectory data to mine hotspots and realized large-granularity gather prediction. Ni et al. [36] through passenger flow forecasting realized the gather prediction between cities. Kumar et al. [37] used trajectory clustering and similarity analysis for gather prediction. Gather prediction also can be transformed into a multitrajectory prediction task under the same time and space, which is focus on the time and space characteristics between multiple trajectories.


## 2.4. Trajectory Prediction

Different with other prediction tasks, the main features of trajectory prediction are geographic information and time information. Trajectory prediction can also use position semantics, speed, and direction. Based on the traditional probability, matrix factorization decomposes the matrix with a low-rank matrix to obtain the implicit feature vector of the user and the trajectory. Tensor factorization expands to three dimensions, including user, time information, and spatial information. Kurashima et al.’s [38] sampling is based on the subject and the distance between the user and the historical location. Liu et al. [39] combined location semantics to embed geographic context information. Research has shown that the sequence between consecutive trajectory points plays a vital role in trajectory prediction, and it is more significant in strong real-time trajectory data, because human behavior patterns are sequential. For prediction based on sequential data, the Markov chain model [40] is the most classic. Cheng et al. proposed a tensor-based model, named FPMC-LR [41], by fusing first-order Markov chains and distance constraints. Feng et al. proposed a personalized ranking metric embedding method (PRME) [42], which embeds the state at all times uniformly, and calculate the Euclidean distance between vectors to measure the similarity.Neural networks are widely used in various tasks because they can learn to model various nonlinear features. The ST-RNN proposed by Liu et al. (2016) is the first method to introduce a deep neural network into trajectory prediction, ST-RNN uses spatiotemporal information to expand RNN, and its effect is improved. STF-RNN replaced the transition matrix with the internal representation of automatically extracted spatiotemporal features, which can more effectively discover useful features related to model human behavior. Zhu et al. [43] considered modeling time intervals to improve performance and equipped LSTM with time gating. Yang et al. [44] used neural network models to model social network structure and user trajectory behavior patterns. HST-LSTM introduces spatiotemporal factors into the gates existing in LSTM to model spatiotemporal features.A recently proposed STGN considers the spatiotemporal context. Our proposed STGRU has the following differences from STGN. First, STGRU is extended based on GRU, which reduces the amount of parameters and is more suitable for real-time trajectories. STGN adds time and space gates to LSTM, and the amount of parameters is more than twice that of LSTM. Secondly, STGRU is equipped with external knowledge gate to extract the road network structure to enhance the spatiotemporal characteristics and the influence of external knowledge on the overall movement pattern. However, STGN is only based on the trajectory of a single user, and it is difficult to capture the spatiotemporal relationship between users.


## 3. Method

In this section, we firstly give the definitions of gather prediction and introduce preliminaries for GRU. Then, we propose Spatio-Temporal Gated Recurrent Unit (STGRU), which uses time and distance intervals and road network structure to model short-term and long-term behavior patterns of users.


### 3.1. Overview

As shown in Figure1, we perform trajectory prediction by stacking a STGRU layer and a softmax layer, then compare the result of trajectory prediction with the threshold η to obtain the result of gather prediction.Figure 1
Gather prediction network model based on STGRU.In our proposed Spatio-Temporal Gated Recurrent Unit, three gates are designed to extract spatiotemporal features and model user behavior patterns. The time gate and the distance gate can learn the time interval and distance interval in the trajectory, obtaining users’ short-term behavior patterns. The road network gate aims to capture road network structural features which have the impact on short-term and long-term behavioral patterns.In this paper, we only discuss the meshing method of dividing area, because meshing has the highest applicability. The STGRU model is also applicable to other dividing area methods, and has been echoed in comparative experiments.


### 3.2. Problem Formulation

LetU=u1,u2,⋯,uM be the set of M users. And according to the side length a, divide the city into a number of grids and number them, where each grid area is a2. Each grid corresponds to a unique area ID r. For user u, she has a sequence of historical regions visited up to time ti−1 represented as Hiu=rt1u,rt2u,⋯,rti−1u, where rtiu means the region user u visits at time ti.The goal of gather prediction is to predict the regions where all users are located at timeti. Specifically, the higher the prediction score sr,tiu of user u for the region r at time ti, means the higher probability that the user u would like to located in the region r at time ti.According to the prediction scores of all users, predictions ofM×k possible regions can be obtained. The number of people in the region r can be obtained by counting the prediction results. And the gather in the region r can be judged whether there the number is through the threshold η:(1)numberr,ti=∑u∈Usr,tiu,rstate=1,numberr,ti≥η0,numberr,ti<η,where rstate is the gather state of region r, 1 means there is clustering in the region r, 0 is not, and numberr,ti is the number of people in the region r at time ti.


### 3.3. Gated Recurrent Unit

GRU (Cho et al. 2014), a variant of LSTM, can also learn the long dependency problem in RNN networks. The structure of GRU is simpler than that of the LSTM network, while the effect is very good. In order to reduce the amount of parameters to be more in line with real-time data types, our method uses standard GRU as show in Figure2. Based on the standard LSTM network, GRU combines the forget gate and input gate of LSTM into a single update gate, removes the cell state, and uses the hidden state to transfer information. The basic update formula of GRU is as follows:(2)Rt=σWxrHt−1,Xt+br,(3)Zt=σWxzHt−1,Xt+bz,(4)H~t=tanhWxhXt+WhhRt⊙Ht−1+bh,(5)Ht=Zt⊙Ht−1+1−Zt⊙H~t.Figure 2
The standard GRU model.Assuming that the number of hidden units ish, the batch input Xt∈ℝn×d at given time step is t, and the hidden state of the previous time step is Ht−1. Rt,Zt∈ℝn×h represents the reset gate and update gate, where σ· is the logistic sigmoid function. H~t∈ℝn×h represents the candidate hidden state at time step t, where tanh· is the double tangent function. Wxr,Wxz,Wxh,Whr,Whz,Whh∈ℝd×h is the weights of gates. br,bz,bh is corresponding biases. And e represents for the element-wise (Hadamard) product.The reset gateRt controls how the hidden state of the previous time step flows into the candidate hidden state of the current time step and captures long-term dependencies in the time series. The update gate Zt can control how the hidden state should be updated by the candidate hidden state containing the current time step information and capture short-term dependencies in the time series.


### 3.4. Components

As shown in two dotted red rectangles in Figure3, STGRU have added time gate, distance gate, and road network gate, which are denoted as Tt, Dt, and Roadt, respectively. Tt and Dt are used to model the influence of time interval and distance interval on trajectory prediction, and Roadt is used to capture the influence of road network structure on behavior patterns. Based on GRU, time gate, distance gate, and road network gate equations are as follows:(6)Tt=σWxtXt+σΔttWt+bt,Dt=σWxdXt+σΔdtWd+bd,Roadt=σWxroadXt+σroadtWroad+broad.Figure 3
STGRU has time gate, distance gate and road network gate, i.e.,Tt, Dt, and Roadt.CombiningTt, Dt, and Roadt, the calculation equation for reset gate and update gate is added as(7)R~t=Rt⊙Roadt,Z~t=Zt⊙Tt⊙Dt⊙Roadt,then modify Eqs. (4) and (5) to(8)H~t=tanhWxhXt+WhhR~t⊙Ht−1+bh,Ht=Z~t⊙Ht−1+1−Z~t⊙H~t,where Δtt is the time interval and Δdt is the distance interval. rt represents road network information. Tt is equivalent to the time interval input information filter, Dt is equivalent to the distance interval input information filter, and Roadt is used to capture the input information of the road network structure. Calculate the influence of the road network gate on the reset gate and the influence of multiple gate controls on the update gate by adding a new reset gate state R~t and a new update gate state Z~t. The influence of the gates determines the influence on the hidden stateHt.The candidate hidden stateH~t is determined by input information, reset gate, and the hidden state of the previous time step. The second reset gate state R~t is designed to memory the user’s long-term road network access information. Roadt is used to memorize the road network information rt, then transferred to R~t, further to H~t, and help simulate the long-term behavior pattern of users.The update gateZt can capture short-term dependencies. Therefore, a time gate and a distance gate are designed, combined with the above road network gate to control update gate state. Tt memorizes the Δtt between the track points, referring to LSTM, and uses element-wise (Hadamard) product to incorporate it into the second update gate state Z~t. Similarly, Dt memorizes the Δdt between the track points, and Roadt memorizes the road network information and integrates it into Z~t. Modeling the distance interval can help capture the user’s spatial behavior patterns, and modeling the time interval can help capture the user’s behavior patterns such as speed and state. Modeling the road network structure can help capture users’ short-term behavior constraints and long-term goals, as well as capture the spatial relationships between users.The method of adapting the model for gather prediction is as follows. First, calculate the time interval and distance interval between track points, andHu can be converted to(9)r1u,0,0,r2u,t2u−t1u,dl1,l2,⋯,rnu,tnu−tn−1u,dln−1,ln.Secondly, add weather, holiday information, and road network information and further transform it into(10)rnu,weathern,daten,tnu−tn−1u,dln−1,ln,roadn,where rtu contains longitude, latitude, and located region; weathert contains the highest temperature, lowest temperature, and average temperature; and datet is marked with 0 or 1 according to whether the date is a holiday. Then, Xt in STGRU is equivalent to rtu,weathert,datet, Δtt is equivalent to ttu−tt−1u, and Δdt is equivalent to dlt−1,lt, where d·,· is the function that computes the distance between two track points. roadt is a vector, which is concatenated by the node where the trajectory point is located in the road network graph and the neighbor nodes. For example, the road segment where the trajectory point i is located represents nodei, and the c neighbor nodes of nodei are, respectively, represented as nodei+1,nodei+2,⋯,nodei+c. Then, roadt can be expressed as roadt=nodei,nodei+1,⋯,nodei+c. In addition, in order to extract the behavior pattern of the group, we performed a unified modeling for all users and deleted the user ID.This paper uses a single-layer network model for comparison experiments, adds softmax layer for output, and uses the loss function of categorical cross entropy:(11)J=−∑i=1Kyilogpi.Finally, the forecast results are counted in the same time and space. When the statistical value of a certain regionr exceeds the set threshold η, it is considered that this region will gather.


### 3.5. Analysis and Training

STGRU reduces the amount of model parameters. The parameter quantity of a single STGRU unit can be calculated as3×dh2+6×dh×dx+6×dh, where dn is the number of hidden units, and dx is the number of input units. Similarly, the unit parameter quantity of a LSTM unit can be calculated as 4dh2+4×dh×dx+4×dh. The GRU unit has one less gate than the LSTM unit, and the amount of parameters is also reduced accordingly, which can be calculated as 3×dh2+3×dh×dx+3×dh. The STGN model is the current SOTA method and is an improved model based on LSTM. The unit parameter of STGN can be calculated as 5×dh2+8×dh×dx+10×dh. The number of parameters of STGRU is slightly more than that of LSTM, which is one-third to one-half less than STGN.The optimizer use Adam, a variant of Stochastic Gradient Descent (SGD), which comprehensively considers the gradient’s first moment estimation (first moment estimation, the mean value of the gradient) and second moment estimation (second moment estimation), and calculates the update step length of parameters. It can automatically adjust the learning rate, and it is very suitable for large-scale data and parameter scenarios.


## 3.1. Overview

As shown in Figure1, we perform trajectory prediction by stacking a STGRU layer and a softmax layer, then compare the result of trajectory prediction with the threshold η to obtain the result of gather prediction.Figure 1
Gather prediction network model based on STGRU.In our proposed Spatio-Temporal Gated Recurrent Unit, three gates are designed to extract spatiotemporal features and model user behavior patterns. The time gate and the distance gate can learn the time interval and distance interval in the trajectory, obtaining users’ short-term behavior patterns. The road network gate aims to capture road network structural features which have the impact on short-term and long-term behavioral patterns.In this paper, we only discuss the meshing method of dividing area, because meshing has the highest applicability. The STGRU model is also applicable to other dividing area methods, and has been echoed in comparative experiments.


## 3.2. Problem Formulation

LetU=u1,u2,⋯,uM be the set of M users. And according to the side length a, divide the city into a number of grids and number them, where each grid area is a2. Each grid corresponds to a unique area ID r. For user u, she has a sequence of historical regions visited up to time ti−1 represented as Hiu=rt1u,rt2u,⋯,rti−1u, where rtiu means the region user u visits at time ti.The goal of gather prediction is to predict the regions where all users are located at timeti. Specifically, the higher the prediction score sr,tiu of user u for the region r at time ti, means the higher probability that the user u would like to located in the region r at time ti.According to the prediction scores of all users, predictions ofM×k possible regions can be obtained. The number of people in the region r can be obtained by counting the prediction results. And the gather in the region r can be judged whether there the number is through the threshold η:(1)numberr,ti=∑u∈Usr,tiu,rstate=1,numberr,ti≥η0,numberr,ti<η,where rstate is the gather state of region r, 1 means there is clustering in the region r, 0 is not, and numberr,ti is the number of people in the region r at time ti.


## 3.3. Gated Recurrent Unit

GRU (Cho et al. 2014), a variant of LSTM, can also learn the long dependency problem in RNN networks. The structure of GRU is simpler than that of the LSTM network, while the effect is very good. In order to reduce the amount of parameters to be more in line with real-time data types, our method uses standard GRU as show in Figure2. Based on the standard LSTM network, GRU combines the forget gate and input gate of LSTM into a single update gate, removes the cell state, and uses the hidden state to transfer information. The basic update formula of GRU is as follows:(2)Rt=σWxrHt−1,Xt+br,(3)Zt=σWxzHt−1,Xt+bz,(4)H~t=tanhWxhXt+WhhRt⊙Ht−1+bh,(5)Ht=Zt⊙Ht−1+1−Zt⊙H~t.Figure 2
The standard GRU model.Assuming that the number of hidden units ish, the batch input Xt∈ℝn×d at given time step is t, and the hidden state of the previous time step is Ht−1. Rt,Zt∈ℝn×h represents the reset gate and update gate, where σ· is the logistic sigmoid function. H~t∈ℝn×h represents the candidate hidden state at time step t, where tanh· is the double tangent function. Wxr,Wxz,Wxh,Whr,Whz,Whh∈ℝd×h is the weights of gates. br,bz,bh is corresponding biases. And e represents for the element-wise (Hadamard) product.The reset gateRt controls how the hidden state of the previous time step flows into the candidate hidden state of the current time step and captures long-term dependencies in the time series. The update gate Zt can control how the hidden state should be updated by the candidate hidden state containing the current time step information and capture short-term dependencies in the time series.


## 3.4. Components

As shown in two dotted red rectangles in Figure3, STGRU have added time gate, distance gate, and road network gate, which are denoted as Tt, Dt, and Roadt, respectively. Tt and Dt are used to model the influence of time interval and distance interval on trajectory prediction, and Roadt is used to capture the influence of road network structure on behavior patterns. Based on GRU, time gate, distance gate, and road network gate equations are as follows:(6)Tt=σWxtXt+σΔttWt+bt,Dt=σWxdXt+σΔdtWd+bd,Roadt=σWxroadXt+σroadtWroad+broad.Figure 3
STGRU has time gate, distance gate and road network gate, i.e.,Tt, Dt, and Roadt.CombiningTt, Dt, and Roadt, the calculation equation for reset gate and update gate is added as(7)R~t=Rt⊙Roadt,Z~t=Zt⊙Tt⊙Dt⊙Roadt,then modify Eqs. (4) and (5) to(8)H~t=tanhWxhXt+WhhR~t⊙Ht−1+bh,Ht=Z~t⊙Ht−1+1−Z~t⊙H~t,where Δtt is the time interval and Δdt is the distance interval. rt represents road network information. Tt is equivalent to the time interval input information filter, Dt is equivalent to the distance interval input information filter, and Roadt is used to capture the input information of the road network structure. Calculate the influence of the road network gate on the reset gate and the influence of multiple gate controls on the update gate by adding a new reset gate state R~t and a new update gate state Z~t. The influence of the gates determines the influence on the hidden stateHt.The candidate hidden stateH~t is determined by input information, reset gate, and the hidden state of the previous time step. The second reset gate state R~t is designed to memory the user’s long-term road network access information. Roadt is used to memorize the road network information rt, then transferred to R~t, further to H~t, and help simulate the long-term behavior pattern of users.The update gateZt can capture short-term dependencies. Therefore, a time gate and a distance gate are designed, combined with the above road network gate to control update gate state. Tt memorizes the Δtt between the track points, referring to LSTM, and uses element-wise (Hadamard) product to incorporate it into the second update gate state Z~t. Similarly, Dt memorizes the Δdt between the track points, and Roadt memorizes the road network information and integrates it into Z~t. Modeling the distance interval can help capture the user’s spatial behavior patterns, and modeling the time interval can help capture the user’s behavior patterns such as speed and state. Modeling the road network structure can help capture users’ short-term behavior constraints and long-term goals, as well as capture the spatial relationships between users.The method of adapting the model for gather prediction is as follows. First, calculate the time interval and distance interval between track points, andHu can be converted to(9)r1u,0,0,r2u,t2u−t1u,dl1,l2,⋯,rnu,tnu−tn−1u,dln−1,ln.Secondly, add weather, holiday information, and road network information and further transform it into(10)rnu,weathern,daten,tnu−tn−1u,dln−1,ln,roadn,where rtu contains longitude, latitude, and located region; weathert contains the highest temperature, lowest temperature, and average temperature; and datet is marked with 0 or 1 according to whether the date is a holiday. Then, Xt in STGRU is equivalent to rtu,weathert,datet, Δtt is equivalent to ttu−tt−1u, and Δdt is equivalent to dlt−1,lt, where d·,· is the function that computes the distance between two track points. roadt is a vector, which is concatenated by the node where the trajectory point is located in the road network graph and the neighbor nodes. For example, the road segment where the trajectory point i is located represents nodei, and the c neighbor nodes of nodei are, respectively, represented as nodei+1,nodei+2,⋯,nodei+c. Then, roadt can be expressed as roadt=nodei,nodei+1,⋯,nodei+c. In addition, in order to extract the behavior pattern of the group, we performed a unified modeling for all users and deleted the user ID.This paper uses a single-layer network model for comparison experiments, adds softmax layer for output, and uses the loss function of categorical cross entropy:(11)J=−∑i=1Kyilogpi.Finally, the forecast results are counted in the same time and space. When the statistical value of a certain regionr exceeds the set threshold η, it is considered that this region will gather.


## 3.5. Analysis and Training

STGRU reduces the amount of model parameters. The parameter quantity of a single STGRU unit can be calculated as3×dh2+6×dh×dx+6×dh, where dn is the number of hidden units, and dx is the number of input units. Similarly, the unit parameter quantity of a LSTM unit can be calculated as 4dh2+4×dh×dx+4×dh. The GRU unit has one less gate than the LSTM unit, and the amount of parameters is also reduced accordingly, which can be calculated as 3×dh2+3×dh×dx+3×dh. The STGN model is the current SOTA method and is an improved model based on LSTM. The unit parameter of STGN can be calculated as 5×dh2+8×dh×dx+10×dh. The number of parameters of STGRU is slightly more than that of LSTM, which is one-third to one-half less than STGN.The optimizer use Adam, a variant of Stochastic Gradient Descent (SGD), which comprehensively considers the gradient’s first moment estimation (first moment estimation, the mean value of the gradient) and second moment estimation (second moment estimation), and calculates the update step length of parameters. It can automatically adjust the learning rate, and it is very suitable for large-scale data and parameter scenarios.


## 4. Experiments

In this section, we conduct experiments to evaluate the performance of our proposed model STGRU on three real-world datasets.


### 4.1. Dataset

We evaluated our proposed method on three SNS-based people flow datasets released by Nightley and Center for Spatial Information Science at the University of Tokyo (CSIS). Each dataset contains trajectories, as detailed follows.(i)
Nagoya People Flow (NPF): NPF dataset contains the trajectories of 2387 users in the Nagoya area in 2013, with a total of 1,068,064 track points. The trajectory time is 6 days, which are July (7/22, 7/28), September (9/16, 9/22), and December (12/24, 12/29). Each trajectory starts from 0 : 00 to 23 : 55 of the current day, and the data interval is 5 minutes(ii)
Osaka People Flow (OPF): OPF dataset contains 4924 users in the Osaka area in 2013, and the covering time is July (7/22, 7/28), September (9/16, 9/22), and December (12/24, 12/29). The total number of track points is 2,552,883(iii)
Tokyo People Flow (TPF): TPF dataset is the largest of the three datasets and contains the trajectories of 11536 users amount of 6,883,245 track points in the Osaka area in 2013. The time is July, 2013 (7/1, 7/7), October (10/7, 10/13), and December (12/16, 12/22).We eliminate user data whose trajectory length was less than 30 in the three data sets and then take 70% of the users as the training set and the remaining 30% as the testing set.The three datasets do not contain the area information of the track points. This paper divides the area of the track according to5km×5km in each area and determines the area where the track points are located according to the latitude and longitude of the track points in the dataset. A sliding window is used to generate samples on both training and test data, and the time interval is randomized within the sliding window to increase the complexity of the trajectory.For example, if the time of the first track point is 8 : 00 am, the random interval is [7, 12, 18, 24, 30, 31]. Assuming the random number 3, then the time interval between the second track point and the first track point is 3×5min=15min, which the second track point times are 8 : 15 am.


### 4.2. Baseline Methods

We compare our proposed model STGRU with five representative methods for trajectory prediction.(i)
RNN [9]: it passes the state cyclically in its own network; so, it can accept a wider range of time series structure input and widely used for time series prediction tasks(ii)
LSTM [10]: this model is suitable for processing and predicting important events with very long intervals and delays in time series. To a certain extent, the problem of gradient disappearance and gradient explosion of RNN is solved(iii)
GRU [11]: a variant of the LSTM model, which has fewer parameters than LSTM and shows better performance on certain smaller and less frequent datasets(iv)
HST-LSTM [14]: it integrates spatiotemporal influence into the three gates of LSTM. Since there is no session information in the datasets, its ST-LSTM vision is used here(v)
STGN [15]: obtained by enhancing LSTM, introducing two pairs of spatiotemporal gates to capture spatiotemporal relationships


### 4.3. Evaluation Metrics

In order to evaluate the performance of our proposed STGRU model and compare it with the above five baselines, we used two standard metrics area under curve (AUC) and Recall@K. The trajectory prediction task is essentially a multiclassification task, and AUC metrics can better evaluate the classification effect. Recall@K is defined as the ratio of the number of correct predictions to the total number of predictions. First, all possible regions are arranged in descending order according to their probability. Then, the recall score is calculated as the percentage of the number of times the true region is found among the top K most likely regions. In this paper, use K=1, 5, 10, 15, and 20 to illustrate different results of Recall@K. U is the set of users, Lu represents the set of real regions of user u in the testing data, and PK,u denotes the set of top K predicted regions; the calculation formula for Recall@K is:(12)Recall@K=1∣U∣∑u∈U∣Lu∩PK,u∣∣Lu∣.


### 4.4. Results and Discussions

#### 4.4.1. Method Comparison

Table1 shows the performance of our proposed model STGRU and the performance of the six baselines evaluated by Recall@K and AUC on three datasets. The hidden state size is set to 32 in our experiment, the number of epochs is set to 200, and the batch size is set to 512. The sliding window size is set to 10, and the random time interval in the Nagoya dataset and the Osaka dataset is 1 to 3. The random time interval of the Tokyo dataset is 1 to 5, because the data density in the Tokyo data set is higher, and needs to increase the complexity of the data by increasing the random interval. To be fair, all baseline experiments in this paper use the same hyperparameter settings.Table 1
Evaluation of prediction results in terms of Recall@K and AUC on three datasets.
(a)NPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.04280.16770.28940.43000.6951GRU0.07120.23720.34210.47710.7778RNN0.08090.25800.35700.48650.8018ST-LSTM0.06210.24380.36630.50500.7976STGN0.07620.27280.37340.50610.8177STGRU0.09200.28290.38910.52310.8290(b)OPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.03830.16380.26340.43750.7140GRU0.04550.19790.30070.46560.7611RNN0.05880.22580.32600.48810.8324ST-LSTM0.05020.21070.31740.48900.7817STGN0.06330.16990.28330.49200.8292STGRU0.06810.24390.34640.51160.8545(c)TPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.07520.33310.48490.64280.8317GRU0.07890.33190.47930.63840.8451RNN0.08560.36340.50660.65610.8645ST-LSTM0.08640.36990.52130.66820.8727STGN0.09000.33270.51030.66720.8734STGRU0.09330.37950.52630.67300.8755From the experimental results, the following observations can be obtained: The STGRU model we proposed is significantly better than the existing state-of-the-art methods in all indicators of the three datasets. The performance gains provided by STGRU over these five counterparts are about 18.1%-110.2%, 5.7%-74.7%, and 3.7%-24.1% in terms of Recall@1 metric in Nagoya, Osaka, and Tokyo datasets, respectively. The results show that the mechanism of modeling the road network structure in STGRU can better model user behavior patterns, modeling short-term temporal and spatial contexts improves the effect on strong real-time data, and is effective for the task of trajectory prediction. That is because the added road network gate is combined with the update gate to integrate the short-term road network characteristics into the model, and the reset gate is combined to integrate the long-term road network characteristics.In addition, the performance of RNN on the three datasets is better than LSTM. This is because RNN has the characteristics of short-term memory. The closer the time, the greater the weight of track points. Even if the random intervals are added, the obtained samples still have strong real-time performance; so, the performance of RNN is better. Similarly, GRU is superior to LSTM in modeling strong real-time data. The performance of HST-LSTM and STGN is better than the above three models, which proves the importance of spatiotemporal factors to track prediction. Among them, the performance of STGN is better than HST-LSTM, which proves that the method of obtaining spatiotemporal effects through specific gates is more effective than improving on the basis of LSTM gates. The reason may be the increase of the parameters.In the three datasets, each dataset covers a total of 6 days of trajectory data in an area of Japan, and the time interval between adjacent track points is 5 minutes. Each area can be divided into about 5000 to 10000 regions. Taking the NPF dataset as an example, the number of regions is about 5000. It can be calculated that the size of the spatiotemporal matrix of the dataset is about5000×3000. However, the number of trajectory points in the NPF dataset is only one million. After removing the repeated spatiotemporal regions, the size of the track point coverage matrix is less than 1% of the size of the spatiotemporal matrix of the dataset. RNN, LSTM, and GRU are directly trained on the spatiotemporal matrix, which will lead to the problems of data sparsity. STGRU adds constraints between track points through time intervals, distance intervals, and road network structure. While the STGRU is being trained, only the local area covered by each sample needs to be considered, which greatly alleviates the problems of data sparsity in the dataset and can better model user behavior patterns compared to the above three models.


#### 4.4.2. Impact of Parameters

In the standard RNN, different cell sizes will lead to different performance. They studied the impact of cell size on STGRU. Observe the impact of different cell sizes on model performance by changing the cell size to 32, 64, 128, 256, and 512. It can be seen from Table2 that increasing the cell size to a certain extent can improve the performance of the model. Large cell size will increase the training time and result a decline in performance. When the number of model units is determined, the cell size determines the complexity of the model, and a larger cell size may fit the data better.Table 2
The performance with different cell sizes.
Cell sizeRecall@1Recall@5Recall@10Recall@20320.09330.37950.52630.6730640.09220.38360.52530.67541280.09420.37740.52170.67362560.09230.37610.52380.67045120.09130.37600.51900.6658


### 4.5. Ablation Experiment

#### 4.5.1. Effectiveness of Time and Distance Gates

STGRU has a time gate and a distance gate combined with update gate to capture short-term dependencies. The effectiveness of time and distance gates on modeling time and distance intervals is important. The time gate and distance gate can be closed by setTt=1 and Dt=1. In order to eliminate the interference of road network gates, the road network gate in STGRU was also closed. There are three sets of experiments, respectively, closing the time gate and the distance gate and closing both two gates at the same time to compare and verify the effectiveness of the time gate and the distance gate.From Table3, it can be found that time gate and distance gate have similar importance on the datasets. Compared with GRU, the performance improvement of GRU+Dt+Tt on the four evaluation metrics is 27.67%, 18.04%, 11.22%, and 7.23%, respectively. And the performance difference between GRU+Tt and GRU+Dt is very small, indicating that the distance interval and time interval have similar effects on modeling behavior patterns. And the performance improvement of GRU+Dt+Tt is small, indicating that there is a large degree of overlap in the characteristics of the time interval and the distance interval on the testing dataset.Table 3
The performance with different times and distance gates.
NPFRecall@1Recall@5Recall@10Recall@20GRU0.07120.23720.34210.4771GRU+Dt0.08870.27630.37780.5080GRU+Tt0.08440.27440.37730.5099GRU+Dt+Tt0.09090.28010.38050.5116


#### 4.5.2. Effectiveness of Road Network Gates

There is a road network gate in STGRU, which is integrated with the update gate and the reset gate to capture long-term and short-term road network dependencies. The motivation of this group is to study the role of road network gates in the update gate and reset gate through experiments. The road network gate can be closed by settingRoadt=1 in R~t and Z~t, respectively. The effectiveness of the road network gate in capturing long-term and short-term dependencies can be verified by setting up three sets of experiments, namely, closing all road network gates and closing a single road network gate.As shown in Table4, the performance of closing a single road network gate is not as good as closing all road network gates. This may be due to the long-term features and short-term features of the road network structure that need to be used together. The closing of a single road network will cause the road network information to be invalid for the prediction result. At the same time, some parameters are used to model the characteristics of the road network, which will cause the performance of the model to decrease. Therefore, the performance of closing one road network gate alone is almost the same.Table 4
The performance with different set of road network gates.
NPFRecall@1Recall@5Recall@10Recall@20STGRU−Rt0.09090.28010.38050.5116STGRU−R2t0.08670.27760.37860.5101STGRU−R1t0.08620.27950.37960.5093STGRU0.09200.28290.38910.5231


#### 4.5.3. Impact of the Sliding Window Size

In our experiment, samples are obtained through a sliding window. The size of the sliding window limits the trajectory length of a single input. In order to compare the performance of our model in different size sliding windows, the sliding windows are set to different lengths to observe the impact, respectively, 10, 15, 20, 25, and 30. In order to ensure the number of samples under a larger sliding window size, it conducts experiments on the Tokyo People Flow dataset, because the dataset has the longest average trajectory length.The size of the sample length determines the length of the model unit, as well as the parameters of the model. As shown in Table5, as the length of the sliding window increases and the amount of model parameters increases, the overall performance of the model has a certain improvement. When the sliding window size is set to 30, the model complexity is 3 times that when the sliding window size is 10, the performance improvement of the four metrics increases are 8.68%, -4.85%, 11%, and 3.37%, respectively. Although the increase of the sample length can improve the performance of the model, it is necessary to consider the actually application scenarios of the gather prediction task. The sample length within 10 is more meaningful, and this is also the main reason that the sliding window size is set to 10 in our comparison experiment with the baselines.Table 5
The performance with different window sizes.
Window sizeRecall@1Recall@5Recall@10Recall@20100.09330.37950.52630.6730150.09290.38970.53310.6828200.09490.36240.51740.6786250.09050.37940.52670.6831300.10140.36110.58420.6957


#### 4.5.4. Impact of the Random Interval Size

Another important parameter is the size of the random interval. Increase the complexity of the trajectory samples by randomly sampling of the time interval between the track points in the sliding window. For comparison, the impact of different random intervals on the complexity of the trajectory sample and the performance of the model sets up different random intervals on the Tokyo People Flow dataset for comparison experiments and sets the random interval sizes to 3, 5, 7, 9, and 11, respectively. Choose the Tokyo People Flow dataset which the continuity in the dataset is strong, and a certain degree of complexity is required to better reflect the purpose of the experiment.According to Table6, it can be see that the model performance is the best when the random interval size is 5 and 7, and the random interval size that is too large and too small will cause the model performance to decrease. On the other two datasets, the model performance is better when the random interval size is 3, which is why the three data sets use different random intervals in the comparison experiment with the baselines. Using random intervals can make the sample closer to the data in the real world.Table 6
The performance with different random interval sizes.
Rand intervalRecall@1Recall@5Recall@10Recall@2030.08890.37250.51480.663650.09330.37950.52630.673070.09200.38350.53000.677690.08220.36770.51960.6752110.07470.35120.51040.6702


### 4.6. Case Study

The purpose of verifying the STGRU model is that it can process and predict short trajectory data and long trajectory data, which conducted two sets of experiments with the baseline models. If the user’s trajectory data is scarce, it means that it can hardly understand the user’s behavior pattern, which requires higher performance of the model. The experiments are based on the Tokyo People Flow dataset, taking data with a track length of less than 30 for calculation, without random intervals, and userecall@k as the evaluation metrics. As shown in Figure 4, STGRU has the best performance on recall@1 and recall@5, which proves that STGRU can better handle sparse data.Figure 4
The performance on trajectory data length is less than 30.In another set of experiments, data with track length greater than 200 was obtained and followed the parameter settings of the comparative experiment. As shown in Figure5, STGRU is also superior to all baselines on long trajectory data, which proves that STGRU can extract and use long-term features very well, especially the effectiveness of long-term road network features for modeling strong real-time data.Figure 5
The performance on trajectory data length is greater than 200.


## 4.1. Dataset

We evaluated our proposed method on three SNS-based people flow datasets released by Nightley and Center for Spatial Information Science at the University of Tokyo (CSIS). Each dataset contains trajectories, as detailed follows.(i)
Nagoya People Flow (NPF): NPF dataset contains the trajectories of 2387 users in the Nagoya area in 2013, with a total of 1,068,064 track points. The trajectory time is 6 days, which are July (7/22, 7/28), September (9/16, 9/22), and December (12/24, 12/29). Each trajectory starts from 0 : 00 to 23 : 55 of the current day, and the data interval is 5 minutes(ii)
Osaka People Flow (OPF): OPF dataset contains 4924 users in the Osaka area in 2013, and the covering time is July (7/22, 7/28), September (9/16, 9/22), and December (12/24, 12/29). The total number of track points is 2,552,883(iii)
Tokyo People Flow (TPF): TPF dataset is the largest of the three datasets and contains the trajectories of 11536 users amount of 6,883,245 track points in the Osaka area in 2013. The time is July, 2013 (7/1, 7/7), October (10/7, 10/13), and December (12/16, 12/22).We eliminate user data whose trajectory length was less than 30 in the three data sets and then take 70% of the users as the training set and the remaining 30% as the testing set.The three datasets do not contain the area information of the track points. This paper divides the area of the track according to5km×5km in each area and determines the area where the track points are located according to the latitude and longitude of the track points in the dataset. A sliding window is used to generate samples on both training and test data, and the time interval is randomized within the sliding window to increase the complexity of the trajectory.For example, if the time of the first track point is 8 : 00 am, the random interval is [7, 12, 18, 24, 30, 31]. Assuming the random number 3, then the time interval between the second track point and the first track point is 3×5min=15min, which the second track point times are 8 : 15 am.


## 4.2. Baseline Methods

We compare our proposed model STGRU with five representative methods for trajectory prediction.(i)
RNN [9]: it passes the state cyclically in its own network; so, it can accept a wider range of time series structure input and widely used for time series prediction tasks(ii)
LSTM [10]: this model is suitable for processing and predicting important events with very long intervals and delays in time series. To a certain extent, the problem of gradient disappearance and gradient explosion of RNN is solved(iii)
GRU [11]: a variant of the LSTM model, which has fewer parameters than LSTM and shows better performance on certain smaller and less frequent datasets(iv)
HST-LSTM [14]: it integrates spatiotemporal influence into the three gates of LSTM. Since there is no session information in the datasets, its ST-LSTM vision is used here(v)
STGN [15]: obtained by enhancing LSTM, introducing two pairs of spatiotemporal gates to capture spatiotemporal relationships


## 4.3. Evaluation Metrics

In order to evaluate the performance of our proposed STGRU model and compare it with the above five baselines, we used two standard metrics area under curve (AUC) and Recall@K. The trajectory prediction task is essentially a multiclassification task, and AUC metrics can better evaluate the classification effect. Recall@K is defined as the ratio of the number of correct predictions to the total number of predictions. First, all possible regions are arranged in descending order according to their probability. Then, the recall score is calculated as the percentage of the number of times the true region is found among the top K most likely regions. In this paper, use K=1, 5, 10, 15, and 20 to illustrate different results of Recall@K. U is the set of users, Lu represents the set of real regions of user u in the testing data, and PK,u denotes the set of top K predicted regions; the calculation formula for Recall@K is:(12)Recall@K=1∣U∣∑u∈U∣Lu∩PK,u∣∣Lu∣.


## 4.4. Results and Discussions

### 4.4.1. Method Comparison

Table1 shows the performance of our proposed model STGRU and the performance of the six baselines evaluated by Recall@K and AUC on three datasets. The hidden state size is set to 32 in our experiment, the number of epochs is set to 200, and the batch size is set to 512. The sliding window size is set to 10, and the random time interval in the Nagoya dataset and the Osaka dataset is 1 to 3. The random time interval of the Tokyo dataset is 1 to 5, because the data density in the Tokyo data set is higher, and needs to increase the complexity of the data by increasing the random interval. To be fair, all baseline experiments in this paper use the same hyperparameter settings.Table 1
Evaluation of prediction results in terms of Recall@K and AUC on three datasets.
(a)NPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.04280.16770.28940.43000.6951GRU0.07120.23720.34210.47710.7778RNN0.08090.25800.35700.48650.8018ST-LSTM0.06210.24380.36630.50500.7976STGN0.07620.27280.37340.50610.8177STGRU0.09200.28290.38910.52310.8290(b)OPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.03830.16380.26340.43750.7140GRU0.04550.19790.30070.46560.7611RNN0.05880.22580.32600.48810.8324ST-LSTM0.05020.21070.31740.48900.7817STGN0.06330.16990.28330.49200.8292STGRU0.06810.24390.34640.51160.8545(c)TPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.07520.33310.48490.64280.8317GRU0.07890.33190.47930.63840.8451RNN0.08560.36340.50660.65610.8645ST-LSTM0.08640.36990.52130.66820.8727STGN0.09000.33270.51030.66720.8734STGRU0.09330.37950.52630.67300.8755From the experimental results, the following observations can be obtained: The STGRU model we proposed is significantly better than the existing state-of-the-art methods in all indicators of the three datasets. The performance gains provided by STGRU over these five counterparts are about 18.1%-110.2%, 5.7%-74.7%, and 3.7%-24.1% in terms of Recall@1 metric in Nagoya, Osaka, and Tokyo datasets, respectively. The results show that the mechanism of modeling the road network structure in STGRU can better model user behavior patterns, modeling short-term temporal and spatial contexts improves the effect on strong real-time data, and is effective for the task of trajectory prediction. That is because the added road network gate is combined with the update gate to integrate the short-term road network characteristics into the model, and the reset gate is combined to integrate the long-term road network characteristics.In addition, the performance of RNN on the three datasets is better than LSTM. This is because RNN has the characteristics of short-term memory. The closer the time, the greater the weight of track points. Even if the random intervals are added, the obtained samples still have strong real-time performance; so, the performance of RNN is better. Similarly, GRU is superior to LSTM in modeling strong real-time data. The performance of HST-LSTM and STGN is better than the above three models, which proves the importance of spatiotemporal factors to track prediction. Among them, the performance of STGN is better than HST-LSTM, which proves that the method of obtaining spatiotemporal effects through specific gates is more effective than improving on the basis of LSTM gates. The reason may be the increase of the parameters.In the three datasets, each dataset covers a total of 6 days of trajectory data in an area of Japan, and the time interval between adjacent track points is 5 minutes. Each area can be divided into about 5000 to 10000 regions. Taking the NPF dataset as an example, the number of regions is about 5000. It can be calculated that the size of the spatiotemporal matrix of the dataset is about5000×3000. However, the number of trajectory points in the NPF dataset is only one million. After removing the repeated spatiotemporal regions, the size of the track point coverage matrix is less than 1% of the size of the spatiotemporal matrix of the dataset. RNN, LSTM, and GRU are directly trained on the spatiotemporal matrix, which will lead to the problems of data sparsity. STGRU adds constraints between track points through time intervals, distance intervals, and road network structure. While the STGRU is being trained, only the local area covered by each sample needs to be considered, which greatly alleviates the problems of data sparsity in the dataset and can better model user behavior patterns compared to the above three models.


### 4.4.2. Impact of Parameters

In the standard RNN, different cell sizes will lead to different performance. They studied the impact of cell size on STGRU. Observe the impact of different cell sizes on model performance by changing the cell size to 32, 64, 128, 256, and 512. It can be seen from Table2 that increasing the cell size to a certain extent can improve the performance of the model. Large cell size will increase the training time and result a decline in performance. When the number of model units is determined, the cell size determines the complexity of the model, and a larger cell size may fit the data better.Table 2
The performance with different cell sizes.
Cell sizeRecall@1Recall@5Recall@10Recall@20320.09330.37950.52630.6730640.09220.38360.52530.67541280.09420.37740.52170.67362560.09230.37610.52380.67045120.09130.37600.51900.6658


## 4.4.1. Method Comparison

Table1 shows the performance of our proposed model STGRU and the performance of the six baselines evaluated by Recall@K and AUC on three datasets. The hidden state size is set to 32 in our experiment, the number of epochs is set to 200, and the batch size is set to 512. The sliding window size is set to 10, and the random time interval in the Nagoya dataset and the Osaka dataset is 1 to 3. The random time interval of the Tokyo dataset is 1 to 5, because the data density in the Tokyo data set is higher, and needs to increase the complexity of the data by increasing the random interval. To be fair, all baseline experiments in this paper use the same hyperparameter settings.Table 1
Evaluation of prediction results in terms of Recall@K and AUC on three datasets.
(a)NPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.04280.16770.28940.43000.6951GRU0.07120.23720.34210.47710.7778RNN0.08090.25800.35700.48650.8018ST-LSTM0.06210.24380.36630.50500.7976STGN0.07620.27280.37340.50610.8177STGRU0.09200.28290.38910.52310.8290(b)OPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.03830.16380.26340.43750.7140GRU0.04550.19790.30070.46560.7611RNN0.05880.22580.32600.48810.8324ST-LSTM0.05020.21070.31740.48900.7817STGN0.06330.16990.28330.49200.8292STGRU0.06810.24390.34640.51160.8545(c)TPFRecall@1Recall@5Recall@10Recall@20AUCLSTM0.07520.33310.48490.64280.8317GRU0.07890.33190.47930.63840.8451RNN0.08560.36340.50660.65610.8645ST-LSTM0.08640.36990.52130.66820.8727STGN0.09000.33270.51030.66720.8734STGRU0.09330.37950.52630.67300.8755From the experimental results, the following observations can be obtained: The STGRU model we proposed is significantly better than the existing state-of-the-art methods in all indicators of the three datasets. The performance gains provided by STGRU over these five counterparts are about 18.1%-110.2%, 5.7%-74.7%, and 3.7%-24.1% in terms of Recall@1 metric in Nagoya, Osaka, and Tokyo datasets, respectively. The results show that the mechanism of modeling the road network structure in STGRU can better model user behavior patterns, modeling short-term temporal and spatial contexts improves the effect on strong real-time data, and is effective for the task of trajectory prediction. That is because the added road network gate is combined with the update gate to integrate the short-term road network characteristics into the model, and the reset gate is combined to integrate the long-term road network characteristics.In addition, the performance of RNN on the three datasets is better than LSTM. This is because RNN has the characteristics of short-term memory. The closer the time, the greater the weight of track points. Even if the random intervals are added, the obtained samples still have strong real-time performance; so, the performance of RNN is better. Similarly, GRU is superior to LSTM in modeling strong real-time data. The performance of HST-LSTM and STGN is better than the above three models, which proves the importance of spatiotemporal factors to track prediction. Among them, the performance of STGN is better than HST-LSTM, which proves that the method of obtaining spatiotemporal effects through specific gates is more effective than improving on the basis of LSTM gates. The reason may be the increase of the parameters.In the three datasets, each dataset covers a total of 6 days of trajectory data in an area of Japan, and the time interval between adjacent track points is 5 minutes. Each area can be divided into about 5000 to 10000 regions. Taking the NPF dataset as an example, the number of regions is about 5000. It can be calculated that the size of the spatiotemporal matrix of the dataset is about5000×3000. However, the number of trajectory points in the NPF dataset is only one million. After removing the repeated spatiotemporal regions, the size of the track point coverage matrix is less than 1% of the size of the spatiotemporal matrix of the dataset. RNN, LSTM, and GRU are directly trained on the spatiotemporal matrix, which will lead to the problems of data sparsity. STGRU adds constraints between track points through time intervals, distance intervals, and road network structure. While the STGRU is being trained, only the local area covered by each sample needs to be considered, which greatly alleviates the problems of data sparsity in the dataset and can better model user behavior patterns compared to the above three models.


## 4.4.2. Impact of Parameters

In the standard RNN, different cell sizes will lead to different performance. They studied the impact of cell size on STGRU. Observe the impact of different cell sizes on model performance by changing the cell size to 32, 64, 128, 256, and 512. It can be seen from Table2 that increasing the cell size to a certain extent can improve the performance of the model. Large cell size will increase the training time and result a decline in performance. When the number of model units is determined, the cell size determines the complexity of the model, and a larger cell size may fit the data better.Table 2
The performance with different cell sizes.
Cell sizeRecall@1Recall@5Recall@10Recall@20320.09330.37950.52630.6730640.09220.38360.52530.67541280.09420.37740.52170.67362560.09230.37610.52380.67045120.09130.37600.51900.6658


## 4.5. Ablation Experiment

### 4.5.1. Effectiveness of Time and Distance Gates

STGRU has a time gate and a distance gate combined with update gate to capture short-term dependencies. The effectiveness of time and distance gates on modeling time and distance intervals is important. The time gate and distance gate can be closed by setTt=1 and Dt=1. In order to eliminate the interference of road network gates, the road network gate in STGRU was also closed. There are three sets of experiments, respectively, closing the time gate and the distance gate and closing both two gates at the same time to compare and verify the effectiveness of the time gate and the distance gate.From Table3, it can be found that time gate and distance gate have similar importance on the datasets. Compared with GRU, the performance improvement of GRU+Dt+Tt on the four evaluation metrics is 27.67%, 18.04%, 11.22%, and 7.23%, respectively. And the performance difference between GRU+Tt and GRU+Dt is very small, indicating that the distance interval and time interval have similar effects on modeling behavior patterns. And the performance improvement of GRU+Dt+Tt is small, indicating that there is a large degree of overlap in the characteristics of the time interval and the distance interval on the testing dataset.Table 3
The performance with different times and distance gates.
NPFRecall@1Recall@5Recall@10Recall@20GRU0.07120.23720.34210.4771GRU+Dt0.08870.27630.37780.5080GRU+Tt0.08440.27440.37730.5099GRU+Dt+Tt0.09090.28010.38050.5116


### 4.5.2. Effectiveness of Road Network Gates

There is a road network gate in STGRU, which is integrated with the update gate and the reset gate to capture long-term and short-term road network dependencies. The motivation of this group is to study the role of road network gates in the update gate and reset gate through experiments. The road network gate can be closed by settingRoadt=1 in R~t and Z~t, respectively. The effectiveness of the road network gate in capturing long-term and short-term dependencies can be verified by setting up three sets of experiments, namely, closing all road network gates and closing a single road network gate.As shown in Table4, the performance of closing a single road network gate is not as good as closing all road network gates. This may be due to the long-term features and short-term features of the road network structure that need to be used together. The closing of a single road network will cause the road network information to be invalid for the prediction result. At the same time, some parameters are used to model the characteristics of the road network, which will cause the performance of the model to decrease. Therefore, the performance of closing one road network gate alone is almost the same.Table 4
The performance with different set of road network gates.
NPFRecall@1Recall@5Recall@10Recall@20STGRU−Rt0.09090.28010.38050.5116STGRU−R2t0.08670.27760.37860.5101STGRU−R1t0.08620.27950.37960.5093STGRU0.09200.28290.38910.5231


### 4.5.3. Impact of the Sliding Window Size

In our experiment, samples are obtained through a sliding window. The size of the sliding window limits the trajectory length of a single input. In order to compare the performance of our model in different size sliding windows, the sliding windows are set to different lengths to observe the impact, respectively, 10, 15, 20, 25, and 30. In order to ensure the number of samples under a larger sliding window size, it conducts experiments on the Tokyo People Flow dataset, because the dataset has the longest average trajectory length.The size of the sample length determines the length of the model unit, as well as the parameters of the model. As shown in Table5, as the length of the sliding window increases and the amount of model parameters increases, the overall performance of the model has a certain improvement. When the sliding window size is set to 30, the model complexity is 3 times that when the sliding window size is 10, the performance improvement of the four metrics increases are 8.68%, -4.85%, 11%, and 3.37%, respectively. Although the increase of the sample length can improve the performance of the model, it is necessary to consider the actually application scenarios of the gather prediction task. The sample length within 10 is more meaningful, and this is also the main reason that the sliding window size is set to 10 in our comparison experiment with the baselines.Table 5
The performance with different window sizes.
Window sizeRecall@1Recall@5Recall@10Recall@20100.09330.37950.52630.6730150.09290.38970.53310.6828200.09490.36240.51740.6786250.09050.37940.52670.6831300.10140.36110.58420.6957


### 4.5.4. Impact of the Random Interval Size

Another important parameter is the size of the random interval. Increase the complexity of the trajectory samples by randomly sampling of the time interval between the track points in the sliding window. For comparison, the impact of different random intervals on the complexity of the trajectory sample and the performance of the model sets up different random intervals on the Tokyo People Flow dataset for comparison experiments and sets the random interval sizes to 3, 5, 7, 9, and 11, respectively. Choose the Tokyo People Flow dataset which the continuity in the dataset is strong, and a certain degree of complexity is required to better reflect the purpose of the experiment.According to Table6, it can be see that the model performance is the best when the random interval size is 5 and 7, and the random interval size that is too large and too small will cause the model performance to decrease. On the other two datasets, the model performance is better when the random interval size is 3, which is why the three data sets use different random intervals in the comparison experiment with the baselines. Using random intervals can make the sample closer to the data in the real world.Table 6
The performance with different random interval sizes.
Rand intervalRecall@1Recall@5Recall@10Recall@2030.08890.37250.51480.663650.09330.37950.52630.673070.09200.38350.53000.677690.08220.36770.51960.6752110.07470.35120.51040.6702


## 4.5.1. Effectiveness of Time and Distance Gates

STGRU has a time gate and a distance gate combined with update gate to capture short-term dependencies. The effectiveness of time and distance gates on modeling time and distance intervals is important. The time gate and distance gate can be closed by setTt=1 and Dt=1. In order to eliminate the interference of road network gates, the road network gate in STGRU was also closed. There are three sets of experiments, respectively, closing the time gate and the distance gate and closing both two gates at the same time to compare and verify the effectiveness of the time gate and the distance gate.From Table3, it can be found that time gate and distance gate have similar importance on the datasets. Compared with GRU, the performance improvement of GRU+Dt+Tt on the four evaluation metrics is 27.67%, 18.04%, 11.22%, and 7.23%, respectively. And the performance difference between GRU+Tt and GRU+Dt is very small, indicating that the distance interval and time interval have similar effects on modeling behavior patterns. And the performance improvement of GRU+Dt+Tt is small, indicating that there is a large degree of overlap in the characteristics of the time interval and the distance interval on the testing dataset.Table 3
The performance with different times and distance gates.
NPFRecall@1Recall@5Recall@10Recall@20GRU0.07120.23720.34210.4771GRU+Dt0.08870.27630.37780.5080GRU+Tt0.08440.27440.37730.5099GRU+Dt+Tt0.09090.28010.38050.5116


## 4.5.2. Effectiveness of Road Network Gates

There is a road network gate in STGRU, which is integrated with the update gate and the reset gate to capture long-term and short-term road network dependencies. The motivation of this group is to study the role of road network gates in the update gate and reset gate through experiments. The road network gate can be closed by settingRoadt=1 in R~t and Z~t, respectively. The effectiveness of the road network gate in capturing long-term and short-term dependencies can be verified by setting up three sets of experiments, namely, closing all road network gates and closing a single road network gate.As shown in Table4, the performance of closing a single road network gate is not as good as closing all road network gates. This may be due to the long-term features and short-term features of the road network structure that need to be used together. The closing of a single road network will cause the road network information to be invalid for the prediction result. At the same time, some parameters are used to model the characteristics of the road network, which will cause the performance of the model to decrease. Therefore, the performance of closing one road network gate alone is almost the same.Table 4
The performance with different set of road network gates.
NPFRecall@1Recall@5Recall@10Recall@20STGRU−Rt0.09090.28010.38050.5116STGRU−R2t0.08670.27760.37860.5101STGRU−R1t0.08620.27950.37960.5093STGRU0.09200.28290.38910.5231


## 4.5.3. Impact of the Sliding Window Size

In our experiment, samples are obtained through a sliding window. The size of the sliding window limits the trajectory length of a single input. In order to compare the performance of our model in different size sliding windows, the sliding windows are set to different lengths to observe the impact, respectively, 10, 15, 20, 25, and 30. In order to ensure the number of samples under a larger sliding window size, it conducts experiments on the Tokyo People Flow dataset, because the dataset has the longest average trajectory length.The size of the sample length determines the length of the model unit, as well as the parameters of the model. As shown in Table5, as the length of the sliding window increases and the amount of model parameters increases, the overall performance of the model has a certain improvement. When the sliding window size is set to 30, the model complexity is 3 times that when the sliding window size is 10, the performance improvement of the four metrics increases are 8.68%, -4.85%, 11%, and 3.37%, respectively. Although the increase of the sample length can improve the performance of the model, it is necessary to consider the actually application scenarios of the gather prediction task. The sample length within 10 is more meaningful, and this is also the main reason that the sliding window size is set to 10 in our comparison experiment with the baselines.Table 5
The performance with different window sizes.
Window sizeRecall@1Recall@5Recall@10Recall@20100.09330.37950.52630.6730150.09290.38970.53310.6828200.09490.36240.51740.6786250.09050.37940.52670.6831300.10140.36110.58420.6957


## 4.5.4. Impact of the Random Interval Size

Another important parameter is the size of the random interval. Increase the complexity of the trajectory samples by randomly sampling of the time interval between the track points in the sliding window. For comparison, the impact of different random intervals on the complexity of the trajectory sample and the performance of the model sets up different random intervals on the Tokyo People Flow dataset for comparison experiments and sets the random interval sizes to 3, 5, 7, 9, and 11, respectively. Choose the Tokyo People Flow dataset which the continuity in the dataset is strong, and a certain degree of complexity is required to better reflect the purpose of the experiment.According to Table6, it can be see that the model performance is the best when the random interval size is 5 and 7, and the random interval size that is too large and too small will cause the model performance to decrease. On the other two datasets, the model performance is better when the random interval size is 3, which is why the three data sets use different random intervals in the comparison experiment with the baselines. Using random intervals can make the sample closer to the data in the real world.Table 6
The performance with different random interval sizes.
Rand intervalRecall@1Recall@5Recall@10Recall@2030.08890.37250.51480.663650.09330.37950.52630.673070.09200.38350.53000.677690.08220.36770.51960.6752110.07470.35120.51040.6702


## 4.6. Case Study

The purpose of verifying the STGRU model is that it can process and predict short trajectory data and long trajectory data, which conducted two sets of experiments with the baseline models. If the user’s trajectory data is scarce, it means that it can hardly understand the user’s behavior pattern, which requires higher performance of the model. The experiments are based on the Tokyo People Flow dataset, taking data with a track length of less than 30 for calculation, without random intervals, and userecall@k as the evaluation metrics. As shown in Figure 4, STGRU has the best performance on recall@1 and recall@5, which proves that STGRU can better handle sparse data.Figure 4
The performance on trajectory data length is less than 30.In another set of experiments, data with track length greater than 200 was obtained and followed the parameter settings of the comparative experiment. As shown in Figure5, STGRU is also superior to all baselines on long trajectory data, which proves that STGRU can extract and use long-term features very well, especially the effectiveness of long-term road network features for modeling strong real-time data.Figure 5
The performance on trajectory data length is greater than 200.


## 5. Conclusion

In this paper, we propose a Spatio-Temporal Gate Recurrent Unit (STGRU) model by enhancing Gate Recurrent Unit for gather prediction. In STGRU, the time gate and distance gate are introduced to model the time interval and distance interval between consecutive trajectory points, which are essential to describe the short-term behaviors of users, and the road network gate is introduced to model the long-term and short-term road network structure. We believe that the geographical environment represented by the road network structure is very important for both the short-term and long-term behaviors of users. The three gates are combined with the update gate in the GRU to extract the user’s short-term behaviors pattern. Only the road net gate and the reset gate in the GRU are combined to extract long-term behaviors patterns of users. Experimental results on three real-world datasets prove the effectiveness of our model, which is better than the latest methods.In future work, we will further incorporate the structured representation of road network information into the model to further improve the aggregation prediction performance.



---

*Source: 6030144-2021-07-15.xml*