OPTICS

Order points by reachability distance; valleys in the reachability plot are clusters, at every density at once.

17 min read1859 wordsadvanced11 viewsupdated 2026-10-07

Definition

OPTICS (Ordering Points To Identify the Clustering Structure, Ankerst, Breunig, Kriegel & Sander, 1999) is a density-based method that does not output one clustering. It outputs an ordering of the points and a reachability distance r(p)r(p) for each one. Plotted in that order, the reachabilities form a bar chart in which every valley is a dense region. Cutting the chart at a height ε′\varepsilon' gives exactly the DBSCAN clustering at radius ε′\varepsilon', for every ε′\varepsilon' at once.

At a glance

Task
Unsupervised clustering with noise; also shows the density hierarchy
Input → output
points x1,…,xnx_1,\dots,x_n and a distance → ordering o1,…,ono_1,\dots,o_n, reachabilities r(oi)r(o_i), core distances; clusters come from a second extraction step
Learns
nothing parametric: a density-based ordering, like a minimum spanning tree walked one point at a time
Training cost
O(n2)O(n^2) distances in the worst case; about O(nlog⁡n)O(n\log n) with a spatial index and a small ε\varepsilon
Prediction cost
no native predict: refit, or attach a new point to the core point that reaches it most cheaply
Hyperparameters
min_samples (minPts), max_eps (ε), and the extraction rule: ξ (xi) or a cut height ε′
Assumes
clusters are regions denser than their surroundings; a meaningful distance (scale your features)

The problem

DBSCAN finds clusters of any shape and labels noise, but it uses one global radius ε\varepsilon. A point is "dense" only relative to that radius, so DBSCAN can only see clusters of roughly one density. When the data mixes dense and sparse groups, no single radius is right.

The worked example below makes this concrete. It has two tight unit squares AA and BB that are only 1.8 apart, and a loose square CC of side 2.5. With minPts = 3, DBSCAN with ε<1.8\varepsilon<1.8 separates AA from BB but calls every point of CC noise. Any ε≥1.8\varepsilon\ge 1.8 merges AA and BB, and CC does not appear until ε≥2.5\varepsilon\ge 2.5. You can have {A,B}\{A, B\} or {A∪B,C}\{A\cup B, C\}, but never {A,B,C}\{A, B, C\}. Rerunning DBSCAN for many radii and comparing the results is expensive and awkward.

OPTICS does the work of all those runs in one pass. It walks through the data so that, for every radius ε′≤ε\varepsilon'\le\varepsilon, each DBSCAN cluster forms one contiguous block of the walk. It then records how far each step had to reach. The result is a 1-D picture of the whole density landscape, and you can read clusters at several densities from it, including nested ones.

The idea

Think of flooding the data. Start anywhere, and always step next to the unvisited point that is cheapest to reach from the points already visited. "Cheap" means close and in a dense area. Inside a cluster every step is short, so the recorded distances stay low. The walk finishes a dense region before it leaves, because leaving costs more than any step inside. When nothing cheap is left, it has to jump across a gap, and the recorded distance spikes. Plot the recorded distances in visiting order and clusters show up as valleys separated by peaks. A shallow, high valley is a sparse cluster; a deep, low one is a dense cluster. A valley inside a wider valley is a cluster nested inside a bigger one.

Vocabulary

minPts
the density threshold min_samples: how many points (counting the point itself) must lie within a radius for that point to be dense
ε (max_eps)
the largest radius OPTICS considers. It only bounds the work; scikit-learn's default is ∞\infty
ε-neighbourhood
Nε(p)N_\varepsilon(p), every point within distance ε\varepsilon of pp, including pp
Core point
a point with at least minPts points in its ε′\varepsilon'-neighbourhood, for the radius ε′\varepsilon' in question
Core distance
core(p)\text{core}(p), the smallest radius at which pp is a core point: the distance to its minPts-th nearest neighbour (itself counted)
Reachability distance
reach(o∣q)=max⁡(core(q), d(q,o))\text{reach}(o\mid q)=\max(\text{core}(q),\,d(q,o)), the smallest radius at which oo is directly density-reachable from qq
Seed list
a priority queue of unprocessed points, keyed by their best reachability so far
Ordering
the sequence in which points leave the seed list
Predecessor
the processed point that set oo's final reachability, i.e. its parent in the walk
Reachability plot
bar ii has height r(oi)r(o_i). Valleys are clusters; the first bar of each connected piece is ∞\infty (undefined)
ξ-steep point
a place where the plot drops or rises by at least a fraction ξ\xi. Pairs of steep-down and steep-up areas bound the clusters found by the ξ extraction

The math

Fix a distance dd, a density threshold minPts, and a maximum radius ε\varepsilon. Everything follows from two quantities.

coreε(p)={d(p,  NNminPts(p))if ∣Nε(p)∣≥minPtsundefined (∞)otherwise\text{core}_{\varepsilon}(p)=\begin{cases}d\big(p,\;\text{NN}_{\text{minPts}}(p)\big) & \text{if } |N_\varepsilon(p)|\ge \text{minPts}\\ \text{undefined }(\infty) & \text{otherwise}\end{cases}
NNk(p)\text{NN}_{k}(p)
the kk-th nearest point to pp, counting pp itself as the 1st (scikit-learn's convention)
Nε(p)N_\varepsilon(p)
points within distance ε\varepsilon of pp
minPts\text{minPts}
min_samples: the density threshold

DBSCAN at radius ε′\varepsilon' calls pp a core point when ∣Nε′(p)∣≥|N_{\varepsilon'}(p)|\ge minPts. That holds exactly when ε′≥core(p)\varepsilon'\ge\text{core}(p). So the core distance is the radius at which pp becomes dense. It is small in dense regions and large in sparse ones.

reachε(o∣q)=max⁡(coreε(q),  d(q,o))\text{reach}_{\varepsilon}(o\mid q)=\max\big(\text{core}_{\varepsilon}(q),\;d(q,o)\big)
qq
an already-processed point that might pull o into its cluster
oo
an unprocessed point
d(q,o)d(q,o)
their distance

Why the max. In DBSCAN at radius ε′\varepsilon', oo is directly density-reachable from qq when (i) qq is a core point, i.e. ε′≥core(q)\varepsilon'\ge\text{core}(q), and (ii) oo lies in qq's neighbourhood, i.e. ε′≥d(q,o)\varepsilon'\ge d(q,o). Both conditions hold exactly when ε′≥max⁡(core(q),d(q,o))\varepsilon'\ge\max(\text{core}(q),d(q,o)). The reachability distance is therefore the smallest radius at which DBSCAN would put oo in qq's cluster. The max also smooths distances inside dense regions: neighbours closer than the core distance all get the same value, core(q)\text{core}(q), which keeps the plot from being jagged.

r(o)  ←  min⁡(r(o),  max⁡(core(q), d(q,o)))for all unprocessed o∈Nε(q)r(o)\;\leftarrow\;\min\Big(r(o),\;\max\big(\text{core}(q),\,d(q,o)\big)\Big)\qquad\text{for all unprocessed } o\in N_\varepsilon(q)
r(o)r(o)
the best reachability of oo from anything processed so far (starts at ∞\infty)
qq
the point just taken from the seed list; the update runs only if q is a core point

After each update the algorithm processes the unprocessed point with the smallest rr. This is Prim's minimum-spanning-tree algorithm with an asymmetric edge weight max⁡(core(q),d(q,o))\max(\text{core}(q),d(q,o)). The reachability plot lists the tree's edge weights in the order the edges were added. Like Prim, the greedy choice guarantees one property: once the walk enters a region that is connected at level ε′\varepsilon', it leaves only through an edge heavier than ε′\varepsilon'. That is the claim behind the cut rule. For any ε′≤ε\varepsilon'\le\varepsilon, the DBSCAN clusters at ε′\varepsilon' are maximal runs of the ordering in which every bar after the first is ≤ε′\le\varepsilon'.

label(oi)={same cluster as oi−1r(oi)≤ε′new clusterr(oi)>ε′ and core(oi)≤ε′noiser(oi)>ε′ and core(oi)>ε′\text{label}(o_i)=\begin{cases}\text{same cluster as } o_{i-1} & r(o_i)\le\varepsilon'\\ \text{new cluster} & r(o_i)>\varepsilon' \text{ and } \text{core}(o_i)\le\varepsilon'\\ \text{noise} & r(o_i)>\varepsilon' \text{ and } \text{core}(o_i)>\varepsilon'\end{cases}
ε′\varepsilon'
the cut height, any value ≤ε\le \varepsilon
oio_i
the i-th point of the ordering

This is scikit-learn's cluster_optics_dbscan. A tall bar ends the current cluster. The point under it either starts a new cluster (if it is dense at ε′\varepsilon') or is noise. The result matches DBSCAN at ε′\varepsilon' for every core point. Only border points can differ, because DBSCAN assigns a border point to any core neighbour, while the ordering may already have reached it from somewhere else.

steep down at i:  r(oi)(1−ξ)≥r(oi+1)steep up at i:  r(oi)≤r(oi+1)(1−ξ)\text{steep down at } i:\; r(o_i)(1-\xi)\ge r(o_{i+1})\qquad\text{steep up at } i:\; r(o_i)\le r(o_{i+1})(1-\xi)
ξ\xi
xi in (0,1)(0,1): the minimum relative drop or rise that counts as a cluster boundary

ξ extraction avoids choosing one height. It groups consecutive steep points into steep-down and steep-up areas. Every steep-down area followed later by a matching steep-up area, with at least min_cluster_size points between them, is reported as a cluster. Because valleys nest, the result is a hierarchy: scikit-learn returns it as cluster_hierarchy_, and labels_ holds the leaves.

What each hyperparameter does

minPts ↑
core(p)\text{core}(p) is the distance to a farther neighbour, so every core distance grows. Bars inside clusters rise toward the cluster's typical spacing and the plot gets smoother. Small clusters (fewer than minPts points) can no longer form valleys. In the example, minPts 3 → 4 lifts the A/B valley floor from 1 to 1.414 and the C floor from 2.5 to 3.536.
minPts ↓
the plot follows single-linkage distances more closely: more detail, but also more noise and chaining through thin bridges
ε (max_eps) ↓
only neighbours within ε\varepsilon are examined, so each region query is cheaper. Points whose minPts-th neighbour is farther than ε\varepsilon get core=∞\text{core}=\infty and are cut off. Cluster structure above ε\varepsilon is lost, and any cut must satisfy ε′≤ε\varepsilon'\le\varepsilon
ξ ↑
only sharp drops count as boundaries: fewer, more pronounced clusters
ε′ (cut height)
a horizontal line through the plot. Lower lines give more, smaller, denser clusters and more noise

Worked example: three squares and a stray point

Thirteen points with minPts = 3 and ε=∞\varepsilon=\infty. With minPts = 3 the core distance is the distance to the 2nd-nearest other point. Every point of AA and BB has two neighbours at distance 1, so its core distance is 1. Every point of CC has two at distance 2.5. The lone point NN has nearest neighbours C3C3 at 3.905 and B4B4 at 4.176, so its core distance is 4.176.

Pointxycore distance (minPts = 3)
A1001
A2101
A3011
A4111
B12.801
B23.801
B32.811
B43.811
C1802.5
C210.502.5
C382.52.5
C410.52.52.5
N554.176
The 13 points. A and B are unit squares 1.8 apart, C is a square of side 2.5, and N sits alone above them.

Running OPTICS by hand

  1. 1Start at A1. Nothing has reached it, so r(A1)=∞r(A1)=\infty and bar 1 is ∞\infty. A1 is a core point (core 1), so every other point gets r(o)=max⁡(1,d(A1,o))r(o)=\max(1,d(A1,o)): A2 = 1, A3 = 1, A4 = max⁡(1,2)=1.414\max(1,\sqrt2)=1.414, B1 = 2.8, B3 = 2.973, …, N = 7.071.
  2. 2Pop A2 (r = 1; it ties with A3 and wins on the lower index). Its updates: A4 drops to max⁡(1,1)=1\max(1,1)=1, B1 to max⁡(1,1.8)=1.8\max(1,1.8)=1.8, B3 to 2.059, N to 6.403. Pop A3 (r = 1). It improves nothing, since every remaining point is already at least as close to A1 or A2.
  3. 3Pop A4 (r = 1). It lowers B3 to max⁡(1,1.8)=1.8\max(1,1.8)=1.8 and N to 5.657. Square A is finished: bars 1–4 are ∞,1,1,1\infty,1,1,1.
  4. 4Pop B1 (r = 1.8, ties with B3, lower index). This is the first rising bar: 1.8 is the gap between the squares. B1 sets B2 = B3 = 1 and B4 = 1.414, so the walk drops back to 1 and finishes square B: B2, B3, B4 all have r = 1. Along the way B2 gives C1 r=max⁡(1,4.2)=4.2r=\max(1,4.2)=4.2, and B4 gives N r=4.176r=4.176 and C3 4.460.
  5. 5Pop N (r = 4.176). The seed list now reads N 4.176, C1 4.2, C3 4.460, and N wins by 0.024. It is a core point at its own radius (core 4.176), so it lowers C3 to max⁡(4.176, 3.905)=4.176\max(4.176,\,3.905)=4.176.
  6. 6Pop C3 (r = 4.176). It reaches C1 and C4 at max⁡(2.5,2.5)=2.5\max(2.5,2.5)=2.5 and C2 at max⁡(2.5, 3.536)=3.536\max(2.5,\,3.536)=3.536. Then C1 (2.5, the tie with C4 goes to the lower index) lowers C2 to 2.5, and C2 and C4 follow at 2.5.
  7. 7Read the plot (table below): ∞,1,1,1,  1.8,  1,1,1,  4.176,  4.176,  2.5,2.5,2.5\infty,1,1,1,\;1.8,\;1,1,1,\;4.176,\;4.176,\;2.5,2.5,2.5. There is a deep valley for A, a bump of 1.8, a deep valley for B, then a peak at N and a shallower valley for C.
PositionPointreachability rpredecessorcore distance
1A1∞—1
2A21A11
3A31A11
4A41A21
5B11.8A21
6B21B11
7B31B11
8B41B21
9N4.176B44.176
10C34.176N2.5
11C12.5C32.5
12C22.5C12.5
13C42.5C32.5
Output of OPTICS (identical to scikit-learn's ordering_ and reachability_). Highlighted: the bars that start a new valley or are noise.
ExtractionClustersNoiseWhy
cut ε′ = 1.5{A}, {B}C1–C4, NB1's bar 1.8 > 1.5 but core(B1) = 1 ≤ 1.5, so B1 starts a new cluster; C's core 2.5 > 1.5
cut ε′ = 2.0{A ∪ B}C1–C4, N1.8 ≤ 2 joins B to A; C is still not dense
cut ε′ = 3.0{A ∪ B}, {C}NN: bar 4.176 > 3 and core 4.176 > 3, so noise; C3 (core 2.5) starts C
cut ε′ = 4.5{A ∪ B ∪ C ∪ N}—every finite bar ≤ 4.5
ξ = 0.05, min_cluster_size = 3{A}, {B}, {C}Nsteep-down/steep-up pairs around each valley; hierarchy also contains A ∪ B
Cutting the same ordering at different heights. One OPTICS run reproduces DBSCAN at every radius, and the ξ method finds all three squares at once.

The ξ row is the clustering no single DBSCAN radius could give. The ξ test checks relative changes: the drop from N's 4.176 to C1's 2.5 is steep because 4.176×0.95=3.967≥2.54.176\times0.95=3.967\ge2.5, and the rise from 1 to B1's 1.8 is steep because 1≤1.8×0.95=1.711\le1.8\times0.95=1.71. So the method sees both the A/B bump and the C valley, even though they sit at different heights.

A new point Z=(9,1)Z=(9,1). OPTICS has no predict, but the same rule applies: ZZ joins whichever processed core point reaches it most cheaply. For C1 that is max⁡(core=2.5,  d=1.414)=2.5\max(\text{core}=2.5,\;d=1.414)=2.5, and C2, C3 and C4 also give 2.5. The best value from square B is 5.2 (from B4). So ZZ belongs to CC for any cut ε′≥2.5\varepsilon'\ge2.5. Refitting on all 14 points agrees: ZZ gets reachability 2.5, and the cut at 3.0 puts it in cluster CC.

▸ OPTICS · minPts = 3step 1/28
0246810A1A2A3A4B1B2B3B4C1C2C3C4N- - core distance · small numbers = current r(o)012345reachability plot · bar height = r(p), in processing orderA1A2A3A4B1B2B3B4NC3C1C2C4
output: 0/13seeds (min r first): —
  1. 1optics(X, minPts):
  2. 2 core(p) ← d(p, minPts-th NN)
  3. 3 p ← unprocessed; r(p) ← ∞
  4. 4 q ← seed with smallest r
  5. 5 output q; bar ← r(q)
  6. 6 if q is a core point:
  7. 7 for each unprocessed o:
  8. 8 m ← max(core(q), d(q,o))
  9. 9 r(o) ← min(r(o), m)
  10. 10cut plot: valleys = clusters

13 points: two dense unit squares A and B 1.8 apart, a sparse square C of side 2.5, and a lone point N. minPts = 3, ε = ∞.

▸ cut the reachability plotdrag the line · ε′ = 1.50
0246810A1A2A3A4B1B2B3B4C1C2C3C4NminPts = 3 · hollow = noise · shading = ε′-balls012345reachability plot · bar height = r(p), in processing order∞1111.81114.1764.1762.52.52.5A1A2A3A4B1B2B3B4NC3C1C2C4ε′1.50
clusters at ε′ = 1.50: A · B
noise: C1, C2, C3, C4, N
DBSCAN(ε = 1.50, minPts = 3): A · B | noise C1, C2, C3, C4, N — identical
minPts
fig.Top: OPTICS on the 13 points with minPts = 3. Each pop draws the point's core-distance circle and adds a bar to the reachability plot. Each update draws dashed arrows to the seeds whose reachability dropped (new values in orange). The final plot reads ∞, 1, 1, 1, 1.8, 1, 1, 1, 4.176, 4.176, 2.5, 2.5, 2.5, coloured by the ξ clusters A, B, C. Bottom: drag the line (or the slider) to cut the plot at ε′ and switch minPts. At ε′ = 1.5 you get A and B; at 2.0 they merge; C appears at 2.5. The readout runs a real DBSCAN at the same ε and matches, except at ε′ in [3.905, 4.176), where DBSCAN makes N a border point of C.

The algorithm, step by step

OPTICS(X, minPts, ε)

  1. 1Core distances. For each pp, query Nε(p)N_\varepsilon(p). If it has at least minPts points, set core(p)\text{core}(p) to the minPts-th smallest distance in it; otherwise ∞\infty.
  2. 2Initialise r(p)=∞r(p)=\infty and unprocessed for every point, and start with an empty ordering.
  3. 3Pick a start. Take any unprocessed point (scikit-learn takes the lowest index). Its rr stays ∞\infty, which marks the start of a new connected piece.
  4. 4Output the point qq and append (q,r(q))(q, r(q)) to the ordering.
  5. 5Expand. If core(q)<∞\text{core}(q)<\infty, then for each unprocessed o∈Nε(q)o\in N_\varepsilon(q) set r(o)←min⁡(r(o),max⁡(core(q),d(q,o)))r(o)\leftarrow\min(r(o),\max(\text{core}(q),d(q,o))), and record qq as predecessor when the value drops. Insert or decrease-key oo in the seed priority queue.
  6. 6Next. If the seed list is non-empty, pop the point with the smallest rr and go to step 4. Otherwise go to step 3, until every point is processed.
  7. 7Extract. Cut at ε′\varepsilon' (one linear scan, rule above) or run ξ extraction on the reachability sequence to get a hierarchy of clusters.

Complexity

Region queries
exactly one ε\varepsilon-neighbourhood query per point. That is O(n⋅query)O(n\cdot\text{query}): O(n2)O(n^2) by brute force, roughly O(nlog⁡n)O(n\log n) with a k-d / ball tree when ε\varepsilon is small
Seed updates
each neighbour pair triggers at most one decrease-key, O(log⁡n)O(\log n) with a heap. scikit-learn instead does a linear argmin over unprocessed points, O(n)O(n) per pop, so O(n2)O(n^2) overall
Memory
O(n)O(n) for ordering, reachability, core distance and predecessor, plus whatever the neighbour queries hold
vs DBSCAN
about the same cost as one DBSCAN run at radius ε\varepsilon (DBSCAN skips the priority queue), but it replaces a whole sweep over ε′\varepsilon'

Variants and practical tuning

MethodKnobsOutputWhen
DBSCAN cut (cluster_optics_dbscan)ε′ ≤ εflat clustering, = DBSCAN(ε′)you know the density level, or want to scan many quickly
ξ extraction (cluster_method='xi')ξ, min_cluster_sizehierarchy of valleys + leaf labelsclusters of different densities in one dataset
Read the plot by eye—insightexploration: how many density levels, how much noise
HDBSCANmin_cluster_size, min_samplesflat clusters picked by stability, plus probabilitiesyou want automatic selection; usually the stronger default today
OPTICS-OFminPtsper-point outlier factorlocal-density outlier scores, the forerunner of LOF (local outlier factor)
Ways to turn an OPTICS ordering into clusters, and related algorithms.

Tuning in practice

min_samples
start around 2d2d for dd features (at least 3–5). Raise it if the plot is jagged or tiny clusters appear; lower it if small real groups vanish
max_eps
set it to bound runtime, not to tune clusters. Too small and sparse clusters become all ∞\infty bars (noise)
xi
default 0.05. Raise to 0.1–0.3 if the ξ method splits clusters on minor wiggles
min_cluster_size
drop valleys narrower than this, given as a count or a fraction of n. Defaults to min_samples
Scaling / metric
everything is a distance, so standardise features or choose a domain metric (haversine for GPS, cosine for embeddings)
Diagnose
always plot reachability_[ordering_]. If you cannot see valleys, no extraction setting will find good clusters

In code

python
1import numpy as np
2
3def optics(X, min_pts=3, max_eps=np.inf):
4 n = len(X)
5 D = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1)) # O(n^2) distances
6 core = np.sort(D, axis=1)[:, min_pts - 1] # min_pts-th neighbour, the point itself included
7 core[core > max_eps] = np.inf # not a core point within max_eps
8 reach = np.full(n, np.inf)
9 pred = np.full(n, -1)
10 done = np.zeros(n, bool)
11 order = []
12 for _ in range(n):
13 todo = np.flatnonzero(~done)
14 q = todo[np.argmin(reach[todo])] # seed with smallest reachability (ties: lowest index)
15 done[q] = True
16 order.append(q)
17 if np.isinf(core[q]):
18 continue # non-core points expand nothing
19 nb = np.flatnonzero((D[q] <= max_eps) & ~done)
20 new = np.maximum(core[q], D[q, nb]) # reachability-distance from q
21 better = new < reach[nb]
22 reach[nb[better]] = new[better]
23 pred[nb[better]] = q
24 return np.array(order), reach, core, pred
25
26def extract_dbscan(order, reach, core, eps):
27 """DBSCAN clusters at radius eps <= max_eps, read straight off the ordering."""
28 labels, c = np.full(len(order), -1), -1
29 for q in order:
30 if reach[q] > eps: # a jump: q is not reachable from the current cluster
31 if core[q] <= eps:
32 c += 1
33 labels[q] = c # ... but it is dense enough to start a new one
34 else:
35 labels[q] = c
36 return labels
37
38X = np.array([[0,0],[1,0],[0,1],[1,1],[2.8,0],[3.8,0],[2.8,1],[3.8,1],
39 [8,0],[10.5,0],[8,2.5],[10.5,2.5],[5,5]], float)
40names = np.array("A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 N".split())
41
42order, reach, core, pred = optics(X, min_pts=3)
43print("order:", " ".join(names[order]))
44print("reach:", np.round(reach[order], 3))
45print("core: ", np.round(core[order], 3))
46for eps in (1.5, 2.0, 3.0):
47 print(f"eps'={eps}:", extract_dbscan(order, reach, core, eps))
48
49# order: A1 A2 A3 A4 B1 B2 B3 B4 N C3 C1 C2 C4
50# reach: [ inf 1. 1. 1. 1.8 1. 1. 1. 4.176 4.176 2.5 2.5 2.5 ]
51# core: [1. 1. 1. 1. 1. 1. 1. 1. 4.176 2.5 2.5 2.5 2.5 ]
52# eps'=1.5: [ 0 0 0 0 1 1 1 1 -1 -1 -1 -1 -1]
53# eps'=2.0: [ 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1]
54# eps'=3.0: [ 0 0 0 0 0 0 0 0 1 1 1 1 -1]
From scratch in NumPy: core distances, the greedy reachability walk, and the DBSCAN cut. It reproduces the tables above.
python
1import numpy as np
2from sklearn.cluster import OPTICS, DBSCAN, cluster_optics_dbscan
3
4X = np.array([[0,0],[1,0],[0,1],[1,1],[2.8,0],[3.8,0],[2.8,1],[3.8,1],
5 [8,0],[10.5,0],[8,2.5],[10.5,2.5],[5,5]], float)
6names = np.array("A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 N".split())
7
8opt = OPTICS(min_samples=3, max_eps=np.inf, cluster_method="xi", xi=0.05,
9 min_cluster_size=3).fit(X)
10print("order:", " ".join(names[opt.ordering_]))
11print("reach:", np.round(opt.reachability_[opt.ordering_], 3))
12print("xi labels:", opt.labels_)
13print("xi hierarchy (ordering positions):", opt.cluster_hierarchy_.tolist())
14
15# one OPTICS run -> DBSCAN at any eps, for free
16for eps in (1.5, 2.0, 3.0):
17 lab = cluster_optics_dbscan(reachability=opt.reachability_, core_distances=opt.core_distances_,
18 ordering=opt.ordering_, eps=eps)
19 print(f"eps'={eps}:", lab)
20
21# what a single DBSCAN radius can do
22for eps in (1.0, 1.79, 1.8, 2.49, 2.5):
23 print(f"DBSCAN eps={eps}:", DBSCAN(eps=eps, min_samples=3).fit(X).labels_)
24
25# order: A1 A2 A3 A4 B1 B2 B3 B4 N C3 C1 C2 C4
26# reach: [ inf 1. 1. 1. 1.8 1. 1. 1. 4.176 4.176 2.5 2.5 2.5 ]
27# xi labels: [ 0 0 0 0 1 1 1 1 2 2 2 2 -1] <- A, B, C, and N is noise
28# xi hierarchy (ordering positions): [[0, 3], [4, 7], [0, 7], [9, 12], [0, 12]]
29# eps'=1.5: [ 0 0 0 0 1 1 1 1 -1 -1 -1 -1 -1]
30# eps'=2.0: [ 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1]
31# eps'=3.0: [ 0 0 0 0 0 0 0 0 1 1 1 1 -1]
32# DBSCAN eps=1.0: [ 0 0 0 0 1 1 1 1 -1 -1 -1 -1 -1]
33# DBSCAN eps=1.79: [ 0 0 0 0 1 1 1 1 -1 -1 -1 -1 -1]
34# DBSCAN eps=1.8: [ 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1]
35# DBSCAN eps=2.49: [ 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1]
36# DBSCAN eps=2.5: [ 0 0 0 0 0 0 0 0 1 1 1 1 -1]
scikit-learn on the worked example: ξ clusters, the hierarchy, free DBSCAN cuts, and the DBSCAN radius sweep that cannot find all three squares.

Use when

  • +Clusters have different densities, or are nested inside each other, so no single DBSCAN radius works.
  • +You want to see the density structure before committing: the reachability plot is a compact, 1-D summary of any dimensionality.
  • +You need many DBSCAN clusterings at different radii: one OPTICS run gives them all.
  • +Arbitrary shapes and explicit noise are required, and the number of clusters is unknown.

Avoid when

  • −You want flat clusters chosen automatically with soft membership: HDBSCAN is usually better and faster.
  • −n is large and max_eps cannot be bounded: the default is quadratic in time.
  • −Data is high-dimensional, where distances concentrate and density loses meaning: reduce dimensionality first.
  • −Clusters are Gaussian blobs of similar size: k-means or a Gaussian mixture is simpler and gives centres or probabilities.

Where it's used

Astronomy

Finding star clusters and galaxy groups in survey catalogues, where densities differ by orders of magnitude and groups nest inside larger groups.

Geospatial hotspots

GPS traces, crime or ride-hailing pickups with a haversine metric. A dense downtown and sparse suburbs show up as separate valleys.

Cytometry and single-cell data

Cell populations and sub-populations of very different sizes and densities in marker or embedding space.

Exploratory analysis and outliers

Plot the reachability to see how many density levels a dataset has before choosing an algorithm. Tall isolated bars, as with OPTICS-OF, flag outliers.

Check yourself

With minPts = 3, a processed point qq has core distance 1.0. An unprocessed point oo lies at distance 0.6 from qq and currently has r(o)=1.4r(o)=1.4. After expanding qq, r(o)r(o) is…

Check yourself

An ordering of 11 points has reachabilities ∞,0.5,0.4,0.5,3.0,0.8,0.7,0.9,5.0,2.0,2.2\infty,0.5,0.4,0.5,3.0,0.8,0.7,0.9,5.0,2.0,2.2 and core distances 0.5,0.5,0.4,0.5,0.8,0.7,0.7,0.8,2.0,2.0,2.20.5,0.5,0.4,0.5,0.8,0.7,0.7,0.8,2.0,2.0,2.2. How many clusters does the cut at ε′=2.5\varepsilon'=2.5 give?

Check yourself

In the worked example, why is no single DBSCAN radius able to return A, B and C as three clusters (minPts = 3)?

Check yourself

What does the first bar of the reachability plot (and the first bar of each disconnected piece) show, and why?

Remember

  • ✓Core distance = the radius at which a point becomes dense (distance to its minPts-th neighbour, itself counted). Reachability max⁡(core(q),d(q,o))\max(\text{core}(q),d(q,o)) = the smallest radius at which oo joins qq's cluster.
  • ✓OPTICS is Prim's algorithm on reachability distances: always expand the cheapest unprocessed point, and record the cost as that point's bar.
  • ✓Valleys in the reachability plot are clusters; deeper means denser, and valleys nest. Cutting at ε′ reproduces DBSCAN(ε′) up to border points, for every ε′ ≤ ε, from one run.
  • ✓ξ extraction finds clusters at different densities from relative steep drops and rises; check it against the plot and watch the last point.
  • ✓minPts smooths the plot and sets the smallest cluster; max_eps only bounds the work, but the default ∞ costs O(n²).
← back to ML Algorithms roadmap