Module kshape 

k-Shape clustering of curve sets through the Shape-Based Distance (SBD).

k-Shape (Paparrizos & Gravano, k-Shape, SIGMOD 2015) is a partitional clustering algorithm for time series that is invariant to amplitude scaling and phase (circular) shift. It alternates two steps, Lloyd-style, until convergence:

1. Assignment. Each z-normalized series is assigned to the cluster whose centroid minimizes the sbd distance. The optimal SBD shift from that same call is stored — it is needed to shift-align the member before the centroid update (a common transcription bug is to discard it).
2. Refinement (shape extraction). Each centroid is recomputed as the top eigenvector of a shift-aligned, mean-centered cross-product matrix — not the arithmetic mean (that would be k-means, not k-Shape). See [shape_extraction] for the exact matrix algebra.

Shape extraction (the only genuinely-new numerical piece)

For a cluster with members X (n_k × m, each row shift-aligned to the current centroid and z-normalized):

S = XᵀX                        (m × m)
Q = I_m − (1/m)·O_m            (centering over the TIME dim; m = series length)
M = Qᵀ S Q                     (symmetric m × m)
μ = argmax eigenvector of M    (LARGEST eigenvalue)

The eigenvector is defined up to sign: the sign that minimizes the total SBD to the members is chosen, then μ is z-normalized. Two subtle points that silently corrupt k-Shape if wrong: the centering divisor is m (the series length), not n_k; and nalgebra returns eigenvalues ascending, so the centroid is the eigenvector at the largest eigenvalue (argmax), not index 0.

Robustness (mirrors crate::kernel_kmeans)

• Init: n_init random-partition restarts, each seeded seed_from_u64(seed + restart_idx); the lowest-total-inertia restart wins. The default n_init = 10 (an fdars convention exceeding tslearn’s 1).
• Empty clusters: a cluster that empties mid-iteration is reseeded in place from the series currently farthest (max SBD) from its centroid — a documented divergence from tslearn’s full restart. The algorithm never panics; k > natural clusters returns valid labels.
• Determinism: the same seed yields byte-identical labels and inertia; sequential and parallel builds agree (SBD is RNG-free).

Out-of-sample prediction

KShapeResult::predict z-normalizes each new series, computes sbd to every stored (already-z-normalized) centroid, and takes the argmin — the centroids are used as-is, so predict(train_data) reproduces the training labels.

Structs

KShapeConfig

Configuration for k-Shape clustering (kshape_fd).

KShapeResult

Result of kshape_fd.

Functions

kshape_fd

Cluster a curve set with k-Shape.

sbd_kmedoids

Cluster a curve set with k-medoids over the Shape-Based Distance.