Problem $2$

$[40$ pts$][$K$-$Means$]$ Given the matrix $x$ whose rows represent different data points, you are asked to perform a $k-$means clustering on this dataset using the Euclidean distance as the distance function. Here $k$ is chosen as $3.$ The Euclidean distance $d$ between a vector $x=[x_1,x_2,$dots,$x_p{]}^T$ and a vector $y=[y_1,y_2,$dots,$y_p{]}^T$ both in $R^p$ is defined as $d=\sqrt[\phantom{2}]{{\displaystyle \underset{i=1}{\overset{p}{}}}(x_i-y_i{)}^2}.$ All data in $x$ were plotted in Figure $1($black$,$ red, blue, and green points$).$ We randomly choose the following $3$ points as the initialized centers of $3$ clusters which are ${}_1=(5\mathrm{.}8,3\mathrm{.}0)($red$),{}_2=(6\mathrm{.}2,3\mathrm{.}0)($blue$),{}_3=(6\mathrm{.}5,3\mathrm{.}5)($green$).$

$x=\left[\begin{array}{c}{x}_1^T\\ x_2^T\\ x_3^T\\ x_4^T\\ x_5^T\\ x_6^T\\ x_7^T\\ x_8^T\end{array}\right]=\left[\begin{array}{cc}4\mathrm{.}0& 3\mathrm{.}5\\ 3\mathrm{.}5& 3\mathrm{.}0\\ 5\mathrm{.}8& 3\mathrm{.}0\\ 5\mathrm{.}8& 2\mathrm{.}5\\ 6\mathrm{.}5& 3\mathrm{.}5\\ 5\mathrm{.}0& 4\mathrm{.}0\\ 5\mathrm{.}5& 3\mathrm{.}5\\ 6\mathrm{.}2& 3\mathrm{.}0\end{array}\right]$

Figure $1$: Scatter plot of dataset and the initialized centers of $3$ clusters.

$($a$)[10$ pts