0
2.0kviews
What is Clustering Technique ? Discuss the Agglomerative algorithm with the following data and plot a Dendrogram using single link approach.

The table below comprises sample data items indicting the distance between the elements.

Item E A C B D
E 0 1 2 2 3
A 1 0 2 5 3
C 2 2 0 1 6
B 2 5 1 0 3
D 3 3 6 3 0
0
110views

Agglomerative Clustering Technique:

In Hierarchical clustering algorithms, either top down or bottom up approach is followed. In Bottom up approach, every object is considered to be a cluster and in subsequent iterations they are merged into single cluster. Therefore it is also called as Hierarchical Agglomerative Clustering.

An HAC clustering is typically visualised as a dendrogram , where each merge is represented by a horizontal line.

Flowchart:

Numerical:

Given:

Distance matrix:

Step 1: From above given distance matrix, E and A clusters are having minimum distance, so merge them together to form cluster(E,A).

Distance matrix:

\begin{aligned} \text{dist((E A), C)} &= \text{MIN(dist(E,C), dist(A,C))} \\ &= \text{MIN(2,2)} \\ &= 2 \\ \text{} \\ \text{dist((E A), B)} &= \text{MIN(dist(E,B), dist(A,B))} \\ &= \text{MIN(2,5)} \\ &= 2 \\ \text{} \\ \text{dist((E A), D)} &= \text{MIN(dist(E,D), dist(A,D))} \\ &= \text{MIN(3,3)} \\ &= 3 \\ \end{aligned}

Step 2: Consider the distance matrix obtained in step 1. Since B,C distance is minimum, we combine B and C.

\begin{aligned} \text{dist((B C), (E A))} &= \text{MIN(dist(B,E), dist(B,A), dist(C E), dist(C A))} \\ &= \text{MIN(2,5, 2, 2)} \\ &= 2 \\ \text{} \\ \text{dist((B C), D)} &= \text{MIN(dist(B, D), dist(C,D))} \\ &= \text{MIN(3,6)} \\ &= 3 \\ \end{aligned}

Step 3: Consider the distance matrix obtained in step 2. Since (E,A) and (B,C) distance is minimum, we combine them

\begin{aligned} \text{dist((E A), (B C))} &= \text{MIN(dist(E,B), dist(E,C), dist(A B), dist(A C))} \\ &= \text{MIN(2, 2, 2, 5, 2)} \\ &= 2 \\ \end{aligned}

Step 4: Finally combine D with (E A B C)