logging in or signing up Cluster Analysis 1 Introduction untellectualism Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: Embed: Flash iPad Dynamic Copy Does not support media & animations Automatically changes to Flash or non-Flash embed WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 8160 Category: Education License: All Rights Reserved Like it (5) Dislike it (0) Added: May 11, 2008 This Presentation is Public Favorites: 5 Presentation Description Cluster Analysis 1 Introduction Comments Posting comment... Premium member Presentation Transcript Slide 1: 1 Cluster Analysis Motivation: why cluster analysis Dissimilarity matrices Introduction to clustering algorithms Slide 2: 2 Example1. Information and communications data – World’s countries The data we will consider Is it possible to describe the characteristics of countries with respect to ICT? Is it possible to individuate groups of countries with similar profiles? Which are the most common profiles of countries with respect to ICT? In other terms, which are the most relevant tendencies with respect to ICT? Is it possible to simplify the description of countries? Slide 3: 3 Cluster analysis aims at grouping observations in clusters Clusters should possibly be characterized by: High within homogeneity: observations in the same cluster should be similar (not dissimilar) High between heterogeneity: observations placed in different clusters should be quite distinct (dissimilar) This means that we are interested in determining groups internally characterized by an high level of cohesion. Also, different clusters should describe different characteristics of the observations Cluster analysis Slide 4: 4 Cluster analysis A basic concept in cluster analysis is dissimilarity between observations and, also, between groups. Let us first of all focus on observations. In the context of cluster analysis, a measure of the dissimilarity between two cases, say the i-th and the k-th, satisfies the following: WHAT IF dik = 0 ? dik= 0 does not mean that two cases are identical. This only means that they are not dissimilar with respect to the particular context under analysis Slide 5: 5 Cluster analysis Dissimilarities between observations are arranged in the so called dissimilarity matrix, a square (n × n) matrix, where n is the number of observations. Cases Cases The (i,k)-th element of the matrix is the dissimilarity between the i-th and the k-th case. The matrix is symmetric, since we assumed that di,k = dk,i In some applications the dissimilarity matrix is obtained by taking into account measurements on a set of variables. Different measures of dissimilarities have been introduced in literature depending on the characteristics of the involved variables. Hence, different dissimilarity matrices can be obtained. In other situations, the dissimilarity matrix may contain other kind of information, for example judgements about the dissimilarity between cases. In this case, the dissimilarity matrix is given. Slide 6: 6 Cluster analysis Example (synthetic data). Dissimilarity matrix How should we choose groups? We can individuate some close pairs (for example, obs 7 and obs 8 are closest). But how many groups should we consider? How can we properly assign each observation to a given group? Slide 7: 7 Cluster analysis Example (synthetic data). Simple example, 2 dimensions – graphical analysis 2 groups are clearly identifiable But maybe also 3 groups may be considered. Which cluster should obs11 and obs6 be assigned to? Slide 8: 8 Cluster analysis: methods We consider here two different approaches to cluster analysis Hierarchical (agglomerative) algorithms Partitioning algorithms Sequential procedures. At the first step, each observation constitutes a cluster. At each step, the two closest clusters are joined to form a new cluster. Thus, the groups at each step are nested with respect to the groups obtained at the previous step. Once an object has been assigned to a group it is never removed from the group later on in the clustering process. The hierarchical method produce a complete sequence of cluster solutions beginning with n clusters and ending with one clusters containing all the n observations. In some application the set of nested clusters is the required solution whereas in other applications only one of the cluster solutions is selected as the solution, i.e., the proper number of clusters has to be selected. Iterative procedures In these methods, the aim is to partition cases into a given number of clusters, say G. The algorithm usually begins with an initial solution (partition). Observations are then reallocated to cluster so as to maximize a pre-specified objective function. Objects possibly change cluster membership throughout the cluster formation process. Slide 9: 9 Cluster analysis: hierarchical algorithms Initial solution: n clusters (one for each observation) At each step: the two closest (lowest dissimilarity) clusters are joined to form a new cluster Slide 10: 10 Cluster analysis: hierarchical algorithms Hierarchical agglomerative algorithms At each step, we should join the two closest clusters. Our starting point is the dissimilarity matrix. It is almost easy to determine which are the two closest observations. Nevertheless, now a problem arises: how do we calculate the dissimilarity between one observation and one cluster or between two clusters? Definition of criteria to measure the Dissimilarity between groups of observations (clusters) Slide 11: 11 We limit attention to two approaches to measure dissimilarity between clusters 1. Criteria based on the dissimilarity between two properly chosen observations 2. Criteria based on syntheses of the dissimilarities or on dissimilarities between syntheses. For the sake of clarity, we illustrate the proposals by referring to a simplified 2-dimensional plot (synthetic data) may be applied also when a dissimilarity matrix is available (regardless of how it was obtained). We consider a 3-clusters partition and show how to measure the dissimilarity between 2 clusters. Cluster analysis: hierarchical algorithms Slide 12: 12 Single linkage: the dissimilarity between two clusters is measured by the smallest possible dissimilarity between cases in the two clusters (dissimilarity between the two closest cases) The two clusters with minimum single linkage are joined Single linkage: which clusters should be joined? The dissimilarity between two clusters is based on one of the possible pairs of observations Single linkage: SMALLEST DISSIMILARITY Cluster analysis: hierarchical algorithms – dissimilarity/clusters Slide 13: 13 Single linkage: It is a flexible method and it can individuate also clusters with particular shapes (elongated, elliptical) However, in cases when clusters are not well separated this method may lead to unsatisfactory solutions due to the so called chaining effect. Consider the three clusters 1-3 in the left panel. Clusters 1 and 2 are (“globally”) closer. Nevertheless, due to the presence of two very close cases in clusters 2 and 3, they will be joined instead. Another example is in the right panel. This last example evidences that this method may be useful in outliers detection. Cluster analysis: hierarchical algorithms – dissimilarity/clusters 1 3 2 Slide 14: 14 Complete linkage: the dissimilarity between two clusters is measured by the smallest possible dissimilarity between cases in the two clusters (dissimilarity between the two closest cases) The two clusters with minimum complete linkage are joined Complete linkage: which clusters should be joined? The dissimilarity between two clusters is based on one of the possible pairs of observations Usually clusters with similar diameters are obtained Single linkage Complete linkage: LARGEST DISSIMILARITY Depending on the criterion chosen to measure dissimilarity between clusters, different clusters are joined Cluster analysis: hierarchical algorithms – dissimilarity/clusters Slide 15: 15 Average linkage: The dissimilarity between two clusters is given by the average the dissimilarities between all the possible pairs of cases The dissimilarity is based upon a synthesis of all the dissimilarities Usually clusters with similar variances are obtained Cluster analysis: hierarchical algorithms – dissimilarity/clusters Slide 16: 16 Dissimilarity between centroids: The dissimilarity between two clusters is given by the dissimilarities between the centroids (Important: this quantity may also be evaluated when only the dissimilarity matrix is available) Cluster analysis: hierarchical algorithms – dissimilarity/clusters The dissimilarity is based upon a synthesis of all the dissimilarities Slide 17: 17 SSWr SSWs Ward’s method: Let us focus only on two of the three clusters considered before, and let us consider the case when a data matrix is available (even if the procedure can be extended to the case when we only have a dissimilarity matrix). This method is based upon the concept of within sum of squares. Cluster analysis: hierarchical algorithms – dissimilarity/clusters Within sum of squares for a cluster c Suppose now that the two clusters r and s are joined to form cluster t. It will be SSWt > SSWr + SSWs (the two original centroids will explain better cases within clusters). The increase consequent to the joining of r and s will be quite small if the two clusters are very close, and high if they are very different. The quantity SSWt (SSWr + SSWs ) is called between sum of squares (SS). Ward’s method: the two clusters with the smallest Between SS are joined. SSWt Slide 18: 18 Cluster analysis: hierarchical algorithms Given a dissimilarity matrix, based on a certain measure of the dissimilarity between cases, there are different methods to measure the dissimilarity between clusters. These criteria often lead to different partitions. Single Linkage Cluster Analysis Complete Linkage Cluster Analysis Slide 19: 19 Cluster analysis: hierarchical algorithms Given a dissimilarity matrix, based on a certain measure of the dissimilarity between cases, there are different methods to measure the dissimilarity between clusters. These criteria often lead to different partitions. Single Linkage Cluster Analysis Complete Linkage Cluster Analysis Slide 20: 20 Cluster analysis: hierarchical algorithms To apply a hierarchical agglomerative algorithm we have to: Obtain the dissimilarity matrix containing the dissimilarities between all the possible pairs of observations (as we will see later, different criteria may be referred to) Choose a method to measure the dissimilarity between clusters These choices have an impact on the sequence of nested partitions obtained as an output. So we usually have different sequences of nested partitions. But, also, for a given sequence of nested partitions the following problem arises: How should we select a suitable number of clusters? Slide 21: 21 Cluster analysis: hierarchical methods/choosing the nr of clusters We consider first the problem of choosing one out of the clustes solutions obtained with one hierarchical clustering process. At this aim, the agglomeration process is monitored as the number of clusters declines from n to 1, and some quality of clustering criteria are evaluated. Internal criteria. The simplest approach to cluster choice consists in the evaluation of the dissimilarity between the two clusters joined at each step. In the first steps of the procedure, similar cases/groups will be joined to form new clusters. At subsequent steps, we can expect an increasing of this dissimilarity, and this increase will tend to grow exponentially in the last aggregation phases, i.e. when very dissimilar clusters are joined. External criteria. Another possibility consists in the evaluation of some statistics – not related to the criterion used to measure the dissimilarity between clusters – which are solely based upon the R2, the within and the between sum of squares characterizing partition of different degree (different number of clusters) Slide 22: 22 Cluster analysis: hierarchical methods/choosing the nr of clusters Internal criteria: Tree diagram (dendrogram) and its height The agglomerative process can be graphically represented using a tree diagram, also called dendrogram, with cases on the horizontal axis and the dissimilarity between the clusters joined at each step on the vertical axis (the dissimilarity is normalized). Tree diagram (Single linkage) If a large change in the height occurs consequently to an aggregation at step C then the (C + 1) solution immediately prior to this step should be chosen. A ‘cut’ in the dendrogram, corresponding to a given aggregation defines the groups to be considered (obs connected to the branches). Slide 23: 23 Cluster analysis: hierarchical methods/choosing the nr of clusters Internal criteria: Tree diagram (dendrogram) and its height Tree diagram (Complete linkage) Where would you ‘cut’ the dendrogram? I.e., which aggregation would you avoid? Remember that the height of the dendrogram is normalized. Observe that the dissimilarity between observations is different from one tree to another. (consider for example the distance between obs 5 and 15) Slide 24: 24 Cluster analysis: hierarchical methods/choosing the nr of clusters External criteria: R2, Pseudo F, Pseudo t2 . Criteria based upon the within and between sum of squares. Consider for simplicity the situation when cluster analysis is based upon a vector of measurements (the concepts can be extended to the case when only a dissimilarity matrix is available) Total sum of squares (SS) Within SS Between SS Consider a partition of the dataset into C clusters The Within SS sum of squares is a synthesis of the squared errors incurred when using the clusters to “make predictions”/explain the variables at the basis of the clustering procedure. Instead, the Total SS is the synthesis of the squared errors when the general means are used (no external information – clusters) Slide 25: 25 R square: quality of a partition. It is related to the proportion of total variation among cases explained by clusters Semi-partial R square: decrease of the R2 when moving from C clusters to (C – 1) clusters. Cluster analysis: hierarchical methods/choosing the nr of clusters External criteria: R2, Pseudo F, Pseudo t2 . R2 = 1 when C = n (each case constitute a cluster – no within SS) R2 = 0 when C = 1 (all cases placed in a single cluster –Within SS=Total SS) As the number of clusters decreases the R2 also decreases. A sudden decrease of the R2 would indicate the joining of clusters which are really dissimilar Slide 26: 26 Cluster analysis: hierarchical methods/choosing the nr of clusters External criteria: R2, Pseudo F, Pseudo t2 . Pseudo F statistic In the initial steps of agglomeration, as n decreases, B decreases and W increases, so FC gradually decreases. A sudden relatively high decrease of FC consequent to an aggregation indicates the joining of two quite distinct clusters. The (C + 1) cluster solution immediately prior to this decrease should be selected. Pseudo t statistic Numerator = increase in the Within SS resulting from joining r and s to form a new cluster. Denominator=sum of the within SS of the two joined clusters. A sudden increase of the statistics indicates the joining of two distinct clusters (high relative increase of the within consequent to aggregation). Slide 27: 27 Cluster analysis: hierarchical methods/choosing the nr of clusters Pseudo F Height (min. distance between clusters) R square Pseudo T Monitoring internal and external criteria: Single linkage All criteria: No clear indications (2 clusters) Slide 28: 28 Cluster analysis: hierarchical methods/choosing the nr of clusters Monitoring internal and external criteria: Complete linkage Height (max. distance between clusters) R square Pseudo F Pseudo T Slide 29: 29 Cluster analysis – partitioning algorithms In partitioning algorithms, the number of clusters has to be specified. The algorithm usually starts with an initial allocation of the objects into G groups. Then observations are placed in the cluster they are closest to. Alternatively, observations are assigned to one cluster so as to maximize an objective function. The procedure iterates until all objects belong to the closest group (the objective function is maximized) or until a convergence criterion is satisfied . Usually (SAS) partitioning methods are based upon measurements on a set of variables rather than on a dissimilarity, and on Euclidean distances. One of the most important partitioning algorithms is the k-means algorithm. In this algorithm, the distance from one observation to a cluster is measured as the distance between the observation and the centroid of the cluster. It can be easily shown that in this case the algorithms attempts to find the partition characterized by the minimum Within SS, i.e., by the maximum R2. In this sense, Ward’s and the k-means algorithms are two R2-maximizing algorithms. The former is based upon a hierarchical solution to the optimization problem. The latter is instead based on an iterative search of the optimum. Slide 30: 30 Step 1: Select the initial partition (this partition may also be defined on the basis of a preliminary cluster analysis / hierarchical procedure) Usually, G seeds are selected Step 2: Allocation Each case is allocated to the closest cluster (closest centroid) Step 3: Seeds update Seeds are updated: centroid of the obtained clusters Step 2 and 3 are iterated until convergence: 2. Re-allocation 3. Seeds update Es. G=2 Cluster analysis – partitioning algorithms Slide 31: 31 k-means algorithm Allocate cases to the closest seed Obtain clusters’ centroids Allocate cases to the closest centroid G seeds are randomly selected. SAS – subroutines defined to select seeds not too close one to each other – higher group separation Select an initial partition Obtain clusters’ centroids Cluster analysis – partitioning algorithms Reallocation step (maxiter) If maxiter=0, cases are assigned to the closest cluster -> no reallocation. Useful to assign cases to previously determined clusters Convergence criteria satisfied? YES stop NO Slide 32: 32 Agglomerative algorithms: OK Many solutions – monitoring of the process OK Flexibility in choosing the measure of dissimilarity (both for obs – see later – and for clusters). The case when only the dissimilarity matrix is available can be handled. KO Problems with large datasets (difficulty in handling very large dissimilarity matrices) KO Hierarchy is not flexible: once obs are joined they are no longer split. Possible distortions in the case when there are outliers Partitioning algorithms OK Large dataset OK Flexible with respect to the aggregation of cases. Groups may change. KO Choice of the number of clusters: difficult KO Partitions with a different number of clusters are not nested and consequently it may be difficult to analyze the relationship between them. Cluster analysis In some applications combinations of the algorithms are considered Large databases: a sample of cases is selected. A hierarchical algorithm is applied to select the number of clusters. Then a partitioning algorithm is applied (optionally, the initial seeds are the centroids of the clusters obtained with the hierarchical algorithm) Flexibility: A hierarchical algorithm is applied. A partition is selected. The centroids of the obtained clusters are used as seeds in a partitioning algorithm. The aim is to evaluate if and to which extent the initial solution changes and, also, to evaluate the possible influence of outliers on results. Slide 33: 33 Cluster analysis Whatever the algorithm used to obtain clusters: 1. Number of clusters Choice – agglomerative methods Guess – partitioning methods 2. Evaluation of the quality of the obtained partition 3. Interpretation of clusters Internal evaluation: Analysis of cases grouped together. Sensible only if obs are identifiable (meaningful labels). Analysis of cluster syntheses (means in the case when cluster analysis is based upon numerical variables, other measures – medians, modes – in other cases). This is possible only when measurements on variables are available Visualization of clusters in factorial maps External evaluation Evaluation of the characteristics of the clusters (same as before) by referring to variables which were not used to obtain clusters Slide 34: 34 CLUSTER ANALYSIS Cautions Cluster analysis (as we described it) is a descriptive technique. The solution is not unique and it strongly depends upon the analyst’s choices. We will describe how it is possible to combine different results in order to obtain stable clusters, not depending too much on the criteria selected to analyze data. Cluster analysis always provide groups, even if there is no group structure. When applying a cluster analysis we are hypothesizing that groups exist. But this assumption may be false or weak. Cluster analysis results’ should not be generalized. Cases in the same cluster are (hopefully) similar only with respect to the information cluster analysis was based on (i.e., dimensions/variables inducing the considered dissimilarities). You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.