OPTICS Cluster Compute

The implementation of the OPTICS algorithm in KNIME consists of two nodes: the OPTICS Cluster Compute node and the OPTICS Cluster Assigner node. Here you will find a brief description of the algorithm, followed by a description of the OPTICS Cluster Compute node.

OPTICS is an algorithm for finding clusters in spatial data. It was first described in Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander (1999). "OPTICS: Ordering Points To Identify the Clustering Structure". ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60 and is based on DBSCAN. Like DBSCAN, it is a density-based clustering algorithm, that is, it groups data points that are densely packed together in some contiguous region of the data space into clusters. Unlike DBSCAN, it can detect clusters of varying density.

The basic idea shared by DBSCAN and OPTICS is that a data point p belongs to a cluster if it has sufficiently many sufficiently close neighbors. "Sufficiently close" is modeled with a parameter epsilon (the neighborhood radius of p), "sufficiently many" with a parameter Minimum Points (the minimum number of points that must be within epsilon of p in order for p to belong to the core of a cluster.)

DBSCAN first checks the epsilon-neighborhood of each point in the data set. If there are more than Minimum Points points in the epsilon-neighborhood of a point p, these points form a cluster. DBSCAN then checks the epsilon-neighborhoods of these points to see if they in turn contain more than Minimum Points data points. If they do, these data points also become part of the cluster. DBSCAN continues in this way until no new point can be added to the cluster.

While this algorithm will find all the clusters with the density determined by the the chosen values for epsilon and Minimum Points, it may miss higher-density clusters that are contained in these clusters. These higher-density clusters become visible only at some epsilon-prime <e epsilon. The problem is that there is no way of knowing these epsilon-prime values in advance, so all one can do is run DBSCAN for as many epsilon-prime values as feasible.

OPTICS solves this problem by ordering the points in the data set and by associating with each point two values: its core-distance and its reachability distance (for definitions, see the link above). This information is enough to find all density-based clusters in the data set for any epsilon-prime <e epsilon (for details on the algorithm, see the link above).

Since both core-distance and reachability-distance are ultimately defined in terms of epsilon and Minimum Points, the only inputs needed to run OPTICS are values for these parameters.