MerQuR+Statistics Glossary

Statistics Glossary → Hierarchical Clustering

Hierarchical Clusteringanalysis

An exploratory grouping method that merges observations step by step, starting with the most similar, to build a tree (dendrogram), and obtains clusters by cutting this tree at the desired level.

Concept

Hierarchical clustering aims to show the whole similarity structure among observations when the number of clusters is not known in advance. Instead of a single partition it produces a nested sequence of clusters: at the bottom each observation is a cluster of its own, at the top all observations are gathered into one. This structure is drawn as a dendrogram, resembling a family tree, which shows at a glance how close the observations are to one another.

In the agglomerative (bottom-up) approach, the distances between all pairs of observations are computed first. At each step the two closest clusters are merged and the distance from the new cluster to the others is updated according to the linkage method: single linkage looks at the closest pair of members, complete linkage at the farthest, average linkage at the mean of all pairs, while Ward's method picks the merge that least increases the within-cluster sum of squares. The merge height in the dendrogram shows how different the merged clusters are; a sudden jump in height indicates that very different clusters were joined and that the tree should be cut below that level.

A merge is never undone later; a poor merge at an early step affects the whole tree. The result depends heavily on the distance measure, the linkage method and the scaling of the variables; single linkage tends to produce long chains, Ward balanced and rounded clusters. Because the whole distance matrix is stored, the method is heavy on very large datasets. The cophenetic correlation shows how well the tree reflects the original distances; where to cut the tree should be decided together with subject knowledge and criteria for the number of clusters.

When to use it

  • When there is no prior idea of the number of clusters and the nested similarity structure among observations (or variables) is of interest, especially with a moderate number of observations (below a few thousand).
  • If the number of clusters is roughly known and there are many observations, K-means is faster; clusters found with Ward's method can also serve as the starting point for K-means.
  • If clusters are not spherical, or outliers are to be set aside as noise, DBSCAN/HDBSCAN is preferred; if membership probabilities and model comparison are needed, latent profile analysis.

An everyday example

An agricultural researcher wants to group 30 local tomato varieties collected from villages by fruit weight, sugar content, acidity and ripening time. Hierarchical clustering first joins the two most similar varieties, then the next most similar pair, and so on, until all the varieties sit in a dendrogram resembling a family tree. Looking at the tree, the researcher may see that the varieties first split into two large branches, 'large, sweet table tomatoes' and 'small, sour paste tomatoes', and that the table tomatoes divide further into early and late ripeners.

Parameters in MerQur

Number of clusters (K)

Concept: Hierarchical clustering produces the whole sequence of merges as a tree; K sets the height at which the tree is cut and so how many clusters result. Changing K changes only the cutting level, not the tree.

Everyday example: Once the tomato tree has been built, the researcher can cut it into two clusters (table and paste) or four (early and late table tomatoes plus two kinds of paste tomato). Which variety joined which first is the same in both cases.

What it does: Into how many clusters the tree is cut (does not change the tree itself).

Effect on the result: Only the cut and the dependent cluster sizes, silhouette and CH change; the tree and the merge coefficients do not change.

On the validation data: (USArrests): For K = 2, 3, 6 the cluster sizes are 19/31, 12/19/19, 4/4/7/8/12/15; silhouette 0.4048, 0.3104, 0.2617.

→ Choosing the number of clusters

Linkage method (Ward / Complete / Average / Single / Centroid / Median / McQuitty)

Concept: The linkage method defines the 'distance' between two clusters that contain several observations. Single linkage looks at the two closest members, complete linkage at the two farthest, average linkage at the mean over all pairs of members; Ward's method measures how much a merge increases the within-cluster sum of squares.

Everyday example: When deciding whether to merge two groups of tomatoes, single linkage asks 'how close are the two most similar varieties in the two groups?' and merges them if even one similar pair exists, so chain-like clusters can form. Ward asks 'how mixed does the group become once merged?' and produces tidy groups of similar size.

What it does: The distance between two clusters: Ward (smallest increase in within-cluster SS at merging; height on the √(2·ΔSS) scale), complete (farthest pair), average (UPGMA), single (nearest pair), centroid, median, McQuitty (WPGMA).

Effect on the result: The shape of the tree, the merge heights and the K cut change; single linkage tends to chain, Ward to balanced clusters.

On the validation data: (USArrests z, K = 3): Ward 12/19/19; complete 8/11/31; average 1/19/30; single 1/1/48; centroid 1/19/30; median 1/7/42; McQuitty 7/13/30. With the default setting the last merge coefficient is 13.5162.

→ Linkage method (Ward, complete, average, single)

Missing Data

Concept: Either removes observations with missing measurements from the analysis or fills the missing value with the mean, the median or an estimate from the most similar observations. In hierarchical clustering every observation is a branch of the tree, so this choice also affects the tree's structure.

Everyday example: If the ripening time of two varieties was not recorded, the delete option leaves these varieties out of the tree altogether. With KNN filling, the missing time is estimated from the average of the five varieties most similar in their other measurements, and the varieties stay in the tree.

What it does: Drops rows with missing values or imputes them on the raw scale with the mean, median or 5 nearest neighbours; the transformation is applied after imputation.

Effect on the result: n and therefore the tree and all results change.

On the validation data: (airquality, Ward z): n = 111, 153, 153, 153; K = 3 sizes 23/38/50, 26/33/94, 25/56/72, 35/53/65.

→ Single imputation (mean, median, kNN filling)

Distance measure (Euclidean / Squared Euclidean / Manhattan / Chebyshev / Pearson correlation (1 - r) / Cosine (1 - cos) / Jaccard / Gower)

Concept: The distance measure defines how different two observations count as being: Euclidean is the straight-line distance, Manhattan the sum of absolute differences, Chebyshev the largest single difference; correlation and cosine distances look at the shape of the profile rather than the size of the values, Jaccard suits binary variables and Gower variables of mixed type.

Everyday example: With Euclidean distance, a large sweet variety and a small but proportionally just as sweet variety end up far apart. Correlation distance asks whether the two varieties' traits follow the same 'pattern'; if their profiles are proportionally alike, it may count them as close.

What it does: The distance between observations. For non-Euclidean measures average, complete, single and McQuitty linkage can be used.

Effect on the result: The distance matrix and therefore the tree, heights and clusters change.

On the validation data: (USArrests z, average linkage, K = 3): Manhattan 7/12/31; Chebyshev 1/18/31; 1 - r 9/20/21; 1 - cosine 1/23/26; Gower 7/12/31. With squared Euclidean and average linkage the root mean square (RMS) distance is the square root of the merge coefficient; in the Poverty data the divisor of the normalized RMS distance is 20.25399. Jaccard converts a two-valued code other than 0/1 to 0/1 and adds a note.

→ Distance measure (Euclidean, Manhattan, Gower, great-circle)

Print the proximity matrix (n <= 100)

Concept: The proximity matrix is the table of distances between every pair of observations and is the raw information on which the tree is built. Looking at it shows directly how close particular pairs of observations are.

Everyday example: If the researcher wonders whether two varieties collected from the same village really are very alike, they look at the cell for this pair in the matrix; if the distance is very small, the two 'varieties' may in fact be two names for the same one.

What it does: Writes the distance matrix between observations to the results (at most 100 observations).

Effect on the result: The results do not change; a distance table is added.

On the validation data: For USArrests the 1225 lower-triangle cells of the 50 x 50 matrix are printed (z with the n - 1 denominator).

→ Distance measure (Euclidean, Manhattan, Gower, great-circle)

Save cluster membership

Concept: Adds to the dataset the cluster number given to each observation when the tree is cut at the chosen K. The clusters can then be used as a grouping variable in later analyses (e.g. comparing clusters).

Everyday example: A number such as 'cluster 1: table' or 'cluster 2: paste' is written next to each tomato variety. The researcher can later examine in a separate analysis whether these clusters differ in disease resistance.

What it does: The K-cut cluster numbers (0-based, in order of first appearance) are added to the dataset.

Effect on the result: The results do not change; a cluster column is added to the dataset.

On the validation data: USArrests (z, Ward, K = 3): the cluster number of each row is added to the data set; cluster sizes 12/19/19.

Variable transformation

Concept: If the variables were measured in different units or over very different ranges, the one with the widest range dominates the distances. A transformation (e.g. the z-score) brings the variables onto a common scale and lets each take part in the tree with similar weight.

Everyday example: If fruit weight ranges from 20 to 400 grams and acidity from pH 3.9 to 4.6, an untransformed analysis builds the tree almost entirely on weight. After z-scoring, differences in acidity also have a say in how the varieties are grouped.

What it does: Brings the variables to a common scale: z-score (n-1), none, range 0-1, maximum = 1, SD = 1.

Effect on the result: The distances and the tree change; without transformation the large-scale variable (Assault) dominates.

On the validation data: (Ward): none 700.8786 (14/16/20); range 3.6297 (12/18/20); maximum 3.2338 (13/17/20); sd 13.5162 (12/19/19).

→ z-score (standardization)

K-selection criteria table

Concept: The cophenetic correlation is the correlation between the original distances between observations and the heights at which they join in the dendrogram; close to 1, the tree summarises the data well. R², semi-partial R², pseudo F and pseudo t² show how well the clusters are separated at different numbers of clusters and how much information a merge loses.

Everyday example: If the cophenetic correlation is 0.85, varieties that look close in the tree really are close in their measurements. If the semi-partial R² jumps when going from four clusters to three, two very different groups are being forced together, and four clusters look more appropriate.

What it does: Cophenetic correlation and the number-of-clusters criteria (semi-partial R², R², pseudo F, pseudo t²).

Effect on the result: The tree does not change; a table that helps to choose the number of clusters is added.

On the validation data: USArrests Ward cophenetic r 0.6975; k = 3: R² 0.5979, pseudo F 34.937, pseudo t² 14.555. In the Poverty data RSQ, SPRSQ, pseudo F and pseudo t² are reported for average, complete and single linkage. In iris Ward, for k = 5-10 the order in which equal-distance merges (ties) are resolved affects the tree.

→ Choosing the number of clusters

Chart, Dendrogram cut, Membership range (k = 2..), Cluster variables (Additional output)

Concept: The dendrogram shows the merge order and heights, the PCA plane the clusters in two dimensions, and the silhouette plot how well each observation fits its cluster. The membership range gives memberships for several values of K together; variable clustering groups not the observations but variables that are highly correlated with one another.

Everyday example: With the membership range, the researcher sees side by side which groups a variety falls into in the 2-, 3- and 4-cluster cuts. Variable clustering might show something like 'sugar content and ripening time vary together, while acidity is a separate dimension'.

What it does: Dendrogram, PCA plane or observation silhouette chart; membership range k = 2..k_max; clustering of variables by 1 - r distance (average linkage).

Effect on the result: The tree and the cut do not change; plots, the membership range and the variable tree are given as additional output.

On the validation data: Membership k = 2..5: 19/31, 12/19/19, 7/12/12/19, 4/7/12/12/15. USArrests variable clustering (1 - r distance, average linkage): heights 0.19813, 0.38559, 0.75340; clusters {Murder, Assault}, {UrbanPop}, {Rape}. The chart types change only the drawing.

→ Dendrogram and cophenetic correlation

Example on real data

Data: McNeil 1977, R datasets USArrests (50 states)

Variables: features Murder, Assault, UrbanPop, Rape (crime rates and urban population in 50 states)

  • Question: How are the 50 states grouped hierarchically on four z-scored crime/urbanization indicators, and what does a three-cluster cut give?
  • Setup: Euclidean distance, Ward linkage (at each step the two clusters with the smallest increase in within-cluster SS are merged), K = 3 cut.
  • Result: The last three merge coefficients are 6.4619, 7.1882 and 13.5162; the large jump at the last step (from 7.19 to 13.52) points to a two- or three-cluster structure. The K = 3 cut gives clusters of 19, 19 and 12 states.
  • Cluster quality: Mean silhouette 0.3104 and Calinski-Harabasz 34.9365; a moderately separated clustering.
  • Descriptive: One 19-state cluster has high crime (Murder mean 12.33, Assault 259.3), the other 19 states have medium crime and high urbanization, and 12 states have low crime and low urbanization; the solution is very close to the k-means solution.
  • Limitation: The Ward tree never undoes a merge; the merge coefficient is reported on the √(2·ΔSS) scale, so the scale conversion should be kept in mind when interpreting it as cumulative SS or semi-partial R².
  • APA: Ward hierarchical clustering on z-scores (Euclidean) was cut into three clusters (n = 19, 19, 12); mean silhouette = .31, Calinski-Harabasz = 34.94.

Related concepts

Linkage method (Ward, complete, average, single)Dendrogram and cophenetic correlationChoosing the number of clustersDistance measure (Euclidean, Manhattan, Gower, great-circle)Silhouette coefficientPartial and semi-partial correlationz-score (standardization)Single imputation (mean, median, kNN filling)

The numbers in the examples are MerQur's output on independent, publicly available validation data; see the MerQur Technical Note for details.