Database Reference
In-Depth Information
highlights the outlier trajectories represented in light grey (outside the darker
grey dense area).
11.2.4 Spatio-Temporal Pattern Mining
Once the HGT clusters have been extracted and filtered, the next step aims at
defining the pattern followed by most trajectories of each HGT. The main matter
of this mining task is to deduce the median trajectory followed by the HGT
and the spatial and temporal density distribution. Studies on several trajectory
clusters showed that these data do not belong to any particular statistical distri-
bution. Gaps between mean and median values are important. Density around
these values changes frequently. For example, for the time dimension, it's easier
for mobile objects to arrive late than early. For this kind of ordered set of data
in descriptive statics, box plot series are very useful to describe the evolution of
data according times. Box plots, proposed by John Tukey in 1977, graphically
describe groups of numerical data through five important sample percentiles:
The sample minimum (smallest observation),
The lower quartile or the 1st decile,
The median,
The upper quartile or the 9th decile, and
The sample maximum (largest observation).
In our maritime context, data lower than the first decile or higher than the
ninth decile are considered as outliers. The idea is to enhance box plot series to
produce 2D plus time patterns. Each pattern summarizes a cluster of trajectories
(HGT) thanks to the median value, and the symmetry and dispersion of the
data set.
First of all, a synthetic median trajectory (
T
m
) can be computed using an
iterative refinement technique similar to the
k
-means algorithm. A trajectory
from the HGT is chosen as initial
T
m
.
T
m
is an ordered set of positions:
P
m
i
.
To optimize this algorithm, a trajectory with length and time duration close to
median length and median time duration has to be chosen as initial
T
m
. Then,
all positions of each trajectory of this HGT are assigned to one position of
T
m
using a matching process. Amongst existing algorithms, dynamic time warping
(DTW)orFrechet matching can be employed. They can align trajectories'
positions in order to minimize the sum of the spatial distances between matched
positions of two trajectories (DTW), or minimize themaximumdistance between
matched positions (Frechet). They also take into account the temporal order
of the positions of trajectories. Figure
11.4
illustrates the clusters of matched
positions (
m
p
i
) between positions of trajectories of the HGT and the
P
m
i
in
black. Light grey thin lines show links between matched positions.
C
