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 seeks to identify a set of groups which both minimize within-group variation and maximize between-group variation. 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. In k-means clustering the researcher specifies the number of clusters in advance, then 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. Finally, two-step clustering creates pre-clusters, then it clusters the pre-clusters. Two step clustering handles very large datasets, is the method chosen when data are categorical, 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.
Similarity and Distance
- Distance. 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.
  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, so to avoid this it is common to first standardize all variables. SPSS supports these interval 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. City block distance, also known as block distance or Manhattan distance, is the average absolute difference across the two or more dimensions which are used to define distance.
  4. 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.
  5. 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.
  6. 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.
  7. Pearson correlation. Interval-level similarity based on the product-moment correlation.
    - 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.
  8. Cosine.. Interval-level similarity based on the cosine of the angle between two vectors of 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. Russel and Rao index is equivalent to the inner (dot) product, giving equal weight to matches and nonmatches. This is the default for binary similarity data.
  2. Euclidean and squared Euclidean distance is also an option for binary data.
  3. 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.
  4. Phi 4-point correlation. is a binary analog of the Pearson correlation coefficient and has a range of -1 to 1.
  5. Size difference. This asymmetry index ranges from 0 to 1.
  6. 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.
  7. Variance. Computed from a2x2 table as (b+c)/4n. It also ranges from 0 to 1.
  8. Dispersion. is a similarity measure with a range of -1 to 1.
  9. Shape. is a distance measure with a range of 0 to 1. Shape penalizes asymmetry of mismatches.
  10. Simple matching. is the ratio of matches to the total number of values.
  11. 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..
  12. 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.
  13. Dice., also called the Czekanowski or Sorensen measure, is an index in which joint absences are excluded from computation and matches are weighted double.
  14. 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.
  15. 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.
  16. Kulczynski 2. is the conditional probability that the characteristic is present in one item, given that it is present in the other.
  17. 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.
  18. Ochiai index is the binary equivalent of the cosine similarity measure and ranges from 0 to 1.
  19. Rogers and Tanimoto index gives double weight to nonmatches.
  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.
    Summary. 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.
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:
- 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 distance between their two furthest member points. This method works well when the plotted clusters form distinct clumps (not elongated chains).
- UPGMA (unweighted pair-group method using averages). The distance between two clusters is the average distance between all inter-cluster pairs. UPGMA 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. and is the default method in SPSS. SPSS labels this "between-groups linkage." This method works well for both elongated chain-type and with clumpy type clusters.
- 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."
- 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.
- Centroid methods. The simplest centroid method is also called the "unweighted pair-group method using centroid averages" (UPGMC). SPSS calls UPGMC the Median method. The cluster to be merged is the one with the smallest sum of Euclidean distances between cluster means (centroids) for all variables. There is also a weighted version (WPGMC) which weights for differences in cluster sizes. WPGMC is preferred when cluster sizes vary markedly. SPSS calls WPGMC the centroid method.
- Correlation of items can be used as a similarity measure. One 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.
- Binary matching is another type of similarity measure, where 1 indicates a match and 0 indicates no match between any pair of cases. There are multiple matched attributes and the similarity score is the number of matches divided by the number of attributes being matched. Note that it is usual in binary matching to have several attributes because there is a risk that when the number of attributes is small, they may be orthogonal to (uncorrelated) with one another, and clustering will be indeterminate.

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 calls hierarchical clustering the "Cluster procedure." In SPSS, select Analyze, Classify, Hierarchical Cluster; select variables; select Cases in the Cluster group click Statistics, select Proximity Matrix; select Range of Solutions in the Cluster Membership group, specify the number of clusters (typically 3 to 6); Continue; OK.
Output
- 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.
- 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 cases as rows, 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 cases are in which groups, 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. For instance, at Stage 1, cases 3 and 18 might be combined, resulting in a cluster labeled 3. Later cluster 3 and case 2 might be combined, resulting in a cluster labeled 2. The researcher looks at the "Coefficients" column of the agglomerative schedule and notes when the proximity coefficient jumps up and is not a small increment from the one before (or when the coefficient reaches some theoretically important level). Note that for distance measures, low is good, meaning the cases are alike; for similarity measures, high coefficients mean cases are alike. After the stopping stage is determined in this manner, the researcher can work backward to determine how many clusters there are and which cases belong to which clusters (but it is easier just to get this information from the cluster membership table). Note, though, that SPSS will not stop on this basis but instead will compute the range of solutions (ex., 2 to 4 clusters) requested by the researcher in the Cluster Membership group of the Statistics button in th Hierarchical Clustering dialog. 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 50 objects, the agglomeration schedule shows, for instance, that judges 3 and 5 are combined in a cluster first (the cluster is labeled 3). Then at a later point, stage 4, the new cluster 3 is combined with judge 7 to form a larger cluster, also now labeled 3. Etc.
  - Linkage plots show similar information in graphic form.
    - 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. 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. The last/bottom row will show all the cases in separate one-case clusters. This is the (n - 1) solution. The next-to-last/bottom column/row will show the (n-2) solution, with two cases combined into one cluster. Subsequent columns/rows show further clustering steps. Row 1 (vertical icicle plots) or column 1 (horizontal icicle plots) will show all cases in a single cluster. 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 50 objects, the vertical icicle plot shows that when there are 2 clusters, the judge labeled "Enthusiast" is in one cluster and all the country-affiliated judges are in the other. When there are 3 clusters, Enthusiast is still in a cluster alone, Russia-China-Romania are in a second cluster, and all other countries in a third cluster. Etc.
    - 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. Cases with low distance/high similarity are close together. Cases 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 50 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") is not shown but indicated by the trailing linkage line furthest to the left. While this figure and those above were for clustering variables, one can also cluster cases. The dendogram below is for the clustering of the 50 objects, with objects 10, 38, 17, 16, 18, 43, 2, 46, and 27 forming one of the first clusters:

K-means Cluster Analysis

K-means cluster analysis. 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, 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.
- 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.
- 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.
- Method. The default 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.
- Agglomerative K-means clustering. Normally in K-means clustering, a given case may be assigned to a cluster, then reassigned to a different cluster as the algorithm unfolds. However, in agglomerative K-means clustering, the solution is constrained to force a given case to remain in its initial cluster.
- 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 you must re-run K-means clustering, asking for a different number of 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 relationship with other variables. The K-means cluster's Save button will save the cluster number of each case (labeled QCL_1). 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.

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. The two-step method is a one-pass-through-the-daa 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 two-step method is also the one chosen when categorical variables with three or more levels are involved. The researcher can let the two-step algorithm determine the number of clusters, or the researcher may set the number of clusters.
- Cluster feature 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 to set threshold distances, maximum levels, and maximum branches per leaf node manually.
- 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.
- Number of clusters. 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. The researcher can also ask for a range of solutions, such as 3-5 clusters. The "Autoclustering statistics" table in SPSS output gives, for example, BIC and BIC change for all solutions.
  In the example above, by the BIC criterion alone one would select 6 clusters as being optimal. By the SPSS default algorithm, however, 2 clusters are selected because this yields a large BIC ratio of change and a large ratio of distances. In essence, the SPSS algorithm judges that the gain in information from having more than 2 clusters 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.
- SPSS. Choose Analyze, Classify, Two-Step Cluster; select your categorical and continuous variables; if desired, click Plots and select the plots wanted; Click Output and select the statistics wanted (descriptive statistics, cluster frequencies, AIC or BIC); Continue, OK.
  - Options button.
    1. Outlier Treatment.. If there are outliers, click Options and select Outlier Treatment to create a separate outlier cluster. Outliers are identified as cases in a leaf entry containing a fraction (default is 25%) of the cases in the largest leaf node. The "Percent" textbox in the "Outlier Treatment" area of the Options dialog lets the researcher set this fraction. At each step of tree-building, outliers are set aside, then checked for matching when the tree is rebuilt. At the end of the process, remaining outliers are placed in s separate cluster.
    2. Cluster Model Update.. In this group the researcher can import and update a cluster model generated in a prior analysis. The variable names must be selected in the same order in which they were specified in the prior analysis.
    3. Standardization. SPSS by default standardizes all continuous variables. In the Standardization area, the researcher can override this by moving any continuous variable into the "Assumed Standardized" box. See further discussion in the Assumptions section below.
  - Output button.
    1. Statistics. "Descriptives by cluster" gives means and standard deviations for continuous variables and frequencies for categorical variables, by cluster. "Cluster frequencies," if checked, gives cluster frequencies (for the final model). "Information criterion," if checked, gives the Akaike information criterion (AIC) table or Bayesian information criterion (BIC) for a range of solutions if the number of clusters is automatically determined (rather than researcher-mandated, in which case this command is ignored). AIC or BIC is chosen in the main Two-Step Cluster dialog.
      - Cluster distribution table. This SPSS output table simply shows how many cases are in each cluster (here, two 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, automobile-related variables used to classify cars). For formatting reasons, the table below is not in its original form, which is one long horizontal row of variables. This examples shows Cluster 1 has cars with larger, more powerful engines and lower mileage compared to Cluster 2.
      - Frequencies table. This table is the descriptive output for the categorical variables. There is one such table for each categorical variable. The table below shows that American cars tend to be in Cluster 1 and cars of other nations in Cluster 2.
    2. Working Data File. This option lets the researcher save the cluster membership number to the working data file. The variable will be labeled tsc_1 when this is the first save, or a higher digit if a subsequent save in the same operation.
    3. XML Files. Under this option, the researche can export the final cluster model and/or the CF tree. They are exported in XML format. If the CFtree is saved, it can be utilized as the "cluster update" file under the Advanced button of the Options button dialog. If the final model is saved, it can be applied to different datasets using SmartScore and the server version of SPSS.
  - Plots button.
    1. Within-cluster percentage plots are bar charts showing how each categorical variable is split within each cluster. These are generated by selecting "fWithin 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.
      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.
    2. Cluster pie charts show slices indicating the percent and count of observations in each cluster.
    3. Variable importance plots, discussed above, help assess which variables are important in differentiating which clusters. These plots are generated by selecting "Rank of variable importance" under the Plots button. . Relative importance of variables in two-step cluster analysis is shown in a chi-square plot in which the y axis is the set of variables and the x axis is the chi-square value. That is, the variables form the bars, with one plot per cluster. Variables with higher chi-square values than other variables are more important in differentiating that cluster from others. The dialog lets the researcher set the confidence level and the importance measure: (1) chi-square for categorical or t-test for continuous, or (2) significance, which reports one minus the p value for the test of equality of means (continuous variables) or the expected frequency (categorical variables).
      - If in the Plots subdialog, the researcher selects "Rank of variable importance" and then selects "By variable" in the Rank Variables group, the importance plots will still show chi-square on the X axis, but the Y axis will be 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 differentiate Cluster 2, which represents cars with lower engine size, weight, and horsepower, and higher mileage, acceleration, and model year.
        
        The plot below shows that both categorical variables, country and number of cylinders, differentiate the cars in Cluster 2.

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. 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, though two-step clustering can handle categorical data. 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. Independent observations. Also, the log-likelihood distance method used by two-step clustering assumes variables are independent of one another.
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 analysiss, 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).
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 method assumes normal distributions for continuous variables and multinomial distributions for categorical variables.

Frequently Asked Questions

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