Data Mining and Knowledge Discovery manuscript No. (will be inserted by the editor) A Clustering Comparison Measure Using Density Profiles and its Application to the Discovery of Alternate Clusterings⋆

Abstract Data clustering is a fundamental and very popular method of data analysis. Its subjective nature, however, means that different clustering algorithms or different parameter settings can produce widely varying and sometimes conflicting results. This has led to the use of clustering comparison measures to quantify the degree of similarity between alternative clusterings. Existing measures, though, can be limited in their ability to assess similarity and sometimes generate unintuitive results. They also cannot be applied to compare clusterings which contain different data points, an activity which is important for scenarios such as data stream analysis. In this paper, we introduce a new clustering similarity measure, known as ADCO, which aims to address some limitations of existing measures, by allowing greater flexi-bility of comparison via the use of density profiles to characterize a clustering. In par-ticular, it adopts a ‘data mining style ’ philosophy to clustering comparison, whereby two clusterings are considered to be more similar, if they are likely to give rise to similar types of prediction models. Furthermore, we show that this new measure can be applied as a highly effec-tive objective function within a new algorithm, known as MAXIMUS, for generating alternate clusterings. Keywords clustering · cluster analysis · clustering comparison · clustering similarity · alternate clusterings · alternate clustering algorithms ⋆ Part of this work appeared in a preliminary form in [1]. See Section 2 for discussion