$4.$ Clustering $(17$ marks$)$

Consider the following data set.

x$1=$

$1$

$2$

$,$ x$2=$

$1$

$1$

$,$ x$3=$

$2$

$2$

$,$ x$4=$

$3$

$3$

$,$ x$5=$

$3$

$0$

$,$ x$6=$

$4$

$1$

$.$

$($a$)$ Describe two differences between the K$-$Means algorithm and the Agglomerative Hierarchical Clustering $($AHC$)$ algorithm. $[4$ marks$]$

$($b$)$ Compute the complete linkage between the two clusters $\{$x$1,$ x$4\}$ and $\{$x$5,$ x$6\}.$

$[4$ marks$]$

$($c$)$ In the lectures, we discussed a potential function which can be used to compare different cluster assignments. Given a cluster assignment, how do you

compute its potential function value? $[3$ marks$]$

$($d$)$ Use the potential function to determine which of the following two cluster

assignments is better.

$$ Cluster Assignment $1$: $\{$x$1,$ x$2,$ x$4\},\{$x$3,$ x$5,$ x$6\}.$

$$ Cluster Assignment $2$: $\{$x$1,$ x$2\},\{$x$3,$ x$4,$ x$5,$ x$6\}.$

$[6$ marks$]$