Ask K-Means to group your data and it always answers with neat round blobs, even when the real groups are long trails or clusters of wildly different sizes. That is where hierarchical clustering and DBSCAN earn their keep. This guide walks through both: dendrograms that let you cut a tree into any number of clusters, density-based discovery for odd shapes, and a clear rule for picking the right tool for the job.

“Clustering is in the eye of the beholder.”

Jain & Dubes, Algorithms for Clustering Data

Last Updated: July 2026 | Tested on: Python 3.14.6, scikit-learn 1.9.0 | Difficulty: Advanced | Reading Time: 16 minutes

K-Means assumes your clusters are round blobs of roughly equal size. That guess works more often than you would expect, but the real world does not always play along. Customer activity often forms long stretched-out trails. Map data bunches up along coastlines and highways. Online communities come in wildly different sizes. Force a round shape onto data that is not round, and the answer goes from slightly off to plain wrong.

Think of seating guests at a wedding. K-Means is like deciding “we will have exactly 5 round tables” before anyone arrives, then squeezing people into the nearest table whether they fit or not. Hierarchical clustering is more like building a family tree first: it records who is closest to whom, and you decide how many groups you want after you can see the whole tree. DBSCAN is the host who walks the room and spots tight knots of people chatting, then quietly leaves the two loners by the bar as “nobody’s group” instead of forcing them onto a table.

Here is the short version. Hierarchical clustering gives you a tree of merges, called a dendrogram, that you can cut at any height to get any number of clusters. You never have to pick K upfront. DBSCAN clusters by density: it finds regions where points are packed tightly together, separated by sparse gaps. It happily discovers oddly shaped clusters and labels the leftover sparse points as noise.

Prerequisites

Two Different Philosophies

The diagram lays the two approaches side by side. On the hierarchical side, every point starts as its own cluster, then the two closest clusters keep merging until only one remains. That history of merges is the dendrogram, and its height axis records the distance at which each merge happened. On the DBSCAN side, the algorithm walks point by point, asking “do you have enough neighbours nearby to count as dense?”, growing a cluster outward from each dense core and tagging the lonely points as noise. The big win over K-Means is on the left: you get to choose the number of clusters after you have seen the whole tree, instead of guessing K before you start.

Hierarchical Clustering: Building a Dendrogram

Agglomerative clustering starts with every point as its own cluster, then keeps merging the two closest clusters until only one is left. The result is a dendrogram, a tree that records every merge and the distance at which it happened. Picture a knockout tournament bracket, but read upside down: the players at the bottom are your data points, and each round joins the closest pair into a bigger group. You cut the tree at a chosen height to get any number of clusters, and you never have to run the algorithm again to try a different number.

The word “closest” hides an important choice. How do you measure the distance between two groups of points, not just two single points? That rule is called the linkage method. Ward merges the pair that adds the least extra variance. Complete uses the farthest pair of points. Average uses the mean distance. Single uses the closest pair. The script below runs all four on the same data so you can see how much the choice matters.

📄 hierarchical_demo.py: linkage methods compared

import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import linkage
from sklearn.metrics import silhouette_score

# Blobs with real overlap so the linkage method actually changes the result
X, y_true = make_blobs(n_samples=150, centers=3, cluster_std=2.0, random_state=42)

linkage_methods = ["ward", "complete", "average", "single"]

print("Linkage Method   | Silhouette Score")
print("-----------------|------------------")
for method in linkage_methods:
    agg = AgglomerativeClustering(n_clusters=3, linkage=method)
    labels = agg.fit_predict(X)
    score = silhouette_score(X, labels)
    print(f"{method:<17}| {score:.4f}")

# Dendrogram merge heights via scipy
Z = linkage(X, method="ward")
print(f"\nLast 3 merge distances (Ward linkage):")
for i in range(-3, 0):
    row = Z[i]
    print(f"  Merge at distance {row[2]:.2f}, resulting cluster size: {int(row[3])}")

▶ Output

Linkage Method   | Silhouette Score
-----------------|------------------
ward             | 0.6855
complete         | 0.6855
average          | 0.6874
single           | 0.3633

Last 3 merge distances (Ward linkage):
  Merge at distance 17.82, resulting cluster size: 49
  Merge at distance 69.59, resulting cluster size: 101
  Merge at distance 118.41, resulting cluster size: 150

What happened here: Ward, complete, and average all landed in the same healthy range (around 0.69), so on roundish blobs any of them is a safe pick. Ward is the usual default because it minimizes total within-cluster variance, the same goal as K-Means, just without fixing K first. Single linkage fell off a cliff to 0.36. Single linkage "chains": it merges on the single closest pair of points between two clusters, so one stray point sitting between groups can stitch them together too early.

The merge distances tell the same story from another angle. The jump from 17.82 to 69.59, then again to 118.41, is huge. Those last two merges are joining clusters that are genuinely far apart, which is the tree's way of saying "stop at 3 clusters." Cut the dendrogram just below that big jump and you get the three blobs.

DBSCAN: Density-Based Clustering

DBSCAN treats a cluster as a crowd: a dense patch of points surrounded by emptier space. Two knobs control it. Epsilon (eps) is the neighbourhood radius, basically "how close counts as nearby." minPts is the minimum number of neighbours a point needs to sit inside a dense patch. A core point has at least minPts neighbours within epsilon, so it is firmly in the crowd. A border point hangs at the edge of a core point's reach but does not have enough neighbours of its own. Everything left over, the points standing alone in the empty space, gets labelled noise.

Here is the part people get wrong, so let me show it honestly. The natural instinct is to score clusters with the silhouette score, the same metric we used above. But silhouette quietly assumes clusters are round, so on crescents it actually rewards K-Means for cutting the data into two neat halves, even though those halves slice straight through the real shapes. To judge fairly, we compare each method against the true crescent labels using the Adjusted Rand Index (ARI), where 1.0 means a perfect match. That is the difference between "looks tidy" and "is actually right."

📄 dbscan_demo.py: crescent-shaped clusters with noise

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score

# Crescent-shaped clusters that K-Means cannot handle
X, y_true = make_moons(n_samples=300, noise=0.08, random_state=42)
X = StandardScaler().fit_transform(X)

# Add 15 outliers far from both crescents (true label -1 = noise)
rng = np.random.default_rng(42)
outliers = rng.uniform(-3, 3, size=(15, 2))
X_all = np.vstack([X, outliers])
y_all = np.concatenate([y_true, np.full(15, -1)])

# DBSCAN: density-based, finds crescents and flags outliers as noise
db_labels = DBSCAN(eps=0.3, min_samples=10).fit_predict(X_all)
n_clusters = len(set(db_labels)) - (1 if -1 in db_labels else 0)
n_noise = (db_labels == -1).sum()

# K-Means: forced to carve space into 2 round regions
km_labels = KMeans(n_clusters=2, random_state=42, n_init=10).fit_predict(X_all)

# Compare to the TRUE crescent labels with Adjusted Rand Index (1.0 = perfect)
db_ari = adjusted_rand_score(y_all, db_labels)
km_ari = adjusted_rand_score(y_all, km_labels)

print(f"DBSCAN : {n_clusters} clusters, {n_noise} noise points, ARI vs truth = {db_ari:.4f}")
print(f"K-Means: 2 clusters, 0 noise points, ARI vs truth = {km_ari:.4f}")
print(f"\nDBSCAN recovers the crescents better: {db_ari > km_ari}")

▶ Output

DBSCAN : 2 clusters, 15 noise points, ARI vs truth = 0.9735
K-Means: 2 clusters, 0 noise points, ARI vs truth = 0.4342

DBSCAN recovers the crescents better: True

What happened here: DBSCAN nailed it. It traced both crescent shapes and flagged all 15 outliers as noise, scoring 0.97 against the true labels (1.0 would be perfect). K-Means managed only 0.43, because it has to split the space into two round regions and ends up slicing each crescent in half and swallowing the outliers into clusters. Notice the trap we avoided: if we had graded with the silhouette score instead, K-Means would have looked like the winner, purely because silhouette prefers round clusters.

The lesson is twofold. DBSCAN shines on arbitrary shapes with noise, and the metric you grade with has to match the shape of your data. DBSCAN does have a real weakness though: when clusters have very different densities, some tight and some spread out, a single epsilon cannot fit them all.

Choosing Epsilon for DBSCAN

Epsilon is the one setting that makes or breaks DBSCAN, so do not guess it. Think of drawing neighbourhoods on a city map: epsilon is how wide you draw each circle. Draw them too small and every house becomes its own island; draw them too big and the entire city collapses into one giant neighbourhood. There is a tidy trick called the k-distance plot. For every point, measure the distance to its k-th nearest neighbour, then sort all those distances from small to large and look for the "elbow," the spot where the curve suddenly shoots upward.

Points before the elbow live inside dense crowds with close neighbours. Points after it are the loners out in empty space. The distance at the elbow is a solid starting value for epsilon. The script below does the measuring and points you near the elbow.

📄 k_distance_plot.py: finding the right epsilon

from sklearn.neighbors import NearestNeighbors
import numpy as np

X = np.random.default_rng(42).normal(size=(200, 2))

# k-distance graph: sort distances to k-th nearest neighbor
nn = NearestNeighbors(n_neighbors=10)
nn.fit(X)
distances, _ = nn.kneighbors(X)
k_distances = np.sort(distances[:, -1])

print("k-distance statistics (10th nearest neighbor):")
print(f"  Min:    {k_distances[0]:.3f}")
print(f"  Median: {k_distances[len(k_distances)//2]:.3f}")
print(f"  Max:    {k_distances[-1]:.3f}")
print(f"  Suggested eps: around {k_distances[len(k_distances)//2]:.2f} (near the knee)")

▶ Output

k-distance statistics (10th nearest neighbor):
  Min:    0.259
  Median: 0.388
  Max:    2.257
  Suggested eps: around 0.39 (near the knee)

What happened here: For this standard-normal data, most points sit within about 0.39 of their 10th neighbour, which is the flat part of the curve where the crowd lives. The maximum jumps all the way to 2.257, the lonely outliers on the far edge. That gap between the typical distance and the extreme is exactly the elbow you are hunting for. Starting epsilon around 0.39 is a sensible first try. Treat it as a starting point, not gospel: nudge it up if too much gets tagged as noise, nudge it down if separate crowds are being glued into one blob.

Decision Guide: K-Means vs Hierarchical vs DBSCAN

Three algorithms, three personalities. Here is the cheat sheet to keep next to your monitor. Read each column as "what this method is good and bad at," then match it to the data in front of you.

📄 comparison_table.py

rows = [
    ("Need to specify K", "Yes",               "Optional (cut tree)", "No"),
    ("Cluster shape",     "Spherical only",     "Any (right linkage)", "Any shape"),
    ("Handles noise",     "No (all assigned)",  "No",                  "Yes (label=-1)"),
    ("Scalability",       "O(nk) fast",         "O(n^2 log n) slow",   "O(n log n) moderate"),
    ("Best for",          "Large, round",       "Small, hierarchical", "Irregular, noisy"),
]

print(f"{'Feature':<20} | {'K-Means':<20} | {'Hierarchical':<20} | {'DBSCAN':<20}")
print("-" * 85)
for row in rows:
    print(f"{row[0]:<20} | {row[1]:<20} | {row[2]:<20} | {row[3]:<20}")

▶ Output

Feature              | K-Means              | Hierarchical         | DBSCAN
-------------------------------------------------------------------------------------
Need to specify K    | Yes                  | Optional (cut tree)  | No
Cluster shape        | Spherical only       | Any (right linkage)  | Any shape
Handles noise        | No (all assigned)    | No                   | Yes (label=-1)
Scalability          | O(nk) fast           | O(n^2 log n) slow    | O(n log n) moderate
Best for             | Large, round         | Small, hierarchical  | Irregular, noisy

Tables are abstract, so here are four concrete jobs and the tool I would reach for first:

• Segment 2 million customers by spending into 5 tiers. Go with K-Means. The data is big, the groups are roughly round, and you already know you want 5 tiers. K-Means is the fast, boring, correct choice.
• Group 200 survey responses and you are not sure how many themes exist. Use hierarchical clustering. The dataset is small, and the dendrogram lets you eyeball 3 themes versus 5 themes without rerunning anything.
• Find hotspots in GPS pickup data where some points are random strays. Use DBSCAN. The hotspots are odd shapes, density is the whole point, and the strays should be labelled noise, not forced into a zone.
• Build a taxonomy of species from genetic distances. Use hierarchical clustering. You genuinely want the nested tree, because the tree itself is the answer.

The 10-second rule: known number of round groups and lots of data, pick K-Means. Want a tree or unsure how many clusters, pick hierarchical. Weird shapes plus real noise, pick DBSCAN. When two of them seem to fit, run both and compare against a metric that suits your data shape, the way we used ARI on the crescents above.

Common Mistakes

❌ Mistake: Using hierarchical clustering on large datasets

# Agglomerative clustering needs the full pairwise distance matrix: O(n^2) memory.
# That n-by-n matrix is the same size no matter how many features you have.
# For 100,000 points (float64): 100000 * 100000 * 8 bytes, about 75 GB.
# That will not fit in RAM. Use BIRCH or Mini-Batch K-Means for large datasets.

n = 100_000
memory_gb = (n ** 2 * 8) / (1024 ** 3)
print(f"Distance matrix for {n:,} points: {memory_gb:.0f} GB")
print(f"Use sklearn.cluster.Birch or MiniBatchKMeans instead.")

▶ Output

Distance matrix for 100,000 points: 75 GB
Use sklearn.cluster.Birch or MiniBatchKMeans instead.

Why this bites: agglomerative clustering compares every point with every other point, so memory grows with the square of the row count. Ten times more rows means a hundred times more memory. The crash does not warn you politely; your kernel just dies. Above roughly 10,000 rows, switch to BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) or Mini-Batch K-Means, both of which live in sklearn.cluster.

❌ Mistake: Running DBSCAN on unscaled features

# age ranges 0-80, income ranges 0-200000. One epsilon cannot fit both.
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
import numpy as np

raw = np.array([[25, 30000], [27, 32000], [55, 120000], [58, 125000]], dtype=float)

# WRONG: income dwarfs age, so distance is basically "income only"
wrong = DBSCAN(eps=3.0, min_samples=2).fit_predict(raw)

# RIGHT: scale first so age and income carry equal weight
scaled = StandardScaler().fit_transform(raw)
right = DBSCAN(eps=1.0, min_samples=2).fit_predict(scaled)

print("Unscaled labels:", wrong)
print("Scaled labels:  ", right)

▶ Output

Unscaled labels: [-1 -1 -1 -1]
Scaled labels:   [0 0 1 1]

Why this bites: DBSCAN measures distance, and distance is meaningless when one column is in the thousands and another is in the tens. On the raw data, income drowns out age completely, so every point looks far from every other point and the whole set comes back as noise (all -1). Scale the features first and the two age-income groups pop right out as clusters 0 and 1. This applies to K-Means and hierarchical clustering too: scale before you cluster, every time.

Practice Exercises

1. Cut the tree yourself. Take the blobs from the first script, build the linkage matrix with scipy.cluster.hierarchy.linkage, then use fcluster to cut it into 2, 3, and 4 clusters. Confirm that cutting at 3 gives the cleanest silhouette score.
2. Break DBSCAN, then fix it. Run the crescents demo with eps=0.1 and count how many points get tagged as noise. Now run the k-distance plot, read the elbow, and pick a better epsilon. Watch the noise count drop.
3. Pick the right tool. Generate three datasets with scikit-learn: make_blobs, make_moons, and blobs with very different densities. Run K-Means, hierarchical, and DBSCAN on each, score every result against the true labels with adjusted_rand_score, and write one sentence per dataset on which algorithm won and why.

Conclusion

You now have two clustering tools that reach where K-Means cannot. Hierarchical clustering builds a dendrogram you can cut at any height, so you decide the number of clusters after seeing the whole tree instead of guessing upfront. DBSCAN clusters by density, traces odd shapes like crescents, and honestly labels stray points as noise instead of forcing them into a group. You also picked up the two habits that separate a clean result from a mess: scale your features before you cluster, and grade with a metric that matches your data shape, the way ARI beat silhouette on the crescents.

Next up is Principal Component Analysis (PCA), where you squeeze many columns down to a handful without losing the story in the data, which also makes clustering faster and far easier to visualize. For the full path from basics to production, browse the Python + AI/ML tutorial series home.

Frequently Asked Questions

Interview Questions on Hierarchical Clustering and DBSCAN

Scenario questions, not trivia: this is the form this topic takes in a real interview.

Q: What is a dendrogram, and how do you decide the number of clusters from it?

A dendrogram is the tree of merges that hierarchical clustering produces, with the vertical axis showing the distance at which each merge happened. You pick the number of clusters by cutting the tree horizontally at a chosen height, and cutting just below a large vertical gap gives well-separated clusters. Because the whole tree is built only once, you can try different cut heights without rerunning the algorithm.

Q: How does DBSCAN differ fundamentally from K-Means?

K-Means assigns every point to the nearest of K centroids, so it needs K upfront and assumes round clusters. DBSCAN defines clusters as dense regions separated by sparse gaps, so it discovers the cluster count on its own, handles arbitrary shapes, and can flag sparse points as noise. K-Means never leaves a point unassigned, whereas DBSCAN routinely does.

Q: What are core, border, and noise points in DBSCAN?

A core point has at least minPts neighbours within epsilon, so it sits firmly inside a dense region. A border point falls within epsilon of a core point but lacks enough neighbours of its own to be a core point. A noise point is neither, standing alone in sparse space, and DBSCAN labels it -1.

Q: Scenario: you run DBSCAN and every point comes back with label -1. What do you check first?

First check whether you scaled your features, because an unscaled large-range column (like income next to age) dominates the distance and makes every point look far apart. Then check epsilon: it is almost certainly too small, so use a k-distance plot to find the elbow and raise eps. Also confirm minPts is not set too high for the size of your data.

Q: Scenario: your hierarchical clustering job crashes with a memory error on 200,000 rows. What is happening and what do you do?

Agglomerative clustering needs the full pairwise distance matrix, which is O(n^2) in memory, so 200,000 rows is roughly 300 GB of float64 and the kernel dies. Switch to a scalable algorithm such as BIRCH or Mini-Batch K-Means, or first shrink the data with sampling or PCA. As a rule, keep classic hierarchical clustering to a few thousand rows.

Q: Scenario: DBSCAN merges two clearly separate crowds into one cluster. What knob do you turn?

Epsilon is likely too large, so the sparse gap between the two crowds still falls inside the neighbourhood radius. Lower eps until the empty band between them exceeds the neighbourhood distance. If the two crowds have very different densities, a single eps may never fit both, so consider HDBSCAN, which adapts to variable density.

Q: When would you prefer single linkage despite its reputation for chaining?

Single linkage merges on the closest pair of points between two clusters, which chains groups together and usually hurts on round blobs. That same behaviour becomes an asset when clusters are long and thin or connected by narrow bridges, such as tracing elongated structures. If you want compact, variance-minimizing clusters instead, reach for Ward linkage.

Series: Python + AI/ML Cookbook. Part 5: Machine Learning

Further reading: for the full reference, see the official Python documentation.

Related Posts

Previous: ML: K-Means Clustering, Unsupervised Discovery

Next: ML: PCA, Dimensionality Reduction Explained

Series Home: Python + AI/ML Tutorial Series