Brunel University Research Archive (BURA) >
University >
Publications >

Please use this identifier to cite or link to this item:

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
Publication 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
Sponsorship: This research was supported by the Fonds National de la Recherche Scientifique Suisse, NSERC-Canada, and FCAR-Quebec.
ISSN: 1064-8275
Appears in Collections:Mathematical Science
Computer Science
Dept of Mathematics Research Papers

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.