Dendrogram
Topic of Hierarchical clustering and kernel density estimation, part of Statistical learning · Also in Hierarchical clustering and kernel density estimation
Dendrogram
| Type | Topic |
| Taught in | Hierarchical clustering and kernel density estimation · Hierarchical clustering and kernel density estimation |
| Part | Statistical learning |
| Questions using it | 2 |
The tree diagram of a hierarchical clustering: leaves are observations, and each join is drawn at the dissimilarity at which two clusters merged. Cutting it at one height gives a partition. The heights belong to the linkage rule and the sample, not to any probability model.
In Hierarchical clustering and kernel density estimation
Both outputs depend on scale and on a tuning choice. A height in a dendrogram is the linkage dissimilarity at which two clusters merged. It is a feature of that merge rule on this sample. A peak in a density estimate is a feature of the smoothed distribution. Reading either display as a posterior probability that those clusters are the groups which generated the sample is a further claim, and the constructions below do not supply it.
In Hierarchical clustering and kernel density estimation, continued
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
- Taught in Hierarchical clustering and kernel density estimation · Hierarchical clustering and kernel density estimation
- Questions that use it (2) — Linkage by hand · Number of merges (answer)
- All 6 questions on Hierarchical clustering and kernel density estimation
See also
Hierarchical clustering · Single, complete, and average linkage · Kernel density estimator · Agglomerative and divisive clustering · Properties of the linkages · Divisive clustering · Kernel density estimation · Choosing the bandwidth