An Algorithm for the Separation-Preserving Transition of Clusterings
From MaRDI portal
Publication:6355772
arXiv2012.05929MaRDI QIDQ6355772FDOQ6355772
Authors: Steffen Borgwardt, Felix Happach, Stetson Zirkelbach 
Publication date: 10 December 2020
Abstract: The separability of clusters is one of the most desired properties in clustering. There is a wide range of settings in which different clusterings of the same data set appear. We are interested in applications where there is a need for an explicit, gradual transition of one separable clustering into another one. This transition should be a sequence of simple, natural steps that upholds separability of the clusters throughout. We design an algorithm for such a transition. We exploit the intimate connection of separability and linear programming over bounded-shape partition and transportation polytopes: separable clusterings lie on the boundary of partition polytopes, form a subset of the vertices of the corresponding transportation polytopes, and circuits of both polytopes are readily interpreted as sequential or cyclical exchanges of items between clusters. This allows for a natural approach to achieve the desired transition through a combination of two walks: an edge walk between two so-called radial clusterings in a transportation polytope, computed through an adaptation of classical tools of sensitivity analysis and parametric programming; and a walk from a separable clustering to a corresponding radial clustering, computed through a tailored, iterative routine updating cluster sizes and re-optimizing the cluster assignment of items.
Has companion code repository: https://github.com/szirkelbach/transitioning-separable-clusterings
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Linear programming (90C05) Applications of mathematical programming (90C90) Sensitivity, stability, parametric optimization (90C31) Polyhedra and polytopes; regular figures, division of spaces (51M20)
This page was built for publication: An Algorithm for the Separation-Preserving Transition of Clusterings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355772)
