Median fuzzy c-means for clustering dissimilarity data

Abstract

Median clustering is a powerful methodology for prototype based clustering of similarity/dissimilarity data. In this contribution we combine the median c-means algorithm with the fuzzy c-means approach, which is only applicable for vectorial (metric) data in its original variant. For the resulted median fuzzy c-means approach we prove convergence and investigate the behavior of the algorithm in several experiments including real world data from psychotherapy research.

Introduction

Clustering of objects frequently is seen as a partitioning of objects/data into smaller subsets such that those objects are grouped together, which have a similar semantically meaning, characteristics, or behavior. Thereby, the clustering approaches may differ in various aspects like flat or hierarchical structure, crisp or soft (fuzzy) cluster assignments, visualization driven approaches, etc. Yet, the similarity is frequently difficult to capture. For metric data usually the Euclidean metric is applied. However, this favored choice may be inappropriate as it is the case in functional data analysis, for example [44]. Generally, the problem of an adequate chosen similarity is crucially and heavily influencing the clustering result as well as the number of meaningful clusters [24], [47]. A further problem arising in clustering is the choice of an appropriate quality criteria for a given cluster solution. This problem leads to a large number of quality measures for cluster solutions [43]. Prominent examples are the Fishers information relating the intra- and the inter-cluster correlation, the $\kappa$ statistics based on ${\chi }^2\text{−}\mathrm{statistics}$ or Bezdek's cluster index [16].

Basic classic cluster approaches like hierarchical clustering, agglomerative clustering or probabilistic clustering are known from mathematical statistics [46]. Another widely applied paradigm is the prototype based clustering [16]. One basic advantage of prototype based methods in this field, like the famous c-means, is their intuitive understanding by the concept of prototypes as representatives for the clusters [32]. Several prototype based methods have been established ranging from statistical approaches [48] and graph methods [37] to neural vector quantizers [20], [26], [42].

Further, one can distinguish between hard and soft variants of cluster algorithms [4], [13], [20]—the most famous of which is fuzzy c-means [17]. Frequently, respective approaches belong to the class of vector quantizers, requiring the data objects and the prototypes to be embedded in a metric vector space. Popular algorithms are, despite the above mentioned c-means variants, the neural gas [38], deterministic annealed vector quantization [45], information theoretic clustering [36] or topographic quantizers like self-organizing maps [34], or soft topographic vector quantization [25], to name just a few. All these algorithms use similarities between objects and prototypes which are described in terms of (Euclidean) distances for cluster determination [35].

Another class of prototype based cluster algorithms relaxes the assumption of a metric space embedding for the objects to be clustered and the prototypes [28], [12], [33]. This restriction is replaced by the weaker requirement that only similarities/dissimilarities or discrete measures between the data objects are given. Respective algorithms are referred as median or relational clustering, message passing or graph clustering methods [19], [49], [11]. Thereby, an underlying metric is assumed for the given dissimilarities in case of relational data clustering, whereas for median clustering this restriction is dropped. These degrees of freedom lead to constraints for the prototypes. For relational data they are assumed as linear combinations of the data. For median clustering this limitation is further reduced to the minimum demand: prototypes have to be data objects.

Fuzzy clustering of relational data based on fuzzy c-means was proposed by Hathaway et al. [31] inspired by the earlier work of Windham about graded numerical classification of dissimilarity data [54]. This approach was extended by Hathaway and Bezdek for more general dissimilarity data, which have to be, however, at least positive, reflexive and symmetric: In this extension the (non-Euclidean) dissimilarity matrix is transformed by the $\beta \text{−}\mathrm{spread}$ transform into an Euclidean matrix, such that the clustering is not longer realized on the original data [30]. Other approaches use the Dempster–Shafer theory of belief functions (or evidence theory) to determine a basic belief assignment (or mass function) to each object in such a way that the degree of conflicts between the masses given to any two objects reflects their dissimilarity [14], [39].

In the present contribution we extend the fuzzy c-means for general dissimilarity data based on the idea of median clustering, i.e. we restrict the prototypes to be data points itself. In this way we continue the work of Hathaway and Bezdek. For this purpose we combine fuzzy c-means with methodology introduced for crisp median clustering [11]. We investigate the new algorithm for synthetic as well as real world data and compare it to other fuzzy clustering methods. For this purpose, we use a fuzzy variant of Cohen's-$\kappa$ for pairwise and the Fleiss’-$\kappa$ for multiple comparisons.