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
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.

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. Linkage method and distance measure options are discussed in the introductory section above.
  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 will dominate. To avoid this it is common to first standardize all variables. SPSS hierarchical clustering supports these types of measures:
  INTERVAL
  1. Euclidean distance is the most common distance measure. A given pair of cases is plotted on two variables, which form the x and y axes. The Euclidean distance is the square root of the sum of the square of the x difference plus the square of the y distance. (Recall high school geometry: this is the formula for the length of the third side of a right triangle.)
  2. Squared Euclidean distance removes the sign and also places greater emphasis on objects further apart, thus increasing the effect of outliers. This is the default for interval data.
  3. Cosine.. Interval-level similarity based on the cosine of the angle between two vectors of values.
  4. 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.
    - 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.
  5. Chebychev 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. Pairs will be defined as different according to their difference on a single dimension, ignoring their similarity on the remaining dimensions.
  6. Block distance, also known as city block distance or Manhattan distance, is the average absolute difference across the two or more dimensions which are used to define distance.
  7. 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. When the k variables are unstandardized and measured on different scales, the variables with the larger scales will dominate.
  8. 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.
  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.
    li> 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.
  14. Kulczynski 2. is the conditional probability that the characteristic is present in one item, given that it is present in the other.
  15. 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.
  16. Ochiai index is the binary equivalent of the cosine similarity measure and ranges from 0 to 1.
  17. Rogers and Tanimoto index gives double weight to nonmatches.
  18. 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.
  19. Sokal and Sneath 1 index also gives double weight to matches.
  20. Sokal and Sneath 2. index gives double weight to nonmatches, but joint absences are excluded from consideration.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
- Method button, continued: linkage. 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 betweeb0grop 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.
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
  - 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.
    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.
    - 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 objects, 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.
    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 LOptions dialog's Statistics section, and illustrated below, shows through the "distance" variable how close or far a given case is from the centroid of its cluster group. Cases with very large distances are outliers 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. 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 gives BIC and BIC change for all solutions. In auto-determining the optimal number of clusters, various criteria have been proposed such as the number of clusters with the smallest BIC (the Schwarz Bayesian Information Criterion), the number of clusters with the smallest AIC (Akaike Information Criterion), and others. By default the SPSS algorithm uses a combination of BIC (though AIC may be selected by the researcher) and log-likelihood distance. SPSS will pick a solution with a reasonably large "Ratio of BIC Changes" and a large "Ratio of Distance Measures." Simulation studies have shown this combined criterion works better than BIC or AIC alone It is also possible to simply to tell SPSS how many clusters are wanted. This table is not provided when the researcher has asked for a fixed number of clusters as there is no "change."
    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.

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. Correlation matrices are inherently standardized (correlation is standardized covariance).
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?
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 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.