Clustering: What k-Means Is Optimising and When DBSCAN Is Better

k-means is taught as "group similar points together." The algorithm is simple. What is less obvious is what objective it is optimising, why the solution depends on initialisation, why it fails on non-convex clusters, and why the number of clusters k is not just a hyperparameter — it is a modelling assumption. DBSCAN solves different problems entirely. Knowing which algorithm fits which data shape is the real skill.

Clustering is unsupervised — there is no ground truth to optimise against. This makes algorithm choice consequential: different algorithms impose different assumptions about what a "cluster" is. Using k-means on data with non-spherical clusters gives you an answer that looks confident but is wrong.

k-means: the objective function

k-means minimises the within-cluster sum of squared distances (WCSS): min_{C_1,...,C_k, μ_1,...,μ_k} Σ_{i=1}^{k} Σ_{x ∈ C_i} ||x - μ_i||^2. Each cluster C_i has centroid μ_i (the mean of its members). The algorithm iterates: assign each point to the nearest centroid, then update centroids to be the mean of their assigned points. This is guaranteed to converge (WCSS decreases monotonically) but to a local minimum, not the global one.

The objective assumes clusters are spherical (Euclidean distance to centroid), similarly sized (equal variance in all directions), and separated by roughly equal distances between centroids. When data violates these assumptions, k-means will still produce k clusters — they just won't be the meaningful ones.

Initialisation: why k-means++ matters

Random initialisation of centroids leads to poor local minima frequently. k-means++ chooses initial centroids probabilistically: first centroid is chosen uniformly at random; each subsequent centroid is chosen with probability proportional to its squared distance from the nearest already-chosen centroid. This initialisation spreads centroids across the data space and consistently finds better solutions in fewer iterations. k-means++ is the default in scikit-learn and should always be used.

Choosing k: inertia, silhouette, and the elbow

WCSS decreases monotonically with k (k=n means every point is its own cluster, WCSS=0). The elbow method plots WCSS vs k and looks for an inflection point where marginal reduction diminishes. The silhouette score measures how similar each point is to its own cluster vs other clusters: s(i) = (b(i) - a(i)) / max(a(i), b(i)), where a(i) is average distance to same-cluster points and b(i) is average distance to nearest-cluster points. s ∈ [-1, 1]; higher is better. Plot silhouette score vs k — the peak often indicates the natural number of clusters.

DBSCAN: density-based clustering

DBSCAN (Ester et al., 1996) defines clusters as dense regions separated by sparse regions. Parameters: ε (neighbourhood radius), min_samples (minimum points in a neighbourhood for a point to be a core point). Core point: has ≥ min_samples neighbours within distance ε. Cluster: maximal set of mutually density-reachable core points (and their neighbourhood points).

DBSCAN advantages: discovers clusters of arbitrary shape (not just spherical). Automatically determines the number of clusters. Identifies noise points (points not in any cluster — often interesting outliers). Does not require specifying k.

When to use DBSCAN over k-means: data has non-convex shapes (crescents, rings, S-curves), you have noise/outliers to identify, you do not know k.

Gaussian Mixture Models: soft clustering with full covariance

GMM models data as drawn from K Gaussian distributions: P(x) = Σ_{k} π_k N(x; μ_k, Σ_k). Training via EM (Expectation-Maximisation): E-step computes posterior P(cluster k | x); M-step updates μ_k, Σ_k, π_k. Unlike k-means, GMM allows ellipsoidal clusters (full Σ_k) and gives soft assignments (probabilities rather than hard memberships). GMM generalises k-means: when all covariances are spherical and equal, GMM reduces to k-means. The Bayesian Information Criterion (BIC) or AIC provides a principled way to choose K in GMM.

Hierarchical clustering: no need to specify k upfront

Agglomerative hierarchical clustering starts with each point as its own cluster and iteratively merges the most similar pair. The result is a dendrogram — a tree of merges. Cutting the dendrogram at different heights gives different numbers of clusters. Linkage criteria (how distance between clusters is computed): single linkage (min distance, produces elongated "chaining" clusters), complete linkage (max distance, produces compact spherical clusters), Ward linkage (minimises WCSS increase per merge, similar to k-means).

Try on Colab: generate four datasets: (1) spherical clusters, (2) elongated ellipses, (3) concentric rings, (4) crescent shapes. Apply k-means, GMM, and DBSCAN to each. Visualise the cluster assignments. Only DBSCAN handles rings and crescents correctly. GMM handles ellipses correctly. k-means handles only spherical clusters. This exercise makes the assumption-shape-algorithm alignment concrete and memorable.