Question $3$

Suppose you have a list of points, i$.$e$.,2$D coordinates, shown in the Table below. Your

goal is to cluster these points into three distinct clusters using the K$-$means algorithm.

Suppose initially we assign A$,$ C$,$ and G as the centers of each cluster, respectively. Use

the Euclidean distance as the distance measure.

Point Name Coordinates

A $(2,10)$

B $(8,4)$

C $(5,8)$

D $(7,5)$

E $(6,4)$

F $(4,9)$

G $(1,2)$

H $(2,5)$

$($a$)$ Show the $3$ clusters, along with their new centers at the first round of iteration of the

K$-$means algorithm. In other words, determine which points will be assigned to each

cluster at the first round of iteration; after that, compute the new centroids $($i$.$e$.,$ centers

of each cluster$).$

$[7$ marks$]$

$($b$)$ Run the K$-$means algorithm until convergence. At each iteration of the algorithm, show

only the $3$ clusters. For this question, you do not need to show derivation steps and

the calculations with the Euclidean distance, just report which points belong to each

cluster at each iteration.

$[10$ marks$]$

$($c$)$ Assume that each point of the above Table further contains a class label. Points A$,$ B

and C belong to class $0$; points D and E belong to class $1$; point E belongs to class

$2$; point F belongs to class $3$; points G and H belong to class $4.$ Assign classes to

the clusters that you found on question $($b$),$ based on the majority value of the class

attribute within each cluster. Discuss a problem which you observe. What would be

the difference if you run K$-$means with $7$ clusters $($K$=7)?$ You do not need to run the

algorithm in this case.