NERF C-MEANS - NON-EUCLIDEAN RELATIONAL FUZZY CLUSTERING

The relational fuzzy c-means (RFCM) algorithm can be used to cluster a set of n objects described by pair-wise dissimilarity values if (and only if) there exist n points in R(n-1) whose squared Euclidean distan ces precisely match the given dissimilarity data. This strong restrict ion on the dissimilarity data renders RFCM inapplicable to most relati onal clustering problems. This paper substantially improves RFCM by ge neralizing it to the case of arbitrary (symmetric) dissimilarity data. The generalization is obtained using a computationally efficient modi fication of the existing algorithm that is equivalent to applying a '' spreading'' transformation to the dissimilarity data. While the method given applies specifically to dissimilarity data, a simple transforma tion can be used to convert similarity relations into dissimilarity da ta, so the method is applicable to any numerical relational data that are positive, reflexive (or anti-reflexive) and symmetric. Numerical e xamples illustrate and compare the present approach to problems that c an be studied with alternatives such as the linkage algorithms.