Elastic trajectory similarity (DTW, LCSS)

Description

Compare behavioural time series or trajectories that differ in speed, phase or outliers by elastic alignment, producing distances for clustering or retrieval of similar user traces.

Euclidean distance fails when series differ in baseline, scale, phase or speed. Das and Gunopulos recommend z-normalising series first, then using dynamic time warping, which finds the best monotone alignment between two series within a warping window, or longest common subsequence similarity, which matches points within a tolerance and skips unmatched outliers, giving a dissimilarity based on matched length. LCSS can also fit a global scaling and shift using matched points only. DTW is distorted by outliers; on video-tracked trajectories LCSS produced intuitive clusters where DTW failed. Non-metric measures can be closer to human judgement, relevance feedback can learn a user's notion of similarity, and lower-bounding indexes allow fast retrieval without false dismissals. In UX the measures apply to mouse paths, scroll traces, gaze sequences, sensor data and engagement curves.

Attributes

Loss type
Siloed
Effort
Days

Steps

  1. Extract each trace as a time series or trajectory (for example cursor path, daily usage curve, gaze path).
  2. Z-normalise each series to remove baseline and scale differences.
  3. Choose a warping window for DTW (for example 10 per cent of length) or a matching tolerance for LCSS.
  4. Compute pairwise DTW distances or LCSS dissimilarities.
  5. Cluster (for example hierarchical) or retrieve nearest neighbours on the distance matrix.
  6. Inspect clusters against examples and intuition; prefer LCSS when traces contain outliers and test sensitivity to window or tolerance.

Sources

  • Handbook of Data Mining (Ye, 2003)

Also known as

  • Elastic similarity for behavioural trajectories
  • Dynamic time warping
  • DTW
  • Longest common subsequence similarity
  • LCSS
  • Elastic distance

Categories

  • Analytics & Behaviour
  • Computational & Machine Learning