Task T4

Similarities, Patterns and Clustering Approaches

 Task leader: S. Marchand-Maillet – CUI
Participants: C. Bernard, J. Gensel, D. Ziebelin, P. Genoud (LIG); H. Cherifi, E. Leclercq, C. Cruz (LIB); G. Giuliani (ISE); Flann Chambers (CUI/LIB); PostDoc (CUI)

Objectives

This task enables inter-trajectory matching and comparison. While the above tasks initially consider trajectories as a model (T2) and then individually (T3), there is a high interest in being able to relate, match and compare trajectories. The basis for such operations is the definition of inter-trajectory similarity measures. Based of similarity one natural operation is to group similar trajectories or, equivalently, to define profiles for categories of trajectories. The knowledge of trajectory profiles can then serve for prediction and even help for simulations (T5).

Activities

A4.1 – Similarity measures for trajectories: aims to install a metric over trajectories that will, in turn, enable similarity computation. As defined in T2 and T3, trajectories will consist of rich multidimensional indicators along a temporal axis. Then, this metric will account for essentially two main aspects. First, it will enable the fusion of metrics over the set of indicators associated with an environmental trajectory. The challenge is to account for both the rich structure of these indicators and their potential correlations. This will be based on the semantic structure defined in T2 and resolved in close collaboration this task. The second major challenge is to handle asynchronous evolutions and potentially partial temporal matching of trajectories. The definition of an internal latent structure within the trajectory (A4.2) will help enabling partial comparisons. The main contributions will be the definition of a similarity model over (potentially part of) trajectories, induced by the specific metric installed over the space of trajectories, to feed all subsequent trajectory mining operations.

A4.2 – Trajectory profiling: aims to structure a dictionary of components to encode trajectories. This encoding will naturally lead to trajectory clustering, using similarity measures produced in A4.1 and enable the grouping of similar trajectories. In parallel, such an encoding will define a trajectory profiling, which will exhibit latent factors (from the dictionary of components) that will prove useful for prediction (see A4.3). Further, the definition of a dictionary of components will help the decomposition of trajectories into base elements and therefore facilitate their partial match (A4.1). The main challenge here is to define the base dictionary components. The most basic approach is to create a dictionary of components using a low-rank decomposition applied on a set of randomly sample parts of trajectories. An evolution of this approach may use statistical learning (encoders) to learn such a dictionary. Interpretability of these components may then appear as a regularizing constraint, in relation to the semantic structure of the trajectory (T2), in order to make any encoding legible and interpretable.

A4.3 – Trajectory prediction: aims to predict future environmental trajectories. The typical Machine Learning apparatus for sequence prediction, such as LSTM using recurrent neural networks may be used for prediction, either at a global level or by interfering over local components. This activity does not aim at innovating in the field of Machine Learning tools for sequence prediction but rather to setup and evaluate the capability of such state-of-the-art sequence methods in the context of encoded multimodal temporal trajectories. It will enable trajectory forecast as a base for decision making and policy evaluation.

Deliverables

  
Activity N° Caption Type Deadline
A4.1 D4.1 Model for measuring the similarity between trajectories Technical Report M18
A4.2 D4.2 A method for dictionary learning over trajectories and its use for trajectory encoding and profiling Technical Report M30
A4.3 D4.3 A report of the use of sequence prediction techniques for trajectory prediction Technical Report M39