Agglomerative Clustering!!!
A guide to understand Agglomerative clsutering.
Introduction-
Clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters).
Clustering is unsupervised learning because there are no labels for the algorithm to learn and evaluate from and the machine just uses the input data to find the pattern.
There are mainly 3 significant clustering techniques-
1-K-Means
2-Hierarchical clustering
3-DBSCAN.
In this blog,I will mainly focus on one of the types of Hierarchical clustering known as Agglomerative clustering.
Let’s get started with Agglomerative Clustering.
Agglomerative Clustering-
Agglomerative clustering works in a “bottom-up” manner. That is, each point is initially considered as a single-element cluster. At each step of the algorithm, the two clusters that are the most similar are combined into a new bigger cluster. This procedure is iterated until all points are the member of just one single big cluster.
Steps used in Agglomerative clustering-
1-Compute the proximity Matrix(distance/similarity matrix).
2-Let each datapoint be a cluster.
3-Repeat -
a) Merge the two closest clusters.
b)Update the proximity Matrix.
4-Until only a single cluster remains.
Example of Agglomerative clustering based on MAX approach of updating Proximity Matrix-
Let’s there are 6 points P1, P2, P3, P4, P5 & P6 and it is two-dimensional points whose coordinates are as follows-
P1(0.40,0.53),P2(0.22,0.38),P3(0.35,0.32),P4(0.26,0.19),P5(0.08,0.41),
P6(0.45,0.30).
Calculating the Euclidean distance between all the pairs of points and forming the proximity matrix as-
Now find the minimum value in the proximity matrix(closer point).In the above table, it is 0.11. Therefore P3 & P6 will form a cluster.
Update the proximity matrix as follows-
max[dist((P3 ,P6),P1)]=max[dist((P3,P1)),(P6,P1)]=max(0.22,0.23)=0.23
max[dist((P3,P6),P2)]=max[dist((P3,P2),(P6,P2))]=max(0.15,0.25)=0.25
max[dist((P3,P6),P4)]=max[dist((P3,P4),(P6,P4))]=max(0.15,0.22)=0.22
max[dist((P3,P6),P5)]=max[dist((P3,P5),(P6,P5))]=max(0.28,0.39)=0.39
After updating , proximity matrix looks like-
select the minimum value(closer points) from the above proximity matrix. Here it is 0.14. So P2 & P5 will form a cluster.
Again updating the proximity matrix-
max[dist((P2,P5),P1)]=max[dist((P2,P1),(P5,P1))]=max(0.23,0.34)=0.34
max[dist((P2,P5),(P3,P6))]=max[dist((P2,(P3,P6)),(P5,(P3,P6))]=max(0.25,0.39)=0.39
max[dist((P2,P5),P4)]=max[dist((P2,P4),(P5,P4))]=max(0.20,0.29)=0.29
After updating the proximity matrix looks like-
Selecting the minimum value from the above matrix, it is 0.22. So P4 & P3, P6 will form a cluster.
Again updating the proximity matrix-
max[dist(((P3,P6),P4),P1)]=max[dist(((P3,P6),P1),(P4,P1))]=max(0.23,0.37)=0.37
max[dist(((P3,P6),P4),(P2,P5))]=max[dist(((P3,P6),(P2,P5)),(P4,(P2.P5))]=max(0.39,0.29)=0.39
Now the proximity matrix looks like-
Select the minimum value from the above proximity matrix. The minimum value is 0.34. So point P1 & P2, P5 will form a cluster.
Updating the matrix for the final time as -
max[dist (P1,(P2,P5)) , (P3,(P6,P4))]=max[dist (P1,(P3,P6,P4)) , ((P2,P5),(P3,P6,P4))]=max(0.37,0.39)=0.39
The final Proximity matrix looks like-
So finally all the 6 points will form one big cluster.
The dendrogram showing the merging of various points-
Advantages of Agglomerative clustering-
1-Easy to understand and implement.
2- No apriori information about the number of clusters required.
Limitation of agglomerative clustering-
1-Large computational complexity both in time & space.
2-No objective function is directly minimized.
3-Sensitive to outliers.
Thanks for reading!!!!!!!!
Reference-
Wikipedia, AAIC
