k-Means Clustering

k-means seeks \(k\) centers that make the total squared distance from each observation to its assigned center small. It can partition a uniform cloud just as it partitions separated groups, so obtaining labels is not evidence that distinct populations exist. Its usefulness depends on the meaning of the distance and what the partition will be used for. Degenerate data, such as too few distinct observations, can also yield fewer than \(k\) occupied clusters.

Lloyd’s algorithm

The objective is \(\sum_i\|x_i-\mu_{c(i)}\|^2\), where \(x_i\) is observation \(i\), \(c(i)\) its assigned cluster, and \(\mu_j\) center \(j\). This sum is called inertia. The general global optimization problem is NP-hard. Lloyd’s algorithm alternates nearest-center assignment with replacing each nonempty cluster’s center by its mean. Each step minimizes the objective with the other part held fixed, so the objective cannot increase; it can stay unchanged. For points 0 and 2, center 1 gives squared error \(1+1=2\), compared with \(0+4=4\) at center 0.

In the code, broadcasting creates squared distances with shape (1500, 4): one row per observation and one column per center. argmin(1) chooses the closest center in each row. The teaching implementation retains an old center if its cluster becomes empty. It stops when assignments no longer change, and raises an error if the iteration budget is exhausted. The first library comparison uses exactly the same initial centers.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import adjusted_rand_score

X, _ = make_blobs(n_samples=1500, centers=4, cluster_std=1.0, random_state=0)
rng = np.random.default_rng(0)
initial = X[rng.choice(len(X), 4, replace=False)].copy()
centers = initial.copy()
previous_labels = None
for it in range(1000):
    labels = ((X[:, None, :] - centers[None, :, :]) ** 2).sum(-1).argmin(1)
    centers = np.array([X[labels == j].mean(0) if (labels == j).any()
                        else centers[j] for j in range(4)])
    if previous_labels is not None and np.array_equal(labels, previous_labels):
        break
    previous_labels = labels.copy()
else:
    raise RuntimeError("assignment convergence not reached")

km = KMeans(n_clusters=4, init=initial, n_init=1, tol=0,
            max_iter=1000, algorithm="lloyd").fit(X)
best = KMeans(n_clusters=4, n_init=10, tol=0,
              max_iter=1000, random_state=0).fit(X)
print(f"from scratch: {it + 1} iterations, inertia {((X - centers[labels]) ** 2).sum():.4f}")
print(f"sklearn, same start: inertia {km.inertia_:.4f}")
print(f"same partition (ARI): {adjusted_rand_score(labels, km.labels_):.4f}")
print(f"sklearn, 10 k-means++ starts: inertia {best.inertia_:.4f}")
# from scratch: 20 iterations, inertia 2515.3439
# sklearn, same start: inertia 2515.3439
# same partition (ARI): 1.0000
# sklearn, 10 k-means++ starts: inertia 2515.3325

With the same start, both implementations give inertia 2515.3439 and adjusted Rand index (ARI) 1.0. ARI compares which pairs of observations share a cluster, accounting for chance agreement; cluster ID numbers need not match. This verifies the partition in this example, not equivalence for every input or stopping rule. Ten k-means++ starts find inertia 2515.3325, lower by about 0.0114. A different starting procedure can give a slightly different partition, and default tolerance-based stopping can also leave differences. Neither run establishes the global optimum.

Exact Lloyd updates reach a stable assignment in the usual nondegenerate case with consistent tie handling. The objective is bounded below by zero, and only finitely many assignments are possible; strict improvement prevents revisiting an assignment. Ties and empty clusters require a specified policy, and floating-point implementations also use tolerances and iteration limits. The resulting fixed point need not be globally best. Initial centers, stopping rules, and numerical details all matter.

Initialization and repeated starts

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

for k, std in ((20, 0.4), (40, 0.3)):
    X, _ = make_blobs(n_samples=3000, centers=k, cluster_std=std,
                      center_box=(-30, 30), random_state=1)
    for init in ("random", "k-means++"):
        inertias = [KMeans(n_clusters=k, init=init, n_init=1,
                           random_state=s).fit(X).inertia_ for s in range(30)]
        print(f"k={k:3d}  {init:10s} best {min(inertias):9.1f}"
              f"  worst {max(inertias):9.1f}  mean {np.mean(inertias):9.1f}")
    print()
# k= 20  random     best    3110.2  worst   72845.4  mean   21009.2
# k= 20  k-means++  best     951.8  worst    1464.1  mean    1060.2
# 
# k= 40  random     best    2802.6  worst   28472.4  mean   10521.9
# k= 40  k-means++  best     521.4  worst     693.7  mean     558.1

For 20 generated groups, random starts have mean inertia 21,009 against 1,060 for k-means++, about 19.8 times as large. Comparing the worst runs gives 72,845 versus 1,464, about 49.8 times. Even the best random run, 3,110, is about 2.1 times the worst k-means++ run. These are comparisons over 30 seeds on this dataset; the table does not make a universal performance claim.

A random start can put several centers in one region while leaving another poorly represented. Subsequent local updates may split one group and merge others. Centers are not confined to regions containing observations: if a center receives points on both sides of a gap, their mean can lie in that gap. Poor results arise from the local assignments and updates settling into an unfavorable configuration, not from a rule forbidding movement across empty space.

In the original k-means++ scheme, the first center is sampled uniformly and later centers are sampled in proportion to squared distance from the nearest existing center. Distant, poorly represented regions then have a greater chance of receiving a center. Scikit-learn uses a greedy variant that tries several sampled candidates before choosing each new center. n_init specifies multiple complete runs for KMeans, keeping the lowest-inertia result. The benchmark sets it to 1 to isolate seed variability; the k-selection examples explicitly request 10 starts. Neither seeding nor restarts guarantee the best partition.

Choosing k

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

X, _ = make_blobs(n_samples=1500, centers=4, cluster_std=1.0, random_state=0)
print(f"{'k':>3} {'inertia':>12} {'silhouette':>12}")
for k in range(2, 10):
    m = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
    print(f"{k:3d} {m.inertia_:12.1f} {silhouette_score(X, m.labels_):12.4f}")
#   k      inertia   silhouette
#   2       7373.4       0.4619
#   3       4037.1       0.4796
#   4       2515.3       0.5086
#   5       2217.2       0.4366
#   6       1959.7       0.4258
#   7       1733.8       0.3947
#   8       1517.5       0.3412
#   9       1365.8       0.3437

The minimum achievable inertia cannot increase when another center is allowed: retaining the old centers remains an option. Independently fitted local solutions need not obey that ordering, although the printed values decrease here. An elbow is a change in the rate of improvement, not simply the largest drop. Here the reductions become much smaller after four centers. Choosing how sharp a bend counts as an elbow is still a judgment.

For a point, let \(a\) be its mean distance to other points in its assigned cluster and \(b\) the smallest mean distance to any other cluster. For \(\max(a,b)>0\), its silhouette is \((b-a)/\max(a,b)\). For example, \(a=1\) and \(b=3\) give \(2/3\). The average score lies between −1 and 1; larger values favor compact, separated groups under the chosen distance. Singleton clusters receive score zero in scikit-learn. The score peaks at four in this sweep, matching the number of generating groups, but that agreement is not guaranteed for other shapes, densities, or objectives. This calculation requires at least two occupied clusters and fewer clusters than observations.

Relate the partition to its intended use. Five customer segments and fifty impose different operational demands even if both have favorable internal scores. Resampling stability, comparison with a meaningful reference distribution, external information, or performance on a downstream task can provide different evidence. Choose the check that addresses the question rather than treating any one score as a test for the existence of clusters.

Which geometry the objective favors

Squared Euclidean distance favors compact groups around centers. The following are tendencies of the objective, not formal requirements that every cluster have the same shape, count, or variance.

• Elongation. Nearest-center regions are convex Voronoi cells, not necessarily spheres. A long group may be split if that reduces distortion enough.
• Unequal counts and spreads. A group with many observations or large spread can gain more from an extra center than a small tight group. K-means does not enforce equal cluster sizes, and sufficiently separated unequal groups can still be recovered.
• Concentric components. Two components with the same mean but different variances are distinguished by their density profiles. Nearest-centroid assignment alone does not model those profiles.

Euclidean distance gives equal coefficients to squared coordinate differences; it does not explicitly weight features by their variance. Multiplying one feature’s units by 1,000 multiplies its contribution by a million. Standardization can remove that unit effect, but equalizing scales is a modeling choice, not a mandatory step for data already expressed in meaningful units. Squared distance also gives outliers substantial influence. Fit any learned scaling or feature transformation on training data before a held-out assessment.

A full-covariance Gaussian mixture can represent elongated groups with different spreads and mixing proportions, although fitting remains sensitive to initialization. Other clustering methods use different geometry or density criteria and have their own limitations. Lloyd assignment costs \(O(nkd)\) per iteration for \(n\) points and \(d\) features. Full-covariance mixture calculations typically include \(O(nkd^2)\) work and covariance factorization; diagonal or spherical mixtures have different costs. Compare the actual covariance model rather than assigning one cost to every mixture.

References

• Arthur, D., & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. SODA.
• Sculley, D. (2010). Web-Scale K-Means Clustering. WWW.
• Tibshirani, Walther, and Hastie (2001). Estimating the number of clusters in a data set via the gap statistic