K-Medoids Clustering Is Solvable in ...
Document type :
Partie d'ouvrage
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]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Optimisation de grande taille et calcul large échelle [BONUS]
Université de Lille
Nielsen, Frank [Auteur]
Laboratoire d'informatique de l'École polytechnique [Palaiseau] [LIX]
Talbi, El-Ghazali [Auteur]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Optimisation de grande taille et calcul large échelle [BONUS]
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
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]
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 >
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 :
Source :