Hierarchical clustering
Section of Hierarchical clustering and kernel density estimation, part of Statistical learning
Hierarchical clustering
| Type | Section |
| Taught in | Hierarchical clustering and kernel density estimation |
| Part | Statistical learning |
| Questions using it | 2 |
A hierarchy gives nested partitions, from single observations to the whole sample. Start by choosing a meaningful dissimilarity and its scale. Standardising variables is one possible choice of scale. Use it when the measurement units would otherwise dominate the distances. Then choose how to compare groups using their pointwise dissimilarities. Once ties are resolved, the merge rule determines the tree. K-means clustering instead fixes the number of clusters in advance and returns a single partition that minimises a within-cluster sum of squares; Ward’s linkage applies the same criterion one merge at a time.
The original vectors are not required. Edit distance between words, or between languages, counts insertions, deletions, and substitutions. The same counting compares genetic sequences. People can be clustered from the strength of a relationship, and sites from an ecological similarity, with no coordinates in sight. Single linkage and complete linkage, defined below, use only those pairwise numbers.
Agglomerative and divisive clustering
Main article: Agglomerative and divisive clustering
Agglomerative clustering starts with each observation alone and merges neighbouring clusters until one cluster remains. Divisive clustering starts with one cluster and splits until every observation is alone. Either way the hierarchy has n levels, counting the single cluster at the top, and n leaves. The picture of the hierarchy is a dendrogram. Agglomerative clustering is the usual choice because the first merges are between points, where the dissimilarity is already defined. A divisive step has to invent a split of a set.
The pointwise dissimilarity may be Euclidean distance, or any other dissimilarity d(x,y). The arguments may be observation vectors or summaries such as cluster means, when the linkage uses means.
Start with n singleton clusters. At each step, find the two closest clusters under the chosen inter-cluster distance, called a linkage, and merge them. Record the distance at which each merge occurs. Stop when one cluster remains.
The first merge compares points, so d applies directly. Every later merge compares sets. A linkage extends d from points to pairs of clusters D_1 and D_2. Three rules are used here. They answer different questions about what makes two sets close.
Definition 1 (Single, complete, and average linkage) Single linkage, or nearest neighbour, takes the distance between the closest pair with one point in each cluster,
d_S(D_1,D_2)=\min\{d(x,y):x\in D_1,\, y\in D_2\}.
The clusters are close as soon as they touch.
Complete linkage, or furthest neighbour, takes the distance between the farthest pair,
d_C(D_1,D_2)=\max\{d(x,y):x\in D_1,\, y\in D_2\}.
A merge is cheap only when every cross pair is close.
Average linkage, in the group-average sense, takes the mean of all cross pairs,
d_A(D_1,D_2)=\frac{1}{|D_1|\,|D_2|}\sum_{x\in D_1}\sum_{y\in D_2}d(x,y),
where |\cdot| is the cardinality of the multiset. Clusters are allowed to be multisets so that duplicate points are legal.
Averaging distances and taking the distance between averages are different operations. The display is group-average linkage. Distance between centroids defines centroid linkage. In R, hclust(method = "average") implements group-average linkage. Centroid linkage can produce inversions, in which a later merge has a smaller height.
Properties of the linkages
Main article: Properties of the linkages
Read each linkage as a different question. Single linkage asks whether any cross-pair is close, so a chain of nearby points can connect distant ends. Complete linkage asks whether every cross-pair is close, discouraging large diameters. Average linkage asks about the typical cross-pair. These criteria suggest tendencies. Spherical clusters and equal cluster sizes are further claims.
The partition can change substantially when a new sample is drawn from the same distribution, or when n changes. Single linkage shows this as chaining. A gap that separates two groups at one sample size can contain points when n is larger, and the linkage then joins the groups at the height of the closest new pair across the gap. Complete linkage is sensitive to distant outliers: one far point raises the maximum pairwise distance and can block a merge of clusters that are otherwise close. Average linkage lies between those two behaviours. No linkage is the most stable under every contamination pattern and every cluster shape. Single and complete linkage need only the pairwise dissimilarities. A linkage that uses means also needs an average of points, which may not exist for the dissimilarities of the previous section.
Example 1 (Chaining on six points) Question. Cluster the one-dimensional points 0,1,2.1,3.3,4.6,6.9 by single and complete linkage.
Solution. The gaps between neighbours are 1, 1.1, 1.2, 1.3, 2.3.
Single linkage merges \{0\} with \{1\} at 1.0. It then merges \{0,1\} with \{2.1\} at 1.1, because the nearest points across those sets are 1 and 2.1. It merges the result with \{3.3\} at 1.2, with \{4.6\} at 1.3, and finally with \{6.9\} at 2.3. The tree is a chain: each point is attached to the growing cluster through its nearest neighbour, and the merge heights are exactly the neighbour gaps 1.0,1.1,1.2,1.3,2.3.
Complete linkage makes the first merge \{0,1\} at 1.0 again. The next smallest distance is 1.2, between 2.1 and 3.3, so \{2.1,3.3\} forms at 1.2. Then \{4.6,6.9\} forms at 2.3. The union \{0,1\}\cup\{2.1,3.3\} has maximum cross distance 3.3-0=3.3. The two halves then merge at 6.9-0=6.9. Complete linkage finds three pairs and then joins those pairs. Single linkage finds a chain, with a possible split of 6.9 from the rest.
Average linkage, included for the comparison, has merge heights 1.0, 1.2, 1.9, 2.83, 4.7. The first two are the same pairs as complete linkage: \{0,1\} at distance 1.0, and \{2.1,3.3\} at distance 1.2. The distance from \{2.1,3.3\} to \{4.6\} is the mean of 4.6-2.1=2.5 and 4.6-3.3=1.3, which is 1.9, and that is the third merge. The six cross distances from \{0,1\} to \{2.1,3.3,4.6\} are 2.1,3.3,4.6,1.1,2.3,3.6, with mean 17/6=2.833, recorded as 2.83. The last merge attaches 6.9. Its distances to the five points already joined are 6.9,5.9,4.8,3.6,2.3, with mean 23.5/5=4.7.
Divisive clustering
Main article: Divisive clustering
Agglomerative clustering fixes the small merges first, and every later merge inherits those decisions. Divisive clustering starts from the whole sample, so the first split is a decision about the large-scale partition. One standard rule selects the cluster of largest diameter, the maximum distance between two of its members, and moves aside the observation whose average distance to the other members is largest. The move continues until transferring another observation no longer increases the separation of the two sides. Categorical variables enter mainly through the choice of dissimilarity, for example Gower’s distance. If one partition is required, the dendrogram can be cut at a single height. The dendrogram itself remains the object the method was built to show: every nested partition at once.
A dendrogram is also a record of irreversible decisions: later merges cannot undo earlier ones. A horizontal cut chooses one partition from that record. Compare nearby cuts and inspect the observations around the large jumps before attaching a scientific interpretation to one level.
The fragment standardises columns, computes distances between rows, and cuts an average-linkage tree into three groups. Keeping the distances fixed while changing the linkage isolates the effect of the merge rule.
d <- dist(scale(x)) # Euclidean distances between standardised rows
hc <- hclust(d, method = "average") # or "single", "complete"
plot(hc) # the dendrogram
cutree(hc, k = 3) # cut the tree into 3 clustersUsed in
See also
Average linkage · Complete linkage · Dendrogram · Single linkage · Ward’s method · Single, complete, and average linkage · Kernel density estimator · Agglomerative and divisive clustering