K-means objective and restart stability

Last updated: 5 Oct 20265 min read

tutorial

K-means assigns each point to its nearest centroid and updates centroids to reduce within-cluster squared distance, but its result depends on scale, initialization and the chosen cluster count.

State the object being minimized

For warehouse profiles represented as scaled numeric vectors, k-means seeks K centroids minimizing the sum of squared distances from each profile to its assigned centroid. The teaching implementation alternates assignment and centroid updates for a tiny two-dimensional cohort. It does not select K automatically. A smaller inertia at larger K is expected; by itself it is not evidence that more segments are operationally useful. Scaling defines the distance first.

Handle initialization and empty groups

Different starting centroids can settle at different local solutions. Repeat fits with distinct initializations and compare inertia and membership, not just one run. If no point is assigned to a centroid, the update is undefined; the code stops rather than silently retaining an empty group. Production libraries may use explicit reinitialization strategies. Keep the chosen seed and initial centroids in a reproducible analysis record.

Inspect cluster support and meaning

A one-warehouse cluster may identify a genuine exceptional site or a measurement error. Review feature distributions, site size and incident logs before giving it a business label. The cluster number is merely an index; relabeling across runs does not imply instability if the same sites remain grouped. Compare partitions by membership or a label-invariant score. The applied audit treats actionability separately from fit.

Know when the shape assumption fails

Centroid distance favors roughly compact groups under the chosen metric and can split one elongated operational pattern into several segments. Dense pockets separated by noise may call for a density-based method. High-dimensional sparse representations can also make Euclidean distance less informative. This page deliberately focuses on the objective and checks; it does not claim K-means is the default answer for every unlabeled dataset.

Do not turn a cluster into a causal claim

If high-backlog warehouses form one group and have more delays, the cluster does not show that backlog caused the delays. A downstream staffing policy needs evaluation against a baseline and an allocation constraint. If cluster IDs become predictive features, fit the scaler and centroids only on training rows within the validation fold. The split lesson still applies.

Implementation

def squared_distance(profile, centroid):
    return sum((left - right) ** 2 for left, right in zip(profile, centroid))

def fit_small_kmeans(profiles, initial_centroids, iterations=20):
    if not profiles or not initial_centroids or iterations <= 0:
        raise ValueError("profiles, centroids and iterations required")
    width = len(profiles[0])
    if width == 0 or any(len(profile) != width for profile in profiles):
        raise ValueError("inconsistent profile width")
    if any(len(centroid) != width for centroid in initial_centroids):
        raise ValueError("inconsistent centroid width")
    centroids = [tuple(centroid) for centroid in initial_centroids]
    for _ in range(iterations):
        assignments = [min(range(len(centroids)),
                           key=lambda index: squared_distance(profile, centroids[index]))
                       for profile in profiles]
        groups = [[profile for profile, assigned in zip(profiles, assignments)
                   if assigned == index] for index in range(len(centroids))]
        if any(not group for group in groups):
            raise ValueError("empty cluster")
        updated = [tuple(sum(profile[column] for profile in group) / len(group)
                         for column in range(width)) for group in groups]
        if updated == centroids:
            break
        centroids = updated
    inertia = sum(squared_distance(profile, centroids[assigned])
                  for profile, assigned in zip(profiles, assignments))
    return centroids, assignments, inertia

warehouses = [(1.0, 1.0), (1.2, .9), (8.0, 8.0), (8.2, 7.8)]
centroids, membership, inertia = fit_small_kmeans(
    warehouses, [(1.0, 1.0), (8.0, 8.0)])
assert membership == [0, 0, 1, 1]
assert inertia > 0

Performance and operating cost

With I iterations, N profiles, K centroids and P dimensions, the direct assignment step is O(I × N × K × P) time; group construction uses O(N × P) space. Multiple restarts multiply the fitting cost.

Common Mistakes

Do not compare inertia across different K as if lower automatically means better.
Do not ignore empty clusters or single-site segments.
Do not fit centroids on validation rows when cluster IDs feed a predictive model.