Published: Sept. 30, 2022

Steffen Borgwardt, Department of Mathematics, University of Colorado Denver

Transitions between Clusterings

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, different partitions of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another; such a scenario arises, for example, when a gradual transition from an old solution to a new one is required. Based on linear programming and network theory, we develop methods for the construction of a sequence of so-called elementary moves that accomplishes such a transition. Specifically, we discuss two types of transitions: short transitions with a low number of steps and transitions that retain separation of clusters throughout.