Patterns › Clustering

K-means clustering

k-means clustering partitions n observations into k clusters by minimising total within-cluster squared distance to the cluster centroid.

What is K-means clustering?

Iterative algorithm: pick k random centroids, assign each point to its nearest, recompute centroids as the mean of assigned points, repeat until assignments stabilise. The objective Σ_k Σ_{i ∈ C_k} ||xᵢ − μ_k||² decreases at every step.

Strengths: fast, scales to large n, gives hard cluster assignments with interpretable centroids. Weaknesses: assumes spherical equal-variance clusters (use model-based / two-step clustering for elliptical clusters), needs k pre-specified, sensitive to outliers, depends on random initialisation (run with nstart > 1 to stabilise).

Compared to hierarchical clustering: k-means is faster and works on millions of rows; hierarchical gives you a dendrogram that lets you pick k visually. Compared to DBSCAN: k-means assigns every point to a cluster (no noise class) and assumes globular shapes; DBSCAN handles arbitrary shapes and identifies outliers as noise.

When should I use K-means clustering?

  • Large datasets where the number of clusters is approximately known.
  • When the cluster shapes are roughly spherical and equal-variance.
  • Pair with the Elbow plot (scree of total within-SS vs k) to pick k.
  • Switch to hclust when you want a dendrogram and the data is small-to-medium.
  • Switch to DBSCAN when clusters are non-globular or you need automatic noise detection.

What data does it need?

≥ 2 numeric features + k + standardise toggle + nstart (random restarts).

What does it report?

Cluster labels per row, centroids, within-cluster sum of squares per cluster, total SS, between SS / total SS = variance explained.

What does it assume?

  • Roughly spherical, equal-variance clusters.
  • All features on comparable scales — standardise unless they're already unit-matched.
  • k pre-specified.

Formula

minimise Σ_k Σ_{i ∈ C_k} ||xᵢ − μ_k||² subject to a partition into k clusters

How do I interpret the result?

Run with nstart ≥ 10 to avoid bad local minima.

Inspect per-cluster centroids on the original (un-standardised) scale to interpret what each cluster represents.

See also

References

  • MacQueen (1967). Some methods for classification and analysis of multivariate observations. 5th Berkeley Symposium.