Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/6682
Title: An interior point algorithm for minimum sum-of-squares clustering
Authors: Du Merle, O
Hansen, P
Jaumard, B
Mladenović, N
Keywords: Classification and discrimination;Cluster analysis;Interior-point methods;Combinatorial optimization
Issue Date: 2000
Publisher: Society for Industrial and Applied Mathematics
Citation: SIAM Journal on Scientific Computing, 21(4): 1485 - 1505, Mar 2000
Abstract: 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 rst time for several fairly large data sets from the literature, including Fisher's 150 iris.
Description: Copyright @ 2000 SIAM Publications
URI: http://epubs.siam.org/doi/abs/10.1137/S1064827597328327
http://bura.brunel.ac.uk/handle/2438/6682
DOI: http://dx.doi.org/10.1137/S1064827597328327
ISSN: 1064-8275
Appears in Collections:Publications
Computer Science
Dept of Mathematics Research Papers
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
Fulltext.pdf295.78 kBAdobe PDFView/Open


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