Authors: Du Merle, Olivier
Hansen, Pierre
Jaumard, Brigitte
Mladenović, Nenad 
Title: An interior point algorithm for minimum sum-of-squares clustering
Journal: SIAM Journal of Scientific Computing
Volume: 21
Issue: 4
First page: 1485
Last page: 1505
Issue Date: 1-Jan-1999
Rank: M21a
ISSN: 1064-8275
DOI: 10.1137/S1064827597328327
An exact algorithm is proposed for minimum sum-of-squares nonhierarchical clustering, i.e., for partitioning a given set of points from a Euclidean m-space into a given number of clusters in order to minimize the sum of squared distances from all points to the centroid of the cluster to which they belong. This problem is expressed as a constrained hyperbolic program in 0-1 variables. The resolution method combines an interior point algorithm, i.e., a weighted analytic center column generation method, with branch-and-bound. The auxiliary problem of determining the entering column (i.e., the oracle) is an unconstrained hyperbolic program in 0-1 variables with a quadratic numerator and linear denominator. It is solved through a sequence of unconstrained quadratic programs in 0-1 variables. To accelerate resolution, variable neighborhood search heuristics are used both to get a good initial solution and to solve quickly the auxiliary problem as long as global optimality is not reached. Estimated bounds for the dual variables are deduced from the heuristic solution and used in the resolution process as a trust region. Proved minimum sum-of-squares partitions are determined for the first time for several fairly large data sets from the literature, including Fisher's 150 iris.
Keywords: Classification and discrimination | Cluster analysis | Combinatorial optimization | Interior-point methods
Publisher: Society for Industrial and Applied Mathematics

Show full item record


checked on Dec 2, 2021

Page view(s)

checked on Dec 3, 2021

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.