Progressive and Iterative Approaches for Time Series Averaging

Saeid Soheily-Khah, Ahlame Douzal Chouakria, Éric GaussierAALTD@PKDD/ECML 2015 · OpenReview

Introduction

Averaging a set of time series is a fundamental challenge in data mining, essential for tasks such as clustering and summarization. Unlike standard vectors where an arithmetic mean suffices, time series data often exhibits temporal misalignments—a phenomenon described as being "stretchy." For instance, two utterances of the same word may vary in emphasis on different syllables, making a simple point-by-point average produce a blurry, non-representative signal.

To address this, researchers utilize Dynamic Time Warping (DTW) to align sequences. However, finding the optimal alignment for $N$ sequences is an NP-complete problem with exponential complexity ($O(T^n)$). This paper evaluates four major heuristic strategies—NLAAF, PSA, CWRT, and DBA—to determine the most effective method for creating representative "average" sequences across diverse datasets.

Methodology

The study categorizes averaging heuristics into two primary strategies:

  1. Progressive Approaches: These utilize a tournament-style pairwise averaging.
  2. NLAAF (NonLinear Alignment and Averaging Filters): A basic tournament-style approach.
  3. PSA (Prioritized Shape Averaging): Employs hierarchical clustering to order the averaging process, prioritizing specific shapes.
  4. Iterative Approaches: These refine an initial template through repeated optimization.
  5. CWRT (Cross-Words Reference Template): Aligns all sequences to a central "medoid."
    • DBA (DTW Barycenter Averaging): A global iterative method that minimizes the squared DTW distance between the average sequence and all other sequences in the set.

Experimental Evaluation

The methods were tested on nine public datasets categorized by similarity type:

  • Global Similarity: CBF, CC, DIGITS, and CHARACTER TRAJ, where sequences within a class share a high degree of overall resemblance.
  • Local Similarity: BME, UMD, SPIRAL, NOISED SPIRAL, and CONSSEASON, which feature complex local patterns despite global differences.

Results and Discussion

The evaluation revealed significant drawbacks in progressive methods, most notably the "Length Explosion" problem. In methods like NLAAF and PSA, the resulting average sequence grows significantly with each pairwise combination; for example, a sequence starting at length 128 can balloon to over 35,000 points. Furthermore, progressive methods suffer from error propagation, where inaccuracies in early pairings affect the final output.

In contrast, DBA demonstrated superior performance in both efficiency and accuracy.

Performance and Quality

DBA consistently achieved the highest Inertia Reduction Rate (IRR), a metric indicating how well the average represents the set. On the "Character Trajectories" dataset, DBA reached a 90.6% reduction.

Inertia Reduction Rate (IRR) comparison across various datasets.

Qualitative results further support DBA's efficacy. As shown in the visualization of the CBF dataset, DBA produces centroids that closely align with ground truth shapes, whereas progressive methods often introduce noise or distortion.

Comparison of centroids for the CBF dataset: (a) ground truth, (b) NLAAF, (c) PSA, (d) CWRT, (e) DBA.

Computational Efficiency

DBA proved significantly faster than its counterparts. For the CBF dataset, while PSA required nearly 10,000 seconds, DBA completed the task in just 42 seconds. This speed, combined with the avoidance of length explosion, makes DBA the most viable option for large-scale time series analysis.

Conclusion

While all evaluated methods are heuristics and do not guarantee a global optimum, DTW Barycenter Averaging (DBA) emerges as the most robust and efficient approach. It avoids the computational pitfalls of progressive methods while delivering superior representational quality. Future work may focus on refining iterative processes to better handle datasets with extreme local temporal variations and noise.

Summary updated

BibTeX
@inproceedings{soheilykhah2015progressive,
  author = {Saeid Soheily-Khah and Ahlame Douzal Chouakria and Éric Gaussier},
  title = {{Progressive and Iterative Approaches for Time Series Averaging}},
  booktitle = {AALTD@PKDD/ECML},
  year = {2015},
  url = {https://openreview.net/forum?id=PP6DT9gWFN},
}
Figure