Technical Review: scikit-learn KMeans

scikit-learn KMeans: Technical Review

Review date:July 14, 2026

Version scope:scikit-learn 1.9.0, released June 2, 2026, with Python 3.11-3.14 support.[1]

Evidence hierarchy:the public API and user guide define supported behavior; the tagged 1.9.0 Python and Cython source is used for implementation details; release notes are used for version-specific changes.

Executive assessment

The textbook account of K-means is brief: choose centers, assign every observation to its closest center, recompute the centers, and repeat. That description captures the optimization loop, but not the engineering required ofsklearn.cluster.KMeans.

The production estimator must validate dense and sparse data, convert layouts and dtypes, choose initial centers, run one or more independent fits, incorporate sample weights, repair empty clusters, stop under floating-point arithmetic, coordinate compiled parallel kernels, and return an estimator whose stored labels remain compatible with later calls topredict. Scikit-learn handles those responsibilities carefully.[2][5]

The implementation quality should not be confused with universality of the model.KMeansminimizes squared Euclidean distance to a fixed number of centroids. It does not discover arbitrary latent structure, infer the scientifically correct number of groups, produce membership probabilities, or make Euclidean distance meaningful for the user.[2][3]

The public 1.9.0 signature is:

KMeans(

n_clusters=8,

*,

init="k-means++",

n_init="auto",

max_iter=300,

tol=1e-4,

verbose=0,

random_state=None,

copy_x=True,

algorithm="lloyd",

)

The defensible conclusion is therefore narrower than "KMeans is a good clustering method":scikit-learn provides a mature implementation of classical batch K-means, while the analyst remains responsible for justifying its geometry, features, value of K, and stability.

1. Objective and statistical interpretation

For equal-weight observations, K-means minimizes within-cluster sum of squares, reported after fitting asinertia_:

\[

\sum_i \min_j \lVert x_i - \mu_j \rVert^2.

\]

Withsample_weight=w, the effective objective is:

\[

\sum_i w_i \min_j \lVert x_i - \mu_j \rVert^2,

\]

and each updated center is a weighted mean rather than an ordinary arithmetic mean.[2][5][6]

This distinction has several consequences.

First, for a fixed set of centers, multiplying one sample's distance by a positive scalar does not change which center is nearest. The sample weight changes the sample's contribution to center updates and inertia, not the nearest-center rule itself.

Second, multiplying all weights by the same positive constant leaves the weighted centers and optimal partition unchanged, but it scales inertia by that constant. Raw inertia values should therefore not be compared across analyses that use different weight normalizations.

Third, the implementation is built around weights behaving as non-negative mass. The built-in random and k-means++ initializers normalize weights into sampling probabilities. Scikit-learn 1.9.0 also introduced a project-wideValueErrorfor an all-zero sample-weight vector.[4][5][9]

There is a source-level validation caveat. The general_check_sample_weighthelper can enforce non-negative weights, butKMeans.fitcalls it without settingensure_non_negative=True.[5][9]Negative values are therefore not rejected by that particular validation call, although built-in initializers can fail when they try to turn signed values into probabilities. Signed weights have no documented K-means interpretation and should not be used as a supported way to encode opposition or subtraction.

The user guide's statement that a weight of two is equivalent to duplicating an observation is exact for the weighted objective and center update. It does not imply that stochastic initialization will follow exactly the same random path as a physically duplicated matrix: duplication changes the row index population from which initial centers are sampled.

The objective favors compact, approximately convex and isotropic groups in the selected feature space. It is poorly matched to rings, crescents, long manifolds, strongly unequal dispersions, or applications in which Euclidean distance has no defensible meaning.[3]

The guide's phrase that K-means seeks groups of "equal variance" is best read as a spherical, equal-covariance modeling tendency, not a constraint that the fitted clusters must have equal empirical variance or equal membership counts.[3]

Finally,n_clustersdefines the optimization problem before fitting. Silhouette analysis, stability tests, external labels, or domain knowledge can help compare candidate values, butKMeansitself does not learn K.[2][3]

2. Input validation and numerical preparation

KMeans.fitaccepts array-like dense input and SciPy sparse input. The tagged implementation validates computation intofloat32orfloat64, converts dense data to C order, and uses CSR for sparse computation. Integer and other compatible numeric arrays are normally converted rather than processed as native integer K-means data.[2][5]

These conversions can allocate memory even whencopy_x=False. A non-C-contiguous dense array, a sparse object that is not already CSR, or an input requiring dtype conversion can still be copied.[2]

Under ordinary validation settings, the input must contain finite numeric values. Users who globally enableassume_finite=Truecan skip some validation for performance, but then responsibility for detecting NaN and infinite values moves to the caller.

The estimator also requiresn_samples >= n_clusters. Requesting more clusters than observations raises an error before optimization begins.[5]

The current KMeans validation path setsaccept_large_sparse=False. In practical terms, CSR inputs requiring 64-bit sparse index arrays are outside the accepted path unless they can be represented safely with the supported index type.[5]

Dense centering is numerical, not statistical preprocessing

For dense input, scikit-learn subtracts the feature-wise mean before initialization and fitting, then adds the mean back to the final centers. With a suitable mutable array andcopy_x=False, it also restores the caller's data before returning.[2][5]

This translation improves numerical behavior without changing pairwise Euclidean distances. It is not equivalent to standardizing features.KMeansdoes not scale variances, normalize rows, decide feature importance, remove outliers, or impute missing values. Those upstream choices define the metric and can alter the clustering completely.

copy_x=Falseis therefore a memory-and-input-preservation hint, not a zero-allocation mode. Scikit-learn still needs centers, labels, cluster-weight sums, shifts, initialization data, and low-level workspaces. Temporary subtraction and restoration can also leave very small floating-point differences in the caller's array.[2][5]

3. Initialization and restart policy

Initialization matters because the K-means objective is non-convex. Different starting centers can converge to different local solutions.[3]

Greedy k-means++

The defaultinit="k-means++"is not the simplest one-candidate version often shown in introductions. Scikit-learn uses greedy k-means++. At each seeding step after the first, it samples several candidates, evaluates the potential produced by each, and keeps the best.[2][5]

Whenn_local_trialsis not supplied, the tagged source uses:

2+int(np.log(n_clusters))

The API summarizes this as2 + log(k), but the source truncates the logarithm to an integer.[5]

Built-in k-means++ uses sample weights both when sampling the first center and when constructing the weighted squared-distance distribution for later candidates.init="random"likewise samples observations without replacement according to normalized sample weights.[5]

Explicit centers and callables

The estimator also accepts an explicit(n_clusters, n_features)center array or a callable. Scikit-learn does not separately applysample_weightduring either of these custom initialization paths; the caller must incorporate weighting if it is desired at that stage.[2]

A subtle implementation detail matters for dense data: the initialization callable receives the internally mean-centered working matrix, not necessarily the caller's original coordinates. Explicit center arrays are shifted into that same working coordinate system before fitting. Custom code should therefore use theXit is given rather than assume that it is unmodified input.[5]

n_init="auto"

In scikit-learn 1.9.0,n_init="auto"means:[2]

-one run forinit="k-means++";

-ten runs forinit="random";

-ten runs for a callable initializer;

-one run for an explicit center array.

An explicit center array forces one run even if a largern_initis requested. One greedy k-means++ run is a default speed-quality compromise; it is not a stability analysis. Sparse, high-dimensional, difficult, or high-consequence applications should consider a larger restart count and compare partitions across seeds.[2]

Across restarts, the implementation accepts a new best result only when inertia is lower and the partition is genuinely different. A pure relabeling of the same partition is recognized as equivalent, so arbitrary cluster-number permutations do not replace an otherwise identical solution.[5]

4. Lloyd and Elkan fitting paths

The defaultalgorithm="lloyd"implements the classical assignment-and-update loop. For each iteration, observations are assigned to their closest centers, weighted feature sums and cluster weights are accumulated, and new centers are obtained from those totals.[5][7]

algorithm="elkan"uses triangle-inequality bounds to avoid some sample-center distance calculations. It maintains an upper bound for each sample, a dense lower-bound array of shape(n_samples, n_clusters), and center-to-center distance information of shape(n_clusters, n_clusters). This can reduce distance work when clusters are well separated, but it adds O(n*k) lower-bound storage and O(k^2) center-distance storage.[2][5][8]

Both algorithms have separate dense and sparse Cython kernels. Sparse input is not routed through a generic dense fallback, although the learned center matrix is dense. Elkan's lower-bound matrix is also dense even whenXis sparse.[5][7][8]

Requesting Elkan withn_clusters=1triggers a warning and a fallback to Lloyd, because the bound machinery offers no useful pruning for a single center.[5]

It is reasonable to view Lloyd as the more predictable memory choice, but scikit-learn does not formally document memory predictability as the reason it is the default. That explanation should be labeled as an engineering inference rather than project intent.

The dense Lloyd kernel works in sample chunks and uses a chunk-by-cluster distance workspace rather than allocating one full(n_samples, n_clusters)distance matrix for the complete dataset. This distinction helps explain why Lloyd's memory behavior is less severe than a naive vectorized implementation might suggest.[7]

5. Empty clusters and duplicate observations

An iteration can leave a center with no assigned sample weight. Scikit-learn attempts to repair this state rather than leaving the center at zero or immediately aborting.[6][7][8]

The dense and sparse kernels identify centers whose accumulated cluster weight is zero. They then select observations that are farthest from their currently assigned centers, remove the selected observation's weighted contribution from its old cluster, and use that contribution to initialize the empty cluster.[6]

One subtlety is that the ranking of candidate observations is based on geometric squared distance, not distance multiplied by sample weight; the selected observation's weight is applied when its contribution is transferred. With unusual weighting, "farthest" and "largest weighted error" are therefore not identical concepts.[6]

If every relevant distance is zero, relocation cannot create new geometry and is skipped. This occurs, for example, when the requested K exceeds the number of distinct coordinates. Any center that still has zero accumulated weight is placed at the location of the largest-weight cluster for numerical convenience. After fitting, scikit-learn checks the number of distinct labels and emits aConvergenceWarningwhen fewer clusters were realized, commonly because duplicate observations prevented K distinct groups.[2][5][6]

This warning is the end of a repair process, not the only behavior related to empty clusters.

6. Convergence and early stopping

The single-run kernels use two stopping tests.[5]

1.Strict convergence:labels are exactly unchanged from the preceding iteration.

2.Center-shift convergence:if labels changed, the sum of squared center-shift distances is compared with an internally scaled tolerance.

The internal tolerance is:

mean feature variance * user tol

For sparse input, feature variance is calculated without densifying the matrix.[5]

Consequently,tol=1e-4is not a raw coordinate-distance threshold. The public API calls it a relative tolerance, while the source makes the scale dependence explicit. Settingtol=0is allowed, but the private single-run documentation discourages it because rounding can prevent the movement test from declaring convergence.[2][5]

max_iter=300is a ceiling for each restart. If a run stops without strict label convergence, scikit-learn performs a final assignment-only pass with the stored centers. This ensures thatlabels_agrees withpredict(X)for those centers.[2][5]

The tradeoff is that, after early stopping,cluster_centers_need not equal the exact weighted means of the observations in the finallabels_. The final pass changes assignments without another center update, and the API documents this edge case.[2]

7. Outputs and estimator API

The principal fitted attributes are:[2]

-cluster_centers_: dense fitted centroids;

-labels_: hard assignments for training observations;

-inertia_: weighted within-cluster sum of squared distances;

-n_iter_: iterations used by the selected restart.

Cluster IDs have no semantic order. Label 0 is not inherently the smallest, earliest, strongest, or most important cluster. Equivalent fits can permute IDs while representing the same partition.

predict(X)performs hard nearest-centroid assignment. It does not return posterior probabilities or calibrated uncertainty.

transform(X)returns ordinary Euclidean distances, not squared distances, to every center. The output shape is(n_samples, n_clusters). It is generally dense even when the input is sparse, which can create a substantial downstream memory cost.[2][5]

fit_transform(X)is not a fused K-means kernel that receives all final distances for free. In the tagged source it callsfit(...)and then the private_transform(...)method. This avoids the second publictransformvalidation path, so it can save some overhead, but it does not reuse a complete training-time distance matrix or change the optimization itself.[5]

score(X, sample_weight=...)returns the negative K-means objective for the supplied data and weights. It equals-inertia_only when evaluated on the same training observations with equivalent weights. The sign follows scikit-learn's higher-is-better scoring convention.[2][5]

8. Parallelism and systems engineering

The numerical work is performed primarily in compiled Cython kernels. Scikit-learn processes fixed-size sample chunks, currently 256 observations, and uses OpenMP for sample-wise parallelism inside a single run.[3][5][7][8]

The estimator exposes non_jobsparameter. The Python loop overn_initrestarts is sequential in the tagged implementation; parallelism is concentrated within the numerical kernels rather than across independent restarts.[5]

Major single-run arrays for centers, labels, cluster weights, and shifts are allocated outside the iteration loop and reused. The low-level routines still use per-thread accumulation buffers and chunk workspaces, so "buffers are reused" should not be read as "the loop allocates nothing."[5][7]

The Lloyd single-run function limits nested BLAS threading while the outer OpenMP layer is active, reducing OpenMP-by-BLAS oversubscription. The implementation also checks for a Windows combination of Microsoftvcompand Intel MKL associated with a small memory leak when active chunks are fewer than available threads, and emits anOMP_NUM_THREADSworkaround.[5]

These are not changes to K-means mathematics. They are examples of library engineering that a short Python reimplementation normally omits.

CPU and device scope

The 1.9.0 KMeans path is based on NumPy/SciPy validation and Cython/OpenMP kernels.KMeansis not listed among the estimators supported by scikit-learn's experimental Array API dispatch, and its public API provides no native GPU option.[10]

Third-party accelerated implementations can be useful, but they should be identified separately rather than described as behavior ofsklearn.cluster.KMeans.

9. Interpreting inertia and comparing K

Lower inertia is better only for the same observations, feature representation, and weight convention. It is unnormalized and is not a direct measure of scientific validity.[3]

The globally optimal K-means objective is non-increasing as K grows: an optimization problem with more centers has at least as much representational capacity. A sequence of independently fittedKMeansestimators is not guaranteed to show perfect monotonicity, however, because each fit can settle in a different local solution or stop at a different point. The claim that observedinertia_"always falls" as K increases is therefore too absolute.[3]

Even a perfectly decreasing inertia curve does not identify the correct K. Extra centers generally improve reconstruction of the same data. A defensible K requires additional evidence such as partition stability, silhouette structure, external labels, held-out behavior, downstream usefulness, or domain constraints.

10. Modeling limits

Several important limitations belong to the objective rather than to scikit-learn's implementation.

Feature scale

KMeansdoes not standardize features. Multiplying one feature by ten makes squared differences along that coordinate contribute one hundred times as much to inertia. Scaling is therefore part of the model, not cosmetic preprocessing.

Outliers

Arithmetic and weighted means are sensitive to extreme observations. K-means has no robust loss that automatically discounts them.

Cluster shape

Nearest-centroid Voronoi regions are convex in the chosen feature space. Curved, disconnected, or strongly elongated groups are not represented naturally.[3]

Hard assignment

Every sample receives exactly one label, including observations close to a decision boundary. The estimator does not express ambiguous membership.

Fixed K

The cluster count is provided by the analyst.

High-dimensional geometry

Euclidean distances can become difficult to interpret as dimensionality grows. Dimensionality reduction may help, but its transformation, retained dimension, and scaling become part of the clustering model.[3]

Missing values

Ordinary validation requires finite input, so missing-value handling belongs upstream. Scikit-learn can globally suppress finiteness checks withassume_finite=True, but disabling validation does not make NaN or infinite values supported K-means observations.[9][12]

Sparse, high-dimensional text data are not automatically invalid for K-means: scikit-learn supports CSR input and provides sparse text-clustering examples. The relevant issue is whether normalization, representation, dimensionality, and Euclidean geometry are appropriate for the question.

11. Scale boundaries and related estimators

Full-batch KMeans revisits the complete dataset during every iteration. The API points users towardMiniBatchKMeansfor large sample counts and gives about 10,000 observations as a practical guideline beyond which mini-batch fitting may be much faster. That number is not a hard cutoff.[2]

When K itself is large,BisectingKMeanscan be more efficient because each bisection operates on a subset of observations rather than comparing every observation with every final center at every stage. The user guide also notes that it avoids empty clusters by construction.[3]

Neither alternative removes the need to validate Euclidean centroid geometry. They change the optimization strategy and scale profile, not the underlying meaning of distance.

12. Reproducibility and recommended reporting

An integerrandom_statemakes initialization repeatable within a fixed software setup. It is not a guarantee of bit-for-bit identity across scikit-learn releases, NumPy or SciPy versions, CPU architectures, thread settings, or dtype changes.

A reproducible KMeans analysis should record at least:

-scikit-learn version;

-input data version or checksum;

-feature construction and feature order;

-missing-value handling;

-scaling, normalization, and dimensionality reduction;

-n_clusters;

-initand any custom initializer code;

-n_init;

-algorithm;

-tolandmax_iter;

-random_state;

-sample weights and their normalization;

-input dtype and sparse format;

-relevant OpenMP or BLAS thread settings;

-the procedure used to assess K and partition stability.

For consequential interpretation, the most useful checks are usually repeated fits, assignment stability, sensitivity to K, sensitivity to scaling, robustness to outliers, and comparison with models based on different geometric assumptions. Another decimal place of inertia is rarely the decisive evidence.

Overall conclusion

sklearn.cluster.KMeansis a mature implementation of a deliberately narrow objective. Its strengths are disciplined numerical and software engineering: greedy weighted k-means++ initialization, configurable restarts, dense and sparse kernels, empty-cluster relocation, scale-aware stopping, a final assignment pass after non-strict convergence, OpenMP parallelism, and integration with the wider estimator API.[2][5][6][7][8]

The estimator is most persuasive when the application can justify six propositions:

1.clusters can reasonably be represented by means;

2.Euclidean distance is meaningful;

3.feature scales are intentional;

4.hard assignments are acceptable;

5.K is externally defensible;

6.the fitted partition is sufficiently stable for the intended use.

When those conditions hold, KMeans is difficult to beat for simplicity, speed, and transparency. When they do not, a polished implementation can still return a clean set of labels that describes the wrong geometry.

Primary references

1.Scikit-learn 1.9.0 release: https://github.com/scikit-learn/scikit-learn/releases/tag/1.9.0

2.KMeansAPI, scikit-learn 1.9.0: https://scikit-learn.org/1.9/modules/generated/sklearn.cluster.KMeans.html

3.K-means user guide, scikit-learn 1.9.0: https://scikit-learn.org/1.9/modules/clustering.html#k-means

4.Scikit-learn 1.9 release notes: https://scikit-learn.org/1.9/whats_new/v1.9.html

5.Tagged Python implementation: https://github.com/scikit-learn/scikit-learn/blob/1.9.0/sklearn/cluster/_kmeans.py

6.Shared Cython implementation: https://github.com/scikit-learn/scikit-learn/blob/1.9.0/sklearn/cluster/_k_means_common.pyx

7.Lloyd Cython kernel: https://github.com/scikit-learn/scikit-learn/blob/1.9.0/sklearn/cluster/_k_means_lloyd.pyx

8.Elkan Cython kernel: https://github.com/scikit-learn/scikit-learn/blob/1.9.0/sklearn/cluster/_k_means_elkan.pyx

9.Validation utilities, including sample-weight validation: https://github.com/scikit-learn/scikit-learn/blob/1.9.0/sklearn/utils/validation.py

10.Experimental Array API support: https://scikit-learn.org/1.9/modules/array_api.html

11.Parallelism and resource management: https://scikit-learn.org/1.9/computing/parallelism.html

12.Computational performance andassume_finite: https://scikit-learn.org/1.9/computing/computational_performance.html