# OPTICS

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

Source: https://www.mlfoundry.in/learn/optics  
Section: ML Algorithms › Unsupervised · Clustering  
Level: advanced · 17 min read · updated 2026-10-07

**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)$ 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.

- **Task:** Unsupervised clustering with noise; also shows the density hierarchy
- **Input → output:** points $x_1,\dots,x_n$ and a distance → ordering $o_1,\dots,o_n$, reachabilities $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(n^2)$ distances in the worst case; about $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 $A$ and $B$ that are only 1.8 apart, and a loose square $C$ of side 2.5. With minPts = 3, DBSCAN with $\varepsilon<1.8$ separates $A$ from $B$ but calls every point of $C$ noise. Any $\varepsilon\ge 1.8$ merges $A$ and $B$, and $C$ does not appear until $\varepsilon\ge 2.5$. You can have $\{A, B\}$ or $\{A\cup B, C\}$, but never $\{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_\varepsilon(p)$, every point within distance $\varepsilon$ of $p$, including $p$
- **Core point:** a point with at least minPts points in its $\varepsilon'$-neighbourhood, for the radius $\varepsilon'$ in question
- **Core distance:** $\text{core}(p)$, the *smallest* radius at which $p$ is a core point: the distance to its minPts-th nearest neighbour (itself counted)
- **Reachability distance:** $\text{reach}(o\mid q)=\max(\text{core}(q),\,d(q,o))$, the smallest radius at which $o$ is directly density-reachable from $q$
- **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 $o$'s final reachability, i.e. its parent in the walk
- **Reachability plot:** bar $i$ has height $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 $d$, a density threshold minPts, and a maximum radius $\varepsilon$. Everything follows from two quantities.

$$
\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}
$$

- $\text{NN}_{k}(p)$: the $k$-th nearest point to $p$, counting $p$ itself as the 1st (scikit-learn's convention)
- $N_\varepsilon(p)$: points within distance $\varepsilon$ of $p$
- $\text{minPts}$: `min_samples`: the density threshold

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

$$
\text{reach}_{\varepsilon}(o\mid q)=\max\big(\text{core}_{\varepsilon}(q),\;d(q,o)\big)
$$

- $q$: an already-processed point that might pull o into its cluster
- $o$: an unprocessed point
- $d(q,o)$: their distance

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

$$
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)$: the best reachability of $o$ from anything processed so far (starts at $\infty$)
- $q$: 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 $r$. This is **Prim's minimum-spanning-tree algorithm** with an asymmetric edge weight $\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'$.

$$
\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$
- $o_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.

$$
\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)$: 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 ↑:** $\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 $\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

> **One run, every DBSCAN:** Cutting the plot is just a linear scan, $O(n)$. After one OPTICS run, any number of DBSCAN clusterings with radii up to $\varepsilon$ cost nothing extra. Lowering the cut never merges clusters, it only splits them or turns points into noise. The family of cuts is therefore a tree of clusters, the same tree **HDBSCAN** builds and then prunes automatically.

## 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 $A$ and $B$ has two neighbours at distance 1, so its core distance is 1. Every point of $C$ has two at distance 2.5. The lone point $N$ has nearest neighbours $C3$ at 3.905 and $B4$ at 4.176, so its core distance is 4.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.

| 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**

1. **Start at A1.** Nothing has reached it, so $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))$: A2 = 1, A3 = 1, A4 = $\max(1,\sqrt2)=1.414$, B1 = 2.8, B3 = 2.973, …, N = 7.071.
2. **Pop A2** (r = 1; it ties with A3 and wins on the lower index). Its updates: A4 drops to $\max(1,1)=1$, B1 to $\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. **Pop A4** (r = 1). It lowers B3 to $\max(1,1.8)=1.8$ and N to 5.657. Square A is finished: bars 1–4 are $\infty,1,1,1$.
4. **Pop 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.2$, and B4 gives N $r=4.176$ and C3 4.460.
5. **Pop 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$.
6. **Pop C3** (r = 4.176). It reaches C1 and C4 at $\max(2.5,2.5)=2.5$ and C2 at $\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. **Read the plot** (table below): $\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.

Output of OPTICS (identical to scikit-learn's ordering_ and reachability_). Highlighted: the bars that start a new valley or are noise.

| 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 |

Cutting the same ordering at different heights. One OPTICS run reproduces DBSCAN at every radius, and the ξ method finds all three squares at once.

| 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 $4.176\times0.95=3.967\ge2.5$, and the rise from 1 to B1's 1.8 is steep because $1\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)$. OPTICS has no `predict`, but the same rule applies: $Z$ joins whichever processed core point reaches it most cheaply. For C1 that is $\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 $Z$ belongs to $C$ for any cut $\varepsilon'\ge2.5$. Refitting on all 14 points agrees: $Z$ gets reachability 2.5, and the cut at 3.0 puts it in cluster $C$.

> Figure: 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 border-point exception, in this data:** At $\varepsilon'=4$, DBSCAN puts N in cluster C, because N is within 4 of the core point C3 ($d=3.905$). The ordering reached N first from B4, at 4.176 > 4, so the cut labels N noise. Core points always agree. Border points are attached arbitrarily even in DBSCAN, which depends on the order in which it scans the points.

## The algorithm, step by step

**OPTICS(X, minPts, ε)**

1. **Core distances.** For each $p$, query $N_\varepsilon(p)$. If it has at least minPts points, set $\text{core}(p)$ to the minPts-th smallest distance in it; otherwise $\infty$.
2. **Initialise** $r(p)=\infty$ and *unprocessed* for every point, and start with an empty ordering.
3. **Pick a start.** Take any unprocessed point (scikit-learn takes the lowest index). Its $r$ stays $\infty$, which marks the start of a new connected piece.
4. **Output** the point $q$ and append $(q, r(q))$ to the ordering.
5. **Expand.** If $\text{core}(q)<\infty$, then for each unprocessed $o\in N_\varepsilon(q)$ set $r(o)\leftarrow\min(r(o),\max(\text{core}(q),d(q,o)))$, and record $q$ as predecessor when the value drops. Insert or decrease-key $o$ in the seed priority queue.
6. **Next.** If the seed list is non-empty, pop the point with the smallest $r$ and go to step 4. Otherwise go to step 3, until every point is processed.
7. **Extract.** 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\cdot\text{query})$: $O(n^2)$ by brute force, roughly $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)$ with a heap. scikit-learn instead does a linear argmin over unprocessed points, $O(n)$ per pop, so $O(n^2)$ overall
- **Memory:** $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'$

> **max_eps = ∞ means O(n²):** scikit-learn's default `max_eps=np.inf` makes every point a neighbour of every other, so no spatial index can prune anything: $n^2$ distances, and painful beyond a few tens of thousands of points. Set `max_eps` to a little above the largest density level you care about. A k-distance plot (distance to the `min_samples`-th neighbour, sorted) shows where that is.

## Variants and practical tuning

Ways to turn an OPTICS ordering into clusters, and related algorithms.

| 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 $2d$ for $d$ 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

> **ξ sometimes absorbs the last point:** Steep areas are judged between consecutive bars, and the end of the plot counts as an infinite bar. A point that comes right after a valley, especially the last point of the ordering, can get pulled into the preceding cluster. In this data, moving N to (5, 6) makes it the 13th point processed, and with every ξ setting from 0.05 to 0.4 scikit-learn then labels it part of C. Check ξ results against the plot, and cross-check with a DBSCAN cut.

## In code

```python
import numpy as np

def optics(X, min_pts=3, max_eps=np.inf):
    n = len(X)
    D = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(-1))   # O(n^2) distances
    core = np.sort(D, axis=1)[:, min_pts - 1]       # min_pts-th neighbour, the point itself included
    core[core > max_eps] = np.inf                   # not a core point within max_eps
    reach = np.full(n, np.inf)
    pred = np.full(n, -1)
    done = np.zeros(n, bool)
    order = []
    for _ in range(n):
        todo = np.flatnonzero(~done)
        q = todo[np.argmin(reach[todo])]            # seed with smallest reachability (ties: lowest index)
        done[q] = True
        order.append(q)
        if np.isinf(core[q]):
            continue                                # non-core points expand nothing
        nb = np.flatnonzero((D[q] <= max_eps) & ~done)
        new = np.maximum(core[q], D[q, nb])         # reachability-distance from q
        better = new < reach[nb]
        reach[nb[better]] = new[better]
        pred[nb[better]] = q
    return np.array(order), reach, core, pred

def extract_dbscan(order, reach, core, eps):
    """DBSCAN clusters at radius eps <= max_eps, read straight off the ordering."""
    labels, c = np.full(len(order), -1), -1
    for q in order:
        if reach[q] > eps:                          # a jump: q is not reachable from the current cluster
            if core[q] <= eps:
                c += 1
                labels[q] = c                       # ... but it is dense enough to start a new one
        else:
            labels[q] = c
    return labels

X = np.array([[0,0],[1,0],[0,1],[1,1],[2.8,0],[3.8,0],[2.8,1],[3.8,1],
              [8,0],[10.5,0],[8,2.5],[10.5,2.5],[5,5]], float)
names = np.array("A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 N".split())

order, reach, core, pred = optics(X, min_pts=3)
print("order:", " ".join(names[order]))
print("reach:", np.round(reach[order], 3))
print("core: ", np.round(core[order], 3))
for eps in (1.5, 2.0, 3.0):
    print(f"eps'={eps}:", extract_dbscan(order, reach, core, eps))

# order: A1 A2 A3 A4 B1 B2 B3 B4 N C3 C1 C2 C4
# reach: [  inf 1.    1.    1.    1.8   1.    1.    1.    4.176 4.176 2.5   2.5   2.5  ]
# core:  [1.    1.    1.    1.    1.    1.    1.    1.    4.176 2.5   2.5   2.5   2.5  ]
# eps'=1.5: [ 0  0  0  0  1  1  1  1 -1 -1 -1 -1 -1]
# eps'=2.0: [ 0  0  0  0  0  0  0  0 -1 -1 -1 -1 -1]
# 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
import numpy as np
from sklearn.cluster import OPTICS, DBSCAN, cluster_optics_dbscan

X = np.array([[0,0],[1,0],[0,1],[1,1],[2.8,0],[3.8,0],[2.8,1],[3.8,1],
              [8,0],[10.5,0],[8,2.5],[10.5,2.5],[5,5]], float)
names = np.array("A1 A2 A3 A4 B1 B2 B3 B4 C1 C2 C3 C4 N".split())

opt = OPTICS(min_samples=3, max_eps=np.inf, cluster_method="xi", xi=0.05,
             min_cluster_size=3).fit(X)
print("order:", " ".join(names[opt.ordering_]))
print("reach:", np.round(opt.reachability_[opt.ordering_], 3))
print("xi labels:", opt.labels_)
print("xi hierarchy (ordering positions):", opt.cluster_hierarchy_.tolist())

# one OPTICS run -> DBSCAN at any eps, for free
for eps in (1.5, 2.0, 3.0):
    lab = cluster_optics_dbscan(reachability=opt.reachability_, core_distances=opt.core_distances_,
                                ordering=opt.ordering_, eps=eps)
    print(f"eps'={eps}:", lab)

# what a single DBSCAN radius can do
for eps in (1.0, 1.79, 1.8, 2.49, 2.5):
    print(f"DBSCAN eps={eps}:", DBSCAN(eps=eps, min_samples=3).fit(X).labels_)

# order: A1 A2 A3 A4 B1 B2 B3 B4 N C3 C1 C2 C4
# reach: [  inf 1.    1.    1.    1.8   1.    1.    1.    4.176 4.176 2.5   2.5   2.5  ]
# xi labels: [ 0  0  0  0  1  1  1  1  2  2  2  2 -1]          <- A, B, C, and N is noise
# xi hierarchy (ordering positions): [[0, 3], [4, 7], [0, 7], [9, 12], [0, 12]]
# eps'=1.5: [ 0  0  0  0  1  1  1  1 -1 -1 -1 -1 -1]
# eps'=2.0: [ 0  0  0  0  0  0  0  0 -1 -1 -1 -1 -1]
# eps'=3.0: [ 0  0  0  0  0  0  0  0  1  1  1  1 -1]
# DBSCAN eps=1.0:  [ 0  0  0  0  1  1  1  1 -1 -1 -1 -1 -1]
# DBSCAN eps=1.79: [ 0  0  0  0  1  1  1  1 -1 -1 -1 -1 -1]
# DBSCAN eps=1.8:  [ 0  0  0  0  0  0  0  0 -1 -1 -1 -1 -1]
# DBSCAN eps=2.49: [ 0  0  0  0  0  0  0  0 -1 -1 -1 -1 -1]
# 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.

> **Reading the hierarchy:** `cluster_hierarchy_` lists [start, end] ranges of the ordering. Here [0, 3] is A, [4, 7] is B, [0, 7] is A ∪ B, [9, 12] is C (positions 10–13 of the table, starting at C3), and [0, 12] is everything. `labels_` keeps only the leaves.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

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

- A. 0.6
- B. 1.0
- C. 1.4
- D. 1.6

**Answer:** B. 1.0 — $\text{reach}(o\mid q)=\max(1.0,\,0.6)=1.0$, and $\min(1.4,\,1.0)=1.0$. Points closer than the core distance all get the core distance, which is the smoothing effect of the max.

**Question:** An ordering of 11 points has reachabilities $\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.2$. How many clusters does the cut at $\varepsilon'=2.5$ give?

- A. 1
- B. 2
- C. 3
- D. 4

**Answer:** C. 3 — Bars above 2.5 are at positions 1 ($\infty$), 5 (3.0) and 9 (5.0). Each of those points has core distance ≤ 2.5 (0.5, 0.8, 2.0), so each starts a cluster: $\{1\text{–}4\},\{5\text{–}8\},\{9\text{–}11\}$, three clusters and no noise. At $\varepsilon'=1.0$ the last three points would be noise; at 4.0 the first two clusters merge.

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

- A. C has fewer than minPts points
- B. Separating A from B needs ε < 1.8, but C's points only become core points at ε ≥ 2.5
- C. N connects all clusters at every radius
- D. DBSCAN cannot find square-shaped clusters

**Answer:** B. Separating A from B needs ε < 1.8, but C's points only become core points at ε ≥ 2.5 — The A–B gap is 1.8 and C's core distance is 2.5. Every ε that makes C dense also bridges A and B. OPTICS's ξ extraction compares relative drops, so it finds both levels in one ordering.

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

- A. 0, because the point is its own neighbour
- B. Its core distance
- C. ∞ (undefined), because no processed point has reached it yet
- D. The average reachability of the cluster

**Answer:** C. ∞ (undefined), because no processed point has reached it yet — Reachability is always measured *from* an already-processed point. A walk that starts fresh has none, so $r=\infty$. Under a cut, that point starts a new cluster if its core distance is ≤ ε′, and is noise otherwise.

**Key points**

- Core distance = the radius at which a point becomes dense (distance to its minPts-th neighbour, itself counted). Reachability $\max(\text{core}(q),d(q,o))$ = the smallest radius at which $o$ joins $q$'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²).

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
