Abstract
Computing the "average" of a set of time series is a fundamental task in data mining, yet it remains computationally daunting under the Dynamic Time Warping (DTW) distance. The DTW-Mean problem, which seeks a series minimizing the sum of squared DTW distances to a sample set, is NP-hard. Historically, researchers have relied on heuristics without performance guarantees. This paper presents the first exact mathematical programming framework for DTW-Mean. By formulating the problem as a Mixed-Integer Nonlinear Program (MINLP) and utilizing network flow techniques, the authors provide a method to find optimal solutions and provable lower bounds, marking a significant shift from heuristic-based approaches to exact optimization.
The Challenge of Averaging Warped Sequences
In time series analysis, standard Euclidean averaging often fails because sequences may represent the same underlying pattern but with local shifts or varying speeds. Dynamic Time Warping (DTW) addresses this by finding an optimal non-linear alignment between sequences.
However, finding a single "Fréchet Mean" series that minimizes the squared DTW distance to all others is a complex combinatorial problem. Until now, the field has largely depended on heuristics like DTW Barycenter Averaging (DBA). While effective in practice, these methods offer no theoretical guarantees on how close the result is to the true mathematical optimum.
Mathematical Programming Formulations
The authors propose several MINLP formulations to model the alignment and distance calculations precisely. A key contribution is the transition from vertex-based to arc-based modeling.
Vertex vs. Arc Formulations
- DTW-V (Vertex-based): Uses binary variables to indicate if a specific point in the alignment grid is part of the optimal path.
- DTW-A (Arc-based): Models the alignment as a network flow problem. Although it involves more variables, the authors demonstrate that this formulation is "tighter." Its mathematical relaxation is closer to the true integer solution, allowing modern solvers to prune the search space more efficiently.
Optimization Techniques
To make the problem tractable, the authors introduced:
- Domain Bounding: A polynomial-time algorithm to calculate tight upper and lower bounds on the mean series' values, significantly reducing the search space.
- Distance Reformulations: They compared standard "Big-M" indicator constraints against Perspective Reformulations and Outer Approximations to handle the nonlinear squared distance terms.
Key Insights and Results
The research yielded several critical findings regarding the behavior of these optimization models:
- The Superiority of Flow: The arc-based formulation consistently outperformed the vertex-based one. Its "tightness" allowed solvers like Gurobi to reach solutions much faster despite the increased variable count.
- Global Constraints: Incorporating constraints like the Sakoe-Chiba band is essential. By limiting how far an alignment can stray from the diagonal, these constraints drastically reduce the number of variables and make previously intractable problems solvable.
- Performance on Real-World Data: Testing on datasets from the UCR Time Series Classification Archive showed that for small instances (length $m=10$, $k=2$ series), the models reached a 0% optimality gap almost instantly. As complexity increased ($m=20, k=5$), the best models still maintained a respectable ~15% gap after one hour, providing a much clearer picture of solution quality than any heuristic.
Conclusion and Future Directions
While scalability remains a challenge for long sequences or large datasets, this work establishes a rigorous foundation for exact DTW-Mean computation. Future research will focus on developing new valid inequalities to further tighten lower bounds and integrating these exact models with relaxation-based heuristics to combine computational speed with provable quality.
Summary updated