Paper_1_2_6 e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 115 Takeshi Watabe Kyoto University Hidekazu Kasahara Kyoto University Masaaki Iiyama Kyoto University Tourist Transition Model among Sightseeing Spots based on Trajectory Data In recent years, congestion of popular sightseeing spots and public transportation has become problematic in tourist destinations. Local governments have begun to forecast the congestion using a congestion simulation based on a tourist transition model and to adjust the operation of public transportation accordingly. In this study, a method to extract sightseeing spots is proposed and a tourist transition model for sightseeing spots based only on actual tourist trajectory data is constructed. The method has been evaluated using a school trip excursion trajectory dataset obtained from tourists in Kyoto, Japan. Key words: GPS, trajectory, tourism informatics, data mining Watabe Takeshi Graduate School of Informatics, Kyoto University Kyoto, Japan Email: watabe@mm.media.kyoto-u.ac.jp Hidekazu Kasahara Academic Centre for Computing and Media Studies, Kyoto University Kyoto, Japan Email: hidekazu.kasahara@mm.media.kyoto-u.ac.jp Masaaki Iiyama Academic Centre for Computing and Media Studies, Kyoto University Kyoto, Japan Email: iiyama@mm.media.kyoto-u.ac.jp e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 116 Introduction In recent years, with an increased influx of tourists to popular tourist destinations, public transportation and sightseeing spots are experiencing severe congestion. In an effort to minimize congestion, local governments forecast congestion by a congestion simulation based on a tourist transition model and adjust the operation of public transportation accordingly. Existing methods rely on information from guidebooks and websites like Wikipedia for model construction. An ideal tourist transition model is expected to contain all sightseeing spots; however, these sources limit model construction to only popular sightseeing spots (Ieiri, 2018). Therefore, a model that represents the transition between sightseeing spots that are not dependent on external data but actual data like GPS trajectories, which contains all the sightseeing spots, is required. In this study, GPS trajectory data are used to construct a tourist transition model because GPS trajectory data can be automatically collected by having tourists carry GPS equipment. As tourists tend to move slowly while sightseeing, it can be relied on their speed to extract sightseeing spots. Because tourists also tend to linger at railway stations or bus stops, first concentration points, which are spots where tourists move slowly including sightseeing spots and transit spots, are extracted. Then, they are classified using tourists’ speed distribution. Finally, the transition probability between sightseeing spots is calculated. The transition model is given by the transition probability. Related works is presented in Section 2 and an overview of this paper in Section 3. Section 4 describes the extraction of sightseeing spots only from GPS trajectory. In Section 5, the tourist transition model is constructed. A tourist transition model is actually constructed and evaluated in Section 6. Section 7 includes conclusions and outlines future work. Related work Extraction of sightseeing spots. Similar studies on sightseeing spots have mainly used two methods. One uses geotagged pictures on SNS (Crandall, 2009; Kurashima, 2009), and the e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 117 other uses GPS trajectory (Okada, 2008; Suhara, 2013). In these approaches, various clustering methods such as k-means (Fujisaka, 2010) and OPTICS (Zheng, 2009) are used. Among them, the mean-shift clustering (Dorin, 2002) is especially widely used (Crandall, 2009; Kurashima, 2009). Crandall (2009) and Kurashima (2013) report on methods for extracting sightseeing spots from geotagged pictures on SNS. Tourists tend to photograph sightseeing spots, which are then geotagged and clustered. However, these methods cannot distinguish between sightseeing spots and transit spots when it is applied to GPS trajectories. Therefore, sightseeing spots and transit spots have to be classified in order to construct a model including only sightseeing spots. Okada (2008) presented a method for the extraction of sightseeing spots from GPS trajectories using staying points by focusing on the speed; however, also this method does not distinguish between sightseeing spots and transit spots. Construction of transition model. In previous works on the sightseeing spots transition model, there is a method which strives for the improvement of the model through external information such as polygon data of sightseeing spots and route information in addition to GPS trajectories. For example, Horvitz and Kurmm (Kurmm, 2006, 2007; Horvitz, 2012) predict destinations using distributions of different districts, travel time, and trajectory’s length. Ziebart (2008) uses accident reports, road conditions, and driving habits. However, external information used for these methods often requires periodic renewal because of the transition of sightseeing spots. It is difficult to predict sightseeing spot changes in advance. Related work on the sightseeing spot transition model can be broadly divided to two categories: grid model (Kurmm, 2006; Xue, 2013, 2015; Takimoto, 2017) and spot model (Tamura, 2014, Ashbrook, 2003; Zheng, 2012; Kasahara, 2016). A grid model divides a geographical space into grids and assumes that a tourist moves on the grids; examples can be found in Xue (2013, 2015) and by Kurmm (2006, 2007). In these methods, the size of the cell is a problem. Xue (2013, 2015) states that the prediction accuracy for a destination is the highest when the side of the cell is 2 e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 118 km, and Kurmm (2006, 2007) sets the side of the cell to 1 km. However, when we set the size of the cell to 1 km or 2 km, some sightseeing spots may fall in one cell. However, the transition probability is obviously too small when the cell size is small. A spot model is a model, which assumes that a tourist moves between sightseeing spots directly, as shown in Ashbook (2003), Zheng (2012) and Tamura (2014). In these methods, Markov chains are used, and the geographical distance, transport networks, and data sparseness are not considered, which is a problem because it is difficult to obtain the transition probability from a sightseeing spot with few tourists. Overview In this study, first points with low moving speed, called staying points, from a tourist trajectory dataset are extracted. Then tourist concentration points are obtained by clustering staying points. Next, tourist concentration points are classified without external data as sightseeing spots and transit spots. In this paper, the sightseeing spots are defined as tourist destination (e.g., traditional temples, shrines, shops and restaurants) and the transit spots as spots that are places where tourist stop but that are not tourist destinations (e.g., stations and bus stops). A network including all tourist concentration points is called the concentration point network. The likelihood of the transition probability between all concentration points is deduced from the concentration network. By using the likelihood, the tourist transition network is built consisting only of sightseeing spots considering transit spots and the tourist transition model is obtained. The grid model divides a geographical space into grids evenly. However, many grids in a grid model correspond to the area where tourist cannot enter. The spot model assumes that a tourist moves between sightseeing spots directly. However, these methods do not consider the transportation network and the geographical distance between sightseeing spots. By introducing transit spots, our model uses a network, which has fewer unnecessary nodes than the grid model and considers the transportation network and geographical distance e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 119 between sightseeing spots (see Figure 1). First, the concentration point network, which contain sightseeing spots and transit points, is constructed. Then, the tourist transition network is constructed, which is the spot model by removing transit spots from the concentration point network. Figure 1. Network of each model Extraction of sightseeing spot Preprocessing of trajectory. A trajectory is a sequence of points, each with a latitude(lat), a longitude(lon), a time stamp(t), and ID(id), observed by GPS equipment. GPS trajectories are easily collected by using GPS equipment such as smartphones. Since some trajectories contain large GPS measurement errors (Inoue, 2015), they must be removed. Trajectories with large errors are considered to have sudden changing speed. The tourists’ speeds depend on their mode of transportation. However, measurement errors cause larger speed changes than any transportation. For this reason, the velocity v is added to trajectory points obtained from latitudes and longitudes and the points are removed, where v is larger than the threshold ve as an error. Extraction of concentration point. There are two patterns in which tourists decrease their speed for prolonged periods; for sightseeing and for transit. They are extracted as staying points. Temporary stopping is shorter than sightseeing and transit. In this research, ts is defined as the longest time of temporary stopping and vs as the maximum speed in sightseeing and transit. When v is less than vs continuously for more than ts, the points therebetween are extracted as a staying point. Next, tourist concentration points are obtained by clustering e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 120 staying points by the mean-shift method. The tourist concentration point c is defined as the centres of gravity of each cluster. Classification of concentration points. At first, a concentration point’s area S is defined as divined area using concentration points and a Voronoi decomposition. We define Iwalk as the area that tourists can enter on foot in S and Itrans as the area that tourist can enter using vehicles in S, Iall as a union of Iwalk and Itrans (see Figure 2). It is supposed that the ratio of the area occupied by Itrans in Iall is small in sightseeing spots and large in transit spots. Concentration points are classified using this assumption. To obtain the area of Iwalk and Itrans, images of Iwalk and Itrans are constructed using tourists’ speeds. At first, it is assumed that points in the trajectory are “walking points” if the speed is lower than vw and a “riding point” if the speed is higher than vw. Next, heat map images of “walking points” and “riding point” are constructed and binary images from heat map images for every concentration point. These binary images are called Icwalk and Ictrans. At last, feature value Rc is defined as: 𝑅" = 𝑁(𝐼'()*+" ) 𝑁(𝐼)--" ) where N(I) is the number of black pixels in I. Icall is the union of Icwalk and Ictrans. If Rc is smaller than Rτ, the concentration point is classified as a sightseeing spot. If Rc is larger than Rc, the concentration point is a transit spot. (a) map and trajectories (b) Itrans and Iwalk Figure 2. Example of Itrans and Iwalk e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 121 Construction of the tourist transition model Construction of the tourist transition network. At first, the concentration point network is constructed, which is a directed weighted network that has concentration points as nodes and edges between them if transitions between the concentration points are in trajectories. The edge weight pi,j is the ratio of the transition from the tourist concentration point i to the tourist concentration point j. We define pi,j as the probability of direct transitions from node i to node j. Next, the tourist transition network is constructed. Tourists don’t use only the shortest path. Therefore, the probability of transition from node i to node j, pi→j is defined as: 𝑝/→1 = 𝛼/ 3 4 𝑀( -67 (896,7 ; /,1 where M is a matrix M = (pi,j), di,j is the number of nodes of the shortest path from node i to node j and li,j the upper limit of the number of nodes that can be passed through from node i to node j. In this research, li,j is difined as 𝑙/,1 = 2 × 𝑑/,1 and α is the normalization term: 𝛼/ = 1 ∑ C∑ 𝑀(-6D (89{6,D} G /," "∈I where K is a set of sightseeing spots. The tourist transition network is defined as a network that has sightseeing spots as nodes and directed weighted edges as pi→j. Construction of tourist transition model. A tourist transition model is constructed using Markov chains, i.e., tourists’ next destination depends only on their current spot. Experiment Preprocessing. Our experiment is based on the 579 school trip excursion trajectory dataset collected by Kasahara (2015). Trajectories are obtained by an application installed in a GPS unit during a day at a one-second interval in December 2015. The experiment area was e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 122 set to a latitude of 34.80 degrees or more to 35.15 degrees or less, and a longitude 135.65 degrees or more to 135.85 degrees or less in order to make it around Kyoto City, where the school excursion was held. The threshold value to eliminate outliers ve was set to 180 (km/h). In addition, because points measured by Assisted GPS and Wi-Fi are low in measurement accuracy, they are eliminated. Experimental data included 9,530,489 observation points and 5,108,676 observation points after deleting points outside the experiment area and outliers. Classification of concentration point. In this study, we used vs = 3.6 (km/h) and ts = 200 (sec) for extracting the staying points. In addition, we used 0.0010 as the Gaussian kernel of the mean-shift clustering. In our method, we extracted 354 concentration points. To evaluate our method, we classified them by hand and obtained 170 sightseeing spots, 171 transit spots and 13 mis-extractions. Fig. 3 shows the distributions of the feature values Rc of the proposed method and Fig. 4 shows the ROC curve of Rc. Fig. 4 shows that the feature values Rc of sightseeing spots are mostly smaller than 0.4187 and the feature values Rc of transit spots are mostly larger than 0.4187. Therefore, we use 0.4187 as threshold Rτ in the model construction. As a result, the correct answer rate is 76.6%. Figure 3. Distribution of feature value Rc. Figure 4. ROC curve of Rc. Fig. 5 shows binary images created at a sightseeing spot corresponding to Ginkakuji, which is a famous temple in Japan. The feature value Rc of this sightseeing spot is very small, namely 0.040. The figure shows that the road inside Ginkakuji is extracted as Iall. In addition, it can be seen that there is almost no area that can be entered by car, apart from a small area. This is because the speed of these points cannot be accurately measured due to GPS e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 123 measurement errors. Fig. 6 shows binary images created at a transit spot corresponding to Yamashina station. The feature value Rc of this transit spot is very large, namely 0.855. The figure shows that the tracks are extracted as the area that can be entered by vehicle. In addition, it can be seen that the Iall are almost covered with Itrans. The example that could be incorrectly classified by the proposed method is shown in Fig. 7. It shows binary images created at a sightseeing spot corresponding to Tofukuji Temple. There is a road to the west of the temple. Therefore, the feature value Rc of this sightseeing spot is very large, namely 0.626. If a sightseeing spot does not have another concentration point like this, the divided area is so large that it contains a road or a track that is not related to the sightseeing spot. Therefore, the feature value Rc of this sightseeing spot becomes large and is misclassified. Itrans Iwalk Figure 5. Ginkaku-ji Temple, i.e., one of the most popular temples in Kyoto, Rc= 0.040 Itrans Iwalk Figure 6. Yamashina station, a station in southwestern Kyoto City, Rc= 0.855 e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 124 Itrans Iwalk Figure 7. Tofuku-ji Temple, which is in extreme southern Kyoto city, Rc= 0.626 Figure 8. Kinkakuji Temple and high transition probability spots Construction of tourist transition model. To evaluate our model, a tourist transition model for the experimental data set is constructed. As example, Fig. 8 shows Kinkakuji, which is a famous Japanese temple, and ten sightseeing spots with high transition probability from Kinkakuji with a map. In addition, in order to evaluate the whole model, the sightseeing spots are divided into several areas and the transition probability between each area is obtained. The result is shown in Table 1. As Table 1 shows, in most areas, the transition probability to the same area is the highest, followed by high transition probabilities to Kiyomizu Temple or Kyoto Station. In addition, transition probabilities tend to be high between geographically adjacent areas. Results show that tourists may make a transition to popular sightseeing spots such as Kyoto station and Kiyomizu Temple regardless of the distance from neighbouring sightseeing spots and to near sightseeing spots. e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 125 Table 1: Transition probability between areas Conclusion In this study, tourist concentration points were extracted and classified into sightseeing spots and transit spots only from trajectories. Furthermore, a method for modelling the transition between sightseeing spots was proposed. Using this method, it was possible to construct networks considering transit spots. Fixed features to incorporate into the model were used such as the threshold of the feature values, the bandwidth of the mean-shift method, and the route that tourist may choose on the concentration point network. However, these optimal values vary place to place. Thus, it is intended to improve our method by automatically determine these features for varying locations. References Ashbrook, D. & Starner, T. (2003). Using gps to learn significant locations and predict movement across multiple users., Personal and Ubiquitous Computing, Vol.7, No.5, pp.275-286. Comaniciu, D., & Meer, P. (2002). Mean shift: A robust approach toward feature space analysis, IEEE Trans. on PAMI. Crandall, D., Backstrom, L., Huttenlocher, D., & Kleinberg, J. (2009). Mapping the world’s photos, Proc, 18th international conference on World wide web, pp.761-770, ACM. Fujisaka, T., Lee, R., & Sumiya, K. (2010). Exploring urban characteristics using movement history of mass mobile microbloggers, Proceedings of the Eleventh Workshop on Mobile Computing Systems & Applications, pp.13-18. Horvitz, E. & Krumm, J. (2012). Some help on the way: opportunistic routing under uncertainty, UbiComp, 99.371-380. Ieiri, Y., Nakajima, Y., & Hishiyama, R. (2018). Construction of the Method to Discovery Potential Sightseeing Spot Based on Information Integration Process, The IEICE Transactions, D, Vol.J101-D, No.9, pp.1325-1333. e-Review of Tourism Research (eRTR), Vol. 16, No. 2/3, 2019 http://ertr.tamu.edu 126 Inoue, H., Kubota, S., Inoue, R., & Shigetaka, K. (2015). Research on acquisition of highly accurate three-dimensional position information using smartphone's GPS sensor, Journal of JSCE F3, Vol.71, No.2, pp.152-168. Kasahara, H., Mori, M., Mukunoki, M., & Minoh, M. (2015). Tourist Status Estimation from GPS Trajectory Using Environmental Constraints, Proceedings of the Annual Conference of JSAI (CD-ROM), Vol.29. Kasahara, H., Tamura, K., Iiyama, M., Mukunoki, M., & Minoh, M. (2016). Tourist Behavior Model Construction Based on Track of Tourists Using Regional Environmental Factors and Application, IPSJ Journal, Vol.57, No.5, pp.1411-1420. Krumm, J. & Horvitz, H. (2006). Predestination: Inferring destinations from partial trajectories, UbiComp, pp.371-380. Krumm, J. & Horvitz, E. (2007). Predestination: Where do you want to go today?, IEEE Computer, pp. 105-107. Kurashima T., Iwata T., Irie G., & Fujimura K. (2010). Travel route recommendation using geotags in photo sharing sites, Proc., 19th ACM international conference on information and knowledge management, pp.579-588. Okada, K., Yokoyama, T., Okuda, T., Kashihara, S., Kadibayashi, Y., & Yamaguchi, S. (2008). Proposal of a Method for Extracting Points of Interest from User's Trajectory, IPSJ SIG Technical Report, Vol.2008, Issue.91, pp.89-94. Suhara, Y., Toda, H., Nishikawa, J., & Washizaki, S. (2013). Simultaneous estimation of staying points and visited POI from GPS log using integer programming, IPSJ SIG Technical Report, Vol.2013-DBS-158, No.24, pp.1-8. Takimoto, Y., Nishida, K., Endo, Y., Toda, H., Sawada, H., & Ishikawa, H. (2017). Personalized destination prediction with consideration of time zone, The IEICE Transactions, D, Vol.J100-D, No.4, pp.472-484. Tamura, K., Kasahara, H., & Mukunoki, M. (2014). Modeling tourist activity via probe-car data and stop area similarity. Society for Tourism Informatics, 10(1), pp.101-112. Xue, A.Y., Zhang, R., Zheng, Y., Xie, X., Huang, J. & Xu, Z. (2013). Destination prediction by sub-trajectory synthesis and privacy protection against such prediction: ICDE, pp.254-256. Xue, A.Y., Qi, J., Xie, X., Zhang, R., Huang, J. and Li, Y. (2015). Solving the Data Sparsity Problem in Destination Prediction, The VLDB Journal 24, pp.219-243. Zheng, Y., Zhang, L., Xie, X., Ma, W.Y. (2009). Mining interesting locations and travel sequences from gps trajectories, Proceedings of the 18th international conference on World Wide Web, pp.791-800. Zheng, Y.T., Li, Y., Zha, Z.J. & Chua, T.S. (2012). Mining Travel Patterns from GPS- Tagged Photos, Advances in Multimedia Modeling, ACM Transactions on Intelligent Systems and Technology, Volume 3, issue 3, May 2012, pp.1-18. Ziebart, B.D., Maas, A.L., Dey, A.K. and Bagnell, J.A. (2008) Navigate Like a Cabbie: Probabilistic Reasoning from Observed Context-Aware Behavior, UbiComp,p.322-331.