An Algorithm for the Separation-Preserving Transition of Clusterings
An Algorithm for the Separation-Preserving Transition of Clusterings
复制标题
DOI：
10.1287/ijoo.2022.0074
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
S. Borgwardt;Felix Happach;Stetson Zirkelbach
中科院分区：
文献类型：
--
作者：
S. Borgwardt;Felix Happach;Stetson Zirkelbach
聚类的可分离性是聚类中最需要的性质之一。同一数据集的不同聚类出现的设置范围很广。我们感兴趣的应用程序，有一个明确的，逐步过渡到另一个可分离聚类的需要。这种转换应该是一系列简单、自然的步骤，始终保持集群的可分离性。我们为这种转换设计了一个算法。我们利用有界形状分割和运输多面体上的可分性和线性规划之间的密切联系：可分聚类位于分割多面体的边界上，形成相应的运输多面体顶点的子集，两个多面体的回路很容易被解释为簇之间的顺序或循环交换。这允许一种自然的方法通过两种行走的组合来实现期望的过渡：运输多形体中两个所谓的径向聚类之间的边缘行走，通过敏感性分析和参数规划的经典工具的改编计算，以及从可分离聚类到相应的径向聚类的行走，通过定制的迭代例程更新聚类大小和重新优化项目的聚类分配来计算。
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.