Transcript Spatio Temporal Rule Mining For LBS

Spatio-temporal Rule Mining:
Issues and Techniques
Győző Gidófalvi
Geomatic ApS
Center for Geoinformatik
and
Torben Bach Pedersen
Aalborg University
16-07-2015
DaWaK 2005
1
Outline
 Why mine spatio-temporal data?
 Frequent pattern mining background
 Frequent itemset mining / association rules
 Sequential patterns
 Taxonomy of spatio-temporal data
 Some examples: STM, HUR, INFATI, DMI
 How to mine spatio-temporal rules?
 Pivoting -> spatio-temporal baskets
 Some examples: INFATI, HUR, DMI
 Mining long, common patterns in trajectories
of moving objects
 Conclusions and future directions
16-07-2015
DaWaK 2005
2
Why Mine Spatio-temporal Data?
 Spatio-temporal data is being collected at enormous
speeds (Tbyte/hour)
 Remote sensors on satellites
 Telescope scanning the skies
 Location data received from mobile devices
 Data needs to be analysed for various purposes
Cataloging, classification, segmentation
Scientific hypothesis formulation
Study complex systems with autonomous mobile entities
Aid the management, storage, and retrieval of spatiotemporal data
 Hidden information in data can be used to provide
customized Location-Based Services (LBS) and LocationBased Advertising (LBA)




16-07-2015
DaWaK 2005
3
Frequent Pattern Mining
 First proposed by Agrawal and Sirkant for the analysis
of customer purchase behaviour
 Frequent itemsets: Discover items are bought together
by customers frequently?
 {bread, peanut butter, jelly}
 Association rules: Discover a possible causal relationship
between the items in such a frequent itemset?
 {bread, peanut butter} -> {jelly} (within trans.)
 Sequential patterns: Discover sequences of items or
itemsets that are frequent in sequences of transactions?
 {Star Wars Episode I} -> {Episode II} -> {Episode
III} (between transactions)
 Episodes: Discover periodic patterns in a long sequence?
 Patterns in other structures: trees, graphs,…
 How do we extend these to the spatio-temporal
domain?
 EX: {Strøget,noon,businessman} -> {cafe}
16-07-2015
DaWaK 2005
4
Frequent Pattern Mining Cont…
 Approaches to frequent itemset mining and association
rules:
 Apriori: bottom-up, generate-and-test frequent itemsets
 BFS traversal of search space
 Pruning using support monotonicity of itemsets
 Projection-based (FP-growth): generate frequent itemset
prefixes and extend the prefix by mining the prefixprojected database
 DFS traversal of search space
 Many other variants employing sophisticates in-memory
data structures and representations of the data.
 Restrictions on frequent itemsets
 Closed frequent itemsets
 Maximal frequent itemsets
16-07-2015
DaWaK 2005
5
Taxonomy of Spatio-temporal Data
 Examples of spatio-temporal data:
 Space Time Man (STM): activities performed by mobile
users at particular times and locations
 HUR1: number of passengers getting on/off busses at
particular times and locations
 HUR2: Personal chip cards recording travels of individuals
 DMI: periodic atmospheric measurements like
temperature, humidity, and pressure for 5 km grid cells
 INFATI: day–to–day movements of 20 private cars on the
road network of Aalborg
 Criteria for categorization of spatio-temporal data:
 Are the measured entities mobile or immobile?
 Are the attribute values of the measured entities static
or dynamic?
16-07-2015
DaWaK 2005
6
How to Mine Spatio-temporal Rules?
 Knowledge extractable by association rules is about
dependencies between items within baskets. -> Need to
construct spatio-temporal baskets.
 Pivoting is the process of grouping a set of records
based on one or more attributes (pivoting attributes)
and assigning the values of an another attribute (pivoted
attribute) to groups or baskets.
 Spatio-temporal rules that can be mined from spatiotemporal baskets can be either implicit or explicit.
16-07-2015
DaWaK 2005
7
Illustration of Pivoting
 INFATI pivoting example: pivoting attributes are
“Location” and “Time”, pivoted attribute is “CarID”
16-07-2015
DaWaK 2005
8
Spatio-temporally Restricted vs. Unrestricted
16-07-2015
DaWaK 2005
9
Explicit Spatio-temporal Rule Mining 1
16-07-2015
DaWaK 2005
10
Explicit Spatio-temporal Rule Mining 2
16-07-2015
DaWaK 2005
11
DMI: Dynamic Attributes of Immobile
Entities
16-07-2015
DaWaK 2005
12
Mining Long, Common Patterns (LCP) in
Trajectories of Moving Objects
 Trajectories of moving objects contain
regularities or patterns
 These patterns can be used in indexing,
tracking, and LBS
 LBS example: intelligent rideshare application
 Find common routes for a set of commuters and
suggest rideshare possibilities to them
 Unique requirements:
 Patterns should rather be long than frequent
 Patterns should be shareable, i.e.: common
 Unique challenges:
 Patterns are extremely long
 Interesting patterns have relatively low support
 Not all sub-patterns are interesting
16-07-2015
DaWaK 2005
13
Method to Mine LCP in Trajectories
 Pre-processing:
 Identify trips, i.e.: gaps
 Map date-time domain to time-of-day domain
 Substitute noisy GPS measurements with spatio-temporal
regions
 Use / exploit unique requirements:
 Prune search space if extractable patterns are doomed to
be short
 Define unique support measure: n-support – # of
transactions satisfying an itemset if the number of distinct
objects associated with those transactions >= n, 0
otherwise
 It can be shown that interesting patterns are closed
frequent itemsets
 In current work, a projection-based FIM algorithm
is being extended to meet and use and meet these
requirements
 Illustrative example:
16-07-2015
DaWaK 2005
14
Pre-processed Example Trajectory
Database
16-07-2015
DaWaK 2005
15
Extracted Long Common Patterns
16-07-2015
DaWaK 2005
16
Conclusions and Future Directions
Today:





Taxonomy of spatio-temporal data
Pivoting to obtain spatio-temporal baskets
Mining explicit and implicit spatio-temporal rules
Spatio-temporally restricted vs. unrestricted mining
Mining long, common patterns in trajectories
Tomorrow:
 Incorporate spatio-temporal indexes in spatio-temporal
rule mining or vice versa
 Incorporate various spatio-temporal space partitioning
methods into mining
16-07-2015
DaWaK 2005
17
Thank you for your attention!
Questions?
16-07-2015
DaWaK 2005
18