Predicting Your Next Stop-over from Location-based Social Network Data with Recurrent Neural Networks

Abstract

In the past years, Location-based Social Network (LBSN) data have strongly fostered a data-driven approach to the recommendation of Points of Interest (POIs) in the tourism domain. However, an important aspect that is o‰en not taken into account by current approaches is the temporal correlations among POI categories in tourist paths. In this work, we collect data from Foursquare, we extract timed paths of POI categories from sequences of temporally neighboring check-ins and we use a Recurrent Neural Network (RNN) to learn to generate new paths by training it to predict observed paths. As a further step, we cluster the data considering users' demographics and learn separate models for each category of users. Œe evaluation shows the e‚ectiveness of the proposed approach in predicting paths in terms of model perplexity on the test set.

INTRODUCTION

Location-based Social Networks (LBSN) allow users to check-in in a Point-of-Interest (POI)1 and share their activities with friends, providing publicly available data about their behavior. One of the distinctive features of LBSN data with respect to traditional location prediction systems, which are mainly based on GPS data and focus on physical mobility [ 33 ], is the rich categorization of POIs in consistent taxonomies, which aŠribute an explicit semantic meaning to users’ activities. Œe availability of venue categories has opened new research lines, such as statistical studies of venues peculiarities [ 17 ], automatic creation of representations of city neighborhoods and users [ 22, 25 ], de€nition of semantic similarities between cities [ 24 ]. Most importantly, venue categories play an important role in POI recommender systems, as they enable to model user interests and personalize the recommendations [ 18 ]. In the past years, liŠle aŠention has been dedicated to the temporal correlations among venue categories in the exploration of a 1Œe term venue is used interchangeably with POI in this work to describe an entity that has a somewhat €xed and physical extension as de€ned by hŠp://schema.org/Place city, which is nonetheless a crucial factor in recommending POIs. Consider the example of a check-in in an Irish Pub at 8 PM: is the user more likely to continue her evening in a Karaoke Bar or in an Opera House? BeŠer a Chinese Restaurant or an Italian Restaurant for dinner a‰er a City Park in the morning and a History Museum in the a‰ernoon? Note that predicting these sequences require an implicit modeling of at least two dimensions: 1) temporal, as certain types of venues are more temporally related than others (e.g. a‰er an Irish Pub, people are more likely to go to Karaoke than to a History Museum 2) personal, as venue categories implicitly de€ne a user pro€le, independently from their order (e.g. Steakhouse and Vegetarian Restaurant do not go frequently together). Most of existing studies aŠempt to model directly sequences of POIs rather than their categories to recommend the next POI to a user (see ‘next POI prediction’ in Sec. 2). In this work, we focus on modeling sequences of POI categories to enhance the generality and the portability of the obtained results. Œis can be considered as a €rst step in the next POI prediction problem, as the POI category can then be turned into a speci€c POI by querying a database of POIs according to a variety of parameters, such as the user context (e.g. position, weather) and/or speci€c POI features such as popularity, average prices and the like.

In order to address this problem, we €rst collect users’ check-ins from Foursquare and extract their corresponding venue categories, segmenting them into a set of temporally neighboring activities, which we call paths. Œen, we train a Recurrent Neural Network to learn to predict these paths in order to generate new ones, thanks to its architecture that is speci€cally meant to model temporal sequences without specifying a speci€c memory length. In the aŠempt to take into consideration the fact that the nature of the generated sequences is not universal, but it critically depends on the typology of user, we cluster users in groups and learn separate models for each of them. Di‚erently from previous work [ 32 ], we cluster users based on their demographics rather than on their past activities, consistently with the intent of obtaining results that are portable to new data without a cold start problem. Œe main scienti€c contributions of this paper are: (1) addressing the problem of next POI category using a machine learning approach on sequences of temporally consecutive check-ins; (2) use of a Recurrent Neural Network (RNN) with Gated Recurrent

Units (GRU) with multiple layers as a model; (3) an initialization of the vectors fed to the neural networks using an unsupervised feature learning algorithm (node2vec) on the hierarchical graph modelling the Foursquare taxonomy; (4) a user clustering based on demographics that is not a‚ected by the cold start problem; (5) an evaluation protocol based on perplexity, which is new in this domain and is able to address the limitations of using accuracy on a set of interdependent target categories. 2 2.1

RELATED WORK

Venue categories Œe availability of venue categories from LBSN data has inspired a number of studies in the past years. In [ 17 ], the authors assess the correlations among venue categories and popularity with a statistical study on a large sample of check-ins collected from di‚erent geographical regions. In [ 26 ], the authors leverage venue categories to automatically create a high level map of the neighborhoods of a city using density-based clustering techniques. In [ 22 ], the authors use venue categories to create semantic representation of city neighborhoods and users. In [ 24 ], the authors create a semantic representation of a city as a bag of venue categories and use it to de€ne a similarity measure between cities. 2.2

Next POI recommendation

All of these studies, however, do not take into account the temporal dependence among venue categories, i.e. they do not aŠempt to predict where a user will move next considering the history of her movements in terms of venue categories. Œis task is similar to the next POI prediction, which has received some aŠention in the past years. For instance, in [ 4 ] the authors propose a matrix factorization method including personalization and geographic constraints that aŠempts to predict the next check-in of the user based on her past activities and geographical factors. In [ 8 ], the authors use a metric embedding approach to develop a personalized model of the sequential transition of POIs. Œese two studies directly develop a model to recommend the next POI, while, similarly to our approach, in [ 32 ] the authors focus on modeling sequences of venue categories. Œey propose a framework that uses a mixed hidden Markov model to predict the most likely next venue category and recommend POIs belonging to the most likely next category in the neighborhood of the user. Although this work has some common features with the one proposed in this paper, such as the modeling of venue categories transitions rather than directly the POIs transitions, there are important di‚erences. First, they utilize Gowalla’s2 data and venue categorization, which included only nine broad categories, such as Food or Shopping, which can reasonably considered independent among each other. Our work, on the other hand, is based on Foursquare taxonomy3, which includes 920 categories organized in a hierarchical fashion, and thus requiring a more complex modeling e‚ort. Secondly, while they cluster users based on their past activities, we follow a di‚erent approach, considering user demographics, e‚ectively tackling the new user problem. Œird, they use a Hidden Markov Model while we use an approach based on Recurrent Neural Networks. Finally,

2hŠps://en.wikipedia.org/wiki/Gowalla

3hŠps://developer.foursquare.com/categorytree they evaluate the proposed approach using accuracy, while we use perplexity. 2.3

Recurrent Neural Networks

Recurrent Neural Networks (RNNs) have received a great deal of attention in machine learning research lately [ 16 ], as, thanks to their improved architectures [ 5, 12 ] and the advancements in computational power, they are able to e‚ectively model sequences. For this reason, they have been used successfully for tasks such as speech recognition [ 10 ], sentiment analysis [ 30 ], image captioning [ 13 ] and neural language models [ 20 ]. One of the typical applications of RNN in the €eld of language modeling is that of generating text by recursively predicting the next word in a sentence [ 29 ]. Œis task is very similar to the use of RNNs in this work, in which the analogy is that of interpreting a sequence of venue categories coming from users’ check-ins as a sentence in a text. 2.4

Itinerary recommendation

Œe problem of modeling and recommending paths to users share important features with that of itinerary recommendation, which aims at recommending sequences of POIs, considering constraints such as time, budget and personal preferences. Typically, to each POI a score is assigned based on popularity and/or personal preferences, travel times between POIs are inferred from data, and the problem of itinerary recommendation is tackled as an optimization problem where the objective is to maximize the total possible score of the itinerary while complying with the constraints [ 7, 15, 31 ]. Note that the greatest di‚erence with our approach is that we do not explicitly formulate the optimization problem with constraints, but rather assume that good paths will be learned from LBSN data. 3 3.1

APPROACH

Problem statement

In this work, we address the problem of next POI category prediction, i.e. we aim to learn to predict the category of the next POI that a user will visit, in order to be able to generate and recommend new paths.

Definition 1. Given the space of POI categories C, the space of check-in ids I , the space of timestamps T , the space of users U , a check-in is a set v = fi; c; τ ; u g where i 2 I is the check-in id, c 2 C is the category of the POI, τ 2 T is the timestamp at which the check-in has been performed and u 2 U is the user who has performed the check-in.

Definition 2. A path is an ordered sequence of POI categories ¹c1; c2; :::; ct º, extracted from a sequence of temporally ordered checkins performed by a particular user u 2 U , i.e. ¹fii ; ci ; τi ; u gº for i = 1::N and where τ ¹i + 1º > τ ¹iº 8i.

Definition 3. We de€ne a category index α 2 N with α = 1::jC j and that uniquely identi€es a category cα 2 C.

In order to learn to generate the next category ct +1 of a path, we collect M paths from LBSN and learn a model of the conditional probability P ¹ct +1 jct ; ct 1; ct 2; :::; c1º from these sequences of POI categories. Œen, from this model, the next category ct +1 can be determined as: 3.2

Model

ct +1 = arg max P ¹c jct ; ct 1; ct 2; :::; c1º c 2C (1) We propose an approach based on Recurrent Neural Networks, which are speci€cally meant to deal with sequential data. Œe main di‚erence of RNNs with respect to standard feed-forward neural networks is the presence of a hidden state variable ht , whose value depends both on the input data presented at time xt and, by means of loop connections, on the previous hidden state ht 1[ 9 ]. A typical application of RNNs in neural language modeling is that of generating text recursively applying a “next word prediction” [ 29 ], and in the same spirit we address the problem of next POI category prediction. Œe main idea is that of using a supervised learning approach where the targets correspond to the inputs shi‰ed in time, i.e. X = f¹c j 0; c j 1; :::; c Njj 1ºg and Y = f¹c j 1; c j 2; :::; c Njj ºg where j = 1:::M is the path index and Nj is the length of the j th path. Œe architecture of the neural network is illustrated in Fig. 1. To simplify the notation, we now drop the path index j and consider one path to illustrate the functioning of the network. A venue category ct is fed into the network via an encoding into an input vector xt , which is then passed to a Gated Recurrent Unit. Gated Recurrent Units (GRU) are gating mechanisms that improve the ability of the RNNs to store long sequences and that recently have been proven to be as e‚ective as more complicated architectures such as Long Short-Term Memory (LSTM) units [ 5 ]. Œe update of the GRU unit hidden state, i.e. the computation of the new state ht given the previous state ht 1 and the current input xt , is described by the following equations:

rt = sigmoid¹Wr ht 1 + Wr xt + br º ht0 = tanh¹Wi ¹rt

ht 1º + Wi xt + bi º zt = sigmoid¹Wzht 1 + Wz xt + bz º ht = zt h0 + ¹1 zt º ht 1 (2) (3) (4) (5) where sigmoid and tanh indicate respectively the sigmoid and hyperbolic tangent activation functions and represent the element-wise product of the matrices. r is called the ‘reset gate’ and it allows to forget or remember the previous state ht 1 when generating the candidate state ht0 . z is called the ‘update gate’ and intuitively it controls how much the unit needs to update its state. Wi , Wr , Wz are weight matrices that are learned during the training. Œe GRU computes the hidden state ht which is stored for the next iteration and used to compute the output of the current iteration ot . Before computing the output ot , during training time, a Dropout layer is applied. Œe Dropout layer is a regularization mechanism which, at training time, randomly switches o‚ a fraction p of neurons, called the dropout rate, preventing them from co-adapting and over€Šing the sampled data [ 28 ]. Dropout can be modelled with a mask vector mt , whose values can be either 1 or 0 with probability p. A‰er the dropout layer, the output state ot = tanh¹Woht mt º is computed using a fully connected layer whose weights are de€ned by the matrix Wo , which is learned at training time. Wo is shaped so that the dimension of the output vector is equal to the number of possible categories, i.e. jot j = jC j. Œus, we can index the components of the output vector using the category index otα . Œen, the So‰max layer normalizes the outputs, turning them into a probability distribution over a set of possible outcomes [ 2 ]: oα e t so f tmax ¹otα º = ÍjC j eot

k k=1 In this way, the So‰max layer models the probability distribution of the next category:

so f tmax ¹otα º = P ¹ct +1 = cα jct ; ct 1; ct 2; :::; c1º as oit depends on the current category encoding xt of ct , but also on all the previous encodings of the sequence by means of the hidden state ht . During the training process, we train the network to produce a probability distribution of categories that is as close as possible to that observed in the data, i.e. maximizing the probability of the observed data. Œerefore, we de€ne the loss Lt as the cross entropy: Lt = logP ¹ct +1 = ctα+1 jct ; ct 1; ct 2; :::; c1º = log¹so f tmax ¹otα ºº (8) where ctα+1 is the category observed in the data as t + 1 element of the path. Œe loss is optimized using Adam [ 14 ], an enhanced version of the stochastic gradient descent that introduces momentum and adaptive learning rates. Œe gradients of the loss function are computed using back propagation on the unrolled neural network [ 27 ]. Œe model has a number of hyper-parameters, such as the number of neurons in the hidden state nhidden , the number of hidden layers nl ayer s , the learning rate lr and the number of epochs η. We optimize these hyper parameters using a grid search on a validation set (see Sec. 5). (6) (7) 3.3

Feature learning from category hierarchy

In this work, the space of possible categories C is de€ned by the Foursquare Taxonomy, which de€nes and classi€es categories in a hierarchical ontology. As can be seen in Fig. 1, it is necessary to specify an encoding to turn the categories into input vectors to be fed into the neural network. A simple and widespread approach to encode categorical variables is that of using the so called one-hot encoding, i.e. to use a binary vector whose dimension is equal to the size of the vocabulary d = jC j where only one component is di‚erent from 0 using the category index α : xone hot ¹cα º = k 1 () k = α 0 () k , α Œe one-hot encoding is a sparse representation and, although straight forward and intuitive, has a number of shortcoming. First, the size of the input vector depends on the size of the category vocabulary C. Œis can be de€ned as the total number of distinct categories that appear in the data, hindering the applicability of the model to unobserved categories, or as the total number of possible categories, which can result in a waste of computational resources when certain categories are not observed in the data. Secondly, the one-hot encoding considers each category as independent from each other and equidistant from the others. Consider as an example the case of three categories: Restaurant = (1,0,0), Italian Restaurant = (0,1,0), Movie Šeater = (0,0,1). Œis representation does not allow to determine whether Restaurant is more similar to Italian Restaurant or Movie Šeater and thus fails to e‚ectively represent the hierarchical relations among categories. For this reason, we

Art_Museum use node2vec [ 11 ], an unsupervised feature learning approach that maps nodes in a graph to a dense vector representation in a Euclidean space of €xed dimension preserving the structure of the graph. Node2vec can be seen as an adaptation of the word2vec model [ 21 ] to graphs, as it simulates a random walk on the graph, turning it into an order sequence of nodes, which constitutes the “words” of a document that is then processed using word2vec. In node2vec, we use a uniform exploration, i.e. p = q = 1, a dimension of the obtained vector d = 100 and 100 walks per category node. In Sec. 5, we compare the results obtained with xone hot and xnode2vec , showing that the laŠer leads to beŠer result and faster computation. A dynamic visualization of the node2vec category embedding can be found online4. To obtain a good visualization, we suggest to use TSNE [ 19 ] with at least perplexity 20 and 1000 iterations.

3.4 Personalized model

In order to take into account the fact that the next POI category prediction problem can strongly be inƒuenced by personal aŠributes of a user, we segment the set of users U in a collection of clusters according to the user demographics. Considering the set of languages l 2 L and of genders g 2 G, we generate all possible clusters Ulg , Ul , Ug and we segment the whole set of paths P accordingly generating Plg , Pl , Pg . We split each of them into training set and test set containing respectively 80-20% of the data, we train the model on the training sets and assess performance on the test sets.

4 EXPERIMENTAL SETUP

4.1 Data Collection

In order to collect check-ins and sucient user information to perform a demographic clustering, we use as data sources both the TwiŠer and the Foursquare API. We collect via the TwiŠer 4hŠp://projector.tensorƒow.org/?con€g=hŠps://gist.githubusercontent. com/enricopal/9a2683de61f5…16c4f59ae295e3fef7/raw/ 159df72f47e881d0f314096fcc8ea561…7132b9/projector con€g.json Search API check-ins done through the Swarmapp5 application and publicly posted on TwiŠer, obtaining 1.5M check-ins from 235.6K users in the temporal interval going from 05-04-2017 to 11-04-2017. From this data, we are able to extract for each checkin the language spoken by the user and the id of the check-in. With the check-in id, to gather additional information about the venue and the user, we query the Foursquare API6, obtaining the venue category c and the user gender. Œus, for each user, we have: ¹user id; language; gender ; ¹c1; τ1º; :::; ¹cN ; τN ºº, where τ is the timestamp of the check-in.

4.2 Preprocessing and Path Extraction

Among all users, only a small part of them uses the application frequently enough to be likely to generate a path. Œus, as a pre€lter to speed up the next processing steps, we €lter out users with less than 10 check-ins. We also observe that there are users with a very large number of check-ins, who are likely to be bots. In order to remove them, we develop a heuristic according to which if a user has done more than twice two check-ins in one minute is a bot. By manually checking the results on a sample of 50 users, we observe no false positives. Œen, in order to extract the paths, i.e. temporal sequences of correlated venue categories, we apply the principle according to which two check-ins are part of the same path if and only if they both occur within a time window, similarly to what has been done in [ 7 ]. Œus, given a set of timestamped check-ins performed by a given user ¹c1; τ1º; :::; ¹cN ; τN º, we split this sequence in multiple paths whenever τi+1 τi > 8h, i.e. the time di‚erence between two consecutive check-ins is higher than 8 hours. Isolated check-ins, i.e. with τi+1 τi > 8h and τi 1 τi > 8h, are removed from the data. We obtain 29.5K paths, with an average length of 4.2 and a maximum length of 50. In Tab. 1, we report the number of users and check-ins a‰er each preprocessing step.

5hŠps://www.swarmapp.com 6hŠps://developer.foursquare.com/docs/checkins/resolve

Collection More than 10 check-ins Bot removal Path extraction

Users

235.6K 19.5K 12.4K 12K As we have mentioned in Sec. 1, the way in which tourists explore a city is di‚erent and personalized. Although a personalized path recommendation would be desirable, the amount of training data is not sucient to achieve such a goal. Œerefore, we cluster users in groups and tailor the path recommendation to a given user group. In order to obtain results that are general and do not depend on the speci€c dataset that we have collected, we propose a clustering approach based on the user demographics information that we have collected, i.e. the language and the gender of the user, segmenting the collected paths according to these clusters. We observe 30 distinct languages in the data and count the number of paths per each language-gender pair. We also consider higher level clusters such as: (all, gender) and (language, all), which can be used when only one of the two features about the user is available. We require to have at least 100 users to create a cluster, obtaining 22 distinct clusters. 4.4

Evaluation

In the experimental part of this work, we try to answer to the following research questions: 1) What is the most e‚ective architecture of the RNN model, i.e. what are the best hyper-parameters of the model? 2) Is the dense encoding provided by node2vec more e‚ective than the sparse one-hot encoding? 3) Are Recurrent Neural Networks beŠer at generating paths with respect to a model with a €xed memory window, such as a bigram model? 4) Is the clustering of users favoring or hindering the e‚ectiveness of the model? In order to answer to these questions, we need to de€ne an appropriate metric to measure the performance of the model. Although accuracy has a straight forward interpretation as it is simply measured as the fraction of correctly predicted venue categories, it would consider all categories independently and weight all errors in the same way. For example, predicting Sardinian Restaurant or Šai Restaurant when the true category is Roman Restaurant would count as an error in the same way. Œus, we opt for a di‚erent metric, commonly used in neural language modeling evaluation, that is perplexity [ 1, 20 ]. Perplexity is de€ned as the exponential of the average negative log-likelihood of the model, which in our case becomes: ppl = 2 ¹ÍkM=11 Nk º ÍMj=1 ÍtN=j1 logP ¹ctj+1=ctα+1 jctj ::c1j º (9) where M is the total number of paths, Nk is the length of the k-th path and ctα+1 is the category observed in the data as t + 1 element of the path. Intuitively, perplexity measures the “surprise” of the model in observing the test data. Note that if we roll an ideal die with a number of faces equal to the number of categories C, i.e. p = 1 , the perplexity is then exactly ppl = jC j. Œus, the perplexity jC j can be interpreted as the number of possible outcomes among which a random system should guess. Œe lower the perplexity, the beŠer is the model. Also note that ppl is equal to the exponential in base 2 of the cross entropy between the model and the data distribution, i.e. the average of the loss Lt over all timesteps of all paths and is thus naturally optimized by the model training. Having de€ned a metric to evaluate the model, we create a training set and a test set, containing respectively 80-20% of the paths. Œe validation set used for the optimization of the hyper-parameters is in turn extracted as a 20% of the training set. In order to optimize the hyper parameters (experiment 1), we perform a grid search, i.e. we explore all the possible combinations of the following values: number of neurons in the hidden layer: nhidden = »64; 128¼ learning rate: lr = »10 4; 5 10 4; 10 3¼ number of epochs: epochs = »1; 2; 5; 10¼ number of hidden layers: nl ayer s = »2; 3¼ For each con€guration ¹nhidden ; lr ; epochs; nl ayer s º, we train the model and measure its perplexity on validation data, exploring a total of 48 possible con€gurations. In Tab. 2, we report the best 5 con€gurations. We can observe that a small learning rate is helping the model learn and that depth, i.e. number of hidden layers, is more e‚ective than width, i.e. number of neurons in the hidden layers. We also observe that training the model for more epochs increases the performance.

In the rest of the section, unless otherwise speci€ed, we use the best con€guration of the model.

Gender

M F All All All All All All All All F F F F F F M M M M M M All frequencies on training data and using add-one smoothing to account for bigrams that do not appear in the training data [ 3 ]: P ¹ct +1 jct º = max ¹1; νct+1;ct º jC j + νct (10) where νct+1;ct denotes the frequency of the bigram ¹ct +1; ct º, i.e. of co-occurrence of the categories ct +1 and ct whereas νct denotes the frequency of the category ct . Œe results are reported in Tab. 3. We can observe that the RNN with node2vec initialization performs beŠer with respect to the other systems and that RNN with one-hot encoding is still far beŠer than the bigram model. Œis shows, on the one hand, the e‚ectiveness of node2vec as an initialization strategy and that of RNNs in predicting paths. We also observe that the di‚erence between the node2vec and one-hot initialization is small, highlighting the ability of RNNs of learning well also starting from a sparse representation. However, we observe a ratio in computing time of 1.35, as the model runs in 39 minutes with node2vec embeddings and in 53 minutes with one-hot encoding on a server with 48 CPU cores and 256GB of RAM, thanks to the ‘compressed’ representation of the inputs. In general, we can say that the proposed approach achieves a perplexity of 75:271 on the test set, shrinking of about 10 times the space of possible categories among which a random system would have to guess. 5.3

Personalized model

In this section, we compare the performance of the global model to that of the model trained on the paths belonging to a speci€c user cluster (experiment 4). Œe perplexity score, the number of paths, the average path length and the max length are reported for each user cluster in Tab. 4. Note that not all users choose to show their gender or language, as can be veri€ed for example by noting that U sers¹Mº + U sers¹F º < U sers¹All º. From the results, we can observe that the model perplexity is increasing for certain user clusters and decreasing for others, hinting to the fact that some user clusters might be less predictable than others. For instance, we observe that Turkish speaking users have a much lower perplexity than Dutch speaking users and we might be tempted to conclude that the behavior of the former category is much easier to predict than that of the laŠer. However, an important role is played by the dimension of the training set, which varies signi€cantly across the clusters and that is a key ingredient in the learning process. In order to look into the correlation between the model perplexity and the number of paths corresponding to the user cluster, we create a scaŠer plot (see Fig. 2) and measure the Spearmann correlation coecient among the two variables [ 6 ], obtaining a negative correlation ρ = 0:48 with a two-sided p-value p = 0:02. Both the plot and the correlation coecient thus appear to show that the amount 110 100 y t i x le90 p r e P 80 70 0 global All M F of training data is negatively correlated with the perplexity of the model, supporting the intuition that the size of the training set is actually enhancing the model.

Another factor that might inƒuence the performance in terms of next category prediction across the di‚erent user clusters is the fact that the average path length varies. Similarly to the previous analysis, we plot average path length and model perplexity (see Fig. 3) and measure the Spearmann correlation between the variables, obtaining a position correlation ρ = 0:49 with a two-sided p-value p = 0:02. 6

CONCLUSIONS

In this paper, we propose a novel approach to recommend sequences of POI categories, as a €rst step to create a system that is able to automatically learn from data a personalized tourist path. Œe approach is based on a Recurrent Neural Network model, which shows to be able to model and predict e‚ectively sequences of POI categories. We experiment di‚erent hyper parameters of the architecture of the network, showing the importance of a small learning rate and of stacking up multiple layers rather than increasing the number of neurons in the hidden layers. We also show that initializing the categories using an encoding based on node2vec improves the performance of the model with respect to the standard one-hot encoding, both in terms of model perplexity and of computing time. Œe analysis of the results of the model using di‚erent user clusters has a less de€nite interpretation, as we observe that in certain cases the performance increases and in other cases the performance decreases. We suggest that possible biasing factors are the size of the training set and the average path length, which is con€rmed by a correlation analysis with the perplexity of the model. Further studies will extend the analyses to a larger dataset with a larger sample of user to rule out €nite size e‚ects on the performance of the clustered models and to include a larger temporal interval to exclude from the analysis possible seasonal e‚ects.

Future work will also involve the integration of the next POI prediction into a real recommender of sequences of POIs for tourists. Given the next most likely POI category, a short list of sorted POIs belonging to that category will be retrieved from a knowledge base containing places and events. Œe short list will be computed using entity2rec [ 23 ] leveraging user context (e.g. geographical position), inherent venue peculiarities (e.g. ratings, reviews) and user preferences.

ACKNOWLEDGMENTS

Œis work was partially supported by the innovation activity PasTime (17164) of EIT Digital.

References

[1] Yoshua Bengio , Re´jean Ducharme, Pascal Vincent, and Christian Jauvin . 2003 . A neural probabilistic language model . Journal of machine learning research 3 , Feb ( 2003 ), 1137 - 1155 .

[2] Christopher M Bishop . 2006 . PaŠern recognition . Machine Learning 128 ( 2006 ), 1 - 58 .

[3] Stanley F Chen and Joshua Goodman . 1996 . An empirical study of smoothing techniques for language modeling . In Proceedings of the 34th annual meeting on Association for Computational Linguistics. Association for Computational Linguistics , 310 - 318 .

[4] Chen Cheng , Haiqin Yang, Michael R Lyu , and Irwin King . 2013 . Where You Like to Go Next: Successive Point-of-Interest Recommendation. . In IJCAI , Vol. 13 . 2605 - 2611 .

[5] Junyoung Chung , Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio . 2014 . Empirical evaluation of gated recurrent neural networks on sequence modeling . arXiv preprint arXiv:1412.3555 ( 2014 ).

[6] Gregory W Corder and Dale I Foreman . 2014 . Nonparametric statistics: A stepby-step approach . John Wiley & Sons.

[7] Munmun De Choudhury , Moran Feldman, Sihem Amer-Yahia , Nadav Golbandi, Ronny Lempel, and Cong Yu . 2010 . Automatic construction of travel itineraries using social breadcrumbs . In Proceedings of the 21st ACM conference on Hypertext and hypermedia. ACM , 35 - 44 .

[8] Shanshan Feng , Xutao Li , Yifeng Zeng , Gao Cong, Yeow Meng Chee, and ‹an Yuan . 2015 . Personalized Ranking Metric Embedding for Next New POI Recommendation. . In IJCAI. 2069-2075.

[9] Ian Goodfellow , Yoshua Bengio, and Aaron Courville . 2016 . Deep Learning . MIT Press. hŠp://www.deeplearningbook.org.

[10] Alex Graves , Abdel-rahman Mohamed , and Geo‚rey Hinton. 2013 . Speech recognition with deep recurrent neural networks . In Acoustics, speech and signal processing (icassp) , 2013 ieee international conference on. IEEE , 6645 - 6649 .

[11] Aditya Grover and Jure Leskovec . 2016 . node2vec: Scalable feature learning for networks . In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM , 855 - 864 .

[12] Sepp Hochreiter and Ju¨rgen Schmidhuber. 1997 . Long short-term memory . Neural computation 9 , 8 ( 1997 ), 1735 - 1780 .

[13] Andrej Karpathy and Li Fei-Fei . 2015 . Deep visual-semantic alignments for generating image descriptions . In Proceedings of the IEEE Conference on Computer Vision and Paˆ ern Recognition . 3128 - 3137 .

[14] Diederik Kingma and Jimmy Ba . 2014 . Adam: A method for stochastic optimization . arXiv preprint arXiv:1412.6980 ( 2014 ).

[15] S Kotiloglu , T Lappas , K Pelechrinis, and PP Repoussis . 2017 . Personalized multi-period tour recommendations . Tourism Management 62 ( 2017 ), 76 - 88 .

[16] Yann LeCun , Yoshua Bengio, and Geo‚rey Hinton. 2015 . Deep learning . Nature 521 , 7553 ( 2015 ), 436 - 444 .

[17] Yanhua Li , Moritz Steiner , Limin Wang, Zhi-Li Zhang , and Jie Bao . 2013 . Exploring venue popularity in foursquare . In INFOCOM , 2013 Proceedings IEEE. IEEE , 3357 - 3362 .

[18] Bin Liu and Hui Xiong . 2013 . Point-of-interest recommendation in location based social networks with topic and location awareness . In Proceedings of the 2013 SIAM International Conference on Data Mining. SIAM , 396 - 404 .

[19] Laurens van der Maaten and Geo‚rey Hinton. 2008 . Visualizing data using t-SNE . Journal of Machine Learning Research 9 , Nov ( 2008 ), 2579 - 2605 .

[20] Tomas Mikolov , Martin Kara€a´t, Lukas Burget, Jan Cernocky`, and Sanjeev Khudanpur . 2010 . Recurrent neural network based language model .. In Interspeech , Vol. 2 . 3.

[21] Tomas Mikolov , Ilya Sutskever, Kai Chen, Greg S Corrado, and Je‚ Dean. 2013 . Distributed representations of words and phrases and their compositionality . In Advances in neural information processing systems . 3111 - 3119 .

[22] Anastasios Noulas , Salvatore Scellato, Cecilia Mascolo, and Massimiliano Pontil . 2011 . Exploiting Semantic Annotations for Clustering Geographic Areas and Users in Location-based Social Networks . Še Social Mobile Web 11 , 2 ( 2011 ).

[23] Enrico Palumbo , Giuseppe Rizzo, and Raphael Tro¨ncy. 2017 . entity2rec: Learning User-Item Relatedness from Knowledge Graphs for Top-N Item Recommendation . In Proceedings of the 11th ACM conference on Recommender systems. ACM.

[24] Daniel Preo ¸tiuc- Pietro , Justin Cranshaw , and Tae Yano . 2013 . Exploring venuebased city-to-city similarity measures . In Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing. ACM , 16 .

[25] Giuseppe Rizzo , Rosa Meo, Ruggero G Pensa, Giacomo Falcone , and Raphae¨l Troncy. 2017 . Shaping City Neighborhoods Leveraging Crowd Sensors . Information Systems 64 ( 2017 ), 368 - 378 .

[26] G. Rizzo , R. Troncy , O. Corcho , A. Jameson , J. Plu , J.C. Ballesteros Hermida , A. Assaf , C. Barbu , A. Spirescu , K. Kuhn , I. Celino , R. Agarwal , C.K. Nguyen , A. Pathak , C. Scanu , M. Valla , T. Haaker , E.S. Verga , M. Rossi , and J.L. Redondo Garcia . 2015 . 3cixty@ Expo Milano 2015 : Enabling Visitors to Explore a Smart City . In 14t h International Semantic Web Conference (ISWC) , Semantic Web Challenge.

[27] Jrgen Schmidhuber . 2015 . Deep learning in neural networks: An overview . Neural Networks 61 ( 2015 ), 85 - 117 .

[28] Nitish Srivastava , Geo‚rey Hinton, Alex Krizhevsky , Ilya Sutskever, and Ruslan Salakhutdinov . 2014 . Dropout: A simple way to prevent neural networks from over€Šing . Š e Journal of Machine Learning Research 15 , 1 ( 2014 ), 1929 - 1958 .

[29] Ilya Sutskever , James Martens, and Geo‚rey E Hinton . 2011 . Generating text with recurrent neural networks . In Proceedings of the 28th International Conference on Machine Learning (ICML-11) . 1017 - 1024 .

[30] Duyu Tang , Bing Qin, and Ting Liu. 2015 . Document Modeling with Gated Recurrent Neural Network for Sentiment Classi€cation. . In EMNLP . 1422 - 1432 .

[31] Pieter Vansteenwegen , Wouter Sou‚riau, and Dirk Van Oudheusden. 2011 . Œe orienteering problem: A survey . European Journal of Operational Research 209 , 1 ( 2011 ), 1 - 10 .

[32] Jihang Ye , Zhe Zhu, and Hong Cheng. 2013 . What's your next move: User activity prediction in location-based social networks . In Proceedings of the 2013 SIAM International Conference on Data Mining. SIAM , 171 - 179 .

[33] Yu Zheng , ‹annan Li, Yukun Chen, Xing Xie, and Wei-Ying Ma . 2008 . Understanding mobility based on GPS data . In Proceedings of the 10th international conference on Ubiquitous computing. ACM , 312 - 321 .