# Exploiting Spatial and Temporal for Point of Interest Recommendation

Authors: Jinpeng Chen; Wen Zhang; Pei Zhang; Pinguang Ying; Kun Niu; Ming Zou
Journal: Complexity
 (2018)

---

## Abstract

An increasing number of users have been attracted by location-based social networks (LBSNs) in recent years. Meanwhile, user-generated content in online LBSNs like spatial, temporal, and social information provides an ever-increasing chance to study the human behavior movement from their spatiotemporal mobility patterns and spawns a large number of location-based applications. For instance, one of such applications is to produce personalized point of interest (POI) recommendations that users are interested in. Different from traditional recommendation methods, the recommendations in LBSNs come with two vital dimensions, namely, geographical and temporal. However, previously proposed methods do not adequately explore geographical influence and temporal influence. Therefore, fusing geographical and temporal influences for better recommendation accuracy in LBSNs remains potential. In this work, our aim is to generate a top recommendation list of POIs for a target user. Specially, we explore how to produce the POI recommendation by leveraging spatiotemporal information. In order to exploit both geographical and temporal influences, we first design a probabilistic method to initially detect users’ spatial orientation by analyzing visibility weights of POIs which are visited by them. Second, we perform collaborative filtering by detecting users’ temporal preferences. At last, for making the POI recommendation, we combine the aforementioned two approaches, that is, integrating the spatial and temporal influences, to construct a unified framework. Our experimental results on two real-world datasets indicate that our proposed method outperforms the current state-of-the-art POI recommendation approaches.


---

## Body

## 1. Introduction

With the development of location acquisition and wireless communication technologies, location-based social networks (LBSNs) like Foursquare (https://foursquare.com/), Gowalla (http://gowalla.com/), and Facebook Places (http://www.facebook.com/about/location/) have been growing rapidly. Because a location dimension is added to traditional social networks, users can easily share their location and experience about the point of interests (POIs) through check-in behaviors (see Figure 1 for an example), along with creating the opportunity to make new friends or get better recommendations. For instance, a user can use a mobile phone to leave comments regarding a hotel on an online social site. Other users can refer to the comments when they visit the hotel in a later time. In a way, it expands these users’ social networks.Figure 1
An example of check-in.Unprecedented large-scale check-in data, which describes a user’s mobile behavior in spatial, temporal, and content aspects, provides us with opportunities to design absorbing services to facilitate users’ travels and social interactions [1]. POI recommendation, one of such services, aims at recommending new POI (point of interest) to users who have not visited them before according to their personal preferences. Several methods are proposed for POI recommendation. Ye et al. recommended POIs using memory-based methods [2]. Cheng et al. improved the scalability leveraging model-based methods [3–5]. Zhang et al. recommended each user a list of restaurants by exploring users’ personal static check-in preferences through geographical check-ins [6]. Considering social friends who tend to have similar check-in behavior, some other researchers leverage the explicit social friendships on LBSNs to improve location recommendation services [7–9]. Among existing works, the temporal patterns of a user’s check-in behaviors have not been explored in depth.Yuan et al. pointed out users’ activities are often time-oriented [10]; that is, users’ mobile behavior exhibits vital temporal patterns on LBSNs and is highly relevant to the location property [11]. For example, a user may regularly go to the office in the morning, go to a restaurant for lunch at noon, and go to a pub at midnight. Therefore, the recommendation results should be influenced by time. So far, some researches consider the temporal influence when users visit locations on their check-in behaviors, but they cannot suggest the successive time for users to visit a recommended POI. For instance, users present considerably different patterns during weekdays and weekends. The temporal check-in preferences of users to locations are reflected by these weekday and weekend patterns [12]. Usually, most of the researches make time-aware location recommendations by suggesting properly visiting time on weekdays or weekends. A few researches are based on the successive time.In this paper, we focus on the problem of spatiotemporal aware POI recommendation, namely, exploiting spatial and temporal for POI recommendation, which aims at returning a set of POIs for a user to visit at a specified time in a day. We believe that this is a natural and useful extension to the conventional POI recommendation problem. However, it is challenging and crucial to predict where a man will visit at a given time point with complex temporal and spatial information.To exploit both geographical and temporal influences for spatiotemporal aware POI recommendation, we propose an approach incorporating spatial influence and temporal influence. First, in order to exploit the spatial behavior, we compute the user spatial orientation through the check-in history. The simple method is to count the number of visits duringF-checkin (FC)/U-checkin (UC) and recommend POIs based on the user’s spatial orientation. However, not all the POIs are the same in their impacts. We further adopt a more effective model to compute the user spatial orientation. Second, to exploit the temporal behavior in POI recommendations, we also show a method integrating temporal information. Intuitively, two users are more likely to go to homologous POIs at the same time if they show analogous temporal patterns. Thus, we perform collaborative filtering by fusing the user’s temporal predilection to POIs. At last, for making the POI recommendation, we combine the aforementioned two approaches, that is, integrating the spatial and temporal preferences, to construct a unified framework.In our experiments on two real-world datasets, the proposed method significantly outperforms state-of-the-art algorithms. The major contributions of this paper are summarized as follows:(i)
We focus on a new spatiotemporal aware POI recommendation problem, which aims at recommending specific POIs for a user.
(ii)
We denote the concept behind FC/UC-oriented users and present a probabilistic model to compute such spatial alignments.
(iii)
We develop POI recommendation methods that exploit the two kinds of influences, the temporal influence and the spatial influence. Moreover, we fuse the spatial and temporal influences with a framework to make the spatiotemporal aware POI recommendation.
(iv)
We evaluate the proposed POI recommendation method by comprehensive experiments on two real-world LBSN datasets collected from Foursquare and Gowalla, respectively. Experimental results show that our method outperforms the state-of-the-art methods in POI recommendation.The remaining of this paper is organized as follows: we first introduce the preliminaries on POI recommendation and denote the task of POI recommendation in Section2. We next present a more effective model computing the user spatial orientation in Section 3. Then, we show an approach incorporating temporal influence to exploit the temporal behavior in POI recommendations in Section 4. We report our experiments and results in Section 5, discuss related work in Section 6, and conclude the study in Section 7.


## 2. Preliminaries and Problem Definition

In this section, we denote some important concepts and the research problem of this paper.


### 2.1. Notation Definitions

In this work, we need to consider the following entities: a set of LBSN usersU=u1,u2,…,un, a set of locations (or POIs) L=l1,l2,…,lm, a set of check-ins of all users visiting all locations in a LBSN C=<ui,li,ti>i∣C∣, where cui,li,ti=<ui,li,ti> (also called check-in or visit) describes user ui visiting location li at time ti. Table 1 summarizes the key symbols used in this paper.Table 1
Symbols.
Symbol
Description
U
Set of all users
u
A user andu∈U
L
Set of all POIs
l
A POI andl∈L
T
A time interval
D¯
Set of all days
D
A day andD∈D¯
<u,l,t>
Check-in that depicts useru visiting location l at time t
C
Collection of check-ins of all users visiting all locations
FC
Set of check-ins, where the locationl of each check-in is familiar to user u
UC
Set of check-ins, where the locationl of each check-in is unfamiliar to user u


### 2.2. Problem Statement

Definition 1 (check-in).
A check-in is a trituple<u,l,t> which represents user u∈U visiting location l∈L at a given time t. Here, U and L are the sets of users and locations in a LBSN, respectively.Definition 2 (check-in set).
A check-in setC=<ui,li,ti>i∣C∣ is a set of check-ins of all users visiting all locations in a LBSN, where C denotes the number of check-ins in C.Definition 3 (F-checkin).
F-checkin FC=<ui,li,ti>i∣F∣ is a set of check-ins, where the location li of each check-in is familiar to user ui and F denotes the number of check-ins in C. Here, a location li is considered familiar to user ui if one of the following two cases holds. Given a time-spent ratio Δt and a check-in number n, li is familiar regarding Δt and n, if (1) TFuli≥Δt, namely, the time spent of u to li is at least Δt and (2) the number of check-ins of u to li is at least n.
Formally, we denoteD¯uli as the set of days on which u check in at li. By D¯u, we denote all the days on which user u check in at any place. We say that the time spent of u at li is the ratio TFuli=D¯uli/D¯u. Here, the larger the ratio, the more familiar the user is with the location li.Definition 4 (U-checkin).
U-checkin UC=<ui,li,ti>i∣U∣ is a set of check-ins, where the location li of each check-in is unfamiliar to user ui and U denotes the number of check-ins in C. Here, a location li is considered unfamiliar to user ui if one of the following two cases holds. Given a time-spent ratio Δt and a check-in number n, li is unfamiliar regarding Δt and n, if (1) TFuli<Δt, namely, the time spent of u to li is less than Δt or (2) the number of check-ins of u to li is less than n.Definition 5 (POI spatial orientation).
We define eachlj (lj∈L) has a spatial orientation denoted as ljo which is the margin value (−1,+1) between its probabilities to be visited between F-checkin and U-checkin.
(1)ljo=WjFNj−WjUNj,where WjF and WjU define the number of visits at lj between F-checkin and U-checkin. Nj is the total number of visits. If ljo is more than zero, it will indicate an alignment toward F-checkin, and if it is less than zero, it will show lj is visited more during U-checkin.Definition 6 (user spatial orientation).
We denote that eachui (ui∈U) has a spatial orientation defined as uio which is the margin value (−1,+1) between probabilities of her F-checkin and U-checkin visits.
(2)uio=AvgiF−AvgiU,where AvgiF and AvgiU are probabilities for ui to visit locations during F-checkin and U-checkin, respectively. If uio is greater than 0, it will reflect ui’s spatial preference toward F-checkin, and if it is less than 0, it indicates that she is more interested in U-checkin.


### 2.3. Problem Definition

Given a check-in setC, a user u, and a time interval T, our aim is to detect the probability of user u visiting location l∈L at time interval T, defined as Pl∣u,T,C, then return a top-k list of locations with the maximum probability for u at time interval T.


## 2.1. Notation Definitions

In this work, we need to consider the following entities: a set of LBSN usersU=u1,u2,…,un, a set of locations (or POIs) L=l1,l2,…,lm, a set of check-ins of all users visiting all locations in a LBSN C=<ui,li,ti>i∣C∣, where cui,li,ti=<ui,li,ti> (also called check-in or visit) describes user ui visiting location li at time ti. Table 1 summarizes the key symbols used in this paper.Table 1
Symbols.
Symbol
Description
U
Set of all users
u
A user andu∈U
L
Set of all POIs
l
A POI andl∈L
T
A time interval
D¯
Set of all days
D
A day andD∈D¯
<u,l,t>
Check-in that depicts useru visiting location l at time t
C
Collection of check-ins of all users visiting all locations
FC
Set of check-ins, where the locationl of each check-in is familiar to user u
UC
Set of check-ins, where the locationl of each check-in is unfamiliar to user u


## 2.2. Problem Statement

Definition 1 (check-in).
A check-in is a trituple<u,l,t> which represents user u∈U visiting location l∈L at a given time t. Here, U and L are the sets of users and locations in a LBSN, respectively.Definition 2 (check-in set).
A check-in setC=<ui,li,ti>i∣C∣ is a set of check-ins of all users visiting all locations in a LBSN, where C denotes the number of check-ins in C.Definition 3 (F-checkin).
F-checkin FC=<ui,li,ti>i∣F∣ is a set of check-ins, where the location li of each check-in is familiar to user ui and F denotes the number of check-ins in C. Here, a location li is considered familiar to user ui if one of the following two cases holds. Given a time-spent ratio Δt and a check-in number n, li is familiar regarding Δt and n, if (1) TFuli≥Δt, namely, the time spent of u to li is at least Δt and (2) the number of check-ins of u to li is at least n.
Formally, we denoteD¯uli as the set of days on which u check in at li. By D¯u, we denote all the days on which user u check in at any place. We say that the time spent of u at li is the ratio TFuli=D¯uli/D¯u. Here, the larger the ratio, the more familiar the user is with the location li.Definition 4 (U-checkin).
U-checkin UC=<ui,li,ti>i∣U∣ is a set of check-ins, where the location li of each check-in is unfamiliar to user ui and U denotes the number of check-ins in C. Here, a location li is considered unfamiliar to user ui if one of the following two cases holds. Given a time-spent ratio Δt and a check-in number n, li is unfamiliar regarding Δt and n, if (1) TFuli<Δt, namely, the time spent of u to li is less than Δt or (2) the number of check-ins of u to li is less than n.Definition 5 (POI spatial orientation).
We define eachlj (lj∈L) has a spatial orientation denoted as ljo which is the margin value (−1,+1) between its probabilities to be visited between F-checkin and U-checkin.
(1)ljo=WjFNj−WjUNj,where WjF and WjU define the number of visits at lj between F-checkin and U-checkin. Nj is the total number of visits. If ljo is more than zero, it will indicate an alignment toward F-checkin, and if it is less than zero, it will show lj is visited more during U-checkin.Definition 6 (user spatial orientation).
We denote that eachui (ui∈U) has a spatial orientation defined as uio which is the margin value (−1,+1) between probabilities of her F-checkin and U-checkin visits.
(2)uio=AvgiF−AvgiU,where AvgiF and AvgiU are probabilities for ui to visit locations during F-checkin and U-checkin, respectively. If uio is greater than 0, it will reflect ui’s spatial preference toward F-checkin, and if it is less than 0, it indicates that she is more interested in U-checkin.


## 2.3. Problem Definition

Given a check-in setC, a user u, and a time interval T, our aim is to detect the probability of user u visiting location l∈L at time interval T, defined as Pl∣u,T,C, then return a top-k list of locations with the maximum probability for u at time interval T.


## 3. Spatial Patterns of Users

In this section, we setup observations based on primary definitions. We verify that certain POIs and users are aligned toward eitherF-checkin or U-checkin.


### 3.1. Absolute User Spatial Orientation Observation

We setup observations to perceive that certain users can be oriented towardF-checkin or U-checkin. We use threshold N to reflect the extent of alignment.


#### 3.1.1. Absolute POI Spatial Orientation

For eachlj visited by a set of users Uj, we calculate ljo∗ as an absolute rate of spatial F-checkin/U-checkin deviation. We select locations which have been visited by at least 5 users (∀lj∈L∣Uj>5).
(3)ljo∗=∑ui∈Ujli,jF−li,jUUj,where li,jF and li,jU are the probabilities of each ui∈Uj to visit lj during F-checkin and U-checkin. Overall, li,jF and li,jU can be calculated using the following equations, where the first part of the equation is the TF value of F-checkin (or U-checkin) in user ui’s location history and the second part denotes the IDF value of the user spatial orientation.
(4)li,jF=Wi,jFWi,j×lgUjui:lij∈FC,li,jU=Wi,jUWi,j×lgUjui:lij∈UC.Here,Wi,j is the total number of times that user ui has visited lj, and Uj is the total number of users visiting lj. Similarly, Wi,jF and Wi,jU record the visits performed exclusively during F-checkin and U-checkin. ui:lij∈FC and ui:lij∈UC record the number of users exclusively visiting lj during F-checkin and U-checkin.


#### 3.1.2. Absolute User Spatial Orientation Observation

For each userui with Li, we compute uio∗ as her average rate of absolute spatial F-checkin/U-checkin deviation. We select users who have visited at least 5 POIs (∀ui∈U∣Li>5). The following equation illustrates relevant probability which reflects to what extent each user is spatially oriented:
(5)uio∗=∑lj∈Lili,joLi,where li,jo is lj’s absolute POI spatial orientation limited to ui’s visits.Ifuio∗ is less than N (20%), we can ensure that ui is not oriented toward F-checkin or U-checkin. However, we find 67.6% and 59.3% of users in Foursquare and Gowalla have an absolute spatial deviation more than the N. Also, more than 15% of users are highly aligned toward F-checkin or U-checkin (uio∗>48%).Based on the observations conducted in LBSN, we can conclude that spatial influences exist for users.


### 3.2. Spatial Orientation Efficient Model

In this section, we present a more effective model to compute the user spatial orientation. First, we obtain users’ spatial orientation towardF-checkin or U-checkin. Therefore, we compute the POI spatial orientation for each location (lj∈L) visited by ui. We detect positive or negative impacts using the following equations:
(6)l¯i,jF=li,jF−ζ,l¯i,jU=li,jU−ζ,where ζ∈0,1 serves as a separator of FC/UC margins. We assume that the POI with higher probability to be visited by a user (visiting score) should play a more significant role in the computation of her spatial orientation. We compute the visiting score for each location (lj) using the method [2] which comprises three influential factors of user preference, social influence, and geographical influence. To calculate the visiting score, we first remove each lj from Li, then obtain the probability (ci,j) of ui to visit lj considering all three factors. We normalize the score utilizing the following equation:
(7)c^i,j=ci,j−MinciMaxci−Minci,where Maxci=argmaxCi,k and Minci=argminCi,k (∀lk∈Li). Further, we use the following equation to capture the final F-checkin orientation probability for each lj∈Li:
(8)Pri,jF=c^i,j∗l¯i,jF=ci,j−MinciMaxci−Minci∗li,jF−ζ.Similarly, theU-checkin orientation probability can be computed as follows:
(9)Pri,jU=c^i,j∗l¯i,jU=ci,j−MinciMaxci−Minci∗li,jU−ζ.The higherc^i,j is, the more likely this location will be visited by ui and will be more influential on ui’s spatial orientation. Finally, the user spatial orientation is captured through the following equation.
(10)u^io=A^vgiF−A^vgiU,where A^vgiF and A^vgiU are respective FC/UC average ratios:
(11)A^vgiF=∑lj∈LiPri,jFLi,A^vgiU=∑lj∈LiPri,jULi.For the value ofA^vgiF−A^vgiU, if it is more than zero, it will indicate that the user is aligned toward F-checkin and, if it is less than zero, it will show U-checkin orientation.


### 3.3. Spatial Orientation-Based Recommendation

In this section, we present the framework to produce a ranked list of candidate POIs for each user disregarding the extent of her spatial orientation. Leveraging check-in history, our method can suggest Top@Num appealing locations for each user. This method mainly considers users’ preference on POIs. By inferring possible categories of the next check-in POI, irrelevant POIs can be filtered (i.e., only POIs in the corresponding categories are considered); in other words, the method can reliably predict users’ preference.After obtaining users’ spatial orientation, we further infer categories for each location inF-checkin or U-checkin. We associate each location l=<lat,long> with a set of categories of venues that are within a 100-meter radius of the location; that is, catel=v⋅cate∣distancev,l≤100m, where v represents the venue.In order to show our method, we further define the set of categories associated with a locationl as Cgl. Assuming the last visited location l^, a likely category c^g can be found for l^. Then, a category cg that is likely to be followed after c^g can be determined. At last, a predicted location l that is likely for the category cg can be found. In order to associate a probability with each value of l, we define the following equation:
(12)PCGl=∑cg,c^gPl∣cg⋅α∗Pgcg∣c^g+1−α∗Pucg∣c^g⋅Pc^g∣l^,where Pgcg∣c^g and Pucg∣c^g represent the probability of the user visiting a location of category cg after visiting one of the categories c^g, as estimated by the global check-in history across all users, and the user’s own check-in history, respectively. α is a balance parameter that controls the relative weighting of Pu and Pg. Pl∣cg and Pc^g∣l^ can be calculated as follows:
(13)Pl∣cg=Ncl∑locNloc,Pc^g∣l^=NclNl,where Ncl represents the number of venues of category cg close to l, Nl represents the total number of venues close to l, and Nloc represents the number of venues of category cg close to loc.


## 3.1. Absolute User Spatial Orientation Observation

We setup observations to perceive that certain users can be oriented towardF-checkin or U-checkin. We use threshold N to reflect the extent of alignment.


### 3.1.1. Absolute POI Spatial Orientation

For eachlj visited by a set of users Uj, we calculate ljo∗ as an absolute rate of spatial F-checkin/U-checkin deviation. We select locations which have been visited by at least 5 users (∀lj∈L∣Uj>5).
(3)ljo∗=∑ui∈Ujli,jF−li,jUUj,where li,jF and li,jU are the probabilities of each ui∈Uj to visit lj during F-checkin and U-checkin. Overall, li,jF and li,jU can be calculated using the following equations, where the first part of the equation is the TF value of F-checkin (or U-checkin) in user ui’s location history and the second part denotes the IDF value of the user spatial orientation.
(4)li,jF=Wi,jFWi,j×lgUjui:lij∈FC,li,jU=Wi,jUWi,j×lgUjui:lij∈UC.Here,Wi,j is the total number of times that user ui has visited lj, and Uj is the total number of users visiting lj. Similarly, Wi,jF and Wi,jU record the visits performed exclusively during F-checkin and U-checkin. ui:lij∈FC and ui:lij∈UC record the number of users exclusively visiting lj during F-checkin and U-checkin.


### 3.1.2. Absolute User Spatial Orientation Observation

For each userui with Li, we compute uio∗ as her average rate of absolute spatial F-checkin/U-checkin deviation. We select users who have visited at least 5 POIs (∀ui∈U∣Li>5). The following equation illustrates relevant probability which reflects to what extent each user is spatially oriented:
(5)uio∗=∑lj∈Lili,joLi,where li,jo is lj’s absolute POI spatial orientation limited to ui’s visits.Ifuio∗ is less than N (20%), we can ensure that ui is not oriented toward F-checkin or U-checkin. However, we find 67.6% and 59.3% of users in Foursquare and Gowalla have an absolute spatial deviation more than the N. Also, more than 15% of users are highly aligned toward F-checkin or U-checkin (uio∗>48%).Based on the observations conducted in LBSN, we can conclude that spatial influences exist for users.


## 3.1.1. Absolute POI Spatial Orientation

For eachlj visited by a set of users Uj, we calculate ljo∗ as an absolute rate of spatial F-checkin/U-checkin deviation. We select locations which have been visited by at least 5 users (∀lj∈L∣Uj>5).
(3)ljo∗=∑ui∈Ujli,jF−li,jUUj,where li,jF and li,jU are the probabilities of each ui∈Uj to visit lj during F-checkin and U-checkin. Overall, li,jF and li,jU can be calculated using the following equations, where the first part of the equation is the TF value of F-checkin (or U-checkin) in user ui’s location history and the second part denotes the IDF value of the user spatial orientation.
(4)li,jF=Wi,jFWi,j×lgUjui:lij∈FC,li,jU=Wi,jUWi,j×lgUjui:lij∈UC.Here,Wi,j is the total number of times that user ui has visited lj, and Uj is the total number of users visiting lj. Similarly, Wi,jF and Wi,jU record the visits performed exclusively during F-checkin and U-checkin. ui:lij∈FC and ui:lij∈UC record the number of users exclusively visiting lj during F-checkin and U-checkin.


## 3.1.2. Absolute User Spatial Orientation Observation

For each userui with Li, we compute uio∗ as her average rate of absolute spatial F-checkin/U-checkin deviation. We select users who have visited at least 5 POIs (∀ui∈U∣Li>5). The following equation illustrates relevant probability which reflects to what extent each user is spatially oriented:
(5)uio∗=∑lj∈Lili,joLi,where li,jo is lj’s absolute POI spatial orientation limited to ui’s visits.Ifuio∗ is less than N (20%), we can ensure that ui is not oriented toward F-checkin or U-checkin. However, we find 67.6% and 59.3% of users in Foursquare and Gowalla have an absolute spatial deviation more than the N. Also, more than 15% of users are highly aligned toward F-checkin or U-checkin (uio∗>48%).Based on the observations conducted in LBSN, we can conclude that spatial influences exist for users.


## 3.2. Spatial Orientation Efficient Model

In this section, we present a more effective model to compute the user spatial orientation. First, we obtain users’ spatial orientation towardF-checkin or U-checkin. Therefore, we compute the POI spatial orientation for each location (lj∈L) visited by ui. We detect positive or negative impacts using the following equations:
(6)l¯i,jF=li,jF−ζ,l¯i,jU=li,jU−ζ,where ζ∈0,1 serves as a separator of FC/UC margins. We assume that the POI with higher probability to be visited by a user (visiting score) should play a more significant role in the computation of her spatial orientation. We compute the visiting score for each location (lj) using the method [2] which comprises three influential factors of user preference, social influence, and geographical influence. To calculate the visiting score, we first remove each lj from Li, then obtain the probability (ci,j) of ui to visit lj considering all three factors. We normalize the score utilizing the following equation:
(7)c^i,j=ci,j−MinciMaxci−Minci,where Maxci=argmaxCi,k and Minci=argminCi,k (∀lk∈Li). Further, we use the following equation to capture the final F-checkin orientation probability for each lj∈Li:
(8)Pri,jF=c^i,j∗l¯i,jF=ci,j−MinciMaxci−Minci∗li,jF−ζ.Similarly, theU-checkin orientation probability can be computed as follows:
(9)Pri,jU=c^i,j∗l¯i,jU=ci,j−MinciMaxci−Minci∗li,jU−ζ.The higherc^i,j is, the more likely this location will be visited by ui and will be more influential on ui’s spatial orientation. Finally, the user spatial orientation is captured through the following equation.
(10)u^io=A^vgiF−A^vgiU,where A^vgiF and A^vgiU are respective FC/UC average ratios:
(11)A^vgiF=∑lj∈LiPri,jFLi,A^vgiU=∑lj∈LiPri,jULi.For the value ofA^vgiF−A^vgiU, if it is more than zero, it will indicate that the user is aligned toward F-checkin and, if it is less than zero, it will show U-checkin orientation.


## 3.3. Spatial Orientation-Based Recommendation

In this section, we present the framework to produce a ranked list of candidate POIs for each user disregarding the extent of her spatial orientation. Leveraging check-in history, our method can suggest Top@Num appealing locations for each user. This method mainly considers users’ preference on POIs. By inferring possible categories of the next check-in POI, irrelevant POIs can be filtered (i.e., only POIs in the corresponding categories are considered); in other words, the method can reliably predict users’ preference.After obtaining users’ spatial orientation, we further infer categories for each location inF-checkin or U-checkin. We associate each location l=<lat,long> with a set of categories of venues that are within a 100-meter radius of the location; that is, catel=v⋅cate∣distancev,l≤100m, where v represents the venue.In order to show our method, we further define the set of categories associated with a locationl as Cgl. Assuming the last visited location l^, a likely category c^g can be found for l^. Then, a category cg that is likely to be followed after c^g can be determined. At last, a predicted location l that is likely for the category cg can be found. In order to associate a probability with each value of l, we define the following equation:
(12)PCGl=∑cg,c^gPl∣cg⋅α∗Pgcg∣c^g+1−α∗Pucg∣c^g⋅Pc^g∣l^,where Pgcg∣c^g and Pucg∣c^g represent the probability of the user visiting a location of category cg after visiting one of the categories c^g, as estimated by the global check-in history across all users, and the user’s own check-in history, respectively. α is a balance parameter that controls the relative weighting of Pu and Pg. Pl∣cg and Pc^g∣l^ can be calculated as follows:
(13)Pl∣cg=Ncl∑locNloc,Pc^g∣l^=NclNl,where Ncl represents the number of venues of category cg close to l, Nl represents the total number of venues close to l, and Nloc represents the number of venues of category cg close to loc.


## 4. Leveraging Temporal Influence

In this section, we first show the baseline user-based CF method. We then present the method of incorporating time influence in the user-based CF. At last, we propose a unified framework.


### 4.1. User-Based Collaborative Filtering

For a user, the CF method first computes the similarity between this user and other users and then generates a POI prediction through the weighted combination of other users’ check-in records on the POI. Specifically, if userui has visited (or checked in) l, we set cui,l=1; otherwise, cui,l=0. Assuming a user uj, the score that uj will visit a POI l which she has not visited before is obtained using the following equation:
(14)c^uj,l=∑ui∈U/ujwuj,uicui,l∑ui∈U/ujwuj,ui,where wuj,ui is the similarity between user uj and ui. The similarity between two users wuj,ui can be calculated by various measures. In all these measures, cosine similarity is a widely applied measure for implicit data. In this work, we also adopt cosine similarity.


### 4.2. Incorporating Temporal Influence

As reported in [2], check-ins constituting spatiotemporal traces follow strong periodic patterns. For example, people tend to check in restaurants at lunchtime and people often go to places of leisure and tourism on weekends, go to work, and study places during weekdays. In this work, days first can be divided into two subsets which are the weekday set (Dd) and the weekend set (De), where D¯=Dd,De. Then, a day can be split into multiple equal time slots based on the hour. Further, we express the behavior of a user at a specific time by a set of check-ins that the user has done at that time. We use cu,t,D,l to represent the check-in activity of a user u, at a POI l at time slot t of a day D. Here, if user u has checked in POI l at time t of a day D, we set cu,t,D,l=1; otherwise, cu,t,D,l=0.To make time-aware POI recommendations by considering the temporal influence, the user-based CF model can be extended from the two aspects: (a) computing the similarity between two users utilizing the temporal factor; (b) only the historical check-ins at timet in the repository are considered during recommendations.By fusing the temporal factor, (14) can be updated as follows:
(15)c^uj,t,D,lt=∑ui∈U/ujwuj,uitcui,t,Dd,l∑ui∈U/ujwuj,uit,ifDd∈Dd,∑ui∈U/ujwuj,uitcui,t,De,l∑ui∈U/ujwuj,uit,ifDe∈De,where wuj,uit is the temporal behavior similarity between uj and ui. Next, we will describe the computation of the temporal behavior similarity wuj,uit.We estimate the similarity between two users based on their temporal behaviors over all time. To be specific, if two users always visit the same POIs at the same time slot, the similarity between these two users will be high. Further, we extend the cosine similarity measure to compute the similarity betweenuj and ui as follows:
(16)wuj,uit=∑t=1T∑k=1Lcuj,t,D,lkcui,t,D,lk∑t=1T∑k=1Lcuj,t,D,lk2∑t=1T∑k=1Lcui,t,D,lk2.


### 4.3. A Unified Framework

Given a useru, time t, and a candidate POI l, we can calculate a score Pl∣Li that user u will check in l at t using the method incorporating spatial influence. Similarly, we can also compute a score c^uj,t,D,lt leveraging the method incorporating temporal influence.We compute the final recommendation score for POIl using linear interpolation to weight the two scores. Specifically, we calculate the combined score that user ui will check in POI l at time slot t utilizing the following equation, where β is a tuning parameter:
(17)cui,t,l=β∗PCGl+1−β∗c^uj,t,D,lt.Through this framework, we compute the check-in score for each candidate POI and generate the topNum list of recommended POIs for each user.Here, the computing cost consists of the calculation of spatial orientation-based recommendation and incorporating temporal influence. The training time for the spatial orientation-based recommendation scales linearly with the number of venue categoryNcl. For the calculation of incorporating temporal influence, the time complexity is OU2 where ∣U∣ is the number of observing users. Then, the time complexity can be estimated as ONcl+U2.


## 4.1. User-Based Collaborative Filtering

For a user, the CF method first computes the similarity between this user and other users and then generates a POI prediction through the weighted combination of other users’ check-in records on the POI. Specifically, if userui has visited (or checked in) l, we set cui,l=1; otherwise, cui,l=0. Assuming a user uj, the score that uj will visit a POI l which she has not visited before is obtained using the following equation:
(14)c^uj,l=∑ui∈U/ujwuj,uicui,l∑ui∈U/ujwuj,ui,where wuj,ui is the similarity between user uj and ui. The similarity between two users wuj,ui can be calculated by various measures. In all these measures, cosine similarity is a widely applied measure for implicit data. In this work, we also adopt cosine similarity.


## 4.2. Incorporating Temporal Influence

As reported in [2], check-ins constituting spatiotemporal traces follow strong periodic patterns. For example, people tend to check in restaurants at lunchtime and people often go to places of leisure and tourism on weekends, go to work, and study places during weekdays. In this work, days first can be divided into two subsets which are the weekday set (Dd) and the weekend set (De), where D¯=Dd,De. Then, a day can be split into multiple equal time slots based on the hour. Further, we express the behavior of a user at a specific time by a set of check-ins that the user has done at that time. We use cu,t,D,l to represent the check-in activity of a user u, at a POI l at time slot t of a day D. Here, if user u has checked in POI l at time t of a day D, we set cu,t,D,l=1; otherwise, cu,t,D,l=0.To make time-aware POI recommendations by considering the temporal influence, the user-based CF model can be extended from the two aspects: (a) computing the similarity between two users utilizing the temporal factor; (b) only the historical check-ins at timet in the repository are considered during recommendations.By fusing the temporal factor, (14) can be updated as follows:
(15)c^uj,t,D,lt=∑ui∈U/ujwuj,uitcui,t,Dd,l∑ui∈U/ujwuj,uit,ifDd∈Dd,∑ui∈U/ujwuj,uitcui,t,De,l∑ui∈U/ujwuj,uit,ifDe∈De,where wuj,uit is the temporal behavior similarity between uj and ui. Next, we will describe the computation of the temporal behavior similarity wuj,uit.We estimate the similarity between two users based on their temporal behaviors over all time. To be specific, if two users always visit the same POIs at the same time slot, the similarity between these two users will be high. Further, we extend the cosine similarity measure to compute the similarity betweenuj and ui as follows:
(16)wuj,uit=∑t=1T∑k=1Lcuj,t,D,lkcui,t,D,lk∑t=1T∑k=1Lcuj,t,D,lk2∑t=1T∑k=1Lcui,t,D,lk2.


## 4.3. A Unified Framework

Given a useru, time t, and a candidate POI l, we can calculate a score Pl∣Li that user u will check in l at t using the method incorporating spatial influence. Similarly, we can also compute a score c^uj,t,D,lt leveraging the method incorporating temporal influence.We compute the final recommendation score for POIl using linear interpolation to weight the two scores. Specifically, we calculate the combined score that user ui will check in POI l at time slot t utilizing the following equation, where β is a tuning parameter:
(17)cui,t,l=β∗PCGl+1−β∗c^uj,t,D,lt.Through this framework, we compute the check-in score for each candidate POI and generate the topNum list of recommended POIs for each user.Here, the computing cost consists of the calculation of spatial orientation-based recommendation and incorporating temporal influence. The training time for the spatial orientation-based recommendation scales linearly with the number of venue categoryNcl. For the calculation of incorporating temporal influence, the time complexity is OU2 where ∣U∣ is the number of observing users. Then, the time complexity can be estimated as ONcl+U2.


## 5. Experiments

In this section, we systematically evaluate the performance of the proposed method and compare our method with the state-of-the-art methods on two real-world datasets. First, we describe the experimental setting, then compare the performance of these methods, and finally study the effect of percentages of training data, the effect of numbers of check-in POIs of users, and the effect of the length of the time slot.


### 5.1. Experimental Setup

#### 5.1.1. Dataset

Our experiments are conducted based on the two datasets from real-world LBSNs, Foursquare and Gowalla. Foursquare check-in data is within Singapore between August 2010 and July 2011, provided by Yuan et al. [10]. Gowalla check-in data was made in Austin between November 2009 and October 2010 [7]. Each check-in contains user, time, and POI ID information. For both datasets, we removed users who have checked in fewer than 5 POIs and then removed POIs fewer than 5 users checked in. After preprocessing, the Foursquare dataset has 194,108 check-ins made by 2321 users at 5596 POIs, and the Gowalla dataset contains 201,525 check-ins made by 4630 users at 6176 POIs. Relevant statistics are shown in Table 2.Table 2
Dataset statistics (after preprocessing).
Dataset
Number of check-ins
Number of users
Number of POIs
Foursquare
194,108
2321
5596
Gowalla
201,525
4630
6176In order to estimate the performance of our proposed method, we split the Foursquare dataset and the Gowalla dataset into two nonoverlapping sets: a training set and a test set, respectively. Here, the proportion of training data is tested on 70% and 80%, respectively. For example, training data 70% means we randomly select 70% of the observed data for each user as the training data to predict the remaining 30% data. The random selection was carried out 5 times independently, and we report the average results. The hyperparameters are tuned on the training dataset.


#### 5.1.2. Evaluation Metrics

A POI recommendation algorithm is to compute a ranking score for each candidate POI (i.e., POI that the user has not visited) and returns the top-N highest ranked locations as recommendations to a target user. To study the effectiveness of the proposed methods, we are interested in the following: (1) how many previously hold-off locations are recommended to the users among the total number of recommended locations and (2) how many previously hold-off locations are recommended to the users among the total number of hold-off locations. More specifically, we examine two metrics: namely, precision@Num and recall@Num (defined by pre@Num and rec@Num, resp.), whereNum is the size of the next POI candidate list, following the work [13, 14]. Given a user u and a time t, the precision and recall for time slot t are calculated as follows:
(18)pre@Numt=∑u∈UTop@Numu,t∩Lu,t∑u∈UTop@Numu,t,rec@Numt=∑u∈UTop@Numu,t∩Lu,t∑u∈ULu,t,where Top@Numu,t is a set of locations recommended to user u that u has not visited in the training set. Lu,t is a set of locations that has been visited by u in the testing set.The overall precision and recall are calculated by averaging the precision and recall values over all time slots, respectively.(19)pre@Num=1T∑t∈Tpre@Numt,rec@Num=1T∑t∈Trec@Numt.As suggested in [2, 10], both the Foursquare and Gowalla datasets have very low density, so recommendation methods show relatively low precision and recall values. In addition, the POIs in the test set of each user may represent only a small portion of POIs that the user may be interested in. Therefore, the low precision and recall obtained in our experiment are common and reasonable. In this work, we focus on the relative improvements we obtained comparing with baseline methods, instead of the absolute values.


#### 5.1.3. Recommendation Methods

Recommendation methods used in the experiments are as follows:(i)
User-based CF (UBCF): the basic user-based collaborative filtering.
(ii)
USG: it takes advantage of three modules of user-based CF, social influence, and geographical influence, where0<α<1 and 0<β<1 [2].
(iii)
LRT: by leveraging the temporal influence, it separately learns the user check-in preferences to locations at each time slot from the check-in user-location matrix at the corresponding time slot only based on matrix factorization with the temporal regularization term [11].
(iv)
UTE-SE: it is the time-aware user-based CF incorporating geographical influence [10].
(v)
STELLAR: it proposes a spatial-temporal latent ranking method to explicitly model the interactions among users, POI, and time, which is based on a ranking-based pairwise tensor factorization framework with a fine-grained modeling of user-POI, POI-time, and POI-POI interactions [15].
(vi)
FPMC: it presents a fourth-order tensor factorization-based ranking approach to produce the interesting locations for users [16].
(vii)
TRM: it puts forward a unified probabilistic generative model, which simultaneously detects the semantic, temporal, and spatial patterns of users’ check-in activities, to help users make a decision to visit the places they are interested in [17].
(viii)
TICRec: it is a probabilistic framework to use temporal influence correlations for location recommendations in location-based social networks [18].


### 5.2. Impact of Parameterβ

In our method, the parameterβ is an important factor to control the balance between geographical influence and temporal influence affecting the location recommendation performance. Figure 2 shows the impact of β of both the Foursquare and the Gowalla datasets on pre@10 and rec@10. From Figure 2(a), we can see that in both Foursquare and Gowalla, the pre@10 of our proposed method shows a fluctuant trend with the increase of β. It is worth noting that the pre@10 for our proposed method quickly decreases on the Foursquare dataset when β reaches 0.6, while the pre@10 for our proposed method on the Gowalla dataset shows a stable tendency when the value of β is greater than 0.6. In terms of rec@10 (Figure 2(b)), we easily obtain a similar conclusion. Therefore, we conclude that our proposed method performs better when the value of β is 0.6. In other words, the obtained results indicate that geographical influence plays a more important role than temporal influence in personalized POI recommendation.Figure 2
Impact of parameterβ.
(a)
pre@10
(b)
rec@10


### 5.3. Impact of Parametern

In our method, the parametern (Definition 3) is a vital factor affecting the location recommendation performance. Figure 3 shows the impact of n of both the Foursquare and the Gowalla datasets on pre@10 and rec@10. From Figure 3, we can see that with the increase of the parameter n, the pre@10 and rec@10 of our proposed method on both datasets are trending upward. It is worth noting that the pre@10 and rec@10 for our proposed method show a stable tendency when the parameter n reaches 14. Therefore, we take the parameter n=14 as an optimal value in the following experiments.Figure 3
Impact of parametern.
(a)
pre@10
(b)
rec@10


### 5.4. Performance Comparison

In this section, we will discuss the results to summarize our findings. Figures4 and 5 illustrate the performance comparison for the Foursquare and Gowalla datasets. From Figure 4(a), it can be clearly seen that our proposed method significantly outperforms other prediction methods. In terms of precision, our method achieves a 0.286–3.61% average improvement compared with the other eight methods. Here, UBCF does not outperform any other seven methods under any measure. The possible reason is that UBCF mainly considers users’ preferences, and ignores other important features, like social influence, geographical influence and temporal influence. Compared to USG and LRT, UTE-SE method always exhibits better results. This is because UTE-SE exploits the time information and the geographical information, while the other two methods only consider the time information. Compared to UTE-SE, STELLAR performs better. This is because STELLAR depicts the temporal effect with a latent feature, which gets rid of the sparse problem. Also, compared with STELLAR, FPMC, TRM, and TICRec, our method improves the average precision by 0.287%, 0.285%, 0.284%, and 0.283%, respectively. The main reason is that these methods ignore an important factor, spatial orientation. In terms of recall (in Figure 4(b)), our method achieves a 3.97–22.87% average improvement compared with the other eight methods. Because of the space limit, the similar analysis is shown in Figure 5. In addition, we observe that all methods perform much better on the Gowalla dataset than on the Foursquare dataset, even though it is sparser. The reason lies in Foursquare data which contains much less POIs.Figure 4
Performance comparison on the Gowalla dataset.
(a)
Gowalla (pre@Num)
(b)
Gowalla (rec@Num)Figure 5
Performance comparison on the Foursquare dataset.
(a)
Foursquare (pre@Num)
(b)
Foursquare (rec@Num)


### 5.5. Effect of Percentages of Training Data

Figures6 and 7 describe the recommendation accuracy of UBCF, USG, LTR, UTE-SE, STELLAR, and our method with respect to varying the percentages of training data. As shown, with the rise of the percentage of the training data, the precision and recall of all methods steadily increase. The possible reason is that the training data set becomes denser as the percentage of the training data rises, which is helpful for recommendation methods to learn users’ preferences on POIs.Figure 6
Effect of percentages of training data on the Gowalla dataset.
(a)
Gowalla (precision)
(b)
Gowalla (recall)Figure 7
Effect of percentages of training data on the Foursquare dataset.
(a)
Foursquare (precision)
(b)
Foursquare (recall)


### 5.6. Effect of Numbers of Check-In POIs of Users

Figures8 and 9 depict the recommendation accuracy regarding the change of the number of check-in (or visited) locations of users in the training set. For example, a measure at “Check in-n=5” is averaged on all users who have checked in five locations in the training set. With the increase of the number of visited locations of users, our method can more accurately estimate the time probability density and predict the visiting probability of new locations for these users at the corresponding hour through using more check-in data. As a whole, the precision and recall incline accordingly.Figure 8
Effect of numbers of check-in locations of users on the Gowalla Dataset.
(a)
Gowalla (precision)
(b)
Gowalla (recall)Figure 9
Effect of numbers of check-in locations of users on Foursquare Dataset.
(a)
Foursquare (precision)
(b)
Foursquare (recall)


### 5.7. Effect of the Length of Time Slot

Figures10 and 11 depict the recommendation accuracy when varying the length of time slots. The length of time slot controls the time granularity of time-aware POI recommendations. Intuitively, a smaller length of time slot indicates that the recommendation results will be more time-specific. Here, we only compare the methods considering temporal influence to focus on the effect of the length of time slot. As shown, we observe that, with the increasing of the time slot length, the precision of all methods gradually increases, but the recall inclines. The possible reason is that on the one hand, increasing the length of the time slot makes the data denser, benefitting for recommendation methods to estimate the accurate visiting probability of users to locations and, on the other hand, the larger length of time slots brings in a larger number of ground truth locations. Due to the number of recommendations (i.e., Num) unchanged, recall values are decreasing with increasing the length of time slot. More importantly, for all lengths of time slots, our method consistently outperforms the state-of-the-art baseline methods. However, with the increase of the length of time slot, the amount of improvement gradually decreases. The main reason is that increasing the length of time slot reduces the temporal influence.Figure 10
Performance of the varying length of time slot on the Gowalla dataset.
(a)
Gowalla (precision)
(b)
Gowalla (recall)Figure 11
Performance of the varying length of time slot on the Foursquare dataset.
(a)
Foursquare (precision)
(b)
Foursquare (recall)


## 5.1. Experimental Setup

### 5.1.1. Dataset

Our experiments are conducted based on the two datasets from real-world LBSNs, Foursquare and Gowalla. Foursquare check-in data is within Singapore between August 2010 and July 2011, provided by Yuan et al. [10]. Gowalla check-in data was made in Austin between November 2009 and October 2010 [7]. Each check-in contains user, time, and POI ID information. For both datasets, we removed users who have checked in fewer than 5 POIs and then removed POIs fewer than 5 users checked in. After preprocessing, the Foursquare dataset has 194,108 check-ins made by 2321 users at 5596 POIs, and the Gowalla dataset contains 201,525 check-ins made by 4630 users at 6176 POIs. Relevant statistics are shown in Table 2.Table 2
Dataset statistics (after preprocessing).
Dataset
Number of check-ins
Number of users
Number of POIs
Foursquare
194,108
2321
5596
Gowalla
201,525
4630
6176In order to estimate the performance of our proposed method, we split the Foursquare dataset and the Gowalla dataset into two nonoverlapping sets: a training set and a test set, respectively. Here, the proportion of training data is tested on 70% and 80%, respectively. For example, training data 70% means we randomly select 70% of the observed data for each user as the training data to predict the remaining 30% data. The random selection was carried out 5 times independently, and we report the average results. The hyperparameters are tuned on the training dataset.


### 5.1.2. Evaluation Metrics

A POI recommendation algorithm is to compute a ranking score for each candidate POI (i.e., POI that the user has not visited) and returns the top-N highest ranked locations as recommendations to a target user. To study the effectiveness of the proposed methods, we are interested in the following: (1) how many previously hold-off locations are recommended to the users among the total number of recommended locations and (2) how many previously hold-off locations are recommended to the users among the total number of hold-off locations. More specifically, we examine two metrics: namely, precision@Num and recall@Num (defined by pre@Num and rec@Num, resp.), whereNum is the size of the next POI candidate list, following the work [13, 14]. Given a user u and a time t, the precision and recall for time slot t are calculated as follows:
(18)pre@Numt=∑u∈UTop@Numu,t∩Lu,t∑u∈UTop@Numu,t,rec@Numt=∑u∈UTop@Numu,t∩Lu,t∑u∈ULu,t,where Top@Numu,t is a set of locations recommended to user u that u has not visited in the training set. Lu,t is a set of locations that has been visited by u in the testing set.The overall precision and recall are calculated by averaging the precision and recall values over all time slots, respectively.(19)pre@Num=1T∑t∈Tpre@Numt,rec@Num=1T∑t∈Trec@Numt.As suggested in [2, 10], both the Foursquare and Gowalla datasets have very low density, so recommendation methods show relatively low precision and recall values. In addition, the POIs in the test set of each user may represent only a small portion of POIs that the user may be interested in. Therefore, the low precision and recall obtained in our experiment are common and reasonable. In this work, we focus on the relative improvements we obtained comparing with baseline methods, instead of the absolute values.


### 5.1.3. Recommendation Methods

Recommendation methods used in the experiments are as follows:(i)
User-based CF (UBCF): the basic user-based collaborative filtering.
(ii)
USG: it takes advantage of three modules of user-based CF, social influence, and geographical influence, where0<α<1 and 0<β<1 [2].
(iii)
LRT: by leveraging the temporal influence, it separately learns the user check-in preferences to locations at each time slot from the check-in user-location matrix at the corresponding time slot only based on matrix factorization with the temporal regularization term [11].
(iv)
UTE-SE: it is the time-aware user-based CF incorporating geographical influence [10].
(v)
STELLAR: it proposes a spatial-temporal latent ranking method to explicitly model the interactions among users, POI, and time, which is based on a ranking-based pairwise tensor factorization framework with a fine-grained modeling of user-POI, POI-time, and POI-POI interactions [15].
(vi)
FPMC: it presents a fourth-order tensor factorization-based ranking approach to produce the interesting locations for users [16].
(vii)
TRM: it puts forward a unified probabilistic generative model, which simultaneously detects the semantic, temporal, and spatial patterns of users’ check-in activities, to help users make a decision to visit the places they are interested in [17].
(viii)
TICRec: it is a probabilistic framework to use temporal influence correlations for location recommendations in location-based social networks [18].


## 5.1.1. Dataset

Our experiments are conducted based on the two datasets from real-world LBSNs, Foursquare and Gowalla. Foursquare check-in data is within Singapore between August 2010 and July 2011, provided by Yuan et al. [10]. Gowalla check-in data was made in Austin between November 2009 and October 2010 [7]. Each check-in contains user, time, and POI ID information. For both datasets, we removed users who have checked in fewer than 5 POIs and then removed POIs fewer than 5 users checked in. After preprocessing, the Foursquare dataset has 194,108 check-ins made by 2321 users at 5596 POIs, and the Gowalla dataset contains 201,525 check-ins made by 4630 users at 6176 POIs. Relevant statistics are shown in Table 2.Table 2
Dataset statistics (after preprocessing).
Dataset
Number of check-ins
Number of users
Number of POIs
Foursquare
194,108
2321
5596
Gowalla
201,525
4630
6176In order to estimate the performance of our proposed method, we split the Foursquare dataset and the Gowalla dataset into two nonoverlapping sets: a training set and a test set, respectively. Here, the proportion of training data is tested on 70% and 80%, respectively. For example, training data 70% means we randomly select 70% of the observed data for each user as the training data to predict the remaining 30% data. The random selection was carried out 5 times independently, and we report the average results. The hyperparameters are tuned on the training dataset.


## 5.1.2. Evaluation Metrics

A POI recommendation algorithm is to compute a ranking score for each candidate POI (i.e., POI that the user has not visited) and returns the top-N highest ranked locations as recommendations to a target user. To study the effectiveness of the proposed methods, we are interested in the following: (1) how many previously hold-off locations are recommended to the users among the total number of recommended locations and (2) how many previously hold-off locations are recommended to the users among the total number of hold-off locations. More specifically, we examine two metrics: namely, precision@Num and recall@Num (defined by pre@Num and rec@Num, resp.), whereNum is the size of the next POI candidate list, following the work [13, 14]. Given a user u and a time t, the precision and recall for time slot t are calculated as follows:
(18)pre@Numt=∑u∈UTop@Numu,t∩Lu,t∑u∈UTop@Numu,t,rec@Numt=∑u∈UTop@Numu,t∩Lu,t∑u∈ULu,t,where Top@Numu,t is a set of locations recommended to user u that u has not visited in the training set. Lu,t is a set of locations that has been visited by u in the testing set.The overall precision and recall are calculated by averaging the precision and recall values over all time slots, respectively.(19)pre@Num=1T∑t∈Tpre@Numt,rec@Num=1T∑t∈Trec@Numt.As suggested in [2, 10], both the Foursquare and Gowalla datasets have very low density, so recommendation methods show relatively low precision and recall values. In addition, the POIs in the test set of each user may represent only a small portion of POIs that the user may be interested in. Therefore, the low precision and recall obtained in our experiment are common and reasonable. In this work, we focus on the relative improvements we obtained comparing with baseline methods, instead of the absolute values.


## 5.1.3. Recommendation Methods

Recommendation methods used in the experiments are as follows:(i)
User-based CF (UBCF): the basic user-based collaborative filtering.
(ii)
USG: it takes advantage of three modules of user-based CF, social influence, and geographical influence, where0<α<1 and 0<β<1 [2].
(iii)
LRT: by leveraging the temporal influence, it separately learns the user check-in preferences to locations at each time slot from the check-in user-location matrix at the corresponding time slot only based on matrix factorization with the temporal regularization term [11].
(iv)
UTE-SE: it is the time-aware user-based CF incorporating geographical influence [10].
(v)
STELLAR: it proposes a spatial-temporal latent ranking method to explicitly model the interactions among users, POI, and time, which is based on a ranking-based pairwise tensor factorization framework with a fine-grained modeling of user-POI, POI-time, and POI-POI interactions [15].
(vi)
FPMC: it presents a fourth-order tensor factorization-based ranking approach to produce the interesting locations for users [16].
(vii)
TRM: it puts forward a unified probabilistic generative model, which simultaneously detects the semantic, temporal, and spatial patterns of users’ check-in activities, to help users make a decision to visit the places they are interested in [17].
(viii)
TICRec: it is a probabilistic framework to use temporal influence correlations for location recommendations in location-based social networks [18].


## 5.2. Impact of Parameterβ

In our method, the parameterβ is an important factor to control the balance between geographical influence and temporal influence affecting the location recommendation performance. Figure 2 shows the impact of β of both the Foursquare and the Gowalla datasets on pre@10 and rec@10. From Figure 2(a), we can see that in both Foursquare and Gowalla, the pre@10 of our proposed method shows a fluctuant trend with the increase of β. It is worth noting that the pre@10 for our proposed method quickly decreases on the Foursquare dataset when β reaches 0.6, while the pre@10 for our proposed method on the Gowalla dataset shows a stable tendency when the value of β is greater than 0.6. In terms of rec@10 (Figure 2(b)), we easily obtain a similar conclusion. Therefore, we conclude that our proposed method performs better when the value of β is 0.6. In other words, the obtained results indicate that geographical influence plays a more important role than temporal influence in personalized POI recommendation.Figure 2
Impact of parameterβ.
(a)
pre@10
(b)
rec@10


## 5.3. Impact of Parametern

In our method, the parametern (Definition 3) is a vital factor affecting the location recommendation performance. Figure 3 shows the impact of n of both the Foursquare and the Gowalla datasets on pre@10 and rec@10. From Figure 3, we can see that with the increase of the parameter n, the pre@10 and rec@10 of our proposed method on both datasets are trending upward. It is worth noting that the pre@10 and rec@10 for our proposed method show a stable tendency when the parameter n reaches 14. Therefore, we take the parameter n=14 as an optimal value in the following experiments.Figure 3
Impact of parametern.
(a)
pre@10
(b)
rec@10


## 5.4. Performance Comparison

In this section, we will discuss the results to summarize our findings. Figures4 and 5 illustrate the performance comparison for the Foursquare and Gowalla datasets. From Figure 4(a), it can be clearly seen that our proposed method significantly outperforms other prediction methods. In terms of precision, our method achieves a 0.286–3.61% average improvement compared with the other eight methods. Here, UBCF does not outperform any other seven methods under any measure. The possible reason is that UBCF mainly considers users’ preferences, and ignores other important features, like social influence, geographical influence and temporal influence. Compared to USG and LRT, UTE-SE method always exhibits better results. This is because UTE-SE exploits the time information and the geographical information, while the other two methods only consider the time information. Compared to UTE-SE, STELLAR performs better. This is because STELLAR depicts the temporal effect with a latent feature, which gets rid of the sparse problem. Also, compared with STELLAR, FPMC, TRM, and TICRec, our method improves the average precision by 0.287%, 0.285%, 0.284%, and 0.283%, respectively. The main reason is that these methods ignore an important factor, spatial orientation. In terms of recall (in Figure 4(b)), our method achieves a 3.97–22.87% average improvement compared with the other eight methods. Because of the space limit, the similar analysis is shown in Figure 5. In addition, we observe that all methods perform much better on the Gowalla dataset than on the Foursquare dataset, even though it is sparser. The reason lies in Foursquare data which contains much less POIs.Figure 4
Performance comparison on the Gowalla dataset.
(a)
Gowalla (pre@Num)
(b)
Gowalla (rec@Num)Figure 5
Performance comparison on the Foursquare dataset.
(a)
Foursquare (pre@Num)
(b)
Foursquare (rec@Num)


## 5.5. Effect of Percentages of Training Data

Figures6 and 7 describe the recommendation accuracy of UBCF, USG, LTR, UTE-SE, STELLAR, and our method with respect to varying the percentages of training data. As shown, with the rise of the percentage of the training data, the precision and recall of all methods steadily increase. The possible reason is that the training data set becomes denser as the percentage of the training data rises, which is helpful for recommendation methods to learn users’ preferences on POIs.Figure 6
Effect of percentages of training data on the Gowalla dataset.
(a)
Gowalla (precision)
(b)
Gowalla (recall)Figure 7
Effect of percentages of training data on the Foursquare dataset.
(a)
Foursquare (precision)
(b)
Foursquare (recall)


## 5.6. Effect of Numbers of Check-In POIs of Users

Figures8 and 9 depict the recommendation accuracy regarding the change of the number of check-in (or visited) locations of users in the training set. For example, a measure at “Check in-n=5” is averaged on all users who have checked in five locations in the training set. With the increase of the number of visited locations of users, our method can more accurately estimate the time probability density and predict the visiting probability of new locations for these users at the corresponding hour through using more check-in data. As a whole, the precision and recall incline accordingly.Figure 8
Effect of numbers of check-in locations of users on the Gowalla Dataset.
(a)
Gowalla (precision)
(b)
Gowalla (recall)Figure 9
Effect of numbers of check-in locations of users on Foursquare Dataset.
(a)
Foursquare (precision)
(b)
Foursquare (recall)


## 5.7. Effect of the Length of Time Slot

Figures10 and 11 depict the recommendation accuracy when varying the length of time slots. The length of time slot controls the time granularity of time-aware POI recommendations. Intuitively, a smaller length of time slot indicates that the recommendation results will be more time-specific. Here, we only compare the methods considering temporal influence to focus on the effect of the length of time slot. As shown, we observe that, with the increasing of the time slot length, the precision of all methods gradually increases, but the recall inclines. The possible reason is that on the one hand, increasing the length of the time slot makes the data denser, benefitting for recommendation methods to estimate the accurate visiting probability of users to locations and, on the other hand, the larger length of time slots brings in a larger number of ground truth locations. Due to the number of recommendations (i.e., Num) unchanged, recall values are decreasing with increasing the length of time slot. More importantly, for all lengths of time slots, our method consistently outperforms the state-of-the-art baseline methods. However, with the increase of the length of time slot, the amount of improvement gradually decreases. The main reason is that increasing the length of time slot reduces the temporal influence.Figure 10
Performance of the varying length of time slot on the Gowalla dataset.
(a)
Gowalla (precision)
(b)
Gowalla (recall)Figure 11
Performance of the varying length of time slot on the Foursquare dataset.
(a)
Foursquare (precision)
(b)
Foursquare (recall)


## 6. Related Work

In recent years, there have already been a reasonable amount of researches in location-based social networks due to the new characteristics of spatial-temporal-social information embedded in the check-in data and the prevalence of various interesting real-world applications [19–26]. We summarize the existing location recommendations into four categories: collaborative filtering, social influence, geographical influence, and temporal influence.


### 6.1. Collaborative Filtering

Some studies supply POI recommendations by using the conventional collaborative filtering techniques based on users’ check-in data [27–29], travel tour data [30, 31], GPS trajectory data [32–35], or text data [36]. Cheng et al. [37] provided a large-scale quantitative analysis and modeling of over 22 million check-ins of location-sharing service users. Zheng et al. [34] studied location-and-activity recommendation using GPS data, where activities could be various human behaviors: shopping, watching movies, and so on. Also, some researches derived users’ similarity by employing their residence as an input of the conventional collaborative filtering method [38–41]. However, these studies have not leveraged the social influence, geographical influence, or temporal influence.


### 6.2. Social Influence

Intuitively, friends of LBSNs tend to have more common interests. Inspired by that, social influence has been widely used to enhance POI recommendation in LBSNs [8, 42–45]. By inferring the social relations, the similarity between users can be derived and integrated into the collaborative filtering methods.


### 6.3. Geographical Influence

In [46], the authors mentioned that geographical influence can be used to improve the POI recommendation by clustering the check-in behavior of users. In order to detect how to use geographical influence for enhancing the performance of POI recommendations, some researchers leveraged the geographical influence of users to compute their similarity weights [2, 8, 47, 48]. In [8], Gao et al. obtained the social correlations of check-in behavior in LBSNs by using a geosocial correlation model. In [2], the authors analyzed the spatial clustering phenomenon shown in the user check-in behavior of LBSNs in order to study the geographical influence. They first found that the geographical influence plays a vital role in user check-in behaviors, then used power law distribution to model it. Finally, they designed a collaborative filtering method by fusing geographical influence with naive Bayesian. Meanwhile, some works studied the geographical influence of POIs. Cheng et al. presented a fused matrix factorization method that combines users’ social information with the geographical influence of users’ check-ins [3]. In [44], Bao et al. presented a new approach that considers users’ preference and specified geopositions and can recommend a list of POIs (such as exhibition halls and places of interest) for a given user. Cheng et al. [49] focused on the problem of successive personalized POI recommendation. In order to solve this problem, they developed a novel matrix factorization method considering both personalized Markov chain and localized regions. A geotopic model is proposed in the literature [41], which assumes that a user is more likely to go to a place that is closer to the locations visited by her. Also, other works modeled the distance between two locations visited by the same user as a common distribution for all users, for example, a power-law distribution or a multicenter Gaussian model [46, 50, 51].


### 6.4. Temporal Influence

A number of time-aware recommendation techniques have been proposed to enhance the recommendation performance. In [52], authors designed a model tracking the time changing behavior throughout the life span of the data, which can make better distinctions between transient effects and long-term patterns. Gao et al. [53] presented a general framework to exploit and model temporal cyclic patterns and their relationships with spatial and social data. In [54], the authors examined the temporal dynamics of urban activity, which indicates that when studying urban dynamics, we need to consider both space and time dimensions. In [11], Gao et al. put forward a novel location recommendation framework based on the temporal properties of user movement observed from a real-world LBSN dataset. In [14], the authors presented the Geographical-Temporal influences Aware Graph (GTAG) to model the check-in behaviors of users and a graph-based preference propagation algorithm for POI recommendation on the GTAG. The proposed methods exploited both the geographical and the temporal influences in an integrated manner. Yuan et al. [10] showed a unified framework exploiting both the temporal influence and the spatial influence, which are specific for the time-aware POI recommendation.In addition, a few research works fused geographical and temporal influences for better recommendation accuracy in LBSNs [14, 55, 56]. In [55], they leveraged matrix factorization to generate POI recommendation and proposed a novel attempt to integrate both geographical and temporal influences into matrix factorization. Liu et al. [56] extended recurrent neural networks (RNN) and proposed a novel method called spatial-temporal recurrent neural networks (ST-RNN), which can capture time interval and geographical distance information. However, they ignored a vital factor, that is, spatial orientation.


## 6.1. Collaborative Filtering

Some studies supply POI recommendations by using the conventional collaborative filtering techniques based on users’ check-in data [27–29], travel tour data [30, 31], GPS trajectory data [32–35], or text data [36]. Cheng et al. [37] provided a large-scale quantitative analysis and modeling of over 22 million check-ins of location-sharing service users. Zheng et al. [34] studied location-and-activity recommendation using GPS data, where activities could be various human behaviors: shopping, watching movies, and so on. Also, some researches derived users’ similarity by employing their residence as an input of the conventional collaborative filtering method [38–41]. However, these studies have not leveraged the social influence, geographical influence, or temporal influence.


## 6.2. Social Influence

Intuitively, friends of LBSNs tend to have more common interests. Inspired by that, social influence has been widely used to enhance POI recommendation in LBSNs [8, 42–45]. By inferring the social relations, the similarity between users can be derived and integrated into the collaborative filtering methods.


## 6.3. Geographical Influence

In [46], the authors mentioned that geographical influence can be used to improve the POI recommendation by clustering the check-in behavior of users. In order to detect how to use geographical influence for enhancing the performance of POI recommendations, some researchers leveraged the geographical influence of users to compute their similarity weights [2, 8, 47, 48]. In [8], Gao et al. obtained the social correlations of check-in behavior in LBSNs by using a geosocial correlation model. In [2], the authors analyzed the spatial clustering phenomenon shown in the user check-in behavior of LBSNs in order to study the geographical influence. They first found that the geographical influence plays a vital role in user check-in behaviors, then used power law distribution to model it. Finally, they designed a collaborative filtering method by fusing geographical influence with naive Bayesian. Meanwhile, some works studied the geographical influence of POIs. Cheng et al. presented a fused matrix factorization method that combines users’ social information with the geographical influence of users’ check-ins [3]. In [44], Bao et al. presented a new approach that considers users’ preference and specified geopositions and can recommend a list of POIs (such as exhibition halls and places of interest) for a given user. Cheng et al. [49] focused on the problem of successive personalized POI recommendation. In order to solve this problem, they developed a novel matrix factorization method considering both personalized Markov chain and localized regions. A geotopic model is proposed in the literature [41], which assumes that a user is more likely to go to a place that is closer to the locations visited by her. Also, other works modeled the distance between two locations visited by the same user as a common distribution for all users, for example, a power-law distribution or a multicenter Gaussian model [46, 50, 51].


## 6.4. Temporal Influence

A number of time-aware recommendation techniques have been proposed to enhance the recommendation performance. In [52], authors designed a model tracking the time changing behavior throughout the life span of the data, which can make better distinctions between transient effects and long-term patterns. Gao et al. [53] presented a general framework to exploit and model temporal cyclic patterns and their relationships with spatial and social data. In [54], the authors examined the temporal dynamics of urban activity, which indicates that when studying urban dynamics, we need to consider both space and time dimensions. In [11], Gao et al. put forward a novel location recommendation framework based on the temporal properties of user movement observed from a real-world LBSN dataset. In [14], the authors presented the Geographical-Temporal influences Aware Graph (GTAG) to model the check-in behaviors of users and a graph-based preference propagation algorithm for POI recommendation on the GTAG. The proposed methods exploited both the geographical and the temporal influences in an integrated manner. Yuan et al. [10] showed a unified framework exploiting both the temporal influence and the spatial influence, which are specific for the time-aware POI recommendation.In addition, a few research works fused geographical and temporal influences for better recommendation accuracy in LBSNs [14, 55, 56]. In [55], they leveraged matrix factorization to generate POI recommendation and proposed a novel attempt to integrate both geographical and temporal influences into matrix factorization. Liu et al. [56] extended recurrent neural networks (RNN) and proposed a novel method called spatial-temporal recurrent neural networks (ST-RNN), which can capture time interval and geographical distance information. However, they ignored a vital factor, that is, spatial orientation.


## 7. Conclusion

A large amount of historical movement data of users in LBSNs inspires the POI recommendation service. In this work, we utilize temporal influence and spatial influence to construct a unified framework, which generates location recommendations in location-based social networks (LBSNs). We first show a new method that utilizes the spatial influence for POI recommendations. Then, we propose a new approach exploring the temporal influence. Lastly, we combine these two approaches through a unified framework. We perform extensive experiments over two real-world LBSN datasets, the Foursquare dataset and the Gowalla dataset. The experimental results show that our proposed method outperforms all the baseline methods.In the future, we will study two directions of location recommendations to extend our method. First, we will continue to study how to take advantage of both spatial influence and temporal influence and explore the novel usage of such information. Second, we will detect how to incorporate the category information of locations into the unified location recommendation framework.



---

*Source: 6928605-2018-08-29.xml*