Information Technology Reference
In-Depth Information
include behavior classification in animal ecology (stand, forage, fly) or travel mode
detection (walk, bike, car, bus; see Sect.
3.4
).
3.2.2 Similarity and Clustering
Trajectories and other traces of moving objects are complex objects and therefore
comparing trajectories in order to assess their similarity or for clustering is a chal-
lenging problem. Trajectories, for example, can significantly vary in length or extent,
shape and orientation, as well as granularity. Furthermore, there are different notions
of what might be considered similar when comparing trajectories. Trajectories could
be considered similar if they have similar shapes (elongated vs. clumped), share
commonalities in terms of derived movement parameters (similar average speed or
sinuosity), visit similar places (edge
G
in Fig.
3.3
f), feature similar patterns (such
as repeated bursts of relocation in Levy walks, Gonzalez et al.
2008
) or express
sequences (Fig.
3.3
e) or diurnal rhythms. Depending on the application domain the
notion of similarity will focus on different aspects of the complex spatio-temporal
traces of moving objects.
Here, a general procedure for assessing trajectory similarity and subsequent tra-
jectory clustering is presented and illustrated through the respective procedure in
Dodge et al. (
P14
.
2012
).
•
Specify a frame of reference
. What shall be compared? The entire lifeline of an
object? Yearly migrations of animals or daily commuting trips of people? To
this end, segmentation methods may be used in preprocessing steps. Dodge et al.
(
P14
.
2012
) investigate the (a) whole lifelines of hurricanes from the moment of
their formation until their degradation, and (b) the movement along a specifically
selected set of edges of an urban transportation network.
•
Choose or define a distance metric.
Dodge et al. (
P14
.
2012
) specifically argue for
a spatio-temporal notion of distance, explicitly going beyond only considering the
atemporal geometry. The trajectory is thereto transformed into a sequence of class
labels based on the movement parameter speed. Then a modified edit distance for
comparing such strings is used as a distance metric.
•
Compute similarity matrix and apply a suitable clustering technique.
To this end,
Dodge et al. (
P14
.
2012
) applied complete-linkage agglomerative hierarchical
clustering.
Figure
3.6
illustrates the procedure for four selected hurricane trajectories. Even
though H2 and H3 appear to have rather similar shapes, in terms of speed sequences
H1 and H2 express the smallest distances and then, the largest similarity, respectively.
