Work Hours
Everyday: 北京时间8:00 - 23:59
Spatio-Temporal Data Mining
&
Trajectory Data Mining
Reading
2
- Di Wang, Tomio Miwa and Takayuki Morikawa (2020). Big
Trajectory Data Mining: A Survey of Methods, Applications, and
Services https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7472055/ - Yu Zheng (2015) Trajectory Data Mining: An Overview, ACM
Transactions on Intelligent Systems and Technology, 6(3): 29 - Microsoft 2007. https://www.microsoft.com/enus/research/project/trajectory-data-mining/
Outline - Geospatial/ Spatial-temporal data mining
– Definitions, techniques & use cases - Trajectory data mining
What is Spatial? - Relating to or existing in space only
- Take a look at https://blog.locale.ai/
What is Spatio-Temporal? - Relating to both space and time
- Spatial (location) and temporal (time) attached
- Changes and movements over time
https://www.flightradar24.com/51.5,-0.12/6
Geo-Spatial data - An eg. of the data
Geospatial data
We have looked at it before!
3d_spatial.arff in Lab 4.1
Spatial-temporal Data - Best example: google maps timeline
Data sources
Use of Spatio-Temporal Mining - Space and time are ubiquitous aspects of reality
- We are living in a space with time dimension…
- Thus basically all human (things) related data are
spatio-temporal in nature - Advances in automatic (semi-automatic) data
generators (sensors, RFID tags, GPS receivers,
mobiles etc) result in MASSIVE spatio-temporal
data - It is believed that more than 95% of business
data are spatial or spatio-temporal
Trajectory Data Mining - Geospatial -> space only
- Geospatial temporal -> space and time
– Trajectory data mining => + Movement
– “a trace generated by a moving object within a
certain spatiotemporal context and is
generally represented by a series of
chronologically ordered points.” (Zhang 2014)
Trajectory Examples - Vehicle trajectories (cars, buses, trucks
etc) - Animal movements (birds, sharks etc)
- People movements (tourists, photo-takers,
students etc) - Mouse click movements (HCI, software
design etc)
Can you name other egs?
Understanding Movements - Animal movements
– Cows frequent visits to shades, but rare visits
to grazing areas => indication of sickness?
– Bees periodic visits to hive from flowers =>
useful for beekeeping - Human movements
– Frequent visits to fast food restaurants but
rare visits to gyms/parks/beaches =>
indication of health risk
– Frequent visits to Indian/Korean/Japanese
restaurants => Asian?
Moving Objects
Questions to ask: Where, when, why, what?
Raw GPS Trajectory
How the data looks like?
Overview of TDM
Spatio-temporal Trajectories
Filtering noise*
Interpolation Stay point detection*
Map-matching*
Preprocessing
Sequential Patterns
Periodic Patterns*
Trajectory Patterns
Regions-of-Interest
Pattern Mining
Trajectory Clustering*
Trajectory Classifier*
Overview of Trajectory Data Mining
TDM Noise Filtering - What?
– The process of fitting raw trajectory recordings onto
an underlying map structure before data mining - How?
– Very different from ‘structured data’
– The idea is how do you combine location (map) with
time data?
– Noisy with GPS etc.
Issues with GPS Trajectories - Spatial uncertainties
- Errors and noisy
- Irregular
- Could be too densely recorded or too
coarsely recorded
Preprocessing
Trajectory Simplification - Aim
– Reduce the complexity of an input trajectory
– Sensors capture as much movement details as possible by
oversampling but still want to preserving the motion of the tracked
entity - Performance metrics
– Reduce processing time
– Reduce Error measure - What error measure?
– Criteria include perpendicular Euclidean distance and time
synchronized Euclidean distance
Illustration of Error Measures - Perpendicular Euclidean Distance
- Time Synchronized Euclidean Distance
Eg: Map-matching
Where, when, what?
Eg: Map-matching
Where, when, what?
Eg: Map-matching
Where, when, what?
9am 5pm
Monday, Wednesday 12pm
Monday, Wednesday 1pm
Thursday 8pm Thursday 6pm
Saturday 4pm
Saturday 5pm
Sunday 11am
Sunday 12pm
Stay Point Detection - The identification of a location a moving object has
stayed for a while within a certain distance threshold - These stay points can indicate interesting insights for eg.
at a restaurant/ shopping mall. - Uses clustering technique studied earlier eg DBSCAN
Stop/Move Representation
Indicates the trajectory
Stop/Move Representation
Locations: restaurants,
shopping malls etc
Trajectory Data Mining
Trajectory Data Mining - Categories of patterns:
– moving together patterns,
– trajectory clustering,
– periodic patterns and
– frequent sequential patterns
Trajectory Clustering - Group similar trajectories geometric proximity in
spatial/spatiotemporal space. - Find a representative trajectory from many
trajectories
= cell
Trajectory Clustering
= cell
Representative trajectory
of a swarm/ group?
Trajectory Classification - With supervised learning, classify
trajectories into activities like hiking/ dining
or different modes (walking/ driving)
GPS
log
Users
Infer
model
Trajectory Classification - Predict next move.
– If it is driving activity, where is next place of
interest after A / B?
A
?
B
Trajectory Classification - Obtain next destination with probability.
After drinks and eating, next?
60%
7%
8%
5%
20%
? - Periodic patterns are trajectories periodically
executed by a moving object. For eg. regular
movement patterns from office staff, which are
rather similar each working day. - There are 2 main approaches:
- Fixed Period Approach
- Reference Spot Approach
Spatio-Temporal Periodic Pattern
Mining
reference
spot 1
reference
spot 2
Cluster these points &
use as reference
reference
spot 3
Fixed (Time) Period Approach
To segment the long trajectory into a set of smaller (shorter) subtrajectories based on a given fixed time period
Reference Spot Approach
Find reference spots using clustering algorithms and then find associated
periods for reference spots
Spatio-Temporal PPM
Periodic Pattern Mining
Not easy! Eg.
movements
of a bee (or
bees)
Periodic Pattern Mining
Trajectory Pattern Mining - TPM considers spatio-temporal information
- In addition, add on aspatial semantic information
to produce richer patterns
Clear, weekday, 1hr 5-7hr 1hr 2-3hr
Rainy, weekday, 1hr 3-4hr 1hr 2-3hr
Open Challenges - Incorporate semantics – semantic
trajectory data mining by incorporating
aspatial information - Techniques largely the same:
– classification is still in its infancy
– Association mining (more used)
– Lots of pre-processing with uncertainties and
noise handling
