HAWKS: Evolving Challenging Benchmark Sets for Cluster Analysis
- 21 December 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 26 (6) , 1206-1220
Abstract
Comprehensive benchmarking of clustering algorithms is rendered difficult by two key factors: (i) the elusiveness of a unique mathematical definition of this unsupervised learning approach and (ii) dependencies between the generating models or clustering criteria adopted by some clustering algorithms and indices for internal cluster validation. Consequently, there is no consensus regarding the best practice for rigorous benchmarking, and whether this is possible at all outside the context of a given application. Here, we argue that synthetic datasets must continue to play an important role in the evaluation of clustering algorithms, but that this necessitates constructing benchmarks that appropriately cover the diverse set of properties that impact clustering algorithm performance. Through our framework, HAWKS, we demonstrate the important role evolutionary algorithms play to support flexible generation of such benchmarks, allowing simple modification and extension. We illustrate two possible uses of our framework: (i) the evolution of benchmark data consistent with a set of hand-derived properties and (ii) the generation of datasets that tease out performance differences between a given pair of algorithms. Our work has implications for the design of clustering benchmarks that sufficiently challenge a broad range of algorithms, and for furthering insight into the strengths and weaknesses of specific approaches.Keywords
All Related Versions
Funding Information
- EPSRC Manchester Centre for Doctoral Training in Computer Science (EP/I028099/1)
This publication has 52 references indexed in Scilit:
- An extensive comparative study of cluster validity indicesPattern Recognition, 2013
- Measuring instance difficulty for combinatorial optimization problemsComputers & Operations Research, 2012
- A review of algorithms for medical image segmentation and their applications to the female pelvic cavityComputer Methods in Biomechanics and Biomedical Engineering, 2010
- Feature Subset Selection in Unsupervised Learning via Multiobjective OptimizationInternational Journal of Computational Intelligence Research, 2006
- Computational cluster validation in post-genomic data analysisBioinformatics, 2005
- Stochastic ranking for constrained evolutionary optimizationIEEE Transactions on Evolutionary Computation, 2000
- The Lack of A Priori Distinctions Between Learning AlgorithmsNeural Computation, 1996
- Silhouettes: A graphical aid to the interpretation and validation of cluster analysisJournal of Computational and Applied Mathematics, 1987
- Comparing partitionsJournal of Classification, 1985
- Approximate Evaluation Techniques for the Single-Link and Complete-Link Hierarchical Clustering ProceduresJournal of the American Statistical Association, 1974