Individual Life Patterns through Location History Mining
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
Background
2
•
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
Motivation
•
Human location history
•
does not only represent an individual’s life regularity
•
but also imply the tastes/preferences of a person
3
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
Challenges
5
•
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
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
1:
Modeling Location History
•
GPS logs
P
and GPS trajectory
•
Stay points
S
={s1
, s
2
,…, s
n
}.
•
Stands for a geo-region where a user has stayed for a while
•
Carry a semantic meaning beyond a raw GPS point
1:
Modeling Location History
•
Location history:
•
represented by a sequence of stay points
•
with transition intervals
8
Day 1: S1
S2
S3
S4
Day 2: S4
S5
S7
S7
Day 3: S7
S8
S9
S10
1:
Modeling Location History
•
Considering the scale of a location
9
S1
S7
C1
C2
C3
C4
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
10
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
.
11
S1
S2
S3
S4
S5
S6
S7
S8
S9
S10
A
B
2: The Paradigm of Life Pattern
12
•
Location dimension: City, Community, Restaurants
•
Time dimension: Year, Month, Week, Day
2: The Paradigm of Life Pattern
•
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
3: The Framework for Life Pattern Mining
14
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
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
3: The Framework for Life Pattern Mining
•
Mining conditional life patterns
•
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
Experiements
•
60 Devices and 138 users
•
From May 2007 ~ present
18
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
Experiments
•
The predictability of life patterns
20
Experiment
•
A case study on non-conditioned patterns
•
One-year GPS logs of each volunteer
21
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.
22
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
Thanks!
yuzheng@microsoft.com
24
© 2006 Microsoft Corporation. All rights reserved. Microsoft, Windows, Windows Vista and other product names are or may be registered trademarks and/or trademarks in the U.S. and/or other countries.
The information herein is for informational purposes only and represents the current view of Microsoft Corporation as of the date of this presentation. Because Microsoft must respond to changing market conditions, it should not be interpreted to be a commitment on the part of Microsoft, and Microsoft cannot guarantee the accuracy of any information provided after the date of this presentation.
MICROSOFT MAKES NO WARRANTIES, EXPRESS, IMPLIED OR STATUTORY, AS TO THE INFORMATION IN THIS PRESENTATION.
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Thanks! yuzheng@microsoft.com 24
