Database Reference
In-Depth Information
individual. Reference spots are highly visited areas in space which are
found using density estimation. Given a reference spot, the movement of
a user can be described as a binary sequence in which the user is either at
that spot or not. Periodic movement may then be detected by applying
a Discrete Fourier Transform (DFT) and selecting all frequencies higher
than a threshold. This procedure is repeated for each reference location,
thus identifying various period lengths which are robust to noise in the
spatial movement of the user.
Periodic movement patterns are then described as a probability dis-
tribution (computed via maximum likelihood) over reference locations
at each time step within a given period. Using these probability dis-
tributions, the next step is to identify the specific patterns. This is
accomplished through a hierarchical clustering of the probability dis-
tributions, using KL-divergence as the distance measure. Patterns are
combined and an overall clustering score is maintained such that when
the score increases too much, the clustering stops and hence picks
k
,the
number of clusters, automatically. Experimental evaluation found the
proposed methods to be able to accurately identify interesting periodic
movement behaviors. Additionally, the authors applied their method to
a real data set, the location of a bald eagle over three years, and they
were able to identify the migration patterns of the eagle over that time.
In addition to utilizing the large quantities of available trajectory
data to identify interesting patterns, it is also possible to identify object
movements that
do not
follow the expected behavior. That is, given
enough data we can identify common behavior patterns and use this to
detect anomalies. To this end, Li et al. [46] introduce a rule and motif
based anomaly detection method for moving objects (ROAM). The idea
in this work is to partition trajectories into several prototypical sub-
movements and use features extracted from these movements to classify
each trajectory as normal or abnormal. In this work, the authors pose
anomaly detection as a supervised learning problem and thus assume a
training set of labeled trajectories is available. The proposed algorithm
is composed of three steps: (i) motif extraction, (ii) feature generation
and (iii) classification.
The motif extraction phase slides a window (of fixed length) over each
trajectory and the set of subtrajectories (i.e. each window) is clustered.
The cluster centroids are referred to as
motifs
, and a second pass through
the dataset determines which trajectories
express
each motif (i.e. have
a subtrajectory that matches with error less than
). Next, features are
generated for each motif and the values are discretized (or clustered)
to ensure generalization (e.g. (right-turn, speed, 11mph) or (right-turn,
time, 2am)). Additionally, a hierarchy is built over the value space
