Titre :

K-Medoids Clustering Is Solvable in Polynomial Time for a 2d Pareto Front

Auteur(s) :

Dupin, Nicolas [Auteur]
Université de Lille
Nielsen, Frank [Auteur]
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
Talbi, El-Ghazali [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Université de Lille

Titre de l’ouvrage :

Optimization of Complex Systems: Theory, Models, Algorithms and Applications

Éditeur :

Springer

Date de publication :

2020-06-15

Mot(s)-clé(s) en anglais :

Bi-objective clustering
Pareto front
Clustering algorithms
Euclidean sum-of-squares clustering
K-medoids
Dynamic programming
Bi-objective optimization

Discipline(s) HAL :

Informatique [cs]
Informatique [cs]/Intelligence artificielle [cs.AI]

Résumé en anglais : [en]

The k-medoids problem is a discrete sum-of-square clustering problem, which is known to be more robust to outliers than k-means clustering. As an optimization problem, k-medoids is NP-hard. This paper examines k-medoids ...
Lire la suite >The k-medoids problem is a discrete sum-of-square clustering problem, which is known to be more robust to outliers than k-means clustering. As an optimization problem, k-medoids is NP-hard. This paper examines k-medoids clustering in the case of a two-dimensional Pareto front, as generated by bi-objective optimization approaches. A characterization of optimal clusters is provided in this case. This allows to solve k-medoids to optimality in polynomial time using a dynamic programming algorithm. More precisely, having N points to cluster, the complexity of the algorithm is proven in O(N3) time and O(N2) memory space. This algorithm can also be used to minimize conjointly the number of clusters and the dissimilarity of clusters. This bi-objective extension is also solvable to optimality in O(N3) time and O(N2) memory space, which is useful to choose the appropriate number of clusters for the real-life applications. Parallelization issues are also discussed, to speed-up the algorithm in practice.Lire moins >

Langue :

Anglais

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL