K-Means Clustering
K-means is the most popular clustering algorithm: it splits unlabelled data into k groups so that points in the same group are close to each other. Businesses use it to find customer segments, and analysts use it to discover structure they didn't know was there.
The algorithm
K-means represents each cluster by its centre, called a centroid. It repeats two simple steps:
- Initialise: choose k starting centroids.
- Assign: put every point in the cluster of its nearest centroid.
- Update: move each centroid to the mean (average position) of the points assigned to it.
- Repeat steps 2 and 3 until the assignments stop changing.
The goal is to minimise inertia: the sum of squared distances from each point to its centroid. Every assign or update step can only lower (or keep) the inertia, so the algorithm always settles down.
A worked example by hand
Six numbers: 1, 2, 3, 8, 9, 10, with k = 2. Suppose we start with poor centroids, c₁ = 1 and c₂ = 2.
| Iteration | Assign | Update |
|---|---|---|
| 1 | Cluster 1: {1}. Cluster 2: {2, 3, 8, 9, 10} (each is closer to 2 than to 1) | c₁ = 1; c₂ = (2 + 3 + 8 + 9 + 10) / 5 = 6.4 |
| 2 | 2 is 1 away from c₁ but 4.4 from c₂; 3 is 2 away vs. 3.4. Cluster 1: {1, 2, 3}. Cluster 2: {8, 9, 10} | c₁ = 2; c₂ = 9 |
| 3 | No point changes cluster | Converged |
Final inertia: (1−2)² + 0 + (3−2)² + (8−9)² + 0 + (10−9)² = 4. Even from a bad start, two iterations found the obvious groups.
K-means in scikit-learn
Here are six customers described by visits per month and spend per visit (thousands of KES):
import numpy as np
from sklearn.cluster import KMeans
X = np.array([[1, 2], [2, 1], [3, 3],
[8, 8], [9, 10], [10, 9]])
km = KMeans(n_clusters=2, n_init=10, random_state=42)
km.fit(X)
order = np.argsort(km.cluster_centers_[:, 0]) # sort centres for a stable display
print(km.cluster_centers_[order])
print(f"Inertia: {km.inertia_:.1f}")
The centres are the averages of each group: (1 + 2 + 3) / 3 = 2 and (2 + 1 + 3) / 3 = 2 for the first group; (8 + 9 + 10) / 3 = 9 and (8 + 10 + 9) / 3 = 9 for the second. Each group contributes 4 to the inertia, for a total of 8. The cluster numbers in km.labels_ (0 or 1) are arbitrary, which is why we sorted the centres before printing.
scikit-learn uses the k-means++ initialisation by default, which spreads the starting centroids out, and n_init=10 runs the whole algorithm 10 times from different starts and keeps the run with the lowest inertia. This protects against a bad start getting stuck in a poor solution.
Choosing k
K-means needs you to choose k. Two common tools:
- Elbow method: fit k = 1, 2, 3, … and plot inertia. Inertia always falls as k grows, so look for the "elbow" where it stops falling steeply. For the six customers above, k = 1 gives an inertia of 155 and k = 2 gives 8; larger k only shaves off a little more. The elbow is clearly at 2.
- Silhouette score (
sklearn.metrics.silhouette_score): measures how well each point fits its own cluster compared with the next nearest. It ranges from −1 to 1; higher is better.
Business sense matters too: a marketing team may only be able to act on three or four segments.
Limitations
- Needs scaling: it uses distances, so standardise features first (see Feature Scaling).
- Assumes round, similar-sized clusters. Long, curved or very uneven clusters confuse it; algorithms such as DBSCAN handle these better.
- Sensitive to outliers, because one extreme point can drag a centroid towards it.
- Always produces k clusters, even if the data has no real groups.
Treating clusters as truth. K-means will happily split random noise into groups. Check that clusters are stable (similar results with different seeds), make sense to people who know the domain, and are useful for a decision before acting on them.
Key points
- K-means alternates between assigning points to the nearest centroid and moving centroids to the mean.
- It minimises inertia, the sum of squared distances to centroids.
- Pick k with the elbow method, silhouette score and domain knowledge.
- Scale features first, and remember it prefers round clusters.
Tip: use the ← and → keys to move between pages.
