Title: Good Clusterings Have Large Volume,
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.