Cluster validity

Since the correct number of clusters is unknown, a cluster validity measure needs to be consulted for the evaluation of the clustering solution (Section 6.7). 

The number k of clusters being inherent in the data set is usually unknown, but it is needed as an input of the fc-means algorithm. Since the algorithm is very fast, it can be run for a range of different numbers of clusters, and the best result can be selected. Here, best refers to an evaluation of the results by cluster validity measures (see Section 6.7). 

Although model-based clustering seems to be restrictive to elliptical cluster forms resulting from models of multivariate normal distributions, this method has several advantages. Model-based clustering does not require the choice of a distance measure, nor the choice of a cluster validity measure because the BIC measure can be... 

A measure of cluster validity then combines these two criteria, for example, by summing up all cluster homogeneities and dividing by the sum of the heterogeneities of all cluster pairs. This results in a validity measure V(k) defined as... 

FIGURE 6.18 Cluster validity V(k), see Equation 6.13, for the algorithms fc-means, fuzzy c-means, and model-based clustering with varying number of clusters. The left picture is the result for the example used in Figure 6.8 (three spherical clusters), the right picture results from the analysis of the data from Figure 6.9 (two elliptical clusters and one spherical cluster). 

FIGURE 6.20 Cluster validities for the Hyptis data for two to nine clusters analyzed with the methods fc-means clustering, fuzzy clustering, and model-based clustering. For the left plot the original data were used, for the right plot the data were autoscaled. 

FIGURE 6.26 Cluster validity measures for the glass vessels data (left) and result from model-based clustering for k = 4 (right) as a projection on the first two robust principal components (compare Figure 3.10, right). 

The validity discriminant discussed in this section is the descendant of an earlier cluster validity measure used by Gunderson ( ) to assess the quality of cluster configurations obtained in an application of the Fuzzy ISODATA algorithms. It is closely related to a method suggested by Sneath ( ) for testing the distinctness, i.e. separation, of two clusters, and also borrows from the ideas of Fisher s linear discriminant theory (see chapt. 4, Duda and Hart,(2 0). The validity discriminant attempts to measure the separation between the classes of a cluster configuration usually, but not necessarily, obtained by application of the FCV algorithms. A brief description follows ... 

Table II summarizes the estimates obtained In the NILU study when using the methodology outlined above. Results for the Haga site have been boxed In for later comparison with results obtained using the cluster validity discriminant. The lower values for the 24h samples probably reflects their being collected when there was little land- or sea-breeze for transport of the emissions from the smelter. Daytime sea breezes would tend to transport emissions toward and past the Haga site, while the evening landbreezes would tend to transport emissions back toward the Haga site.

A Monte Carlo study demonstrated the problem of estimating the number of clusters [DUBES, 1987]. One principal reason for this problem is that clustering algorithms tend to generate clusters even when applied to random data [DUBES and JAIN, 1979]. JAIN and MOREAU [1987] therefore used the bootstrap technique [EFRON and GONG, 1983] for cluster validation. 

A major problem in cluster analysis is defining a cluster (see Figure 9.4). There is no measure of cluster validity that can serve as a reliable indicator of the quality of a proposed partitioning of the data. Clusters are defined intuitively, depending on the context... 

Xu, Y. and Brereton, R.G. (2005) A comparative study of cluster validation indices applied to genotyping data. Chemom. Intell. Lab. Syst., 78, 30-40. 

This chapter begins with a high-level overview of similarity measures followed by a discussion of the commonly used clustering approaches, including few exemplary applications in biomedical sciences. The final section of this chapter is devoted to cluster validity methods developed for measuring the compactness and separation quality of the clusters produced by the analysis. 

Cluster validation method Euclidean City block Pearson s dissimilarity Cosine dissimilarity... 

Given the same dataset, different choices of preprocessing, clustering algorithms, and distance measures could lead to varied clustering results. Therefore, the assessment of cluster validity is of utmost important. However, in practice, the cluster quality is hard to evaluate, particularly in the analysis of biological data. 

Cluster validity is a measure of correspondence between a cluster structure and the data within the structure (Mirkin, 2005). The adequacy of a clustering structure refers to the sense in which the clustering structure provides true information about the data (Jain and Dubes, 1988). The validity of a clustering structure can be expressed based on three different criteria (Jiang et al., 2004) ... 

Internal Measures Internal criteria assess the fit between the clustering structure and the data without prior knowledge. Internal measures are the most appropriate cluster validity criteria for unsupervised clustering. Many internal measures of... 

Measures for Predictive Strength and Cluster Stability This type of cluster validity focuses on the reliability of clusters, that is, whether cluster structure was predicted by chance (Jiang et al., 2004). In addition, the analysis of predictive power, particularly in biological data analysis, is performed by investigating whether clustering results obtained from one set of experimental condition can be related to the ones from another set (Zhao and Karypis, 2005). 

Internal measures are unsupervised measures of cluster validity, pcifoimcd for the analysis of cluster quality in data without prior knowledge. This type of measure can be further divided into two classes measures of cluster cohesion (compactness) and measures of cluster separation. 

Handl, J., Knowles, J., and Kell, D. B. (2005). Computational cluster validation in post-genomic data analysis. Bioinformatics, 21(15) 3201-3212. 

---