Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Classifying clustering schemes
Author: Carlsson, Gunnar
Memoli, Facundo
Citation: Foundations of Computational Mathematics, 2013; 13(2):221-252
Publisher: Springer
Issue Date: 2013
ISSN: 1615-3375
School/Discipline: School of Computer Science
Statement of
Funnar Carlsson and Facundo Mémoli
Abstract: 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.
Keywords: Clustering; functoriality; chaining effect; single linkage; data analysis
Rights: © SFoCM 2013
DOI: 10.1007/s10208-012-9141-9
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.