i GPS ( ) POI(Place Of Interest)

25 2 1

i GPS ( ) POI(Place Of Interest)

ii POI Mean-Shift Web Web (1) (2) POI (3) POI 2011 1 12 12 2011 12 7 4

Modeling tourist activity via probe-car data and spot similarity Kazunori TAMURA Abstract The number of personal tourists, who freely decide on visiting spot, is increasing in recent years. Conventionally, the questionnaire method in which a tourist records his/her touristic activities based on his/her memory has been used for survey and analysis of the personal tourism. However, tourists cannot remember all of their activities precisely and it is not realistic to collect a lot of data by this method. On the other hand, a large amount of probe-car data using GPS has been stored. Probe-car data provides cars location points, speeds and so on. Since probe-car data is automatically stored by car navigation system, it has an advantage that data with high objectivity is able to be collected at low cost compared with the questionnaire method. Thus, we aim at modeling tourists activities using probe-car data of users who use cars for sightseeing. The tourist activity model helps in comprehending which tourism spot tends to be visited by tourists. Furthermore, it can be used for the spot recommendation system by predicting the tourism spots where a user will visit next. We grasp tourists activities as spot transitions and build the model which can predict the user s next transition. In previous research related to the tourist activity modeling, tourists activities are modeled using first-order Markov model (we simply call it Markov model). Markov model assumes that the next visiting spot depends only on the current spot. However, there is a sparsity problem in Markov model, that is, it is difficult to predict the next transition from a minor spot where a few users visit. In this paper, we assume that users who are in similar spots tend to move to the same spot, and cope with the sparsity problem in Markov model using spot similarities. Probe-car data, in this paper, consists of two kinds of data. One is the stop location data, which records when and where a car stops more than 10 minutes. A user s stop location data ordered by time can be regarded as his/her location history of the tour. The other is the place of interest(poi) data, which records the POI name which a user set as his/her destination. In this paper, we relate the stop locations to spots and calculate spot similarities using the POI data to model tourists activities. Details iii

iv of the proposed method are as follows. First, areas where many users stop are extracted as spots in order to model tourists activities as spot transitions. We cluster the stop location data by the mean shift procedure and define the spots each of which corresponds to a cluster. Once we have extracted a set of spots, each location history, which is a sequence of locations, is converted to a sequence of spots. Next, spot similarities are calculated based on external information from the Web. Using external data acquired from the Web, we can (1) get fine features of spots, (2) get features which reflect impression of the POIs people generally have, and (3) relate POIs to sightseeing areas in the real world. Finally, the scores of transitions from a user s current spot to another spot are calculated. Our model predicts that a user will move to the largest score spot. Conventional Markov model uses data of transitions only from the current spot. In contrast, our model uses data of transitions even from other spots which are similar to the current spot. This enables us to predict the next spot properly even if the user is in a minor spot at the time. To examine the effectiveness of the proposed method, we conducted an experiment, in which we evaluated the accuracy of the transition prediction by our model. We use the probe-car data in Kyoto in 2011 stored by car navigation systems produced by Pioneer. We filtered out tourists from all the car navigation users by collecting data of users who live in outside of Kyoto prefecture and who have stopped in Kyoto city area on at most 7 days. Applying proposed method to 4 data sets, which vary in parameters of spot extraction, the prediction accuracies for all 4 data sets were higher than ones with Markov model. This result shows that our model describes tourists activities better than the conventional method.

1 1 2 3 2.1........................................ 3 2.2........................................ 5 2.3.......................................... 6 2.4..................... 6 3 7 3.1....................................... 7 3.2..................................... 9 3.3.............................. 10 3.4.............. 10 3.4.1............................... 12 3.4.2................................. 13 3.4.3 tf-idf........................ 13 3.4.4........................ 14 3.4.5....................... 14 3.5............ 15 4 15 4.1....................................... 16 4.1.1............................... 16 4.1.2............................. 17 4.1.3............. 17 4.1.4.......................... 17 4.2................... 19 4.3..................................... 20 4.4.............................. 22

5 23 24 25

1 [1] GPS 1

POI(Place of Interest) POI POI POI ID POI Ashbrook [2] [2] ( ) 1 1 2

Web 2 3 4 5 2 2.1 10 0km/h 10 POI(Place of Interest) POI POI POI POI 1 POI 3

ƒ WK/ µµ WK/ WK/ ƒ WK/ 1: POI POI POI POI POI Web POI POI 2 POI POI POI POI POI 4

U u h u (h u 1,, hu h u ) hu H h u i u i h u i = (l u i, pu i ) lu i p u i POI p u i H POI P H S {s i } s t s t+1 s i H li u li u 1 2.2 GPS Flickr Foursquare SNS [3] Flickr Bao[4] Foursquare GPS Web GPS Zheng [5] [6] Zheng [5] POI yellow page [6] Wikipedia 5

2.3 SNS [3, 4] SNS 1 [3, 4] Zheng [5] POI POI POI POI POI POI Bao [4] Foursquare POI POI Foursquare 2.4 6

1 1 Pr(s t+1 s t, s t 1,, s 1 ) = Pr(s t+1 s t ) (1) Pr(s t+1 s t ) Pr(s t+1 s t ) = N(s t, s t+1 ) N(s t ) (2) N(s t, s t+1 ) s t s t+1 N(s t ) s t s t P(s t+1 s t ) s t+1 s t P(s t+1 s t ) s t s t s t s t s t P(s i s t ) P(s i s t) (1 i S ) 3.4 3 3.1 2 4 2 7

H m ij 2: 1. H S S 1 3.2 2. 2 h u i s u i s u i 2 3.3 3. 8

Web 3 3.4 4. 2 3 s t s t+1 4 3.5 3.2 POI POI POI POI POI POI H h u i li u Mean-Shift [7] Mean-Shift 2 1 1 Mean-Shift [3, 8] Mean-Shift bandwidth Mean-Shift bandwidth bandwidth 9

Mean-Shift 3.3 h u i h u i = (l u i, pu i ) h u i = (s u i, pu i ) su i h u i h u = (h u 1,, h u h u ), h u H 3.4 c s = (c s 1,, cs P ) cs i s POI p i ( P) c s i = # { (u, k) s u k = s, pu k = p } i (3) # c s POI p i s s POI p i POI p i POI p i c s i s POI p i s POI c s i s 10

POI c s i c s c s c s c s c s POI POI c s i 0 POI c s i 0 0 POI POI 2.3 POI POI Web POI Web POI (POI ) POI c s Web POI Web Web POI 1. POI 11

POI 2. POI 3. POI 3 POI Web POI Web POI POI Web Web Web POI 1. POI Web 2. 3. tf-idf POI 4. POI c s 5. 3.4.1 POI Web Web POI POI POI POI Web Web 12

Web Web δ Web POI POI p i POI d i 1 1 URL Web 3.4.2 POI MeCab[9] Web T POI d i t j ( T) n i j 3.4.3 tf-idf POI tf-idf [10] POI tf-idf 1 tf-idf tf-idf POI d i t j w i j w i j = t f i j id f j (4) ( t f i j = log 1 + n ) i j k n ik id f j = log P # { d d t j } # { d d t j } t j POI POI POI POI p i POI v p i POI (5) (6) 13

3 単 語 p v 1 p2 v 寺 0.1 0.2 0.03 映 画 0.0 0.0 0.1 美 術 0.02 0.01 0.02 電 車 0.001 0.05 0.08. pp v 3: POI 3.4.4 POI Web POI c s POI s i v s i (7) POI 3.4.5 v s i = j c s i j v p j j c s i j s i s j σ i j σ i j (8) (7) σ i j = cos(v s i, v s j ) (8) cos(u, v) cos(u, v) = u v u v (9) 14

3.5 2.4 (2) Pr(s t+1 s t ) (2) s t+1 N(s t, s t+1 ) m i j N(s i, s j ) m i j s i s j s i m i j s j (10) m i j s i m i j s j m i j = σ α ik m k j (10) k α 0 (10) m i j s j s i σ ii = 1 m i j = m i j + σ α ik m k j (11) (11) m i j 1 2 α m k j (k i) α m k j (k i) s i j m i j (11) k i 4 15

4.1 4.1.1 3 0km/h 1 ID 2011 1 12 12 2011 12 7 17172 1 2 4 2.73 1 2500 2000 ユー 1500 ザー 1000 数 500 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 停 車 数 4: 16

4.1.2 POI POI POI ID POI POI ID 2011 2583 POI 860 4.1.3 ID ID ID ID POI li u,pu i H 10 5 4.1.4 3.2 Mean-Shift POI τ bandwidth τ 2 4 bandwidth Mean-Shift bandwidth=0.0003 bandwidth=0.0010 2 0.0001 10m bandwidth 0.0003,0.0010 30m,100m 17

τ Mean-Shift POI τ τ = 0 τ = 5 2 τ c s τ = 0, τ = 5 bandwidth 5 τ = 0 bandwidth τ = 5 bandwidth τ bandwidth τ {0, 5} bandwidth {0.0003, 0.0010} 4 3.3 H 3.4 σ i j POI Web σ 100 Yahoo! 2 2 1 1 1 4 (a),(b),(c),(d) ス ポ ッ ト 数 1800 1600 1400 1200 1000 800 600 400 200 0 τ=0 τ=5 0 0.0005 0.001 0.0015 0.002 bandwidth 5: 18

bandwidth τ (a) 0.0003 0 956 1606 2.53 (b) 0.0003 5 82 554 2.38 (c) 0.0010 0 569 2010 2.57 (d) 0.0010 5 101 963 2.46 1: 4.2 Leave-one-out Leaveone-out U U 1 1 U 1 2 CMC CMC n, 2 s i s i s j m i j s j 3 4 CMC 6 α 0.5,1.0,1.5,2.0,2.5 19

6 m i j α (a),(b),(c) 1.5 (d) 2.0 (d) bandwidth τ (d) α = 2.0 4.3 Web 2 ( ) s i s j d i j σ i j σ i j = 1 λd i j + 1 (12) λ λ = 100 20

0.2 0.18 0.16 0.14 予 測 0.12 成 0.1 功 0.08 率 0.06 提 案 手 法 0.04 マルコフ 0.02 多 項 分 布 0 1 2 3 4 5 6 7 8 9 10 順 位 予 測 成 功 率 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 提 案 手 法 マルコフ 多 項 分 布 1 2 3 4 5 6 7 8 9 10 順 位 (a) bandwidth=0.0003, τ=0 (α=1.5) (b) bandwidth=0.0003, τ=5 (α=1.5) 0.25 0.4 予 測 成 功 率 0.2 0.15 0.1 0.05 0 提 案 手 法 マルコフ 多 項 分 布 1 2 3 4 5 6 7 8 9 10 順 位 予 測 成 功 率 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 提 案 手 法 マルコフ 多 項 分 布 1 2 3 4 5 6 7 8 9 10 順 位 (c) bandwidth=0.0010, τ=0 (α=1.5) (d) bandwidth=0.0010, τ=5 (α=2.0) 6: CMC a s i a s i k u k s i 1 0 σ i j = cos(a s i, a s j ) (13) 2 4.2 7 1 21

1 2 0.2 0.18 0.16 予 0.14 測 0.12 成 0.1 功 0.08 率 0.06 提 案 手 法 0.04 距 離 0.02 停 車 ユーザー 0 1 2 3 4 5 6 7 8 9 10 順 位 (a) bandwidth=0.0003, τ=0 予 測 成 功 率 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 提 案 手 法 距 離 停 車 ユーザー 1 2 3 4 5 6 7 8 9 10 順 位 (b) bandwidth=0.0003, τ=5 7: 4.4 10 2 4 1 1 A B 2 A A B A B 22

bandwidth=0.0003, τ = 5 POI 82 50 τ τ = 8 51 τ = 8 CMC 8 0.7 0.6 予 測 成 功 率 0.5 0.4 0.3 0.2 0.1 0 手 動 マージあり 手 動 マージなし 1 2 3 4 5 6 7 8 9 10 順 位 8: CMC 5 1 23

Web Web CMC 24

[1], :, Proceedings of JSCE, Vol. 625, pp. 53 64 (1999). [2] Ashbrook, D. and Starner, T.: Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, Vol. 7, No. 5, pp. 275 286 (2003). [3],,, :,,LOIS, Vol. 109, No. 450, pp. 55 60 (2010). [4] Bao, J., Zheng, Y. and Mokbel, M. F.: Location-based and Preference-Aware Recommendation Using Sparse Geo-Social Networking Data, ACM SIGSPA- TIAL GIS 2012, pp. 199 208 (2012). [5] Zheng, V. W., Zheng, Y., Xie, X. and Yang, Q.: Collaborative location and activity recommendations with GPS history data, Proceedings of the 19th international conference on World Wide Web, pp. 1029 1038 (2010). [6],, :,,CVIM, pp. 17 23 (2007). [7] Comaniciu, D. and Meer, P.: Mean Shift: A robust approach toward feature space analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, pp. 603 619 (2002). [8] Crandall, D., Backstrom, L., Huttenlocher, D. and Kleinberg, J.: Mapping the World s Photos, Proceedings of the 18th international conference on World Wide Web, pp. 761 770 (2009). [9] Mecab: Yet another part-of-speech and morphological analyzer. http:// mecab.sourceforge.jp. [10] Salton, G. and Buckley, C.: Term-weighting approaches in automatic text retrieval, Information Processing & Management, Vol. 24, No. 5, pp. 513 523 (1988). 25