What's the algorithm for agglomerative hierarchical clustering? I have read some descriptions about agglomerative hierarchical clustering, however, I cannot seem to find an accurate description of the algorithm.
My notes give:


*

*Assign each observation to own single-object cluster.
Calculate distances between clusters.

*Choose closest pair of clusters and merge them together
(amount of clusters reduced by one).

*Calculate distance between new and old clusters and replace
the merged ones with it.

*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?
 A: 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.
