On strategies for building effective ensembles of relative clustering validity criteria

Author(s)

Jaskowiak, Pablo A. ^[1] ; Moulavi, Davoud ^[2] ; Furtado, Antonio C. S. ^[2] ; Campello, Ricardo J. G. B. ^[1] ; Zimek, Arthur ^[3] ; Sander, Joerg ^[2]

Affiliation

^[1] Univ Sao Paulo, Dept Comp Sci, Sao Carlos, SP - Brazil

^[2] Univ Alberta, Dept Comp Sci, Edmonton, AB - Canada

^[3] Univ Munich, Database Syst & Data Min Grp, Munich - Germany

• Document type: Journal article
• Source: KNOWLEDGE AND INFORMATION SYSTEMS; v. 47, n. 2, p. 329-354, MAY 2016.
• Web of Science Citations: 8

Abstract

Evaluation and validation are essential tasks for achieving meaningful clustering results. Relative validity criteria are measures usually employed in practice to select and validate clustering solutions, as they enable the evaluation of single partitions and the comparison of partition pairs in relative terms based only on the data under analysis. There is a plethora of relative validity measures described in the clustering literature, thus making it difficult to choose an appropriate measure for a given application. One reason for such a variety is that no single measure can capture all different aspects of the clustering problem and, as such, each of them is prone to fail in particular application scenarios. In the present work, we take advantage of the diversity in relative validity measures from the clustering literature. Previous work showed that when randomly selecting different relative validity criteria for an ensemble (from an initial set of 28 different measures), one can expect with great certainty to only improve results over the worst criterion included in the ensemble. In this paper, we propose a method for selecting measures with minimum effectiveness and some degree of complementarity (from the same set of 28 measures) into ensembles, which show superior performance when compared to any single ensemble member (and not just the worst one) over a variety of different datasets. One can also expect greater stability in terms of evaluation over different datasets, even when considering different ensemble strategies. Our results are based on more than a thousand datasets, synthetic and real, from different sources. (AU)

• FAPESP's process: 12/15751-9 - Gene selection and Outliers in microarray data
• Grantee: Pablo Andretta Jaskowiak
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• FAPESP's process: 10/20032-6 - Study and development of validation methods for density- and graph-based clustering techniques
• Grantee: Ricardo José Gabrielli Barreto Campello
• Support Opportunities: Scholarships abroad - Research
• FAPESP's process: 11/04247-5 - Gene Selection and Clustering Validation in Gene Expression Data
• Grantee: Pablo Andretta Jaskowiak
• Support Opportunities: Scholarships in Brazil - Doctorate