A review of some popular fuzzy cluster validity indices is given. An index that is based on the generalization of silhouettes to fuzzy partitions is compared with the reviewed indices in conjunction with fuzzy c-means clustering.
Prevalent in many applications,
The c-means, alternatively k-means
It is common to define the pairwise similaritiesdissimilarities in terms of distances which, in turn, give a structure i.e. the dataset underlying structure. The clustering algorithm, by processing the pairwise distances implicitly or explicitly, produces a structure, a partition. Its success is determined by the extent to which the produced partition aligns with the underlying structure, or more precisely, agrees with the pairwise distances. Supplying inconsistent values for , forces the algorithm either to separate similar points or to group dissimilar points in the same cluster. Hence the issue of cluster number is crucial and largely affects clustering quality. Even by choosing features and a measure consistent with the end-use, the inherent number of clusters might be unknown. For example, in a topic-driven clustering application, terms that are significant to each possible topic or common theme might be universally known, but the number of topics represented by documents in a particular dataset is unknown. Even if the cluster number is guessed correctly, there is the unfortunate possibility of obtaining a suboptimal clustering due to local optimum convergence. Besides, clustering of different types, crisp versus fuzzy, can be obtained on the same dataset. For “this and that kind” of reasons, cluster analysis is incomplete without the assessment of clustering quality. The issues of cluster number and quality are the main concerns of cluster validity.
This study reviews some fuzzy cluster validity indices then presents a generalization of silhouettes to fuzzy partitions. The performance of all reviewed indices is compared, with discussion, using two different datasets.
FCM, described in
Modeling the pairwise similarities-dissimilarities by a
distance measure restates the goal of clustering as the
search for optimally compact and separated clusters. One
cluster is compact only if its member points are within
small proximity from each other. Two clusters are well
separated only if their member points are distant from each
other. Accordingly, the variance-based criterion found in
cmeans can be thought of as a measure of compactness,
which was shown to be equivalent to a measure of
separation for the same number of clusters
The partition coefficient, PC, is defined as the Frobenius
norm of the membership matrix, divided by the number of
points, as in
∑ ∑
(6)
The coefficient is bounded by and 1, if applied to FCM
output. Its use as a measure of partition fuzziness was first
investigated by Bezdek in his Ph.D. dissertation
An index that really measures compactness and separation
was proposed by Xie and Beni, XB index
The development of the index started as part of work that
formulates clustering as a problem of maximum likelihood
estimation (MLE) of a mixture of multivariate densities
Gath and Geva in
Pakhira et el. proposed an index, referred here as PBM,
that targets both fuzzy and crisp partitions
{ ∑ ∑ ( } ) ) In (10), is the center of the whole dataset. The index can be factorized into a measure of compactness ∑ ∑ ( ) (10) (11) (12) (13) is a measure of the set clustering quality. To illustrate silhouette construction, consider for the data point , the cluster to which has been assigned, , and let be any cluster different than . The silhouette is defined in terms of a measure of compactness and a measure of separation . The average distance of to points in computes while is the minimum average distance from to all other clusters. Let denotes the cluster corresponding to (see Fig. 2). Clearly, (14) evaluates to values in [ ]. The average silhouette over a cluster or the whole dataset are given respectively by ∑ {
} ∑ ∑ ∑ a measure of separation and an artificial factor, irrelevant to compactness and separation, {
} ∑ ( ) The whole term in (10) is raised to power two that is also irrelevant to the assessment of clustering quality. Larger values of the index are assumed to indicate better clustering. It can be noticed though that the quantity in (12) does not necessarily capture the separation between all pairs of clusters; an authentic separation measure should account for the poor separation found in partitions into large number of clusters. .
Rousseeuw proposed an index for the validation of crisp
partitions
From the data point perspective, the measure assumes positive values if the separation distance is larger than the compactness distance and negative values if vice versa. A value near zero indicates that the point is at clusters boundary region, of course in the context of clustering on hands. At the coarser cluster level, the average silhouette indicates weak structure if near zero, strong if near +1 and misclustering if near -1. Since a clustering algorithm cannot do any better than the underlying structure, an average close to +1 is attainable only in the presence of a strong structure.
The following appealing properties recommend the silhouette index: (14) (15) (16) As opposed to other indices, it validates a given clustering at point level, providing thus the finest granularity. It is algorithm-independent. It takes as input only the pairwise similaritiesdissimilarities and the membership matrix. As explained in the original work of Rousseeuw, it can be used to ‘visualize’ the clustering quality of a given partition. Its assessment of compactness and separation conforms literally to the stated goal of clustering; a relatively small compared to means that has been successfully grouped with its similar points in the same cluster in a way that separates from its dissimilar points.
The above construction of silhouettes is not directly
applicable to fuzzy partitions since it requires crisp cluster
boundaries, necessary to the computation of cluster
average distances. Nevertheless, a fuzzy partition might be
validated by silhouettes after being defuzzified, for
example, by setting the maximum membership degree of
each point to one and nullifying the rest. However, this
discards cluster overlapping, defeating the reason of using
FCM not HCM. An extension that integrates fuzzy values
with silhouettes, computed from the defuzzified partition,
into an average silhouette-based index was proposed in
A generalization of silhouettes to fuzzy partitions is given in (Rawashdeh & Ralescu), based on the following central observations: A partition of a set of points into any number of clusters is essentially a clustering of the associated pairwise distances into intra-distances (within-cluster) and interdistances (between-cluster). A strong structure, a good clustering, has small intradistances and large inter-distances i.e. similar points are grouped together and dissimilar points are separated. In the context of a crisp partition, each distance is either intra-distance or inter-distance. This is modeled by intrainter scores associated to a distance that assume the values 0 and 1, indicating distance membership. In the context of a fuzzy partition, two points belong to each cluster simultaneously and separately with some degree, intuitively suggesting the assignment of fuzzy intra-inter scores to the pairwise distances, The original construction of silhouettes, which already incorporates the pairwise distances, is reformulated to employ intra-inter scores. The following is applicable to both crisp and fuzzy partitions, and it carries similar computation as in the original construction, provided that the partition is crisp. As input, the construction requires the pairwise distances and the membership matrix . Step 1. Given a partition into clusters, each distance , associated with and , is intra-distance with respect to either cluster and inter-distance with respect to any of the 2-combinations of clusters. The following constructs all of the intra-inter matrices: , (18) (19) } (20) } (21) Step 2. With respect to each point , weighted means over the associated distances are computed, using intrainter scores as weights; from which the compactness distance and the separation distances are selected. That is Step 3. The silhouette of each point is found using (14). Similar to the original average index, the average intrainter silhouette, gSil, over members of the whole dataset is an assessment of its clustering quality. For each fuzzy cluster, a weighted mean using point membership values as weights, is a measure of its clustering quality.
For further evaluation of the validity indices presented above, a few concrete examples are considered as follows:
Clustering algorithms rely on pairwise distances to form their output and this should be taken into consideration when testing any proposed validity index. Consider the dataset given in Fig. 3. It is tempting to claim that is the optimal number of clusters, however, this requires a similarity measure better to the task, than the Euclidean distance.
Although HCM, using the Euclidean distance, successfully detects the two clusters, XB, PBM, Sil, eSil and gSil all score better than due to better compactness (Fig. 4). Only FHV gives a better score, since it is based on fitting the data with a mixture of Gaussians. A single bi-Gaussian fits the overlapping clusters in Fig. 4b better than two Gaussians, assuming the crisp probabilitymembership values produced by HCM.
Different FCM partitions, using , were obtained on a dataset shown in Fig. 5.
Fig. 6 shows the performance of PC, Sil, eSil and gSil. PBM, XB and FHV are shown in Figs. 7, 8 and 9 respectively.
The extended index, eSil, scores the partition with clusters (Fig. 5a) higher than the one with clusters (Fig. 5b). A different ranking is suggested by the original index, Sil, and the generalized index, gSil. Both Sil and eSil incorporate the same silhouettes that are computed from the defuzzified membership matrix; clearly, the disagreement is caused by the weights in eSil. The points that occupy the undetected middle cluster (Fig. 5a) are not assigned high memberships to any of the three detected clusters; hence, they have low weights. The index eSil just ignores these points that are of insignificant weights and of approximately zero silhouettes. For the same reason, eSil always appears above the curve of Sil. The generalized index gSil can be naturally applied to both crisp and fuzzy partitions. It accounts for changes in the parameter and does not require any defuzzification of partitions. It scores highest the partition with clusters (Fig. 5c). The PBM index evaluates the clustering in Fig. 5d as the best. The separation measure, maximum center-to-center distance, does not decrease with even after reaching the cluster number that is sufficient for a good clustering of the dataset. In addition, the compactness measure decreases monotonically with , provided a reasonable clustering algorithm is used. Therefore, PBM has a nondecreasing behavior with that can be easily exposed using small toy datasets. Moreover, it is not recommended to use any factor that is irrelevant to the assessment of compactness and separation, as part of a validity index.
The XB index also fails in its ranking; it scores better than . The separation measure, minimum center-tocenter distance, does not account for the spread of detected clusters: in Fig. 5a, the centers are well separated but there is overlapping among the clusters in the middle region. The separation measure is not thorough in its assessment as opposed to silhouette-based indices that make assessments at point level. Therefore, XB is not reliable to detect good cluster numbers, and to compare between any two partitions, in general; it is in disagreement with the silhouette-based indices in its scoring of the partitions with and .
Distance-based similarities and dissimilarities are inferred from how distance values compare with each other, not from distance magnitudes. Hence, the strength of the underlying structure is determined by distance values relative to each other. Since the quotient in (14) is just a difference in compactness and separation relative to their maximum, an average over the whole dataset measures the strength of a given clustering. Values close to +1, obtained from the average silhouette index, indicate good clustering and a strong underlying structure as well. It is worth noting that, silhouette-based indices are also scale-invariant that is, scaling the dataset by some factor, multiplying by 100 for example, does not affect their values since the structure is still the same. This is not the case for FHV and PBM. Hence, silhouette-based indices are easier to interpret.
A satisfactory or useful clustering requires careful selection of the features and the measure which, combined together, define the pairwise similarities-dissimilarities. Clustering algorithms, probably of different models, by varying model parameters, as in cluster number, produce partitions, candidate structures. The job of a validity index is to find the candidate that is best supported by the pairwise similarities-dissimilarities, in other words, the clustering that best aligns with the underlying structure. FCM is used mainly to model cluster overlapping in datasets, facilitated by partial cluster memberships assigned to the points, which also results in points in the same cluster taking different membership values. The generalized silhouette index is applicable to both approaches, crisp and fuzzy, of structure modeling to guide the search for the best structure in the dataset.