Classifying clustering schemes
Date
2013
Authors
Carlsson, Gunnar
Memoli, Facundo
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Foundations of Computational Mathematics, 2013; 13(2):221-252
Statement of Responsibility
Funnar Carlsson and Facundo Mémoli
Conference Name
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.
School/Discipline
School of Computer Science
Dissertation Note
Provenance
Description
Access Status
Rights
© SFoCM 2013