A fuzzy hybrid hierarchical clustering method with a new criterion able to find the optimal partition

Classical fuzzy clustering methods are not able to compute a partition in a set of points when classes have nonconvex shape. Furthermore we know that in this case, the usual criteria of class validity such as fuzzy hypervolume or compactness-separability, do not allow to find the optimal partition. The purpose of our paper is to provide a clustering method able to divide a set of points into nonconvex classes without knowing a priori their number. We will show that it is possible to reconcile a fuzzy clustering method with a hierarchical ascending one while maintaining a fuzzy partition by a method called unsupervised fuzzy graph clustering. To that effect, we shall use the Fuzzy C-Means algorithm to divide the set of points into an overspecified number of subclasses. A fuzzy relation is then established between them in order to extract the structure of the set of points. It can be represented by a graduated hierarchy. Finally, we present a new criterion to find the cut of the hierarchy giving the optimal regrouping. This one allows to find the real classes existing into the set of points. The given results are compared with those obtained by other classical cluster validity criteria and we propose to study the influence of the number of initial subclasses on the final computed partition. (C) 2002 Elsevier Science B.V. All rights reserved.