Statistical Details

Statistical Details for Hierarchical Clustering

The following description of hierarchical clustering methods gives distance formulas that use the following notation. Lowercase symbols generally pertain to observations and uppercase symbols to clusters.

n is the number of observations

v is the number of variables

xi is the ith observation

CK is the Kth cluster, subset of {1, 2,..., n}

NK is the number of observations in CK

x is the sample mean vector

xK is the mean vector for cluster CK

is the square root of the sum of the squares of the elements of x (the Euclidean length of the vector x)

d(xi, xj) is

Average Linkage

In average linkage, the distance between two clusters is the average distance between pairs of observations, or one in each cluster. Average linkage tends to join clusters with small variances and is slightly biased toward producing clusters with the same variance. See Sokal and Michener (1958).

Distance for the average linkage cluster method is

Centroid Method

In the centroid method, the distance between two clusters is defined as the squared Euclidean distance between their means. The centroid method is more robust to outliers than most other hierarchical methods but in other respects might not perform as well as Ward’s method or average linkage. See Milligan (1980).

Distance for the centroid method of clustering is

Ward’s

In Ward’s minimum variance method, the distance between two clusters is the ANOVA sum of squares between the two clusters added up over all the variables. At each generation, the within-cluster sum of squares is minimized over all partitions obtainable by merging two clusters from the previous generation. The sums of squares are easier to interpret when they are divided by the total sum of squares to give the proportions of variance (squared semipartial correlations).

Ward’s method joins clusters to maximize the likelihood at each level of the hierarchy under the assumptions of multivariate normal mixtures, spherical covariance matrices, and equal sampling probabilities.

Ward’s method tends to join clusters with a small number of observations and is strongly biased toward producing clusters with approximately the same number of observations. It is also very sensitive to outliers. See Milligan (1980).

Distance for Ward’s method is

Single Linkage

In single linkage the distance between two clusters is the minimum distance between an observation in one cluster and an observation in the other cluster. Single linkage has many desirable theoretical properties. See Jardine and Sibson (1976), Fisher and Van Ness (1971), and Hartigan (1981). Single linkage has, however, fared poorly in Monte Carlo studies. See Milligan (1980). By imposing no constraints on the shape of clusters, single linkage sacrifices performance in the recovery of compact clusters in return for the ability to detect elongated and irregular clusters. Single linkage tends to chop off the tails of distributions before separating the main clusters. See Hartigan (1981). Single linkage was originated by Florek et al. (1951a, 1951b) and later reinvented by McQuitty (1957) and Sneath (1957).

Distance for the single linkage cluster method is

Complete Linkage

In complete linkage, the distance between two clusters is the maximum distance between an observation in one cluster and an observation in the other cluster. Complete linkage is strongly biased toward producing clusters with approximately equal diameters and can be severely distorted by moderate outliers. See Milligan (1980).

Distance for the Complete linkage cluster method is

Fast Ward

is a way of applying Ward's method more quickly for large numbers of rows. It is used automatically whenever there are more than 2000 rows.

Statistical Details for Robust Estimation Methods

Normal Mixtures uses the EM algorithm to do fitting because it is more stable than the Newton-Raphson algorithm. Additionally we are using a Bayesian regularized version of the EM algorithm, which allows us to smoothly handle cases where the covariance matrix is singular. Since the estimates are heavily dependent on initial guesses, the platform will go through a number of tours, each with randomly selected points as initial centers.

Doing multiple tours makes the estimation process somewhat expensive, so considerable patience is required for large problems. Controls enable you to specify the tour and iteration limits.

Additional Details for Robust Normal Mixtures

Because Normal Mixtures is sensitive to outliers, JMP offers an outlier robust alternative called Robust Normal Mixtures. This uses a robust method of estimating the normal parameters. JMP computes the estimates via maximum likelihood with respect to a mixture of Huberized normal distributions (a class of modified normal distributions that was tailor-made to be more outlier resistant than the normal distribution).

The Huberized Gaussian distribution has pdf

So, in the limit as k becomes arbitrarily large,

tends toward the normal PDF. As

tends toward the exponential (Laplace) distribution.

The regularization parameter k is set so that P(Normal(x) < k) = Huber Coverage, where Normal(x) indicates a multivariate normal variate. Huber Coverage is a user field, which defaults to 0.90.