Transcript Spatio Temporal Rule Mining For LBS

Mining Long, Sharable Patterns in
Trajectories of Moving Objects
Győző Gidófalvi
Geomatic ApS
Center for Geoinformatik
and
Torben Bach Pedersen
Aalborg University
18-07-2015
STDBM 2006, Seoul, South Korea
1
Outline
 Why mine trajectories of moving objects?
 From spatio-temporal data to spatio-temporal
baskets: pivoting
 From trajectories to transactions in 3 steps
 Method for mining long, sharable patterns
 Observations and associated steps
 Experiments
 Conclusions and future directions
18-07-2015
STDBM 2006, Seoul, South Korea
2
Outline
 Why mine trajectories of moving objects?
 From spatio-temporal data to spatio-temporal
baskets: pivoting
 From trajectories to transactions in 3 steps
 Method for mining long, sharable patterns
 Observations and associated steps
 Experiments
 Conclusions and future directions
18-07-2015
STDBM 2006, Seoul, South Korea
3
Outline
 Why mine trajectories of moving objects?
 From spatio-temporal data to spatio-temporal
baskets: pivoting
 From trajectories to transactions in 3 steps
 Method for mining long, sharable patterns
 Observations and associated steps
 Experiments
 Conclusions and future directions
18-07-2015
STDBM 2006, Seoul, South Korea
4
Outline
 Why mine trajectories of moving objects?
 From spatio-temporal data to spatio-temporal
baskets: pivoting
 From trajectories to transactions in 3 steps
 Method for mining long, sharable patterns
 Observations and associated steps
 Experiments
 Conclusions and future directions
18-07-2015
STDBM 2006, Seoul, South Korea
5
Outline
 Why mine trajectories of moving objects?
 From spatio-temporal data to spatio-temporal
baskets: pivoting
 From trajectories to transactions in 3 steps
 Method for mining long, sharable patterns
 Observations and associated steps
 Experiments
 Conclusions and future directions
18-07-2015
STDBM 2006, Seoul, South Korea
6
Outline
 Why mine trajectories of moving objects?
 From spatio-temporal data to spatio-temporal
baskets: pivoting
 From trajectories to transactions in 3 steps
 Method for mining long, sharable patterns
 Observations and associated steps
 Experiments
 Conclusions and future directions
18-07-2015
STDBM 2006, Seoul, South Korea
7
Why mine trajectories of moving objects?
 Large amounts of location data from mobile devices
 Locations data is interesting as a sequence
 Extracting patterns in
trajectories can:
 aid the management,
storage, and retrieval of
trajectories

improve tracking of
moving objects

be used to provide
customized LocationBased Services (LBS)
and Location-Based
Advertising (LBA)
18-07-2015
STDBM 2006, Seoul, South Korea
8
From spatio-temporal data to spatio-temporal
baskets: pivoting
 Pivoting is the process of grouping a
set of records based on one or more
attributes (pivoting attributes) and
assigning the values of one of more
different attributes (pivoted attributes)
to groups or baskets.
 Frequent itemset mining to
discover relationships between items
in the basket [AGR94]
pivoting
attribute
ObjectID LocationID
1
A
1
B
1
C
1
B
1
A
2
A
2
B
2
C
2
D
2
C
2
B
2
A
spatio-temporal item
ObjectID
1
2
18-07-2015
pivoted
attributes
Time
8:00
8:05
8:10
8:15
8:20
8:00
8:05
8:10
8:15
8:20
8:25
8:30
pivoting
Spatio-temporal basket
A_8:00, B_8:05, C_8:10, B_8:15, A_8:20
A_8:00, B_8:05, C_8:10, D_8:15, C_8:20, B_8:25, A_8:30
STDBM 2006, Seoul, South Korea
9
From trajectories to transactions in 3 steps
 STEP I: Identify trips
 a trip ends when the total
displacement in k consecutive GPS
readings is less than δ
 STEP II: Capture periodicity of
patterns
 Map date-time domain to time-ofday domain
 STEP III: Eliminate the problem
of noisy GPS readings
 Substitute readings with spatiotemporal regions
18-07-2015
STDBM 2006, Seoul, South Korea
10
Mining long, sharable patterns (LSP)
LBS example application: intelligent ridesharing
 Find sharable 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
 Unique challenges:
 Patterns are extremely long
 Interesting patterns have relatively low support
 Not all sub-patterns are interesting
18-07-2015
STDBM 2006, Seoul, South Korea
11
Sample trajectory database
Task: Find all patterns that have at least length 4, are parts of at
least 4 trajectories, which belong to at least 2 distinct objects
(shareable / common)
18-07-2015
STDBM 2006, Seoul, South Korea
12
Filter infrequent itemsets
 Observation: Infrequent items cannot be part of a pattern
 DEF: An item is frequent if the number of transactions that contain
that item >= MinSupp (for example 4), and the number of unique
objects associated with those transactions >= n (for example 2).
 STEP 1: Delete all infrequent items
infrequent items
18-07-2015
STDBM 2006, Seoul, South Korea
13
Filter short transactions
 Observation: A short transaction can never support a long pattern
 DEF: A transaction is short if the number of items in it is less than
or equal to MinLength (for example 4).
 STEP 2: Delete all short transactions
short transactions
18-07-2015
STDBM 2006, Seoul, South Korea
14
Project DB based on item with least n-support
 Observation: All patterns that a given item i participates in can be
found in the item-projected DB, T_i.
 DEF: An item-projected DB, T_i, contains all the items from the
transactions containing item i.
 STEP 3: Project DB based on the item with the least n-support
Projecting item with least n-support
18-07-2015
STDBM 2006, Seoul, South Korea
15
Find the single most frequent itemset in the
projected DB
 Observation: There is a single most frequent itemset in a projected
DB, and its support is equal to the support of the projecting item
 STEP 4: Identify single most frequent itemset
projecting item
Closed Frequent Itemset
n-support in
projected DB
18-07-2015
STDBM 2006, Seoul, South Korea
16
Delete unnecessary items from predecessor DB
 Observation: Items that have the same support in the item projected
DB as the projected DB, can be deleted from the later.
 STEP 5: Delete unnecessary items from predecessor DB
Unnecessary items
support in predecessor DB
support in projected DB
18-07-2015
STDBM 2006, Seoul, South Korea
17
Pseudo code for complete LCP mining
 Recursive, projection-based LCP mining
1.
2.
3.
4.
5.
Filter infrequent items
Filter short transactions
Project DB based on item with least n-support
Find the single most frequent itemset in the projected DB
Recursively mine the projected DB by further projecting
on frequent items that are not part of the single most
frequent itemset
6. Delete unnecessary items from predecessor DB
18-07-2015
STDBM 2006, Seoul, South Korea
18
Extracted long sharable patterns
18-07-2015
STDBM 2006, Seoul, South Korea
19
Experimental setup & performance results


INFATI data: 20 cars driving in Aalborg for 2 month, 1.8 million GPS
readings, 3699 trips
LCP implemented on MS-SQL, running on 3.6 GHz, 2GB RAM
Minimum
length
experiments
Minimum
support
experiments
18-07-2015
STDBM 2006, Seoul, South Korea
20
Visualization of extracted patterns



Large amount of spatio-temporal data
Some but not all patterns are visible, but not
explicit
Difficult to analyse
18-07-2015


28 explicit, at least 200-long patterns that
are supported by at least 4 trips of at least 2
cars
Easy to analyse
STDBM 2006, Seoul, South Korea
21
Conclusions and future directions
 Results:
 Frequent itemset mining can be modified to extract long
sharable patterns from trajectories
 A RDBMS provides support for an easy but effective
implementation
 Challenges:
 Some of the patterns are while different in terms of items, but
they are not all that different in spatio-temporal space.
 How can we further compress the patterns in a way that
takes this spatial-temporal closeness into consideration?
 Compression should take place during the mining
process and should be exploited to further improve
efficiency
18-07-2015
STDBM 2006, Seoul, South Korea
22