Transcript Web Services整合無線通訊 應用實務

Learning Transportation Mode from
Raw GPS Data for Geographic
Applications on the Web
Yu Zheng, Like Liu, Longhao Wang, Xing Xie
Microsoft Research Asia
4F, Sigma building, No.49 Zhichun road, Haidian District, Beijing 100080, P. R.
China
Speaker: Hsiang Wei Jen
Advisor Prof. Hsing Mei
Web Computing Laboratory
Computer Science and Information Engineering Department
Fu Jen Catholic University
Page:1
Outline
• Introduction
• Contribution
• GEOLIFE
– Architecture of GeoLife
• FRAMEWORK
– Inference Strategy
– Post-Processing
– CRF-Based Inference
• Change Point Based Segmentation
Page:2
Introduction
• Web-based mapping application (e.g. Google Maps,
Yahoo Maps…) have attracted many user.
• In these applications, GPS data play important roles.
• These applications only use raw GPS data.(e.g.
coordinate,timestamp)
• Mining knowledge from raw GPS data to find
transportation modes, such as walking, driving etc.
• Propose an approach using raw GPS data that is based
on supervised learning to automatically learn the
transportation modes including walking, taking a bus,
ride and driving.
Page:3
Introduction
• Knowledge of transportation modes
– For user:
•
•
•
•
Reflect on indivdual past events.
Deeply understand indivdual life pattern.
Presents richer knowledge to other users
Facilitates life sharing among people.
– For the application systems
• Enables context-aware computing based on a user’s present
transportation mode.
• Distinguish GPS tracks by transportation modes so that users
can find proper routes to their destinations in a more effective
manner
• Mine deeper knowledge such as traffic condition, popular routes
for different transportation modes
Page:4
Contribution
• It is an important step towards improving geographic
applications on the Web by using knowledge mined
from raw GPS data.
• Such knowledge can enhance the connection between
locality and mobility, and enable more novel
applications on the Web.
• It helps users deeply understand their own
experience and better shares other people’s
knowledge.
• It enables local/mobile application systems to
perform context-aware computing based on
transportation mode and create an innovative user
interface for Web users.
Page:5
GEOLIFE
• GPS-log-driven application over Web Map
• Given the GPS track log and associated
multimedia data.
• Share life experience with other and absorb
rich knowledge.
• Allows users to give a spatial range over maps
and/or temporal interval as a query
• Support each person’s recall of past event
Page:6
Architecture of GeoLife
Page:7
Prototype of GeoLife
Page:8
An example of inferring transportation
modes from GPS data
Page:9
Route recommendation based on
transportation mode
Page:10
Using transportation mode to improve
mobile search
Page:11
FRAMEWORK
• Definition
–
–
–
–
–
–
–
GPS log: sequence of GPS points
Track
Trip
Segment
Change point: A place which user change transportation mode
Walk Segment: walk transportation mode
Non-Walk segment: other transportation modes
Page:12
Inference Strategy
•
•
•
•
First divide the GPS track by change point
Extract feature form each segment
Send these features to inference model
Two Alternative way
– General classifier like Decision Tree: post-processing
– Conditional random field (CRF)
Page:13
Post-Processing
• Improve the prediction accuracy
• Threshold Exceed ?
– Yes: use this transportation mode as result on the segment
– No: Re-calculate the probability of its adjacent segment
– equation
• Segment[i].P(Bike) = Segment[i].P(Bike) X P(Bike|Car)
• Segment[i].P(Bike) = Segment[i].P(Bike) X P(Bike|Car)
• …
Page:14
CRF-Based Inference
• CRF graphic mode for prediction transportation mode.
• State stand for the transporation mode while an
observation is the feature extract from the segment.
• State depends on current, previous and next
observation
Page:15
Change Point Based Segmentation
• Change Point detect
– People must stop and then go when changing their
transportation
– Walk should be a transition between different
transportation modes.
– GPS data collecteed by 45 people for six month.
Page:16
Change Point Based Segmentation
• Find change point by detecting walk segment from a trip.
• Trip are categorized into Walk Segment and non-Walk Segment.
• Detecting procedure
– Step 1: Using a loose upper bound of velocity (Vt) and that of
acceleration (at) to distinguish all possible Walk Points from nonWalk Points.
– Step 2: If the length of a segment composed by consecutive Walk
Points or non-Walk Points less than a threshold, merge the segment
into its backward segment.
– Step 3: If the length of a segment exceeds a certain threshold, the
segment is regarded as a Certain Segment. Otherwise it is deemed
as an Uncertain Segment. If the number of consecutive Uncertain
Segment exceeds a certain threshold, these Uncertain Segments
will be merged into one non-Walk Segment.
– Step 4: The start point and end point of each Walk Segment are
potential change points, which are leveraged to partition a trip.
Page:17
An example of detecting change points
Page:18
Conclusions
• 將原始的GPS data，利用資料探勘的技術發掘交
通模式。
• 將發掘出的模式做更深入的應用。
Page:19