Understanding Individual Life Patterns through Location History Mining

GPS-enabled devices have made it possible to track human location history, offering insight into individual behaviors and preferences. This paradigm explores modeling techniques, challenges, and motivations for mining location data to predict and personalize user experiences. The framework presented aims to extract valuable insights from location patterns for applications like context-aware computing and personalized recommendations.

• Location History
• Data Mining
• Personalization
• GPS Trajectories
• Behavior Prediction

azam_in Follow

Uploaded on Oct 02, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Mining Individual Life Pattern Based on Location History: A Paradigm and Framework Yu Zheng @ Microsoft Research Asia On behalf of Ye Yang March 16, 2009

2. Background GPS-enabled devices have become prevalent These devices enable us to record our location history with GPS trajectories Human location history is a big cake given the large number of GPS phones 2

3. Motivation Human location history does not only represent an individual s life regularity but also imply the tastes/preferences of a person University Movie center Super- market Microsoft 3

4. Motivation An individual s life pattern can be used to model and predict a person s behaviors/preferences and enable valuable applications context-aware computing personalized recommendation 4

5. Challenges How to model an individual s location history Life Pattern could have multiple representation/definitions E.g., John typically leaves home at 8:30 am E.g., Matt usually goes to a cinema once a month E.g., Marry goes shopping after visiting a Starbucks Different applications need different patterns Many mining algorithms Duplicated effort 5

6. What we do Propose a model representing an individual s location history Define the paradigm of individual life patterns Present a framework for mining individual life pattern 6

7. 1:Modeling 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

8. 1:Modeling Location History ?1 ?2 ?2 , , ?? 1 ??) Location history: represented by a sequence of stay points with transition intervals ???? = (?1 Day 1: S1 S2 S3 S4 Restaurant Day 2: S4 S5 S7 S7 C4 S9 S6 Day 3: S7 S8 S9 S10 S10 S7 S8 S1 Day 1: C1 C3 C2 C1 Home S2 S5 S4 Company Day 2: C1 C2 C4 C1 C3 C1 C2 Day 3: C1 C3 C4 C3 S3 Supermarket 8

9. 1:Modeling Location History B A Considering the scale of a location C3 C4 C2 C1 S1 S4 S7 S5 S3 S2 S8 S10 S6 S9 Restaurant Day 1: C1 C3 C2 C1 A C4 S9 S6 Day 2: C1 C2 C4 C1 S10 S7 S8 Day 3: C1 C3 C4 C3 S1 Home S2 S5 C3 C1 S4 Day 1: A B A A Company B C2 Day 2: A A B A S3 Supermarket Day 3: A B B B 9

10. 1:Modeling Location History Build a tree using a hierarchical clustering algorithm Each node represents a cluster of stay points Different levels denote different geospatial granularity City n City i City 1 Community A Community B Restaurant Company Supermarket Home 10

11. 1:Modeling Location History An individual s location history can be represented by a sequence of stay point clusters with transition time between two clusters on different geospatial scales. A S9 S6 S10 S7 Day 1: A B A A Day 2: A A B A Day 3: A B B B S8 S1 S2 S4 S5 B S3 C4 Restaurant S9 S6 Day 1: C1 C3 C2 C1 Day 2: C1 C2 C4 C1 Day 3: C1 C3 C4 C3 Company S10 S7 S8 S1 S2 Home S5 S4 C3 C1 Day 1: S1 S2 S3 S4 Day 2: S4 S5 S7 S7 Day 3: S7 S8 S9 S10 C2 S3 Supermarket 11

12. 2: The Paradigm of Life Pattern Life Pattern P ? = ?? ??? Non-Conditional Life Pattern Pnc Conditional Life Pattern Pc ??? = ?? ??? 1| ??? 2 ?? = ??? Sequential Life Pattern PS Non-Sequential Life Pattern Pns Life Associate Rule Pnc Pnc 1 2 Location dimension: City, Community, Restaurants Time dimension: Year, Month, Week, Day 12

13. 2: The Paradigm of Life Pattern ? = ????? ? .(???? ?1,?2.(????? ?1,?2 Atomic life pattern E.g., Marry typically arrives at the Starbucks between 2 and 3 pm. E.g., Marry typically stays in the Starbucks for 1 to 1.5 hours E.g., Marry typically arrives at the Starbucks between 2 and 3 pm, and stays there for 1 to 1.5 hours ??? = ? (??? ?) Non-sequential life pattern E.g., Typically, Marry leaves home around 9 am. E.g., Typically, Marry leaves around 9 am and comes back around 7 pm ?? = ? (?? ?) Sequential life pattern E.g., John usually goes to a Starbucks caf after shopping in a Outlets (Outlets Starbucks) E.g., John usually visits Outlets Starbucks restaurants 13

14. 3: The Framework for Life Pattern Mining Modeling Location History Modeling Location History Modeling Location History Modeling Location History Stay Point Stay Point GPS GPS GPS GPS Log Log Log Log Stay Points Stay Points Stay Points Stay Point Stay Point Stay Point GPS GPS GPS Log Log Log Stay Point Stay Points Clustering Clustering Clustering Clustering Stay Point Sequences Sequences Sequences Sequences Stay Point Detection Detection Detection Detection GPS Traces Traces Traces Traces Log Parsing Parsing Parsing Parsing Mining Non-Conditioned Life Patterns Mining Non-Conditioned Life Patterns Mining Non-Conditioned Life Patterns Mining Non-Conditioned Life Patterns Mining Atomic Life Patterns Mining Atomic Life Patterns Mining Atomic Life Patterns Mining Atomic Life Patterns Atomic Patterns Atomic Patterns Atomic Patterns Atomic Patterns Location History Location History Location History Location History Atomic Pattern Atomic Pattern Atomic Pattern Frequent Frequent Frequent Atomic Pattern Combination Combination Combination Combination Frequent Sequence Mining Sequence Mining Sequence Mining Sequence Mining Temporal Sampling Temporal Sampling Temporal Sampling Time Time Time Temporal Sampling and Partition and Partition and Partition and Partition Time Condition Condition Condition Condition Non- Non- Non- Non- Sequential Patterns Patterns Patterns Sequential Sequential Sequential Sequential Patterns Patterns Patterns Patterns Sequential Sequential Sequential Patterns Location Location Condition Location Location Condition Condition Condition Location Selection Location Selection Location Selection Location Selection Mining Conditioned Life Patterns Mining Conditioned Life Patterns Mining Conditioned Life Patterns Mining Conditioned Life Patterns Life Sequence Dataset Life Sequence Dataset Life Sequence Dataset Life Sequence Dataset Conditioned Patterns Conditioned Patterns Conditioned Patterns Conditioned Patterns Mining Atomic Life Pattern Mining Atomic Life Pattern Mining Atomic Life Pattern Mining Atomic Life Pattern Mining Conditioned Life Patterns Mining Conditioned Life Patterns Mining Conditioned Life Patterns Mining Conditioned Life Patterns 14

15. 3: The Framework for Life Pattern Mining Mining Atomic life patterns A user need to specify the geo-region that interest them (location condition) the time span and/or temporal type they concern (Temporal condition) A suggested support value (S) E.g., show me my life patterns about Sigma building in the weekends of the last year E.g., show me my life patterns on Friday during 2008 in Beijing Algorithms like FP-growth, MAFIA, CHARM and Closet+ can be used here Possible results 1. In the last year, you typically arrive at Sigma around 10~11 am, and stay 4-6 hours; you visited Sigma building every two weekends. 2. In 2008, you went to Xidan once a month. you visit there in the evening. Typically, you spent 2-3 hours in Xidan; you went to a Movie center every three weeks. 15

16. 3: The Framework for Life Pattern Mining Mining non-conditioned life patterns based on atomic patterns Combine atomic patterns E.g., In the last year, you went to Xidan once a month; in most case, you visited there in the evening of weekend and spent 2-3 hours there. Mining sequential life patterns Algorithms like CloSpan, etc. E.g., In 2008, you typically travel to Xidan from Sigma building in the weekend. More specifically, you usually leave Sigam building around 7 pm and spent 30 to 50 minutes on the way. 30-50min Sigma building ----------------> Xidan 16

17. 3: The Framework for Life Pattern Mining Mining conditional life patterns 1 ??? Pr ??? 2 2] =Pr ??? 1| ??? Pr[??? 2 One or two conditions would be more useful E.g., typically, you will go to Zhongguanchun movie center if you leave Sigma building before 4 pm in weekends. If you leave Sigma building after 7 pm in the weekends, you usually visit Xidan. If stayed in Xidan more than 3 hours, you went to a Thai-food restaurant. 17

18. Experiements 60 Devices and 138 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% 18

19. Experiments Select 10 volunteers out of the 138 users Partition their location histories into two parts Mine patterns separately Investigate the predictability of the detected life patterns 19

20. Experiments The predictability of life patterns 1 0.95 0.9 Predicability Sequential 0.85 NonSequenti al 0.8 0.75 0.7 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Support 20

21. Experiment A case study on non-conditioned patterns One-year GPS logs of each volunteer 5 5 4 4 Mean Score Mean Score 3 3 Interesting Representative Intersting 2 2 Representative 1 1 0 0 All Days Workdays Holidays Day Week Month 21

22. Experiments A case study on conditioned patterns Condition 1:not visiting the most frequent place; Condition 2: visiting the second frequent place; Condition 3: visiting the second frequent place while not visiting the most frequent place. 5 4 Mean Score 3 Interesting 2 Representative 1 0 Cond. 1 Cond. 2 Cond. 3 22

23. Conclusion Propose a model representing an individual s location history Define the paradigm of individual life patterns Present a framework for mining individual life pattern 23

24. Thanks! yuzheng@microsoft.com 24