Good Clusterings Have Large Volume

Steffen Borgwardt () and Felix Happach ()
Additional contact information
Steffen Borgwardt: Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Colorado 80204
Felix Happach: Department of Mathematics and TUM School of Management, Technische Universität München, 80333 München, Germany

Operations Research, 2019, vol. 67, issue 1, 215-231

Abstract: The clustering of a data set is one of the core tasks in data analytics. Many clustering algorithms exhibit a strong contrast between a favorable performance in practice and bad theoretical worst cases. Prime examples are least-squares assignments and the popular k -means algorithm. We are interested in this contrast and study it through polyhedral theory. Several popular clustering algorithms can be connected to finding a vertex of the so-called bounded-shape partition polytopes. The vertices correspond to clusterings with extraordinary separation properties, in particular allowing the construction of a separating power diagram, defined by its so-called sites, such that each cluster has its own cell. First, we quantitatively measure the space of all sites that allow construction of a separating power diagram for a clustering by the volume of the normal cone at the corresponding vertex. This gives rise to a new quality criterion for clusterings, and explains why good clusterings are also the most likely to be found by some classical algorithms. Second, we characterize the edges of the bounded-shape partition polytopes. Through this, we obtain an explicit description of the normal cones. This allows us to compute measures with respect to the new quality criterion, and even compute “most stable” sites, and thereby “most stable” power diagrams, for the separation of clusters. The hardness of these computations depends on the number of edges incident to a vertex, which may be exponential. However, the computational effort is rewarded with a wealth of information that can be gained from the results, which we highlight through some proof-of-concept computations.

Keywords: clustering; linear programming; power diagram; polyhedron; normal cone; stability (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1779 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:1:p:215-231

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().