A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering
Open Access
- 1 December 2009
- journal article
- Published by FapUNIFESP (SciELO) in Pesquisa Operacional
- Vol. 29 (3) , 503-516
Abstract
Minimum sum-of-squares clustering (MSSC) consists in partitioning a given set of n points into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. Recently, Peng & Xia (2005) established the equivalence between 0-1 semidefinite programming (SDP) and MSSC. In this paper, we propose a branch-and-cut algorithm for the underlying 0-1 SDP model. The algorithm obtains exact solutions for fairly large data sets with computing times comparable with those of the best exact method found in the literature.Keywords
This publication has 24 references indexed in Scilit:
- Approximating K‐means‐type Clustering via Semidefinite ProgrammingSIAM Journal on Optimization, 2007
- Graph partitioning using linear and semidefinite programmingMathematical Programming, 2003
- J-Means: a new local search heuristic for minimum sum of squares clusteringPattern Recognition, 2001
- An Interior Point Algorithm for Minimum Sum-of-Squares ClusteringSIAM Journal on Scientific Computing, 1999
- Variable neighborhood searchComputers & Operations Research, 1997
- Semidefinite ProgrammingSIAM Review, 1996
- Evaluation of a Branch and Bound Algorithm for ClusteringSIAM Journal on Scientific and Statistical Computing, 1985
- Complete-Link Cluster Analysis by Graph ColoringJournal of the American Statistical Association, 1978
- Numerical methods for fuzzy clusteringInformation Sciences, 1970
- A Method for Cluster AnalysisBiometrics, 1965