Back to Study Material Machine Learning

K-means clustering

K-means is one of the most widely used clustering algorithms. It partitions a dataset into k groups such that each data point belongs to the group with the...

K-means clustering

Partitioning Data into Natural Groups

K-means is one of the most widely used clustering algorithms. It partitions a dataset into k groups such that each data point belongs to the group with the nearest centroid (center point), and the centroids are the average positions of all points in their respective groups. The goal is to minimize the total within-cluster variance.

The algorithm iterates between two steps. In the assignment step, each data point is assigned to the nearest centroid based on Euclidean distance. In the update step, each centroid is recalculated as the mean of all points assigned to its cluster. These steps repeat until assignments no longer change or a maximum number of iterations is reached.

Choosing k — the number of clusters — is not straightforward. The elbow method plots within-cluster sum of squares (inertia) against k. As k increases, inertia decreases because clusters become smaller and tighter. The elbow in the plot — where the rate of decrease sharply changes — suggests a natural k. The silhouette score is another metric, measuring how similar each point is to its own cluster compared to other clusters; higher is better.

K-means has limitations. It assumes spherical clusters of similar size and density. It struggles with elongated, irregular, or overlapping clusters. It is sensitive to outliers because outliers pull centroids toward them. It requires specifying k in advance. For more complex cluster shapes, DBSCAN or Gaussian Mixture Models may be more appropriate.

K-means also depends on initialization. Random centroid initialization can lead to poor local optima. K-means++ addresses this by choosing initial centroids spaced far apart, improving both speed and solution quality.

A concrete example: a retailer uses K-means with k equal to 4 to segment customers by purchase frequency and average order value, discovering four distinct segments: high-value frequent buyers, bargain hunters, occasional big spenders, and inactive accounts.

Exam tip: be able to describe the two-step iteration, name two limitations, and explain the elbow method for choosing k.