Methods overview
----------------

Short reference about some linkage methods of **hierarchical agglomerative cluster analysis** (HAC).

Basic version of HAC algorithm is one generic; it amounts to updating, at each step, by the fomula known as Lance-Williams formula, the proximities between the emergent (merged of two) cluster and all the other clusters (including singleton objects) existing so far. There exist implementations not using Lance-Williams formula. But using it is convenient: it lets one code various **linkage methods** by the same template.

The recurrence formula is generic and includes several parameters (alpha, beta, gamma). Depending on the linkage method, the parameters are set differently and so the unwrapped formula obtains a specific view. Many texts on HAC show the formula, its method-specific views and explain the methods. I would recommend articles by Janos Podani as very thorough.

The room and need for the different methods arise from the fact that a proximity (distance or similarity) between two clusters or between a cluster and a singleton object could be formulated in many various ways. HAC merges at each step two most close clusters or points, but how to compute the aforesaid proximity in the face that the input proximity matrix was defined between singleton objects only, is the problem to formulate.

So, the methods differ in respect to how they define proximity between any two clusters at every step. "Colligation coefficient" (output in agglomeration schedule/history and forming the "Y" axis on a dendrogram) is just the proximity between the two clusters merged at a given step.

 - Method of **single** linkage or **nearest neighbour**. Proximity
   between two clusters is the proximity between their two closest
   objects. This value is one of values of the input matrix. The [conceptual metaphor][1] of this built of cluster, its archetype, is *spectrum* or *chain*.
   
 - Method of **complete** linkage or **farthest neighbour**. Proximity
   between two clusters is the proximity between their two most distant
   objects. This value is one of values of the input matrix. The metaphor of this built of cluster is *circle* (in the sense, by hobby or plot).
   
 - Method of **between-group average** linkage (UPGMA). Proximity
   between two clusters is the arithmetic mean of all the proximities
   between the objects of one, on one side, and the objects of the
   other, on the other side. The metaphor of this built of cluster is generic, just united *class*; and the method is frequently set the default one in hierarhical clustering packages.
   
 - **Simple average**, or method of **equilibrious between-group average** linkage (WPGMA) is the modified previous. Proximity between two clusters is the
   arithmetic mean of all the proximities between the objects of one, on
   one side, and the objects of the other, on the other side; while the
   subclusters of which each of these two clusters were merged recently
   have equalized influence on that proximity – even if the subclusters
   differed in the number of objects.
   
 - Method of **within-group average** linkage (MNDIS). Proximity between
   two clusters is the arithmetic mean of all the proximities in their
   joint cluster. This method is an alternative to UPGMA. It usually will lose to it in terms of cluster density, but sometimes will uncover cluster shapes which UPGMA will not.
   
 - **Centroid** method (UPGMC). Proximity between two clusters is the proximity between their geometric centroids: squared euclidean
   distance between those. The metaphor of this built of cluster is *proximity of platforms* (politics); 
   
 - **Median**, or **equilibrious centroid** method (WPGMC) is the modified previous. Proximity between two clusters is the proximity between their geometric
   centroids (squared euclidean distance between those); while the
   centroids are defined so that the subclusters of which each of these
   two clusters were merged recently have equalized influence on its
   centroid – even if the subclusters differed in the number of objects.
   
 - **Ward’s** method, or minimal **increase of sum-of-squares** (MISSQ), sometimes incorrectly called "minimum variance" method. Proximity
   between two clusters is the magnitude by which the summed square in
   their joint cluster will be greater than the combined summed square
   in these two clusters: $SS_{12}-(SS_1+SS_2)$. (Between two singleton objects
   this quantity = squared euclidean distance / $2$.) The metaphor of this built of cluster is *type*.

Some among less well-known methods (see Podany J. New combinatorial clustering methods // Vegetatio, 1989, 81: 61-77.) [also implemented by me as a SPSS macro found on my web-page]:

 - Method of minimal **sum-of-squares** (MNSSQ). Proximity between two
   clusters is the summed square in their joint cluster: $SS_{12}$. (Between
   two singleton objects this quantity = squared euclidean distance /
   $2$.)
   
 - Method of minimal **increase of variance** (MIVAR). Proximity between
   two clusters is the magnitude by which the mean square in their joint
   cluster will be greater than the weightedly (by the number of
   objects) averaged mean square in these two clusters:
   $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$. (Between two
   singleton objects this quantity = squared euclidean distance / $4$.)
   
 - Method of minimal **variance** (MNVAR). Proximity between two
   clusters is the mean square in their joint cluster: $MS_{12} =
   SS_{12}/(n_1+n_2)$. (Between two singleton objects this quantity = squared
   euclidean distance / $4$.).

First 5 methods permit any proximity measures (any similarities or distances).

Last 6 methods require distances; and fully correct will be to use only *squared euclidean distances* with them, because these methods compute centroids in euclidean space. Therefore distances should be euclidean for the sake of geometric correctness. At worst case, you might input other *metric* distances at admitting more heuristic, less rigorous analysis. Now about "squared". Computation of centroids and deviations from them are most convenient mathematically/programmically to perform on squared distances, that's why HAC packages usually require to input and are tuned to process the squared ones. However, there exist implementations - fully equivalent yet a bit slower - based on nonsquared distances input and requiring those; see for example ["Ward-2"][2] implementation for Ward's method. You should consult with the documentation of you clustering program to know which - squared or not - distances it expects in order to do it right.

Methods MNDIS, MNSSQ, and MNVAR require on steps, in addition to just update the Lance-Williams formula, to store a within-cluster statistic (which depends on the method).

Methods which are most frequently used in studies where clusters are expected to be solid more or less round clouds, - are methods of average linkage, complete linkage method, and Ward's method.

Ward's method is the closest, by it properties and efficiency, to K-means clustering; they share the same objective function - minimization of the pooled within-cluster SS "in the end". Of course, K-means (being iterative and if provided with decent initial centroids) is usually a better minimizer of it than Ward. However, Ward seems to me a bit more accurate than K-means in uncovering clusters of uneven sizes (variances) or clusters thrown about space very irregularly. MIVAR method is weird to me, I can't imagine when it could be recommended, it doesn't produce dense enough clusters.

Methods centroid, median, minimal increase of variance – may give sometimes the so-called [reversals][3]: a phenomenon when the two clusters being merged at some step appear closer to each other than pairs of clusters merged earlier. That is because these methods do not belong to so the called ultrametric. This situation is inconvenient but is theoretically OK.

Methods of single linkage and centroid belong to so called space *contracting*, or “chaining”. That means - roughly speaking - that they tend to attach objects one by one to clusters, and so they demonstrate relatively smooth growth of curve “% of clustered objects”. On the contrary, methods of complete linkage, Ward’s, sum-of-squares, increase of variance, and variance commonly get considerable share of objects clustered even on early steps, and then proceed merging yet those – therefore their curve “% of clustered objects” is steep from the first steps. These methods are called space *dilating*. Other methods fall in-between.

**Flexible versions**. By adding the additional parameter into the Lance-Willians formula it is possible to make a method become specifically self-tuning on its steps. The parameter brings in correction for the being computed between-cluster proximity, which depends on the size (amount of de-compactness) of the clusters. The meaning of the parameter is that it makes the method of agglomeration more space dilating or space contracting than the standard method is doomed to be. Most well-known implementation of the flexibility so far is to average linkage methods UPGMA and WPGMA (Belbin, L. et al. A Comparison of Two Approaches to Beta-Flexible Clustering // Multivariate Behavioral Research, 1992, 27, 417–433.).

**Dendrogram.** On a dendrogram "Y" axis, typically displayed is the proximity between the merging clusters - as defined by methods above. Therefore, for example, in centroid method the *squared* distance is typically gauged (ultimately, it depends on the package and it options) - some researches are not aware of that. Also, by tradition, with methods based on *increment* of nondensity, such as Ward’s, usually shown on the dendrogram is *cumulative* value - it is sooner for convenience reasons than theoretical ones. Thus, (in many packages) the plotted coefficient in Ward’s method represents the overall, across all clusters, within-cluster sum-of-squares observed at the moment of a given step. 

To choose the "right" method
----------------------------

There is no *single* criterion. Some guidelines how to go about selecting a method of cluster analysis (including a linkage method in HAC as a particular case) are outlined in [this answer][4] and the whole thread therein.


  [1]: http://stats.stackexchange.com/a/63549/3277
  [2]: http://stats.stackexchange.com/q/109949/3277
  [3]: http://stats.stackexchange.com/q/26769/3277
  [4]: http://stats.stackexchange.com/a/195481/3277