Paper_1_2_2 e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 73 Junjie Sun Kyoto University Chenyi Zhuang National Institute of Advanced Industrial Science and Technology, Japan Qiang Ma Kyoto University Travel Route Recommendation by Considering User Transition Patterns Travel route recommendation services that recommend a sequence of points-of-interest (POIs) for tourists are very useful in location-based social networks (LBSNs). Currently, most of the work that addresses this task are focusing on personalization and POI features, which estimate user-location relations while rarely considering transitions, i.e., the relationships between locations. To this end, we propose a latent factorization model that learns transition patterns with enhanced spatial-temporal features between locations. Furthermore, we recommend travel routes by combining knowledge on locations and transitions. Experimental results with public datasets reveal that our approaches improve upon the performance of conventional methods. Key words: travel route recommendation, LBSN, sightseeing, matrix factorization Junjie Sun Department of Social Informatics Graduate School of Informatics Kyoto University Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, JAPAN Email: jj-sun@db.soc.i.kyoto-u.ac.jp Chenyi Zhuang National Institute of Advanced Industrial Science and Technology 2-3-26 Aomi, Koto-ku, Tokyo 135-0064 JAPAN Email: zhuangchenyi@gmail.com Qiang Ma Department of Social Informatics Graduate School of Informatics Kyoto University Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, JAPAN Email: qiang@i.kyoto-u.ac.jp e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 74 Introduction The development of LBSN services has increased the number of user-location interaction behaviours via various devices. It is an important task to help tourists planning their travel routes in an unfamiliar city. Travel route recommendation, which is addressed in this paper, aims to recommend a sequence of POIs and to satisfy tourists’ trip constraints. Recent studies formulate travel route recommendation problems based on the orienteering problem model (Tsiligirides, 1984) in which tourists earn a reward when they visit one POI. The travel path with the maximum reward score under several trip constraints will be recommended (Friggstad et al., 2018; Lim et al., 2015; Vansteenwegen et al., 2011). The user- location relations (i.e., matching users and locations) are studied, and reward scores are assigned to POIs which can be regarded as tourist preferences on POIs. Generally, a travel route consists of nodes (i.e., locations) and edges (i.e., the transition between locations). Transition patterns can be regarded as location-location relations. The higher the weight on the transition, the tighter the connection between two locations. Transition patterns may also imply some valuable sightseeing routes (paths), since some POIs are in a sequential structure or a large area, and walking through these paths is also a part of the trip (e.g., a park or a street along the way to the next POI). However, related work rarely considers the edges (i.e., transition knowledge) of the specific target travel city. Most of them model edges as constraints: In general orienteering- problem based approaches (Vansteenwegen et al., 2011; Kurata et al., 2011), the travel time cost on transitions is considered; traffic conditions are considered in (Chen et al., 2015), which uses traffic-aware edge constraints; uncertain travel time between POIs is considered in (Zhang et al., 2016). In (Zhuang et al., 2017), POIs are recommended by using enriched location- location features. In (Liu et al., 2016), the users’ next visited location is predicted, while a deep learning approach with tong short-term memory (LSTM) that integrates next-location prediction into travel route planning is proposed in (Xu et al., 2017), which can be regarded as e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 75 leveraging transition patterns. In (Chen et al., 2016), transition reward is included into the travel route recommendation objective function, and travel routes based on both POIs and transition probability are recommended. Their transition probability is factorized from explicit feature- pairs such as the POI popularity and category (i.e., shopping-park or popular-unpopular pairs). Therefore, the dependency between locations caused by spatial-temporal factors has not been considered so far in previous works that combine both points and transitions to recommend travel route. In this paper, we propose a spatial-temporal enhanced latent factorization model to study the connections between locations, and the experimental results reveal the efficiency of spatial-temporal influences between locations. Travel Route Recommendation 1. Objective function: Given a user query (𝑝#, 𝑝%, 𝐿) in which 𝑝# and 𝑝% represent the origin and destination points, respectively. 𝐿 represents the travel length budget, i.e., how many POIs one wants to visit. A common travel route recommendation problem definition and objective function are given in (Lim et al., 2015; Chen et al., 2016). Basically, there are 𝑁 POIs; and let 𝑃 = {𝑝,, 𝑝-, … , 𝑝/} in the target travel city. A travel route is recommended according to the user query by solving the following objective function: max44π‘₯67𝑅(𝑝7|𝑝6) / 7:- /;, 6:, (1) 𝑅 is the reward function; 𝑁 is the available number of POIs in the city; π‘₯67 is a binary indicator that equals 1 when users travel from 𝑝6 to 𝑝7, and equals 0 otherwise. It is subject to several constraints such as the requirement that a travel route must start from 𝑝# and end at 𝑝% and the travel budget. In this paper, we consider the travel length budget. Due to the space limitation, please refer to related work for the details of that constraints. e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 76 Similar to (Chen et al., 2016), we model transition rewards into the reward function in Eq. 1 as below: 𝑅<𝑝7=𝑝6> = 𝛼𝑅A<𝑝7> + (1 βˆ’ 𝛼)𝑅E(𝑝7|𝑝6), (2) where 𝑅A and 𝑅E represent point reward and transition reward, which are defined in the following sections; and 𝛼 ∈ (0, 1) is a trade-off parameter that indicates the importance of the point and transition rewards. 2. POI reward: We assign rewards to POIs by considering user-location relations. Since it is a well-studied area, we directly leverage the proposed method in (Chen et al., 2016) to assign rewards to POIs. It is called PoiRank, which uses Rank Support Vector Machine (RankSVM) (Ching-Pei, 2014) with features such as category, popularity, and average visit duration to rank all POIs. Finally, a softmax function is used to transfer rank scores to POI rewards. They are represented as 𝑅A<𝑝7>. 3. Transition reward: To improve the recommended travel route quality, which makes the route planning order aware, we regard transition patterns as rewards on transitions. Since transitions that we can observe are incomplete and the new POI has no transitions, we need to infer transition rewards from observed data. Unlike explicitly factorize feature pairs in (Chen et al., 2016), we use a latent matrix factorization method with enhanced spatial-temporal features to infer the transition patterns. Transition rewards are represented as: 𝑅E<𝑝7=𝑝6> = 𝑇I6,7, (3) where 𝑇I6,7 is the inferred transition reward matrix as defined below. 1) Weighted transition matrix: There are users’ transitions between locations, i.e., moving from POI 𝑝6 to 𝑝7 according to travel routes data. In this manner, we capture a weighted transition matrix represented by 𝑇J ∈ ℝ|L|Γ—|L|, where each entry 𝑇J6,7 denotes the observed transition frequency between POIs 𝑝6 and 𝑝7 , and |𝑉| is the number of POIs in a particular city. Then 𝑇 is equal to 𝑇J normalized by the maximum entry; 𝑇 is regarded as the e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 77 relative transition weights between locations; similar to the idea of collaborative filtering, in which POIs may have common connections to other POIs owing to common features that match very well. One reasonable solution is to factorize the observed weighted transition matrix 𝑇 as below: 𝑇 β‰ˆ 𝑉#𝑀𝑉QE, (4) where 𝑉# ∈ ℝ|L|Γ—R and 𝑉Q ∈ ℝ|L|Γ—R represent latent features of a source and a destination point, respectively. 𝑀 is the interaction matrix that represents the relationship between locations, and π‘˜ specifies the number of latent features. 2) Spatial-temporal influences: Spatial and temporal influences are very important in location recommendation tasks. Inspired by (Lian et al., 2014), we can explicitly embed spatial- temporal influences to improve our weighted transition matrix factorization model. For spatial influence, we consider the simple assumption that the closer POIs are the more likely they are visited. We calculate the distances between POIs using the Haversine formula (Sinnott 1984), then take the reciprocal and normalize each entry by the maximum value in the matrix to construct the POI spatial influence matrix 𝐺 ∈ ℝ|L|Γ—|L|. The spatial influence matrix can be regarded as additional global knowledge that each entry represents the confidence of location-location spatial influence, where the distance is smaller when the influence is larger. The spatial influence matrix can be written as 𝐺 β‰ˆ 𝑉U𝑉UE , where 𝑉U represents the spatial feature between POIs and it can get be obtained by factorizing 𝐺 through standard non-negative matrix factorization (NMF) (Lee et al., 1999). For temporal influence, we consider the relationship between the check-in time of each POI and the user transition time interval. Each POI has an available open time window and visits vary over 24 hours (e.g., Figure 1). We assume that the visit time of a location over a day follows a mixed Gaussian distribution and has visit peaks. Also, we observe that users’ transitions between locations in different cities are almost all less than 2 hours (e.g., Figure 2), e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 78 and we use a Poisson distribution to fit it. For example, two locations’ spatial influences are higher due to a smaller distance (i.e., a transition from one to the other is more likely), while their visit peaks have a big gap (e.g., one has a peak in the morning and the other in the night) that indicates that the transition possibility would not be very high. Therefore, if two locations’ visit peaks better match the users’ transition interval, the temporal influence is higher. Figure 1: Visit time distributions; examples of two POIs over 24 hours Figure 2: Visit time interval distributions in the Toronto dataset A gaussian mixture model (GMM) is applied to fit the check-in data. It automatically fits the data and the GMM component ranges from 1 to 3, which corresponds to morning, afternoon, and night. Then the temporal influence matrix 𝐢J ∈ ℝ|L|Γ—|L| is constructed by matching the mean differences between locations with the fitted transition time interval distribution. 𝐢 is equal to the normalized 𝐢J that represents the temporal influence between POIs. We represent our constructed temporal influence matrix 𝐢 as 𝐢 β‰ˆ 𝑉W𝑉WE , where 𝑉W represents the latent temporal features between POIs and it can be obtained through standard NMF. We explicitly combine the spatial and temporal influences linearly to enrich Eq. 4 as: 𝑇 β‰ˆ 𝑉#𝑀𝑉QE + 𝑉U𝑀𝑉UE + 𝑉W𝑀𝑉WE (5) The latent factors 𝑉#, 𝑉Q and 𝑀 can be computed by solving the following function: min LZ,L[,\ ]𝐼 βŠ™ (𝑇 βˆ’ 𝑉#𝑀𝑉QE βˆ’ 𝑉U𝑀𝑉UE βˆ’ 𝑉W𝑀𝑉WE)] - + πœ†[ ‖𝑉#β€–- + ‖𝑀‖- + ‖𝑉Qβ€–- ], (6) e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 79 where βˆ₯βˆ™βˆ₯- denotes the Frobenius norm; 𝐼 is a binary weighted matrix with entries 𝐼#,Q indicating whether transitions have been observed; and πœ† is the regularization parameter. Finally, we can infer the transition matrix using Eq. 5 and normalize it by the maximum entry to obtain the transition reward matrix 𝑇I . We use the Theano framework (https://github.com/Theano/Theano) to learn latent variables and solve the objective function in Eq. 1 with the Gurobi optimization package (http://www.gurobi.com). Experiment To evaluate our proposed approaches, we apply our methods to public location-based social network datasets provided by (Chen et al., 2016; Lim et al., 2015). These datasets capture user travel routes extracted from Flickr photos; the statistics are listed in Table 1. In our experimental settings, we randomly split each city dataset into five. We use five- fold cross-validation to evaluate different approaches, which means that when testing on a part of the dataset, we use the other data to train different models. Specifically, we consider users’ real-life travel routes with more than 3 check-ins and test the following methods on each city dataset: PoiPop: Recommends a travel route only based on the ordered POI popularity. PoiRank, Markov, Rank+Markov: Proposed in (Chen et al., 2016), these methods recommend routes based on i) the ranking of POI scores, ii) transition probabilities through explicit feature pairs, and iii) their combination. Table 1: Statistics of Travel Route Datasets Dataset #Photos #Check-ins #Travel routes #Users Edinburgh 82,060 33,944 5,028 1,454 Glasgow 29,019 11,434 2,227 601 Osaka 392,420 7,747 1,115 450 Toronto 157,505 39,419 6,057 1,395 e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 80 Tmf, GTmf, TGTmf: Our proposed methods that recommend routes based on i) weighted transition matrix factorization, ii) spatial influence, and iii) spatial-temporal influence. Rank + Tmf, Rank + GTmf, Rank + TGTmf: Our proposed methods that combine location and transition rewards. To compare all the mentioned approaches, we evaluate the performance of each method based on users’ real-life travel routes using the following metrics: F1 score: The F1 score is a common metric for evaluating POI and travel route recommendations. It evaluates the recommended results with the user’s real travel route using the harmonic mean of recall and precision of recommended locations. Pairs-F1 score: Proposed in (Chen et al., 2016), the Pairs-F1 score is used to evaluate both POI identity and visiting simultaneously. Pairs-F1 computes the F1 score of a pair of points and has a value between 0 and 1. It will achieve a score of 1 if and only if the POIs and the visiting order are exactly the same as the user’s real travel route. Results The performance of the different approaches for each of the city datasets is summarized in Table 2 and Table 3, in terms of F1 score and Pairs-F1 score, respectively. The best method for each dataset is shown in bold and the second best in italic. PoiRank improves upon the performance of PoiPop, which is only based on POI popularity, by leveraging more features. Among all the transition-based approaches, directly factorizing the weighted transition matrix had no effect that compares to the explicit factorization method Markov, which indicates that the latent factor model includes those features. Subsequently, the performance improved drastically when additional spatial and temporal influences were considered. Generally, we found that the combination method with a trade-off parameter 𝛼 of around 0.7 achieves the best performance, which indicates that point e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 81 rewards are relatively more important. Furthermore, the methods Rank+GTmf and Rank+TGTmf that we proposed outperformed baseline methods on different datasets, which indicates that spatial and temporal information is efficient in the transition patterns inference. Table 2: Performance in Terms of F1 Score Edinburgh Glasgow Osaka Toronto PoiPop 0.660 Β± 0.158 0.690 Β± 0.164 0.640 Β± 0.130 0.664 Β± 0.120 PoiRank 0.679 Β± 0.145 0.708 Β± 0.148 0.724 Β± 0.160 0.749 Β± 0.164 Markov 0.667 Β± 0.152 0.741 Β± 0.165 0.688 Β± 0.152 0.711 Β± 0.151 Tmf 0.661 Β± 0.157 0.660 Β± 0.157 0.660 Β± 0.136 0.691 Β± 0.157 GTmf 0.658 Β± 0.170 0.769 Β± 0.190 0.671 Β± 0.172 0.691 Β± 0.157 TGTmf 0.682 Β± 0.172 0.777 Β± 0.184 0.729 Β± 0.186 0.722 Β± 0.175 Rank + Markov 0.705 Β± 0.162 0.756 Β± 0.165 0.720 Β± 0.166 0.743 Β± 0.165 Rank + Tmf 0.689 Β± 0.161 0.733 Β± 0.172 0.738 Β± 0.174 0.745 Β± 0.160 Rank + GTmf 0.709 Β± 0.163 0.772 Β± 0.189 0.741 Β± 0.169 0.764 Β± 0.172 Rank + TGTmf 0.717 Β± 0.163 0.786 Β± 0.178 0.753 Β± 0.187 0.767 Β± 0.170 Table 3: Performance in Terms of Pairs-F1 Score Edinburgh Glasgow Osaka Toronto PoiPop 0.399 Β± 0.253 0.407 Β± 0.296 0.324 Β± 0.193 0.364 Β± 0.201 PoiRank 0.399 Β± 0.226 0.437 Β± 0.252 0.468 Β± 0.281 0.512 Β± 0.293 Markov 0.385 Β± 0.233 0.503 Β± 0.298 0.416 Β± 0.261 0.442 Β± 0.256 Tmf 0.380 Β± 0.236 0.375 Β± 0.246 0.360 Β± 0.200 0.420 Β± 0.261 GTmf 0.412 Β± 0.277 0.558 Β± 0.332 0.398 Β± 0.273 0.476 Β± 0.296 TGTmf 0.403 Β± 0.279 0.576 Β± 0.328 0.496 Β± 0.319 0.540 Β± 0.308 Rank + Markov 0.446 Β± 0.265 0.526 Β± 0.299 0.470 Β± 0.292 0.502 Β± 0.292 Rank + Tmf 0.419 Β± 0.252 0.492 Β± 0.298 0.501 Β± 0.308 0.505 Β± 0.288 Rank + GTmf 0.461 Β± 0.277 0.563 Β± 0.330 0.509 Β± 0.304 0.539 Β± 0.303 Rank + TGTmf 0.471 Β± 0.276 0.588 Β± 0.325 0.537 Β± 0.326 0.547 Β± 0.306 e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 82 Conclusion This paper describes a technique that uses locations and transitions extracted from travel route data to recommend travel routes according to user queries. Experiment results demonstrate that our approaches outperform conventional methods on different datasets by using spatial-temporal enhanced transition patterns inference. In our future work, we would like to apply the method proposed in this paper to Kyoto city and evaluate it with real tourists. References Chen, D., Ong, C. S., & Xie, L. (2016). Learning points and routes to recommend trajectories. In: 25th ACM CIKM (pp. 2227-2232). Chen, C., Zhang, D., Guo, B., Ma, X., Pan, G., & Wu, Z. (2015). TripPlanner: Personalized trip planning leveraging heterogeneous crowdsourced digital footprints. IEEE TITS, 16(3), 1259-1273. Ching-Pei, L. and Chih-Jen, L. (2014). Large-scale linear ranksvm. Neural computation 26, 4 (2014), 781–817. Friggstad, Z., Gollapudi, S., Kollias, K., Sarlos, T., Swamy, C., & Tomkins, A. (2018). Orienteering Algorithms for Generating Travel Itineraries. In: 11th ACM WSDM (pp. 180-188). Lian, D., Zhao, C., Xie, X., Sun, G., Chen, E., & Rui, Y. (2014). GeoMF: joint geo- graphical modeling and matrix factorization for point-of-interest recommendation. In: 20th ACM SIGKDD (pp. 831-840). Lim, K. H., Chan, J., Leckie, C., & Karunasekera, S. (2015). Personalized Tour Recommendation Based on User Interests and Points of Interest Visit Durations. In: 24th IJCAI (pp. 1778-1784). Liu, Q., Wu, S., Wang, L., & Tan, T. (2016). Predicting the Next Location: A Recurrent Model with Spatial and Temporal Contexts. In: 30th AAAI (pp. 194-200). Lee, D. D.Seung, H. S. (1999). Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755), 788. Kurata, Y. (2011). CT-Planner2: More flexible and interactive assistance for day tour planning. In: ENTER 2011 (pp. 25-37). Sinnott R. W. Virtues of the haversine. (1984). Sky and telescope, 68(2):159. Tsiligirides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9), 797-809. Vansteenwegen, P., Souriau, W., Berghe, G. V., & Van Oudheusden, D. (2011). The citytrip planner: expert system for tourists. Expert Systems with Applications, 38(6), 6540- 6546. Xu, J., Li, C., Wang, S., Huang, F., Li, Z., He, Y., & Zhao, Z. (2017). DTRP: A Flexible Deep Framework for Travel Route Planning. In: WISE2017 (pp. 359-375). Springer, Cham. e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 83 Zhang, C., Liang, H., & Wang, K. (2016). Trip recommendation meets real-world constraints: POI availability, diversity, and traveling time uncertainty. ACM TOIS, 35(1), 5. Zhuang, C., Yuan, N. J., Song, R., Xie, X., & Ma, Q. (2017). Understanding people lifestyles: construction of urban movement knowledge graph from GPS trajectory. In: 26th IJCAI (pp. 3616-3623). Acknowledgment This work is partly supported by MIC SCOPE (172307001).