Clustering Algorithms: K-Means, DBSCAN and Hierarchical

Clustering groups records that are similar without being told what the groups are: customers who shop alike, products that sell together, sensor readings that behave the same way. There is no single best algorithm, because each one encodes an assumption about what a cluster looks like. Choose an algorithm whose assumption matches your data, and clustering works; choose one whose assumption does not, and it confidently returns nonsense. This guide shows both outcomes on two small datasets.

Three algorithms, three ideas of a cluster

• K-means places k centres and assigns each point to the nearest one, moving the centres until they settle. It assumes clusters are roughly round, similar in size, and that you know k (scikit-learn: clustering).
• DBSCAN defines clusters as dense regions: a point with at least min_samples neighbours within distance eps is a core point, and connected core points form a cluster. It finds clusters of any shape, does not need k, and labels points in sparse regions as noise (scikit-learn: DBSCAN).
• Hierarchical (agglomerative) clustering starts with every point alone and repeatedly merges the two closest clusters, producing a tree you can cut at any level. The linkage decides what "closest" means: ward merges to keep clusters compact, much like k-means, while single joins clusters through their nearest points and can follow long, thin shapes.

Where each succeeds and fails

Two synthetic datasets with known answers make the differences visible: three round blobs, and two interlocking crescents ("moons"). The adjusted Rand index compares each clustering with the truth, from 1 for a perfect match to around 0 for chance (scikit-learn: adjusted_rand_score).

from sklearn.cluster import DBSCAN, AgglomerativeClustering, KMeans
from sklearn.datasets import make_blobs, make_moons
from sklearn.metrics import adjusted_rand_score, silhouette_score
from sklearn.preprocessing import StandardScaler

X_blobs, y_blobs = make_blobs(n_samples=600, centers=3, cluster_std=1.0, random_state=42)
X_moons, y_moons = make_moons(n_samples=600, noise=0.06, random_state=1)

for name, X, y, k in [("blobs", X_blobs, y_blobs, 3), ("moons", X_moons, y_moons, 2)]:
    X = StandardScaler().fit_transform(X)
    labels = {
        "k-means": KMeans(n_clusters=k, n_init=10, random_state=0).fit_predict(X),
        "DBSCAN": DBSCAN(eps=0.3, min_samples=5).fit_predict(X),
        "ward": AgglomerativeClustering(n_clusters=k, linkage="ward").fit_predict(X),
        "single": AgglomerativeClustering(n_clusters=k, linkage="single").fit_predict(X),
    }
    print(name, {m: round(adjusted_rand_score(y, l), 2) for m, l in labels.items()})

blobs {'k-means': 1.0, 'DBSCAN': 1.0, 'ward': 1.0, 'single': 1.0}
moons {'k-means': 0.48, 'DBSCAN': 1.0, 'ward': 0.58, 'single': 1.0}

On round, well-separated blobs, every method recovers the three groups. On the moons, k-means and ward linkage split the data with a roughly straight boundary, cutting each crescent in half, because they look for compact, round groups. DBSCAN and single linkage follow the curved shapes perfectly. Nothing in k-means' output warns you of this: it always returns k tidy-looking groups.

How many clusters? The silhouette score

K-means and ward linkage need k in advance. The silhouette score measures how much closer each point is to its own cluster than to the next one, averaged over all points, from -1 to 1 (scikit-learn: silhouette_score). Try a range of k and compare:

X = StandardScaler().fit_transform(X_blobs)
print({k: round(silhouette_score(X, KMeans(n_clusters=k, n_init=10, random_state=0).fit_predict(X)), 3)
       for k in range(2, 6)})

{2: 0.686, 3: 0.843, 4: 0.679, 5: 0.522}

The score peaks at 3, the true number. On real data the peak is rarely this clear, and the silhouette favours round, well-separated clusters, so it can mislead on shapes like the moons. Treat it as one input alongside whether the resulting groups make sense to someone who knows the domain.

Scaling decides the result

Every one of these algorithms measures distance, so features on large scales dominate. Cluster customers on annual spend (thousands of rupees) and number of visits (single digits) without scaling, and the clusters are simply spend bands; visits barely register. Standardise features first, as the code above does with StandardScaler, and consider which features to include at all: every feature you add is a dimension along which "similar" is judged.

Choosing an algorithm

DBSCAN's weak spot is its parameters: eps depends on the scale and density of your data. A common heuristic is to plot each point's distance to its k-th nearest neighbour, sorted, and pick eps near the elbow of that curve.

From clusters to decisions: a segmentation in outline

A typical customer segmentation runs like this. Choose a handful of behavioural features that the business can act on, such as recency of last purchase, purchase frequency, average order value and share of discounted orders. Handle skew, for example with a log transform of spend, then standardise. Run k-means for a range of k and read the silhouette scores alongside the cluster profiles: the average of each feature per cluster. Name each cluster in plain words, such as "frequent, full-price buyers" or "lapsed discount hunters", and check the names with the people who will use them. Only then decide actions per segment, and track whether they change behaviour differently across segments, which is the real test of a segmentation.

Judging clusters without labels

In real projects there is no ground truth to compute an adjusted Rand index against. Judge clusters by whether they are stable (rerun with different seeds or a subsample and see whether the groups hold), distinct (compare feature averages per cluster; if two clusters look the same, merge them) and useful (can someone act differently for each group?). A segmentation that marketing cannot describe in a sentence per segment is rarely worth deploying.

Clustering sits alongside the supervised methods in top machine learning algorithms explained, and high-dimensional data often benefits from dimensionality reduction first. K-means, hierarchical clustering and DBSCAN are covered in the unsupervised part of the machine learning module of the Data Science course.

Sources

• Clustering (scikit-learn user guide) — scikit-learn documentation
• sklearn.metrics.silhouette_score — scikit-learn documentation
• sklearn.metrics.adjusted_rand_score — scikit-learn documentation
• sklearn.cluster.DBSCAN — scikit-learn documentation