AI.Cruz
MACHINE LEARNING

OPTICS: Ordering Points to Identify Clustering Structure

OPTICS extends DBSCAN to handle clusters of varying density. Rather than outputting cluster labels directly, it produces a reachability plot — valleys are clusters, peaks are boundaries and noise.

1Why DBSCAN Fails on Variable-Density Data

DBSCAN uses a global ε (epsilon) radius. Every core point needs at least MinPts neighbours within ε. If you have two clusters — one dense and one sparse — no single ε works: too small misses the sparse cluster, too large merges everything. OPTICS solves this by not committing to a fixed ε, instead ordering points by how reachable they are from their neighbours.

DBSCAN limitation

  • ✗ Single global ε — one threshold for all clusters
  • ✗ Dense cluster requires small ε; sparse cluster needs large ε
  • ✗ Fails when cluster densities differ significantly

OPTICS solution

  • ✓ No fixed ε — uses reachability distances instead
  • ✓ Finds clusters of varying density in a single run
  • ✓ Reachability plot lets you choose thresholds post-hoc

2Core Distance and Reachability Distance

OPTICS defines two key distance measures that together capture local density:

Core distance of p (core-dist(p)): the distance from p to its MinPts-th nearest neighbour. If p has fewer than MinPts neighbours within any radius, its core distance is undefined — it is noise. Otherwise, core-dist(p) = distance to the MinPts-th closest point.

Reachability distance of q from p (reach-dist(q,p)): the maximum of core-dist(p) and the actual distance dist(p,q). Formally: reach-dist(q,p) = max(core-dist(p), dist(p,q)). This smooths out distances within a core point's neighbourhood — two points inside the same dense region have the same reachability distance (= core-dist(p)).

Intuition: reach-dist prevents artificially low distances inside a cluster. If p is a dense core point, all its close neighbours are treated as equally reachable (reach-dist = core-dist(p)). Jumping from one cluster to another causes reach-dist to spike — this spike is visible as a peak in the reachability plot.

3The Reachability Plot

OPTICS outputs a sorted ordering of all points along with their reachability distances. When you plot reachability distance (y-axis) vs. processing order (x-axis), the shape reveals cluster structure without committing to specific cluster labels:

Valleys
Low, flat regions in the plot. Points with low reachability distances are deep inside a dense cluster — these form the cluster core.
Peaks
High spikes between valleys. The transition between two clusters or between a cluster and noise causes reachability to jump — the spike is the boundary.
Flat high plateau
Noise points are scattered with no dense neighbours, so their reachability is large and roughly uniform — the plateau at the right is noise.

To extract clusters: choose a horizontal cut-off on the reachability plot (like setting ε in DBSCAN after the fact). Points below the cut are cluster members; points above are noise. OPTICS is roughly 1.6× slower than DBSCAN but handles variable-density clusters that DBSCAN cannot.

4OPTICS vs. DBSCAN vs. BIRCH

DBSCAN
Fixed ε. Fast. Best when all clusters have similar density and you know ε. Fails on variable-density data.
OPTICS
No fixed ε. ~1.6× slower than DBSCAN. Best for variable-density clusters; reachability plot helps interpret results.
BIRCH
Single-pass scan. O(n) memory. Best for massive datasets that do not fit in RAM. Assumes spherical clusters.

Related

Compute core distances and reachability distances from scratch

Recall check

0 of …

Say the answer out loud before revealing — recalling is what makes it stick. ➜ Next: Cluster Validation

  1. What does the core distance of a point p represent?

  2. Why is reachability distance defined as max(core-dist(p), dist(p,q)) rather than just dist(p,q)?

  3. How do you read clusters from an OPTICS reachability plot?

  4. When should you choose OPTICS over DBSCAN?