Problem: Manual implementation of K$-$means $(13$ pts$.)$

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

constraints

$($b$)$ Training data set for K$-$means clustering w$/$ constraints

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

Given the data set as shown in Figure $1$ and assume that points A$1,$ A$6$ and A$8$ are chosen to be

the initialized cluster centers. The coordinates of the data points are:

A$1=(0,0),$ A$2=(0,1),$ A$3=(1,2),$ A$4=(2,0),$ A$5=(3,0),$ A$6=(4,1),$ A$7=(4,1),$ A$8=(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 $1$b$.$ Show the new clusters and cluster centers after the first iterations, does the

algorithm converge after the first iteration?