Clustering is a fundamental technique in data analysis and machine learning, used to group similar data points together. Among various clustering methods, the Minimum Sum-of-Squares Clustering (MSSC) is one of the most widely used. MSSC aims to minimize the total squared Euclidean distance between data points and their corresponding cluster centroids. Due to the unsupervised nature of clustering, achieving global optimality is crucial but computationally challenging. The complexity of finding the global solution increases exponentially with the number of data points, making exact methods impractical on large-scale datasets. Even obtaining strong lower bounds on the optimal MSSC objective value is computationally prohibitive, making it difficult to assess the quality of heuristic solutions. We address this challenge by introducing a novel method to validate heuristic MSSC solutions through optimality gaps. Our approach employs a divide-and-conquer strategy, decomposing the problem into smaller instances that can be handled by an exact solver. The decomposition is guided by an auxiliary optimization problem, the “anticlustering problem”, for which we design an efficient heuristic. Computational experiments demonstrate the effectiveness of the method for large-scale instances, achieving optimality gaps below 3% while maintaining reasonable computational times. These results highlight the practicality of our approach in assessing feasible clustering solutions for large datasets, bridging a critical gap in MSSC evaluation.

Strong bounds for large-scale Minimum Sum-of-Squares Clustering / Livia Croella, A., Piccialli, V., Sudoso, A.M.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 336:1(2027), pp. 280-295. [10.1016/j.ejor.2026.07.045]

Strong bounds for large-scale Minimum Sum-of-Squares Clustering

Veronica Piccialli
;
Antonio M. Sudoso
2027

Abstract

Clustering is a fundamental technique in data analysis and machine learning, used to group similar data points together. Among various clustering methods, the Minimum Sum-of-Squares Clustering (MSSC) is one of the most widely used. MSSC aims to minimize the total squared Euclidean distance between data points and their corresponding cluster centroids. Due to the unsupervised nature of clustering, achieving global optimality is crucial but computationally challenging. The complexity of finding the global solution increases exponentially with the number of data points, making exact methods impractical on large-scale datasets. Even obtaining strong lower bounds on the optimal MSSC objective value is computationally prohibitive, making it difficult to assess the quality of heuristic solutions. We address this challenge by introducing a novel method to validate heuristic MSSC solutions through optimality gaps. Our approach employs a divide-and-conquer strategy, decomposing the problem into smaller instances that can be handled by an exact solver. The decomposition is guided by an auxiliary optimization problem, the “anticlustering problem”, for which we design an efficient heuristic. Computational experiments demonstrate the effectiveness of the method for large-scale instances, achieving optimality gaps below 3% while maintaining reasonable computational times. These results highlight the practicality of our approach in assessing feasible clustering solutions for large datasets, bridging a critical gap in MSSC evaluation.
2027
machine learning; minimum sum-of-squares clustering; large scale optimization; clustering validation
01 Pubblicazione su rivista::01a Articolo in rivista
Strong bounds for large-scale Minimum Sum-of-Squares Clustering / Livia Croella, A., Piccialli, V., Sudoso, A.M.. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 336:1(2027), pp. 280-295. [10.1016/j.ejor.2026.07.045]
File allegati a questo prodotto
File Dimensione Formato  
Croella_Strong-bounds_2027.pdf

accesso aperto

Note: https://www.sciencedirect.com/science/article/pii/S0377221726006636/pdf
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 3.11 MB
Formato Adobe PDF
3.11 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1778718
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact