Title :

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

Author(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

Book title :

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

Publisher :

Springer

Publication date :

2020-06-15

English keyword(s) :

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

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL