Clustering Under Radius Constraints Using Minimum Dominating Sets
Partitionnement Sous Contraintes De Rayon Utilisant les Ensembles Dominants Minimaux
Abstract
In this paper, we evaluate the applicability of algorithms designed to solve the minimum dominating set problem to perform clustering. The associated clustering problem relies on user constraints, and more specifically on radius intra-cluster constraints. We adapt and evaluate implementations from the state of the art on classification datasets, to compare them with other exact or approximate radius-based clustering algorithms, namely equiwide clustering and hierarchical agglomerative clustering with minimax linkage. We consequently provide the benchmark tools and datasets used in this work.
Dans ce travail nous évaluons l'applicabilité des algorithmes construits pour résoudre le problème de l'ensemble dominant de cardinalité minimale à une tâche de clustering. Le problème de clustering associé repose sur des contraintes utilisateurs, et plus précisément sur la contrainte imposée au rayon intra-cluster. Nous adaptons et évaluons des implémentations issues de l'état de l'art sur des ensembles de données de classifications, pour les comparer avec d'autres algorithmes exacts ou approximatifs. Ces algorithmes sont Equiwide Clustering et le clustering hierarchique utilisant le minimax linkage. Conséquemment, nous mettons à disposition les outils d'évaluation et les jeux de données utilisés dans ce travail.