Implementation of the OPTICS (Ordering points to identify the clustering structure) clustering algorithm using a kd-tree.
optics(x, eps, minPts = 5, ...)
extractDBSCAN(object, eps_cl) extractXi(object, xi, minimum = FALSE, correctPredecessors = TRUE)
# S3 method for optics predict(object, newdata = NULL, data, ...)
- a data matrix, a distance matrix.
- upper limit of the size of the epsilon neighborhood. Limiting the neighborhood size improves performance and has no or very little impact on the ordering as long as it is not set too low.
- the parameter is used to identify dense neighborhoods and the reachability distance is calculated as the distance to the minPts nearest neighbor. Default is 5 points.
- Threshold to identify clusters (eps_cl <= eps).
- Steepness threshold to identify clusters hierarchically using the Xi method.
- an object of class optics. For predict it needs to contain not just an ordering, but also an extracted clustering.
- the data set used to create the OPTICS clustering object.
- new data set for which cluster membership should be predicted.
- boolean representing whether or not to extract the minimal (non-overlapping) clusters in the Xi clustering algorithm.
- boolean Correct a common artifacting by pruning the steep up area for points that have predecessors not in the cluster--found by the ELKI framework, see details below.
- additional arguments are passed on to fixed-radius
nearest neighbor search algorithm. See
frNNfor details on how to control the search strategy.
This implementation of OPTICS implements the original algorithm as described by
Ankerst et al (1999). OPTICS is an ordering algorithm using similar concepts
to DBSCAN. However, for OPTICS
eps is only an upper limit for the neighborhood size used to reduce
computational complexity. Note that
minPts in OPTICS has a different
effect then in DBSCAN.
It is used to define dense neighborhoods, but since
eps is typically
set rather high, this does not effect the ordering much. However,
it is also used to calculate the reachability distance
and larger values will make the reachability distance plot smoother. OPTICS linearly orders the data points such that points which are spatially closest become neighbors in the ordering. The closest analog to this ordering is dendrogram
in single-link hierarchical clustering. The algorithm also calculates the
reachability distance for each point.
plot() produces a reachability-plot
which shows each points reachability distance where the points are sorted
by OPTICS. Valleys represent clusters (the deeper the valley, the more dense
the cluster) and high points indicate points between clusters.
extractDBSCAN extracts a clustering from an OPTICS ordering that is
similar to what DBSCAN would produce with an eps set to
eps_cl (see Ankerst et al, 1999).
The only difference to a DBSCAN clustering is that OPTICS is not able to
assign some border points and reports them instead as noise.
extractXi extract clusters hiearchically
specified in Ankerst et al (1999) based on the steepness of the reachability plot.
One interpretation of the
parameter is that it classifies clusters by change in relative cluster density.
The used algorithm was originally contributed by the ELKI framework,
but contains a set of fixes. See
frNN for more information on the parameters related to nearest neighbor search.
An object of class 'optics' with components:
extractDBSCANwas called, then in addition the following components are available:
extractXiwas called, then in addition the following components are available:
Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Joerg Sander (1999). OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD international conference on Management of data. ACM Press. pp. 49--60.
set.seed(2) n <- 400 x <- cbind( x = runif(4, 0, 1) + rnorm(n, sd=0.1), y = runif(4, 0, 1) + rnorm(n, sd=0.1) ) plot(x, col=rep(1:4, time = 100)) ### run OPTICS res <- optics(x, eps = 10, minPts = 10) res ### get order res$order ### plot produces a reachability plot plot(res) ### plot the order of points in the reachability plot plot(x, col = "grey") polygon(x[res$order,]) ### extract a DBSCAN clustering by cutting the reachability plot at eps_cl res <- extractDBSCAN(res, eps_cl = .065) res plot(res) ## black is noise hullplot(x, res) ### re-cut at a higher eps threshold res <- extractDBSCAN(res, eps_cl = .1) res plot(res) hullplot(x, res) ### extract hierarchical clustering of varying density using the Xi method res <- extractXi(res, xi = 0.05) res plot(res) hullplot(x, res) # Xi cluster structure res$clusters_xi ### use OPTICS on a precomputed distance matrix d <- dist(x) res <- optics(x, eps = 1, minPts = 10) plot(res)