Transcript pptx
Larger datasets are becoming available from GPS, GSM, RFID, and other
sensors.
Interest in movement has shifted from raw movement data analysis to more
application-oriented ways of analyzing segments of movement.
Hence, semantically rich trajectories has have been promoted.
We will review:
1.
Constructing trajectories from movement tracks
2.
Enriching trajectories with semantic information
3.
Using data mining techniques to analyze semantic trajectories
Trajectory: a trajectory is the path that a moving object follows through
space as a function of time. Thus, it can be captured as a time-stamped
series of location points, denoted as {x1, y1, t1, x2, y2, t2, ..., xN, yN, tN} where
xi, yi represent geographic coordinates of the moving object at time ti and N
is the total number of elements in the series.
Semantic Trajectory: a trajectory that has been enhanced with annotations
and/or one or several complementary segmentations (e.g. segmented by
“start” and “stop” points).
Raw movement data: data points collected from tracking devices, such as
GPS.
We would like to turn imperfect raw movement data into a trajectory dataset
that is correct and manageable from the viewpoint of the targeted
application.
Steps:
1.
Trajectory data cleaning
2.
Trajectory map-matching
3.
Compression of trajectory data
Preprocessing
Semantic
Enrichment
Behavior
Mining
Most query processing and indexing techniques are built upon this assumption that
spatio-temporal positions of moving objects can be precisely provided.
Real-life trajectory data is far from being reliable enough for applications:
Noises
Poor GPS Signal
Battery Outage
…
GPS errors can be divided into to main categories:
1.
Systematic errors: happens due to low number of available satellites and invalidates the
GPS position. Can be solved by automatic filtering methods -> for example using the
maximum speed of the object.
2.
Random errors: happens duo to external reasons. Can be reduced by smoothing methods
which are based on statistical analysis -> Kernel based methods, regression based
methods …
We have to find noisy points (outliers) replace them with a better value. For
example, we could use the Maximum speed of an object to find outliers.
Preprocessing
Semantic
Enrichment
Behavior
Mining
For objects that moves in a network, such as road network.
There are two reconstruction levels:
1.
2.
Replacing the point with a point inside the network:
Geometric map-matching: point-to point, point-to-curve, curve-to-curve
Topological map matching: adjacency and connectivity of the graph are important.
Probabilistic map-matching: consider speed, direction, heading …
Hybrid
Transforming the raw trajectory into a semantic map-matched trajectory, for
example a. sequence of road segments.
Preprocessing
Semantic
Enrichment
Behavior
Mining
Trajectory data in applications grow progressively and intensively as the
tracking time goes by.
Such enormous amounts of data can sooner or later lead to storage,
transmission, computation, and display challenges.
Objectives of compression algorithms:
Reducing the size of dataset.
Reducing the computation complexity.
Supporting low devastation (reduced and original trajectories are not too different)
Algorithms can be categorized to 3 groups:
Top-down algorithms recursively split trajectory and keep the key points (DP).
Bottom-up algorithms in each step add a point that has the lowest cost.
Windowing algorithms (online reduction).
Preprocessing
Semantic
Enrichment
Behavior
Mining
There are three general steps:
1.
Trajectory segmentation into Episodes
2.
Episodes annotation
3.
Trajectory annotation
Preprocessing
Semantic
Enrichment
Behavior
Mining
Trajectory segmentation is driven by application-dependent criteria.
The most common one: “stop”s and “move”s periods.
The challenge is to find the stop points:
No movement at all during some length of time -> probably stopping at a place of
interest (POI) such as a “Restaurant”, the “Eifel tower”, a “Museum” and etc.
A five minute gap that car is not moving or low speed (Krumm and Horvitz [2006]).
Moving with a almost constant speed and direction for a fishing boat.
…
Preprocessing
Semantic
Enrichment
Behavior
Mining
After finding stop points, we could annotate episodes with activities or POIs:
At home, at work, …
In bus, driving, walking
Shopping, walking, …
…
Preprocessing
Semantic
Enrichment
Behavior
Mining
Synthesizing all the information in the trajectory into a singe label that
characterizes the whole trajectory. For example, considering annotations of
episodes we could come up with the “Tourist” label for the trajectory.
Preprocessing
Semantic
Enrichment
Behavior
Mining
Knowledge discovery from trajectories aims at identifying behaviors, either among
individual trajectories or groups of trajectories.
Spatial and Spatiotemporal Patterns
Granularity of Trajectory Patterns
Global Vs. Partial Patterns
Individual Vs. Group Patterns
Constrained Trajectory Patterns
Common techniques:
Clustering trajectories sharing similar characteristics such as shape, speed, direction…
Classifying trajectories in predefined classes.
Discovering common sequences of movements (from A to B to C)
Identifying objects that their movements are related to each other (leadership, flock, …)
Semantics-based behavior discovery techniques can be divided in two main
groups:
1.
approaches searching for common behaviors that are previously unknown.
2.
approaches looking for specific behaviors.
Preprocessing
Semantic
Enrichment
Behavior
Mining
Meet: A group of trajectories end at the same region C.
If we use semantic trajectories with stops annotated with POIs (school A,
school B, . . . , cinema Lux). we can discover the frequent semantic behavior
“going from school to cinema on Wednesday afternoon”, which corresponds to
the fact that this cinema offers special price tickets for students on
Wednesday afternoons.
The Semantic Trajectory Data Mining Query Language (ST-DMQL) [Bogorny et
al. 2009] allows users to specify semantic enrichment of trajectories with
contextual domain information,
The language is implemented in Weka-STPM [Bogorny et al. 2011], an
extended version of the Weka data mining toolkit and the first toolkit for
multilevel mining of semantic trajectories. It is a free and open-source tool
that also provides spatial visualization of the semantic trajectories and
behaviors.
Another tool that analyzes semantic trajectories to infer behavior is M-ATLAS
[Giannotti et al. 2011]. This system provides support for both raw and
semantic trajectories, and is organized in a plug-and-play architecture that
allows the easy integration of different mining algorithms, from clustering to
classification techniques.
Preprocessing
Semantic
Enrichment
Behavior
Mining
Spatio-temporal vs.
semantic behavior
Chasing behavior: provide an algorithm that evaluates if an individual (a
person or animal) called the stalker intentionally follows another individual
called the target. The stalker must follow the target for a certain time
period, and during this period, the movement of the two individuals must
remain with similar speed and direction. Moreover, the target must always be
in front of the stalker. Siqueira and Bogorny [2011].
Avoidance behavior: present an algorithm for identifying the trajectories
that avoids a static object. For example, when analyzing human trajectories
an avoidance of street cameras may reveal a suspect behavior;
A trajectory shows an Avoidance behavior when it moves towards a target
geographic object, turns around this object without intersecting it, and after
avoiding the target object, the trajectory returns to its original path. Alvares
et al. [2011].
Preprocessing
Semantic
Enrichment
Behavior
Mining
Semantic Trajectories Modeling and Analysis, ACM Computing Surveys, Vol.
45, No. 4, Article 42, Publication date: August 2013.
Computing with Spatial Trajectories, Yu Zheng, Xiaofang Zhou, Springer
Mobility Data Management and Exploration, Nikos Pelekis, Yannis Theodoridis,
Spronger