flowchart TB TrainX["Training Data X"]:::input TrainSW["Sample Weights"]:::input HP_nClusters["n_clusters"]:::parameter HP_init["init method
(k-means++ / random / array / callable)"]:::parameter HP_nInit["n_init
(number of initializations)"]:::parameter HP_maxIter["max_iter"]:::parameter HP_tol["tol"]:::parameter HP_algorithm["algorithm
(lloyd / elkan)"]:::parameter HP_randomState["random_state"]:::parameter ValidateX["Validate & Convert X
(dtype, CSR, C-order)"]:::mechanism MeanSubtract["Subtract Feature Mean
(dense only)"]:::mechanism ComputeNorms["Compute Squared Row Norms"]:::mechanism ComputeTol["Compute Data-Dependent Tolerance
(mean variance × tol)"]:::mechanism InitCentroids["Initialize Centroids"]:::mechanism KPP["k-means++ Initialization:
distance-proportional sampling
with local trials"]:::mechanism RandomInit["Random Initialization:
weight-proportional sampling"]:::mechanism AlgoSelect{"Select Algorithm"}:::decision LloydIter["Lloyd Iteration:
assign labels → recompute centers"]:::mechanism ElkanIter["Elkan Iteration:
triangle-inequality bounds
+ assign/update"]:::mechanism LabelAssign["E-Step: Assign Each Sample
to Nearest Center"]:::state CenterUpdate["M-Step: Recompute Centers
as Weighted Means"]:::state CenterShift["Compute Center Shift
(squared displacement)"]:::state ConvergeCheck{"Convergence Check:
labels unchanged OR
center shift ≤ tol"}:::decision IterLoop["Repeat up to max_iter"]:::mechanism InertiaCalc["Compute Inertia
(weighted sum of squared distances)"]:::mechanism MultiInitSelect["Select Best Run
(lowest inertia,
distinct clustering)"]:::aggregation RestoreMean["Restore Feature Mean
to Centers"]:::mechanism TrainedCenters["cluster_centers_"]:::output TrainedLabels["labels_"]:::output TrainedInertia["inertia_"]:::output TrainedNIter["n_iter_"]:::output TrainX --> ValidateX TrainSW --> ValidateX HP_randomState --> InitCentroids ValidateX --> MeanSubtract ValidateX --> ComputeNorms ValidateX --> ComputeTol HP_tol --> ComputeTol MeanSubtract --> InitCentroids ComputeNorms --> InitCentroids HP_init --> InitCentroids HP_nClusters --> InitCentroids TrainSW --> InitCentroids InitCentroids --> KPP InitCentroids --> RandomInit HP_init --> KPP HP_init --> RandomInit KPP --> AlgoSelect RandomInit --> AlgoSelect HP_algorithm --> AlgoSelect AlgoSelect -->|lloyd| LloydIter AlgoSelect -->|elkan| ElkanIter LloydIter --> LabelAssign ElkanIter --> LabelAssign LloydIter --> CenterUpdate ElkanIter --> CenterUpdate TrainSW --> LabelAssign TrainSW --> CenterUpdate LabelAssign --> CenterShift CenterUpdate --> CenterShift CenterShift --> ConvergeCheck ComputeTol --> ConvergeCheck HP_maxIter --> IterLoop ConvergeCheck -->|not converged| IterLoop IterLoop --> LloydIter IterLoop --> ElkanIter ConvergeCheck -->|converged| InertiaCalc LabelAssign --> InertiaCalc CenterUpdate --> InertiaCalc TrainSW --> InertiaCalc HP_nInit --> MultiInitSelect InertiaCalc --> MultiInitSelect MultiInitSelect --> RestoreMean MeanSubtract --> RestoreMean RestoreMean --> TrainedCenters MultiInitSelect --> TrainedLabels MultiInitSelect --> TrainedInertia MultiInitSelect --> TrainedNIter classDef input fill:#cfe8ff,stroke:#333,color:#000; classDef parameter fill:#ffd9b3,stroke:#333,color:#000; classDef mechanism fill:#e6e6e6,stroke:#333,color:#000; classDef state fill:#e6ccff,stroke:#333,color:#000; classDef aggregation fill:#fff2cc,stroke:#333,color:#000; classDef decision fill:#f8c8dc,stroke:#333,color:#000; classDef output fill:#c6f6c6,stroke:#333,color:#000;