Web [1] [2] Web [3], [4] *2 [5] Crandall [6] [7] [8] Crandall [9] [10] [11] Crandall χ 2 [12] [13] Naaman [14] Flickr 6

Transcription

1 1,a) 2,b) 1,c) 1,d) , Flickr Extracting Hot Photo-spots from Geotagged Photographs with Timestamps Masahito Kumano 1,a) Motonori Koseki 2,b) Keiko Ono 1,c) Masahiro Kimura 1,d) Received: February 2, 2012, Revised: March 23, 2012, Accepted: April 18, 2012 Abstract: Discovering good photo-spots in the real world is an important problem from the point of view of sightseeing industry. While a popular photo-spot in general means a spatially localized region, it should have its own hot-period, a period of time during which it can provide more interesting photographs than other photo-spots. In this paper, we address the problem of extracting a pair of a major photo-spot and its hot-period, which is called a hot photo-spot, from a large number of geotagged photographs with timestamps that many people have taken. We propose a mathematical model for hot photo-spots, and present a method of efficiently identifying them. Using synthetic and real Flickr data, we experimentally demonstrate the effectiveness of the proposed method. Keywords: hot photo-spots extraction, kernel density estimation, anomaly detection, spatiotemporal mining, social media mining 1 Department of Electronics and Informatics, Faculty of Science and Technology, Ryukoku University, Otsu, Shiga , Japan 2 Division of Electronics and Informatics, Graduate School of Science and Technology, Ryukoku University, Otsu, Shiga , Japan a) kumano@rins.ryukoku.ac.jp b) t12m023@mail.ryukoku.ac.jp c) kono@rins.ryukoku.ac.jp d) kimura@rins.ryukoku.ac.jp 1. Flickr *1 Web *1 c 2012 Information Processing Society of Japan 41

2 Web [1] [2] Web [3], [4] *2 [5] Crandall [6] [7] [8] Crandall [9] [10] [11] Crandall χ 2 [12] [13] Naaman [14] Flickr T T [1,T] D T = {d n ; n =1,,N} d n x n t n *2 6.1 d n =(x n,t n ), (n =1,,N) c 2012 Information Processing Society of Japan 42

3 x n =(x n,1,x n,2 ) x n,1 x n,2 d n t n d n N Flickr *3 2 Euclid R 2 Ω = [ π/2,π/2] [ π, π] ( R 2) D T R k Ω k =1,,K I k =[T k,0,t k,1 ] k =1,,K R k I k R k K R k h 0 Ω 1 T k,0 <T k,1 T k =1,,K h 0 > 0 R k I k (R k,i k ) T D T {(R k,i k ); k =1,,K} R k I k D k = {d n =(x n,t n ) D T ; x n R k,t n I k }, (k =1,,K) D k R k 3. T D T = {d n = (x n,t n ); n =1,,N} {(R k,i k ); k = 1,,K} R k k =1,,K I k k =1,,K 3.1 D T R k k =1,,K *3 ˆp(x) = 1 Nh 2 N n=1 ( G (x x n ) /h 2), ( x R 2 ) (1) R 2 Euclid G(s) Epanechnikov Gaussian h > 0 *4 Crandall [6] D T x n n =1,,N (1) ˆp(x) D T ˆp(x) {ĉ k ; k =1,,K } k ĉ k x n n =1,,N X k = {x n(k,j) ; j =1,,N k }, (k =1,,K ) X 1 X K X k μ 0 k {1,,K } K μ 0 k {1,,K} ĉ k X k Ω R k {R 1,,R K } 3.2 R k I k =[T k,0,t k,1 ] T k,0 T k,1 T k,0 <T k,1 T k {1,,K} q k (t) R k t q k (t) q k (t) =q k(t)+q 0 (t) (2) q 0 (t) k t q k (t) R k k w k,0 I k w k,0 R k I k I k,1,i k,2, 2 k k R k R k *4 6.4 c 2012 Information Processing Society of Japan 43

4 J = {J =[T 0,T 1 ]; T 0,T 1 Z, 1 T 0 <T 1 T } J = {J i ; i =1,,T(T 1)/2} R k R k k =1,,K J i i =1,,T(T 1)/2 Fisher R k Fisher J R k Fisher Fisher R k R k Fisher R k k = 1,,K J i i =1,,T(T 1)/2 1 R k J i 2 2 N m k R k m i J i m k,i R k J i m R k,ī k J i R m k,i k J i m k,ī R k J i m k,i + m k,ī = m k, m k,i + m k,ī = N m k, m k,i + m k,i = m i, m k,ī + m k,ī = N m i Fisher Fisher ( )( ) m k N m k F k,i = min(m k,m i ) j=m k,i j m i ( ) j (3) N R k J i R k m k,i φ k J i Fisher F k,i I k,1,i k,2, I k,1 Table 1 1 J i m i contingency table. R k m k,i m k,ī m k R k m k,i m k,ī N m k m i N m i N Ji R k 1 I k,2 R k 2 φ k > 0 Fisher F k,i k =1,,K; i =1,,T(T 1)/2 (3) N T ( ) l f(l, j) =log, (l =1,,N; j =0, 1,,l) j 0 (j =0) f(l, j) = f(l, j 1) + log(l j+1) log(j) (j 1) (4) Fisher F k,i F k,i = min(m k,m i ) j=m k,i exp(f(m k,j)+f(n m k,m i j) f(n,m i)) (5) (5) f(l, j) R k Algorithm 1: i := 1; 2: while(i T (T 1)/2) do /* J i F k,i */ 3: R k J i ; 4: if m k,i <φ k then 5: goto step8; 6: end if 7: F k,i (3) ; 8: i := i +1; 9: end while 10: F k,i J i R k I k,1,i k,2, ; Algorithm 1: m k ; 2: (4) {f(m k,i); 1 i m k } {f(n m k,i); 1 i N m k } {f(n,i); 1 i N} ; 3: i := 1; c 2012 Information Processing Society of Japan 44

5 4: while(i T (T 1)/2) do /* J i F k,i */ 5: R k J i ; 6: if m k,i <φ k then 7: goto step10; 8: end if 9: (5) F k,i ; 10: i := i +1; 11: end while 12: F k,i J i R k I k,1,i k,2, ; Fisher F k,i (R k,j i ) T D T 4. R k k =1,,K R k 1 I k 4.1 R k t q k (t) (2) qk (t) qk(t) w, t I k =[Tk,0 =,T k,1 ], (6) 0, otherwise, T k,0 T k,1 1 T k,0 <T k,1 T T k,1 = T k,0 + τ R k I k =[T k,0,t k,1 ] k τ w w k,0 k w k,0 =0 *5 q 0 (t) *5 τ w w k,0 k Binomial(100, 1), t [T 0 q 0 (t),t 1 ], Binomial(100, 0.1), otherwise. (7) Binomial(n b,p b ) n b p b T 0 T 1 1 T 0 <T 1 T 4.2 k I k =[Tk,0,T k,1 ] [ ˆT k,0, ˆT k,1 ] E = 1 2K K ( T k,0 ˆT T k,0 + k,1 ˆT ) k,1 k=1 R k [T 0,T 1 ] R k [T 0,T 1 ] T = 100 K =10 T 0 =5 T 1 =10 T k,0 R k [T 0,T 1 ] w 5 w 25 τ [1, 100] τ =5 τ = w w 10 I k =[Tk,0,T k,1 ] t 1 q k (t 1 ) I k t 0 q k (t 0 ) (2) (6) (7) w =5 q k (t 1 ) q k (t 0 ) w =10 q k (t 1 ) q k (t 0 ) 2 w q k (t 1 ) q k (t 0 ) 1(a) 1(b) w E 1(a) 1(b) w w =5 τ τ =5 τ τ =15 τ c 2012 Information Processing Society of Japan 45

6 (a) τ =5 τ = T/10 q 0 (t) Binomial(100, 0.1) t [1,T] 100 N = K(wT/ T 2 ) CPU Intel corei7 980X 3.33 GHz 6GB Memory PC T 5. Flickr (b) τ =15 1 Fig. 1 Estimation errors of hot-periods. 2 Fig. 2 Comparison of the proposed and the naive methods in processing time. w w 15 τ τ =5 τ τ =15 τ R k T K =10 w = Flickr ,922 3 (a) 3(b) 0 3 { [10 0, 10 1 ) [10 1, 10 2 ) [10 2, 10 5 ) } 3 * u m Crandall [6] Yin [7] *6 6.2 c 2012 Information Processing Society of Japan 46

7 (a) Map around Japan h R k 1 1 u 10 m 162,933 Flickr dataset Flickr dataset (b) Geographic locations of photographs 3 Flickr Fig. 3 Geographic locations of photographs in the Flickr dataset. 4 Flickr 1 Fig. 4 Daily fluctuation of the number of photographs in the Flickr dataset. 1 Crandall Yin h Crandall metropolitanscale 100 km landmark-scale 100 m Crandall landmark-scale h = 100 m G(s) Epanechnikov K =24,954 R k μ 0 = 100 K = c 2012 Information Processing Society of Japan 47

8 2 Top 10 Table 2 Hot photo-spots extracted by the proposed method (Top 10). Rank , /2 4/ , /31 4/ , /8 4/ , /17 10/ , /3 11/ , /20 11/ , /23 7/ , /3 4/ , /2 10/ , /11 4/ Top 10 Table 3 Photo-spots extracted by the comparison method (Top 10). Rank , /1 12/ , , /1 12/ , , /1 12/ , , /1 12/ , /3 12/ , /2 12/ , /2 12/ , /1 12/ , /3 12/ , /1 12/ Fig. 5 Daily fluctuations of the numbers of photographs in the top 10 hot photo-spots by the proposed method Rank 1 Rank Rank 5 c 2012 Information Processing Society of Japan 48

9 Fig Daily fluctuations of the numbers of photographs in the top 10 by the comparison method Fig. 7 Example of the photographs in the hot photo-spot of rank 1 extracted by the proposed method (Daigoji temple) Rank 1 Rank 2 Rank 10 8 Rank Rank c 2012 Information Processing Society of Japan 49

10 Fig. 8 8 Examples of the hot spot photographs in the other hot photo-spots extracted by the proposed method. Rank Levy Collective Intelligence [15] Web Wikipedia Surowiecki Wisdom of Crowds [16] Flickr 2 1 GPS GPS Flickr 2 Flickr 2 c 2012 Information Processing Society of Japan 50

11 Flickr dataset 548,922 20,000 8 GPS Flickr dataset /31 4/7 9 I k 6.4 h Fig. 9 Time fluctuation of the number of photographs in a hot photo-spot extracted by the proposed method. 5.2 h 100 m h h h 1 km h h h 1 R k R k h c 2012 Information Processing Society of Japan 51

12 6.6 Kleinberg [17] Naaman [14] 7. JSPS [1] Vol.51, No.7, pp (2010). [2] Sakaki, T., Okazaki, M. and Matsuo, Y.: Earthquake Shakes Twitter Users: Real-time Event Detection by Social Sensors, Proc. 18th International Conference on World Wide Web, pp (2010). [3] Vol.51, No.6, pp (2010). [4] Vol.26, No.3, p.225 (2011). [5] Vol.51, No.7, pp (2010). [6] Crandall, D.J., Backstrom, L., Huttenlocher, D. and Kleinberg, J.: Mapping the world s photos, Proc. 18th International Conference on World Wide Web, pp (2009). [7] Yin, Z., Cao, L., Han, J., Zhai, C. and Huang, T.: Geographical Topic Discovery and Comparison, Proc. 20th International Conference on World Wide Web, pp (2011). [8] Web Vol.52, No.12, pp (2011). [9] Arase, Y., Xie, X., Hara, T. and Nishio, S.: Mining People s Trips from Large Scale Geo-tagged Photos, Proc. 18th International Conference on Multimedea, pp (2010). [10] Yin, H., Lu, X., Wang, C., Yu, N. and Zhang, L.: Photo2Trip: An interactive trip planning system based on geo-tagged photos, Proc. 18th International Conference on Multimedea, pp (2010). [11] Lu, X., Wang, C., Yang, J.-M., Pang, Y. and Zhang, L.: Photo2Trip: Generating travel routes from geo-tagged photos for trip planning, Proc. 18th International Conference on Multimedea, pp (2010). [12] Swan, R. and Allan, J.: Automatic generation of overview timelines, Proc. 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp (2000). [13] Vol.23, No.5, pp (2008). [14] Naaman, M., Song, Y.J., Paepcke, A. and Garcia-Molina, H.: Automatic Organization for Digital Photographs with Geographic Coordinates, Proc. ACM/ IEEE-CS JCDL Joint Conference on Digital Libraries, pp (2004). [15] Levy, P.: Collective Intelligence: Mankind s Emerging World in Cyberspace, Basic Books (1999). [16] Surowiecki, J.: The Wisdom of Crowds: Why the Many Are Smarter Than the Few and How Collective Wisdom Shapes Business, Economies, Societies and Nations, Doubleday (2004). [17] Kleinberg, J.: Bursty and hierarchical structure in streams, Proc. 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp (2002) IEEE-CS ACM c 2012 Information Processing Society of Japan 52

13 NTT c 2012 Information Processing Society of Japan 53