Text

An Algorithm for the Separation-Preserving Transition of Clusterings

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 for which 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 and 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 reoptimizing the cluster assignment of items.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON OPTIMIZATION; Vol.5 No.1 Winter 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 1-26

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

LINEAR PROGRAMMING
SEPARABLE CLUSTERINGS
PARTITION POLYTOPES

Info Detail Spesifik

https://doi.org/10.1287/ijoo.2022.0074

Pernyataan Tanggungjawab

Steffen Borgwardt, Felix Happach, Stetson Zirkelbach

Versi lain/terkait

Lampiran Berkas

Komentar