CLAIRE: clustering evaluation based on item response theory and model agreement

Abstract

Clustering evaluation is a complex task. External measures, such as the Rand index, are often used for benchmarking, but they are not applicable in real, unsupervised scenarios due to the lack of ground truth. Thus, we often turn to internal measures for model evaluation, e.g. silhouette, Dunn, and Davies-Bouldin. These indexes have the advantage of evaluating models based on the clustered data points themselves, however, they rely on a chosen distance, so they are only meaningful for models that use the same distance. Additionally, they fail if all instances are assigned to a single cluster and they aim to evaluate separation and cohesion instead of quantifying a model’s ability to recover any underlying classes. Thus, internal measures are not suited to compare models that are estimated differently. In this paper, we propose CLAIRE (CLuster Agreement-based Item REsponses), a method for global evaluation of clustering models, by assuming that good models agree on whether pairs of instances should be clustered together or not. We leverage Item Response Theory to estimate model ability and instance difficulty, using response matrices obtained by measuring the agreement between models. Experiments were carried out using diverse sets of clustering methods and datasets with different numbers of clusters and varying shapes and levels of overlapping and noise. Results show that CLAIRE is robust to the presence of random partitions in the pool of models and correctly ranks models across the many tested scenarios with a surprisingly high correlation with external measures of clustering quality, meaning it also indirectly evaluates the recovery of underlying classes.

Authors

Manuel Ferreira-Junior, Centro de Informática, Universidade Federal de Pernambuco, Recife, Brazil

Eufrasio A. Lima Neto, Departamento de Estatística, Universidade Federal da Paraíba, João Pessoa, Brazil

Marcelo R. P. Ferreira, Departamento de Estatística, Universidade Federal da Paraíba, João Pessoa, Brazil

Telmo M. Silva Filho, School of Engineering Mathematics and Technology, University of Bristol, Bristol, United Kingdom

Ricardo B. C. Prudêncio, Centro de Informática, Universidade Federal de Pernambuco, Recife, Brazil