[Perf #478] KMeans Digits fit: eliminate 5.9x training deficit while preserving clustering equivalence

[godofecht]

Parent: #478

Canonical v2 Digits: Flow fit 351.94 ms vs sklearn 59.75 ms while Flow predict is faster (0.082 ms vs 0.132 ms). End-to-end is ~0.170x. Iris KMeans already wins ~6.7x, so the hole is scale-sensitive fit behavior.

Profile initialization, distance matrix/assignment, centroid accumulation, empty-cluster handling, convergence checks, restarts, allocation/copies and iteration count. Record distance evaluations and iterations so algorithmic work is separated from kernel throughput. Preserve the existing ARI/inertia semantic contract.

Acceptance: stage/iteration profile, operation counts, scaled samples/features/clusters/restarts, no regression in inertia/ARI parity, Digits fit >=0.95x first and >=1.05x target, current prediction win retained.

[godofecht]

OpenProjects analysis found a concrete remaining initializer target in lib/scikit/cluster.flow: _kmeans_sk_pp_init samples all local-trial candidates for a center-selection step before scoring them, but then scores each candidate with its own scalar n × d _kmeans_sqdist pass. The same module already uses blas_matmat_nt for Lloyd assignment.

The greedy local trials can be scored in one batch without changing the random draw stream or exact real-arithmetic objective. Gather sampled candidate rows C, reuse one global xnorm[i] = ||x_i||^2 cache across all center selections and all n_init restarts, compute G = X C^T, then evaluate D_it = xnorm[i] + xnorm[c_t] - 2 G_it and P_t = sum_i min(closest[i], D_it).

For canonical Digits (n=1797, d=64, k=10, T=4, n_init=10), a simple feature-operation model drops from 124,208,640 scalar sub/mul/accumulate ops to 83,035,776 norm/dot ops, a structural reduction of 41,172,864 (~33.1%), before the throughput gain from moving the dominant work onto SGEMM.

Floating-point trajectory safety needs a guard: if approximate potential intervals satisfy P_hat[a]+E[a] < P_hat[b]-E[b] for every competitor, the winner is provably unchanged; otherwise fall back to the existing direct scorer for that selection step. This mirrors the guarded BLAS assignment strategy already in _kmeans_assign.

Full derivation + Flow executable: godofecht/OpenProjects/ml/batched-greedy-kmeans-plusplus.{md,flow}. The decisive profile is init sampling vs candidate scoring vs Lloyd, plus fallback rate and exact chosen-center sequence per restart.