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.