Correlation Between Locations from GPS Trajectories
Explore how GPS trajectories can reveal correlations between different locations based on human behavior, enabling the development of a location recommendation system. Challenges such as sequence dependency and user experiences are discussed alongside the methodology for modeling human location history to infer correlations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Learning Location Correlation From GPS Trajectories Yu Zheng Microsoft Research Asia March 16, 2010
Background Locations are correlated in the space of human behavior These location might not belong to the same business categories They would not be co-located Jewel shop C Jewel shop B Far away Far away Far away Cafe Cinema Different categories Jewel shop A 2
What We Do Mine the correlation between locations from GPS trajectories The relation between locations in the space of human behavior Enable a location recommendation system 3
Challenges The correlation between locations depends on Sequence between locations being visited The travel experience (knowledge) of a user accessing these locations u1 u2 u3 Trip1 Trip2 B A C B C A B u1 u2 u3 Trip1 Trip2 Trip3 Trip3 Could be random access u1 u2 u3 A B A B C C A C B A C Trip1 Trip2 Trip3 A B C A C B B A C 0 0 1 2 1 2 0 0 0 0 1 2 1 2 1 2 1 2 e.g., One-way, accessibility 0 1 2 0 0 Tourist 1 2 1 2 u1 u2 u3 Trip1 Trip2 Trip3 A B C D A B C A C B B A C 0 3 1 2 0 1 2 0 0 1 2 1 2 Cor(A, B)>Cor(A, C)>Cor(A,D) Local expert CorExpert(A, B)>CorTourist(A, B) 4
Methodology Modeling human location history Inferring user experiences Computing location correlation Personalized location recommender 5
Solution Step 1:Modeling human location history GPS logs P and GPS trajectory A Stay Point S Latitude, Longitude, Time p1: Lat1, Lngt1, T1 p2: Lat2, Lngt2, T2 ... pn: Latn, Lngtn, Tn p6 p1 p3 p7 p2 p5 p4 Stay points S={s1, s2, , sn}. Stands for a geo-region where a user has stayed for a while Carry a semantic meaning beyond a raw GPS point Location history: represented by a sequence of stay points with transition intervals ?1 ?2 ?2 , , ?? 1 ??) ???? = (?1
GPS Logs of User i GPS Logs of User 2 GPS Logs of User 1 GPS Logs of User i+1 GPS Logs of User n-1 GPS Logs of User n 1. Stay point detection 2. Hierarchical clustering 3.Graph Building l1 c10 {C } G1 High c20 c21 c21 l2 c20 c31 c30 c32 c33 c34 G2 Low l3 c33 c30 c32 Stands for a stay point S Stands for a stay point cluster cij c34 G3 c31 Shared Hierarchical Framework
Solution 2. Infer a users experience Mutual reinforcement relationship A user with rich travel knowledge are more likely to visit more interesting locations A interesting location would be accessed by many users with rich travel knowledge A HITS-based inference model Users are hub nodes Locations are authority nodes Topic is the geo-region 8
Users: Hub nodes The HITS-based inference model Locations: Authority nodes 9
Solution 3.Mining the location correlation The correlation between locations can be represented by the sum of the experiences of the users taking this sequence ??? ?,? = ? ?? ?? ? u1 u2 u3 Trip1 Trip2 Trip3 A B C A C B B A C 0 1 2 0 0 1 2 1 2 ??? ?,? =1 Trip 1: ??? ?,? = ?1 ??? ?,? = ?1 2 ?1 2 ?2 2 ?3 ??? ?,? = ?1+1 2 ?2 ??? ?,? =1 Trip 2: ??? ?,? = ?2 ??? ?,? = ?3,??? ?,? = ?3,??? ?,? =1 ??? ?,? = ?2 ??? ?,? =1 2 ?1+ ?2+ ?3 ??? ?,? = ?3,??? ?,? = ?3,??? ?,? =1 ??? ?,? = ?3,??? ?,? = ?3,??? ?,? =1 Trip 3: 2 ?3 2 ?3 10
Personalized Recommendation Integrate the location correlation into a CF model User-location matrix Slope-One: an item-based CF model ??? Slope-One model (????,?+???) |??,?(?)| ? ? ?? ? ? ?0?1?2?3?4 1 1 0 1 1 2 0 0 1 0 0 0 ? ???= |??,?(?)| ?0 ?1 ?2 ?3 ? ? ?? ? ? 0 0 0 1 0 0 2 1 ? = Our method (????,?+ ???) ??? ? ? ?? ? ? ? ???= ??? ? ? ?? ? ? 11
Experimental Settings 60 Devices and 136 users From May 2007 ~ present Microsoft emplyees Employees of other companies Government staff Colleage students age<=22 26<=age<29 22<age<=25 age>=30 9% 16% 18% 30% 14% 58% 45% 10% 12
A large-scale GPS dataset (by Feb. 18, 2009) 10+ million GPS points 260+ million kilometers 36 cities in China and a few city in the USA, Korea and Japan
Results Effectiveness Perform a user study-based evaluation Metric: NDCG & MAP More effective than the slop-one-based method Same performance with the Pearson correlation-based CF The Pearson Correlation- Based CF model The Weighted Slope One Algorithm Ours 0.840 0.862 0.762 NDCG@5 0.922 0.938 0.891 NDCG@10 0.798 0.804 0.665 MAP 14
Results Efficiency Faster than the Pearson-based one Almost have the same efficiency as the slop one Computing Complexity (E+04) Computing Times Per Perdiction 40 35 30 25 20 15 10 5 0 The Pearson Correlation-Based Model The Weighted Slope One Algorithm Ours (Experience + Sequentiality) Ours (Sequentiality) Methods 15
Conclusion The correlation between locations in the space of human behavior Sequence property User experience Conduct a personalized location recommender based on the correlation The recommender is Efficient than the Pearson correlation-based method and Effective than the slop one based approach 16
Thanks! yuzheng@microsoft.com 17
