Time Series Clustering

Clustering algorithms (K-Means, DBSCAN, hierarchical methods) and clustering evaluation (the Silhouette Score, computed with a full worked example in the lesson on evaluation of clustering in data mining) are covered in depth elsewhere in this series, and most of the industry applications commonly listed for time-series clustering — finance, healthcare, energy, retail, transportation — are covered with concrete examples in the lesson on data mining applications and related lessons. What genuinely sets time-series clustering apart from ordinary clustering, and deserves its own worked example, is a single question: how do you measure the "distance" between two sequences that don't even have to be the same length?

Why Ordinary (Euclidean) Distance Doesn't Work Here

Every clustering algorithm needs a way to measure how similar two data points are, and ordinary Euclidean distance — summing the squared difference at each matching position — requires the two things being compared to have exactly the same number of dimensions, matched up position by position. Two time series rarely cooperate with that requirement: one sensor might report readings a fraction of a second out of phase with another, or one process might simply take longer to reach the same milestone than another, shifting every later reading out of alignment even though the underlying pattern is otherwise identical. Euclidean distance, comparing position 1 to position 1 and position 2 to position 2 regardless of any such shift, would score two genuinely similar sequences as very different just because they drifted out of sync.

Dynamic Time Warping: Distance That Tolerates Misalignment

Dynamic Time Warping (DTW) solves this by finding the alignment between two sequences — allowing points to be stretched or compressed in time — that minimizes total distance, rather than forcing a rigid position-by-position comparison. Take two short sequences of different lengths, A = [1, 3, 4] and B = [1, 2, 4, 4]:

Pairwise absolute differences d(i,j) = |A_i - B_j|:
         B=1   B=2   B=4   B=4
A=1  |    0     1     3     3
A=3  |    2     1     1     1
A=4  |    3     2     0     0

DTW builds a cumulative cost table D(i,j) = d(i,j) + min(D(i-1,j), D(i,j-1), D(i-1,j-1)), filling it one cell at a time from the top-left corner:

         B=1   B=2   B=4   B=4
A=1  |    0     1     4     7
A=3  |    2     1     2     3
A=4  |    5     3     1     1

The bottom-right cell, D(3,4) = 1, is the total DTW distance between the two full sequences. Tracing backward from that final cell through whichever neighbor each value came from recovers the actual alignment DTW found: A's first, second, and third points align with B's first, second, and third points respectively (each contributing 0, 1, and 0 to the running cost), and then A's last point (4) is aligned a second time against B's fourth point (also 4), at zero additional cost, since they're identical. In effect, DTW recognized that B simply held at the value 4 for one extra time step compared to A, and absorbed that timing difference into the alignment instead of penalizing it — exactly the kind of comparison ordinary Euclidean distance, which cannot even be computed here without first forcing both sequences to the same length, is structurally incapable of making.

Why This Matters for Clustering Specifically

Once DTW (or a similar alignment-tolerant measure) replaces Euclidean distance as the similarity function, any of the standard clustering algorithms covered elsewhere in this series — K-Means, hierarchical clustering, DBSCAN — can be applied to time series essentially unchanged, since clustering algorithms are built around whatever distance function they're given rather than around Euclidean distance specifically. The result is what makes grouping "cities with similar seasonal temperature patterns" or "machines with similar vibration signatures before failure" possible even when the underlying events don't happen to occur at perfectly aligned timestamps across every series being compared — which, in nearly all real sensor and transaction data, they don't.