Database Reference
In-Depth Information
Fig. 12.11
Trajectory clustering example. Four trajectories are clustered into two clusters based on
trajectory similarity
temporal constraint. The time complexity of swarm is the also highest among three
patterns. Since it needs to enumerate every possible combination of objects, the time
complexity is
O
(2
n
), where
n
is the number of moving objects in dataset. But by
applying pruning rules on the search algorithm [
21
], swarm pattern mining is quite
efficient in real scenario.
5.3
Trajectory Clustering
Different from moving object clusters that detect clusters of objects and the cor-
responding time intervals that they are being together, trajectory clustering will
group (sub-)trajectories based on the overall trajectory similarity. Moving object
cluster mining is more suitable to answer questions such as “find a group of people
staying together for more than 2 hours”, whereas trajectory clustering can answer
questions like “group hurricane paths over years based on the trajectory similarity”.
Figure
12.11
illustrates an example of trajectory clustering. There are two clusters
based on trajectory similarity.
A typical clustering framework needs to consider two factors: (1) similarity mea-
sure and (2) clustering methods. As we discuss earlier in Sect.
4
, the typical similarity
measures between two trajectories include Euclidean distance, Dynamic Time Warp-
ing and Longest Common Subsequence. And typical clustering methods include
K-Means, Hierarchical clustering and Gaussian Mixture Model.
Gaffney and Smyth [
12
] propose to cluster trajectories based on a probabilistic
modeling of trajectories. In probabilistic clustering, we assume that the data are
being generated in the following “generative” manner:
An individual is drawn randomly from the population of interest.
The individual has been assigned to cluster
k
with probability
w
k
,
sum
k
=
1
w
k
=
1.
These are the prior weights on the
K
clusters.
