Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 39 ยท Clustering

Density-Based and Grid-Based Clustering

Learn density-based clustering with DBSCAN (eps, min_samples, core, border and noise points), choosing eps, OPTICS for varying density, and grid-based methods like STING and CLIQUE.

k-means assumes round clusters and forces every record into one. Real data often has crescents, rings and stray noise points. Density-based clustering defines a cluster as a region where records are packed closely together, separated from other regions by sparse space. It finds arbitrary shapes, needs no k and labels noise explicitly.

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) has two parameters:

  • eps: the radius of the neighborhood around a record.
  • min_samples (MinPts): how many records must lie inside that radius for the area to count as dense.

Every record is then one of three kinds:

  • Core point: at least min_samples records (itself included) within eps.
  • Border point: not a core point, but within eps of a core point.
  • Noise point: neither; it belongs to no cluster (label -1).

A cluster is a maximal set of core points that can reach each other through chains of neighbors, plus their border points. "Density-reachable" means you can hop from core point to core point, each hop shorter than eps.

Three kinds of points

Core Dense neighborhood
Border Near a core point
Noise Isolated, no cluster

Clusters grow by hopping from core point to core point.

1 / 2

DBSCAN from scratch

Python DBSCAN in 25 lines

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.

The isolated point keeps label -1. Compare with scikit-learn and see what happens on shapes where k-means fails.

Python DBSCAN versus k-means on rings

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.

Choosing eps

A practical trick: compute each record's distance to its min_samples-th nearest neighbor, sort the values, and look for the knee where they start to climb steeply. Values beyond the knee belong to noise, so eps is the distance at the knee.

Python The k-distance plot as numbers

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.

The distances stay small for most records and jump near the top, where the noise points live. Pick eps around the point where the curve bends.

Strengths and weaknesses

  • Finds clusters of any shape and handles noise.
  • Does not need k, but needs eps and min_samples.
  • A single eps cannot fit clusters with very different densities.
  • High dimensions make distances nearly equal and break the notion of density.

OPTICS and varying density

OPTICS does not produce one clustering; it orders the records and records each one's reachability distance. Valleys in the reachability plot are clusters, and deep valleys are dense ones. Cutting at different heights gives what DBSCAN would return for different eps values, so OPTICS handles varying density. HDBSCAN goes further and builds a hierarchy of DBSCAN results, choosing stable clusters automatically.

Python OPTICS on clusters with different density

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.

With one eps about a quarter of the records, mostly from the sparse blob, are labeled noise; OPTICS keeps almost all of both blobs because it adapts to each blob's density.

Grid-based clustering

Grid-based methods divide the space into a finite number of cells and work on cells, not records. The running time depends on the number of cells, not the number of records, which makes them very fast on huge data.

  • STING divides space into a hierarchy of rectangular cells and stores statistics (count, mean, min, max, distribution) in each. A query descends the hierarchy from coarse to fine cells, skipping irrelevant ones.
  • CLIQUE is both grid-based and density-based and finds clusters in subspaces of high-dimensional data: it keeps cells with enough records, then joins adjacent dense cells.
  • WaveCluster applies a wavelet transform to the cell counts to find dense regions at several resolutions.
Python A mini grid clustering

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.

The result is only as fine as the cell size: large cells are fast but coarse, tiny cells give detail but many cells.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In DBSCAN, what is a core point?

    Core points have a dense neighborhood; clusters grow by connecting core points.
  2. 2. What label does scikit-learn's DBSCAN give to noise?

    Noise records receive the label -1.
  3. 3. Why use OPTICS instead of DBSCAN?

    A single eps cannot suit both dense and sparse clusters; OPTICS keeps reachability distances for all scales.
  4. 4. Why are grid-based methods fast on huge datasets?

    After one pass counting records per cell, all work is done on the cells.

Summary

  • Density-based clustering grows clusters through dense regions: DBSCAN uses eps and min_samples, labels noise as -1 and finds arbitrary shapes.
  • Use a k-distance curve to pick eps; use OPTICS or HDBSCAN when densities vary.
  • Grid-based methods (STING, CLIQUE, WaveCluster) cluster cells instead of records for speed.

Next: Evaluating Clusters