Community Page

OPTICS: Ordering Points to Identify the Clustering Structure

Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, and Jörg Sander. International Conference on Management of Data and Symposium on Principles of Database Systems Philadelphia (SIGMOD/PODS 1999), PA, USA - May 31 - June 03, 1999, page 49-60. New York, NY, USA, ACM, (1999)


Cluster analysis is a primary method for database mining. It is either used as a stand-alone tool to get insight into the distribution of a data set, e.g. to focus further analysis and data processing, or as a preprocessing step for other algorithms operating on the detected clusters. Almost all of the well-known clustering algorithms require input parameters which are hard to determine but have a significant influence on the clustering result. Furthermore, for many real-data sets there does not even exist a global parameter setting for which the result of the clustering algorithm describes the intrinsic clustering structure accurately. We introduce a new algorithm for the purpose of cluster analysis which does not produce a clustering of a data set explicitly; but instead creates an augmented ordering of the database representing its density-based clustering structure. This cluster-ordering contains information which is equivalent to the density-based clusterings corresponding to a broad range of parameter settings. It is a versatile basis for both automatic and interactive cluster analysis. We show how to automatically and efficiently extract not only 'traditional' clustering information (e.g. representative points, arbitrary shaped clusters), but also the intrinsic clustering structure. For medium sized data sets, the cluster-ordering can be represented graphically and for very large data sets, we introduce an appropriate visualization technique. Both are suitable for interactive exploration of the intrinsic clustering structure offering additional insights into the distribution and correlation of the data.


Users of this resource

Cite this publication

Comments and Reviews

rating distribution

average user rating 

The average rating is computed over all reviews. However, some of them may be invisible to you due to the visibility setting chosen by the reviewers.
(4.5 out of 5.0 based on 2 reviews)
  • userPicture@cscholz
    extension for dbscan, nice to read, a lot of new approaches, very detailed

  • userPicture@bjoern

Please log in to take part in the discussion (add own reviews or comments).