Inferring Continuous Latent Preference on Transition Intervals for Next Point-of-Interest Recommendation

Recently, many efforts have been devoted to next Point-of-Interest (POI) recommendation [8, 18], which not only help users promptly identify their very next favorite POIs, but also benefit location-based social network (LBSNs) service providers to acquire more customers. However, to achieve accurate personalized POI recommendation is very challenging as it’s well known that the check-in data of each user is in fact highly sparse. Existing work studied users’ preferences on POIs by employing various context information, e.g., social relations, distance constraints and temporal information etc., to enhance the recommendation performance. To leverage on the temporal influence, some of existing works simply explore the temporal periodicity of human mobility, as the intuition behind is that human mobility often exhibits periodical patterns. For example, certain types of locations, such as office and Gym, are visited regularly at the same time slot [5, 9, 17].

Another research line of considering the temporal information is to explore the sequential behavior from successive check-ins. Cheng et al. utilized the factorized personalized Markov Chain (FPMC) [4] to capture the time-critical successive check-ins for next POI recommendation. Specifically, [12] investigated how to perform POI recommendations for a specific time period by learning users’ evolving sequential preferences. Therefore, the expected time that a user will check in some places can be estimated by enumerating all possible time.

Furthermore, almost all existing work focused on utilizing the time stamps (absolute time) of check-ins, e.g., Monday morning, or 9:00 pm on Saturday. As reported in [9], user behavior shows clear periodic patterns. For example, people usually check in a workplace at 9:00 am. However, we argue that utilizing such patterns implicitly assumes that all check-ins follow a probability distribution, e.g., Gaussian with fixed mean and variance. In fact, people with different occupations follow various office hours. Consequently, the temporal patterns towards other activities should also vary. Thus, most existing work cannot take such diversity into consideration. Therefore, we argue that the time-intervals between check-ins do reflect the temporal behavior patterns of human activity with more flexibility.

Observations of transition intervals

Full size image

Figure 1(a) plots the probability of next check-in locations in City of New York (NYC)^{Footnote 1} for “food” and “nightlife” given the previous check-in as “work” over different time intervals. There are three local maxima when the intervals are 4 h, 12 h, and 23 h for food check-in. The observation confirms a behavior pattern that people usually have breakfast 1 hour before, and have lunch and dinner at about 4 h and 12 h after they start to work, respectively. And the maximum of nightlife check-in indicates that people usually visit nightlife spots at about 10 h after the start of work. In summary, the working hour for each user may be different, but the transition intervals between check-in activities follow similar patterns. Figure 1(b) plots the cumulative distribution function (CDF) of the top-4 most popular location categories for “after work”, in which the transition interval pattern is evident, e.g., the outdoor spots are often checked in after work within a short interval. We argue that such latent behavior patterns with time intervals should play a key role for next POI recommendation. The challenges come from two aspects, how to model such personalized latent behavior pattern and how to boost next POI recommendation with incorporation of the latent preferences.

In this paper, we propose a probabilistic approach to infer the continuous latent preference on transition intervals for next POI recommendation. Under our proposed framework, the next check-in and the time-intervals between successive check-ins can be obtained simultaneously. Thus, the checked-in time for a future activity can also be inferred from the time stamp of the previous check-in. Specifically, we model the overall transition preference with three components, namely, personal preference, spatial preference, and transition interval preference. They are modeled by a third-rank tensor, a distance constraint, and a continuous latent variable, respectively. Then, we develop a probabilistic factor analysis model to combine these three components. The probabilistic model performs statistical inference and Bayesian methods where the latent preference variables are assumed to follow Gaussian distributions with different means and variances. The transition probabilities, the estimated transition intervals, and the uncertainty of them are then obtained. During model learning phases, the Expectation Maximization (EM) is developed to optimize the proposed probability model. Experimental results demonstrate that the proposed model outperforms other state-of-the-art methods in terms of next POI recommendation and the expected transition time.

Latest studies have integrated temporal influence into POI recommendation for further performance improvement.

[7] investigated the temporal cyclic patterns of user check-ins in terms of temporal non-uniformness and temporal consecutiveness and demonstrated its effectiveness to improve recommendation performance. [4] proposed a tensor-based FPMC-LR model for next POI recommendation by considering the sequential behaviors between check-ins. [6] proposed a personalized ranking metric embedding model (PRME) for next new POI recommendation by considering the order relationship between check-ins. [12] proposed a bi-weighted low-rank graph construction model to make recommendations for a specified future time period by considering users’ evolving sequential preferences.

[11] explicitly modeled the check-in time as the modes of a fourth-rank tensor for next POI recommendation, in which the time interval is utilized to capture the intensity of relation between the two successive check-in locations. The approach is designed in a two-fold manner, which predicts the POI category first, and then determine the expected visitings. Their work assumed that the intensity of relation decays over the transition time, but the temporal periodicity exists. Its applicability is constrained by the availability and accuracy of the categorization.

However, none of the existing methods investigated the transition interval pattern explicitly. Alternatively, they utilized absolute time to capture the temporal preference. We argue that modelling the transition interval preference may help us to capture more diversified human mobility patterns. Moreover, existing work [9] modeled the latent behavior pattern in a discrete manner, and the number of patterns must be predefined. This motivates us to further investigate on the transition latent variables. In this paper, we extend the transition preference with the dimension of transition interval preference, and apply a continuous latent variable factor analysis approach to remove the requirement of predefinition.

Let \(U =\{u_1,u_2,...,u_M\}\) be a set of LBSN users, and \(L =\{l_1,l_2,...,l_N\}\) be a set of locations (POIs). Let \(l^t_u\) be the location visited by user u at time t, then the set of locations visited by u before time t is denoted by \(L_u^t\), and \(L_u^t= \{l^1_u,..., l^{t-1}_u \}\). Let \(\tau _{u,i,j}\) be the transition interval for u between location i and j, and the corresponding set of transition intervals for \(L_u^t\) is denoted by \(T_u = \{\tau _{u,l_u^1,l_u^2},..., \tau _{u,l_u^{t-2},l_u^{t-1}} \}\). Our goal is to recommend user u next POI via the ranking of probabilities that he/she will move from the current location i to the next location j, with the transition interval \(\tau _{u,i,j}\) inferred at the same time. Based on first-order Markov chain property, the transition probability is denoted as \(x_{u,i,j} = p(j = l_u^{t}|i = l_u^{t-1})\). Thus, each user is associated with a specific transition matrix which in total generates a transition tensor \(\chi \in \mathbb {N}^{|U| \times |L| \times |L|}\) with each \(\chi _{u,i,j}\) representing the observed transition frequency of user u from location i to location j.

3.1 Preferences Modeling

Personal Preference. As the transitions among \(\chi \) are partially observed, we follow most previous work [4, 9] to apply the low-rank factorization model, a special case of Canonical Decomposition which models the pairwise interaction between all three modes of the tensor (user U, current location I, next location J), to fill up the missing values, given as:

where \(\varvec{v}_u^{U,J}\) and \(\varvec{v}_j^{J,U}\) denote the latent factor vectors for users and next locations, respectively. Other notions are defined in the same manner. The term \(\varvec{v}_u^{U,I} \cdot \varvec{v}_i^{I,U}\) can be removed since it is independent of location j and does not affect the ranking result [14], thus, leading to a more compact expression for \(\hat{\chi }_{u,i,j}\):

Transition Interval Preference. To extract the transition interval preference of user u for the next location, we first define the transition interval tensor Z. With the temporal intervals between successive POIs extracted for user u, the POI-POI transition interval matrix \(Z_u\) is constructed, which in turn generates a transition interval tensor \(Z \in \mathbb {R}^{|U| \times |L| \times |L|}\) with each \(\hat{z}_{u,i,j}\) representing the estimated transition interval of user u from location i to location j. Similar to yielding \(\hat{\chi }_{u,i,j}\), \(\hat{z}_{u,i,j}\) is generated by modeling the pairwise interaction between the modes of the transition interval tensor, given as:

where \(\varvec{e}_u^{U,J}\) and \(\varvec{e}_j^{J,U}\) denote the latent factor vectors for users and next locations in tensor Z, respectively. Other notions are defined in the same manner.

Transition intervals v.s. the number of check-ins

Full size image

To investigate the relation between the number of transitions and the transition intervals, we plot the check-in counts with respect to its transition intervals between two successive check-ins for Foursquare-NYC dataset and Gowalla dataset in log scale (Fig. 2). We can observe that the number of transitions decreases as the temporal interval increases, and the relation follows a power law distribution with exponent \(k\approx -1\). Therefore, we define \(z_{u,i,j}\) to specifically indicate the latent transition interval preference for user u to visit location j from the current location i by leveraging on the observations in Fig. 2 under conditions of uncertainty. We assume the latent variable \(z_{u,i,j}\) is Gaussian with prior mean of \(\hat{z}_{u,i,j}^{-1}\) and variance of \(\sigma _1^2\), given as:

Spatial Preference. Users’ mobility is geographically constrained by the distance that one can travel within a limited time, and their preference to visit a location decreases as the geographical distance increases [5]. Most POIs which are likely to be explored are close to users’ residence, workplace, and frequently visited POIs. Hence, the spatial behaviors of users can be utilized to enhance next POI recommendation. Here, we define the spatial influence \(sp(d_{i, j})\) for any user to visit a location j which is \(d_{i, j}\) km away from the current location i to leverage on the distance constraint: \(sp(d_{i, j}) = \rho \cdot d_{i, j}^{-1}\). The optimal setting of \(\rho \) will be learned during the inference phase.

3.2 A Factor Analysis Latent Variable Model

In this paper, we adopt a so-called statistical factor analysis [2] latent variable model to incorporate the aforementioned three preferences, in which the combination is a linear function for observed data x:

where z denotes the latent variable, \(\epsilon \) is a z-independent noise process, w contains the factor loading, and \(\mu \) permits the model to have non-zero mean. Conventionally, the latent variables are assumed to be independent and to follow standard normal distribution, \(z \sim N(0,1)\), and the noise follows Gaussian distribution, \(\epsilon \sim N(0,\sigma ^2)\). Then the variable x induced from Eq. (5) follows Gaussian distribution, \(x \sim N(\mu , w^2 + \sigma ^2)\). The parameters may thus be inferred in a maximum-likelihood manner, and there is no closed-form analytic solution for w and \(\sigma ^2\).

We define \(\mu = \hat{\chi }_{u,i,j} +\rho \cdot d_{i, j}^{-1}\) to incorporate the personal preference and distance preference, then a special case of factor analysis for next POI recommendation can be obtained as:

where w is a trade-off parameter used to control the contribution of the transition interval preference and will be learned during model inference phase. The set of all parameters for the proposed model is \(\varvec{\varTheta } := \{ \varvec{\rho }, \varvec{w}, \varvec{\sigma }_1^2, \varvec{\sigma }_2^2, \varvec{V}_u^{U,J}, \varvec{V}_j^{J,U}, \varvec{V}_j^{J,I}, \varvec{V}_i^{I,J}, \varvec{E}_u^{U,J}, \varvec{E}_j^{J,U}, \varvec{E}_j^{J,I}, \varvec{E}_i^{I,J} \}\). In general, we believe that user behavior is personalized, and it is reasonable to assume that the check-ins from the same user share the same value of parameters \(\{ \varvec{w}, \varvec{\sigma }_1^2, \varvec{\sigma }_2^2 \}\). Otherwise, they are not learnable for check-ins from the test set.

In our model, the noise represents random influences in the transitions that is not generated from the user preference, but arises from social network, weather, etc. Since the distribution over the noise is also Gaussian and defined as \(\epsilon \sim N(0, \sigma _2^2)\), Eq. (6) implies a probability distribution over \(x_{u,i,j}\) for a given \(z_{u,i,j}\):

Given the above formulations, the marginal distribution for the observed \(x_{u,i,j}\) is then obtained by integrating latent variables and is likewise Gaussian:

The conditional distribution of the latent variable \(z_{u,i,j}\) given the observed \(x_{u,i,j}\) can be derived by Bayes rule and is also Gaussian:

where the posterior mean and posterior variance are specified by

\(C=\frac{\sigma _1^2 w (x_{u,i,j}-\hat{\chi }_{u,i,j} -\rho d_{i, j}^{-1}) + \hat{z}_{u,i,j}^{-1} \sigma _2^2}{ w^2 \sigma _1^2 +\sigma _2^2}\) and \(M=\frac{ \sigma _1^2 \cdot \sigma _2^2}{ w^2 \cdot \sigma _1^2 +\sigma _2^2}\) respectively.

3.3 Parameter Inference

Learning in probabilistic models can be simplified as maximizing the data log-likelihood with respect to all the model parameters. In our model, we consider the latent variables \(\{z_{u,i,j}\}\) to be ‘missing data’ and complete data to comprise the observed transitions \(x_{u,i,j}\) together with them. Assuming that users are independent as well as their check-in histories are independent, the corresponding complete-data log-likelihood is given as:

where the components are derived from Eqs. (7) and (4):

Estimates for the model parameters \(\varvec{\varTheta }\) may be obtained by iterative maximization of \(\mathcal {L}_C\), and a typical approach is to use Expectation-Maximization (EM) algorithm [15]. It is well known that EM algorithm iterates the two steps expectation (E-step) and maximization (M-step) until convergence, and it is guaranteed to increase the data likelihood to a local maximum. In the E-step, the expectation of \(\mathcal {L}_C\), with respect to the posterior distribution of \(z_{u,i,j}\) given the observed \(x_{u,i,j}\), is computed by using the current estimate for the parameters \(\varvec{\varTheta }\). In the M-step, new parameter values \(\varvec{\varTheta }^\prime \) are determined by maximizing the expected complete-data log-likelihood. In our inference process, the corresponding steps are defined as follows:

E-step: we take the expectation of \(\mathcal {L}_C\) with respect to the distributions \(p( z_{u,i,j}| x_{u,i,j})\):

where we have omitted terms independent of the model parameters. The involved expectations are given as:

where \(\langle z_{u,i,j} \rangle \) denotes the posterior mean of Eq. (9), and \(\langle z_{u,i,j}^2 \rangle \) is obtained in conjunction with the posterior variance of Eq. (9).

M-step: \(\langle \mathcal {L}_C \rangle \) is maximized with respect to the model parameters \(\varvec{\varTheta }\). This can be done by differentiating Eq. (13) and setting the partial derivatives to be zero, which gives a closed-form solution for parameters of \(\{ \varvec{\rho }, \varvec{w}, \varvec{\sigma }_1^2, \varvec{\sigma }_2^2 \}\). For other parameters in factorization model, their values must be obtained via an iterative procedure as there are no closed-form solutions for them. Specifically, to obtain the revised parameters of \(\{ \varvec{V}_u^{U,J}, \varvec{V}_j^{J,U}, \varvec{V}_j^{J,I}, \varvec{V}_i^{I,J}, \varvec{E}_u^{U,J}, \varvec{E}_j^{J,U}, \varvec{E}_j^{J,I}, \varvec{E}_i^{I,J} \}\), we follow the widely used stochastic gradient decent (SGD) algorithm to optimize the partial derivations to be zero with respect to each parameter. That is to take the second derivative of \(\mathcal {L}_C\). Then, the updating procedure is performed as:

where \(\alpha >0\) is the learning rate.

To maximize the likelihood, the sufficient statistics of the posterior distribution are calculated from the E-step Eqs. (14) and (15), after which revised estimates of parameters are obtained from M-step. These steps are iterated in sequence until the algorithm is judged to be converged. The detailed algorithm and the parameter updating rules are shown in Algorithm 1.

4.1 Datasets

We evaluate models on two real-world datasets which are acquired from Foursquare (NYC) and Gowalla and provided by [1, 3] respectively. The statistics of the three datasets are listed in Table 1. Each dataset is split into two non-overlapping subsets to evaluate the model performance (for each user, the earliest 80% of check-ins as training set, and the remaining 20% check-ins as test set).

4.2 Evaluation Metrics

Different from the existing approaches, e.g., FPMC-LR, which took a set of POIs visited within a time interval as the previous/next POI to fit the training process to overcome the data sparsity, we take only two POIs to construct the <previous, next> POI pair during our training process, and to predict the “exact” next POI, instead of a set of next POIs as in FPMC-LR. Thus we only adopt recall to evaluate the performance for the “exact” next POI recommendation, as whatsoever the length of recommendation list is increasing, there exists only one correct solution for the “exact” next POI recommendation, and the precision cannot be higher than \(1{\slash }|recommendation~list|\). Therefore, we evaluate the performance of the next POI recommendation and the next new POI recommendation by defining recall as^{Footnote 2}:

where \(S_{N,u}^{POI}\) is the list of top-N recommended POIs in descending order, \(S_{visited}^{POI}\) denotes the visited POIs for user u, and \(S_{visited}^{newPOI}\) denotes the locations that haven’t been visited by a user yet in the training set but will be visited in the test set. |U| denotes the number of the users, and N is the size of the next POI candidate list.

To make a fair comparison with the existing works, we further evaluate the performance of next POI recommendation by considering consecutive next check-ins within \(\gamma \) hours as the next location set (\(\gamma \) is set to 6 following [4, 6]). Precision and recall are accordingly defined as:

where \(S_{visited}^{\gamma }\) denotes the visited POIs for user u in the next \(\gamma \) hours. The precision and recall are computed by averaging all precision and recall for all samples in test set.

It is a relatively new research topic to predict the transition interval and evaluate the performance for such a model. We use the following two metrics to evaluate the performance of transition interval prediction.

• Mean Absolute Percentage Error (MAPE) focuses on the difference between the estimated transition interval \(\hat{z}_{u,i,j}\) and the actual time interval \(T_{u,i,j}\) across all testing data:

  $$\begin{aligned} MAPE = \frac{1}{|N_{d}|} \sum _{N_{d}} \frac{ |T_{u,i,j} - \hat{z}_{u,i,j} |}{T_{u,i,j}} \end{aligned}$$

  (21)

  where \(|N_{d}|\) is the size of the test set.The model with smaller error is the better one.

• Precision for the POI recommendation is introduced to help the evaluation for the predicted transition interval of each movement. It is introduced because MAPE is susceptible to large errors and often take more weights from them, which makes MAPE less appropriate to evaluate the task of personalized POI recommendation. It is defined as:

  $$\begin{aligned} Precision@T = \frac{1}{|U|} \sum _{u \in U} \frac{sum(\varvec{S}_{T,u})}{|S_{visited}^{POI}|} \end{aligned}$$

  (22)

  where \(S_{T,u}\) equals to “1” if the difference between \(\hat{z}_{u,i,j}\) and \(T_{u,i,j}\) is less than a specified threshold T, i.e \(|\hat{z}_{u,i,j} - T_{u,i,j}|<T\), or “0” otherwise.

4.3 Performance Comparison on Next POI Recommendation

Alongside with our model, the following state-of-the-art methods are evaluated and compared on the performance of next POI recommendation:

• MF: it factorizes the user-POI preference matrix in conventional recommender system [10].

• PMF: Probabilistic Matrix Factorization (PMF) [13] is a generalized matrix factorization model for traditional recommendation task.

• FPMC-LR: it extends factorized personalized Markov chain with the localized region constraint, which uses BPR as the optimization criterion [4].

• PRME-G: it considers the distance between current location and next location for metric embedding, which is the state-of-the-art personalized sequential POI recommendation [6].

• LBP: it jointly models next POI recommendation under the influence of users’ latent behavior pattern, which is determined by the periodic property of human mobility along with time and the transition periodicity of location categories [9]^{Footnote 3}.

Performance comparison on next POI recommendation

Full size image

The parameters are tuned in the training set to find the optimal values, and they are subsequently used in the testing set. Figure 3 depicts the detailed results. The results show that:

• FPMC-LR, PRME-G, and our model all outperform MF and PMF significantly. It indicates that spatial influence plays an important role in next POI recommendation. Moreover, our model consistently outperforms FPMC-LR, PRME-G and LBP, which leads to the conclusion that the consideration of transition interval preference can better capture users’ mobility in LBSNs.

• Our model has improved performance over baselines for next new POI recommendation. We argue that the gain also comes from the adoption of the transition interval preference. Since \(\hat{\chi }_{u,i,j}\) models the observed transitions, the history of visiting “next new POI” is blank (\(\hat{\chi }_{u,i,j}\approx 0\)) in the training data. Therefore, the performance enhancement to \(\hat{x}_{u,i,j}\) for next new POI recommendation is due to the part of \(w \cdot z_{u,i,j}\) in Eq. (8)^{Footnote 4}.

Tables 2 and 3 tabulate the comparison results when considering the next POI as a set of locations. It’s obvious to see that our proposed model consistently outperforms other baselines in terms of precision and recall. And the improvement is even better than that in Fig. 3, which further verifies the effectiveness of incorporating transition interval preference for predicting POIs within a time slot, say for the next \(\gamma \) hours. We can also observe that precisions of \(\gamma \)-hour next POI recommendation fluctuate with increasing the length of recommendation list, which mainly accounts to the nature of the dataset. Our collected check-in data is a relatively sparse dataset. For example, the users may only contribute few check-ins in the next \(\gamma \) hour, the precision will inevitably decreases with the size of the candidate list increasing according to Eq. (19). Thus, we argue that recall is a more proper measurement to evaluate the performance for next POI recommendation.

4.4 Performance Comparison on Transition Interval

The performance comparison on transition intervals is performed between our model and the following baselines: MF, PMF, and FPMC. However, to our best knowledge, our model is the first work which is capable of providing the transition interval for next POI, and capable of obtaining the transition interval and next POI recommendation simultaneously. There is no way to get the transition interval values along with the POI recommendation directly in MF, PMF, and FPMC. In order to perform the comparison, we use the transition interval matrix/tensor (from MF, PMF, and FPMC) between POIs to generate the unobserved transition intervals. That is, we factorize the observed transition matrix and interval matrix from them separately, and then align the results to get their transition intervals for next POIs.

Perf. comparison for transition interval prediction

Full size image

Transition interval prediction v.s. T

Full size image

Figure 4 shows the performance comparison on transition interval predictions. The results show that the proposed model always achieves the highest precision over baselines, which proves that our model is capable of providing effective POI recommendations to users as well as predicting how soon it will happen. We also compute MAPE between the predicted transition intervals and the ground truth of the test set (See Table 4). Lower values indicate more accurate predictions. It is evident that the proposed model outperforms the baselines by a significant margin. Figure 5 shows the performance comparison by relaxing the threshold T, and our method outperforms all the baselines again^{Footnote 5}.

This paper proposes a probabilistic approach for next POI recommendation by exploring the transition interval patterns of each user, and the expected transition interval for next move can also be learned simultaneously. Specifically, the proposed model considers the transition interval preference as a key component of the overall transition behavior and utilizes a continuous latent variable to model such preference. The objective function is to maximize the posterior probability of the overall transitions. Expectation Maximization (EM) algorithm is used to estimate the model parameters. The experimental results on the real-world datasets show that the proposed model outperforms the state-of-the-art methods in terms of next POI recommendation, next new POI recommendation, and the expected transition interval prediction. Our proposed model can be easily extended to recommend next basket items and the purchase interval of them by redefining the transition tensor. In addition, we look forward to deploying the proposed model for commercial purposes, such as Weixin App, where the POI recommendation is able to benefit the users and location-based service providers. In the future, we would like to study how to integrate other contextual information into our model, e.g. social relationship and textual content of POIs, which may deeply exploit users’ check-in behavior to enhance the recommendation performance.