OPTICS: ordering points to identify the clustering structure

OPTICS (Ordering Points To Identify the Clustering Structure) is a cluster-analysis algorithm for database mining. The authors observe that almost all well-known clustering algorithms require input parameters that are hard to determine but significantly influence the result, and that for many real datasets no single global parameter setting describes the intrinsic clustering structure accurately. Instead of producing an explicit clustering, OPTICS creates an augmented ordering of the database that represents its density-based clustering structure, and this cluster-ordering contains information equivalent to the density-based clusterings corresponding to a broad range of parameter settings.

Because it captures a whole range of parameter settings at once, the cluster-ordering is a versatile basis for both automatic and interactive cluster analysis: the authors show how to efficiently extract not only traditional clustering information, such as representative points and arbitrary-shaped clusters, but also the intrinsic clustering structure itself. For medium-sized datasets the ordering can be represented graphically, and for very large datasets the authors introduce an appropriate visualization technique, both supporting interactive exploration and offering insight into the distribution and correlation of the data.