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 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 gives exactly the DBSCAN clustering at radius , for every at once.
At a glance
- Task
- Unsupervised clustering with noise; also shows the density hierarchy
- Input → output
- points and a distance → ordering , reachabilities , 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
- distances in the worst case; about with a spatial index and a small
- 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 . 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 and that are only 1.8 apart, and a loose square of side 2.5. With minPts = 3, DBSCAN with separates from but calls every point of noise. Any merges and , and does not appear until . You can have or , but never . 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 , 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
- ε-neighbourhood
- , every point within distance of , including
- Core point
- a point with at least minPts points in its -neighbourhood, for the radius in question
- Core distance
- , the smallest radius at which is a core point: the distance to its minPts-th nearest neighbour (itself counted)
- Reachability distance
- , the smallest radius at which is directly density-reachable from
- 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 's final reachability, i.e. its parent in the walk
- Reachability plot
- bar has height . Valleys are clusters; the first bar of each connected piece is (undefined)
- ξ-steep point
- a place where the plot drops or rises by at least a fraction . Pairs of steep-down and steep-up areas bound the clusters found by the ξ extraction
The math
Fix a distance , a density threshold minPts, and a maximum radius . Everything follows from two quantities.
- the -th nearest point to , counting itself as the 1st (scikit-learn's convention)
- points within distance of
min_samples: the density threshold
DBSCAN at radius calls a core point when minPts. That holds exactly when . So the core distance is the radius at which becomes dense. It is small in dense regions and large in sparse ones.
- an already-processed point that might pull o into its cluster
- an unprocessed point
- their distance
Why the max. In DBSCAN at radius , is directly density-reachable from when (i) is a core point, i.e. , and (ii) lies in 's neighbourhood, i.e. . Both conditions hold exactly when . The reachability distance is therefore the smallest radius at which DBSCAN would put in 's cluster. The max also smooths distances inside dense regions: neighbours closer than the core distance all get the same value, , which keeps the plot from being jagged.
- the best reachability of from anything processed so far (starts at )
- 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 . This is Prim's minimum-spanning-tree algorithm with an asymmetric edge weight . 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 , it leaves only through an edge heavier than . That is the claim behind the cut rule. For any , the DBSCAN clusters at are maximal runs of the ordering in which every bar after the first is .
- the cut height, any value
- 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 ) or is noise. The result matches DBSCAN at 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.
xiin : 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 ↑
- 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 are examined, so each region query is cheaper. Points whose minPts-th neighbour is farther than get and are cut off. Cluster structure above is lost, and any cut must satisfy
- ξ ↑
- 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 . With minPts = 3 the core distance is the distance to the 2nd-nearest other point. Every point of and has two neighbours at distance 1, so its core distance is 1. Every point of has two at distance 2.5. The lone point has nearest neighbours at 3.905 and at 4.176, so its core distance is 4.176.
| Point | x | y | core distance (minPts = 3) |
|---|---|---|---|
| A1 | 0 | 0 | 1 |
| A2 | 1 | 0 | 1 |
| A3 | 0 | 1 | 1 |
| A4 | 1 | 1 | 1 |
| B1 | 2.8 | 0 | 1 |
| B2 | 3.8 | 0 | 1 |
| B3 | 2.8 | 1 | 1 |
| B4 | 3.8 | 1 | 1 |
| C1 | 8 | 0 | 2.5 |
| C2 | 10.5 | 0 | 2.5 |
| C3 | 8 | 2.5 | 2.5 |
| C4 | 10.5 | 2.5 | 2.5 |
| N | 5 | 5 | 4.176 |
Running OPTICS by hand
- 1Start at A1. Nothing has reached it, so and bar 1 is . A1 is a core point (core 1), so every other point gets : A2 = 1, A3 = 1, A4 = , B1 = 2.8, B3 = 2.973, …, N = 7.071.
- 2Pop A2 (r = 1; it ties with A3 and wins on the lower index). Its updates: A4 drops to , B1 to , 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.
- 3Pop A4 (r = 1). It lowers B3 to and N to 5.657. Square A is finished: bars 1–4 are .
- 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 , and B4 gives N and C3 4.460.
- 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 .
- 6Pop C3 (r = 4.176). It reaches C1 and C4 at and C2 at . 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.
- 7Read the plot (table below): . 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.
| Position | Point | reachability r | predecessor | core distance |
|---|---|---|---|---|
| 1 | A1 | ∞ | — | 1 |
| 2 | A2 | 1 | A1 | 1 |
| 3 | A3 | 1 | A1 | 1 |
| 4 | A4 | 1 | A2 | 1 |
| 5 | B1 | 1.8 | A2 | 1 |
| 6 | B2 | 1 | B1 | 1 |
| 7 | B3 | 1 | B1 | 1 |
| 8 | B4 | 1 | B2 | 1 |
| 9 | N | 4.176 | B4 | 4.176 |
| 10 | C3 | 4.176 | N | 2.5 |
| 11 | C1 | 2.5 | C3 | 2.5 |
| 12 | C2 | 2.5 | C1 | 2.5 |
| 13 | C4 | 2.5 | C3 | 2.5 |
| Extraction | Clusters | Noise | Why |
|---|---|---|---|
| cut ε′ = 1.5 | {A}, {B} | C1–C4, N | B1'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, N | 1.8 ≤ 2 joins B to A; C is still not dense |
| cut ε′ = 3.0 | {A ∪ B}, {C} | N | N: 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} | N | steep-down/steep-up pairs around each valley; hierarchy also contains A ∪ B |
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 , and the rise from 1 to B1's 1.8 is steep because . So the method sees both the A/B bump and the C valley, even though they sit at different heights.
A new point . OPTICS has no predict, but the same rule applies: joins whichever processed core point reaches it most cheaply. For C1 that is , and C2, C3 and C4 also give 2.5. The best value from square B is 5.2 (from B4). So belongs to for any cut . Refitting on all 14 points agrees: gets reachability 2.5, and the cut at 3.0 puts it in cluster .
- 1optics(X, minPts):
- 2 core(p) ← d(p, minPts-th NN)
- 3 p ← unprocessed; r(p) ← ∞
- 4 q ← seed with smallest r
- 5 output q; bar ← r(q)
- 6 if q is a core point:
- 7 for each unprocessed o:
- 8 m ← max(core(q), d(q,o))
- 9 r(o) ← min(r(o), m)
- 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, ε = ∞.
The algorithm, step by step
OPTICS(X, minPts, ε)
- 1Core distances. For each , query . If it has at least minPts points, set to the minPts-th smallest distance in it; otherwise .
- 2Initialise and unprocessed for every point, and start with an empty ordering.
- 3Pick a start. Take any unprocessed point (scikit-learn takes the lowest index). Its stays , which marks the start of a new connected piece.
- 4Output the point and append to the ordering.
- 5Expand. If , then for each unprocessed set , and record as predecessor when the value drops. Insert or decrease-key in the seed priority queue.
- 6Next. If the seed list is non-empty, pop the point with the smallest and go to step 4. Otherwise go to step 3, until every point is processed.
- 7Extract. Cut at (one linear scan, rule above) or run ξ extraction on the reachability sequence to get a hierarchy of clusters.
Complexity
- Region queries
- exactly one -neighbourhood query per point. That is : by brute force, roughly with a k-d / ball tree when is small
- Seed updates
- each neighbour pair triggers at most one decrease-key, with a heap. scikit-learn instead does a linear argmin over unprocessed points, per pop, so overall
- Memory
- 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 (DBSCAN skips the priority queue), but it replaces a whole sweep over
Variants and practical tuning
| Method | Knobs | Output | When |
|---|---|---|---|
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_size | hierarchy of valleys + leaf labels | clusters of different densities in one dataset |
| Read the plot by eye | — | insight | exploration: how many density levels, how much noise |
| HDBSCAN | min_cluster_size, min_samples | flat clusters picked by stability, plus probabilities | you want automatic selection; usually the stronger default today |
| OPTICS-OF | minPts | per-point outlier factor | local-density outlier scores, the forerunner of LOF (local outlier factor) |
Tuning in practice
- min_samples
- start around for 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 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
1import numpy as np23def 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) distances6 core = np.sort(D, axis=1)[:, min_pts - 1] # min_pts-th neighbour, the point itself included7 core[core > max_eps] = np.inf # not a core point within max_eps8 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] = True16 order.append(q)17 if np.isinf(core[q]):18 continue # non-core points expand nothing19 nb = np.flatnonzero((D[q] <= max_eps) & ~done)20 new = np.maximum(core[q], D[q, nb]) # reachability-distance from q21 better = new < reach[nb]22 reach[nb[better]] = new[better]23 pred[nb[better]] = q24 return np.array(order), reach, core, pred2526def 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), -129 for q in order:30 if reach[q] > eps: # a jump: q is not reachable from the current cluster31 if core[q] <= eps:32 c += 133 labels[q] = c # ... but it is dense enough to start a new one34 else:35 labels[q] = c36 return labels3738X = 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())4142order, 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))4849# order: A1 A2 A3 A4 B1 B2 B3 B4 N C3 C1 C2 C450# 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]1import numpy as np2from sklearn.cluster import OPTICS, DBSCAN, cluster_optics_dbscan34X = 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())78opt = 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())1415# one OPTICS run -> DBSCAN at any eps, for free16for 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)2021# what a single DBSCAN radius can do22for 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_)2425# order: A1 A2 A3 A4 B1 B2 B3 B4 N C3 C1 C2 C426# 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 noise28# 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]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_epscannot 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 has core distance 1.0. An unprocessed point lies at distance 0.6 from and currently has . After expanding , is…
Check yourself
An ordering of 11 points has reachabilities and core distances . How many clusters does the cut at 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 = the smallest radius at which joins '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²).