Clustering: K-Means, Hierarchical & DBSCAN

What is Clustering?

Clustering assigns data points to groups (clusters) such that points in the same cluster are more similar to each other than to points in other clusters — without using any labels. It's used for customer segmentation, anomaly detection, image compression, and as a preprocessing step for supervised learning.

K-Means Clustering

The most widely used clustering algorithm. Iteratively assigns points to the nearest centroid and updates centroids to the mean of their assigned points:

K-Means Objective (Inertia)$$J = \sum_{k=1}^K\sum_{\mathbf{x}\in C_k}\|\mathbf{x}-\boldsymbol{\mu}_k\|^2$$Minimise the total within-cluster sum of squared distances to centroids. NP-hard in general, but the Lloyd's heuristic converges fast in practice.

Python

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_blobs

# Synthetic 2D clusters
X, y_true = make_blobs(n_samples=500, centers=4, cluster_std=1.0, random_state=42)
X = StandardScaler().fit_transform(X)

# ── Elbow Method: find optimal K
inertias, silhouettes = [], []
from sklearn.metrics import silhouette_score
K_range = range(2, 11)
for k in K_range:
    km = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=42)
    labels = km.fit_predict(X)
    inertias.append(km.inertia_)
    silhouettes.append(silhouette_score(X, labels))

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))
ax1.plot(K_range, inertias, marker="o", color="#4a8fa8")
ax1.set_title("Elbow Method — Inertia vs. K")
ax1.set_xlabel("Number of Clusters K"); ax1.set_ylabel("Inertia (WCSS)")

ax2.plot(K_range, silhouettes, marker="o", color="#5c8a58")
ax2.set_title("Silhouette Score vs. K")
ax2.set_xlabel("K"); ax2.set_ylabel("Silhouette Score")
plt.tight_layout(); plt.show()

# Fit with best K (both methods agree: k=4)
km_best = KMeans(n_clusters=4, init="k-means++", n_init=10, random_state=42)
labels = km_best.fit_predict(X)

plt.figure(figsize=(7,5))
colors = ["#4a8fa8","#5c8a58","#b85c2a","#c4891a"]
for k in range(4):
    mask = labels == k
    plt.scatter(X[mask,0], X[mask,1], c=colors[k], s=20, alpha=0.7, label=f"Cluster {k}")
plt.scatter(km_best.cluster_centers_[:,0], km_best.cluster_centers_[:,1],
            marker="X", s=200, c="black", zorder=5, label="Centroids")
plt.title(f"K-Means (K=4)  Silhouette: {silhouette_score(X,labels):.3f}")
plt.legend(); plt.tight_layout(); plt.show()

⚠️

K-Means limitations: assumes spherical clusters of equal size; sensitive to outliers; must specify $K$ in advance; sensitive to initialisation (use init="k-means++" and n_init=10). Always scale features first — K-Means uses Euclidean distance.

Hierarchical Clustering

Builds a tree of clusters (dendrogram) without needing to specify $K$ upfront. Two approaches:

AgglomerativeBottom-up. Start with each point as its own cluster; repeatedly merge the two most similar clusters until one cluster remains. Most common.

DivisiveTop-down. Start with one cluster; recursively split. Less common.

Linkage: SingleDistance between closest points. Creates "chaining" — elongated clusters.

Linkage: CompleteDistance between farthest points. Tends to create compact clusters.

Linkage: AverageAverage of all pairwise distances. Good default.

Linkage: WardMinimises variance within clusters. Usually the best choice for compact, similar-sized clusters.

Python

from sklearn.cluster import AgglomerativeClustering
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

# Dendrogram — cut at any height to get K clusters
Z = linkage(X[:50], method="ward")   # use small sample for visibility
fig, ax = plt.subplots(figsize=(12, 4))
dendrogram(Z, ax=ax, color_threshold=5.0)
ax.set_title("Hierarchical Clustering Dendrogram (Ward linkage)")
ax.set_xlabel("Sample index"); ax.set_ylabel("Distance")
plt.tight_layout(); plt.show()

# Cut to get 4 clusters
agg = AgglomerativeClustering(n_clusters=4, linkage="ward")
labels_agg = agg.fit_predict(X)
print(f"Silhouette (Agglomerative): {silhouette_score(X, labels_agg):.4f}")

DBSCAN — Density-Based Clustering

DBSCAN discovers clusters of arbitrary shape and automatically identifies outliers — no need to specify $K$.

Core pointHas at least min_samples points within radius $\epsilon$.

Border pointWithin $\epsilon$ of a core point, but not a core point itself.

Noise pointNot a core point and not within $\epsilon$ of any core point. Label = -1.

Python

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
import numpy as np

X_moons, _ = make_moons(n_samples=300, noise=0.08, random_state=42)
X_moons = StandardScaler().fit_transform(X_moons)

# K-Means fails on non-spherical shapes; DBSCAN handles it naturally
fig, axes = plt.subplots(1, 2, figsize=(12, 4))

# K-Means
km = KMeans(n_clusters=2, random_state=42)
axes[0].scatter(X_moons[:,0], X_moons[:,1], c=km.fit_predict(X_moons),
               cmap="RdYlGn", s=20, alpha=0.8)
axes[0].set_title("K-Means (K=2) — fails on non-spherical data")

# DBSCAN
db = DBSCAN(eps=0.2, min_samples=5)
labels_db = db.fit_predict(X_moons)
n_clusters = len(set(labels_db)) - (1 if -1 in labels_db else 0)
noise_pts  = (labels_db == -1).sum()
axes[1].scatter(X_moons[:,0], X_moons[:,1], c=labels_db,
               cmap="RdYlGn", s=20, alpha=0.8)
axes[1].set_title(f"DBSCAN — {n_clusters} clusters, {noise_pts} noise points")

plt.tight_layout(); plt.show()

# Choosing eps: k-distance graph (use elbow of sorted distances)
from sklearn.neighbors import NearestNeighbors
nbrs = NearestNeighbors(n_neighbors=5).fit(X_moons)
distances, _ = nbrs.kneighbors(X_moons)
distances = np.sort(distances[:, -1])    # distance to 5th nearest neighbour
plt.plot(distances, color="#4a8fa8")
plt.title("k-Distance Graph — Elbow suggests eps value")
plt.xlabel("Points sorted by distance"); plt.ylabel("5th NN distance")
plt.tight_layout(); plt.show()

Choosing a Clustering Algorithm

K-MeansLarge datasets, spherical clusters, known K. Very fast — $O(mKd)$ per iteration.

HierarchicalUnknown K, want interpretable dendrogram, small-medium data. $O(m^2)$ memory.

DBSCANArbitrary-shaped clusters, outlier detection, don't know K. Sensitive to $\epsilon$ and min_samples.

Summary

K-Means: minimise inertia. Use elbow + silhouette score to pick $K$. Always scale. Use k-means++ init.
Hierarchical: dendrogram lets you choose $K$ after training. Ward linkage is usually best.
DBSCAN: density-based, arbitrary shapes, auto-detects outliers. Tune $\epsilon$ via k-distance graph.