K-Medoids Clustering Is Solvable in Polynomial Time for a 2d Pareto Front - Département d'informatique Accéder directement au contenu
Chapitre D'ouvrage Année : 2020

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-02304806 , version 1 (03-10-2019)

Identifiants

Citer

Nicolas Dupin, Frank Nielsen, El-Ghazali Talbi. K-Medoids Clustering Is Solvable in Polynomial Time for a 2d Pareto Front. Optimization of Complex Systems: Theory, Models, Algorithms and Applications, Springer, pp.790-799, 2020, ⟨10.1007/978-3-030-21803-4_79⟩. ⟨hal-02304806⟩
159 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More