OPTICS
OPTICS: Ordering Points To Identify the Clustering Structure · Also known as: OPTICS, Ordering Points To Identify the Clustering Structure, density-based clustering with reachability plot, generalized DBSCAN
OPTICS (Ordering Points To Identify the Clustering Structure) is a density-based clustering algorithm introduced by Ankerst, Breunig, Kriegel, and Sander in 1999. It generalizes DBSCAN by processing points in an ordering that encodes the full density-based cluster structure of a dataset, enabling the detection of clusters of varying densities through a reachability plot rather than requiring a fixed global density threshold.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use OPTICS when the dataset contains clusters of varying local densities that a single global epsilon (as in DBSCAN) cannot capture simultaneously, or when you want to visually inspect the density hierarchy before committing to a specific cluster extraction threshold. It suits spatial, geographic, or high-dimensional point-cloud data where cluster shapes are arbitrary and noise is present. OPTICS assumes that meaningful clusters are denser than the surrounding space, that a meaningful distance metric exists, and that minPts can be set based on domain knowledge (typically 5–20 for low-dimensional data, higher for high-dimensional data). It is not recommended when all clusters are known to have uniform density (standard DBSCAN is then simpler), when the dataset is very large and computational cost is prohibitive without an efficient index structure, or when the data are purely categorical with no coherent distance metric.
Strengths & limitations
- Handles clusters of arbitrarily varying density in a single pass, overcoming the main limitation of DBSCAN.
- Does not require the user to pre-specify the number of clusters.
- Automatically identifies and labels noise points rather than forcing them into clusters.
- The reachability plot provides an interpretable visual summary of the full cluster hierarchy.
- Cluster extraction can be performed at multiple granularities post hoc without rerunning the algorithm.
- The reachability plot and xi-steep extraction can be non-trivial to interpret correctly; the choice of xi and minPts strongly affects results.
- Computational complexity is O(n log n) with a spatial index (e.g., k-d tree or ball tree) but O(n²) without one, making it slow on very large datasets.
- Performance degrades in high-dimensional spaces due to the curse of dimensionality, where distance concentration makes density estimation unreliable.
- The algorithm still requires two hyperparameters (epsilon and minPts), and while epsilon plays a secondary role, poor choices can affect the reachability plot.
Frequently asked
How does OPTICS differ from DBSCAN?
DBSCAN partitions data using a fixed global epsilon and minPts, which means it can only find clusters at one density level at a time. OPTICS processes the data in a density-ordered sequence and records reachability distances, effectively computing the DBSCAN result for all epsilon values simultaneously. A post-processing step then extracts clusters at any chosen density threshold — or automatically across all levels using the xi parameter.
What values should I choose for minPts and epsilon?
A common rule of thumb sets minPts to at least the dimensionality of the data plus one, or to 2 times the number of dimensions; values of 5 to 20 work well for low-dimensional data. For epsilon, set it to a large permissive value (e.g., the maximum pairwise distance) so it does not prematurely exclude neighbors; the reachability plot is relatively insensitive to epsilon as long as it is not too small. Inspect the reachability plot and adjust xi or the extraction threshold rather than tuning epsilon directly.
How do I extract concrete clusters from the reachability plot?
Two main approaches exist. The simpler one applies a horizontal threshold epsilon' to the reachability plot: points with reachability distance below epsilon' belong to a cluster, yielding the same result as running DBSCAN with that epsilon'. The more automatic xi-steep approach identifies valleys by detecting relative drops and rises of at least xi in reachability distance; it requires choosing xi (typically 0.01–0.1) but avoids specifying an absolute distance threshold.
Is OPTICS suitable for high-dimensional data?
With caution. In high dimensions the curse of dimensionality causes all pairwise distances to concentrate, making density differences harder to detect. Dimensionality reduction (PCA, UMAP) or the use of domain-specific distance metrics before applying OPTICS can mitigate this. HDBSCAN, which builds on similar principles, is often more robust in moderately high-dimensional settings.
Sources
- Ankerst, M., Breunig, M. M., Kriegel, H.-P., & Sander, J. (1999). OPTICS: Ordering points to identify the clustering structure. ACM SIGMOD Record, 28(2), 49–60. DOI: 10.1145/304181.304187 ↗
- Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), 226–231. link ↗
- Aggarwal, C. C., & Reddy, C. K. (Eds.) (2013). Data Clustering: Algorithms and Applications (Ch. 4). CRC Press. ISBN: 978-1-4665-5821-2
How to cite this page
ScholarGate. (2026, June 3). OPTICS: Ordering Points To Identify the Clustering Structure. ScholarGate. https://scholargate.app/en/machine-learning/optics
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- DBSCANMachine learning↔ compare
- HDBSCANMachine learning↔ compare
- Hierarchical ClusteringMachine learning↔ compare