I have read some descriptions about agglomerative hierarchical clustering, however, I cannot seem to find an accurate description of the algorithm.

My notes give:

  1. Assign each observation to own single-object cluster. Calculate distances between clusters.
  2. Choose closest pair of clusters and merge them together (amount of clusters reduced by one).
  3. Calculate distance between new and old clusters and replace the merged ones with it.
  4. Repeat Steps 2. and 3. until all observations belong to one cluster (of whole data).

However, I don't really understand step 3.

Does it mean that calculate all distances between clusters?

What does "replace the merged ones with it" mean?


In step (2) you "Choose closest pair of clusters and merge them together".

In step (3) you are essentially computing the inter-cluster distances that will allow you to select which ones to merge next. The horrendous phrasing "Calculate distance between new and old clusters and replace the merged ones with it", I assume, means that you only need to recompute the distances in which the newly merged clusters are involved (i.e. remove the old clusters from your data structure and insert the new one).

Let $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$ be two clusters. There are a few common inter-cluster distance metrics (also called linkage types): \begin{align} d_C(A,B) &= \max_{a,b}\{d(a,b)\;\forall\;a\in A,b\in B\} \tag{Complete} \\ d_S(A,B) &= \min_{a,b}\{d(a,b)\;\forall\;a\in A,b\in B\} \tag{Single} \\ d_A(A,B) &= \frac{1}{mn}\,\sum_{a\in A\\b\in B}\, d(a,b) \tag{Average} \\[2mm] d_E(A,B) &= \frac{2}{mn}\sum_{a\in A\\b\in B}\, d(a,b) - \frac{1}{n^2}\sum_{a,\alpha\in A} d(a,\alpha) - \frac{1}{m^2}\sum_{b,\beta\in B} d(b,\beta)\;\; \tag{Energy} \\[2mm] d_W(A,B) &= \frac{nm}{n+m} \left[ \left(\frac{1}{n}\sum_{a\in A} a\right) - \left(\frac{1}{m}\sum_{b\in B} b\right) \right]^2 \tag{Ward} \end{align} where $d:\mathbb{D}\times\mathbb{D}\rightarrow\mathbb{R}_+$ is a distance metric on the underlying space of the data, such as: \begin{align} d_2(a,b)=||a-b||_2 \;\;\;\;\;\;\;\;\text{ or }\;\;\;\;\;\;\;\; d_\infty(\alpha,\beta)=\max_{i} |\alpha_i - \beta_i| \end{align} assuming $\mathbb{D}=\mathbb{R}^k$.

So step (3) is just computing one of the linkage metrics between the new cluster from (2) and the rest of the clusters.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.