Transcript PPT

When And Where Next:
Individual Mobility Prediction
Gyözö Gidofalvi and Fang Dong
Geodesy and Geoinformatics
KTH – Royal Institute of Technology
Outline
 Motivation
 Related work
 Problem definition
 Inhomogeneous Continuous-Time Markov (ICTM) model for temporal
and spatial mobility prediction
 Empirical evaluation
 Conclusions and future work
2012-11-06
MobiGIS 2012, Redondo Beach, CA
2
Motivation
 Increasing adoption of location-aware mobile devices
 Capable of observing and processing the movement information of the individual
mobile user
 Cons of mobile computing: distributed processing and privacy-preservation
 Increasing adoption of Location-Based Services (LBS)
 Most services still only focus on current location of the user
 Movement of an individual contains a high degree of regularity
 Trajectory of an individual exhibits a 93% potential predictability [Barabasi et. al]
 Regularity can be temporal, periodic and sequential
 Broad applications of movement prediction




Transport
Urban planning
Mobile communication network optimization
Prefetching for LBS
2012-11-06
MobiGIS 2012, Redondo Beach, CA
3
Outline
 Motivation
 Related work
 Problem definition
 Inhomogeneous Continuous-Time Markov (ICTM) model for temporal
and spatial mobility prediction
 Empirical evaluation
 Conclusions and future work
2012-11-06
MobiGIS 2012, Redondo Beach, CA
4
Related Work
 Movement prediction approaches that have been proposed in the last
10 years can be classified along 4 major dimensions:
 Prediction model:
 Discrete-time Markov model based vs. sequential rule / trajectory pattern based
 Model basis / generality:
 General model for all objects vs type-base model for similar (type of) objects vs.
specific model for each individual object
 Definition of Regions Of Interest (ROI) for prediction:
 Application specific ROIs vs. density-based ROIs vs. grid-based ROIs
 Prediction provision:
 Sequential spatial prediction (loc. of next ROI) vs. spatio-temporal prediction
2012-11-06
MobiGIS 2012, Redondo Beach, CA
5
Shortcoming of Existing Approaches
 Spatio-temporal (where and when) prediction models are sequential
rule based / trajectory pattern based methods
 Temporal and periodic regularities at different scale need different
models
 Individual models are expensive and difficult to combine
  Instead: Dynamically weighted ensemble of Inhomogeneous
Continuous-Time Markov (ICTM) models to capture the temporal-,
periodic- and sequential regularities in movements to predict when
and where the object will move next.
2012-11-06
MobiGIS 2012, Redondo Beach, CA
6
Outline
 Motivation
 Related work
 Problem definition
 Inhomogeneous Continuous-Time Markov (ICTM) model for temporal
and spatial mobility prediction
 Empirical evaluation
 Conclusions and future work
2012-11-06
MobiGIS 2012, Redondo Beach, CA
7
Problem Definition
 Given: moving object trajectory:
 Ordered sequence of timestamped Euclidean locations
 Def: staytime in region R:
 Def: A set of mutually exclusive regions
is
prevalent and maximally discriminant (pmd-regions) if the total area
of the regions in
is minimal and
 Given the current region
time t predict:
and the trajectory history
upto
 Departure time t+s* as:
 Next region
2012-11-06
as:
MobiGIS 2012, Redondo Beach, CA
8
Outline
 Motivation
 Related work
 Problem definition
 Inhomogeneous Continuous-Time Markov (ICTM) model for temporal
and spatial mobility prediction
 Empirical evaluation
 Conclusions and future work
2012-11-06
MobiGIS 2012, Redondo Beach, CA
9
Method Overview
Preprocessing
1. Grid-based spatial aggregation of temporal
mobility statistics
2. Grid-based detection of pmd-regions
3. Tracking the evolution of pmd-regions
4. Conversion from grid-based to region-based
trajectory
Prediction
1. Individual ICTM model parameter estimation
via temporal domain projection and
sequential, spatial and temporal constraints
2. Weighted ensemble of ICTM models for
prediction
• Grid-based staytime
statistics: g
• pmd-regions: reg
• pmd-region visit and
transition statistics:
reg_vis_trans
Departure time and next region
2012-11-06
MobiGIS 2012, Redondo Beach, CA
10
Grid-based Detection of pmd-regions
 Greedy spatially contiguous region growing of ”dense” grid cells until
the min_rp-requirement for the extracted pmd-regions is met
 Definition of dense grid cell:
 Staytime in grid cells exhibit power law distribution
 Head part of the distribution tends to be qualitatively different and have distinct
semantic meaning
  Grid cells in the head of the distribution (above the mean) are ”dense”
2012-11-06
MobiGIS 2012, Redondo Beach, CA
11
Tracking the Evolution of pmd-regions
 Grid-based mobility statistics change over time  pmd-regions
evolve: shift, grow, shrink, disappear, reappear or emerge
 Tracking method:
1. Detect current pmd-regions
2. Spatially intersect current pmd-regions with pmd-regions from the past
3. Assign the ID of the intersected old pmd-region to the current pmd-region and
update the spatial information according to the current pmd-region
4. Assign a new unique ID to any remaining current pmd-region and store it’s
spatial information
2012-11-06
MobiGIS 2012, Redondo Beach, CA
12
Conversion from Grid-based to Region-based
Trajectory
Grid-based trajectory stream
Filter noisy GPS readings via buffering:
• Valid arrival: minimum staytime threshold (min_tst)
• Valid departure: maximum interruption time
threshold (max_tint)
Region-based trajectory stream
Store in DB
reg_vis_trans: <reg_id, arr_time, dep_time, prv_reg,
nxt_reg, date, day_of_week, isweekend>
2012-11-06
MobiGIS 2012, Redondo Beach, CA
13
Continuous-Time Markov (CTM) Process
 Markov property:
 If
is independent of t then the
transition probabilities are homogeneous, otherwise the transition
probabilities are inhomogeneous  ICTM model.
2012-11-06
MobiGIS 2012, Redondo Beach, CA
14
Applicability of the ICTM Model
 The holding times in a state of a CTM process must be memoryless
 exponentially distributed
 Transition probabilities are:
 Temporally inhomogeneous: pattern drift
 Periodically inhomogeneous: daily, weekly, weekend-weekday patterns
 Sequentially inhomogeneous: sequential patterns (daycace  work  daycare)
2012-11-06
MobiGIS 2012, Redondo Beach, CA
15
Prediction Using the ICTM Model
 State space S (i.e., set of pmd-regions)
 Transition rate qij : number of times the process transitions from state
i to state j in the unit time interval
 Rate parameter:
 Transition probability: pij = qij / vi
 Probability that the process remains in state i during (t, t+s] is:
 Departure time / staytime prediction:
 Next region prediction:
2012-11-06
MobiGIS 2012, Redondo Beach, CA
16
Estimation of Temporally Inhomogeneous
Transition Rates
 Given that the object has arrived at the current pmd-region R_c at
time t_a on date d_a and that the previous pmd-regions visited by
the object was R_p:
2012-11-06
MobiGIS 2012, Redondo Beach, CA
17
Estimation of Periodically Inhomogeneous
Transition Rates
 Given that the object has arrived at the current pmd-region R_c at
time t_a on date d_a and that the previous pmd-regions visited by
the object was R_p:
2012-11-06
MobiGIS 2012, Redondo Beach, CA
18
Estimation of Sequentially Inhomogeneous
Transition Rates
 Given that the object has arrived at the current pmd-region R_c at
time t_a on date d_a and that the previous pmd-regions visited by
the object was R_p:
2012-11-06
MobiGIS 2012, Redondo Beach, CA
19
Weighted Ensemble of ICTM Models
 Given ICTM models M1,…,Md that capture different aspects of
inhomogeneity
 PrM(i(s)|i) : probability according to model M that the process remains
in state i during the next s time units
 PrM(j|i) : probability according model M that the process will transition
from the current state i to the next state j
 Prediction using a weighted ensemble of models:
 Departure time / staytime prediction:
 Next region prediction:
2012-11-06
MobiGIS 2012, Redondo Beach, CA
20
Model Weights in the Ensemble
 Transitions rates of an ICTM model are estimated on the basis of a
query condition QC and an evidence set EQC
 Importance of a model M with query condition QC over a finitedomain dimension D and evidence set EQC should be:
 directly proportional to the relative size of the evidence set, |EQC|/|E0|, and
 inversely proportional to the relative expected domain selectivity of the query
condition, SD(QC)/SD(0), where SD(.) returns the size of its argument w.r.t. D
2012-11-06
MobiGIS 2012, Redondo Beach, CA
21
Outline
 Motivation
 Related work
 Problem definition
 Inhomogeneous Continuous-Time Markov (ICTM) Model for temporal
and spatial mobility prediction
 Empirical evaluation
 Conclusions and future work
2012-11-06
MobiGIS 2012, Redondo Beach, CA
22
Empirical Evaluation
 Test environments:
 64-bit Windows 7 on Intel core i7 2630 QM with 8GB RAM
 Android 2.3.7 on HTC G7 with 1GHz CPU and 512 MB RAM
 Data set:
 Subset of the GeoLife: Trajectories of top 10 users with highest average sampling
rate, longest continuous sampling period, and least amount of sampling gaps
 210,000 - 640,000 samples for 19 – 61 observation days
 Prediction performance measures:





Absolute Temporal Prediction Error (ATPE): lower the better [0, inf] (time units)
Relative Temporal Prediction Error (RTPE): lower the better [0, inf]
Overall Spatial Prediction Accuracy (OSPA): higher the better [0,1]
True Spatial Prediction Confidence (TSPC): higher the better [0,1]
False Spatial Prediction ”Confusion” (FSPC): lower the better [0,1]
 Baseline: rule-based prediction method with batch learning advantage
2012-11-06
MobiGIS 2012, Redondo Beach, CA
23
CPU and Battery Consumption Results
 CPU
 Grid-based mobility statistics: 14% of CPU for sampling frequency of 4.7
seconds
 pmd-region extraction and tracking: 4.8 seconds (executed infrequently)
 Prediction: 1.4 seconds (executed 5-10 times a day)
 Battery:
 Transient consumption is 47µAh/sec
 On a 1300mAh battery application can run 7.68 hours
 With a sampling frequency of 1 minute (still yielding acceptable gridbased mobility statistics) the application can run 10-12 times longer
than 7.68 hours.
2012-11-06
MobiGIS 2012, Redondo Beach, CA
24
Temporal Prediction Performance Results
 Individual ICTM models: Mtod, Mdow, and Mww
 Weighted ensemble ICTM models: Msta, Mdyn and Mbat
 Baseline: Mrule
2012-11-06
MobiGIS 2012, Redondo Beach, CA
25
Spatial Prediction Performance Results
 Individual ICTM models: Mtod, Mdow, and Mww
 Weighted ensemble ICTM models: Msta, Mdyn and Mbat
 Baseline: Mrule
2012-11-06
MobiGIS 2012, Redondo Beach, CA
26
Outline
 Motivation
 Related work
 Problem definition
 Inhomogeneous Continuous-Time Markov (ICTM) Model for temporal
and spatial mobility prediction
 Empirical evaluation
 Conclusions and future work
2012-11-06
MobiGIS 2012, Redondo Beach, CA
27
Conclusion and Future Work
 Dynamically weighted ensemble of ICTM models, Mdyn, can simply
and effectively capture the temporal-, periodic- and sequentialregularities in object movement
 In the long run perf(Mdyn)  perf(Mbat) > perf(Mrule)
 Predict departure time within 45 minutes of actual departure time
 Predict next region correctly in 67% of the cases
 Future work
 Investigate other dynamical weighting schemes
 How to perform prediction using the ICTM model fro a group of socially related
individuals?
2012-11-06
MobiGIS 2012, Redondo Beach, CA
28
Thank you for your attention!
Q/A?
2012-11-06
MobiGIS 2012, Redondo Beach, CA
29