OPTICS: Reachability Ordering and Clusters at Multiple Density Scales

Why a single radius is restrictive

Imagine observations from a dense downtown area and a sparsely sampled rural area. A radius that connects rural observations may merge downtown neighbourhoods. A radius that separates downtown groups may fragment the rural population.

DBSCAN chooses one radius and produces a partition with noise. OPTICS instead constructs an ordering with density-related distances. The ordering provides a view of how observations become reachable as the effective scale changes. A maximum search radius may still limit which relationships are considered.

Core distance measures local support

Fix a minimum neighbourhood count m and a maximum radius. The core distance of a point is the distance needed to include m observations under the stated self-counting convention, provided that many observations lie within the maximum radius. Otherwise its core distance is undefined, often represented as infinity.

For a core point o and a candidate p, define

This quantity combines the scale at which o has enough support with the actual separation to p. It is directional: the expression uses the core distance of o, not p. Do not confuse it with HDBSCAN’s symmetric mutual-reachability distance.

Follow an update numerically

Suppose o has core distance 0.2 and p is 0.1 away. The candidate reachability of p through o is 0.2. Even though the pair is close, a radius below 0.2 would not give o enough neighbours to propagate density reachability.

If another core point q has core distance 0.05 and lies 0.12 from p, its candidate value is 0.12. An unprocessed p can keep the better candidate, lowering its current reachability estimate. The algorithm maintains these candidates while expanding the ordering.

def reach(core_distance, pair_distance):
    return max(core_distance, pair_distance)
assert reach(0.2, 0.1) == 0.2
assert min(reach(0.2, 0.1), reach(0.05, 0.12)) == 0.12

This is a scale calculation, not a posterior probability of common membership. A small value means p can be reached through a sufficiently supported nearby point at a small radius.

How the ordering is constructed

Start with an unprocessed observation. Compute its neighbourhood and core distance. If it is core, update reachability candidates for unprocessed neighbours. Process the candidate with the smallest current reachability next, updating more neighbours in turn. When a connected expansion is exhausted, begin another unprocessed region.

A priority queue is a natural way to manage candidates, although implementations can use different data structures. The result records ordering, reachability and often predecessor information. The first observation of a new expansion can have infinite reachability because no previous processed point supplied a connection.

Ordering is not chronological order, a principal coordinate or a semantic ranking. Its purpose is to place related density expansions together so their scale structure can be inspected.

Read a reachability plot carefully

The x-axis is position in the ordering; the y-axis is reachability. A low valley suggests a region connected at a small density scale. Higher barriers separate regions requiring a larger scale to connect. Nested valleys can suggest groups inside larger groups.

Valley width counts observations in the ordering, not physical diameter. Valley height is not a calibrated probability or a universal cluster-quality score. Two equally meaningful populations with different sampling density can occupy valleys of different depths.

Repeat the analysis across plausible minimum-count settings and inspect original-space examples from each valley. A visually compelling valley may reflect duplicated records, quantisation of a sensor or uneven sampling rather than an intended population.

Extracting labels is another step

A DBSCAN-style cut at a selected radius can extract a partition using the reachability representation within the supported range. A steepness-based Xi extraction instead identifies sufficiently sharp changes in reachability and may yield hierarchical structure before a flat selection.

These extraction procedures use different criteria and parameters. Report which one generated the labels. Saying “OPTICS found five clusters” omits the part of the procedure that turned the ordering into those five groups.

The result can still include noise. If the application requires every observation to be assigned, forcing remaining points into a nearest group is an additional assumption that should be evaluated separately.

Resource and deployment considerations

Neighbourhood searches dominate much of the work. Favourable low-dimensional spatial indexing can help, while high dimensions or dense neighbourhoods make it expensive. Complexity statements depend on the implementation: a library’s ordering procedure may be quadratic even when the original algorithm uses more efficient candidate handling.

Store the ordering and reachability values so alternative cuts can be inspected without confusing them with newly fitted geometry. Evaluate new observations under an explicit attachment or refitting policy. Like DBSCAN, an exploratory density hierarchy is not automatically a fixed classifier with a natural predict operation.

OPTICS is particularly useful when choosing one density scale too early would hide the phenomenon. Use clustering evaluation to decide whether any extracted partition is stable and useful rather than treating the plot itself as the final evidence.

References

1. Ankerst, Breunig, Kriegel and Sander. OPTICS: Ordering Points To Identify the Clustering Structure. SIGMOD, 1999.
2. scikit-learn. Clustering user guide.