Module kernel_kmeans 

Kernel-k-means clustering of curve sets through the Global Alignment Kernel.

Standard k-means minimizes Euclidean distance to an explicit centroid. Kernel k-means lifts the data into the reproducing-kernel feature space induced by the GAK kernel and minimizes the feature-space distance to each cluster mean — without ever materializing a centroid curve. Every quantity the algorithm needs is read from the n×n GAK Gram matrix K (built once via gak_gram_train).

The kernel trick (no centroid)

For a cluster C_k the squared feature-space distance of point i is

d²(i, k) = K[i,i] − (2/|C_k|)·Σ_{j∈C_k} K[i,j] + (1/|C_k|²)·Σ_{j,l∈C_k} K[j,l]

The last term within_k = (1/|C_k|²)·Σ_{j,l∈C_k} K[j,l] depends only on the cluster, so it is precomputed once per cluster per iteration and reused across all points — the assignment sweep is then O(n²) once the Gram is in memory. With the normalized GAK K[i,i] = 1, so the diagonal term is a constant that drops out of the argmin (kept in the returned inertia for interpretability).

Because there is no centroid, KernelKmeansResult has no centers field — this is a hard correctness property of kernel k-means, not an omission.

Robustness

• Init: n_init random-partition restarts (k-means++ is wrong here — it assumes L2 curve vectors, but we only have similarity-valued Gram entries). Each restart is seeded seed_from_u64(seed + restart_idx) for reproducibility. The lowest-total-inertia restart is returned.
• Empty clusters: if a cluster empties mid-iteration (or k exceeds the number of natural clusters), it is reseeded with the point currently farthest (max d²) from its assigned cluster — the algorithm never panics.
• Determinism: the Gram is built once and reused across all restarts; the same seed yields identical labels.

Out-of-sample prediction

KernelKmeansResult::predict assigns new curves via the cross-Gram from gak_gram_predict (n_test × n_train, normalized so k(test,test)=1), reusing the fitted σ, the training within-cluster sums, and the training cluster sizes — no re-estimation.

Structs

KernelKmeansConfig

Configuration for kernel-k-means clustering (kernel_kmeans_fd).

KernelKmeansResult

Result of kernel_kmeans_fd.

Functions

kernel_kmeans_fd

Cluster a curve set with kernel-k-means through the GAK kernel.