An LP-based k-means algorithm for balancing weighted point sets

DOI10.1016/J.EJOR.2017.04.054MaRDI QIDQ1694906zbMATH OpenOpenAlexWikidataFDO

Authors Steffen Borgwardt, Andreas Brieden, Peter Gritzmann

Publication date 6 February 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.4004

zbMATH Keywords

\(k\)-meansclusteringdata mininglinear programmingweight-balancing

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational learning theory (68Q32) Linear programming (90C05) Applications of mathematical programming (90C90)

Abstract: The classical $k$-means algorithm for partitioning $n$ points in $mathbb{R}^d$ into $k$ clusters is one of the most popular and widely spread clustering methods. The need to respect prescribed lower bounds on the cluster sizes has been observed in many scientific and business applications. In this paper, we present and analyze a generalization of $k$-means that is capable of handling weighted point sets and prescribed lower and upper bounds on the cluster sizes. We call it weight-balanced $k$-means. The key difference to existing models lies in the ability to handle the combination of weighted point sets with prescribed bounds on the cluster sizes. This imposes the need to perform partial membership clustering, and leads to significant differences. For example, while finite termination of all $k$-means variants for unweighted point sets is a simple consequence of the existence of only finitely many partitions of a given set of points, the situation is more involved for weighted point sets, as there are infinitely many partial membership clusterings. Using polyhedral theory, we show that the number of iterations of weight-balanced $k$-means is bounded above by $n^{O(dk)}$, so in particular it is polynomial for fixed $k$ and $d$. This is similar to the known worst-case upper bound for classical $k$-means for unweighted point sets and unrestricted cluster sizes, despite the much more general framework. We conclude with the discussion of some additional favorable properties of our method.

Recommendations

• How fast is the \(k\)-means method?
• How fast is the \(k\)-means method?
• Efficient solutions for weight-balanced partitioning problems
• \(k\)-means requires exponentially many iterations even in the plane
• k-means requires exponentially many iterations even in the plane

Cites work

• 10.1162/15324430260185628
• k-means requires exponentially many iterations even in the plane
• A Polynomial Time Algorithm for Shaped Partition Problems
• Constrained Clustering
• Constrained minimum-k-star clustering and its application to the consolidation of farmland
• Geometric clustering for the consolidation of farmland and woodland
• scientific article; zbMATH DE number 5379591 (Why is no real title available?)
• scientific article; zbMATH DE number 1332320 (Why is no real title available?)
• scientific article; zbMATH DE number 2159163 (Why is no real title available?)
• scientific article; zbMATH DE number 863501 (Why is no real title available?)
• scientific article; zbMATH DE number 1424293 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• Improved and simplified inapproximability for \(k\)-means
• k-Means Has Polynomial Smoothed Complexity
• Least squares quantization in PCM
• Lower Bounds for Approximation by Nonlinear Manifolds
• Minkowski-type theorems and least-squares clustering
• Multicategory classification by support vector machines
• NP-hardness of Euclidean sum-of-squares clustering
• On clustering bodies: geometry and polyhedral approximation
• On optimal weighted balanced clusterings: gravity bodies and power diagrams
• Optimal partitions having disjoint convex and conic hulls
• Partitions. Optimality and clustering. Vol. II: Multi-parameter.
• Power Diagrams: Properties, Algorithms and Applications
• Smoothed analysis of the k-means method
• The complexity of the \texttt{k-means} method
• The hardness of approximation of Euclidean k-means
• The planar \(k\)-means problem is NP-hard
• The vector partition problem for convex objective functions.

Cited in

(11)

• Constrained clustering via diagrams: a unified theory and its application to electoral district design
• Efficient solutions for weight-balanced partitioning problems
• Faster balanced clusterings in high dimension
• On parameterized approximation algorithms for balanced clustering
• Improved parameterized approximation for balanced \(k\)-median
• Power diagram detection with applications to information elicitation
• On optimal weighted balanced clusterings: gravity bodies and power diagrams
• scientific article; zbMATH DE number 176588 (Why is no real title available?)
• Turning Grain Maps into Diagrams
• One point per cluster spatially balanced sampling
• The intersection of location-allocation, partitional clustering and model-based clustering techniques -- a review

This page was built for publication: An LP-based \(k\)-means algorithm for balancing weighted point sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1694906)