Ordering points to identify the clustering structure (OPTICS) is an algorithm for finding density-based^[1]clusters in spatial data. It was presented in 1999 by Mihael Ankerst, Markus M. Breunig,Hans-Peter Kriegel andJörg Sander.^[2]Its basic idea is similar toDBSCAN,^[3] but it addresses one of DBSCAN's major weaknesses: the problem of detecting meaningful clusters in data of varying density. To do so, the points of the database are (linearly) ordered such that spatially closest points become neighbors in the ordering. Additionally, a special distance is stored for each point that represents the density that must be accepted for a cluster so that both points belong to the same cluster. This is represented as adendrogram.

LikeDBSCAN, OPTICS requires two parameters:ε, which describes the maximum distance (radius) to consider, andMinPts, describing the number of points required to form a cluster. A pointp is acore point if at leastMinPts points are found within itsε-neighborhood${\displaystyle N_{\epsilon }(p)}$ (including pointp itself). In contrast toDBSCAN, OPTICS also considers points that are part of a more densely packed cluster, so each point is assigned acore distance that describes the distance to theMinPtsth closest point:

Thereachability-distance of another pointo from a pointp is either the distance betweeno andp, or the core distance ofp, whichever is bigger:

Ifp ando are nearest neighbors, this is the we need to assume to havep ando belong to the same cluster.

Both core-distance and reachability-distance are undefined if no sufficiently dense cluster (w.r.t.ε) is available. Given a sufficiently largeε, this never happens, but then everyε-neighborhood query returns the entire database, resulting in${\displaystyle O(n^2)}$ runtime. Hence, theε parameter is required to cut off the density of clusters that are no longer interesting, and to speed up the algorithm.

The parameterε is, strictly speaking, not necessary. It can simply be set to the maximum possible value. When a spatial index is available, however, it does play a practical role with regards to complexity. OPTICS abstracts from DBSCAN by removing this parameter, at least to the extent of only having to give the maximum value.

The basic approach of OPTICS is similar toDBSCAN, but instead of maintaining known, but so far unprocessed cluster members in a set, they are maintained in apriority queue (e.g. using an indexedheap).

function OPTICS(DB, ε, MinPts)isfor each point p of DBdo        p.reachability-distance = UNDEFINEDfor each unprocessed point p of DBdo        N = getNeighbors(p, ε)        mark p as processed        output p to the ordered listif core-distance(p, ε, MinPts) != UNDEFINEDthen            Seeds = empty priority queue            update(N, p, Seeds, ε, MinPts)for each next q in Seedsdo                N' = getNeighbors(q, ε)                mark q as processed                output q to the ordered listif core-distance(q, ε, MinPts) != UNDEFINEDdo                    update(N', q, Seeds, ε, MinPts)

In update(), the priority queue Seeds is updated with the${\displaystyle \epsilon }$-neighborhood of${\displaystyle p}$ and${\displaystyle q}$, respectively:

function update(N, p, Seeds, ε, MinPts)is    coredist = core-distance(p, ε, MinPts)for each o in Nif o is not processedthen            new-reach-dist = max(coredist, dist(p,o))if o.reachability-distance == UNDEFINEDthen // o is not in Seeds                o.reachability-distance = new-reach-dist                Seeds.insert(o, new-reach-dist)else               // o in Seeds, check for improvementif new-reach-dist < o.reachability-distancethen                    o.reachability-distance = new-reach-dist                    Seeds.move-up(o, new-reach-dist)

OPTICS hence outputs the points in a particular ordering, annotated with their smallest reachability distance (in the original algorithm, the core distance is also exported, but this is not required for further processing).

Using areachability-plot (a special kind ofdendrogram), the hierarchical structure of the clusters can be obtained easily. It is a 2D plot, with the ordering of the points as processed by OPTICS on the x-axis and the reachability distance on the y-axis. Since points belonging to a cluster have a low reachability distance to their nearest neighbor, the clusters show up as valleys in the reachability plot. The deeper the valley, the denser the cluster.

The image above illustrates this concept. In its upper left area, a synthetic example data set is shown. The upper right part visualizes thespanning tree produced by OPTICS, and the lower part shows the reachability plot as computed by OPTICS. Colors in this plot are labels, and not computed by the algorithm; but it is well visible how the valleys in the plot correspond to the clusters in above data set. The yellow points in this image are considered noise, and no valley is found in their reachability plot. They are usually not assigned to clusters, except the omnipresent "all data" cluster in a hierarchical result.

Extracting clusters from this plot can be done manually by selecting ranges on the x-axis after visual inspection, by selecting a threshold on the y-axis (the result is then similar to a DBSCAN clustering result with the same${\displaystyle \epsilon }$ and minPts parameters; here a value of 0.1 may yield good results), or by different algorithms that try to detect the valleys by steepness, knee detection, or local maxima. A range of the plot beginning with a steep descent and ending with a steep ascent is considered a valley, and corresponds to a contiguous area of high density. Additional care must be taken to the last points in a valley to assign them to the inner or outer cluster, this can be achieved by considering the predecessor.^[4] Clusterings obtained this way usually arehierarchical, and cannot be achieved by a single DBSCAN run.

LikeDBSCAN, OPTICS processes each point once, and performs one${\displaystyle \epsilon }$-neighborhood query during this processing. Given aspatial index that grants a neighborhood query in${\displaystyle O(\log n)}$ runtime, an overall runtime of${\displaystyle O(n\cdot \log n)}$ is obtained. The worst case however is${\displaystyle O(n^2)}$, as with DBSCAN. The authors of the original OPTICS paper report an actual constant slowdown factor of 1.6 compared to DBSCAN. Note that the value of${\displaystyle \epsilon }$ might heavily influence the cost of the algorithm, since a value too large might raise the cost of a neighborhood query to linear complexity.

In particular, choosing${\displaystyle \epsilon >\underset{x,y}{max}d(x,y)}$ (larger than the maximum distance in the data set) is possible, but leads to quadratic complexity, since every neighborhood query returns the full data set. Even when no spatial index is available, this comes at additional cost in managing the heap. Therefore,${\displaystyle \epsilon }$ should be chosen appropriately for the data set.

OPTICS-OF^[5] is anoutlier detection algorithm based on OPTICS. The main use is the extraction of outliers from an existing run of OPTICS at low cost compared to using a different outlier detection method. The better known versionLOF is based on the same concepts.

DeLi-Clu,^[6] Density-Link-Clustering combines ideas fromsingle-linkage clustering and OPTICS, eliminating the${\displaystyle \epsilon }$ parameter and offering performance improvements over OPTICS.

HiSC^[7] is a hierarchicalsubspace clustering (axis-parallel) method based on OPTICS.

HiCO^[8] is a hierarchicalcorrelation clustering algorithm based on OPTICS.

DiSH^[9] is an improvement over HiSC that can find more complex hierarchies.

FOPTICS^[10] is a faster implementation using random projections.

HDBSCAN*^[11] is based on a refinement of DBSCAN, excluding border-points from the clusters and thus following more strictly the basic definition of density-levels by Hartigan.^[12]

Java implementations of OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO and DiSH are available in theELKI data mining framework (with index acceleration for several distance functions, and with automatic cluster extraction using the ξ extraction method). Other Java implementations include theWeka extension (no support for ξ cluster extraction).

TheR package "dbscan" includes a C++ implementation of OPTICS (with both traditional dbscan-like and ξ cluster extraction) using ak-d tree for index acceleration for Euclidean distance only.

Python implementations of OPTICS are available in thePyClustering library and inscikit-learn. HDBSCAN* is available in thehdbscan library.

• Cluster analysis algorithms

• CS1: long volume value
• Articles with short description
• Short description matches Wikidata