$1\mathrm{.}2$ Problem: Manual implementation of K$-$means $(13$ pts$.)$

$>$

$^x$

$($a$)$ Training data set for K$-$means clustering w$/$o $($b$)$ Training data set for K$-$means clustering w$/$ conconstraints straints

Figure $1$: Manual implementation of K$-$means

Given the data set as shown in Figure $1$ and assume that points $A1,A6$ and $A8$ are chosen to be the initialized cluster centers. The coordinates of the data points are:

$A1=(0,0),A2=(0,1),A3=(-1,2),A4=(2,0),A5=(3,0),A6=(4,-1),A7=(4,1),A8=(5,3)$

$(1)$ Use the K$-$means algorithm and Euclidean distance to cluster the $8$ data points shown in $1$a into $K=3$ clusters. Show the new clusters $($i$.$e$.$ the examples belonging to each cluster$)$ and cluster centers after the first iterations, does the algorithm converge after the first iteration?

$(2)$ Consider the case that there exist $1$ must link $($solid orange line$)$ and $1$ cannot link $($dashed red line$)$ as shown in $1b.$ Show the new clusters and cluster centers after the first iterations, does the algorithm converge after the first iteration?