Stable Clusterings and the Cones of Outer Normals

We consider polytopes that arise in the cluster analysis of a finite set of data points. These polytopes encode all possible clusterings and their vertices correspond to clusterings that admit a power diagram, which is a polyhedral separation of the underlying space where each cluster has its own cell. We study the edges of these polytopes and show that they encode cyclical transfers of elements between clusters. We use this characterization to obtain a relation between power diagrams and the volume of the cones of outer normals of the respective clustering. This allows us to derive a new stability criterion for clusterings, which can be used to measure the dependability of the clustering for decision-making. Further, the results explain why many popular clustering algorithms work so well in practice.     «

We consider polytopes that arise in the cluster analysis of a finite set of data points. These polytopes encode all possible clusterings and their vertices correspond to clusterings that admit a power diagram, which is a polyhedral separation of the underlying space where each cluster has its own cell. We study the edges of these polytopes and show that they encode cyclical transfers of elements between clusters. We use this characterization to obtain a relation between power diagrams and the vo...     »