We use the standard notation that we have been using all along:

• \(X_{ik}\) = Response for variable k in sample unit i (the number of individual species k at site i)
• \(n\) = Number of sample units
• \(p\) = Number of variables

Johnson and Wichern list four different measures of association (similarity) that are frequently used with continuous variables in cluster analysis:

Some other distances also use a similar concept.

• Euclidean Distance

  This is used most commonly. For instance, in two dimensions, we can plot the observations in a scatter plot, and simply measure the distances between the pairs of points. More generally we can use the following equation:

  \(d(\mathbf{X_i, X_j}) = \sqrt{\sum\limits_{k=1}^{p}(X_{ik} - X_{jk})^2}\)

  This is the square root of the sum of the squared differences between the measurements for each variable. (This is the only method that is available in SAS. In Minitab there are other distances like Pearson, Squared Euclidean, etc.)

• Minkowski Distance

  \(d(\mathbf{X_i, X_j}) = \left[\sum\limits_{k=1}^{p}|X_{ik}-X_{jk}|^m\right]^{1/m}\)

  Here the square is replaced by raising the difference by a power of m and instead of taking the square root, we take the mth root.

Here are two other methods for measuring association:

• Canberra Metric

  \(d(\mathbf{X_i, X_j}) = \sum\limits_{k=1}^{p}\frac{|X_{ik}-X_{jk}|}{X_{ik}+X_{jk}}\)

• Czekanowski Coefficient

  \(d(\mathbf{X_i, X_j}) = 1- \frac{2\sum\limits_{k=1}^{p}\text{min}(X_{ik},X_{jk})}{\sum\limits_{k=1}^{p}(X_{ik}+X_{jk})}\)

For each distance measure, similar subjects have smaller distances than dissimilar subjects.  Similar subjects are more strongly associated.

Or, if you like, you can invent your own measure! However, whatever you invent, the measure of association must satisfy the following properties:

1. Symmetry

   \(d(\mathbf{X_i, X_j}) = d(\mathbf{X_j, X_i})\)

   i.e., the distance between subject one and subject two must be the same as the distance between subject two and subject one.

2. Positivity

   \(d(\mathbf{X_i, X_j}) > 0\) if \(\mathbf{X_i} \ne \mathbf{X_j}\)

   ...the distances must be positive - negative distances are not allowed!

3. Identity

   \(d(\mathbf{X_i, X_j}) = 0\) if \(\mathbf{X_i} = \mathbf{X_j}\)

   ...the distance between the subject and itself should be zero.
4. Triangle inequality

   \(d(\mathbf{X_i, X_k}) \le d(\mathbf{X_i, X_j}) +d(\mathbf{X_j, X_k}) \)

   This follows from a geometric consideration, that is the sum of two sides of a triangle cannot be smaller than the third side.

In the Woodyard Hammock example, the observer recorded how many individuals belong to each species at each site.  However, other research methods might only record whether or not the species was present at a site.  In sociological studies, we might look at traits that some people have and others do not. Typically 1(0) signifies that the trait of interest is present (absent).

For sample units i and j, consider the following contingency table of frequencies of 1-1, 1-0, 0-1, and 0-0 matches across the variables:

If we are comparing two subjects, subject I, and subject j, then a is the number of variables present for both subjects.  In the Woodyard Hammock example, this is the number of species found at both sites.  Similarly, b is the number (of species) found in subject i but not subject j, c is just the opposite, and d is the number that is not found in either subject.

From here we can calculate row totals, column totals, and a grand total.

Johnson and Wichern list the following Similarity Coefficients used for binary data:

The first coefficient looks at the number of matches (1-1 or 0-0) and divides it by the total number of variables. If two sites have identical species lists, then this coefficient is equal to one because c = b = 0. The more species that are found at one and only one of the two sites, the smaller the value for this coefficient. If no species in one site are found in the other site, then this coefficient takes a value of zero because a = d = 0.

The remaining coefficients give different weights to matched (1-1 or 0-0) or mismatched (1-0 or 0-1) pairs.  For example, the second coefficient gives matched pairs double the weight and thus emphasizes agreements in the species lists. In contrast, the third coefficient gives mismatched pairs double the weight, more strongly penalizing disagreements between the species lists. The remaining coefficients ignore species not found in either site.

The choice of coefficient will have an impact on the results of the analysis. Coefficients may be selected based on theoretical considerations specific to the problem at hand, or so as to yield the most parsimonious description of the data. For the latter, the analysis may be repeated using several of these coefficients. The coefficient that yields the most easily interpreted results is selected.

The main thing is that you need some measure of association between your subjects before the analysis can proceed.  We will look next at methods of measuring distances between clusters.

In the agglomerative hierarchical approach, we define each data point as a cluster and combine existing clusters at each step. Here are four different methods for this approach:

1. Single Linkage: In single linkage, we define the distance between two clusters as the minimum distance between any single data point in the first cluster and any single data point in the second cluster. On the basis of this definition of distance between clusters, at each stage of the process, we combine the two clusters with the smallest single linkage distance.

2. Complete Linkage: In complete linkage, we define the distance between two clusters to be the maximum distance between any single data point in the first cluster and any single data point in the second cluster. On the basis of this definition of distance between clusters, at each stage of the process, we combine the two clusters that have the smallest complete linkage distance.

3. Average Linkage: In average linkage, we define the distance between two clusters to be the average distance between data points in the first cluster and data points in the second cluster. On the basis of this definition of distance between clusters, at each stage of the process we combine the two clusters that have the smallest average linkage distance.

4. Centroid Method: In the centroid method, the distance between two clusters is the distance between the two mean vectors of the clusters. At each stage of the process we combine the two clusters that have the smallest centroid distance.

5. Ward’s Method: This method does not directly define a measure of distance between two points or clusters. It is an ANOVA-based approach. One-way univariate ANOVAs are done for each variable with groups defined by the clusters at that stage of the process. At each stage, two clusters merge that provide the smallest increase in the combined error sum of squares.

In the following table, the mathematical form of the distances is provided. The graph gives a geometric interpretation.

Notationally, define

• \(\boldsymbol{X _ { 1 , } X _ { 2 , } , \dots , X _ { k }}\) = Observations from cluster 1
• \(\boldsymbol{Y _ { 1 , } Y _ { 2 , } , \dots , Y _ { l }}\) = Observations from cluster 2
• d(x,y) = Distance between a subject with observation vector x and a subject with observation vector y

Linkage Methods or Measuring Association d₁₂ Between Clusters 1 and 2

The following video shows the linkage method types listed on the right for a visual representation of how the distances are determined for each method.

The results of cluster analysis are best summarized using a dendrogram. In a dendrogram, distance is plotted on one axis, while the sample units are given on the remaining axis. The tree shows how the sample units are combined into clusters, the height of each branching point corresponding to the distance at which two clusters are joined.

In looking at the cluster history section of the SAS (or Minitab) output, we see that the Euclidean distance between sites 33 and 51 was smaller than between any other pair of sites (clusters). Therefore, this pair of sites were clustered first in the tree diagram. Following the clustering of these two sites, there are a total of n - 1 = 71 clusters, and so, the cluster formed by sites 33 and 51 is designated "CL71". Note that the numerical values of the distances in SAS and in Minitab are different because SAS shows a 'normalized' distance. We are interested in the relative ranking for cluster formation, rather than the absolute value of the distance anyhow.

The Euclidean distance between sites 15 and 23 was smaller than between any other pair of the 70 unclustered sites or the distance between any of those sites and CL71. Therefore, this pair of sites were clustered second. Its designation is "CL70".

In the seventh step of the algorithm, the distance between site 8 and cluster CL67 was smaller than the distance between any pair of unclustered sites and the distances between those sites and the existing clusters. Therefore, site 8 was joined to CL67 to form the cluster of 3 sites designated as CL65.

The clustering algorithm is completed when clusters CL2 and CL5 are joined.

The plot below is generated by Minitab. In SAS the diagram is horizontal. The color scheme depends on how many clusters are created (discussed later).

What do you do with the information in this tree diagram?

We decide the optimum number of clusters and which clustering technique to use. We adapted the wood1.sas program to specify the use of the other clustering techniques. Here are links to these program changes. In Minitab also you may select other options instead of a single linkage from the appropriate box.

As we run each of these programs we must remember to keep in mind that our goal is a good description of the data.

Applying the Cluster Analysis Process

First, we compare the results of the different clustering algorithms. Note that clusters containing one or only a few members are undesirable, as that will give rise to a large number of clusters, defeating the purpose of the whole analysis. That is not to say that we can never have a cluster with a single member! In fact, if that happens, we need to investigate the reason. It may indicate that the single-item cluster is completely different from the other members of the sample and is best left alone.

To arrive at the optimum number of clusters we may follow this simple guideline. Select the number of clusters that have been identified by each method. This is accomplished by finding a breakpoint (distance) below which further branching is ignored. In practice, this is not necessarily straightforward. You will need to try a number of different cut points to see which is more decisive. Here are the results of this type of partitioning using the different clustering algorithm methods on the Woodyard Hammock data.  A dendrogram helps determine the breakpoint.

Cluster Analysis	Linkage Type	Cluster Yield
	Complete Linkage	Partitioning into 6 clusters yields clusters of sizes 3, 5, 5, 16, 17, and 26.
	Average Linkage	Partitioning into 5 clusters would yield 3 clusters containing only a single site each.
	Centroid Linkage	Partitioning into 6 clusters would yield 5 clusters containing only a single site each.
	Single Linkage	Partitioning into 7 clusters would yield 6 clusters containing only 1-2 sites each.

For this example, complete linkage yields the most satisfactory result.

For your convenience, the following screenshots demonstrate how alternative clustering procedures may be done in Minitab.

The next step of cluster analysis is to describe the identified clusters.

Analysis

We perform an analysis of variance for each of the tree species, comparing the means of the species across clusters. The Bonferroni method is applied to control the experiment-wise error rate. This means that we will reject the null hypothesis of equal means among clusters at level \(\alpha\) if the p-value is less than \(\alpha/ p\). Here, \(p = 13\) so for an \(\alpha = 0.05\) level test, we reject the null hypothesis of equality of cluster means if the p-value is less than \(0.05/13\) or \(0.003846\).

Here is the output for the species carcar.

This is an alternative approach for performing cluster analysis. Basically, it looks at cluster analysis as an analysis of variance problem instead of using distance metrics or measures of association.

This method involves an agglomerative clustering algorithm. It will start out at the leaves and work its way to the trunk, so to speak. It looks for groups of leaves that form into branches, the branches into limbs, and eventually into the trunk. Ward's method starts out with n clusters of size 1 and continues until all the observations are included in one cluster.

This method is most appropriate for quantitative variables and not binary variables.

Based on the notion that clusters of multivariate observations should be approximately elliptical in shape, we assume that the data from each of the clusters have been realized in a multivariate distribution. Therefore, it would follow that they would fall into an elliptical shape when plotted in a p-dimensional scatter plot.

Let \(X _ { i j k }\) denote the value for variable k in observation j belonging to cluster i.

Furthermore, we define:

We sum over all variables and all of the units within each cluster. We compare individual observations for each variable against the cluster means for that variable.

The total sums of squares are defined the same as always. Here we compare the individual observations for each variable against the grand mean for that variable.

This \(r^{2}\) value is interpreted as the proportion of variation explained by a particular clustering of the observations.

• Error Sum of Squares: \(ESS = \sum_{i}\sum_{j}\sum_{k}|X_{ijk} - \bar{x}_{i\cdot k}|^2\)  
• Total Sum of Squares: \(TSS = \sum_{i}\sum_{j}\sum_{k}|X_{ijk} - \bar{x}_{\cdot \cdot k}|^2\)    
• R-Square: \(r^2 = \frac{\text{TSS-ESS}}{\text{TSS}}\) 

Using Ward's Method we start out with all sample units in n clusters of size 1 each. In the first step of the algorithm, n - 1 clusters are formed, one of size two and the remaining of size 1. The error sum of squares and \(r^{2}\) values are then computed. The pair of sample units that yield the smallest error sum of squares, or equivalently, the largest \(r^{2}\) value will form the first cluster. Then, in the second step of the algorithm, n - 2 clusters are formed from that n - 1 clusters defined in step 2. These may include two clusters of size 2 or a single cluster of size 3 including the two items clustered in step 1. Again, the value of \(r^{2}\) is maximized. Thus, at each step of the algorithm, clusters or observations are combined in such a way as to minimize the results of error from the squares or alternatively maximize the \(r^{2}\) value. The algorithm stops when all sample units are combined into a single large cluster of size n.

This final method that we would like to examine is a non-hierarchical approach. This method was presented by MacQueen (1967) in the Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.

One advantage of this method is that we do not have to calculate the distance measures between all pairs of subjects. Therefore, this procedure seems much more efficient or practical when you have very large datasets.

Under this procedure, you need to pre-specify how many clusters to consider. The clusters in this procedure do not form a tree. There are two approaches to carrying out the K-Means procedure. The approaches vary as to how the procedure begins the partitioning. The first approach is to do this randomly, which is to start out with a random partitioning of subjects into groups and go from there. The alternative is to start with an additional set of starting points to form the centers of the clusters. The random nature of the first approach avoids bias.

Once this decision has been made, here is an overview of the process:

• Step 1: Partition the items into K initial clusters.
• Step 2: Scan through the list of n items, assigning each item to the cluster whose centroid (mean) is closest. Each time an item is reassigned, we recalculate the cluster mean or centroid for the cluster receiving that item and the cluster losing that item.
• Step 3: Repeat Step 2 over and over again until no more reassignments are made.

Let's look at a simple example in order to see how this works. Here is an example where we have four items and two variables:

Suppose that we initially decide to partition the items into two clusters (A, B) and (C, D). The cluster centroids, or the mean of all the variables within the cluster, are as follows:

For example, the mean of the first variable for cluster (A, B) is 5.

Next, we calculate the distances between item A and the centroids of clusters (A, B) and (C, D).

This is the Euclidean distance between A and each of the cluster centroids. We see that item A is closer to cluster (A, B) than cluster (C, D). Therefore, we are going to leave item A in cluster (A, B) and no change is made at this point.

Next, we will look at the distance between item B and the centroids of clusters (A, B) and (C, D).

Here, we see that item B is closer to cluster (C, D) than cluster (A, B). Therefore, item B will be reassigned, resulting in the new clusters (A) and (B, C, D).

The centroids of the new clusters are calculated as:

Next, we will calculate the distance between the items and each of the clusters (A) and (B, C, D).

It turns out that since all four items are closer to their current cluster centroids, no further reassignments are required.

We must note, however, that the results of the K-means procedure can be sensitive to the initial assignment of clusters.

For example, suppose the items had initially been assigned to the clusters (A, C) and (B, D). Then the cluster centroids would be calculated as follows:

From here we can find that the distances between the items and the cluster centroids are:

 Question

If this is the case, then which result should be used as our summary?

We can compute the sum of squared distances between the items and their cluster centroid. For our first clustering scheme for clusters (A) and (B, C, D), we had the following distances to cluster centroids:

So, the sum of squared distances is:

\(9.\bar{4} + 16.\bar{1} + 0 + 1.\bar{1} = 26.\bar{6}\)

For clusters (A, C) and (B, D), we had the following distances to cluster centroids:

So, the sum of squared distances is:

\(18.25 + 6.25 + 18.25 + 6.25 = 49. 0\)

We would conclude that since \(26.\bar{6} < 49.0\), this would suggest that the first clustering scheme is better and partition the items into the clusters (A) and (B, C, D).

In practice, several initial clusters should be tried and compared to find the best results.  A question arises, however, how should we define the initial clusters?

Now that you have a good idea of what is going to happen, we need to go back to our original question for this method... How should we define the initial clusters? Again, there are two main approaches that are taken to define the initial clusters.

1st Approach: Random assignment

The first approach is to assign the clusters randomly. This does not seem like it would be a very efficient approach. The main reason to take this approach would be to avoid any bias in this process.

2nd Approach: Leader Algorithm

The second approach is to use a Leader Algorithm. (Hartigan, J.A., 1975, Clustering Algorithms). This involves the following procedure:

• Step 1. Select the first item from the list. This item forms the centroid of the initial cluster.
• Step 2. Search through the subsequent items until an item is found that is at least distance δ away from any previously defined cluster centroid. This item will form the centroid of the next cluster.
• Step 3: Step 2 is repeated until all K cluster centroids are obtained or no further items can be assigned.
• Step 4: The initial clusters are obtained by assigning items to the nearest cluster centroids.

The following video illustrates this procedure for k = 4 clusters and p = 2 variables plotted in a scatter plot:

In this lesson we learned about:

• Methods for measuring distances or similarities between subjects
• Linkage methods for measuring the distances between clusters
• The difference between agglomerative and divisive clustering
• How to interpret tree diagrams and select how many clusters are of interest
• How to use individual ANOVAs and cluster means to describe cluster composition
• The definition of Ward's method
• The definition of the K-means method