Database Reference
In-Depth Information
Root
Id:2
Region:A
Support:31
Id:4
Region:F
Support:37
Id:3
Region:B
Support:28
Match
Id:1
Region:C
Support:35
[9,15]
[4,20]
[70,90]
[134,150]
[8,70]
[2,51]
[10,12]
Id:9
Region:B
Support:31
Id:6
Region:A
Support:26
Id:7
Region:C
Support:21
Id:8
Region:D
Support:25
Id:10
Region:E
Support:28
Id:11
Region:D
Support:37
Id:5
Region:D
Support:35
[10,56]
Id:10
Region:E
Support:21
Prediction
Figure 6.9 Sample prediction tree produced by WhereNext.
The modeling tools that are able to model the sequential evolution of the
objects they describe are good candidates for a predictive usage. Indeed, once
a trajectory has been associated to the most likely model (for instance, by
choosing one of the
k
HMMs combined in a mixture-model, as described for
the clustering problem), such model can be
run
to simulate the most likely next
steps. In most cases we can apply the same remarks discussed earlier in this
section for classification: if the model is based on an overall summary of the
behavior of a set of trajectories, most likely it will not be able to capture local
events, even though their appearance is highly correlated with a future behavior -
in our case, the next location.
In literature it can be found an approach called
WhereNext
, which works in a
way not too dissimilar from the one followed by TraClass for the classification
problem. Basically, WhereNext extracts T-patterns (see Section
6.2.2
) from a
training data set of trajectories and combines them into a tree structure similar to
a prefix-tree. In particular, each root-to-node path corresponds to a T-pattern, and
root-to-leaf paths correspond to maximal patterns. Figure
6.9
shows a sample
prediction tree, condensing 12 patterns, 7 of which are maximal (one per leaf).
When a new trajectory is presented, its most recent segment is compared
against the regions represented in the tree, looking for the best match among the
root-to-node paths. For instance, Figure
6.9
depicts the case where the last part
of the trajectory visits region A followed by region B after a delay between 9
and 15 time units. The match is depicted by the dark shaded sequence. Then, the
model finds that the matched sequence is a prefix of a longer pattern, and so it
suggests as likely continuation region E (marked in light shaded in the figure),
to be reached after a delay between 10 and 56 time units.
