Time-Series Clustering and Alignment

Elastic alignment can recover shared shape. It can also erase timing differences that mattered. Both the brake on it and the price of it have been measured rather than argued.

The brake came fitted from the start. Dynamic time warping arrived in 1978 with its limit already built in. Sakoe and Chiba restrict the warping path with an “adjustment window” j - r <= i <= j + r and with a slope constraint P. Their abstract announces it: “A new technique, called slope constraint, is successfully introduced, in which the warping function slope is restricted so as to improve discrimination between words in different categories.” The constraint carried a number. They set the window length r to 6 frames, which at their 18 ms sampling period “covered the utmost +-108 ms timing difference”. Across 3,000 recognition tests — 10 speakers, 6 reference-pattern sets, 50 input patterns — the optimized symmetric-form algorithm “gives no more than about two-thirds errors, even compared to the best conventional algorithm”, against 0.8 percent error for plain linear time normalization. The window was not a later patch. It shipped with the method.

The third column is not the poor relation of the second. Over 48 UCR data sets, Paparrizos and Gravano found no significant difference in average rank between shape-based distance (SBD), cDTW_opt and cDTW_5, under a Friedman test with post-hoc Nemenyi at 95% confidence. SBD is only 4.4x slower than Euclidean distance. The cost gap runs the other way too: “SBD is three orders of magnitude (3533x) faster than DTW”. An independent benchmark ran eight clustering methods over 112 UCR data sets and reached the same shape. For k-means “the tallies are 32, 31 and 28 for DTW, shape-based, and Euclidean, respectively”, and the average Adjusted Rand Index across all eight methods ran only from 0.26 (agglomerative + Euclidean) down to 0.16 (density peaks + DTW). "Is more computationally expensive" has a factor attached to it. The accuracy it buys may not survive a significance test.

One motor develops a vibration pattern over six minutes. Another shows the same progression over nine. Euclidean pointwise distance calls them different, because the peaks fall at different timestamps. Time-series similarity must decide whether timing variation is noise, signal, or evidence of a different process. Alignment is therefore a modeling choice. It is not a preprocessing afterthought.

Begin with the temporal question and only then select the representation. Steps 1 to 4 fix the unit, the invariances, the representation and the split. Step 5 is where the elastic route becomes expensive a second time, because under DTW the prototype you are asked to inspect is itself a research problem.

The obvious way to average sequences under DTW is pairwise — schemes such as NLAAF and PSA. In 2011 Petitjean and colleagues showed that this is not associative: “Pairwise averaging strategies are intrinsically sensitive to the order, with no guarantee that a different order would lead to the same result.” Their global alternative, DTW Barycenter Averaging, does better on the archive data sets: “for all datasets, DBA reduces/improves the intraclass inertia”, with a geometric average of inertia ratios of 65% against both NLAAF and PSA.

A better centroid did not, by itself, buy a better clustering. An independent evaluation over 48 UCR data sets found k-DBA beat k-means with DTW on 39 of 48 data sets, “with an average improvement in Rand Index of 25.6%”. And yet k-DBA “still does not perform better than k-AVG+ED in a statistical significant manner”. That is why step 5 names medoids before centroid curves. A medoid is an observed series. It costs neither an averaging algorithm nor an argument about ordering.

Time-series pipelines should expose which differences were normalized away. The field's most-used benchmark makes one of those choices for you, before you open the data. The UCR Time Series Archive grew from 16 data sets to 45, then to 85, then to 128, and it states the policy in Section III-C: “The time series are already z-normalized to remove offset and scaling (transformed data have zero mean and in unit of standard deviation).” The same curators grant the exception: “for some (we believe, very rare) cases, data normalization is ill-advised”. Their own Fall 2018 briefing records where the line falls. The 85 data sets of the Summer 2015 release “are z-normalized by legacy”. The 43 added in 2018 are “kept as is unless they were already z-normalized by donating source”.

Each route preserves a different view of temporal behavior. They are not equally exposed to the same failures. One of them, the sliding-window route, has a published result saying its output can be independent of the data.

Equal values, similar shapes, aligned motifs, shared spectra, and common generative dynamics can each define a cluster of series. Those are five claims, not five names for one.

Document the window, the resampling, the normalization, the alignment constraint, and the prototype. Each of those has a measured default somewhere in this lesson: a warping band of a few percent rather than ten, a benchmark that z-normalizes by policy, a centroid method whose result depends on the order it saw the series. Without that record, a cluster name hides the temporal definition that produced it.