HST-LSTM: A Hierarchical Spatial-Temporal Long-Short Term Memory Network for Location Prediction

1 Introduction

With the widespread use of positioning technology, it is increasingly possible to track and mine the movements of people. When people turn to digital map applications (Baidu Map, Google map, etc) for positioning or navigation services, their travel information is recorded and massive trajectories of them are accumulated. These trajectory data open great opportunities for location prediction research and from which location-based services (LBS) such as navigational services, traffic management and location-based recommendation and advertising are beneficial.

Location prediction has long been studied since the positioning technology is frequently used. Some researches [Lin and Hsu, 2014; Chen et al., 2015; Trasarti et al., 2015] focus on real time location prediction problem using continuous intensive positioning data which are mostly generated by vehicles, these researches help promote the performance of tasks like congestion prediction and route planning. Other works [Lian et al., 2014; Li et al., 2015; Cheng et al., 2013; Liu et al., 2016] pay attention to long time prediction like Point of Interest (POI) recommendation, which aims to predict potential visit pattern with a gentle time constraint.

With the fast development of urbanization and modern civilization, it is becoming more and more important to mine people's movements and predict their next destinations in a short time period in order to achieve better urban management and services. Researches [Yuan et al., 2015; Vaca et al., 2015] have found that the modern citites consist of functional zones such as residential areas, business districts, and educational areas, etc. People's movements among these functional zones reveal different socioeconomic activities like working, shopping, entertaining, etc. In this paper, we address the problem of discovering movement patterns among these functional zones in order to predict the next move people will go ahead in minutes or hours. Figure 1(a) illustrates an example of several trajectories different users made over different functional zones. People move from one zone to another one and may stay in one zone for a period of time. For simplicity, we assume that consecutive visits in the same zone represent the same socioeconomic activity and the point trajectories then can be compressed to zone visiting sequences as shown in Figure 1(b).

Temporal and spatial contexts are key factors in location prediction problem. Figure 2 gives an example of next locations' visiting frequencies after users' visiting location 22 in consecutive time slots. It is obviously seen that the top locations visited after the location 22 differ in each time slot and some locations like 10, 957 just appear in the first several slots while other locations such as 678, 1028 appear in the last several slots. These observations reveal the importance of spatial-temporal contexts in location prediction problem.

A lot of works [Li et al., 2015; Liu et al., 2016] leverage temporal and spatial features to boost prediction performance. Some of them [Lian et al., 2014; Li et al., 2015] leverage these features as constraints to learn a better prediction model. Others [Liu et al., 2016] utilize embedding methods which embed time interval and geographical distance using vectors or tensors to encode spatial-temporal effects and achieve good prediction performance. Recently, deep neural networks especially Recurrent Neural Network (RNN) based models are more and more fancy to deal with sequential data. The introducing of the gate mechanism solves vanishing gradient problem and many tasks achieve state-of-the-art performance by using LSTM based models. However, most sequential models just emphasize the dependencies among sequence nodes, ignoring other corresponding correlations like spatial and temporal relations among them. We argue that these spatial-temporal relations are essential for mitigating the data sparsity which exists in most deep models. In this paper, we propose the idea of introducing these spatial-temporal relations into gates to guide the learning of deep models .

Recently, many prediction tasks benefit from contextual information. [Sordoni et al., 2015; Song et al., 2017] find that people's historical behaviors effect their choices in the future, they both take advantages of historical information as contexts and model them via hierarchical architectures and show the effectiveness. Considering the periodicity of people's movements that people tend to visit the same or similar places, we also propose a hierarchical model to encode people's visit historical information as contexts to boost prediction accuracy.

In this paper, we address the location prediction problem in a weak real time condition and the contributions can be summarized as follows:

• We propose a novel Spatial-Temporal Long-Short Term Memory (ST-LSTM) model which combines spatialtemporal influences into LSTMmodel naturally to mitigate the data sparsity in location prediction problem.
• To model the visit context, we propose HST-LSTM, a hierarchical extension of ST-LSTM. HST-LSTM models users' historical visiting sequences in an encoder and decoder manner to boost the prediction performance.
• Finally, we show empirically that the proposed model outperforms several location prediction methods on a re-

al world trajectory data set.

2 RelatedWork

POI recommendation is the task most related to our work and it focuss on recommending POIs for users with a gentle time constraint while our location prediction problem is under a weak real time condition. Most of conventional methods are based on Collaborative Filtering (CF) technique and the most popular one is user-based CF [Yuan et al., 2013], which takes advantage of check-ins of similar users for recommendation. Others are the Matrix Factorization (MF) based methods [Lian et al., 2014; Li et al., 2015], which factorize the user-item preference matrix to learn the general taste of a user.

Recently, sequential influence has been considered for location prediction. Markov chain property is the favorite one for traditional approaches. FPMC [Rendle et al., 2010] is the state-of-the-art personalized Markov chain algorithm. [Cheng et al., 2013] employs FPMC to model the personalized POI transition and aims to recommend POIs for the next hours by merging consecutive check-ins in the previous hours. Based on the current POI, their method only considers the POIs in the defined region as candidates, which might be a little thoughtless. [Lian et al., 2013] breaks the region restriction and also adopts FPMC to represent the short-term and long-term preference to predict the next check-in.

Embedding technique which embeds words into low dimension latent space to handle semantic gap has become popular and transfers to many studying areas. PRME [Feng et al., 2015] is the state-of-the-art embedding method for POI Recommendation. It learns both users' and locations' latent vector representations at the same time by minimize the distances of successive POI check-ins and the similarities of users' representations and their own visited POIs. However, PRME merely models short-term transition patterns and ignores the long-term dependency within users' movements.

Recurrent Neural Networks (RNN) [Williams and Zipser, 1989] achieved great advance to deal with sequential data.

,

,

Many study fields, such as Language Modeling [Mikolov et al., 2010], Speech Recognition [Graves et al., 2013], etc. achieved state-of-the-art performance with the help of RNNs. Recently, recurrent model is applied to POI recommendation tasks. [Liu et al., 2016] is the fisrt one to introduce deep neural network to location prediction problem, they extend recurrent networks (RNN) with spatial and temporal information and propose the ST-RNN to recommend POIs and achieve good results. The hierarchical architecture is favorite for RNN models recently and it produces a efficient way to memorize and utilize historical information and boosts performance of tasks such as query suggestion [Sordoni et al., 2015].

3 The ProposedModel

To better convey the proposed HST-LSTM model, we first introduce some relevant definitions will be used:

• Area of Interest (AOI). An area of interest is a functional zone that offers same geographical function, such as a shopping center or a workspace, which covers certain area on digtial maps and contains various individual POIs.
• Visit Record. The visit record consists of all the AOIs that one user visited in a certain time (several weeks or months).
• Visit Session. An AOI sequence which visited by a user in a certain time interval (one day in this paper as it is a natural segmentation slot of visit record) is defined as a visit session. The AOIs in one visit session have strong correlations with each other since they are all visited by a same user and they reveal the user's movement patterns.
• Visit Session Sequence. A visit session sequence consists of a user's consecutive visit sessions. A user's historical visit sessions of a user could act as contextual information to help predict next AOI the user is about to visit in current and future visit sessions.

Assume that a user u has n visit sessions and one visit session Si (i ∈ [1, n]) consists of an AOI sequence {li1 , li2 , ..., limi }, where mi is the length of ith visit session. Then the visit record Vu of user u can be represented as {..., li1 , li2 ..., limi , ..., ln 1 , ln 2 ..., lnmn }. For simplify, we denote Vu as {lu 1 , lu 2 , ..., luN }, where N is the total number of locations that user u has visited. Our problem can be formulated as follows: Given a user u and his/her first j (j ∈ [1, N]) visiting locations {lu 1 , ..., lu j }, our task is to predict next N - j locations {lu j+1 , ..., luN } that the user most likely to visit next.

3.1 Spatial-Temporal LSTM

Standard LSTM [Hochreiter and Schmidhuber, 1997] is an optimized RNN model that can avoid the vanishing gradient problem by introducing the gate mechanism. Given the input lt at time t, the output of LSTM hidden layer ht is computed as following composite function:

where h0 = 0, σ(·) is the logistic sigmoid function and φ(·) is the hyperbolic tangent function, i, f, o and c are input gate, forget gate, output gate and cell state respectively. These multiple gates allow the cell in LSTM to keep, update or forget information over time. The three gates control the information flow run through the cell. In detail, the input gate i decides whether to feed the input data, the forget gate f decides whether to forget history and the output gate o decides whether to produce current state. These gates are trained from massive data to learn how to function normally. However, it is always hard to learn well functioned gates due to the data sparsity and our visit AOI sequences are such sparse data. As mentioned in former sections, different time intervals have different impacts on users' move intentions and the length of time interval is essential for predicting future movements. This is the same when it comes to spatial interval. We argue that temporal and spatial influences can work as implicit information to guide the learning of gate mechanism and we propose to add spatial-temporal factors into three gates and the equations are as follows:

where s, q ∈ Rd are vectors with dimension d, s0 = 0, q0 = 0 and they represent the spatial impact factor and the temporal impact factor respectively. st-1, qt-1 denote the vector representations of intervals between lt-1 and lt. F(·) is a function of these two factors and we define it as an add operation:

where Wsk,Wqk ∈ R|c|∗d are linear transition matrix with respect to spatial and temporal factors, |c| is cell state size. We have tried tons of F(·) operations such as concatenation, element-wise addition or multiplication, etc., and find that the add operation defined above is the most concise and efficient way. If we learn a distinct vector for each possible continuous time interval and geographical distance, the parameters are uncountable and the proposed model will face more severe data sparsity problem. We solve this problem by partitioning time interval and geographical distance into discrete slots and only encoding the upper and lower bound of these slots. For a certain time interval vq or geographical distance vs in a slot, we calculate the corresponding vector q and s with a linear interpolation using the following equations:

where u(vq) and l(vq) are the upper bound and lower bound values of the time slot with respect to q, and u(vs) and l(vs) are the upper bound and lower bound values of the distance slot with respect to s. Q ∈ RNq∗d and S ∈ RNs∗d are the temporal factor matrix and spatial factor matrix and Nq , Ns ∈ R are the total number of time and distance slots respectively.

3.2 Location Prediction with HST-LSTM

Based on the proposed ST-LSTM, we employ a hierarchical extension of the proposed ST-LSTM to model the periodicity of visit sequence in an encoder and decoder manner.

The Encoding of Visit Session

Given a user u and his visit record Vu, and Vu consist of visit sessions {S1, S2, ...Sn}, for i ∈ [1, n - 1], we first encode visit session Si = {li1 , li2 , ..., limi } as follows:

where STLSTM e (·) denotes one step forward pass of encoding and lij is the one-hot representation of the j th visit AOI in visit session Si, Wl is the AOI embedding matrix and lij is the AOI embedding representation w.r.t. lij . hij is the output at time step j and we take the final output himi as the representation of the whole visit session Si which is denoted as hie .

Global Context Encoding

After encoding the visit sessions, we get their vector representations, which are {h0e , h1e , ...hn-1 e }. Then we feed them into a global contextual LSTM to model the long-term evolution of visit sequence. The equations are as follows:

where LSTM c (·) is the global contextual LSTM and denotes one step forward pass of encoding. hic represents the output of the global contextual LSTM at time step i.

Decoding and Prediction

We suppose that hic acts as contextual visiting information and could be decoded to help predict potential visit patterns of visit session i. For a user u and his/her visit sessions {S1, S2, ...Sn} and contextual vectors {h1c , h2c , ..., hnc }, we decode each visit session Si using following equations:

where STLSTM d (·) denotes one step forward pass of decoding. lij is the one-hot representation of the j th visit AOI in visit session Si. We assume that the output hd,i j is a summary of past j travelling areas in visit session Si and represents the travel intention at time j and it can be decoded as a distribution over AOIs which are likely to go next:

where pij is the probability distribution of AOIs. Wp and bp are the transformation matrix and bias of the prediction layer and they are shared across all time steps. The probability of the most likely visit AOI after visiting lij is calculated as follows:

3.3 Learning

Given all of training visit records T = V 1 , V 2 , ..., V N , the objective function of HST-LSTM can be defined as follows:

where N is the number of visiting records, lij represent j th AOI of visit session Si and mi is the length of Si. θ represents all of the model parameters which are learned by maximizing J(θ).

4 Experiments

4.1 Data set and settings

Our experimental data set are generated from Baidu map 1 log data. We gathered all users' traveling records in city Peking during one week(from Dec. 2, 2015 to Dec. 8, 2015), which contains 311,310 usable point paths and 16,775,817 positioning points. We transform the point paths into AOI paths by grouping positioning points within the same AOI and get our final experiment data set consisting of 144,320 unique AOI paths which share 9000 semantic AOIs. To evaluate the robustness of the proposed model, we choose 20%,40%,60% and 80% of data as training set respectively, and the remaining data are as test data to evaluate the model. The parameters to learn are initialized with normal distribution. Hyper parameters such as embedding dimension |l|, cell state size |c|, spatial and temporal embedding size d are tuned using grid search. In detail, |l|, |c| ∈ {8, 16, 32, 64, 128}, d ∈ {8, 16, 32}. Parameter optimization is done using minibatch Adam and the early stop strategy is employed, the batch size is 100 and the initial learning rate is set to 0.01 for deep models.

1 http://map.baidu.com

4.2 ComparisonMethods

To prove the effectiveness of the proposed HST-LSTM, we compare our model with following prediction methods:

• Top. We simply choose the most popular location for prediction.
• Matrix Factorization (MF)[Mnih and Salakhutdinov, 2008]. Matrix Factorization based methods have been

widely used in recommendation and prediction tasks. In our location prediction problem, we use MF to mine the relationship between each two consecutive visited AOIs, and then use it for prediction.

• Variable-Order Markov (VOM) model[Begleiter et al., 2004]. Variable-order Markov based models are the state-of-art methods for location prediction problems. We learn conditional distributions with a varying order k - 1 (k is the max length of an AOI path) and provides means of capturing different orders of dependencies based on training data and we adopt the principle of longest match for prediction.
• FPMC[Rendle et al., 2010]. FPMC is the state-of-theart personalized Markov Chain algorithm for recommendation or prediction tasks.
• PRME[Feng et al., 2015]. PRME is the state-of-the-art embedding method for POI recommendation. It embeds users and POIs into latent spaces to calculate similarities between users and POIs and similarities among POIs for better recommendation performance.
• ST-RNN[Liu et al., 2016]. ST-RNN is the state-of-theart deep model for POI Recommendation, it fuses geographical influence and time influence into RNN model with distance transition matrix and time transition matrix respectively for better POI Recommendation.
• LSTM[Hochreiter and Schmidhuber, 1997]. LSTMnetwork has shown its ability in handling sequential data and has superiority in encoding long-term dependencies and it is natural to apply LSTM to our sequential AOI path data for location prediction.

4.3 Evaluation Criteria

We evaluate the performance of the model and the baselines in terms of two kinds of criteria. The first one is Acc@k which can be defined as: Acc@k = #hit@k #tests , where #hit@k means the number of predicted locations ranking at top k and #test stands for the number of total testing samples. In this paper, we choose k = 1, 5, 10, 20. Another evaluation criteria is mean reciprocal rank (MRR), which is defined as: MRR = 1N ·∑Ni=1 1 Ranki , where N is the total number of test instances and Ranki is the predict rank of instance i.

250

Figure 4: Figure (a) and (b) show the cross entropy loss curves and the Acc@1 curves of HST-LSTM, ST-LSTM and LSTM during first 250 learning iterations on both train and test sets. For train set, both the loss and Acc@1 values of each iteration are obtained by averaging results of all mini-batches in one iteration.

4.4 Results and Analysis

Overall Performance

We report the comparison results between the proposed model HST-LSTM and other methods, the overall performances are shown in Table 1 and Figure 3. From the statistics we can conclude that:

• HST-LSTM and ST-LSTM are superior to methods with a certain large margin which demonstrates the effectiveness of the proposed spatial-temporal model.
• HST-LSTM achieves much better prediction performance than ST-LSTM in all evaluation criteria with different data settings which shows that the historical visit information are important clues for location prediction.
• Comparing to ST-RNN with a different spatial-temporal modeling mechanism, the proposed ST-LSTM model performs better and it proves the effectiveness of the idea of combining spatial-temporal factors with gate mechanism to mitigate data sparsity.
• Embedding methods are superior to non-embedding methods in most cases, this shows the advantages of embedding methods when dealing with sparse data.
• Sequential models perform quite better than nonsequential models which proves that long term dependencies are essential in sequence modeling.

Besides, we show the cross entropy loss curves and Acc@1 curves in Figure 4. It is obviously seen from Figure 4(a) that HST-LSTM and ST-LSTM model converge much better than standard LSTM model, which proves the proposed spatial-temporal models have better abilities to fit sequential data. Figure 4(b) shows similar results with evaluation criteria Acc@1.

The Influence of Spatial-Temporal Factors on Gate Mechanism

We did experiments that merely introducing spatial-temporal factors into one or two gates, for example, ST-LSTM-i means only applying spatial-temporal factors into input gate. The results are shown in Table 3. We can see that the more gates learned by spatial-temporal factors, the better the prediction performance is. When all three gates are learned, the model performs best, which proves the fact from another perspective that three gates of a memory cell work together to process the information passing through it.

Choosing the Best Windows of Temporal and Spatial Bins

We also did batch of experiments with different temporal and spatial slot size settings and the Acc@1 results are shown in Table 2. We can observe that when time slot size t ∈ [1, 2] and spatial slot size s ∈ [300, 500], the best prediction performance is achieved, which is consistent with the reality that people's location transfer time unit is about one hour or two and the unit of distance interval of two AOIs is between 3 to 5 hundred meters.

5 Conclusion

This paper proposes a novel spatial-temporal LSTM model for location problem and it introduces spatial-temporal factors into gate mechanism to mitigate data sparsity problem. Further more, we leverage historical visit information and adopt a hierarchical architecture to boost the location prediction performance. The experimental results prove the effectiveness of the proposed method.

Acknowledgements

This work was supported in part by the 973 program (2015CB352300), NSFC (61625107, U1611461,U1509206), Zhejiang province key project (2015C01027), the China Knowledge Center for Engineering Sciences and Technology, and fundamental research funds for central universities in China.