Mobility Data Mining - Mobility Data - page 109

to be very close to each other during the duration of the flock. However, a
group might appear also under different conditions. One of these alternatives is
to require that at each timestamp the objects form a cluster - thus borrowing
ideas and methods from the clustering literature. Notable examples are moving
clusters and convoys , two forms of pattern that at each time stamp group objects
by means of density-based clustering . Such an approach can be summarized in
the following points (see also Figure 6.5 c for an example):
First, all objects that have a large number of neighbors are labeled as core
objects ; among the remaining objects, those that are neighbors of core objects
are labeled as border objects ; the remaining objects are labeled as noise ;
Second, core objects are grouped into clusters in such a way that each pair
of neighboring core objects falls in the same cluster. Essentially, clusters are
computed as transitive closure of the neighbor relation;
Finally, border objects are assigned to the same cluster of their neighboring
core objects, while noise is discarded.
The neighbors of an object are all the objects at a distance not larger than a
threshold r , and the minimum number of neighbors required to make an object
a core object is also a parameter m . Therefore, we can see that a core object and
its neighbors approximately satisfy the closeness requirements of a flock - more
exactly, these are density requirements. The step forward here is that multiple
compact groups can be merged together if they are adjacent (see the second
step), in order to form larger ones. Besides their sheer size, the groups formed
through this process can also have a relatively large extension (therefore not all
pairs of objects in the cluster will be close to each other, because they actually
are neighbors of neighbors of neighbors) and an arbitrary shape. In several con-
texts this can be useful, for instance in analyzing vehicle trajectories, since the
road network simply forces large groups of cars to distribute along the roads
(therefore creating a cluster with a snake-like shape) instead of freely agglom-
erate around a center (which would instead yield a compact, spherical-shaped
cluster).
The key difference between moving clusters and convoys is the fact that
convoys require that the population of objects involved in the pattern is always
the same, while in moving clusters it can gradually change along the time: the
only strict requirements are that at each timestamp a (spatially dense) cluster
exists, and that when moving from a timestamp to the consecutive one the
population shared by the corresponding spatial clusters is larger than a given
fraction (a parameter of the method). A simple example of moving cluster that
illustrates this point is shown in Figure 6.2 : at each time slice a dense cluster is
2 Notice that a border object might have two or more neighboring core objects belonging to different
clusters. In this case one of them is chosen through any arbitrary criterion.