Stable Clusterings and the Cones of Outer Normals

Felix Happach ()
Additional contact information
Felix Happach: Technische Universität München

A chapter in Operations Research Proceedings 2017, 2018, pp 37-43 from Springer

Abstract: Abstract 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.

Keywords: Clustering; Normal cone; Polyhedron; Power diagram; Linear programming (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:spr:oprchp:978-3-319-89920-6_6

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_6

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().