The area under the ROC curve as a measure of clustering quality

Pablo A. Jaskowiak*, Ivan G. Costa, Ricardo J.G.B. Campello

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The area under the receiver operating characteristics (ROC) Curve, referred to as AUC, is a well-known performance measure in the supervised learning domain. Due to its compelling features, it has been employed in a number of studies to evaluate and compare the performance of different classifiers. In this work, we explore AUC as a performance measure in the unsupervised learning domain, more specifically, in the context of cluster analysis. In particular, we elaborate on the use of AUC as an internal/relative measure of clustering quality, which we refer to as Area Under the Curve for Clustering (AUCC). We show that the AUCC of a given candidate clustering solution has an expected value under a null model of random clustering solutions, regardless of the size of the dataset and, more importantly, regardless of the number or the (im)balance of clusters under evaluation. In addition, we elaborate on the fact that, in the context of internal/relative clustering validation as we consider, AUCC is actually a linear transformation of the Gamma criterion from Baker and Hubert (1975), for which we also formally derive a theoretical expected value for chance clusterings. We also discuss the computational complexity of these criteria and show that, while an ordinary implementation of Gamma can be computationally prohibitive and impractical for most real applications of cluster analysis, its equivalence with AUCC actually unveils a much more efficient algorithmic procedure. Our theoretical findings are supported by experimental results. These results show that, in addition to an effective and robust quantitative evaluation provided by AUCC, visual inspection of the ROC curves themselves can be useful to further assess a candidate clustering solution from a broader, qualitative perspective as well.

Original languageEnglish
JournalData Mining and Knowledge Discovery
Volume36
Issue number3
Pages (from-to)1219-1245
ISSN1384-5810
DOIs
Publication statusPublished - May 2022
Externally publishedYes

Keywords

  • Area under the curve
  • Area under the curve for clustering
  • AUC/ROC
  • Clustering validation
  • Qualitative/visual clustering evaluation
  • Receiver operating characteristics

Fingerprint

Dive into the research topics of 'The area under the ROC curve as a measure of clustering quality'. Together they form a unique fingerprint.

Cite this