Destination prediction provides important support for many locationbased applications, such as urban resource dispatching, targeted advertising, etc. Destination prediction using sparse and partial movement trajectories poses many challenges. The traditional destination prediction methods using Markov model suffer from the data sparsity problem. Though the recurrent neural network (RNN) based destination prediction can handle the data sparsity problem, it only focuses on the context relationship between sequences and ignores the spatial-temporal information behind trajectories. In this paper, we introduce a spatial temporal bidirectional long-short term memory (ST-BiLSTM) network to destination prediction. This proposed method not only makes advantage of LSTM to handle data sparsity and long-term dependencies, but also employs the bidirectional structure of LSTM to effectively model the beginning and end of the sequence, which have greater correlation between sequences. Furthermore, we embed the spatial-temporal factors into the gates equations to further boost the prediction accuracy of the model. Experimental results on the taxi trajectory dataset in the city of Porto, demonstrate that our proposed algorithm outperforms the standard LSTM and BiLSTM models with more than 15% and 10% accuracies, respectively.
With the wide application of navigation and positioning technology, it is possible to
study the law of target trajectory motion. Driven by a large number of available
trajectory data, destination prediction has become a hot topic. Since the Markov model
can represent time series data well, it is widely used for position modeling and
prediction. By dividing the corresponding position into a unified grid unit or path segment
and using it as various states of the Markov process, researches[
Zhang J et al.[
In this paper, we focus on trajectory prediction using long short-term memory
network. Inspired by the work of Liu Q, we also have embedded the spatial-temporal
factors into LSTM cells to make full use of data. In the sequence-based prediction
process, the beginning and end of the sequence tend to be more correlated with the
sequence[
• We adopt the ST-BiLSTM model which embedding spatial-temporal information in net cells to boost the prediction accuracy.
• By conducting experiments on real taxi datasets, our algorithm outperforms the standard LSTM and BiLSTM models with more than 15% and 10% accuracies, respectively. 2
In this section we will introduce the structure of our ST-BiLSTM model and then elaborate the learning and prediction process of the entire model. 2.1
Compared with the standard RNN unit, long short-term memory [
During the prediction process based on trajectory sequence, the most relevant parts
of the prefix are its beginning and its end [
(U (ti) − ti) + (ti − L(ti) ML(di)(U (di) − di) + MU (di)(di − L(di))
(U (di) − di) + (di − L(di) 2.2
Theoretically, the LSTM network can obtain good training and prediction effects in a rich and well-distributed data set, but the real data set is often very dense in some areas, while in other some areas are sparse. Meanwhile, as mentioned in former sections, different time spot or location have different impacts on trajectory trend.
We argue that temporal and spatial influences can work as implicit information to guide the learning of gate mechanism. The introduction of Spatial-Temporal information during the training process can also speed up the training. We directly add the spatiotemporal transfer information to each gate mechanism function of LSTM and the equations are as follows： gt = tanh(DxtWxg + ht - 1Whg + F(st − 1, qt − 1)+bg) it = (DxtWxi + ht - 1Whi + F (st − 1, qt − 1)+bi) ft = (DxtWxf + ht - 1Whf + F (st − 1, qt − 1)+bf) (3) where s, q∈Rd are d-dimensional vector and s0, q0 are 0 and St-1, qt-1 represent the transfer vector from lt-1 to it time interval, respectively. Finally, the function F is used to calculate the two influencing factors to obtain the overall influencing factor vector, where F chooses a simple linear addition. Msk, Mqk∈R|c|*d represent the space-time transfer matrix, respectively, c is the grid cell size.
Fk(st − 1, qt − 1) = Mskst + Mqkqt − 1, k = i, f , o (4)
We use the following formula to calculate the Spatial-Temporal transfer matrix by dividing the region and time into fixed intervals. At a given time interval ti and distance interval di, the corresponding time transfer matrix Mti and distance transfer matrix Mdi can be calculated by the following formulas, respectively.
where U(ti), L(ti) represent the upper and lower bounds of the time period ti, U(di) and L(di) represent the upper and lower bounds of the distance segment di. In this way, the transition probability matrix can be obtained from a continuous data set, and it also provides a better solution for modelling continuous spatial-temporal factors. Given a trajectory sequence Ti = {p1, p2, p3, ..., pn-1, pn}, we first model the sequence {p1, p2, p3, ..., pn-1} as input using ST-BiLSTM and get two vector Hifn-1, Hib1. Hifn-1, Hib1 are the last-time outputs of the forward and backward LSTM layer respectively. And then, Hifn-1 and Hib1 are combined into a vector Vi which is used as the encoded part of the network to represent the sequence Ti.
Please note that the first paragraph of a section or subsection is not indented. The first paragraphs that follows a table, figure, equation etc. does not have an indent, either.
In order to better enable the model to recognize these short-term dependencies, the idea of sliding windows is introduced during the training process. We propose the input of the model is not a single position but a window of k successive GPS points of the trajectory. So that a sliding window with K is trained down the trajectory sequence instead of the previous one. The encoding process is shown in Table 1, where LSTMf and LSTMb are the forward and backward recurrent neural layer, respectively. We use the three-layer fully connected network as the decoding part to obtain the output of the model, and then we will describe the detail of this decoding structure. Given a trajectory sequence Ti={p1, p2, p3, ..., pn-1, pn}, we use the coding structure of the previous layer to encode the vector Vi, and the layer structure uses Vi. As an input to the network. Since the meta-data contained in the trajectory also plays a key role in predicting destination, they also should be added to the input of decoding structure.
Inspired by the word vectors generator in NLP, we trained each part of the metadata of these trajectory to a word vector table. These word vectors are combined with the vector Vi obtained by the Bi-LSTM layer to serve as input for decoding the partially connected network. The final model architecture is shown in Fig. 3.
The final position will be calculated by the following equation. Where Pd is obtained by the softmax layer which represents the probability distribution of each grid. And the cell i whose probability is Pdi is the final prediction result.
Pd i = max(Pd ) (7)
Dataset. In this paper we use a taxi trajectory dataset in the city of Porto. It’s also published by Kaggle 2015 and contains more than 1.7 million track information of 442 taxis from 2013-07-01 to 2014-06-30. The trajectory information is composed of a series of GPS point sequences. we used the first 70% for training and the remaining 30% for test.
Experiment Settings. We divided the research area into the specification 60*80 grid cells, so each cell represents 0.71*0.74 km2. And we also set other size 70*90 and 40*60 as the comparison. During the training process, the batch_size is set to 75, the learning rate learning_rate is 0.01, and the stochastic gradient descent (SGD) is used to minimize the objective function value. 4.2
In order to further verify the effectiveness of the ST-BiLSTM algorithm introduced in this paper, we compare it with the following algorithms for prediction results：
• MLP [
• BiLSTM. The bidirectional structure can better learn the begin and end parts of the sequence while maintaining the advantages of the LSTM itself;
• ST-RNN [
We adopt the mean haversine distance to evaluation our model prediction accuracy, which is defined as follows: dhaver sin e(x, y) = 2R arctan(
a(x, y) a(x, y) −1 ) (8)
Where R is the radius of the earth, and a(x, y) is defined as follows (lonx is the longitude of point x, and laty is its longitude): a(x, y) = sin2 (laty - latx) + cos(laty) cos(latx)sin2(lony - lonx) (9) 2 2
In order to further verify the effectiveness of the proposed algorithm, based on the semi-positive distance, the dis@k distance is used as the evaluation standard. The dis@k is defined as follows： dis @ k = min(d (x1, y), d (x2, y),..., d(xk, y)) (10)
Where d is the mean haversine distance, k = 1, 2, 3 in this paper. Obviously, when k is 1, dis@k is same as the original mean haversine distance evaluation. 4.4
models, LSTM converges earlier than RNN, and the prediction accuracy is more prominent. In terms of network structure, in Fig. 4 and Table 2, ST-BiLSTM and BiLSTM with the bidirectional structure are superior in accuracy to their corresponding single layer models ST-LSTM and LSTM. These prove that LSTM is superior to the RNN unit in the research content of this paper, and the bidirectional structure is indeed superior to the single layer structure in terms of prediction accuracy. Fig. 4. Prediction accuracy under different methods.
Fig 5. Prediction accuracy under different grid size. Method MLP LSTM BiLSTM ST-RNN ST-LSTM ST-BiLSTM
space-time factors on the overall prediction environment, we add time and space factors to RNN, LSTM, and BiLSTM respectively. The experimental results are shown in Fig. 4 and Table 2. The prediction accuracy of each algorithm after embedding time and space factors has improved. Moreover, ST-RNN, ST-LSTM, ST-BiLSTM prediction accuracy is higher than MLP under top5 prediction point.
The Influence of Grid Size. Theoretically, the smaller the grid cell partition is, the higher the prediction accuracy is. However, the smaller cell division in the actual training process means higher training cost of the network which will lead to the lower accuracy. As shown in Fig. 5, the final prediction accuracy of 60*80’s granularity is higher than 40*60, indicating that the prediction accuracy can be improved by improving the grid cell partition specification to some extent. On the other hand, if the grid specification is too intensive, the prediction accuracy will be reduced. In the Figure 7, the prediction accuracy under the 70*90 specification is not as good as the 60*80 specification. 5
We propose a ST-BiLSTM model based on LSTM to adopt a bidirectional structure and embed spatial-temporal factors. On the one hand, by introducing spatial-temporal factors to overcome the influence of data sparseness in partial regions, on the other hand, the introduction of bidirectional structure also enables the start and ending parts of long trajectories to be better studied. The model of this paper is tested on the taxi trajectory dataset int the city of Porto, and the experimental results also fully proves the validity of the model. In the future, we should collect other datasets as much as possible for verification, and further accelerate the training process. 6
This work was supported in part by the National Key Research and Development Program (2018YFB0505200), the National Natural Science Foundation of China (61872046 and 61671077), and the Open Project of the Beijing Key Laboratory of Mobile Computing and Pervasive Device.