Source-linked AI summary
shapeDTW: shape Dynamic Time Warping
Jiaping Zhao, Laurent Itti
TL;DR
DTW can produce locally implausible matches because it compares points without their neighborhood structure. shapeDTW encodes local subsequences into descriptors before applying DTW, yielding lower alignment errors and significantly better nearest-neighbor classification across UCR datasets. Its performance can depend on the descriptor, particularly for noisy series.
Problem
DTW finds globally optimal paths but may match temporal points with dissimilar local structures because pointwise coordinate similarity is unreliable.
Method
shapeDTW encodes each temporal point's local subsequence with a shape descriptor, aligns the descriptor sequences using DTW, and transfers the warping path to the original series.
Results
shapeDTW achieves lower alignment errors than DTW, dDTW, and wDTW, while NN-shapeDTW significantly outperforms NN-DTW on 64 of 84 UCR datasets.
Takeaways & Limitations
shapeDTW provides a generic alignment framework in which users can design local subsequence descriptors for their domain data.
Takeaways & Limitations
On noisy datasets with high-frequency spikes or abrupt direction changes, neighborhood-based similarity can perform worse than coordinate-based DTW.
Abstract
from arXiv · showhide
Dynamic Time Warping (DTW) is an algorithm to align temporal sequences with possible local non-linear distortions, and has been widely applied to audio, video and graphics data alignments. DTW is essentially a point-to-point matching method under some boundary and temporal consistency constraints. Although DTW obtains a global optimal solution, it does not necessarily achieve locally sensible matchings. Concretely, two temporal points with entirely dissimilar local structures may be matched by DTW. To address this problem, we propose an improved alignment algorithm, named shape Dynamic Time Warping (shapeDTW), which enhances DTW by taking point-wise local structural information into consideration. shapeDTW is inherently a DTW algorithm, but additionally attempts to pair locally similar structures and to avoid matching points with distinct neighborhood structures. We apply shapeDTW to align audio signal pairs having ground-truth alignments, as well as artificially simulated pairs of aligned sequences, and obtain quantitatively much lower alignment errors than DTW and its two variants. When shapeDTW is used as a distance measure in a nearest neighbor classifier (NN-shapeDTW) to classify time series, it beats DTW on 64 out of 84 UCR time series datasets, with significantly improved classification accuracies. By using a properly designed local structure descriptor, shapeDTW improves accuracies by more than 10% on 18 datasets. To the best of our knowledge, shapeDTW is the first distance measure under the nearest neighbor classifier scheme to significantly outperform DTW, which had been widely recognized as the best distance measure to date. Our code is publicly accessible at: https://github.com/jiapingz/shapeDTW.
1 INTRODUCTION
DTW can produce globally optimal but locally implausible alignments because it compares temporal points without neighborhood structure. shapeDTW addresses this by describing local subsequences before DTW alignment, improving alignment quality and nearest-neighbor classification.
- DTW may wrongly match points with distinct local structures because it compares temporal points using coordinate values rather than neighborhood information.
- shapeDTW aligns the resulting descriptor sequences with DTW, then transfers the warping path to the original time series.
- Local patches are more discriminative than individual pixel values in image matching, motivating an analogous neighborhood-based representation for temporal points.
- shapeDTW represents each temporal point with a descriptor encoding structural information from its surrounding local subsequence.
- shapeDTW achieves lower alignment errors than DTW, dDTW, and wDTW on simulated and real sequence pairs.
- NN-shapeDTW significantly outperforms NN-DTW on 64 of 84 UCR time-series datasets.
2 RELATED WORK
Related work improves DTW through path constraints, step patterns, derivatives, weighting, complexity correction, metric learning, or local-structure constraints. shapeDTW differs by comparing local-neighborhood descriptors and by supporting alignment as well as classification.
- Global warping constraints and alternative step patterns can prevent pathological warpings, but their selection depends on application-specific prior knowledge.
- dDTW aligns first-order derivative sequences, while wDTW penalizes distances according to phase differences between points.
- Complexity-invariant distances rectify existing measures without modifying DTW, whereas learned metrics require ground-truth alignments that are usually unavailable.
- shapeDTW measures point similarity through local neighborhoods, unlike prior methods that use single-point y-values or derivatives.
- Most reviewed classification methods were designed for classification and cannot align temporal sequences at their current stages, while shapeDTW supports both uses.
3 SHAPE DYNAMIC TIME WARPING
shapeDTW augments DTW by representing each temporal point with a descriptor of its local neighborhood, then aligning the descriptor sequences with DTW. This preserves DTW’s global warping framework while favoring matches between points with similar neighborhood structures.
- Complexity: The descriptor-alignment procedure has quadratic time complexity, the same computational complexity as DTW.Descriptor construction is linear, while DTW alignment takes O(LP×LQ) time.
- Motivation: DTW searches globally optimal alignment paths but may match points with dissimilar local structures.Its matching component compares temporal-point values while enforcing boundary, monotonicity, and continuity constraints.
- Algorithm: shapeDTW first converts each time series into a sequence of local shape descriptors and then aligns those descriptor sequences using DTW.Descriptors encode structural information from subsequences centered on temporal points.
- Optimization: The shapeDTW optimization minimizes descriptor-sequence matching cost under DTW-style warping constraints.The descriptor distance is aggregated with an ℓ1/ℓ2 matrix norm and solved by dynamic programming.
- Difference from DTW: shapeDTW uses Euclidean distances between shape descriptors rather than directly comparing temporal-point values.It therefore retains DTW’s handling of local nonlinear warping while preferring similar neighborhood structures.
4 SHAPE DESCRIPTORS
shapeDTW provides a generic framework in which local subsequences are mapped to descriptors, with choices spanning raw, approximated, shape-invariant, and compound representations. Descriptor neighborhood length and feature design determine which local structure and magnitude information are retained.
- Descriptor framework: Users can adapt shapeDTW to domain data by designing mappings from local subsequences to vector-valued shape descriptors.Each mapping F converts a subsequence si into a descriptor di whose similarity can be measured with Euclidean distance.
- Neighborhood size: Neighborhood length l controls the local context represented around each temporal point.l = 1 omits neighborhood information, whereas l approaching the full series makes descriptors too similar for point identification.
- Magnitude-aware descriptors: Raw subsequences, PAA, and DWT descriptors encode local shape together with magnitude information.Raw subsequences directly use the centered subsequence; PAA uses interval means, while DWT uses Haar-wavelet coefficients.
- Shape-invariant descriptors: Slope, Derivative, and HOG1D descriptors are invariant to y-shift and represent local shape independently of vertical offset.HOG1D uses concatenated gradient histograms, while Slope uses fitted-line slopes and Derivative uses first-order derivatives.
- Compound descriptors: Compound descriptors concatenate complementary shape and magnitude descriptors using a weighting factor γ.This fusion is intended to make subsequences more discriminative when both shape and y-magnitude provide useful cues.
5 ALIGNMENT QUALITY EVALUATION
Alignment quality is evaluated by the mean absolute deviation between two alignment paths. The measure normalizes the area between paths by the length of the reference sequence, so spatially closer paths receive lower values.
- Metric: Mean absolute deviation measures the proximity between two alignment paths.It is positively proportional to the area between the paths.
- Definition: The measure equals the area between alignment paths divided by the length of reference sequence P.For paths α and β, δ(α, β) = A(α, β)/LP.
- Interpretation: Smaller mean absolute deviation indicates spatially more proximate alignment paths.The figure illustrates the area between red and blue paths as the quantity used in the normalization.
6 EXPERIMENTAL VALIDATION
Experiments evaluate shapeDTW for sequence alignment and time series classification against DTW and its variants. Across simulated alignments and 84 UCR datasets, shapeDTW generally produces lower alignment errors and higher classification accuracy, while descriptor choice and noise impose limits.
- Experimental setup: ShapeDTW was evaluated against DTW, dDTW, and wDTW on synthetic and real sequence-alignment tasks, plus 84 UCR classification datasets.The alignment evaluation combined qualitative comparisons with quantitative alignment-path measures.
- Qualitative alignment: Local-neighborhood information makes shapeDTW less brittle than DTW and dDTW on series containing peaks, valleys, and other rich local features.DTW can confuse points with similar magnitudes but different local shapes, whereas shapeDTW uses neighborhood structure.
- Simulated alignment: ShapeDTW consistently achieved lower alignment errors than DTW, dDTW, and wDTW across stretching amounts from 10% to 50%.The comparison averaged Mean Absolute Deviation scores over 27,136 simulated pairs; shapeDTW nearly halved dDTW's errors.
- Simulated alignment: Across 84 datasets, shapeDTW had mean Mean Absolute Deviation 1.68 versus 2.75 for dDTW and lower errors on 56 datasets.This comparison used simulated pairs with an average 30% stretch and dDTW under the symmetric1 step pattern.
- Time series classification: NN-shapeDTW outperformed or tied NN-DTW on 64/63/64/61 of 84 datasets for Raw-Subsequence/PAA/DWT/HOG1D descriptors, with significant Wilcoxon results.ShapeDTW retains DTW's O(L^2) time complexity while adding descriptor extraction cost and space.
- Limitations: Raw-Subsequence can lose on noisy datasets because neighborhood comparisons may accumulate and magnify noise.The largest reported losses were 10% on Computers and 6.6% on Synthetic-control.
- Time series classification: Descriptor design affects outcomes: simple dataset-independent descriptors improve over DTW, while compound HOG1D+DWT outperforms HOG1D/DWT on 66/51 datasets.The compound descriptor's Wilcoxon p-values versus HOG1D and DWT were 5.5 · 10^-5 and 0.0034.
7 CONCLUSION
shapeDTW achieves quantitatively better alignments than DTW and its variants, while remaining a generic framework that supports user-designed local subsequence descriptors. Under nearest neighbor classification, NN-shapeDTW obtains significantly improved accuracies over NN-DTW.
- shapeDTW achieves quantitatively better alignments than DTW and its variants.
- shapeDTW is a generic framework that allows users to design and integrate their own local subsequence descriptors.
- NN-shapeDTW obtains significantly improved classification accuracies compared with NN-DTW.