Start learning

K-Means Clustering

Lesson 42. About 7 minutes, with a video walkthrough.

K-means splits unlabelled data into K groups. It repeatedly assigns each point to its nearest group centre, then moves each centre to the middle of its points, until nothing changes.

Your Path Through This Lesson

0 of 5 done

By the End of This Lesson You Can
  • Run the K-means loop by hand on a small example.
  • Train KMeans in scikit-learn and read its results.
  • Choose K with the elbow method.

Clustering: Grouping Without Labels

So far every model had a target to learn: pass or fail, a price, a tumour type. In unsupervised learning there is no target. We only have features, and we want to find natural groups.

Examples: grouping customers by shopping habits, grouping news articles by topic, grouping students by study patterns.

The Algorithm

  1. Choose K, the number of clusters.
  2. Place K centroids (group centres), for example at K random points.
  3. Assign: give each point to its nearest centroid.
  4. Update: move each centroid to the mean of the points assigned to it.
  5. Repeat steps 3–4 until the assignments stop changing.

K-means is trying to minimise the inertia: the total squared distance from each point to its centroid.

Watch the loop run:

By Hand

Students' weekly study hours: 1, 2, 3, 10, 11, 12. K = 2, starting centroids at 1 and 2.

Round Centroids Group A Group B New centroids
1 1, 2 1 2, 3, 10, 11, 12 1, 7.6
2 1, 7.6 1, 2, 3 10, 11, 12 2, 11
3 2, 11 1, 2, 3 10, 11, 12 2, 11 (no change: stop)

In round 1, point 3 is closer to 2 than to 1, so it joins group B. Round 2 moves the centroid to 7.6, which pulls 2 and 3 back to group A. By round 3 nothing moves, so we're done: a light-study group around 2 hours and a heavy-study group around 11.

python
import numpy as np
from sklearn.cluster import KMeans

hours = np.array([[1], [2], [3], [10], [11], [12]])
km = KMeans(n_clusters=2, init=np.array([[1], [2]]), n_init=1).fit(hours)
print("labels   :", km.labels_)
print("centroids:", km.cluster_centers_.ravel())
print("inertia  :", km.inertia_)
print("iterations:", km.n_iter_)
Output
labels   : [0 0 0 1 1 1]
centroids: [ 2. 11.]
inertia  : 4.0
iterations: 3

The inertia is : each point's squared distance to its centroid.

A Bigger Example

python
from sklearn.datasets import make_blobs

X, true_groups = make_blobs(n_samples=300, centers=4, cluster_std=0.9, random_state=1)

km = KMeans(n_clusters=4, n_init=10, random_state=0).fit(X)
print("points per cluster:", np.bincount(km.labels_))
print("centroids:\n", km.cluster_centers_.round(2))
print("cluster of a new point (0, 0):", km.predict([[0, 0]]))
Output
points per cluster: [76 75 75 74]
centroids:
 [[-7.13 -7.99]
 [-1.55  4.44]
 [-9.9  -3.92]
 [-6.23 -2.96]]
cluster of a new point (0, 0): [1]

n_init=10 runs K-means 10 times from different starting centroids and keeps the run with the lowest inertia. A bad start can land in a poor solution, so multiple starts are a cheap insurance policy. scikit-learn's default starting method, k-means++, also spreads the first centroids apart.

Choosing K: The Elbow Method

Inertia always drops as K grows (with K = number of points, it's zero). So we look for the elbow: the K after which adding clusters stops helping much.

python
for k in range(1, 8):
    inertia = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X).inertia_
    print(f"K={k}: inertia {inertia:8.1f}")
Output
K=1: inertia   9250.6
K=2: inertia   2097.3
K=3: inertia   1008.5
K=4: inertia    474.1
K=5: inertia    423.2
K=6: inertia    375.0
K=7: inertia    335.8

The inertia falls steeply up to K = 4, then flattens out. That bend is the elbow, and it matches the 4 groups we generated. Real data rarely has such a sharp elbow; the silhouette score gives a second opinion.

Limitations

Limitation Why What to do
You must choose K The algorithm can't infer it Elbow method, silhouette score, domain knowledge
Assumes round, similar-sized clusters It uses distance to a centre Try DBSCAN or hierarchical clustering
Sensitive to scale Distances are dominated by large-unit features Scale features first (StandardScaler)
Sensitive to outliers The mean is pulled by extreme points Remove outliers, or use a robust method
Watch Out

Cluster numbers are arbitrary. "Cluster 0" in one run may be "cluster 2" in another. Interpret clusters by looking at their centroids and members, not their numbers.

Try It Yourself
  1. Redo the hand example starting from centroids 10 and 12. Do you end in the same place?
  2. Run KMeans(n_clusters=3) on the blobs. Which two true groups get merged?
The Key Idea

K-means alternates two steps, assign to nearest centroid and move centroid to the mean, until stable. Choose K with the elbow method, and scale your features.

Summary

  • K-means: assign each point to the nearest centroid, move centroids to their means, repeat.
  • It minimises inertia, the total squared distance to centroids.
  • Use several starts (n_init) and k-means++ initialisation.
  • Pick K with the elbow method; scale features first.
  • Next: a clustering method that builds a whole tree of groups, hierarchical clustering.