The following matrix shows the pairwise distances between any two points among eight points. (a) [3 marks] Please use the agglomerative approach to group these points with distance group average linkage. Draw the corresponding dendrogram for the clustering.

(b) [2 marks, 4000-enrolment only] Suppose that we want to nd 4 clusters. According to the dendrogram in (a), please state the 4 clusters. For each cluster, please include all data points involved.

(c) [2 marks, 6000-enrolment only] Suppose that data points satisfy the triangle inequality. That is, for any three data points, a, b and c, we have |a,b|+|b,c||a,c| where |a,b| denotes the pairwise distance between a and b. |b,c| and |a,c| have similar meanings. Does the triangle inequality enhance the agglomerative approach? If yes, please elaborate it. If no, please give the reason.

b 11 0 c5 13 0 d122 14 0 e 7 17 1 18 0 f 13 4 15520 0 g9 15 12 16 15 19 0 h 11 20 1221 17 22 30 0 b 11 0 c5 13 0 d122 14 0 e 7 17 1 18 0 f 13 4 15520 0 g9 15 12 16 15 19 0 h 11 20 1221 17 22 30 0