K-Means Clustering

K-means partitions $n$ points into $k$ clusters, each represented by its centroid, minimizing within-cluster variance.

Ask the Data science assistant 1 min read · Updated September 9, 2026

Definition

Algorithm: (1) initialize $k$ centroids, (2) assign each point to nearest centroid, (3) update centroids as the mean of assigned points, (4) repeat until convergence.

Converges to a local minimum — different initializations can yield different results.

Intuition

The centroid is the "representative point" of a cluster; new points are assigned to the cluster of their nearest centroid.

K-means assumes clusters are spherical and evenly sized — it struggles with elongated or unequally-sized clusters.

Worked example

With $k=3$ on customer data, you might discover clusters corresponding to "budget shoppers", "regulars", and "high spenders".

Compressing colors in an image: cluster pixel colors into $k$ palette values, then replace each pixel with its centroid.

The math

Within-cluster sum of squares: $\text{WCSS} = \sum_{j=1}^k \sum_{x \in C_j} ||x - \mu_j||^2$ .

Elbow method: plot WCSS vs $k$ ; the "elbow" where adding more clusters gives diminishing returns suggests a good $k$ .

In practice

Used for market segmentation, image quantization, and as a preprocessing step before supervised learning.

For high-dimensional data, consider PCA first to reduce dimensionality and speed up clustering.

Go deeper

InteractiveK-Means Clustering Playground

More in Data science

Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.