3. Hierarchical Clustering

Hierarchical Clustering

Hierarchical clustering results in a series of clustering results:

• the results start off with each object in their own cluster and end with all of the objects in the same cluster
• the intermediate clusters are created by a series of merges
• the resultant tree-like structure is called a dendrogram

You build a binary tree of the data that successively merges similar groups of points, visualising this tree provides a useful summary of the data.

This resolves an issue with flat clustering (k-Means) where structure is lost.

Link to original

Algorithm

To perform hierarchical clustering:

1. Start by assigning each item to a cluster. ($n$ items = $n$ clusters)
   1. Set distances between clusters the same as the distances between the items they contain
2. Find the closest pair of clusters and merge them into a single cluster
3. Recalculate distances between the new cluster and each of the old clusters
4. Repeat steps $2$ and $3$ until all items are clustered into a single cluster of size $n$.

Advantages and Disadvantages

Advantages	Disadvantages
Hierarchies of similar objects are produced, which is informative for particular applications	Not efficient
Do not require information regarding number of clusters	Once a decision to combine two clusters is made, it cannot be undone
Any designed number of clusters can be obtained by ‘cutting’ the dendrogram at a chosen level	Use of different distance metrics for measuring between clusters may generate different results (or they just aren’t useful)

Example

We can determine clusters by slicing through the dendrogram at a desired level:

This produces 3 clusters: $(BA,NA,RM),(FI),(MI,TO)$