Misc,
Classifying Clustering Schemes
(2010)cite arxiv:1011.5270.
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 data set, for example by adding points or by applying functions to it. We
show that within this framework, one can prove a theorems analogous to one of
J. Kleinberg, in which for example one obtains an existence and uniqueness
theorem instead of a non-existence 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.
