K-Means Clustering

What you will learn in this lesson:

• How K-means works, traced through its two alternating steps
• Why the algorithm is guaranteed to converge, and why it isn't guaranteed to find the best possible clustering
• How to choose K using the elbow method
• Why feature scaling matters for K-means, for the same reason it mattered for KNN
• How to fit K-means in Python and inspect the resulting clusters

Clustering: Finding Structure Without Labels

Every algorithm so far in this course has been supervised: every training example came with a known correct answer. K-means is the first genuinely unsupervised algorithm in this course. There are no labels at all. The only goal is to discover groups of similar points that already exist in the data.

Concretely, imagine a retailer with purchase histories for thousands of customers but no pre-existing notion of "customer segments." K-means can group those customers into K clusters based purely on purchasing patterns, without ever being told what a "good" segment looks like in advance.

The Algorithm: Two Steps, Repeated

You choose K, the number of clusters, up front. K-means then alternates between two simple steps until nothing changes:

1. Assignment step. Assign every point to whichever of the K cluster centers (called centroids) it is currently closest to, using Euclidean distance.
2. Update step. Move each centroid to the mean position of all the points currently assigned to it.

Repeat both steps. Points may switch clusters as the centroids move, and centroids move again as the assignments change. Eventually, the assignments stop changing entirely, and the algorithm has converged.

A Worked Example, by Hand

Take four points on a number line: 1, 2, 9, and 10, with K=2. Start with two badly placed initial centroids at 2 and 10. The assignment step computes each point's distance to both centroids:

The update step moves each centroid to the mean of its assigned points: Cluster A's new centroid is (1 + 2) / 2 = 1.5, and Cluster B's new centroid is (9 + 10) / 2 = 9.5. Running the assignment step again with these updated centroids produces the exact same grouping, since every point is still closer to its own cluster's centroid than to the other one. Nothing changes, so the algorithm has converged after a single update.

Why It's Guaranteed to Converge, but Not Guaranteed to Be Optimal

Both steps can only ever decrease, or leave unchanged, the total squared distance between points and their assigned centroid. Assigning each point to its nearest centroid can't increase that total, and moving a centroid to the mean of its points is mathematically the position that minimizes squared distance to exactly those points. Since this quantity can't increase and there are only finitely many ways to partition the data, the process must eventually stop changing.

What it doesn't guarantee is finding the globally best clustering. K-means is sensitive to where the centroids start. A bad initialization can converge to a clustering that's clearly worse than another arrangement the algorithm could have found from a different starting point. In practice, scikit-learn's default n_init=10 runs the whole algorithm 10 times from different random starting points and keeps the best result, which makes landing in a clearly bad local arrangement far less likely.

Choosing K: the Elbow Method

K-means needs you to choose K in advance, and there's no single formula that tells you the "correct" number of clusters, because that depends on what structure is actually in the data and what you intend to do with the result. A common heuristic is the elbow method: run K-means for a range of K values, plot the total within-cluster squared distance (called inertia) against K, and look for the point where adding more clusters stops producing a meaningfully large drop in inertia.

Inertia always decreases as K increases (more clusters can always fit the data at least as well), down to zero when K equals the number of points. The elbow method isn't looking for the minimum, it's looking for diminishing returns: the point where the curve bends and adding another cluster buys you much less improvement than the previous one did.

Why Feature Scaling Matters Here Too

K-means assigns points based on Euclidean distance, exactly like KNN. A feature with a much larger numeric range will dominate that distance calculation and effectively decide the clustering on its own, regardless of whether it's actually the most meaningful feature for grouping the data. Standardizing every feature before clustering is standard practice for the same reason it mattered for KNN: it ensures every feature contributes comparably to the notion of "closeness."

K-Means in Python

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

# Generate synthetic data with 3 well-separated true groups
X, true_labels = make_blobs(n_samples=300, centers=3, cluster_std=1.0, random_state=42)

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Try several values of K and print inertia for each (the elbow method)
print("K  | inertia")
for k in range(1, 7):
    model = KMeans(n_clusters=k, n_init=10, random_state=0)
    model.fit(X_scaled)
    print(f"{k}  | {model.inertia_:.1f}")

# Fit the final model with K=3 and inspect cluster sizes
final_model = KMeans(n_clusters=3, n_init=10, random_state=0)
labels = final_model.fit_predict(X_scaled)
print("\nPoints per cluster:", np.bincount(labels))

Looking at the printed inertia values, you should see a sharp drop from K=1 to K=2 to K=3, then a much smaller drop from K=3 onward. That's the elbow, and it should land close to 3, matching the true number of groups the synthetic data was generated with.

Limitations Worth Knowing

K-means assumes clusters are roughly spherical and similarly sized, because it's built entirely around distance to a single central point. It struggles with clusters that are elongated, nested, or very different in size or density. It's also sensitive to outliers, since a single far-away point can pull a centroid noticeably toward it. These aren't reasons to avoid K-means, since it's fast and often good enough, but they're reasons to plot your clusters and sanity-check them rather than trusting the labels blindly.