Classifying Clustering Schemes

By Gunnar E. Carlsson, Facundo M'emoli. 2010

98 citations recorded by the source corpus.

Many clustering schemes are defined by optimizing an objective function defined on the partitions of the underlying set of a finite metric space. In this paper, we construct a framework for studying what happens when we instead impose various structural conditions on the clustering schemes, under the general heading of functoriality. Functoriality refers to the idea that one should be able to compare the results of clustering algorithms as one varies the dataset, for example by adding points or by applying functions to it. We show that, within this framework, one can prove a theorem analogous to one of Kleinberg (Becker et al. (eds.), NIPS, pp. 446–453, MIT Press, Cambridge, 2002), in which, for example, one obtains an existence and uniqueness theorem instead of a nonexistence result. We obtain a full classification of all clustering schemes satisfying a condition we refer to as excisiveness. The classification can be changed by varying the notion of maps of finite metric spaces. The conditions occur naturally when one considers clustering as the statistical version of the geometric notion of connected components. By varying the degree of functoriality that one requires from the schemes, it is possible to construct richer families of clustering schemes that exhibit sensitivity to density.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Representation & Self-Supervised Learning, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. John Healy
2. Leland McInnes
3. Maarten Grootendorst
4. D. Angelov

In Computational Theory and Mathematics

1. John Healy
2. Leland McInnes

In Representation & Self-Supervised Learning

1. Leland McInnes
2. John Healy
3. Mohammad Rostami
4. Maarten Grootendorst
5. Dmitry Kobak
6. Soheil Kolouri
7. D. Angelov
8. Marta Ruiz Costa-jussà

In Signal Processing

1. John Healy
2. Leland McInnes
3. D. Angelov
4. Maarten Grootendorst

Citations in the corpus

• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2018, positive): “…FinEPMet . choice of non-expansive maps in Definition 6 is due to Spivak, but we note that it closely mirrors the work of Carlsson and Memoli in [3] on topological methods for clustering as applied to finite metric spaces. choice is significant since pure isometries are too strict and do not…”
• Accelerated Hierarchical Density Based Clustering (2017, unknown): “uite of techniques bringing the powerful tool of topology to bear on data analysis problems. Recently the techniques of topological data analysis have been brought to bear on clustering problems [9], [10], [13], [49], [50]. A number of insights can be gained by looking at HDBSCAN* through the lens o”