K-Means Clustering — Tutorial

Lloyd's algorithm: cluster by centroid

K-means partitions n data points into K clusters by minimising the within-cluster sum of squared distances. The algorithm alternates two steps:

1. Assignment: assign each point to its nearest centroid 2. Update: move each centroid to the mean of its assigned points

Repeat until centroids don't move (convergence). This minimises the objective ΣΣ ||xᵢ - μₖ||².

Initialisation matters. Random initialisation can converge to poor local minima. K-means++ initialises centroids by spreading them out probabilistically — the first centroid is chosen randomly, then each subsequent one is chosen with probability proportional to its squared distance from the nearest existing centroid. Sklearn uses K-means++ by default (init='k-means++').

K-means has complexity O(n·K·d·i) where n=points, K=clusters, d=dimensions, i=iterations. It scales well to millions of points.

Choosing K: the elbow method and silhouette score

K is a hyperparameter you choose. Two methods for finding the right K:

Elbow method: plot inertia (within-cluster sum of squares) vs K. Inertia always decreases as K increases (at K=n, each point is its own cluster and inertia=0). Look for an "elbow" — a point where adding more clusters yields diminishing returns. If the curve bends at K=3, use K=3.

Silhouette score: for each point, compare its distance to its own cluster vs the nearest other cluster. Score ranges from -1 (wrong cluster) to +1 (well-separated). Higher is better. Average over all points gives the overall quality. Use cross_val_score style iteration: compute silhouette_score(X, labels) for K=2 to 10, pick the highest.

In practice, domain knowledge often determines K: "we want 5 customer segments" or "there are 8 product categories."

Limitations and alternatives

K-means assumes clusters are spherical (roughly equal radius) and similar in size. It fails when clusters have elongated or irregular shapes, very different densities, or when there are outliers (a single outlier can pull a centroid far from the true centre).

Alternatives when K-means fails: - DBSCAN: density-based clustering, finds clusters of arbitrary shape, identifies outliers as noise. No K needed — density threshold ε and min_samples instead. - Gaussian Mixture Models (GMM): soft assignment (each point belongs to each cluster with a probability), handles elliptical clusters. - Hierarchical clustering: builds a dendrogram showing all possible clusterings from K=1 to K=n.

For production recommendation systems: K-means is often applied to user or item embeddings to create segment buckets that speed up retrieval.

Continue your research

Use these connected ModelRefs sections to compare alternatives, inspect implementation paths, and review the evidence and governance boundaries relevant to K-Means Clustering — Tutorial.

• Browse models
• Review providers
• Inspect benchmarks
• Explore workflows
• Learn AI concepts
• Read decision guides
• Review trust and methodology
• Start a decision path