Fixed points approach to clustering |
| |
Authors: | Alexander V Genkin Ilya B Muchnik |
| |
Institution: | (1) Institute for Problems of Information Transmission, Yermolovoj 19, 101447 Moscow, Russia;(2) College of Engineering, Biomolecular Center, Boston University, 36 Cummington St., 02215 Boston, MA, USA |
| |
Abstract: | 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 transformed 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 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 |
本文献已被 SpringerLink 等数据库收录! |
|