Tour planning and recommendation is an important but tedious task for tourists visiting unfamiliar cities and places. While there are various personalized tour recommendation works, they typically adopt a simple measure of user interests based on the number of times a user has visited a place. In this paper, we propose an improved personalized tour recommendation system that considers a user's interest preferences in specific categories, relative to his/her overall interests. Using a Flickr dataset across eight cities, we compared our proposed algorithm against various baselines and experimental results show that our algorithm obtained superior performance in terms of user interest and popularity.
• Information systems → Personalization; Recommender systems; Location based services; Data mining; Web applications.
Tour planning is an important task for ensuring satisfactory visits to unfamiliar cities and places. However, visitors are faced with the challenge of identifying popular places aligned with their personal interests. In addition, there is an added complexity due to the need to schedule visits to all ∗Both authors contributed equally to this research.
IUI Workshops’19, March 20, 2019, Los Angeles, USA Copyright © 2019 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. recommended places while considering the available tour budget, time and cost.
There is an abundance of information available on Internet about travel guides and famous places, but they do not consider the user’s personal interests and preferences nor contemplate the trip’s constraints like time and cost. Despite the availability of such online information, people may end up spending excessive eforts and time to plan their itinerary, and yet end up with an undesired itinerary thus leaving them with an unsatisfactory and frustrating experience.
In recent times, personalized tour recommendation systems have benefited from the advancement in web technologies and geo-location services. The large amount of online available geo-tagged photos facilitate the modelling of user interest, preferences and trip constraints while strategizing itinerary planning. While many works consider user interest, they adopt a simple measure based on the number of times a user has visited a place.
Unlike earlier works that adopt a simplistic definition of user interest based on visit counts, this paper proposes a tour recommendation system that utilizes a novel user-relative measure of interest preferences build upon the Orienteering problem.
We propose two variation of user-specific interest preferences. The first approach aims to recommend an itinerary with no prior knowledge about the user by taking advantage of the large collection of geo tagged photos available online. Based on photo frequencies of each POI by all users, it determines the popularity of each POI and suggests the itinerary based on most popular POIs. The second approach aims to improve upon the targeted personalization level for each user. The benefits of this approach include having a tour itinerary that is customized for each user and caters to the user’s categories of interest. For example, in a city full of many tourist attractions, this approach caters to specific category the user is interested in. For example, if a user has shown to prefer outdoors and beaches more than museums and multiplexes, then the recommendation system takes that into account while building the itinerary. 2
Orienteering problem is a routing problem which can be
viewed as a contest with multiple nodes, where each node
has some specific score. The goal of the contest is to
maximize the total score which is gathered by visiting diferent
nodes. The contest is time constrained, which needs a
strategical plan to choose a subset of nodes visit in sequence, to
maximize collected budget within given time and budget [
Tour recommendation is a well-studied field that typically
focus on maximizing user preferences within the given trip
constraints [
Diferences with earlier work . Our proposed work
differs from these earlier works in several aspects. We
automatically derive a measure of user-based interest from the
user’s photo frequency at POIs of a specific category,
relative to: (i) The average photo frequencies of other users
at that POI; and (ii) The average photo frequency of that
user at all POIs. In contrast, these earlier works either use
time-based user interest, frequency-based user interest or
explicitly mentioned user interest preferences. In addition,
we improve upon the targeted personalization level for each
user by recommending customized itineraries that cater to
the user interest categories.
Problem Formulation. Similar to many earlier works [
Max Õ Õ pi ∈P pj ∈P
(1) where Pathpi ,pj = 1 if a path between POI pi and pj is selected as part of the itinerary, and Pathpi ,pj = 0 otherwise. Intu (pi ) represents a user-specific interest score of how interesting POI pi is to user u, while Pop(pi ) indicates the general popularity of POI pi . In addition, Equation 1 is subjected to the following constraints: (i) starting and ending at specific POIs; (ii) connectivity of POIs in the itinerary; (iii) completing the itinerary within a specific time or distance budget B.
In addition, Equation 1 is subjected to the following constraints:
Pathps ,pi =
Pathpj ,pd = 1
Constraint 2 ensures that the recommended itinerary starts at a specific POI ps , and ends at another specific POI pd . In real-life, this starting and destination POIs would correspond to POIs near the hotel that a tourist is staying at.
Pathpi ,pk =
Constraint 3 ensures that the recommended itinerary fuliflls two conditions, namely: (i) all selected paths are connected as a full itinerary; and (ii) no POIs are visited more than once.
Õ Õ pi ∈I pj ∈I
Constraint 4 ensures that the recommended itinerary can be completed within a specific time or distance budget B.
Algorithms and Baselines. We developed an Integer program to solve the problem defined in Section 3, along with novel approaches to defining user interest preferences. The two proposed approaches based on photo frequency are as follows:
(2) (3) (4) (i) POI based Photo frequency (P FP ): Given a set of travel history of all users U , the system determines the popularity of the POI using average photo frequency at each POI. (ii) User based photo frequency (P FU ): Given a set of travel history of a user u, the system determines the popularity of that category of POI for the user using average photos taken by that user at that category of the POI.
In a city, there can be multiple categories of places comprising of multiple POIS. Consider m POIs for a particular city. Let P = {p1, .., pm } be the set of POIs in that city. Each POI p has a category Catp (e.g., church, park, beach) and latitude/longitude coordinates associated with it. The popularity function Pop(p) that indicates the popularity of a POI p, based on the average frequency of photos clicked at that POI. We now introduce the key notations and definitions used in this work.
Definition 1: Travel History.
(1) P FP : Given a user u who has visited n POIs, the travel history is modelled as an ordered sequence, Sph = ((p1, f php1), (p2, f php2)...), with each duplet (px , f phpx ) comprising the visited POI px , and number of photos at POI px . (2) P FU : Given a POI p visited by n users, the travel record of POI p is modelled as an ordered sequence, Sph = ((u1, f phu1 ), (u2, f phu2 )...), with each duplet (ux , f phux ) comprising the user ux , and number of photos taken by ux .
Definition 2: Average POI Photo Frequency.
(1) P FP : Given a set of travel history of all users U , the system determines the popularity of the POI using average photo frequency at each POI.
1 Õ ph(p) = n where n is the number of photos taken by user u at all POIs P and δ (ux = u) = 1, if ux = u and 0, otherwise.
In tour recommendation problems, the user interest
preferences are typically derived from POI visit frequency [
Intuf ph (c) = (2) P FU :
Intuf ph (c) = relative to the average visit frequency for a better personalization.
Definition 3: Photo Frequency based User Interest.
As described earlier, the category of a POI p is denoted as Catp . Given that C represents the set of all POI categories, the interest of a user u in POI category c is determined as follows:
Õ (f phpx )δ (Catpx = C) ∀c ∈ C px ∈Sph ph(px ) where δ (Catpx = C) = 1, if Catpx = C and 0, otherwise.
Õ (f phux )δ (Catp = C) ∀c ∈ C ux ∈Sph ,p ∈P ph(ux ) where δ (Catp = C) = 1, if Catp = C and 0, otherwise.
Briefly, the above equations model the interest of a user in a particular POI category c based on photo frequency at each POI of category c, relative to the average photo frequency (of all users and a single user) at the same POI. The reason is that a user is likely to click more photos of the POI that he/she is interested in.
Hence, firstly by calculating how many more (or less) photos a user has taken, the interest level of this user in POIs of this category can be determined. Secondly, by calculating how many more (or less) photos have been taken by all users, the overall interest level of all users in POIs of this category can be determined.
Dataset. For our experiments, we utilized the Yahoo! Flickr
Creative Commons 100M dataset [
Evaluation and Metrics. We evaluated our algorithm and the baselines using leave-one-out cross-validation, which involves evaluating a specific travel sequence of a user while using his/her other travel sequences as training data. The and PT − 1PU ). starting/ending POI and travel duration are set to that of the specific travel sequence being evaluated, which is used as a representation of a person’s real-life visit. The following evaluation metrics were used: (1) Tour Popularity: Tpop (I ). The total popularity of all
POIs in itinerary I. (2) Tour Interest: T u I . The total interest of all POIs
I nt ( ) in itinerary I to user u. (3) Tour Precision: Tp (I ). The proportion of POIs recommended in itinerary I, which matched user’s real-life travel sequence. (4) Tour Recall: Tr (I ). The proportion of POIs in a user’s actual travel sequence that were also recommended in itinerary I.
Algorithm PT − .5PU PT − 1PU PT − .5PA PT − 1PA PT − .5T PT − 1T Algorithm PT − .5PU PT − 1PU PT − .5PA PT − 1PA PT − .5T PT − 1T Algorithm PT − .5PU PT − 1PU PT − .5PA PT − 1PA PT − .5T PT − 1T Algorithm PT − .5PU PT − 1PU PT − .5PA PT − 1PA PT − .5T PT − 1T
Popularity (5) Tour F1−score: TF1 (I ). The harmonic mean of both the recall and precision of a recommended tour itinerary I. 5
Table 1 show the comparison between Time-based User Interest (PT − .5T and PT − 1T ), Photo Frequency-based User Interest with respect to all users (PT − .5PA and PT − 1PA) and Photo Frequency-based User Interest with respect to single user (PT − .5PU and PT − 1PU ). Overall results show that our Photo Frequency-based algorithms outperform the baselines in terms of popularity and interest, while ofering comparable performance in terms of other metrics. Comparison of Popularity and Interest. In terms of Interest (Tint ) metric, the proposed algortihms outperform the baselines in all the cities, with PT − 1PA being the best performing algorithm, followed by PT − 1PU . In terms of Popularity (Tpop ) metric, PT − .5PU performs equally good as the baseline PT − .5T . In four cities PT − .5PU performs the best and in other four PT − .5T . The results show that the Photo Frequency-based algorithms reflects on the overall popularity and overall interests of the POIs better than the baselines, for recommending itineraries.
Comparison between Time based and Photo-Frequency based User Interest. With regards to precision (Tp ), recall (Tr ) and f1-score (TF1 ) the proposed algorithms outperform one of the baselines (PT − 1T ) in all the cities, standing the second best. In terms of Tp , PT − .5PU performs the second best in five cities, followed by PT − .5PA performing the second best in one city. In terms of Tr , PT − .5PU performs the second best in four cities and PT − .5PA performs the second best in rest four. Here, PT − .5PU and PT − .5PA perform equally good. These two proposed algorithms outperform the baseline (PT − 1T ) with regards to recall. In concern to the F1-score TF1 metric, the proposed algorithm PT − 1PA performs the best on one city, PT − .5PU performs the second best in five cities, followed by PT − .5PA performing the second best in two cities. The results show that the proposed algorithms outperforms the baselines in most cities in terms of popularity and interest. The algorithms (PT − .5PU and PT − .5PA) outperform one baseline, performing second best in terms of precision, recall and f1-score.
We modelled our tour recommendation problem as an instance of the Orienteering problem and proposed two algorithms for recommending personalized tours. We recommend suitable POIs using both photo frequency user interest preference and POI popularity. We used geo-tagged photos to determine the photo frequency of the user and automatically derive user interest and POI popularity to train the algorithms. Our work improves upon the previous research in following ways: (i) We introduce photo frequency based user interest derived from the number of photos taken by the user at a POI of a specific category, unlike earlier works which consider time-based or frequency-based user interest; and (ii) We improve upon the targeted personalization level for each user by recommending customized itineraries that cater to the user interest preferences learnt from the user photo frequency dataset. Using Flickr dataset across eight cities, we evaluate our algorithms in terms of precision, recall, F1-score, tour popularity and interest. The results show that: (i) Using photo-frequency based user interest outperform the baselines in all cities in terms of interest. It is at par with the baselines in terms of tour popularity by sharing equal stand; and (ii) The proposed algorithms outperform one of the baseline algorithms of time-based user interest in terms of overall precision, recall and F1-score.
In this work, our focus was to recommend user-relative personalized tour itineraries. Some possible future work directions are: (i) Using sentiment awareness on content obtained from location based social network tags to combine sentiment analysis techniques with personalization approaches and path planning algorithms for recommending itineraries that consider user interest preferences and sentiments; and (ii) Recommending tour itineraries by considering the public transport arrival and departure time to facilitate realistic tour planning and minimize public transport waiting time. Moreover, real time uncertainty of public transport could be modelled to improve the suitability.
This research is partly supported by the Singapore University of Technology and Design under grant SRG-ISTD-2018-140, and Defence Science and Technology, Australia. The authors thank Jefrey Chan, Aaron Harwood and the anonymous reviewers for their useful comments on this work.