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:
- Progressive Approaches: These utilize a tournament-style pairwise averaging.
- NLAAF (NonLinear Alignment and Averaging Filters): A basic tournament-style approach.
- PSA (Prioritized Shape Averaging): Employs hierarchical clustering to order the averaging process, prioritizing specific shapes.
- Iterative Approaches: These refine an initial template through repeated optimization.
- 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.
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.
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