Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 40 ยท Unsupervised Learning

Hierarchical Clustering and DBSCAN

Cluster non-round data with scikit-learn: agglomerative clustering and linkage, dendrograms, DBSCAN density clustering with eps and min_samples, plus Gaussian mixtures.

K-means is quick, but it forces round, similar-sized clusters and needs k up front. Other algorithms relax those rules. This lesson covers three families you will meet most often:

  • Agglomerative (hierarchical) clustering, which builds a tree of merges.
  • DBSCAN, which finds dense regions of any shape and labels sparse points as noise.
  • Gaussian mixture models, which give soft, probabilistic cluster membership.

Agglomerative clustering

Start with every point as its own cluster. Repeatedly merge the two closest clusters until only the requested number remain (or one big cluster). "Closest" depends on the linkage:

Linkage Distance between clusters Typical effect
ward Merge that least increases within-cluster variance Compact, similar-sized clusters (default)
complete Largest pairwise distance Compact clusters
average Mean pairwise distance In between
single Smallest pairwise distance Can follow chains and thin shapes
Python AgglomerativeClustering with different linkages

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On two interleaved crescents, single linkage follows each crescent as a chain and recovers them; the compact-cluster methods (ward, k-means) cut straight through. There is no universally best linkage: it must match the shape you expect.

Agglomerative clustering has no predict for new points; it only labels the data you fit. It also scales poorly (memory grows with the square of the number of samples), so use it on thousands, not millions, of rows.

Dendrograms

The merge history is a tree called a dendrogram. Cutting it at a height gives a number of clusters. SciPy draws it (see the SciPy hierarchy lesson if you want details); here is the idea with a small dataset.

Python Dendrogram of a small dataset

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look for long vertical lines: merging across them joins very different groups, so cutting just below them gives natural clusters. Alternatively give scikit-learn a distance_threshold (with n_clusters=None) and it will choose the number for you.

DBSCAN: clusters from density

DBSCAN (density-based spatial clustering) has two parameters:

  • eps: the radius of a neighborhood.
  • min_samples: how many points (including itself) a neighborhood needs to count as dense.

A point with at least min_samples neighbors within eps is a core point. Core points that are close together join one cluster; points near a core point but not core themselves are border points; everything else is noise and gets the label -1.

DBSCAN point types

Core Dense neighborhood.
Border Near a core, but sparse itself.
Noise Belongs to no cluster (-1).

Clusters grow by chaining core points together.

1 / 2
Python DBSCAN on crescents with noise

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Too small an eps shatters the data into many tiny clusters and lots of noise; too large merges everything. A practical way to pick eps is the k-distance plot: compute each point's distance to its k-th nearest neighbor (k = min_samples), sort the values, and choose eps near the knee.

Python Choosing eps with nearest-neighbor distances

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If most points have a 5-NN distance around 0.1-0.2 and a few jump much higher, an eps just above the bulk (around 0.2 here) separates clusters from noise.

Gaussian mixture models

A Gaussian mixture assumes the data comes from several bell-shaped (Gaussian) clouds, each with its own center and shape. Unlike k-means, it can model elongated clusters and gives probabilities of membership. Choose the number of components with the BIC (lower is better).

Python Gaussian mixture with BIC

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BIC should be lowest at 2 components. predict_proba returns a row of probabilities, which is useful when a point sits between clusters.

Which one should I use?

Situation Try
Roughly round clusters, big data K-means / MiniBatchKMeans
Unknown shapes, outliers present DBSCAN (or HDBSCAN, available as sklearn.cluster.HDBSCAN)
Want a tree of groupings Agglomerative
Overlapping or elongated clusters, soft labels Gaussian mixture

sklearn.cluster.HDBSCAN is a density method that handles clusters of varying density with fewer parameters than DBSCAN, worth testing when eps is hard to choose.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What label does DBSCAN give to noise points?

    Points that belong to no dense region are labeled -1.
  2. 2. Which linkage tends to recover two interleaved crescents?

    Single linkage merges by the smallest pairwise distance, so it can follow a chain of nearby points along a crescent.
  3. 3. What does increasing DBSCAN's eps do?

    A larger neighborhood radius makes more points count as dense and joins clusters that were separate.
  4. 4. What extra output does a Gaussian mixture provide over k-means?

    predict_proba gives soft assignments, and each component has its own covariance, allowing elongated clusters.

Summary

  • Agglomerative clustering merges the closest clusters bottom-up; linkage decides what "closest" means.
  • DBSCAN grows clusters from dense regions, labels noise as -1, and needs eps and min_samples.
  • Gaussian mixtures give soft, elliptical clusters; pick components with BIC.
  • Scale features, and judge results with silhouette scores, stability and domain sense.

Next: Principal Component Analysis