Journal of Classification 10:219-240 (1993)
Fixed Points Approach to Clustering (pdf)
Alexander V. Genkin, Institute for Problems of Information Transmission
Ilya B. Muchnik, Boston University
Assume that a dissimilarity measure between elements and subsets of the
set being clustered is given. We define the transformation of the set of subsets under
which each subset is transferred into the set of all elements whose dissimilarity to it is
not greater than a given threshold. Then a cluster is defined as a fixed point of this
transformation. Three well-known clustering strategies are considered from this point of
view: hierarchical clustering, graph-theoretic methods, and conceptual clustering. For
hierarchical clustering generalizations are obtained that allow for overlapping clusters
and/or clusters not forming a cover. Three properties of dissimilarity are introduced
which guarantee the existence of a fixed points for each threshold. We develop the
relation to the theory of quasi-concave set functions, to help give an additional
interpretation of clusters.
Keywords: Fixed points; Hierarchical clustering; Graph-theoretic clustering; Conceptual clustering; Overlapping clusters.