Agglomerative clustering algorithm Most popular hierarchical clustering technique Basic algorithm 1. Compute the distance matrix between the input data points 2. Let each data point be a cluster 3. Repeat Merge the two closest clusters Update the distance matrix 6. Until only a single cluster remains Key operation is the computation of the distance between two clusters e Different definitions of the distance between clusters lead to different algorithms
Agglomerative clustering algorithm ◼ Most popular hierarchical clustering technique ◼ Basic algorithm 1. Compute the distance matrix between the input data points 2. Let each data point be a cluster 3. Repeat 4. Merge the two closest clusters 5. Update the distance matrix 6. Until only a single cluster remains ◼ Key operation is the computation of the distance between two clusters ◆ Different definitions of the distance between clusters lead to different algorithms
Input/ Initial setting a Start with clusters of individual points and a distance/proximity matrix 1p2p3p4|p5 3 Distance/ Proximity Matrix p1 p2 p3
Input/ Initial setting ◼ Start with clusters of individual points and a distance/proximity matrix p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . Distance/Proximity Matrix . ... p1 p2 p3 p4 p9 p10 p11 p12