Clustering — K-Means | ML-101

Learning Without Labels

All the algorithms in previous modules — linear regression, decision trees, SVMs — learned from labeled examples. Someone had to tell the model that this email is spam or that this tumor is malignant. But most data in the world arrives without labels. Unsupervised learning is the branch of machine learning that finds structure in unlabeled data.

Clustering is the most fundamental unsupervised task: partition a dataset into groups such that points within the same group are more similar to each other than to points in other groups. Clustering powers customer segmentation, document organization, anomaly detection, image compression, and biological taxonomy. The challenge is that “similar” must be defined mathematically, and the number of groups may not be known in advance.

The K-Means Algorithm

K-Means is the simplest and most widely used clustering algorithm. Given a dataset of n points and a target number of clusters K, it partitions the data by alternating between two steps until convergence:

Step 1 — Assignment: Assign each point to the nearest cluster centroid. Nearest is measured by Euclidean distance. Each point belongs to exactly one cluster.

Step 2 — Update: Recompute each centroid as the mean of all points assigned to it. Move the centroid to the center of its cluster.

Repeat until the assignments stop changing. This is guaranteed to converge because each step reduces the objective function — the total within-cluster sum of squared distances — and there are only finitely many possible assignments.

K-Means Objective (Inertia)

J = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \|\mathbf{x} - \boldsymbol{\mu}_k\|^2

J is the total within-cluster sum of squares (inertia). μ_k is the centroid of cluster C_k. K-Means minimizes J iteratively — each step is guaranteed to decrease or maintain J.

K-Means converges to a local minimum, not necessarily the global one. The final result depends heavily on the initial centroid positions, which is why initialization matters enormously.

Choosing K

K is a hyperparameter that must be specified before training. Two common methods help select a good K:

The Elbow Method: Run K-Means for K = 1, 2, 3, … and plot the inertia (total within-cluster variance) against K. As K increases, inertia always decreases — eventually to zero when K equals n. The “elbow” — the point where adding more clusters yields diminishing returns — suggests a natural K. In practice this bend is often gentle and subjective.

Silhouette Score: For each point i, compute the average distance to all other points in its cluster (a(i)) and the average distance to all points in the nearest other cluster (b(i)). The silhouette score is:

Silhouette Score

s(i) = \dfrac{b(i) - a(i)}{\max\bigl(a(i),\, b(i)\bigr)}

s(i) ranges from -1 (misclassified) to +1 (perfectly clustered). A score near 0 means i is on the boundary. Average s(i) over all points gives the overall silhouette score for a given K — choose K that maximizes it.

Domain Knowledge Over Metrics

Neither the elbow method nor the silhouette score is definitive. Both are heuristics. In practice, domain knowledge — knowing that you have five product categories, or three customer tiers — is often the most reliable guide to choosing K. Use the metrics to validate your choice, not to make it blindly.

Initialization and K-Means++

Standard K-Means initializes centroids by choosing K points uniformly at random from the dataset. This is fast but fragile: a bad initialization can lead to poor local minima where clusters are clearly unnatural. A common workaround is to run K-Means multiple times with different random seeds and keep the best result (lowest inertia). Scikit-learn does this with n_init=10 by default.

A far better approach is K-Means++, a smarter initialization strategy introduced by Arthur and Vassilvitskii in 2007. Instead of placing all centroids randomly, it spreads them out:

1. Choose the first centroid uniformly at random.

2. For each subsequent centroid, choose a point with probability proportional to its squared distance from the nearest already-chosen centroid.

3. Repeat until K centroids have been placed.

K-Means++ initialization is probabilistically guaranteed to produce a solution within O(log K) of the optimal inertia. In practice it converges faster and produces far better clusters than random initialization. It is now the default in most implementations, including scikit-learn.

K-Means Limitations

K-Means is fast and scalable but carries several structural assumptions that limit its applicability:

Spherical clusters: K-Means assigns each point to its nearest centroid using Euclidean distance. This implicitly assumes clusters are roughly convex and isotropic — blob-shaped in feature space. It cannot discover elongated, curved, or irregularly shaped clusters. Two crescent-shaped distributions interleaved in 2D will confuse K-Means completely.

Equal cluster sizes: K-Means centroids are means, which are pulled toward dense regions. When clusters have very different sizes or densities, the algorithm tends to split large clusters and merge small ones. The resulting partition can be far from the true structure.

Sensitive to outliers: Means are not robust to extreme values. A single outlier can pull a centroid far from the bulk of its cluster, distorting the boundary for all nearby points.

Requires K in advance: Unlike hierarchical methods, K-Means needs K specified before training. If the true number of clusters is unknown, you must run the algorithm many times and use a selection criterion.

Assumes Euclidean distance: The algorithm uses Euclidean distance, which does not make sense for all data types. Categorical features, text, or graph-structured data require different distance functions and specialized algorithms.

Mini-Batch K-Means

Standard K-Means requires all data to fit in memory and processes the entire dataset at each iteration. For very large datasets — millions of points — this becomes prohibitively slow. Mini-Batch K-Means addresses this by updating centroids using only a random mini-batch of the data at each step, analogous to stochastic gradient descent in supervised learning.

At each iteration, a small random sample (typically 100–10,000 points) is drawn from the dataset. Each sample point is assigned to its nearest centroid, and the centroid positions are updated using a running average with a learning rate that decays over time. This dramatically reduces computation per iteration while still converging to a good solution.

The trade-off: Mini-Batch K-Means converges faster in wall-clock time but produces slightly higher inertia than full K-Means. For most practical applications with large datasets, the speed gain far outweighs the small quality loss. Scikit-learn provides MiniBatchKMeans with the same interface as standard KMeans.

Always Scale Your Features

Like SVMs, K-Means is sensitive to feature scale because it uses Euclidean distance. A feature measured in thousands (e.g., annual income) will dominate distance calculations over a feature measured in units (e.g., number of purchases). Always standardize features to zero mean and unit variance before clustering. This is one of the most common mistakes in unsupervised learning.

In the next lesson, we step beyond K-Means to explore hierarchical clustering, which builds a dendrogram of nested groupings, and DBSCAN, which discovers clusters of arbitrary shape based on local density — with no K required.

Key Takeaways

Clustering partitions unlabeled data into groups of similar points — no labels required.
K-Means alternates between assigning points to nearest centroids and updating centroids as cluster means until convergence.
The objective is to minimize inertia: total within-cluster sum of squared distances from each point to its centroid.
K-Means converges to a local minimum — initialization matters. K-Means++ spreads centroids intelligently and is now the default.
Choose K with the elbow method (inertia curve) or silhouette score; domain knowledge is often most reliable.
K-Means assumes spherical, similarly-sized clusters and is sensitive to outliers and feature scale.
Mini-Batch K-Means scales to large datasets by updating centroids on random subsamples at each iteration.