{"id":526,"date":"2019-01-08T08:25:56","date_gmt":"2019-01-08T08:25:56","guid":{"rendered":"http:\/\/csp15.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=526"},"modified":"2019-01-08T09:22:44","modified_gmt":"2019-01-08T09:22:44","slug":"cluster-analysis-and-cluster-validity","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp15\/chapter\/cluster-analysis-and-cluster-validity\/","title":{"rendered":"Cluster Analysis and Cluster Validity"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\nLearning Objectives:<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand the Cluster Validity and Cluster Validation Process\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To\u00a0 discuss the different Measures of Cluster Validity\r\n\r\n\u2022\u00a0\u00a0\u00a0\u00a0\u00a0 To understand External, Internal and the Statistical Framework for determining Cluster Validity\r\n\r\n \r\n\r\n25.1 Cluster Validity<\/strong>\r\n\r\n \r\n

Let us first give a definition of validation of clustering. \u201cThe validation of clustering structures is the most difficult and frustrating part of cluster analysis. Without a strong effort in this direction, cluster analysis will remain a black art accessible only to those true believers who have experience and great courage.\u201d-[Jain & Dubes]<\/p>\r\n \r\n

For cluster analysis, the question is how to evaluate the \u201cgoodness\u201d of the resulting clusters? But as it is said the clusters can be defined from different perspectives. However validation is needed to compare clustering algorithms, solve the problem of determining the number of clusters, comparing two clusters, comparing two sets of clusters, and for avoiding finding patterns in noise.<\/p>\r\n \r\n

Now let us understand a simple evaluation of clustering using precision and recall. Let us see the example given in Figure 25.1. Here we see that is a total of 5 oranges and 5 apples. The clustering produces two clusters, cluster 1 with 5 oranges and 2 apples and cluster 2 with 3 apples. Precision in this context is\u00a0defined as the number of items of a particular category (oranges or apples) obtained in the cluster divided by total number of items .of that category. Recall on the other hand is defined as the number of items of a particular category cluster. Accordingly precision and recall of oranges and are given in Figure 25.1. Note that these measures can be determined only if the ground truth is given. We will discuss these measures in detail later in the module.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.1 Precision and Recall of Clustering<\/strong><\/p>\r\n \r\n\r\n25.2 Good Clustering<\/strong>\r\n\r\n \r\n

We will now discuss the issues of good clustering. First we have the internal criterion which defines good clustering as a clustering that produces high quality clusters in which the intra-class similarity is high and the inter-class similarity is low. The measured quality of a clustering depends on both the representation of the items that are to be clustered and the similarity measure used. On the other hand external criterion measures the quality of a clustering by its ability to discover some or all of the hidden patterns or latent classes available, where we compare the clustering results to gold standard data.<\/p>\r\n \r\n\r\n25.3 Aspects of Cluster Validation<\/strong>\r\n\r\n \r\n

Cluster validation involves evaluation of the clustering using external index by comparing the clustering results to ground truth<\/em> (externally known results). Evaluation of the quality of clusters without<\/em> reference to external information using only the data is called as evaluation using internal index. Another aspect is determining the reliability<\/em> of clusters, that is the confidence level that the\u00a0clusters are not formed by chance, normally determined using a statistical framework.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n25.3.1 Cluster Validation process<\/strong>\r\n\r\n \r\n\r\nNow let us discuss the process of cluster validation. The following are the steps involved:\r\n\r\n \r\n

1. The first step is to find out whether the set of data has the clustering tendency that is distinguishing whether non-random structures actually exist in the data or whether the set of data is actually one cluster (Figure 25.2). Figure 25.2 shows the clusters obtained for different algorithms for random points.<\/p>\r\n \r\n\r\n\"\"\r\n

Figure 25.2 Clustering of Random Points<\/strong><\/p>\r\n \r\n

2. The next step is the comparison of the results of a cluster analysis to the externally known results,that is<\/p>\r\n

to externally given class labels.<\/p>\r\n \r\n

3. The third step is the evaluation how well the results of a cluster analysis fit the data without<\/em> reference to<\/p>\r\n

external information. Use only the data.<\/p>\r\n \r\n

4. Then we carry out the comparison of the results of two different sets of cluster analyses to determine<\/p>\r\n

which is better.<\/p>\r\n \r\n\r\n5. Finally we have the important task of determining the \u201ecorrect\u201f number of clusters for the given data set.\r\n\r\n \r\n

In cluster validation, the steps 2, 3, and 4, can be further distinguished dependingon whether we want to evaluate the entire clustering or just individual clusters.<\/p>\r\n \r\n

According toJain & Dubes, cluster validation refers to procedures that evaluate the results of clustering in a quantitative<\/strong> and objective<\/strong> fashion. In this context evaluation is quantitative when we employ the measures for evaluation while it is objectivewhen wevalidate of the measures.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.3 Clustering and Evaluation<\/strong><\/p>\r\n \r\n

Figure 25.3 shows that for a given data set X, we can apply the clustering algorithm and given the gold standard in terms of different partitions P and the associated codebook C, determine the validity index. The process is repeated by trying out with different number of clusters.<\/p>\r\n \r\n\r\n25.3.2 Measures of Cluster Validity<\/strong>\r\n\r\n \r\n

As we have already discussed, external index is where we validate against ground truth, or compare two clusters to find out the similarity between them (Figure 25.4). Figure 25.4 also illustrates the determination of the internal index where we validate without<\/em>any external information, and if we do the same with different number of clusters we can solve the problem of determining the number of clusters.<\/p>\r\n\"\"\r\n

Figure 25.4External Index and Internal Index<\/strong><\/p>\r\n \r\n\r\n25.4Comparing with Ground Truth<\/strong>\r\n\r\n \r\n\r\nNow let notation for comparing with ground truth be as follows:\r\n\r\nN: number of objects in the data set;\r\n\r\nP={P1,\u2026,Pm}: the set of \u201cground truth\u201d clusters;<\/span>\r\n\r\nC={C1,\u2026,Cn}: the set of clusters reported by a clustering algorithm.<\/span>\r\n\r\n \r\n

Now we create the \u201cincidence matrix\u201d, which is a N \u00b4 N matrix where both the rows and columns correspond to objects. Pij = 1 if object Oi and object Oj belong to the same \u201cground truth\u201d cluster in P; Pij=0 otherwise. Similarly Cij = 1 if object Oi and object Oj belong to the same cluster in C; Cij=0 otherwise.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nA pair of data object (Oi,Oj) falls into one of the following categories :\r\n\r\n\"\"\r\n

Now we define two evaluation measures based on this incidence matrix, Rand index and Jaccard coefficient. Rand Index may be dominated by DD, which is about objects not belonging to the same cluster in either the ground truth case or in the clusters obtained through the clustering algorithm.<\/p>\r\n\"\"\r\n\r\n25.5 Purity Based Measures<\/strong>\r\n\r\n \r\n\r\nNow let us discuss another method used to find external index. Here we assume that the class of each object is available. The confusion matrix is given in Figure 25.5\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.5 Confusion Matrix <\/strong><\/p>\r\n \r\n

given in Figure 25.5. Here the details are as follows:<\/p>\r\n\u2022\u00a0 n = the number of points\r\n\r\n \r\n\r\n\u2022\u00a0 \u00a0mi<\/sub>= the points in cluster i\r\n\r\n \r\n\r\n\u2022\u00a0 cj<\/sub> = the points in class j\r\n\r\n \r\n\r\n\u2022\u00a0 \u00a0nij<\/sub>= the points in cluster i coming from class j\r\n\r\n \r\n\r\n\u2022\u00a0\u00a0\u00a0pij<\/sub>=nij<\/sub>\/mi\u00a0 = probability of element from cluster i to be assigned in class j\r\n\r\n \r\n\r\n \r\n\r\n25.5.1 Purity Based Measures<\/strong>\r\n\r\n \r\n

We can define two measures entropy and purity. Both these measures can be measured for a cluster or for a clustering which is the evaluation of the complete set of clusters. Entropy of a cluster is based on probabilitypijof element from cluster i being assigned to class j. Here L is the total number of classes and K the total number of clusters.<\/p>\r\n\"\"\r\n

Entropy of a clustering is based on average entropy of each cluster as well as the total number of objects in the data set n. This value is highest when objects belong uniformly across clusters and zero when objects belong to a single cluster.<\/p>\r\n \r\n

Purity of a cluster i <\/strong>is the class j for which the probability pijthat is the probability that an element from cluster i is assigned to class j.<\/p>\r\n \r\n\r\nPurity of a cluster: pi<\/sub>=maxj<\/sub>\u00a0pij<\/sub>\r\n\r\n\"\"\r\n\r\n<\/div>\r\n \r\n

The purity of the clustering C is based on average of the purity of each cluster pi, the points in cluster i and the total number of objects in the data set n.<\/span><\/p>\r\n \r\n\r\n25.5.2 Precision and Recall<\/strong>\r\n\r\n \r\n\r\nPrecision<\/strong> of cluster i <\/strong>with respect to class j:prec(i,j)=pij<\/sub> where pij<\/sub> is theprobability of element from cluster i to be assigned in class j\r\n\r\n \r\n\r\nRecall of cluster i <\/strong>with respect to class j: Rec(i,j) =nij\/<\/sub>cj\u00a0<\/sub>where nij<\/sub>\u00a0is the\u00a0<\/span>number of data points in cluster i coming from class j and cj<\/sub> is the total number of data points in class j<\/span>\r\n

\r\n\r\n \r\n\r\nF-measure <\/strong>is defined as the Harmonic Mean of Precision and Recall:\r\n\r\n\"\"\r\n\r\n25.5.3 Precision\/Recall for Clusters and Clustering<\/strong>\r\n\r\n \r\n

We normally assign to cluster the class which is the class j such that cluster i has the maximum number of data <\/em>points coming from class j<\/p>\r\n\"\"\r\n

Now we define the Precision of cluster i as<\/strong>\u00a0 prec(i)= ni<\/sub>ki\/<\/sub>mi<\/sub>\u00a0 where mi<\/sub>ki\u00a0<\/sub>is the number of data points in cluster i coming from class and is the total number of data points in cluster i.<\/p>\r\n\"\"\r\n\r\n<\/div>\r\n

<\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\n25.5.4 Good and Bad Clustering<\/strong>\r\n\r\n \r\n

Now let us understand the evaluation using the examples given in Figure 25.6. We had discussed that the purity of a cluster i<\/strong> is the class j for which the probability of pij, an element from cluster i being assigned to class j. Purity of a cluster i: = .<\/strong> In Figure 25.6 (a), the purity of cluster 1 is Max value of cluster divided by the total number of data points in class 1 i.e. 85\/90=0.94, that\u00a0of cluster 2 is 90\/110=0.81, and that of cluster 3 is 85\/100=0.85. The overall purity of the clustering is 0.86. Similarly we can find the precision and recall for each cluster and for the overall clustering. Figure 25.6 (b) shows another example with the calculated evaluation measures. As we can see in Figure 25.6<\/span><\/p>\r\n \r\n

a)\u00a0 a good clustering has high values of purity, precision and recall while a bad clustering. of Figure 25.6 (b) has low values of purity, precision and recall is<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.6 Good and Bad Clustering<\/strong><\/p>\r\n \r\n\r\n25.6 Internal Measure<\/strong>\r\n\r\n \r\n

As discussed previously internal measures are used to measure the goodness of a clustering structure without comparing with external information. There are basically two aspects that are considered namely cohesion<\/strong>whichmeasures how closely related the data points in a cluster are and separation<\/strong>which measures how distinct or well-separated the data points of a cluster are from the data points of other clusters (Figure 25.7). These aspects can be measured using sum of squares and sum of squared error.<\/p>\r\n \r\n\r\n\"\"\r\n

Figure 25.7 Cohesion and Separation<\/strong><\/p>\r\n \r\n\r\n25.6.1 Internal Measure -Sum of Squares<\/strong>\r\n\r\n \r\n\r\nWhen we measure cluster cohesion, we measure homogeneity measured by the within cluster sum of squares<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\nCluster Separation is measured by the between cluster sum of squares\r\n\r\n\"\"\r\n\r\n \r\n\r\nThe sum of BSS + WSS = constant. In general, a larger number of clusters tend to result in smaller WSS as shown in the example (Figure 25.8)\r\n\r\n\"\"\r\n

Figure 25.8 Example of WSS an BSS with Different Number of Clusters<\/strong><\/p>\r\n \r\n\r\nInternal Measure SSE curve for a more complicated data set is shown in Figure 25.9.\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.9 SSE for a Complex Data Set 25.6.2 Internal Measure \u2013Average Distance<\/strong><\/p>\r\n \r\n

In the same spirit as the sum of squareswe alsodefine Cohesion a<\/em>(x<\/em>)<\/strong>as theaverage distance of x<\/em> to all other vectors in the same cluster. We also define Separation b<\/em>(x<\/em>)<\/strong>as theaverage distance of x <\/em>to the vectors in other clusters. We find the minimum among the clusters<\/p>\r\n \r\n\r\n25.6.3 Internal Measure -Silhouette coefficient<\/strong>\r\n

Another important internal measure is theSilhouetteCoefficients(x)<\/strong>which is defined below. We first define silhouette as:<\/p>\r\n\"\"\r\n

We use the above to define the Silhouette coefficient (SC) to find the silhouette of all the N data points :<\/p>\r\n\"\"\r\n\r\n25.7 Correlation with Distance Matrix<\/strong>\r\n\r\n \r\n

We will down define two matrices, the proximity\/distance matrix and the incidence matrix. The proximity matrix \/distance matrix is a matrix having rows and columns equal to the number of objects where each entry Dij is the similarity between object Oi and Oj. The incidence matrix has one row and one column for each data point and the entry is 1 if the associated pair of points belong to the same cluster and 0 if the associated pair of points belong to different clusters.<\/p>\r\n \r\n

Now we need to compute the correlation between the two matrices. Here we need to calculate only n(n-1)\/2 entries. High correlation indicates good clustering.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\nGiven Distance Matrix D = {d<\/em>11<\/em>,d<\/em>12<\/em>, \u2026, d<\/em>nn<\/em> }<\/em> and Incidence Matrix C= { c<\/em>11<\/em>,<\/em>c<\/em>12<\/em>,\u2026, c<\/em>nn<\/em> } <\/em>.\r\n\r\n \r\n\r\nCorrelation r<\/em> <\/strong>between D and C is given by\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nThis is not a good measure for some density or contiguity based clusters.\r\n\r\n \r\n

Correlation of incidence and proximity matrices for the K-means clustering of two data sets with different values is shown in Figure 25.10.<\/p>\r\n\"\"\r\n

Figure 25.10. Correlation Values Using Distance Matrix 25.7.1 Using Similarity Matrix for Cluster Validation<\/strong><\/p>\r\n \r\n

We can order the similarity matrix with respect to cluster labels and inspect visually. This is shown in Figure 25.11 which is a good clustering. Clusters in random data are not so crisp and is shown in Figure 25.12.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.11 Good Clustering<\/strong><\/p>\r\n\"\"\r\n

Figure 25.12Example of Clustering<\/strong><\/p>\r\n \r\n\r\n25.8 Statistical Framework for SSE<\/strong>\r\n\r\n \r\n

Now let us discuss some statistical aspects. Now let us consider the example where we compare the SSE (discussed previously) of 0.005 against three clusters in random data. The figure shows the SSE Histogram of 500 sets of random data points of size 100 distributed over the range 0.2 \u2013 0.8 for x and y values.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Correlation of incidence and distance matrices for the K-means of the following two data sets and the Histogram is shown in Figure 25.14.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

Figure 25.14 Histogram of Correlation with K means 25.8.1 Empirical p-value<\/strong><\/p>\r\n \r\n

Another measure of correlation is the empirical p-value. If we have a measurement v (e.g., the SSE value) and we have N measurements on random datasets, the empirical p-value is the fraction of measurements in the random data that have value less or equal than value v (or greater or equal if we want to maximize), in other words the value in the random dataset is at least as good as that in the real data. We usually require that p-value \u2264 0.05. However it is difficult to know the right notion of a random dataset.<\/p>\r\n \r\n\r\n25.8.2 Hyper Geometric Distribution<\/strong>\r\n\r\n \r\n

The next two measures of correlation or association are defined in terms of genes in a random data set. Given that the total number of genes in the data set associated with term T is M, if we randomly draw n genes from the data set N, the probability that m of the selected n genes will be associated with T is given as<\/p>\r\n \r\n\r\n\"\"\r\n\r\n25.8.3 P-Value<\/strong>\r\n\r\n \r\n

Based on Hyper-geometric distribution given above, the probability of having m genes or fewer associated to T in N can be calculated by summing the probabilities of a random list of N genes having 1, 2, \u2026, m genes associated to T. So the p-value of over-representation is as follows:<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n\r\nSummary<\/strong>\r\n