Cluster Analysis

Overview

Cluster analysis, also called segmentation analysis or taxonomy analysis, seeks to identify homogeneous subgroups of cases in a population. That is, cluster analysis is used when the researcher does not know the number of groups in advance but wishes to establish groups and then analyze group membership. (Contrast, for instance, discriminant function analysis, which analyzes group membership for known groups pre-specified by the researcher). Cluster analysis implements this by seeking to identify a set of groups which both minimize within-group variation and maximize between-group variation. Later, group id values may be saved as a case variable and used in other procedures such as crosstabulation.
Other techniques, such as and Q-mode factor analysis, multidimensional scaling, and latent class analysis also perform clustering and are discussed separately.
SPSS offers three general approaches to cluster analysis:

Hierarchical clustering allows users to select a definition of distance, then select a linking method for forming clusters, then determine how many clusters best suit the data. Hierarchical clustering generates representation of clusters in icicle plots and dendograms.

K-means clustering has the researcher specify the number of clusters in advance, then the algorithm calculates how to assign cases to the K clusters. K-means clustering is much less computer-intensive and is therefore sometimes preferred when datasets are large (ex., > 1,000). K-means clustering generates an ANOVA table showing mean-square error.

Two-step clustering creates pre-clusters, then it clusters the pre-clusters using hierarchical methods. Two step clustering handles very large datasets, is the method chosen when data are categorical (it supports continuous variables also), and has the largest array of output options, including variable importance plots.

Contents

Key concepts and terms
Hierarchical cluster analysis
K-means cluster analysis
Two-step cluster analysis
Cluster analysis in SAS
Other types of cluster analysis
Assumptions
Frequently asked questions
Bibliography

Key Concepts and Terms

Cluster formation is the selection of the procedure for determining how clusters are created, and how the calculations are done. In agglomerative hierarchical clustering every case is initially considered a cluster, then the two cases with the lowest distance (or highest similarity) are combined into a cluster. The case with the lowest distance to either of the first two is considered next. If that third case is closer to a fourth case than it is to either of the first two, the third and fourth cases become the second two-case cluster; if not, the third case is added to the first cluster. The process is repeated, adding cases to existing clusters, creating new clusters, or combining clusters to get to the desired final number of clusters. There is also divisive clustering, which works in the opposite direction, starting with all cases in one large cluster. Hierarchical cluster analysis, discussed below, can use either agglomerative or divisive clustering strategies.
Cluster validity. By whatever method discussed below the researcher forms clusters, the utility of clusters must be assessed by three criteria:
1. Size. All clusters should have enough cases to be meaningful. One or more very small clusters indicates the researcher has requested too many clusters. Analysis resulting in a very large, dominant cluster may indicate too few clusters have been requested.
2. Meaningfulness. As in factor analysis, ideally the meaning of each cluster should be readily intuited from the constituent variables used to create the clusters. Variable importance plots, discussed below, are one method of making this assessment.
3. Criterion validity. The crosstabulation of the cluster id numbers by other variables known from theory or prior research to correlate with the concept which clustering is supposed to reflect, should in fact reveal the expected level of association.
Failure to meet these criteria may indicate the researcher has requested too many or too few clusters, or possibly that an inappropriate distance measure (discussed below) has been selected. It is also possible that the hypothesized conceptual basis for clustering does not exist, resulting in arbitrary clusters.
Distance (proximities). The first step in cluster analysis is establishment of the similarity or distance matrix. This matrix is a table in which both the rows and columns are the units of analysis and the cell entries are a measure of similarity or distance for any pair of cases.
Types of cluster analysis.
1. Disjoint. Each object is classified in only one cluster. Clusters are not clustered. K-means clustering and two-step cluster analysis, both discussed below, is of this type.
2. Hierarchical. Each object is classified in only one bottom-level cluster but clusters may be clustered. A given object may be in multiple clusters, one per level of clustering. As its name clearly implies, hierarchical cluster analysis creates this type of clustering.
3. Overlapping. Objects may be in more than one cluster, even at the same level.
4. Fuzzy. Objects may be assigned membership in disjoint, hierarchical, or overlapping clusters on a probabilistic basis. Objects have a probability of membership in each cluster. Factor analysis, discussed separately, yields fuzzy clusters. PROC VARCLUS in SAS is a method of converting the fuzzy clusters emerging from factor analysis into non-fuzzy disjoint clusters.

Hierarchical Cluster Analysis

Hierarchical clustering is appropriate for smaller samples (typically < 250). When n is large, the algorithm will be very slow to reach a solution and, indeed, may "hang" one's computer. To accomplish hierarchical clustering, the researcher must specify how similarity or distance is defined and how clusters are aggregated (or divided). Hierarchical clustering generates all possible clusters of sizes 1...K, but is used only for relatively small samples. In hierarchical clustering, the clusters are nested rather than being mutually exclusive, as is the usual case. That is, in hierarchical clustering, larger clusters created at later stages may contain smaller clusters created at earlier stages of agglomeration.
One may wish to use the hierarchical cluster procedure on a sample of cases (ex., 200) to inspect results for different numbers of clusters. The optimum number of clusters depends on the research purpose. Identifying "typical" types may call for few clusters and identifying "exceptional" types may call for many clusters. After using hierarchical clustering to determine the desired number of clusters, the researcher may wish then to analyze the entire dataset with k-means clustering (aka, the Quick Cluster procedure: Analyze, Cluster, K-Means Cluster Analysis), specifying that number of clusters.
- Forward clustering, also called agglomerative clustering: Small clusters are formed by using a high similarity index cut-off (ex., .9). Then this cut-off is relaxed to establish broader and broader clusters in stages until all cases are in a single cluster at some low similarity index cut-off. The merging of clusters is visualized using a tree format.
- Backward clustering, also called divisive clustering, is the same idea, but starting with a low cut-off and working toward a high cut-off. Forward and backward methods need not generate the same results.
- Clustering variables. In the Hierarchical Cluster dialog, in the Cluster group, the researcher may selected Variable rather than the usual Cases, in order to cluster variables.
SPSS Input for hierarchical clustering
- SPSS calls hierarchical clustering the "Cluster procedure." In SPSS, select Analyze, Classify, Hierarchical Cluster. The following main dialog appears:
  Move the variables desired to the variable list box. This example uses the SPSS example file judges.sav, where columns (variables) are judges from eight countries and rows are 300 fictional cases of gymnasts being rated on a 0-10 scale. To cluster judges, check Variables in the cluster group. Check if Statistics and/or Plots are desired.
- Statistics button. Under the Statistics button, one may request the agglomeration schedule and the proximity matrix, described below in the section on output. One may also specify the minimum and maximum number of clusters (3 to 6 is common), or one may ask for a specific number, or none.
- Plots button. Under the Plots button, one may request dendograms and icicle plots, also described below in the section on output. Also, the orientation (vertical or horizontal) of icicle plots may be specified.
- Methods button. In SPSS, similarity/distance measures are selected in the Measure area of the Method subdialog obtained by pressing the Method button in the Classify dialog. There are three measure pulldown menus, for interval, binary, and count data respectively. The proximity matrix table in the output shows the actual distances or similarities computed for any pair of cases. In SPSS, proximity matrices are selected under Analyze, Cluster, Hierarchical clustering; Statistics button; check proximity matrix.
  Under the Methods button, one may request the cluster (linkage) method and the distance measure to be used. The distance measure choices will depend on the level of measurement specified: interval, count, or binary. It is also possible to standardize and transform variables at this point, though in the current example that is not needed as all variables are of the same 0 - 10 scale. When scale differs among variables, standardization is recommended.
  - Methods button: Distance measures. There are a variety of different measures of inter-observation distances and inter-cluster similarities and distances to use as criteria when merging nearest clusters into broader groups or when considering the relation of a point to a cluster. Distance measures how far apart two observations are. Cases which are alike share a low distance. Similarity measures how alike two cases are. However, it is common to refer to all measures as "distance" measures since the same function is served. Note that when two or more variables are used to define distance, the one with the larger magnitude and/or variance will dominate. To avoid this it is common to first standardize all variables. As discussed in the FAQ section, standardization depends on research purpose. SPSS hierarchical clustering supports these types of measures:
  - Methods button: Cluster (linkage) method. Under the Method button in the SPSS Classify dialog, the pull-down Method selection determines how cases or clusters are combined at each step. Different methods will result in different cluster patterns. SPSS offers these method choices:
    - Between-groups linkage, also called UPGMA linkage (unweighted pair-group method using averages), is the default. The distance between two clusters is the average distance between all inter-cluster pairs. This method is generally preferred over nearest or furthest neighbor methods since it is based on information about all inter-cluster pairs, not just the nearest or furthest ones. This method works well for both elongated chain-type and with clumpy type clusters.
    - Within-groups linkage, also referred to as "average linkage within groups," is the mean distance between all possible inter- or intra-cluster pairs. The average distance between all pairs in the resulting cluster is made to be as small as possibile. This method is therefore appropriate when the research purpose is homogeneity within clusters. SPSS labels this "within-groups linkage."
    - Nearest neighbor. In this "single linkage" method, the distance between two clusters is the distance between their closest neighboring points. This method works well when the plotted clusters are elongated or chain-like.
    - Furthest neighbor. In this "complete linkage" method, the distance between two clusters is the maximum distance between a point in the first cluster and a point in the second cluster. This method works well when the plotted clusters form distinct clumps (not elongated chains).
    - Centroid method. The cluster to be merged is the one with the smallest sum of distances between cluster means (centroids) for all variables. The centroid method also weights for differences in cluster size. When this method is selected, squared Euclidean distance is preferred over simple Euclidean distance as a distance measure. This method is also called the "weighted pair-group method using centroid averages" (WPGMC).
    - Median clustering. This is an unweighted version of the centroid method. It should not be used when cluster sizes vary markedly. When this method is selected, squared Euclidean distance is preferred over simple Euclidean distance as a distance measure. This method is also called the "unweighted pair-group method using centroid averages" (UPGMC).
    - Ward's method is a minimum distance hierarchical method which calculates the sum of squared Euclidean distances from each case in a cluster to the mean of all variables. The cluster to be merged is the one which will increase the sum the least. That is, this method minimizes the sum of squares of any pair of clusters to be formed at a given step. As such it is an ANOVA-type approach which maximizes between-group differences and minimizes within-group distances, optimizing the F statistic, and is preferred by some researchers for this reason. This method tends to create clusters of small size.
    - SAS. See further discussion of linkage methods in the section on SAS implementation.
SPSS output for hierarchical cluster analysis
- Proximity table. This table shows the distance from each case to each other case. The table will be very large when n is very large. For this example, variables were clustered and judges, eight in number, were the variables.
- Summary measures assess how the clusters differ from one another.
  - Means and variances. A table of means and variances of the clusters with respect to the original variables shows how the clusters differ on the original variables. SPSS does not make this available in the Cluster dialog, but one can click the Save button, which will save the cluster number for each case (or numbers if multiple solutions are requested). Then in Analyze, Compare Means, Means the researcher can use the cluster number as the grouping variable to compare differences of means on any other continuous variable in the dataset.
  - Linkage tables show the relation of the cases to the clusters.
    - Cluster membership table. This shows variables as rows (this example clusters variables, not cases), where columns are alternative numbers of clusters in the solution (as specified in the "Range of Solution" option in the Cluster membership group in SPSS, under the Statistics button). Cell entries show the number of the cluster to which the case belongs. From this table, one can see which variables (judges in this example) are in which cluster, depending on the number of clusters in the solution.
    - Agglomeration Schedule. Agglomeration schedule is a choice under the Statistics button for Hierarchical Cluster in the SPSS Cluster dialog. In this table, the rows are stages of clustering, numbered from 1 to (n - 1). The (n - 1)^th stage includes all the cases in one cluster. There are two "Cluster Combined" columns, giving the case or cluster numbers for combination at each stage. In agglomerative clustering using a distance measure like Euclidean distance, stage 1 combines the two cases which have lowest proximity (distance) score. The cluster number goes by the lower of the cases or clusters combined, where cases are initially numbered 1 to n.
      The proximity/distance/agglomeration coefficient in the "Coefficients" column is an indicator of how far the agglomeration algorithm has to reach to combine an existing cluster with the next closest cluster or variable (judge). For this example one can see that there is a large jump between stages 5 and 6, corresponding to combining cluster 1 (judges 2,5,7, and 1) with cluster 2 (judges 2, 4, and 6) from stage 5. A large agglomeration coefficient will correspond with a long distance in the dendogram discussed below. When there are relatively few cases, icicle plots or dendograms provide the same linkage information in an easier format.
      In the figure above on 8 judges rating 300 objects, the agglomeration schedule shows, for instance, that judges 3 and 5 are combined in a cluster first (the cluster is labeled 3). judges 2 and 4 become cluster 2. Then judge 6 is added to cluster 2. Then at stage 4, the new cluster 3 formed at stage 1 is combined with judge 7 to form a larger cluster, also now labeled 3. Then cluster 3 is joined to judge 1 and is labeled cluster 1. Then cluster 2 is joined to cluster 1 and is labeled cluster 1. Finally, judge 8 (the "enthusiast" judge, who is most different from others) is joined to cluster 1, which then is the only remaining cluster.
  - Linkage plots show similar information in graphic form.
    - Dendrograms, also called hierarchical tree diagrams or plots, show the relative size of the proximity coefficients at which cases were combined. The bigger the distance coefficient or the smaller the similarity coefficient, the more clustering involved combining unlike entities, which may be undesirable. Trees are usually depicted horizontally, not vertically, with each row representing a case on the Y axis, while the X axis is a rescaled version of the proximity coefficients. Variables or cases with low distance/high similarity are close together. Those showing low distance are close, with a line linking them a short distance from the left of the dendogram, indicating that they are agglomerated into a cluster at a low distance coefficient, indicating alikeness. When, on the other hand, the linking line is to the right of the dendogram the linkage occurs a high distance coefficient, indicating the cases/clusters were agglomerated even though much less alike. If a similarity measure is used rather than a distance measure, the rescaling of the X axis still produces a diagram with linkages involving high alikeness to the left and low alikeness to the right. In SPSS, select Analyze, Classify, Hierarchical Cluster; click the Plots button, check the Dendogram checkbox.
      In the figure above, from hierarchical cluster analysis on 8 judges who rated 300 objects, the dendogram shows judges 3 & 5 (these were Romania and China respectively) to be in one of the two earliest clusters, with judge 7 (Russia) affiliated with cluster 3 & 5 only at a greater distance. In general, the dendogram shows the pattern of clustering among the judges, with connecting lines further to the right indicating more distance between judges and clusters. The final linkage to judge 8 ("Enthusiast") shows ths judge to be least like the others, but the real jump occurs a step earlier, as noted in the section above regarding the agglomeration schedule.
      One can also cluster cases. The dendogram below is for the clustering of 50 objects by the 8 judgest, with objects 10, 38, 17, 16, 18, 43, 2, 46, and 27 forming one of the first clusters:
- Icicle plots are usually horizontal, showing cases as rows and number of clusters in the solution as columns. If there are few cases, vertical icicle plots may plotted, with cases as columns, as below.. Reading from the last column right to left (horizontal icicle plots) or last row bottom to top (vertical icicle plots), the researcher can see how agglomeration proceeded. For a vertical icicle plot, the bottom row will show all the cases in separate one-case clusters except the first pair clustered. Subsequent number-of-clusters rows show further clustering steps. This is a visual way of representing information on the agglomeration schedule, but without the proximity coefficient information.
  In the figure above, from hierarchical cluster analysis on 8 judges who rated 300 objects, the vertical icicle plot shows what happens when there are the following number of clusters:

K-means Cluster Analysis

K-means cluster analysis. Large datasets are possible with K-means clustering, unlike hierarchical clustering, because K-means clustering does not require prior computation of a proximity matrix of the distance/similarity of every case with every other case. Because cases may be shifted from one cluster to another during the iterative process of converging on a solution, k-means clustering is a type of "relocation clustering method." However, there is also a variant called "agglomerative K-means clustering," where the solution is constrained to force a given case to remain in its initial cluster.
K-means cluster analysis uses Euclidean distance. The researcher must specify in advance the desired number of clusters, K. Initial cluster centers are chosen randomly in a first pass of the data (note different initial values may affect the solution: see Assumptions section on randomization), then each additional iteration groups observations based on nearest Euclidean distance to the mean of the cluster. That is, the algorithm seeks to minimize within-cluster variance and maximize variability between clusters in an ANOVA-like fashion. Cluster centers change at each pass. The process continues until cluster means do not shift more than a given cut-off value or the iteration limit is reached.
- SPSS Input for K-means cluster analysis
  - Example. This example uses the same dataset in which 8 judges rated 300 athletes in an athletic event. K-means clustering will cluster the athletes (cases) using the 8 judges as clustering variables. (There is no option, as in hierarchical cluster analysis, to select between clustering cases or clustering variables. To cluster the variables (the judges), the researcher would have to transpose the dataset.
  - Main K-means dialog. The main K-means dialog accepts four types of input: (1) the variable list, same as for hierarchical clustering; (2) the number of clusters, specified in advance by the researcher; (3) the method (iterate, or iterate and classify); and (4 choices about cluster centers.
    - SPSS. In SPSS, Analyze, Cluster, K-Means Cluster Analysis; enter variables in the Variables: area; optionally, enter a variable in the "Label cases by:" area; enter "Number of clusters:"; choose Method: Iiterate and classify, or just Classify). Unlike hierarchical clustering, there is no option for "Range of solutions"; instead the researcher desiring to do so must re-run K-means clustering, asking for a different number of clusters.
    - Number of clusters. This may be put forward by the researcher based on theory, on exploration with sampled data using hierarchical clustering, or on repeated exploratory use of K-means clustering itself. Here 2 are requested, seeking to cluster the 300 athletes into two categories.
    - Method. The default (and usual) method is "Iterate and classify," under which an interative process is used to update cluster centers, then cases are classified based on the updated centers. However, SPSS supports a "Classify only" method, under which cases are immediately classified based on the initial cluster centers, which are not updated.
    - Cluster centers are the average value on all clustering variables of each cluster's members. The "Initial cluster centers," in spite of its title, gives the average value of each variable for each cluster for the k well-spaced cases which SPSS selects for initialization purposes when no initial file is supplied. The "Final cluster centers" table in SPSS output gives the same thing for the last iteration step. The "Iteration history" table shows the change in cluster centers when the usual iterative approach is taken. When the change drops below a specified cutoff, the iterative process stops and cases are assigned to clusters according to which cluster center they are nearest.
      - Drawing initial cluster centers from a file. In the K-means Cluster main dialog, in the Cluster centers area, one may check "Write final as" and enter a file name. This will save the final cluster centers of each variable to a data file which can later be used as the initial centers for a different sample of cases. In the same area, there is a "Read initial from" checkbox and place to enter a file name for this purpose. If the initial file is created manually, note the file referenced must have as its first column a variable named "cluster_". The additional columns are the same variables you specified in the dialog box, though they need not be in the same order. You may have additional variables in this file beyond those specified in the dialog box -- these will be ignored. If you do not draw initial cases from a file, SPSS will find k well-separated cases (that is, a case for each variable for each of the k clusters requested) and use these as initial values. Either way, the output includes a table of "Initial cluster centers."
  - Iterate button. Optionally, you may press the Iterate button and set the number of iterations and the convergence criterion. The default maximum number of iterations in SPSS is 10. For the convergence criterion, by default, iterations terminate if the largest change in any cluster center is less than 2% of the minimum distance between initial centers (or if the maximum number of iterations has been reached). To override this default, enter a positive number less than or equal to 1 in the convergence box. There is also a "Use running means" checkbox which, if checked, will cause the cluster centers to be updated after each case is classified, not the default, which is instead to update after the entire set of cases is classified.
  - Save button: Optionally, the researcher may press the Save button to save the final cluster number of each case as an added column in the dataset (labeled QCL_1). This variable may then be used in analysis with other procedures (ex., crosstabulation). Note that the cluster id variable will be nominal in level except for two-cluster solutions, when it will be binary. The researcher may also save the Euclidean distance between each case and its cluster center (labeled QCL_2) by checking "Distance from cluster center."
    Cluster relationship with other variables. The relationship of any variable in the dataset with the clusters formed by the clustering variables can be viewed (among other ways) by selecting Analyze, Descriptive Statistics, Crosstabs, with QCL_1 as rows and that variable as columns. Needless to say, that variable need not have been one of the clustering variables.
  - Options button: Optionally, you may press the Options button to select statistics or missing values options. Only the first option (initial cluster centers)is a default.
    There are three statistics options:
    1. "Initial cluster centers" gives the initial variable means for each clusters.
    2. "ANOVA table" is the central statistical output of K-means clustering, discussed below.
    3. "Cluster information for each case" gives each case's final cluster assignment and the Euclidean distance between the case and the cluster center; also gives the Euclidean distance between final cluster centers.
    In addition, there are two missing values options: listwise (the default) and pairwise deletion of cases with missing values.
- SPSS Output for K-Means cluster analysis
  - The ANOVA table. ANOVA F-tests for each variable indicate how well the variable helps to discriminate between clusters. Non-significant variables might be dropped as not contributing to the differentiation of clusters. Note, however, that these F tests are post-hoc, based on assigning cases to groups to minimize within-group and maximize between group distances, and therefore the F tests should be considered useful for exploratory purposes only and not used as conventional significance tests, the assumptions of which are inherently violated by the clustering process.
    In the figure above, the 8 judges (7 nations plus "Enthusiast" are the "variables") rating 300 athletes, the ANOVA table shows the largest error associated with the "Enthusiast" judge, meaning that judge (variable) is least helpful in forming and differentiating the clusters. All judges/variables are significant, but this is largely meaningless. The ANOVA table is used mainly to look at the size of the mean square errors.
  - Number of cases in each cluster. This table, illustrated below, is useful in viewing the split of cases among clusters. Some 146 athletes are of type 1 and 154 of type 2, where types are clusters established by using the ratings of judges as a criterion. Cluster 1 is lower-scoring athletes and cluster 2 is higher-scoring, as we can see by creating the new variable Score (the sum of all judges' scores for a particular athlete), and by saving the cluster membership number (using the Save button of the k-means clustering dialog, which adds the cluster membership variable QCL_1 to the dataset)
    Getting different clusters. Sometimes the researcher wishes to experiment to get different clusters, as when the "Number of cases in each cluster" table shows highly imbalanced clusters and/or clusters with very few members. Different results may occur by setting different initial cluster centers from file (see above), by changing the number of clusters requested, or even by presenting the data file in different case order.
  - Cluster membership table.. This table, selected by checking "Cluster information for each case" in the Options dialog's Statistics section, and illustrated below, shows through the "distance" variable how close or far a given athlete is from the centroid of their cluster group. Athletes (cases) with very large distances are outliers which are not as representative of the cluster as cases with small distances. SPSS does not filter or flag such large outliers, however, so visual inspection is necessary.

Two-Step Cluster Analysis

Two-step cluster analysis is often preferred for large datasets, since hierarchical and k-means clustering do not scale efficiently when n is very large. As it handles categorical as well as continuous data, the two-step procedure is also the one chosen when categorical variables with three or more levels are involved. While there is no option to cluster variables rather than cases, one can output variablewise plots by cluster as well as clusterwise plots by variable, as illustrated further below.
Approach: The two-step method is a one-pass-through-the-data approach which addresses the scaling problem by identifying pre-clusters in a first step, then treating these as single cases in a second step which uses hierarchical clustering. The researcher can let the two-step algorithm determine the number of clusters automatically, or the researcher may set the number of clusters.
Background: The SPSS two-step procedure extends work of Banfield & Raftery (1993), whose work developed a clustering method for continuous variables based on the reduction in log-likelihood when two clusters are merged; and extended work of Melia & Heckerman (1998) using a similar probabilistic approach for categorical variables. While traditional k-means and hierarchical clustering procedures were effective for small and medium datasets, they did not cluster accurately for very large datasets. SPSS incorporated the two-step concept developed for BIRCH clustering (Zhang et al., 1996) under which a very large dataset would be reduced to sub-clusters which in a second step could each be analyzed accurately by largely traditional clustering methods.
Cluster feature tree (CF tree). The preclustering stage employs a CF-tree with nodes leading to leaf nodes, following a sequential clustering method described by Theodoridis and Koutroumbas (1999). Cases start at the root node and are channeled toward nodes and eventually leaf nodes which match it most closely. If there is no adequate match (the distance measure for the case is above the threshold level), the case is used to start its own leaf node. It can happen that the CF-tree fills up and cannot accept new leaf entries in a node, in which case it is split using the most-distant pair in the node as seeds. If this recursive process grows the CF-tree beyond maximum size, the threshold distance is increased and the tree is rebuilt, allowing new cases to be input. The process continues until all the data are read. The default for the preclustering stage in SPSS employs CF-tree with three levels of nodes maximum and with eight entries per node maximum. Click the Advanced button in the Options button dialog in SPSS to set threshold distances, maximum levels, and maximum branches per leaf node manually.
Warning! The CF tree and hence the clustering solution will be affected by the order of the data. See the Assumptions section on randomization, which is strongly recommended.
Proximity. When one or more of the variables are categorical, log-likelihood is the distance measure used, with cases categorized under the cluster which is associated with the largest log-likelihood, using a method developed by Meila and Heckerman (1998). If variables are all continuous, Euclidean distance is used, with cases categorized under the cluster which is associated with the smallest Euclidean distance. The SPSS two-step clustering model also handles mixed categorical and continous data. Note that earlier two-step clustering methods, such as BIRCH, supported only continuous variables and did not use log-likelihood distances. The SPSS algorithm uses a decrease in log-likelihood for combining clusters as the distance measure since the log-likelihood method is compatible with categorical as well as continuous variables.
SPSS inputs for two-step clustering
- Main 2-step clustering dialog. As illustrated below, the main 2-step clustering dialog requests 5 types of input:
  1. The variable list. Essentially the same as hierarchical or k-means clustering, but variables may be categorical as well as continuous.
  2. Count of continuous variables. Continuous variables will be standardized by default.
  3. The distance measure. Log likelihood is the default, though traditional Euclidean distance may be used. There are no other options. Euclidean distance may only be used if all variables are continous. In such a case Euclidean distance avoids the assumptions of the log-linear method (independence of variables, multinormal distribution), though two-step clustering is fairly robust even when these assumptions are violated.
  4. Number of clusters. By default, SPSS uses an algorithm based in part on a Bayesian (BIC) or Akaike (AIC) information criteria loss to determine automatically the optimal number of clusters, though the researcher may override this and specify a fixed number of clusters. For instance, the researcher may take run a sample of clases through the hierarchical clustering procedure to determine the number of cases, then specify this number in two-step clustering. This is discussed further in the output section with regard to the autoclustering table.
  5. Clustering criterion. SPSS offers BIC and AIC, with the default being the former as BIC is now generally preferred by researchers. Whichever is chosen under this option determins the loss criterion employed by the algorithm for automatic determination of number of clusters. AIC and BIC are discussed further in the section on structural equation modeling.
- Options button dialog. In most cases, the researcher simply accepts the defaults in the illustration below. As illustrated, the options button allow five categories of input specification:
  1. Outlier treatment. No check is the default. If the CF tree fills, it is regrown using a larger distance change threshold. In the final solution, if a value cannot be assigned to a cluster it is considered an outlier, receives an identification number of -1, and is not included in the cluster count.
    Checking "noise handling" requests creation of a separate leaf just for outlier cases. Outliers are defined as cases in other leaves with fewer than the specified percentage (default is 25%) of the maximum leaf size. After creation of the "noise leaf", the CF tree is regrown, an attempt is made to transfer noise leaf cases to other leaves, and when the attempt is unsuccessful, noise outliers are discarded.
  2. Memory allocation. The default is 64 MB. Very large datasets may require more. Warning!: If memory is set too low, the two-step clustering algorithm may fail to find the correct or desired number of clusters.
  3. Standardization. In this section the researcher may override standardization settings for individual variables set in the main two-step cluster dialog. Note, however, that two-step clustering assumes all variables are standardized, either by the two-step clustering procedure or beforehand by the researcher.
  4. CF tree tuning criteria. Accessed by clicking "Advanced," the researcher may override the default criteria shown below in the illustration, such as maximum branches or maximum tree depth. Accepting the defaults is normal. The "initial distance change threshold" sets the "tightness" criterion such that when a new case is introduced to a cluster, it that yields a tightness exceeding the threshold, the cluster (leaf) is split. With regard to "maximum bumber of nodes possible," which is a function to maximum branches and maximum tree depth, note each node created requires memory and an excessive size may erode the performance of the two-step clustering procedure.
  5. Cluster model update. Accessed by clicking "Advanced," this option allows the researcher to import a CF tree previously saved in an XML file. The imported model is then updated for current data. The current variable list must be in the same order as in the previous save. The XML file is not changed, however, unless the researcher explicitly chooses to save again. Note: if an XML file is imported, its settings will override any specified in the current model (ex., distance measure, noise handling, memory allocation, or CF tree tuning criteria settings). The updating procedure assumes no current case was used in the previously saved model. If there is overlap, rather than update the two datasets should be combined, eliminating duplicates, and a two-step cluster analysis run.
- Plots button dialog. The default is no plots. Choosing one or more plots also causes a cluster membership variable to be created and added to the current dataset. As illustrated below, supported plots are the within cluster percentage chart, the cluster pie chart, the variable importance chart (by cluster or by variable), significance tests of importance, and the confidence level. Plots are further discussed in the output section below.
- Output button dialog. Here the research can specity output for cluster descriptives, cluster frequencies, and AIC or BIC coefficients - all discussed in the output section below.
  - Cluster membership variable. One can also ask to create a cluster membership variable. Note that if one has asked for a plot, an identical cluster membership variable will have been created. The variable will begin with the name "TSC_" followed by an SPSS-set code number. "TSC", of course, stands for two-stage cluster.
  - Export tree or model. One can also export in XML format the CFR tree or the entire model. Saving the CF tree allows the model to be updated later for additional datasets, as described above. Saving the entire model allows it to be used by SmartScore and SPSS Statistics Server (a separate product)to apply the model to other data files.
- SPSS outputs for two-step clustering
  - Autoclustering table. The "Autoclustering statistics" table in SPSS output can be used to assess the optimal number of clusters in two-step cluster analysis. As a rule of thumb, the solution with the lowest information criterion measure (the Schwarz Bayesian Information Criterion BIC or the Akaike Information Criterion AIC) and the highest ratio of distance measures is optimal (see below for further discussion of this ratio). When autoclustering is selected, SPSS will first pick a solution (number of clusters) based on lowest BIC, then will adjust the solution by taking into account solutions with a large "Ratio of Distance Measures." Simulation studies have shown these criteria in combination work better than BIC or AIC alone. On the other hand, the researcher may simply tell SPSS how many clusters are wanted, in which case the autoclustering table is not printed.
    In the example above, by the BIC criterion alone one would select 4 clusters as being optimal, since the lowest BIC coefficient is the best model. By the SPSS default algorithm, 4 clusters are also selected because this yields a large BIC ratio of change and a large ratio of distances. Note the SPSS algorithm need not agree with the BIC criterion used alone, though it does in this example. When it differs, in essence the SPSS algorithm judges that the gain in information from having more than the number of clusters specified by BIC alone is not worth the increased complexity (diminution of parsimony) of the model. The researcher has the option to override this default and specify 6 or some other number of clusters.
  - Cluster distribution table. This SPSS output table simply shows how many cases are in each cluster, enabling the researcher to judge if there are skewed splits among the clusters. Here that is not the case for the four computed clusters:
  - Centroids table. This table is the descriptive output for the continuous variables. It shows mean differences between the clusters on the continuous variables used for clustering (in this example, judges). For formatting reasons, the table below is abbreviated from its original form, which is one long horizontal row of variables. This example shows that of the 300 gymnastic events judged by the 7 country judges plus the "enthusiast" judge, the events in cluster 4 tended to be rated highest by judges in all countries.
  - Frequencies table. This table is the descriptive output for the categorical variables. There is one such table for each categorical variable. For a different example (since the judges dataset had no categorical variables), the table below shows that American cars tend to be in Cluster 1 and cars of other nations in Cluster 2.
  - Cluster pie chart. The cluster pie chart shows the relative size of the clusters, in this example for the four-cluster solution.
  - Within cluster variation plot. For continuous variables, error bar charts are shown for each cluster. These charts are labeled "Confidence Intervals for means" and show each continuous variable's mean with wing bars depicting the 95% confidence limits around each mean. In the example below, the 300 gymnastic events rated by the 8 judges clustered into 4 clusters of successively high average rankings. The plot below for Italy is similar to those for other country judges.
  - Within-cluster percentage plots. For categorical variables, a within-cluster percentage plot shows how each categorical variable is split within each cluster. These are generated by selecting "Within cluster percentage chart" under the Plots button. Clusters form the bars, the length of which reflects chi-square, with one plot per variable. For clusterwise importance plots there is a chi-square value on the X axis and cluster number on the Y axis: the longer the horizontal bar for any cluster, the higher the chi-square value, which is a measure of how much the within-cluster distribution of that variable differs from what would be expected based on the whole-sample distribution. In this plot, a dotted blue line represents the critical value line and if a bar is shorter than the critical value line, then the given variable is not important in differentiating that cluster from any of the others. If a variable is a significant differentiator for a given cluster, this means it differentiates that cluster from at least one of the other clusters.
    In the example above, automobiles from America, Europe, and Japan were clustered on various attributes (ex., engine size), deriving two clusters. US cars with large engine size dominate the first cluster.
  - Variablewise importance plot. For continuous variables, obtained in the Plots subdialog, the researcher selects "By variable" in the Rank Variables group. The importance plot shows chi-square on the X axis, and on the Y axis is the list of variables. Bars longer than the critical value line indicate variables important in differentiating that cluster. There is one such plot per cluster for the continuous variables and one for the categorical variables. In the figure for the example below, all the continuous variables (the judges in this example) differentiate Cluster 1, which represents the lowest-ranked events. Among the judges, the Russian judge contributes the most to differentiating this cluster.
    The examples below show variablewise importance plots for the cars example, which included both continuous (top figure) and categorical (bottom figure) variables. The top figure, below, shows that cluster 2, which is the smaller and predominantly European and Japanese cars, is differentiated by the top three variables in a negative direction and by the bottom three variables in a positive direction. The negative factors contribute more to differentiating cluster 2 than the positive ones.
    The second plot, below, shows that both categorical variables, country and number of cylinders, differentiate the cars in Cluster 2.
  - Clusterwise variable importance plot. If in the Plots dialog, Variable Importance Plot group, Rank Variables subgroup, the researcher selects "By cluster" rather than "By variable," a plot is produced like that illustrated below, one for each variable (each judge in this example). Note this selection changes the type of importance plots produced but does not change the auto-clustering table, the cluster distribution table, or other output.
    In the clusterwise importance plot above, which is for the variable (judge) representing the United States, the bars are arranged from top to bottom in descending order of importance (length). Thus the bars represent clusters 4, 1, 3, and 2 in that order. The US judge is most important in differentiating cluster 4, which reflects the highest-rated gymnastics events in the example. The US only barely makes any difference at all in differentiating cluster 2, by contrast.

Cluster Analysis in SAS

PROC CLUSTER is the SAS procedure for hierarchical cluster analysis. It has more method of aggregation options than SPSS (11 rather than 7) but does not contain an option to choose between clustering variables versus clustering cases. Therefore, to cluster judges similarly to the example above in SPSS for the judges data it is necessary to transform or flip the dataset so cases (athetes being judged) become variables and variables (judges) become cases. This results in this example in a dataset labeled "judges_flipped.sav."
SAS syntax for hierarchical cluster analysis of the example dataset is shown below:

PROC FASTCLUS is the SAS procedure for k-means clustering, discussed above using SPSS examples. Here the same dataset is used, in which 8 judges rate 300 athletes. PROC FASTCLUS classifies the 300 athletes into two clusters, using the rankings of the 8 judges as criteria. Note that PROC FASTCLUS is intended for datasets with sample size greater than 100. With smaller datasets it may be too sensitive to the order with which observations were entered into the dataset. Also note that the larger the variance of a variable, the greater the influence it will have in the results.

SAS syntax for PROC FASTCLUS.
```
PROC IMPORT OUT= WORK.fastclus1 
            DATAFILE= "\\tsclient\C\Docs\David\Courses\PA765\Datasets\SPSS Samples\judges.sav"
            DBMS=SPSS REPLACE;
RUN;
TITLE "PROC FASTCLUS Example" JUSTIFY=CENTER;
PROC FASTCLUS DATA=fastclus1  OUT=clusters MAXCLUSTERS=2 MAXITER=100 LIST;
VAR judge1-judge8;
RUN;
PROC PRINT DATA=clusters;
RUN;
```
Explanation of FASTCLUS syntax:
1. PROC IMPORT, PROC PRINT, and TITLE follow the explanation given above for PROC CLUSTER syntax.
2. PROC FASTCLUS. The DATA=fastclus1 makes the working dataset the one created by and named in PROC IMPORT. OUT=clusters sends output of PROC FASTCLUS to a new working dataset called "clusters". MAXCLUSTERS=2 sets the number of clusters to create to 2. MAXITER=100 sets the maximum number of iterations in the algorithm to 100. LIST generates a listing of all 300 athletes id numbers and cluster membership numbers, shown below.
3. VAR. This statement is needed to restrict the set of clustering variables when there are additional variables in the datasets.

PROC FASTCLUS output.

The cluster listing table. Output if the LIST parameter is in the PROC FASTCLUS command, this table (only partially reproduced below) shows the cluster assignment for each athlete (case). Since two clusters were requested by the MAXCLUSTERS= parameter, athletes are assigned to cluster 1 or cluster 2.

                                         Cluster Listing

                                                       Distance
                                                           from
                                     Obs    Cluster        Seed
                                  _____________________________
                                       1          1      1.8672
                                       2          2      0.9011
                                       3          1      2.1870
                                       4          1      1.8102
                                       5          2      1.9251
                                     ...         ...     ...
                                     296          2      1.3450
                                     297          2      1.2042
                                     298          1      0.5907
                                     299          1      1.7255
                                     300          2      1.1923

The cluster summary table. This table shows there are 147 athletes in cluster 1 and 153 in cluster 2. Also shown for each case is the root mean squared standard deviation and other statistics for each of the two clusters, plus the number of the nearest other cluster (trivial in the 2-cluster solution but helpful in other contexts). "Distance" refers to Euclidean distance. "Distance between cluster centroids" refers to distance from the row cluster centroid and the centroid of the nearest other cluster, where a centroid is the point within a cluster whose coordinates are the means of all observed cases in that cluster.

                                        Cluster Summary

                                      Maximum Distance
                           RMS Std           from Seed     Radius     Nearest     Distance Between
Cluster     Frequency    Deviation      to Observation    Exceeded    Cluster    Cluster Centroids
__________________________________________________________________________________________________
   1              147       0.5559              2.5209                      2               3.8989
   2              153       0.5435              2.4249                      1               3.8989

The statistics for variables table. For each variable used to determine clusters (each judge in this example), the total standard deviation of scores for that judge is listed, along with the pooled within-cluster standard deviation and the R-square value when that judge is predicted from the cluster. R-square reflects between-cluster variance and 1 minus R-square reflects unexplained/residual/error/within-cluster variance. The right-most column is the ratio of the two. Higher ratios reflect lower error variance for the row variable (judge).

                                    Statistics for Variables
                Variable     Total STD    Within STD      R-Square     RSQ/(1-RSQ)
                __________________________________________________________________
                judge1         0.87867       0.50550      0.670132        2.031520
                judge2         0.86534       0.51947      0.640834        1.784231
                judge3         0.84560       0.48751      0.668728        2.018671
                judge4         0.71206       0.44652      0.608088        1.551593
                judge5         0.69246       0.41578      0.640676        1.783004
                judge6         0.99648       0.57462      0.668583        2.017351
                judge7         0.99411       0.55932      0.684499        2.169563
                judge8         1.00803       0.79870      0.374305        0.598222
                OVER-ALL       0.88175       0.54957      0.612821        1.582786

                                  Pseudo F Statistic =   471.67

                       Approximate Expected Over-All R-Squared =   0.12777
                             Cubic Clustering Criterion =  116.387
               WARNING: The two values above are invalid for correlated variables.

If variables are not correlated, the approximate expected overall R-squared and the cubic clustering criterion (CCC) coefficient may be used when comparing the 2-cluster solution with other solutions, with higher coefficients being better. By rule of thumb, CCC > 3 (some say 2) indicates a well-fitting cluster model. Negative CCC usually indicates the presence of outliers. For this example, however, variables are correlated and so over-all R-Squared and CCC would not be reported.

Tables of cluster means and cluster standard deviations are also output, not shown here. In these listings, clusters are the rows and variables (judges) are the columns.

The case listing table shows for each observation (athlete) the input value for each clustering variable (each judge), as well as the cluster number and the Euclidean distance.

 
           Obs      judge1      judge2      judge3      judge4      judge5      judge6
             1        7.10        7.20        7.00        7.70        7.10        7.10
             2        9.30        9.70        8.90        9.60        8.60        9.50
             3        8.90        8.80        8.10        9.30        8.50        8.10
            ...

           Obs      judge7      judge8       CLUSTER    DISTANCE
             1        7.00        7.30           1        1.86724
             2        9.60        9.70           2        0.90105
             3        7.60        8.70           1        2.18702
            ...

Crosstabulation of cluster membership with any other discrete variable may be accomplished using PROC FREQ. In the syntax below, the working dataset "clusters" was created by the OUT= parameter of the PROC FASTCLUS procedure. Anyvarname could be the name of any other discrete variable in the dataset. Cluster is a variable created automatically by PROC FASTCLUS, containing the cluster membership number for each case.
```
   PROC FREQ DATA=clusters;
      TABLES Anyvarname*Cluster;
   RUN;
```

PROC VARCLUS supports hierarchical (if the HIERARCHY parameter is specified) or disjoint (the default) clustering based on multiple-group component cluster algorithms. Its typical use is to sort variables into disjoint clusters.

Example. In 1993, the General Social Survey polled a national random sample of individuals regarding their likes and dislikes for each of 11 genres of music, ranging from opera to heavy metal. PROC VARCLUS may be used to sort these music-genre variables into clusters.
Syntax.
```
PROC IMPORT OUT= WORK.varclus1 
            DATAFILE= "C:\Data\GSS93 subset.sav"
            DBMS=SPSS REPLACE;
RUN;
TITLE "PROC VARCLUS Example" JUSTIFY=CENTER;
PROC VARCLUS DATA=varclus1 MAXEIGEN = .7 TRACE OUTTREE=tree MAXCLUSTERS=4;
VAR bigband--hvymetal;
RUN;
PROC TREE DATA=tree HORIZONTAL NCLUSTERS=4 OUT=outfile;
RUN;
PROC PRINT DATA=outfile;
RUN;
```
The syntax above is interpreted as follows (note PROC VARCLUS has many more options than utilized in this example):
1. PROC IMPORT is the same as previously described for PROC CLUSTER.
2. TITLE is an optional statment placing text at the top of each page of output.
3. PROC VARCLUS invokes an oblique principal components clustering procedure unless the parameter CENTROID is specified, in which case a centroid components clustering procedure is used (not the case in this example). Principal components is a factor analysis approach which seeks a weighted linear combination of variables which explains the maximum possible variance in the input variables. Centroid components is based on maximizing the sum across clusters of explained variance, based on unweighted means of standardized or unstandardized variables. The default is standardized, treating all variables as equal in importance. If the COV option is specified, the covariance matrix is used, meaning data are unstandardized and variables with larger variances become more critical to results.
  1. DATA=varclus1. This parameter specifies the working data set, created by PROC IMPORT.
  2. MAXEIGEN = .7. This parameter allows splitting of clusters when the eigenvalue is .7 or greater. That is, it sets the threshold for creating additional clusters. If the MAXEIGEN parameter is omitted and CENTROID is not specified, the cluster with the largest eigenvalue associated with the second principal component is split, provided its eigenvalue is 1.0 or greater. In this example, MAXEIGEN = .7 is a more lenient criterion. If CENTROID is specified, If the researcher specifies CENTROID, VARCLUS splits clusters baseed on the smallest percentage of variation explained by its cluster component rather than with the second principal component. In this example, VARCLUS will continue to split clusters until the number of clusters is 4 (specified by the MAXCLUSTERS= parameter, discussed below) or no cluster meets the MAXEGEN=.7 criterion. Note that alternatively one may specify a PROPORTION= parameter(not used in this example), which sets the minimum proportion of variance explained for a cluster to be split.
  3. TRACE. This option causes step-by-step display of the splitting process, showing each variable's assignment to each cluster at each iteration.
  4. OUTTREE=tree. The creates the working data file "tree", used by PROC TREE below to print the dendogram (cluster tree diagram) and create the cluster membership data file. Alternatively, "tree" can be used with PROC SCORE to computer component scores for each cluster.
  5. MAXCLUSTERS=4;. This parameter sets the maximum number of clusters at 4. There is also a MINCLUSTERS= parameter, not used in this example, so the minimum defaults to 1.
4. VAR bigband--hvymetal;. The VAR statement specifies the variables to be used. The music genre variables are adjacent in the data file, with 11 variables starting with bigband and ending with hvymetal.
5. PROC TREE and PROC PRINT are the same as previously described for PROC CLUSTER.

VARCLUS output, including output from PROC TREE and PROC PRINT.

The dendogram from PROC TREE. The cluster tree below depicts four clusters, with rap and heavy metal music being one cluster, blues and jazz another, country and bluegrass a third, and all others a fourth. Were clusters to be merged further to the right in the dendogram, blues and jazz respondents would merge with rap and heavy metal respondents sooner than they would with all others, as indicated by the merge bridge being further to the left.

The cluster summary table. Output below is for the four-cluster solution, but similar output is provided for the 1-, 2-, and 3-cluster solutions. The "Cluster Summary" table below shows that the cumulative proportion of variance explained in the 4-cluster solution by all four clusters is 67.5%. A 5-cluster solution might have explained more.

                                  Cluster Summary for 4 Clusters

                                     Cluster    Variation    Proportion        Second
             Cluster    Members    Variation    Explained     Explained    Eigenvalue
             ________________________________________________________________________
                   1          5            5     2.786607        0.5573        0.7235
                   2          2            2     1.559927        0.7800        0.4401
                   3          2            2     1.425733        0.7129        0.5743
                   4          2            2     1.350464        0.6752        0.6495

                     Total variation explained = 7.122731 Proportion = 0.6475

The R-squared table. This table shows which music genre variables are associated with which cluster in the 4-cluster solution. The "Own Cluster" and "Next Closest" columns display the R-squared value of the row variable with its own cluster and with its nearest cluster respectively. The "1-R**2 Ratio" column is the ratio of 1 - the "Own Cluster" R-squared to 1 - the "Next Closest" R-squared. Smaller ratio variables indicate better clustering. Cluster 2 clusters best, cluster 1 least well.

                                     R-squared with 4 Clusters                
                                   
                                       Own       Next    1-R**2    Variable
         Cluster       Variable    Cluster    Closest     Ratio    Label
         _______________________________________________________________________________
         Cluster 1     bigband      0.5049     0.1077    0.5549    Bigband Music
                       musicals     0.6333     0.0799    0.3985    Broadway Musicals
                       classicl     0.6511     0.0817    0.3799    Classical Music
                       folk         0.4123     0.1270    0.6731    Folk Music
                       opera        0.5850     0.0714    0.4469    Opera
         -------------------------------------------------------------------------------
         Cluster 2     blues        0.7800     0.0919    0.2423    Blues or R & B Music
                       jazz         0.7800     0.1068    0.2463    Jazz Music
         -------------------------------------------------------------------------------
         Cluster 3     blugrass     0.7129     0.0786    0.3116    Bluegrass Music
                       country      0.7129     0.0047    0.2885    Country Western Music
         -------------------------------------------------------------------------------
         Cluster 4     rap          0.6752     0.0362    0.3370    Rap Music
                       hvymetal     0.6752     0.0117    0.3286    Heavy Metal Music

The standardized scoring coefficients table. The scoring coefficients, as in factor analysis, are coefficients by which standardized variables are multiplied when computing cluster compute component scores. As such they are part of intermediate output and usually are not reported or interpreted. Note that each music genre variable is scored for only one cluster. In any column, the ratio of scoring coefficients shows the weighting of standardized variables for that cluster.

                                Standardized Scoring Coefficients

   Cluster                                         1             2             3             4
   ___________________________________________________________________________________________
   bigband       Bigband Music              0.254980      0.000000      0.000000      0.000000
   blugrass      Bluegrass Music            0.000000      0.000000      0.592197      0.000000
   country       Country Western Music      0.000000      0.000000      0.592197      0.000000
   blues         Blues or R & B Music       0.000000      0.566152      0.000000      0.000000
   musicals      Broadway Musicals          0.285581      0.000000      0.000000      0.000000
   classicl      Classical Music            0.289571      0.000000      0.000000      0.000000
   folk          Folk Music                 0.230437      0.000000      0.000000      0.000000
   jazz          Jazz Music                 0.000000      0.566152      0.000000      0.000000
   opera         Opera                      0.274473      0.000000      0.000000      0.000000
   rap           Rap Music                  0.000000      0.000000      0.000000      0.608476
   hvymetal      Heavy Metal Music          0.000000      0.000000      0.000000      0.608476

The cluster structure table. This is a table of correlations of each row variable with each column cluster. This provides information on how much each cluster represents each music genre variable.

                                        Cluster Structure

   Cluster                                         1             2             3             4
   ___________________________________________________________________________________________
   bigband       Bigband Music              0.710528      0.328180      0.229415      -.079317
   blugrass      Bluegrass Music            0.280356      0.169543      0.844314      -.012270
   country       Country Western Music      0.062101      -.028955      0.844314      -.068802
   blues         Blues or R & B Music       0.303215      0.883155      0.150752      0.157381
   musicals      Broadway Musicals          0.795803      0.282606      0.099232      -.034073
   classicl      Classical Music            0.806920      0.285795      0.022910      0.011338
   folk          Folk Music                 0.642139      0.157035      0.356342      -.058354
   jazz          Jazz Music                 0.326757      0.883155      -.003696      0.163230
   opera         Opera                      0.764848      0.267163      0.099164      0.051174
   rap           Rap Music                  0.016384      0.190224      -.029399      0.821725
   hvymetal      Heavy Metal Music          -.059234      0.108086      -.049504      0.821725

The table of inter-cluster correlations. VARCLUS uses oblique principal components, so clusters may correlate. This table shows these correlations.

                                   Inter-Cluster Correlations

                 Cluster             1             2             3             4

                 1             1.00000       0.35666       0.20280      -0.02607
                 2             0.35666       1.00000       0.08326       0.18151
                 3             0.20280       0.08326       1.00000      -0.04801
                 4            -0.02607       0.18151      -0.04801       1.00000

The cluster history summary statistics table. The rows represent the 1-, 2-, 3-, and 4-cluster solutions respectively. The "Proportion of Variation Explained by Clusters" column shows that in the final (4-cluster) solution, 64.75% of the variation in the music genre variables was accounted for by the four clusters. The lower the coefficient in the ratio column at the far right, the better the clustering.


                   Total     Proportion        Minimum        Maximum     Minimum        Maximum
    Number     Variation   of Variation     Proportion         Second   R-squared   1-R**2 Ratio
        of     Explained      Explained      Explained     Eigenvalue       for a          for a
  Clusters   by Clusters    by Clusters   by a Cluster   in a Cluster    Variable       Variable
  ______________________________________________________________________________________________
         1      3.275665         0.2978         0.2978       1.660727      0.0003
         2      4.669804         0.4245         0.4183       1.456046      0.0384         0.9645
         3      5.954356         0.5413         0.4355       1.174827      0.2198         0.7829
         4      7.122731         0.6475         0.5573       0.723516      0.4123         0.6731

PROC PRINT in this example was used to print the content of the working data file "outfile," which was an output of PROC TREE. As can be seen below, each case (row) is a music genre variable from the input dataset. In the "outfile" dataset, the CLUSTER variable contains the cluster to which each music genre variable was assigned by PROC VARCLUS. This dataset could be saved and used in other forms of analysis (ex., cross-tabulations).

                              Obs    _NAME_      CLUSTER    CLUSNAME

                                1    bigband        1        Clus4
                                2    blugrass       2        Clus5
                                3    country        2        Clus5
                                4    blues          3        Clus6
                                5    musicals       1        Clus4
                                6    classicl       1        Clus4
                                7    folk           1        Clus4
                                8    jazz           3        Clus6
                                9    opera          1        Clus4
                               10    rap            4        Clus7
                               11    hvymetal       4        Clus7

PROC MODECLUS is a SAS procedure for nonparametric density clustering. It is the newest SAS clustering procedure and is differentiated from those above in that it can compute p values giving the significance of each cluster. Nonsignificant clusters can be hierarchically combined to form significant clusters. Also, it is not necessary to specify the number of clusters in advance. Nonparametric density clustering is particularly recommended for data characterized by clusters of unequal size and dispersion and irregular shape, though PROC MODECLUS also perform well for compact clusters of equal size and dispersion. A larger sample size is required than for other clustering procedures.

Other Forms of Cluster Analysis

Expected maximization (EM) clustering. This method is similar to k-means clustering, except that EM clustering uses maximum likelihood estimation to determine clusters. It is similar to k-means clustering in that the number of clusters, k, must be determined beforehand by the researcher. Cases are assigned to clusters based on maximizing the likelihood of the data distribution, given the final clusters. The final clustering selected is thus the one with the maximum probabilities of cluster memberships.
- Cross-classification to determine k. Some computer programs support v-fold cross-classification to assist the researcher in determining k, the number of clusters to request. In this method, the sample is divided into v "folds" or groups, one of which is reserved as the test group. Models are developed for the (v - 1) folds, then tested on the test group. Output takes the form of a scree plot with the number of clusters being the x axis and -2LL (-2 log likelihood) being the y axis. The -2LL will diminish with each successive cluster added. The researcher selects as the optimal number of clusters the number where the scree line has an "elbow" and levels off (or occasionally even increases).
- Distributional characteristics. Like other maximum likelihood methods, the EM approach supports categorical as well as continuous variables, which is a major reason for its use. While k-means clustering can also be adapted to support categorical variables, EM clustering (depending on the computer program) makes it easy for the researcher to select among alternative probability distribution assumptions (ex., normal, log-normal, or Poisson) for each variable.
- Classification probabilities. Whereas in k-means clustering cases are assigned to one and only one cluster, in EM clustering each case belongs to each cluster with a certain probability. Just as in factor analysis each variable loads on all factors but may load most heavily on one given factor, so in EM clustering the researcher may assign the case to the cluster for which it has the highest probability of belonging (the highest "classification probability").
Q-mode factor analysis can be used if the distance matrix is composed of correlations (see above). This method of cluster analysis has the special problem of negative factor loadings. In conventional factor analysis of variables, a negative loading indicates a negative relation of the variable to the factor. In Q-mode factor analysis, a negative loading does not have a clear meaning. One common approach is to consider all cases with negative loadings as being in a cluster of their own. Factor analysis as a clustering procedure also suffers from the problem of what to do with cases which crossload on more than one factor. Also, factor analysis assumes a linear model which may not be appropriate for clustering cases in particular research settings. On the other hand, unlike cluster analysis or multidimensional scaling, factor analysis takes control relationships into account and does not treat correlation simply as a distance measure.
Multidimensional scaling (MDS) performs a type of cluster analysis when the researcher selects "By cases" as the mode under the Measure button dialog in SPSS multidimensional scaling. Everitt and Rabe-Hesketh (1997) used real and simulated data to compare MDS and clustering methods, finding a better fit with clustering models when the data had an underlying hierarchical (tree) structure and a better fit with MDS models when data had an underlying non-hierarchical spatial structure. This difference is paralleled in the graphical output of the two techniques: a hierarchical dendogram (tree) for cluster analysis vs. a perceptual map for MDS. Also, MDS and clustering methods may well result in a different number of factors. Sometimes the methods are combined: Sireci & Geisinger (1992), for instance, used MDS and cluster analysis sequentially to analyze the content of test items, first obtaining similarity ratings of items from a panel of experts, then employing MDS on this distance data, then using the MDS stimulus coordinates as the input data for hierarchical cluster analysis.
Discriminant analysis may be performed on membership/nonmembership in a cluster. This will show which variables contributed the most to definition of the cluster. It also gives the discriminant function formula for predicting cluster membership for additional cases.
F-ratio methods. There are many other cluster formation methods. Most rely on an analog to the F-ratio in analysis of variance, which is the ratio of between-groups variance to within-groups variance. Note that the results of F-ratio methods can depend on the initial, arbitrary selection of pairs of cases as starting centers for clusters. Because of this, an iterative approach is needed to establish stable results.

Assumptions

Randomization. K-means cluster analysis and two-stage cluster analysis both depend upon the sequence of observations in the dataset (hierarchical clustering does not). In each method, different data orders usually yield different outcomes. Randomization of cases is recommended. The smaller the dataset, the greater the problem of data order even with randomization. Small datasets can yield strikingly different cluster patterns for different data sequences. A recommended strategy is to couple randomization with multiple runs as a form of stability analysis to establish that the clusters of research interest are stable across different random orderings.
Data level. Data are interval in level or are true dichotomies for hierarchical and k-means clustering. Two-step clustering can handle categorical data as well as continuous. When at least one variable is categorical, two-step clustering must be used. K-means clustering uses Euclidean distance as a measure and whereas correlation is a standardized distance measure, Euclidean distances reflect the magnitude of the variables. Reducing an underlying continuous distribution to a dichotomy reduces magnitudes from the true state, which is why only interval data and true dichotomies are appropriate.
Independence of observations. Independent observations are assumed. Response for case k should not be predictive of the response for case k + 1 (no autocorrelation).
Independence of variables. The independence assumption is required by the related assumption of a joint multinomial-normal distribution on categorical and continuous variables, and this assumption in turn is needed by the log-likelihood distance method used by two-step clustering by default.
This assumption can be tested by creating a bivariate correlation matrix of the continuous variables to see if the correlations are not significantly different from zero Likewise, crosstabulation can establish if any pair of categorical variables is not significantly related (chi-square test). To establish the independennce of a continuous and categorical variable, the SPSS Means procedure may be used. Two-step clustering is fairly robust even when the assumption of independence is violated.
Comparability. Standardization of variables is not required but is often recommended so that all variables have equal impact on the computation of distances. Some computer algorithms, including two-step clustering in SPSS, make standardization the default. K-means clustering (PROC FASTCLUS in SAS) is highly sensitive to unequal variances and standardization is usually recommended. Correlation matrices are inherently standardized (correlation is standardized covariance). Standardization depends on the research purpose See the FAQ section on this issue.
GLM assumptions. The same assumptions as correlation, regression, factor analysis, and other members of the multiple linear general hypothesis family of procedures. However, significance testing is not performed on cluster membership apart from exploratory/descriptive purposes, so violation of these assumptions may be less important to the research purpose. Also note that where most GLM procedures compute partial coefficients, estimating effects of a variable after other model variables have been controlled, cluster analysis treats correlation as simple distance and variables are located in MDS space based on zero-order correlation, similarity, or dissimilarity measures.
Sample size. K-means cluster analysis assumes a large sample (ex., > 200). Likewise, the log-likelihood method in two-step cluster analysis assumes a large sample.
Outliers. K-means cluster analysis is very sensitive to outliers. It is common to remove outliers before conducting k-means cluster analysis. However, two-stage clustering is also sensitive but in the SPSS Options button dialog for this type of cluster analysis, one can select "Outlier Treatment" to have outlier cases automatically segregated into their own cluster.
Normality. The two-step cluster procedure's log-likelihood method assumes normal distributions for continuous variables and multinomial distributions for categorical variables. Two-step clustering is fairly robust even when the normality assumption is violated.

Frequently Asked Questions

Where did the example files in this section come from?
Should data be standardized prior to running cluster analysis?
What are alternative distance measures?
- Euclidean distance and squared Euclean distance are discussed above.
- Cosine.. Interval-level similarity based on the cosine of the angle between two vectors of values. Consider classifying stories on two dimensions: hate-love and sad-happy. Two stories will be at zero cosine distance if they are in the same direction from the origin, even if one is much further from the origin than the other, as is the case of points A, B, and C in this example. Maximum cosine distance is attained when points are on vectors from the origin which are 180 degrees from each other, on opposite sides of the origin, regardless of distance from the origin. Euclidean distance would be better if the research question centered on how much love or hate or happiness or sadness were displayed by stories. Cosine distance would be better if the research question centered on differentiating types of stories.
  
  Here The cosine distance of points B and C (which are cases 2 and 3) with respect to the origin (point A) is 0, since they are on a line from the origin. However, the vectors from point B to point C, and from point C to point B, are in opposite directions and hence have a cosine distance of 1.
- Chebyshev distance is the maximum absolute difference between a pair of cases on any one of the two or more dimensions (variables) which are being used to define distance, ignoring their similarity on the remaining dimensions. Thus in classifying stories, if a pair of stories is far apart on the sadness-happiness dimension and close on the hate-love dimension, the sadness-happiness distance will be the Chebyshev distance. Information on the hate-love dimension is not utilized, so long as distance on that dimension is less. In this example, the Chebyshev distance from A to B is 5 and from A to C is 10, since only the longest vector is counted (this is the vector for the sadness-happiness dimension).
- Block distance, also known as city block distance or Manhattan distance, is the absolute difference across the two or more dimensions which are used to define distance. Some authors also call this "Chebyshev distance," but note SPSS distinguishes the two. For the two dimensions in the example plot above, the block distance is the number of grid cells over and up from one point to another, regardless of the path taken as long as it is a shortest path (represented by the blue lines in the figure).
- Minkowski distance is the generalized distance function. The pth root of the sum of the absolute differences to the pth power between the values for the items.
  When p = 1, Minkowski distance is city block distance. In the case of binary data, when p = 1 Minkowski distance is Hamming distance, defined by the number of common "1" codings. When p = 2, Minkowski distance is Euclidean distance. Note that when the k variables are unstandardized and measured on different scales, the variables with the larger scales will dominate.
- Pearson correlation. Interval-level similarity based on the product-moment correlation. For case clustering as opposed the variable clustering, the reseacher transposes the normal data table in which columns are variables and rows are cases. By using columns as cases and rows as variables instead, the correlation is between cases and these correlations may constitute the cells of the similarity matrix. Such case correlation is most intepretable when the set of variables is coherent (ex., environmental votes) rather than disparate (ex., mixing environmental and defense votes).
  - Absolute values. Since for Pearson correlation, high negative as well as high positive values indicate similarity, the researcher normally selects absolute values. This can be done by checking the absolute value checkbox in the Transform Measures area of the Methods subdialog (invoked by pressing the Methods button) of the main Cluster dialog.
- Customized.. This is a generalization of Minkowski distance, using the rth root of the sum of the absolute differences to the pth power between the item values.
  COUNTS
  1. Chi-square measure.. Based on the chi-square test of equality for two sets of frequencies, this measure is the default for count data.
  2. Phi-square measure. . Phi-square normalizes chi-square measure by the square root of the combined frequency. Normalization yields distances with a mean of 0 and a standard deviation of 1.
  BINARY
  1. Squared Euclidean distance is also an option for binary data as it is for interval.
  2. Size difference. This asymmetry index ranges from 0 to 1.
  3. Pattern difference. This dissimilarity measure also ranges from 0 to 1. Computed from a 2x2 table as bc/(n**2), where b and c are the diagonal cells and n is the number of observations.
  4. Variance. Computed from a2x2 table as (b+c)/4n. It also ranges from 0 to 1.
  5. Dispersion. is a similarity measure with a range of -1 to 1.
  6. Shape. is a distance measure with a range of 0 to 1. Shape penalizes asymmetry of mismatches.
  7. Simple matching. is the ratio of matches to the total number of values.
  8. Phi 4-point correlation. is a binary analog of the Pearson correlation coefficient and has a range of -1 to 1.
  9. Lambda. TGoodman and Kruskal's lambda, which is interpreted as the proportional reduction of error (PRE) when using one item to predict the other (predicting in both directions). It ranges from 0 to 1, with 1 being perfect predictive monotonicity..
  10. Anderberg's D. is a variant on lambda. D is the actual reduction of error using one item to predict the other (predicting in both directions). I ranges from 0 to 1.
  11. Dice., also called the Czekanowski or Sorensen measure, is an index in which joint absences are excluded from computation and matches are weighted double.
  12. Hamann is the number of matches minus the number of nonmatches, divided by the total number of items. The Hamann index ranges from -1 to 1.
  13. Jaccard. This is an index in which joint absences are excluded from consideration. Equal weight is given to matches and nonmatches. Also known as the similarity ratio. Jaccard is commonly recommended for binary data.
  14. Kulczynski 1 is the ratio of joint presences to all nonmatches. Its lower bound is 0 and it is unbounded above. It is theoretically undefined when there are no nonmatches; however, the software assigns an arbitrary value of 9999.999 when the value is undefined or is greater than this value.
  15. Kulczynski 2. is the conditional probability that the characteristic is present in one item, given that it is present in the other.
  16. Lance and Williams index, also called the Bray-Curtis nonmetric coefficient, is based on a 2x2 table, using the formula (b+c)/(2a+b+c), where a represents the cell corresponding to cases present on both items, and b and c represent the diagonal cells corresponding to cases present on one item but absent on the other. It ranges from 0 to 1.
  17. Ochiai index is the binary equivalent of the cosine similarity measure and ranges from 0 to 1.
  18. Rogers and Tanimoto index gives double weight to nonmatches.
  19. Russel and Rao index is equivalent to the inner (dot) product, giving equal weight to matches and nonmatches. This is a common choice for binary similarity data.
  20. Sokal and Sneath 1 index also gives double weight to matches.
  21. Sokal and Sneath 2. index gives double weight to nonmatches, but joint absences are excluded from consideration.
  22. Sokal and Sneath 3. index is the ratio of matches to nonmatches. Its minimum is 0 but it is unbounded above. It is theoretically undefined when there are no nonmatches; however, the software assigns an arbitrary value of 9999.999 when the value is undefined or is greater than this value.
  23. Sokal and Sneath 4 index is based on the conditional probability that the characteristic in one item matches the value in the other, taking the mean of predictions either direction.
  24. Sokal and Sneath 5 index is the squared geometric mean of conditional probabilities of positive and negative matches. It ranges from f 0 to 1.
  25. Yule's Y. , also called the coefficient of colligation, is a similarity measure based on the cross-ratio for a 2 x 2 table and is independent of the marginal totals. It ranges from -1 to +1.
  26. Yule's Q. is a similarity measure which is a special 2x2 case of Goodman and Kruskal's gamma. It is based on the cross-ratio and is independent of the marginal totals. It ranges from -1 to +1.
It is acknowledged that k-means and hierarchical clustering are inefficient and inaccurate for large datasets, but what is the evidence that two-step clustering does better?
Can I cluster variables instead of cases?
Isn't discriminant analysis the same as cluster analysis?
What is the ratio of distance measure used in autoclustering in two-step cluster analysis?
What is BIRCH clustering?
What is ClustanGraphics?
What is SaTScan?

Bibliography

Abonyi, J�nos& Feil, Bal�zs (2007). Cluster analysis for data mining and system identification. Boston and Basel, Switzerland: Birkh�user Basel.
Aldenderfer, Mark S. and Roger K. Blashfield (1984). Cluster analysis. Thousand Oaks, CA: Sage Publications, Quantitative Applications in the Social Sciences Series No. 44.
Anderberg, M. R. (1973). Cluster analysis for applications. New York: Academic Press.
Arabie, P.; Carroll, J. D.; & DeSarbo, W. S. (1987). Three-way scaling and clustering. Beverly Hills, CA: Sage.
Banfield, J. D. & Raftery, A. E. (1998). Modl-based Gaussian and non-Gaussian clustering. Biometrics 49, 803-821.
Corter, James E. (1996). Tree models of similarity and association. Thousand Oaks, CA: Sage Publications, Quantitative Applications in the Social Sciences Series No. 112.
Everitt B. S. (1980) Cluster Analysis,. London: Heinemann.
Everitt, B. S., & Rabe-Hesketh, S. (1997). The analysis of proximity data. London: Arnold.
Everitt, Brian S., Sabine Landau, & Morven Leese (2001). Cluster analysis, 4th Edition. London: Edward Arnold Publishers Ltd. Highly recommended introductory text.
Jain, A. K.& Dubey, R. C. (1988). Algorithms for clustering data. Englewood Cliffs, NJ: Prentice Hall.
Jajuga, Krzystof; Sokolowski; Andrzej; & Bock, Hans-Hermann (2002). Classification, clustering and data analysis. Y: Springer.
Kachigan, Sam K. (1982). Multivariate statistical analysis. NY: Radius Press. Chapter 8 provides a very readable introduction to cluster analysis.
Kaufman, Leonard & Rousseeuw Peter J. (2005). Finding groups in data: An introduction to cluster analysis NY: Wiley-Interscience.
Melia, M. & Heckerman, D. (1998). An experimental comparison of several clustering and initialization methods. Microsoft Research Technical Report MSR-TR-98-06.
Rapkin, B. D., & Luke, D. A. (1993). Cluster analysis in community research: Epistemology and practice. American Journal of Community Psychology 21, 247-277.
Romesburg, Charles (2004). Cluster analysis for researchers. Internet: lulu.com.
Sarle, W.S & Kuo, An-Hsiang (1993). The MODECLUS procedure. SAS Technical Report P-256, Cary, NC: SAS Institute Inc.
Schneider, Andreas & Roberts, A. E. (2005). Classification and the relations of meaning. Quality & Quantity 38(5): 547-557. Treats the logic of K-means cluster analysis in the classification of affective meanings:
Sireci, S. G. & Geisinger , K. F. (1992). Analyzing test content using cluster analysis and multidimensional scaling. Applied Psychological Measurement 16(1), 17-31.
SPSS, Inc. (2001). The SPSS twostep cluster component. Chicago, IL: SPSS. SPSS white papers/technical report TSCPWP-0101.
Theodoridis, S. & Koutroumbas, K. (1999). Pattern recognition. NY: Academic Press.
Zhang, T.; Ramakrishnon, R.; & Livny, M. (1996). BIRCH: Method for very large databases. Proceedings of the ACM. Management of Data. Pp. 103�114. Montreal, Canada.