Classification & Uniqueness of Clustering Functors

Clustering algorithms are a widely used tool in machine learning and data science that organize data points into “groups” by recognizing patterns. They have proven useful for dealing with ever-increasing amounts of data. We review a formalization and classifi- cation of clustering algorithms developed by Carlsson and Mémoli [CM10b]. For such formal clustering algorithms we will use the term clustering functor. An important theoretical result in the study of clustering algorithms is an impossibility theorem by Kleinberg [Kle02]. It states that no clustering algorithm can be rich, consistent and scale invariant at the same time. As identified by Carlsson and Mémoli, the so-called Vietoris- Rips clustering functor has some unique characterizing properties [CM10a, Thm. 18], [CM10b, Thm. 7.1]. The Vietoris-Rips clustering functor is based on the idea that for some threshold parameter δ > 0, we assign two data points to the same cluster if, ac- cording to some metric, they are δ-close to each other. It was previously shown that the Vietoris-Rips clustering functor satisfies a set of modified conditions from Kleinberg’s impossibility theorem [CM10b, Sec. 7.3.1]. By showing that these modified conditions imply the characterizing properties of the Vietoris-Rips clustering functor discussed by Carlsson and Mémoli, we were able to prove that the Vietoris-Rips clustering functor uniquely satisfies the modified conditions from Kleinberg’s impossibility theorem.