Agglomerative and divisive clustering
Section of Hierarchical clustering and kernel density estimation, part of Statistical learning
Agglomerative and divisive clustering
| Type | Section |
| Taught in | Hierarchical clustering and kernel density estimation |
| Part | Statistical learning |
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.
Used in
See also
Single, complete, and average linkage · Kernel density estimator · Hierarchical clustering · Properties of the linkages · Divisive clustering · Kernel density estimation · Choosing the bandwidth · Bias and variance in one bandwidth