|Authors:||Du Merle, Olivier
|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||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 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
checked on Dec 3, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.